inria-00441376, version 2
Set Systems and Families of Permutations with Small Traces
Otfried Cheong 1Xavier Goaoc
2Cyril Nicaud 3
N° RR-7154 (2009)
Résumé : 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 \ge i \ge 0$ the shatter function $f_R$ of a set system $([n],R)$ satisfies $f_R(b) < 2^i(b-i+1)$ then $|R| = O(n^i)$; 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.
- 1 : Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] (KAIST)
- Korea Advanced Institute of Science and Technology
- 2 : VEGAS (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 3 : Laboratoire d'Informatique Gaspard-Monge (LIGM)
- Université Paris Est Marne-la-Vallée – ESIEE – Ecole des Ponts ParisTech – Fédération de Recherche Bézout – CNRS : UMR8049
- Domaine : Informatique/Géométrie algorithmique
- Mots-clés : Set systems – VC dimension – Sauer Lemma – Permutation pattern
- Référence interne : RR-7154
- Versions disponibles : v1 (15-12-2009) v2 (17-12-2009)
- inria-00441376, version 2
- http://hal.inria.fr/inria-00441376
- oai:hal.inria.fr:inria-00441376
- Contributeur : Xavier Goaoc
- Soumis le : Jeudi 17 Décembre 2009, 18:22:25
- Dernière modification le : Jeudi 17 Décembre 2009, 21:04:12
Documents associés
Exporter