Files in this item
Files  Description  Format 

application/pdf LIUDISSERTATION2015.pdf (649kB)  (no description provided) 
Description
Title:  Extremal graph theory: supersaturation and enumeration 
Author(s):  Liu, Hong 
Director of Research:  Balogh, Jozsef 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Reznick, Bruce; Molla, Theo 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Supersaturation
Enumeration Typical Structure Extremal Combinatorics 
Abstract:  In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4free graph. In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh. In Chapter 4 and Chapter 5, we study the number of maximal sumfree subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sumfree subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos. In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions. 
Issue Date:  20151204 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/89148 
Rights Information:  Copyright 2015 Hong Liu 
Date Available in IDEALS:  20160302 
Date Deposited:  201512 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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