On the representing number of intersecting families
type: Item
instance of: scholarly article
title: On the representing number of intersecting families
zbMATH Open document ID: 0629.05006
DOI: 10.1007/BF01200473
author: Martin Aigner
author: D. Grieser
author: P. Erdős
published in: Archiv der Mathematik
publication date: 1987-01-01T00:00:00Z
review text: The paper presents a generalization of well-known results: Theorems of Erdős-Ko-Rado (1961) and Hilton-Milner (1967). Let \({\mathcal M}\) be a family of sets, and \(R\) a single set. \(R\) is said to represent \({\mathcal M}\) or be a representing set for \({\mathcal M}\) if \(R\cap X\neq 0\) for all \(X\in {\mathcal M}\) has representing number \(r\) if \(r\) is the cardinality of a smallest set representing. Let \(\begin{pmatrix} M \\ k\end{pmatrix}\) 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 \({\mathcal M}\subseteq \begin{pmatrix} M \\ k\end{pmatrix}\) 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: \textit{I. Anderson} and \textit{A. J. W. Hilton}, The Erdős-Ko-Rado theorem with valency conditions, Q. J. Math., Oxf. II. Ser. 37, 385-390 (1986; Zbl 0619.05037).
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 4023287
zbMATH Keywords: extremal set theory
zbMATH Keywords: family of subsets
zbMATH Keywords: family of sets
zbMATH Keywords: intersection
Wikidata QID: Q105659295
MaRDI profile type: Publication
cites work: Intersection Theorems for Systems of Sets
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Erdős-Ko-Rado from Kruskal-Katona
cites work: On intersecting families of finite sets
cites work: Q3218170
cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: A simple proof of the Erdős-Chao Ko-Rado theorem
cites work: The exact bound in the Erdős-Ko-Rado theorem
full work available at URL: https://doi.org/10.1007/bf01200473
OpenAlex ID: W2160174869
description: scientific article; zbMATH DE number 4023287