Submission date: 18 September 2022

Abstract:

Call a hereditary family F of graphs strongly persistent if there exists a graphon W such that in all subgraphons W' of W, F is precisely the class of finite graphs that have positive density in W'.
The first result of the paper is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. In fact, we prove an analogous characterization for the natural extension of these properties to structures in finite relational languages.
We call graphons (or more generally theons) with the self-similarity property above weakly random. Weak randomness can be seen as a weakening of graph quasirandomness: while the latter requires densities of any finite graph to be the same in any subgraphon, the former only requires the set of finite graphs with positive density to be invariant across subgraphons. A hereditary family F is said to have the weakly random Erdős-Hajnal property (WR) if every graphon that is a limit of graphs in F has a weakly random subgraphon; this includes as a special case the approximate Erdős-Hajnal property (AEHP), where the subgraphon is required to be an almost clique or almost anti-clique. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with few prime graphs.
The classes AEHP and WR can be seen as measuring the complexity of hereditary families in terms of structural variation in their limit objects (here specifically in terms of unavoidable sub-objects), and this work can be seen as initiating a classification theory for hereditary families of finite structures.

Mathematics Subject Classification: Primary: 05C80, Secondary: 05C75, 03C13, 05C65, 28A35

Keywords and phrases:

Full text arXiv 2209.08638: pdf, ps.