2026-09-18T19:33:58Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/29436 2023-07-10 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Furedi, Zoltan Kostochka, Alexandr V. Furedi, Zoltan West, Douglas B. Balogh, József Kim, Youn-Jin 2012-02-01T00:46:19Z 2012-02-01T00:46:19Z 2014-02-01T11:00:26Z 2011-12 2012-02-01T00:46:19Z 2011-12 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_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 -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^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 $n-d+3$. In the case $d > n - c_2 \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$. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-11-21T22:18:12Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 KIM_YOUNJIN.pdf: 532935 bytes, checksum: d07b7137675a9bcc8a324b0553765ba3 (MD5) Made available in DSpace on 2012-02-01T00:46:19Z (GMT). No. of bitstreams: 2 KIM_YOUNJIN.pdf: 531341 bytes, checksum: c67b8540f6a5ca81315b9097b17dc0ba (MD5) license.txt: 4059 bytes, checksum: dc42ed373ab2fd185eec9ce70491b3fa (MD5) Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2012-02-01T00:50:22Z Item is restricted until 2014-02-01T00:50:07Z Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:26Z Item was in collections: Graduate Theses and Dissertations at Illinois (ID: 204) Dissertations and Theses - Mathematics (ID: 749) No. of bitstreams: 3 KIM_YOUNJIN.pdf: 531341 bytes, checksum: c67b8540f6a5ca81315b9097b17dc0ba (MD5) license.txt: 4059 bytes, checksum: dc42ed373ab2fd185eec9ce70491b3fa (MD5) KIM_YOUNJIN.pdf.txt: 122256 bytes, checksum: 0ff27d8c80eda8068a91b005e38f8f56 (MD5) Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:26Z http://hdl.handle.net/2142/29436 en Copyright 2011 Younjin Kim graphs cycles extremal graphs minimal saturated graphs diameter random graphs set families boolean algebras Problems in extremal combinatorics Dissertation / Thesis text Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD