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

Abstract:

The number of induced copies of a graph H in a graph G is denoted by i_H(G). Let i_H(n) denote the maximum of i_H(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 a_i + \sum_{i=1}^h g(a_i,h), where \sum_{i=1}^h a_i = n and the a_i 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 i_H(n)=g(n,h) for all n≤ 2^√h. Furthermore, all extremal n-vertex graphs yielding i_H(n) in the aforementioned range are determined.

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

It is known that i_H≥ h!/(h^h-h) for all graphs H, and that a random graph H satisfies almost surely that i_H ≤ h^{3log h}h!/(h^h-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 i_H =(1+o(h^{-h^1/3}))h!/(h^h-h).