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
| Identifer | oai:union.ndltd.org:asu.edu/item:8895 |
| Date | January 2011 |
| Contributors | Kamat, 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 Sets | Arizona State University |
| Language | English |
| Detected Language | English |
| Type | Doctoral Dissertation |
| Format | 100 pages |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, All Rights Reserved |
Page generated in 0.0018 seconds