Extremal graph theory: supersaturation and enumeration

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2016

Author dc:creator

• Liu, Hong

Contributors dc:contributor

• Balogh, Jozsef
• Kostochka, Alexandr
• Reznick, Bruce
• Molla, Theo

• Supersaturation
• Enumeration
• Typical Structure
• Extremal Combinatorics

Statement dc:rights

• Copyright 2015 Hong Liu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/89148

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/89148