Files in this item
Files  Description  Format 

application/pdf KIM_YOUNJIN.pdf (531kB)  (no description provided) 
Description
Title:  Problems in extremal combinatorics 
Author(s):  Kim, YounJin 
Director of Research:  Furedi, Zoltan 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  Furedi, Zoltan; West, Douglas B.; Balogh, József 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graphs
cycles extremal graphs minimal saturated graphs diameter random graphs set families boolean algebras 
Abstract:  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 unionfree} if $F_1\cup \dots \cup F_a \neq F_{a+1}$ whenever $F_1,\dots,F_{a+1}$ are distinct sets in $\mathcal{F}$. We prove a conjecture of Erd\H os and Shelah that $f(m, B_2\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 unionfree})$. 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^2}) + k^2)$ 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_1 \log n$, the typical graph of diameter $d$ consists of an induced path of length $d$ and a highly connected block of order $nd+3$. In the case $d > n  c_2 \log n$, the typical graph has a completely different snakelike structure. We also extend the results to random graphs of diameter $d$ with edge probability $p$. 
Issue Date:  20120201 
Genre:  thesis 
URI:  http://hdl.handle.net/2142/29436 
Rights Information:  Copyright 2011 Younjin Kim 
Date Available in IDEALS:  20120201 20140201 
Date Deposited:  201112 
This item appears in the following Collection(s)

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