Enumerating combinatorial objects with limited sub-configurations

Li, Lina

Permalink

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

Description

Title

Enumerating combinatorial objects with limited sub-configurations

Author(s)

Li, Lina

Issue Date

2020-04-30

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

Balogh, József

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Ford, Kevin
• Lavrov, Mikhail

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Combinatorics
• Graph theory
• container method

Abstract

Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several problems of this type using various techniques. In Chapter 2, we investigate the family of linear hypergraphs with forbidden linear cycles. A substantial part of the work indeed focuses on a closely related problem, the study of the family of graphs with limited short even cycles, which may be of independent interest. To attack this problem, we introduce a new variant of the graph container algorithm. Another application of it to additive combinatorics is presented in Chapter 3 on generalized Sidon sets. In Chapter 4, we investigate an enumeration problem on Gallai colorings, i.e. rainbow triangle-free colorings. In particular, we describe the typical structure of Gallai r-colorings of complete graphs, and complete the characterization of the extremal graphs for Gallai colorings. This work heavily relies on the hypergraph container method, and some ad-hoc stability analysis. Another closely related problem is the study of sparse analogue of classical extremal results in random graphs, for example, the Erdős-Stone theorem, as it can also be interpreted as counting graphs in the corresponding probability space. In Chapter 5, we show a random analogue of the famous Erdős-Gallai theorem on extremal functions of paths.

Graduation Semester

2020-05

Type of Resource

Thesis

Permalink

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

Copyright and License Information

2020 by Lina Li. All rights reserved.

Owning Collections