×

zbMATH — the first resource for mathematics

Beyond the Erdős-Ko-Rado theorem. (English) Zbl 0742.05080
\([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 P. Erdős, Chao Ko and 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”.

MSC:
05D05 Extremal set theory
05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] {\scB. Cooper}, unpublished manuscript.
[2] Delsarte, P, An algebraic approach to the association schemes in coding theory, Philips res. rep. suppl., 10, (1973) · Zbl 1075.05606
[3] Erdős, P.L; Frankl, P; Katona, G.O.H, Extremal hypergraph problems and convex hulls, Combinatorica, 5, 11-26, (1985) · Zbl 0579.05033
[4] Erdős, P; Ko, C; Rado, R, Intersection theorems for systems of finite sets, Quart. J. math. Oxford ser. (2), 12, 313-320, (1961) · Zbl 0100.01902
[5] Frankl, P; Frankl, P, The erdős-ko-Rado theorem is true for n = ckt, (), 365-375, Keszthely · Zbl 0401.05001
[6] Hsieh, W.N, Intersection theorems for systems of finite vector spaces, Discrete math., 12, 1-16, (1975) · Zbl 0311.05001
[7] {\scM. Hujter}, unpublished manuscript.
[8] Lovász, L, On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1-7, (1979) · Zbl 0395.94021
[9] Schrijver, A, Association schemes and the Shannon capacity: eberlein polynomials and the erdős-ko-Rado theorem, (), 671-688, Szeged, Hungary, 1978
[10] Wilson, R.M, The exact bound in the erdős-ko-Rado theorem, Combinatorica, 4, 247-257, (1984) · Zbl 0556.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.