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>