Combinatorics Seminar

When: Sunday, March 11, 10am

Where: Schreiber 309

Speaker: Misha Tyomkyn, Tel Aviv University

Title: Edge-statistics on large graphs


The inducibility of a graph H measures, how many induced copies of H a large graph G can have. Generalizing this notion, we study, how many induced graphs of a fixed order k and size \ell a large graph G can have.
We conjecture that when 0<\ell<\binom{k}{2} the corresponding density is at most 1/e+o(1), which would be tight for some values of \ell. >


In support of our conjecture we prove that for all (k,ell) the above quantity is bounded away from 1 by an absolute constant. Furthermore, in many ranges of $\ell$ we establish stronger bounds. In particular, we prove the conjecture for `most' values (k,\ell).
We raise a number of open questions.



Joint work with Noga Alon and Dan Hefetz