Set Systems and Families of Permutations with Small Traces

Details Set Systems and Families of Permutations with Small Traces Set Systems and Families of Permutations with Small Traces

2009-12-15

arxiv.org/abs/0912.2979v2

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Set Systems and Families of Permutations with Small Traces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Set Systems and Families of Permutations with Small Traces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set Systems and Families of Permutations with Small Traces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306351