Erdös–Ko–Rado Theorem—22 Years Later

DOI10.1137/0604042zbMath0526.05001OpenAlexW2012908763WikidataQ105699215 ScholiaQ105699215MaRDI QIDQ3041202

Peter Frankl, Michel Marie Deza

Publication date: 1983

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0604042

zbMATH Keywords

family of subsetsErdős-Ko-Rado theoremexpository paperset-systems

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Hypergraphs (05C65) Permutations, words, matrices (05A05)

Related Items

Modular and fractional \(L\)-intersecting families of vector spaces, The maximum product of sizes of cross-intersecting families, Erdős-Ko-Rado type theorems for simplicial complexes, Intersecting families in \(\begin{pmatrix}[m\\ \ell\end{pmatrix}\cup\begin{pmatrix}[n]\\ k\end{pmatrix}\)], The Erdős-Ko-Rado theorem for vector spaces, Intersection theorems under dimension constraints, The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities, Intersecting \(k\)-uniform families containing a given family, Size and structure of large \((s,t)\)-union intersecting families, On regular 3-wise intersecting families, Upper bounds for \(s\)-distance sets and equiangular lines, A common generalization to theorems on set systems with \(\mathcal L\)-intersections, An analogue of the Erdős-Ko-Rado theorem for the distance-regular graphs of bilinear forms, Independence numbers and chromatic numbers of the random subgraphs of some distance graphs, Some intersection theorems for ordered sets and graphs, Some greedy \(t\)-intersecting families of finite sequences, A Group-Theoretic Setting for Some Intersecting Sperner Families, Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture, Proof of a conjecture of Frankl and Füredi, The maximum sum of sizes of cross-intersecting families of subsets of a set, On intersecting families of independent sets in trees, On Intersecting Chains in Boolean Algebras, On Chvàtal's conjecture and a conjecture on families of signed sets, Non-trivial intersecting uniform sub-families of hereditary families, A Hilton-Milner-type theorem and an intersection conjecture for signed sets, Cross-Intersecting Families of Vectors, Approximation by juntas in the symmetric group, and forbidden intersection problems, Nontrivial t-Intersecting Families for Vector Spaces, A semidefinite programming approach to a cross-intersection problem with measures, Cross-intersecting subfamilies of levels of hereditary families, Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set, A short proof of an Erdős-Ko-Rado theorem for compositions, An Erdős-Ko-Rado theorem for the derangement graph of PGL(\(2,q\)) acting on the projective line, On the Holroyd-Talbot conjecture for sparse graphs, Cross-intersecting non-empty uniform subfamilies of hereditary families, On \(q\)-analogues and stability theorems, Integer sequences without singleton intersection, Set Systems with L-Intersections and k-Wise L-Intersecting Families, Uniform hypergraphs under certain intersection constraints between hyperedges, The maximum product of weights of cross-intersecting families, Erdös-Ko-Rado theorems for a family of trees, The Erdős-Ko-Rado theorem for finite affine spaces, A new short proof of the EKR theorem, On the star of the family of independent sets in a graph, Families of vector spaces with \(r\)-wise \(\mathcal{L}\)-intersections, Intersecting Families in Symmetric Unions of Direct Products of Set Families, A proof of Frankl–Kupavskii's conjecture on edge‐union condition, Erdős-Ko-Rado theorems for chordal graphs and trees, Anzahl formulas of subspaces in symplectic spaces and their applications, Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas, Extremal problems under dimension constraints., Erdős-Ko-Rado theorems in certain semilattices, Shadows and intersections in vector spaces, The Erdős-Ko-Rado theorem for singular linear spaces, On independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\): estimates, conjectures, and applications to the Nelson-Erdős-hadwiger problem and the borsuk problem, Maximum hitting of a set by compressed intersecting families, Erdös-Ko-Rado theorem for ladder graphs, Rainbow matchings in properly-colored hypergraphs, Erdős-Ko-Rado theorems for permutations and set partitions, On the stability of the Erdös-Ko-Rado theorem, The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations, Intersecting faces of a simplicial complex via algebraic shifting, The edge-diametric theorem in Hamming spaces, A sharp bound for the product of weights of cross-intersecting families, New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems, Erdős-Ko-Rado theorems of labeled sets, The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective space, Cross-intersecting families of permutations, Multiple cross-intersecting families of signed sets, Cross \(\mathcal L\)-intersecting families on set systems, An Erdős-Ko-Rado theorem for unions of length 2 paths, Intersecting antichains and shadows in linear lattices, Unnamed Item, An Erdős-Ko-Rado theorem for restricted signed sets, Intersecting families, signed sets, and injection, Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs, Compression and Erdős-Ko-Rado graphs, Graphs with the Erdős-Ko-Rado property, Forbidden Intersections, Stability versions of Erdős-Ko-Rado type theorems via isoperimetry, Extremal \(G\)-free induced subgraphs of Kneser graphs, The maximum sum and the maximum product of sizes of cross-intersecting families, A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations, Around Borsuk's hypothesis, Strongly intersecting integer partitions, On \(t\)-intersecting families of signed sets and permutations, A short proof of Talbot's theorem for intersecting separated sets, A generalization of Fisher's inequality, The Erdős-Ko-Rado properties of various graphs containing singletons, The Erdős-Ko-Rado properties of set systems defined by double partitions, A cross‐intersection theorem for subsets of a set, \(r\)-cross \(t\)-intersecting families for vector spaces, On complete multipartite derangement graphs, Cross-intersecting families of vectors, The Edge-Diametric Theorem in Hamming Spaces, The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An inequality for finite permutation groups
• On Sperner families in which no k sets have an empty intersection
• On set intersections
• A finite set intersection theorem
• Extremal problems and coverings of the space
• On Sperner families in which no k sets have an empty intersection. II
• An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
• Intersection theorems with geometric consequences
• The proof of a conjecture of G. O. H. Katona
• Intersection theorems for systems of finite vector spaces
• On Sperner families satisfying an additional condition
• On t-designs
• On the maximum number of permutations with given maximal or minimal distance
• Families of finite sets satisfying a union condition
• Extremal problems among subsets of a set
• Erdős-Ko-Rado from Kruskal-Katona
• A simple proof of the Erdős-Chao Ko-Rado theorem
• A generalization of the Erdős-Ko-Rado theorem on finite set systems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Some Properties of Perfect Matroid Designs
• A General Intersection Theorem For Finite Sets
• Families of finite sets with prescribed cardinalities for pairwise intersections
• Families of finite sets satisfying an intersection condition
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Extensions of the Erdös-Ko-Rado Theorem
• Generalizations of theorems of Katona and Milner
• On families of finite sets no two of which intersect in a singleton
• Intersection Properties of Systems of Finite Sets
• The Erdös-Ko-Rado Theorem for Integer Sequences
• ANALOGUES OF A THEOREM OF ERDÖS, KO, AND RADO ON A FAMILY OF FINITE SETS
• Intersection theorems for systems of finite sets
• On a combinatorial conjecture of Erdös
• A Combinatorial Theorem on Systems of Sets
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• A generalization of a combinatorial theorem of macaulay
• A bound on lightweight sequences with application to definite decoding (Corresp.)
• Maximal number of subsets of a finite set No k of which are pairwise disjoint
• On intersecting families of finite sets