2016/08/27 by Vadim Lozin, Lozin, Vadim
Computer Science · Decision Sciences · Mathematics · #05 Combinatorics #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1608.07727
openalex publication_date 2016/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The speed of a hereditary property P is the number Pn of n-vertex labelled graphs in P. It is known that the rates of growth of Pn constitute discrete layers and the speed jumps, in particular, from constant to polynomial, from polynomial to exponential and from exponential to factorial. One more jump occurs when the entropy limn→∞\fraclog2 Pn\binomn2 changes from 0 to a nonzero value. In the present paper, for each of these jumps we identify a graph parameter responsible for it, i.e. we show that a jump of the speed coincides with a jump of the respective parameter from finitude to infinity. In particular, we show that the speed of a hereditary property P is sub-factorial if and only if the neighbourhood diversity of graphs in P is bounded by a constant, and that the entropy of a hereditary property P is 0 if and only if the VC-dimension of graphs in P is bounded by a constant. All the result are obtained by Ramsey-type arguments.