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.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2013, 34, pp.229-239. 〈http://www.sciencedirect.com/science/article/pii/S0195669812001072〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00752064
Contributeur : Xavier Goaoc <>
Soumis le : mercredi 14 novembre 2012 - 17:18:59
Dernière modification le : mardi 25 octobre 2016 - 16:59:10
Document(s) archivé(s) le : samedi 17 décembre 2016 - 10:44:04

Fichier

SetSystemsSmallTraces.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 〈http://www.sciencedirect.com/science/article/pii/S0195669812001072〉. 〈hal-00752064〉

Partager

Métriques

Consultations de
la notice

508

Téléchargements du document

307