On the number of types in sparse graphs

摘要: We prove that for every class of graphs l which is nowhere dense, as defined by Nesetril and Ossona de Mendez [28, 29], first order formula φ(x, y), whenever one draws a graph G ∈ subset its nodes A, the number subsets A|y| are form {u A|y|: |= φ(u, v)} some valuation u x in bounded O(|A||x|e), e > 0. This provides optimal bounds on VC-density first-order definable set systems dense classes. also give two new proofs upper quantities classes relevant their logical treatment. Firstly, we provide proof fact uniformly quasi-wide, implying explicit, polynomial functions relating notions. Secondly, combinatorial result Adler [1] stating stable. In contrast to previous above results, our completely finitistic constructive, yield explicit computable related uniform quasi-wideness (margins) stability (ladder indices).