Extremal graph theory: supersaturation and enumeration

Liu, Hong

Permalink

https://hdl.handle.net/2142/89148 Copy

Description

Title

Extremal graph theory: supersaturation and enumeration

Author(s)

Liu, Hong

Issue Date

2015-12-04

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, Jozsef

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Reznick, Bruce
• Molla, Theo

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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_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.

Graduation Semester

2015-12

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2015 Hong Liu

Owning Collections