Set Systems and Families of Permutations with Small Traces

Otfried Cheong (1) , Xavier Goaoc (2) , Cyril Nicaud (3)

1 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
3 LIGM - Laboratoire d'Informatique Gaspard-Monge

Let F be a family of permutations on [n] = {1, . . . , n} and let Y = {y1 , . . . , ym } ⊆ [n], with y1 < y2 < . . . < ym . The restriction of a permutation σ on [n] to Y is the permutation σ|Y on [m] such that σ|Y (i) < σ|Y (j) if and only if σ(yi ) < σ(yj ); the restriction of F to Y is F|Y = {σ|Y | σ ∈ F }. Marcus and Tardos proved the well-known conjecture of Stanley and Wilf that for any permutation τ on [m] there is a constant c such that if no permutation in F admits τ as a restriction then F has size O(c^n ). In the same vein, Raz proved that there is a constant C such that if the restriction of F to any triple has size at most 5 (regardless of what these restrictions are) then F has size at most C^n . In this paper, we consider the following natural extension of Raz's question: assuming that the restriction of F to any m-element subset in [n] has size at most k, how large can F be? We first investigate a similar question for set systems. A set system on X is a collection of subsets of X and the trace of a set system R on a subset Y ⊆ X is the collection R|Y = {e ∩ Y | e ∈ R}. For finite X, we show that if for any subset Y ⊂ X of size b the size of R|Y is smaller than 2i (b − i + 1) for some integer i then R consists of O(|X|i ) sets. This generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We show that in certain situations, bounding the size of R knowing the size of its restriction on all subsets of small size is equivalent to Dirac-type problems in extremal graph theory. In particular, this yields bounds with non-integer exponents on the size of set systems satisfying certain trace conditions. We then map a family F of permutations on [n] to a set system R on the pairs of [n] by associating each permutation to its set of inversions. Conditions on the number of restrictions of F thus become conditions on the size of traces of R. Our generalization of Sauer's Lemma and bounds on certain Dirac-type problems then yield a delineation, in the (m, k)-domain, of the main growth rates of F as a function of n.

Domaines: Géométrie algorithmique [cs.CG]

Otfried Cheong, Xavier Goaoc, Cyril Nicaud. Set Systems and Families of Permutations with Small Traces. European Journal of Combinatorics, 2013, 34, pp.229-239. ⟨hal-00752064⟩