10.1184/R1/6721328.v1 Zelealem Belaineh Yilma Zelealem Belaineh Yilma Results in Extremal Graph and Hypergraph Theory Carnegie Mellon University 2011 Erdos-Ko-Rado Turan graphs Szemeredi’s Regularity Lemma Colorcritical Graphs Supersaturation 2011-05-01 00:00:00 Thesis https://kilthub.cmu.edu/articles/thesis/Results_in_Extremal_Graph_and_Hypergraph_Theory/6721328 <p>In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them.</p> <p>A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star.</p> <p>We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)<sup>2</sup>-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed.</p> <p>We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.</p>