Problems in extremal combinatorics

We consider a variety of problems in extremal graph and set theory. Given a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. Let $f(m,\Gamma)$ be the minimum of $f({\mathcal F},\Gamma)$ over all families of size $m$ where $m$ is a positive integer. A family $\mathcal{F}$ is {\it B_d-free} if it has no subfamily \mathcal{F}'=\{F_I: I \subseteq [d]\} of 2^d distinct sets such that for every $I,J \subseteq [d]$, both F_I \cup F_J=F_{I \cup J} and F_I \cap F_J = F_{I \cap J} hold. A family $\mathcal{F}$ is $a$-{\it union-free} if F₁\cup \dots \cup F_a \neq F_a+1 whenever F₁,\dots,F_a+1 are distinct sets in $\mathcal{F}$. We prove a conjecture of Erd\H os and Shelah that f(m, B₂\text{\rm -free})=\Theta(m^2/3). We also obtain lower and upper bounds for f(m, B_d\text{\rm -free}) and $f(m,a\text{\rm -union-free})$. A graph $G$ is {\it $F$-saturated } if it does not contain $F$ as a subgraph but the addition of any new edge creates at least one copy of $F$ in $G$. We focus on finding the minimum size of an $n$-vertex $F$-saturated graph, denoted by $\sat(n,F)$. We prove \sat(n,C_k) = n + \frac{n}{k} + O((\frac{n}{k²}) + k²) for all $n\geq k\geq 3$, where C_k is a cycle with length $k$. We conjecture that our three constructions are optimal. We obtain the exact asymptotics for the number of $n$-vertex graphs of diameter $d$, extending earlier results to hold for almost all $d$ and $n$. Additionally, we find the typical structure of almost all $n$-vertex graphs with diameter of at least $d$. In the case d < n - c₁ \log n, the typical graph of diameter $d$ consists of an induced path of length $d$ and a highly connected block of order $n-d+3$. In the case d > n - c₂ \log n, the typical graph has a completely different snake-like structure. We also extend the results to random graphs of diameter $d$ with edge probability $p$.

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

2012

Author dc:creator

• Kim, Youn-Jin

Contributors dc:contributor

• Furedi, Zoltan
• Kostochka, Alexandr V.
• West, Douglas B.
• Balogh, József

• graphs
• cycles
• extremal graphs
• minimal saturated graphs
• diameter
• random graphs
• set families
• boolean algebras

Statement dc:rights

• Copyright 2011 Younjin Kim

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

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