Return to search

Erdos--Ko--Rado Theorems: New Generalizations, Stability Analysis and Chvatal's Conjecture

abstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma. / Dissertation/Thesis / Ph.D. Mathematics 2011

Identiferoai:union.ndltd.org:asu.edu/item:8895
Date January 2011
ContributorsKamat, Vikram Mahendra (Author), Hurlbert, Glenn (Advisor), Colbourn, Charles (Committee member), Czygrinow, Andrzej (Committee member), Fishel, Susanna (Committee member), Kierstead, Henry (Committee member), Arizona State University (Publisher)
Source SetsArizona State University
LanguageEnglish
Detected LanguageEnglish
TypeDoctoral Dissertation
Format100 pages
Rightshttp://rightsstatements.org/vocab/InC/1.0/, All Rights Reserved

Page generated in 0.0021 seconds