Beyond the Erdős-Ko-Rado theorem (Q1174149): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(91)90031-b / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2102524299 / rank | |||
Normal rank |
Latest revision as of 10:59, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Beyond the Erdős-Ko-Rado theorem |
scientific article |
Statements
Beyond the Erdős-Ko-Rado theorem (English)
0 references
25 June 1992
0 references
\([n]\) denotes the set \(\{1,2,\ldots,n\}\); for any set \(S\), \(\binom{S}{k}\) denotes the set of its \(k\)-subsets; \(n_r(k,t)\) is defined to be \((k - t+1)\left(2+ \frac{t-1}{r+1}\right)\); \(\mathcal A_r\) is the set \(\left\{F\in \binom{[n]}{k}: | F\cap[t+2r]|\geq t+r\right\}\). A \(t\)-intersecting family over \([n]\) is a set of subsets of \([n]\) that intersect pairwise in at least \(t\) points. The first author has conjectured that: Conjecture 2.1. If \(\mathcal F\) is of maximum cardinality, then \({\mathcal F}={\mathcal A}_r\) for some \(r\). ``We prove Conjecture 2.1 for \(n>(k-t+1)c\sqrt{t/\log t}:\) Theorem 2.4. Suppose that \(\mathcal F\) is a \(t\)-intersecting family over \([n]\) of maximal cardinality. Suppose further that \(n\) is in the range \(n_r(k,t)\leq n\leq(k-t+1)\left(2+\frac{t-1}{r}\right)\), and \(t\geq 1+cr(r+1)/(1+\log r)\). Then \(\mathcal F\) is ismorphic to \({\mathcal A}_r\) (or to \({\mathcal A}_{r+1}\) in the case \(n=n_r(k,t))\). The proof is elementary. It uses the so-called `shifting' operation, introduced by \textit{P. Erdős}, \textit{Chao Ko} and \textit{R. Rado} in ``Intersection theorems for systems of finite sets'' [Q. J. Math., Oxf. II. Ser. 12, 313--320 (1961; Zbl 0100.01902)]. We follow the line of the first author, ``The Erdős-Ko-Rado Theorem is true for \(n = ckt\)'' [Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 365--375 (1978; Zbl 0401.05001)], where several properties of the shifted families were proved''.
0 references