Shatter functions with polynomial growth rates

2017/01/23 by Bukh, Boris, Goaoc, Xavier
#05D05 #52C99 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.06632

Abstract

We study how a single value of the shatter function of a set system restricts its asymptotic growth. Along the way, we refute a conjecture of Bondy and Hajnal which generalizes Sauer's Lemma.

Related

• On the shatter function of semilinear set systems
• Shattering-extremal set systems of small VC-dimension
• Shattering-extremal set systems from Sperner families
• Set Systems and Families of Permutations with Small Traces
• Shattering-extremal set systems of VC dimension at most 2