Decomposition horizons: from graph sparsity to model-theoretic dividing lines
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