## 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^{-h1/3}))h!/(h^{h}-h).