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.