Extremal problems on counting combinatorial structures

Extremal;Counting;Triangle-free;Maximal;Structure;Poset;Comparable pair;Chromatic number;Choosability

Petrickova, Sarka

关键词: Extremal;    Counting;    Triangle-free;    Maximal;    Structure;    Poset;    Comparable pair;    Chromatic number;    Choosability;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/97401/PETRICKOVA-DISSERTATION-2017.pdf?sequence=1&isAllowed=y

美国|英语

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

【 摘 要 】

The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field.The complete balanced bipartite graph on $n$ vertices has $\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion. In Chapter 2, we solve the following problem of Paul Erd\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\'{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\'{o}zsef Balogh. In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that$G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\'{e}di Removal Lemma, the Erd\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint $P_3$'s, which is of independent interest.This is a joint work with J\'{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh. In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given aposet $P$, a family $\F\subseteq P$ is \emph{centered} if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the \emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbb{F}_q^n$ has the centeredness property. Several open problems are also given. This is a joint result with J\'{o}zsef Balogh and Adam Zsolt Wagner.In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable.Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable.We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\chi(G^k)$ unbounded and $\chi_{\ell}(G^k)\geq c \chi(G^k) \log \chi(G^k)$.We also provide an upper bound, $\chi_{\ell}(G^k)1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.