Submission date: 15 September 2022

Abstract:

Let C be a hereditary class of graphs. Assume that for every p there is a hereditary NIP class D_p with the property that the vertex set of every graph G ∈ C 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 D_p and log N_p(G) ∈ o(log |G|). We prove that C is (monadically) NIP. Similarly, if every D_p is stable, then C 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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2209.11229: pdf, ps.