Online talk: Yelena Yuditsky

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.