Elementary Techniques for Erdos-Ko-Rado-like Theorems

2008/08/06 by Greg Brockman, Brockman, Greg, Bill Kay +1
Computer Science · Engineering · Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05D05

paper · pdf · doi:10.48550/arxiv.0808.0774

10 pages, 0 figures

openalex publication_date 2008/08/06 · arxiv created 2008/08/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The well-known Erdos-Ko-Rado Theorem states that if F is a family of k-element subsets of 1,2,...,n (n>2k-1) such that every pair of elements in F has a nonempty intersection, then |F| is at most \binomn-1k-1. The theorem also provides necessary and sufficient conditions for attaining the maximum. We present elementary methods for deriving generalizations of the Erdos-Ko-Rado Theorem on several classes of combinatorial objects. We also extend our results to systems under Hamming intersection.

Citations

• On a Problem of Formal Logic

Related

• On a d-degree Erdős-Ko-Rado Theorem
• A Common Generalization of the Theorems of Erdős-Ko-Rado and Hilton-Milner
• Algebraic approach to stability results for Erdős-Ko-Rado theorem
• A remark on the t-intersecting Erdős-Ko-Rado theorem
• Intersection theorems for families of matchings of complete k-partite k-graphs