Decomposition horizons: from graph sparsity to model-theoretic dividing lines
share
Let 𝒞 be a hereditary class of graphs. Assume that for every p there is a hereditary NIP class 𝒟_p with the property that the vertex set of every graph G∈𝒞 can be partitioned into N_p=N_p(G) parts in such a way that the union of any p parts induce a subgraph in 𝒟_p and log N_p(G)∈ o(log |G|). We prove that 𝒞 is (monadically) NIP. Similarly, if every 𝒟_p is stable, then 𝒞 is (monadically) stable. Results of this type lead to the definition of decomposition horizons as closure operators. We establish some of their basic properties and provide several further examples of decomposition horizons.
READ FULL TEXT
