# Set Systems and Families of Permutations with Small Traces

2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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

Cited literature [29 references]

https://hal.inria.fr/hal-00752064
Contributor : Xavier Goaoc Connect in order to contact the contributor
Submitted on : Wednesday, November 14, 2012 - 5:18:59 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:19 AM
Long-term archiving on: : Saturday, December 17, 2016 - 10:44:04 AM

### File

SetSystemsSmallTraces.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00752064, version 1

### Citation

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