Files in this item
Files  Description  Format 

application/pdf PETRICKOVADISSERTATION2017.pdf (984kB)  (no description provided) 
Description
Title:  Extremal problems on counting combinatorial structures 
Author(s):  Petrickova, Sarka 
Director of Research:  Balogh, Jozsef 
Doctoral Committee Chair(s):  Kostochka, Alexandr V 
Doctoral Committee Member(s):  Kirkpatrick, Kay; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Extremal
Counting Trianglefree Maximal Structure Poset Comparable pair Chromatic number Choosability 
Abstract:  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 trianglefree, the number of (labeled) trianglefree 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 trianglefree graphs are bipartite. In Chapters 2 and 3 we study analogous problems for trianglefree 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 trianglefree graphs on $n$ vertices. We show that the number of maximal trianglefree 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 RuzsaSzemer\'{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 trianglefree graphs. We prove that almost all maximal trianglefree 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 RuzsaSzemer\'{e}di Removal Lemma, the Erd\H{o}sSimonovits stability theorem, and recent results of BaloghMorrisSamotij and SaxtonThomason 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 trianglefree graphs with many vertexdisjoint $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 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\}^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 chromaticchoosable. Xuding Zhu asked whether there is some $k$ such that all $k$th power graphs are chromaticchoosable. 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)^3$ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager. 
Issue Date:  20170419 
Type:  Text 
URI:  http://hdl.handle.net/2142/97401 
Rights Information:  Copyright 2017 Sarka Petrickova 
Date Available in IDEALS:  20170810 
Date Deposited:  201705 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois