Enumerating combinatorial objects with limited sub-configurations

Combinatorics;Graph theory;container method

Li, Lina

关键词: Combinatorics;    Graph theory;    container method;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/107931/LI-DISSERTATION-2020.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.