| A Delta-system is a hypergraph with hyperedges A 1,...,Ak such that there is a set K such that if i ≠ j, then Ai ∩ Aj = K. The classical Sunflower Lemma of Erdos and Rado asserts that any r-uniform set system with at least (r -- 1)!kr edges contains a Delta-system with k hyperedges.;In this dissertation, we demonstrate methods based on the Sunflower Lemma used to solve a variety of problems in graph theory.;The first of these problems is one in the field of graph minors. We prove a conjecture of Myers that, for every fixed positive integer s and every integer t sufficiently large with respect to s, there is a constant C such that every graph with average degree at least C · t contains a minor isomorphic to Ks,t. In fact, we determine asymptotically (in s) the smallest average degree that forces a graph to contain a Ks,t-minor, and in the case s = 3, we determine the smallest such average degree exactly.;The second problem we study is one in the field of domination in graphs. We develop methods for proving Nordhaus-Gaddum bounds on the k-domination number of a graph for any positive integer k. We prove such bounds when k = 1 and apply the method used to derive similar bounds on parameters of the same order of magnitude as the domination number. We then extend the bounds to arbitrary k > 1. We close our study of domination by considering when the ratio of the Roman domination number of a graph to its domination number is either 1 or 2.;Our final problem is one in graph representations. We develop a lemma on traces of hypergraphs, extending results of Balogh and Bollobas. We then use this lemma, along with probabilistic methods, to show that for every positive integer k, almost every graph has no k-minimum-difference-representation. This answers a question of Boros, Gurvich, and Meshulam. |
