Files in this item

FilesDescriptionFormat

application/pdf

application/pdfLI-DISSERTATION-2020.pdf (683kB)
(no description provided)PDF

Description

Title:Enumerating combinatorial objects with limited sub-configurations
Author(s):Li, Lina
Director of Research:Balogh, József
Doctoral Committee Chair(s):Kostochka, Alexandr
Doctoral Committee Member(s):Ford, Kevin; Lavrov, Mikhail
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2020-04-30
Type:Thesis
URI:http://hdl.handle.net/2142/107931
Rights Information:2020 by Lina Li. All rights reserved.
Date Available in IDEALS:2020-08-26
Date Deposited:2020-05


This item appears in the following Collection(s)

Item Statistics