Hereditary graph families with exotic typical structure
Hereditary graph families with exotic typical structure
-
Sergey Norin, McGill University
A graph听is听H-free if it does not contain an induced subgraph isomorphic to听H. The study of the typical structure of听H-free graphs was initiated by Erd艖s, Kleitman and Rothschild, who have shown that almost all听triangle-free graphs are bipartite. Since then the typical structure of听H-free graphs has been determined for several families of graphs听, including complete graphs, trees and cycles. Recently, Reed and Scott proposed a conjectural description of the typical structure of听H-free graphs for all graphs, which extends all previously known results in the area.听听
We will discuss a听 construction of an infinite family of graphs H for which听the Reed-Scott conjecture fails, and several related results.听
Based on joint work with Yelena Yuditsky.