Set Systems and Families of Permutations with Small Traces

2009/12/15 by Cheong, Otfried, Goaoc, Xavier, Nicaud, Cyril
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0912.2979

Abstract

We study the maximum size of a set system on n elements whose trace on any b elements has size at most k. We show that if for some b ≥ i ≥ 0 the shatter function f_R of a set system ([n],R) satisfies f_R(b) < 2ⁱ(b-i+1) then |R| = O(nⁱ); this generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We use this bound to delineate the main growth rates for the same problem on families of permutations, where the trace corresponds to the inclusion for permutations. This is related to a question of Raz on families of permutations with bounded VC-dimension that generalizes the Stanley-Wilf conjecture on permutations with excluded patterns.

Related

• Shattering-extremal set systems of small VC-dimension
• Shattering-extremal set systems of VC dimension at most 2
• Small families of partially shattering permutations
• Shattering k-sets with Permutations
• Shatter functions with polynomial growth rates