Set systems and families of permutations with small traces

Abstract

Let F be a family of permutations on [n] = {1. . . . . n} and let Y = {y(1) . . . . . y(m)} subset of [n], with y(1) < y(2) < . . . < y(m). The restriction of a permutation sigma on [n] to Y is the permutation sigma(vertical bar Y) on [m] such that sigma(vertical bar Y) (i) < sigma(vertical bar Y) (j) if and only if sigma (y(i)) < sigma (y(j)): the restriction of F to Y is F-vertical bar Y = {sigma(vertical bar Y) vertical bar sigma is an element of F}. Marcus and Tardos proved the well-known conjecture of Stanley and Will that for any permutation tau on [m] there is a constant c such that if no permutation in F admits tau 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 subset of X is the collection R-vertical bar Y = {e boolean AND Y vertical bar e is an element of R}. For finite X, we show that if for any subset Y subset of X of size b the size of R-vertical bar Y is smaller than 2(i)(b - i + 1) for some integer i then R consists of O(vertical bar X vertical bar(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. (c) 2012 Elsevier Ltd. All rights reserved.