Files in this item
Files  Description  Format 

application/pdf SHARIFZADEHDISSERTATION2016.pdf (702kB)  (no description provided) 
Description
Title:  Embedding problems and RamseyTurán variations in extremal graph theory 
Author(s):  Sharifzadeh, Maryam 
Director of Research:  Balogh, József 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Kirkpatrick, Kay; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Combinatorics
Graph RamseyTuran 
Abstract:  In this dissertation, we will focus on a few problems in extremal graph theory. The first chapter consists of some basic terms and tools. In Chapter 2, we study a conjecture of Mader on embedding subdivisions of cliques. Improving a bound by Mader, Bollobás and Thomason, and independently Komlós and Szemerédi proved that every graph with average degree d contains a subdivision of K_[Ω(√d)]. The disjoint union of complete bipartite graph K_(r,r) shows that their result is best possible. In particular, this graph does not contain a subdivision of a clique of order w(r). However, one can ask whether their bound can be improved if we forbid such structures. There are various results in this direction, for example Kühn and Osthus proved that their bound can be improved if we forbid a complete bipartite graph of fixed size. Mader proved that that there exists a function g(r) such that every graph G with ẟ(G) ≥ r and girth at least g(r) contains a TK_(r+1). He also asked about the minimum value of g(r). Furthermore, he conjectured that C_4freeness is enough to guarantee a clique subdivision of order linear in average degree. Some major steps towards these two questions were made by Kühn and Osthus, such as g(r) ≤ 27 and g(r) ≤ 15 for large enough r. In an earlier result, they proved that for C_4free graphs one can find a subdivision of a clique of order almost linear in minimum degree. Together with József Balogh and Hong Liu, we proved that every C_(2k)free graph, for k ≥ 3, has such a subdivision of a large clique. We also proved the dense case of Mader's conjecture in a stronger sense. In Chapter 3, we study a graphtiling problem. Let H be a fixed graph on h vertices and G be a graph on N vertices such that hn. An Hfactor is a collection of n/h vertexdisjoint copies of H in G. The problem of finding sufficient conditions for a graph G to have an Hfactor has been extensively studied; most notable is the celebrated HajnalSzemerédi Theorem which states that every nvertex graph G with ẟ(G) ≥ (11/r)n has a K_rfactor. The case r=3 was proved earlier by Corrádi and Hajnal. Another type of problems that have been studied over the past few decades are the socalled RamseyTurán problems. Erdős and Sós, in 1970, began studying a variation on Turán's theorem: What is the maximum number of edges in an nvertex, K_rfree graph G if we add extra conditions to avoid the very strict structure of Turán graph. In particular, what if besides being K_rfree, we also require α(G) = o(n) . Since the extremal example for the HajnalSzemerédi theorem is very similar to the Turán graph, one can similarly ask how stable is this extremal example. With József Balogh and Theodore Molla, we proved that for an nvertex graph G with α(G) = o(n), if ẟ(G) ≥ (1/2+o(1))n then G has a triangle factor. This minimum degree condition is asymptotically best possible. We also consider a fractional variant of the CorrádiHajnal Theorem, settling the triangle case of a conjecture of Balogh, Kemkes, Lee, and Young. In Chapter 4, we first consider a RamseyTurán variant of a theorem of Erd\Ho s. In 1962, he proved that for any r > l ≥ 2, among all K_rfree graphs, the (r1)partite Turán graph has the maximum number of copies of K_l. We consider a RamseyTurántype variation of Erdős's result. In particular, we define RT(F,H,f(n)) to be the maximum number of copies of F in an Hfree graph with nvertices and independence number at most f(n). We study this function for different graphs F and H. Recently, Balogh, Hu and Simonovits proved that the RamseyTurán function for even cliques experiences a jump. We show that the function RT(K_3,H,f(n)) has a similar behavior when H is an even clique. We also study the sparse analogue of a theorem of Bollobás and Gy\Ho ri about the maximum number of triangles that a C_5free graph can have. Finally, we consider a RamseyTurán variant of a function studied by Erdős and Rothschild about the maximum number of edgecolorings that an nvertex graph can have without a monochromatic copy of a given graph. 
Issue Date:  20160714 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/93041 
Rights Information:  Copyright 2016 Maryam Sharifzadeh 
Date Available in IDEALS:  20161110 
Date Deposited:  201608 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois