Premium
An intersection theorem for systems of sets
Author(s) -
Kostochka A. V.
Publication year - 1996
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/(sici)1098-2418(199608/09)9:1/2<213::aid-rsa13>3.0.co;2-o
Subject(s) - cardinality (data modeling) , intersection (aeronautics) , combinatorics , mathematics , upper and lower bounds , discrete mathematics , intersection theorem , cardinal number (linguistics) , computer science , compactness theorem , brouwer fixed point theorem , fixed point theorem , engineering , mathematical analysis , data mining , aerospace engineering , linguistics , philosophy
Erdõs and Rado defined a Δ‐system, as a family in which every two members have the same intersection. Here we obtain a new upper bound on the maximum cardinality ϕ( n, q ) of an n ‐uniform family not containing any Δ‐system of cardinality q. Namely, we prove that, for any α > 1 and q, there exists C = C (α, q ) such that, for any n, $$\varphi(n,q)\leq C n! \left({{(\log \log \log n)^2}\over{\alpha \log \log n}}\right)^n .$$ © 1996 John Wiley & Sons, Inc.