DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Goaoc, Xavier | ko |
dc.contributor.author | Nicaud, Cyril | ko |
dc.date.accessioned | 2013-03-04T06:46:05Z | - |
dc.date.available | 2013-03-04T06:46:05Z | - |
dc.date.created | 2012-12-31 | - |
dc.date.created | 2012-12-31 | - |
dc.date.issued | 2013-02 | - |
dc.identifier.citation | EUROPEAN JOURNAL OF COMBINATORICS, v.34, no.2, pp.229 - 239 | - |
dc.identifier.issn | 0195-6698 | - |
dc.identifier.uri | http://hdl.handle.net/10203/81927 | - |
dc.description.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. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD | - |
dc.subject | GEOMETRIC PERMUTATIONS | - |
dc.subject | NUMBERS | - |
dc.subject | GRAPHS | - |
dc.title | Set systems and families of permutations with small traces | - |
dc.type | Article | - |
dc.identifier.wosid | 000311813300006 | - |
dc.identifier.scopusid | 2-s2.0-84867138319 | - |
dc.type.rims | ART | - |
dc.citation.volume | 34 | - |
dc.citation.issue | 2 | - |
dc.citation.beginningpage | 229 | - |
dc.citation.endingpage | 239 | - |
dc.citation.publicationname | EUROPEAN JOURNAL OF COMBINATORICS | - |
dc.identifier.doi | 10.1016/j.ejc.2012.06.007 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Goaoc, Xavier | - |
dc.contributor.nonIdAuthor | Nicaud, Cyril | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | GEOMETRIC PERMUTATIONS | - |
dc.subject.keywordPlus | NUMBERS | - |
dc.subject.keywordPlus | GRAPHS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.