Mon, August 10, 3pm ET (8pm BST, 7am Tue NZST)
Yelena Yuditsky, Ben-Gurion University
Typical structure of hereditary graph families
Youtube
Abstract:
A family of graphs $\cal F$ is hereditary if it is closed under isomorphism and taking induced subgraphs. For example, for a given graph $H$, a hereditary family is the family of all $H$-free graphs, that is graphs without an induced copy of $H$.
Alon, Balogh, Bollobás and Morris showed that for every hereditary family $\cal F$ there exist $\epsilon >0$ and $l\in \mathbb{N}$ such that the number of graphs in $\cal F$ on $n$ vertices is $2^{(1-1/l)n^2/2+o(n^{2-\epsilon})}$. They showed this bound by deriving various structural properties of almost all graphs in $\cal F$. We study and obtain additional structural properties of almost all graphs in some restricted hereditary families. As an application of our results, we prove the existence of an infinite family of counterexamples for the recent Reed-Scott conjecture about the structure of almost all $H$-free graphs.
This is a joint work with Segey Norin.