# 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 : 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.
Mots-clés :
Document type :
Reports

Cited literature [18 references]

https://hal.inria.fr/inria-00441376
Contributor : Xavier Goaoc <>
Submitted on : Thursday, December 17, 2009 - 6:22:25 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Thursday, September 23, 2010 - 11:06:35 AM

### Files

RR-7154.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00441376, version 2
• ARXIV : 0912.2979

### Citation

Otfried Cheong, Xavier Goaoc, Cyril Nicaud. Set Systems and Families of Permutations with Small Traces. [Research Report] RR-7154, INRIA. 2009, pp.14. ⟨inria-00441376v2⟩

Record views