Files in this item



application/pdfLIU-DISSERTATION-2015.pdf (649kB)
(no description provided)PDF


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
Degree Granting Institution:University of Illinois at Urbana-Champaign
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_4-free 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 sum-free 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 sum-free 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:2015-12-04
Rights Information:Copyright 2015 Hong Liu
Date Available in IDEALS:2016-03-02
Date Deposited:2015-12

This item appears in the following Collection(s)

Item Statistics