Combinatorics Seminar

When: Sunday, October 29, 10am
Where: Schreiber 309
Speaker: Raphael Yuster, University of Haifa
Title: On the exact maximum induced density of almost all graphs and their inducibility


The number of induced copies of a graph H in a graph G is denoted by iH(G). Let iH(n) denote the maximum of iH(G) taken over all graphs G with n vertices (this is the well-known parameter of maximum induced density).

Let g(n,h) = \prod{i=1}^h ai + \sum_{i=1}^h g(ai,h), where \sum_{i=1}^h ai = n and the ai are as equal as possible.

It is proved that for almost all graphs H on h vertices (and in particular, for a typical/random graph) it holds that iH(n)=g(n,h) for all n≤ 2√h. Furthermore, all extremal n-vertex graphs yielding iH(n) in the aforementioned range are determined.

Another well-studied graph parameter is the inducibility of H which is iH = limn →∞ iH(n)/\binom{n}{h}.

It is known that iH≥ h!/(hh-h) for all graphs H, and that a random graph H satisfies almost surely that iH ≤ h3log hh!/(hh-h). The result above implies an improvement upon this upper bound, almost matching the lower bound. It is shown that for almost all graphs H, it holds that iH =(1+o(h-h1/3))h!/(hh-h).