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