Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  629.05006
Autor:  Aigner, M.; Erdös, Paul; Grieser, D.
Title:  On the representing number of intersecting families. (In English)
Source:  Arch. Math. 49, 114-118 (1987).
Review:  The paper presents a generalization of well-known results: Theorems of Erdös-Ko-Rado (1961) and Hilton-Milner (1967). Let M be a family of sets, and R a single set. R is said to represent M or be a representing set for M if R\cap X\ne 0 for all X in M has representing number r if r is the cardinality of a smallest set representing. Let \pmatrix M \\ k\endpmatrix denote the collection of all k-subsets of a finite set. A family is intersecting if any two members of it have a non-trivial intersection. Theorem. Denote by g(n; r,k) the maximal cardinality of an intersecting family M\subseteq \pmatrix M \\ k\endpmatrix of an n-set with representing number r, 1 \leq r \leq k \leq n. Then there are constants cr,k, Cr,k only depending on r and k, such that cr,knk-r \leq g(n; r,k) \leq Cr,knk-r. The precise value of g(n; i,k) = \binom{n-1}{k-1} and g(n; 2,k) = \binom{n-1}{k-1}-\binom{n-k-1}{k-1} are given by Theorems Erdös-Ko-Rado and Hilton-Milner, correspondingly. Some estimations of g(k) = g(n; k,k), which for n \geq n0(k) is independent of n, are obtained. The authors put the following questions: first, improve the bounds on g(k), second, estimate the value of n0(k). See also: I. Anderson and A. J. W. Hilton, The Erdös-Ko-Rado theorem with valency conditions, Q. J. Math., Oxf. II. Ser. 37, 385-390 (1986; Zbl 619.05037).
Reviewer:  Yu.M.Voloshin
Classif.:  * 05A17 Partitions of integres (combinatorics)
                   05A05 Combinatorial choice problems
                   04A20 Combinatorial set theory
Keywords:  extremal set theory; family of subsets; family of sets; intersection
Citations:  Zbl 619.05037

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page