Talk information

Date: Sunday, October 18, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Raphael Yuster (University of Haifa)
Title: Induced Subgraph Densities: Forcing and Implication

Abstract:

We discuss two basic, seemingly unrelated questions concerning induced subgraph densities, and show that they are closely connected.

The forcing problem asks whether knowing that the induced densities of a few fixed graphs agree with those expected in a random graph $G(n,p)$ is enough to guarantee quasirandomness. The implication problem asks when a positive induced density of one graph necessarily implies a positive induced density of another.

We give a complete characterization of induced-density implication in terms of a combinatorial embedding condition. Interestingly, we show that two distinct graphs can imply each other, and investigate the structure of such “density twins”.

We then use these results, together with additional ideas, to establish a surprising contrast with the classical non-induced setting: while pairs of ordinary subgraph counts can force quasirandomness, no pair of induced subgraph counts can do so.

Joint work with Asaf Shapira.