2026-05-24T05:25:41Zhttps://keep.lib.asu.edu/oai/request

oai:keep.lib.asu.edu:node-1495992024-12-20T18:25:12Zoai_pmh:alloai_pmh:repo_items

149599 https://hdl.handle.net/2286/R.I.8895 http://rightsstatements.org/vocab/InC/1.0/ All Rights Reserved 2011 viii, 92 p. : ill Doctoral Dissertation Academic theses Text eng Kamat, Vikram M Hurlbert, Glenn Colbourn, Charles Czygrinow, Andrzej Fishel, Susanna Kierstead, Henry Arizona State University Partial requirement for: Ph. D., Arizona State University, 2011 Includes bibliographical references (p Field of study: Mathematics 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. Mathematics chordal graphs chvatal's conjecture cross-intersecting families independent sets intersecting families stability analysis Extremal problems (Mathematics) Combinatorial analysis Erdős-Ko-Rado theorems: new generalizations, stability analysis and Chvátal's Conjecture