##
**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 c_{r,k}, C_{r,k} only depending on r and k, such that c_{r,k}n^{k-r} \leq g(n; r,k) \leq C_{r,k}n^{k-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 n_{0}(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 n_{0}(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