Skip to Main content Skip to Navigation
Journal articles

Set Systems and Families of Permutations with Small Traces

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download
Contributor : Xavier Goaoc <>
Submitted on : Wednesday, November 14, 2012 - 5:18:59 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Saturday, December 17, 2016 - 10:44:04 AM


Files produced by the author(s)


  • HAL Id : hal-00752064, version 1


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



Record views


Files downloads