Extremal problems on counting combinatorial structures

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²/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{n2/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^n2/8+o(n2), 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₃'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 a poset $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\}ⁿ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset \{0,1,\ldots,k\}ⁿ 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ⁿ 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)<\chi(G^k)³ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Petrickova, Sarka

Contributors dc:contributor

• Balogh, József
• Kostochka, Alexandr V.
• Kirkpatrick, Kay
• Molla, Theodore

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

Statement dc:rights

• Copyright 2017 Sarka Petrickova

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/97401