Beyond the Erdős-Ko-Rado theorem
\([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.
- Anticlusters and intersecting families of subsets
- A new short proof of the EKR theorem
- The maximum size of 3-wise t-intersecting families
- On the Erdős-Ko-Rado theorem and the Bollobás theorem for t-intersecting families
- scientific article; zbMATH DE number 4029608
- The maximum measure of 3-wise t-intersecting families
- Extending the Erdős-Ko-Rado theorem
- Intersecting k-uniform families containing all the k-subsets of a given set
- A cross‐intersection theorem for subsets of a set
- scientific article; zbMATH DE number 15490
- Extremal hypergraph problems and convex hulls
- scientific article; zbMATH DE number 3775586 (Why is no real title available?)
- scientific article; zbMATH DE number 3621717 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersection theorems for systems of finite vector spaces
- On the Shannon capacity of a graph
- The exact bound in the Erdős-Ko-Rado theorem
- Families intersecting on an interval
- The Erdős-Ko-Rado bound for the function lattice
- More about shifting techniques
- Extremal problems under dimension constraints.
- Erdős-Ko-Rado and Hilton-Milner type theorems for intersecting chains in posets
- On the Erdős-Ko-Rado theorem and the Bollobás theorem for t-intersecting families
- A Bahadur-Kiefer theorem beyond the largest observation
- Beyond the Erdős matching conjecture
- The structure of large non-trivial \(t\)-intersecting families of finite sets
- On strengthenings of the intersecting shadow theorem
- Extremal t-intersecting families for direct products
- Cross-intersecting subfamilies of levels of hereditary families
- Restricted intersecting families on simplicial complex
- On the size of shadow-added intersecting families
- Shattered matchings in intersecting hypergraphs
- AK-type stability theorems on cross t-intersecting families
- The maximum product of sizes of cross-intersecting families
- Intersection theorems under dimension constraints
- Multiply-intersecting families revisited
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Non-trivial t-intersecting families for symplectic polar spaces
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- The maximum product of weights of cross-intersecting families
- Extending the Erdős-Ko-Rado theorem
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- scientific article; zbMATH DE number 91004 (Why is no real title available?)
- A new short proof of the EKR theorem
- Improved Upper Bounds Concerning the Erdős-Ko-Rado Theorem
- An Erdős-Ko-Rado theorem for cross t-intersecting families
- Erdös-Ko-Rado from intersecting shadows
- On Mubayi's conjecture and conditionally intersecting sets
- scientific article; zbMATH DE number 1420985 (Why is no real title available?)
- Union-intersecting set systems
- On the stability of the Erdös-Ko-Rado theorem
- Intersecting faces of a simplicial complex via algebraic shifting
- Nontrivial t-intersecting families for vector spaces
- Around the complete intersection theorem
- Towards extending the Ahlswede-Khachatrian theorem to cross \(t\)-intersecting families
- Erdős-Rado without choice
- On symmetric intersecting families of vectors
- A universal bound concerning \(t\)-intersecting families
- r$r$‐Cross t$t$‐intersecting families via necessary intersection points
- A product version of the Hilton-Milner theorem
- Intersection theorems for \((- 1, 0, 1)\)-vectors
- Non-trivial \(t\)-intersecting separated families
- Some good characterization results relating to the Kőnig-Egerváry theorem
- Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erd\H{o}s and S\'os
- Extremal problems concerning ordered intersections of sets
- Large non-trivial \(t\)-intersecting families of signed sets
- Nearly extremal non-trivial cross t-intersecting families and r-wise t-intersecting families
- Improved bounds concerning the maximum degree of intersecting hypergraphs
- The complete intersection theorem for systems of finite sets
- Non-trivial t-intersecting families for the distance-regular graphs of bilinear forms
- Erdős-Ko-Rado type results for partitions via spread approximations
- Hilton-Milner theorem for k-multisets
- Erdős-Ko-Rado theorem and Hilton-Milner type theorem for k-partitions
- The Erdős-Ko-Rado theorem in _2-norm
- Simplices in t-intersecting families for vector spaces
- Invitation to intersection problems for finite sets
- The exact bound in the Erdős-Ko-Rado theorem
- The maximum size of 3-wise t-intersecting families
- On the measure of intersecting families, uniqueness and stability
This page was built for publication: Beyond the Erdős-Ko-Rado theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174149)
