Premium
On large intersecting subfamilies of uniform setfamilies
Author(s) -
Duke Richard A.,
Erdős Paul,
Rödl Vojtěch
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10098
Subject(s) - subfamily , combinatorics , integer (computer science) , mathematics , intersection (aeronautics) , constant (computer programming) , bounded function , type (biology) , discrete mathematics , computer science , mathematical analysis , biology , ecology , biochemistry , gene , engineering , programming language , aerospace engineering
In an earlier work R. A. Duke and V. Rödl, The Erdős–Ko–Rado theorem for small families, J Combin Theory Ser A 65(2) (1994), 246–251 it was shown that for t a fixed positive integer and κ a real constant, 0 < κ < 1/2, if n is sufficiently large each family of ⌊κ n ⌋‐element subsets of [ n ] of size N (linear in n ) contains a t ‐intersecting subfamily of size at least (1 − o (1))κ N . Here we consider the case when t , the intersection size, is no longer bounded, specifically t = ⌊τ n ⌋ for 0 < τ < κ. We show that for sufficiently large n and N each family of this type contains an r ‐wise t ‐intersecting subfamily of size at least N 1−δ , and that, apart for the size of δ, this result is the best possible. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003