MATH Seminar
| Title: On Problems in extremal graph theory and Ramsey theory |
|---|
| Defense: Dissertation |
| Speaker: Steven La Fleur of Emory University |
| Contact: Steven La Fleur, slafeu@emory.edu |
| Date: 2013-04-03 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Extremal graph theory and Ramsey theory are two large subjects in graph theory. Both subjects involve finding substructures within graphs, or generalize graphs, under certain conditions. This dissertation investigates the following problems in each of these subjects.\\ \\ We consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer $q$. The number $a$, $0 \leq a < q$ is a jump for $q$ if, for any positive $e$, any integer $m$, and any $q$-multigraph on $n > n_0(e,a)$ vertices and at least $(a + e)(n(n-1)/2)$ edges, counting multiplicity, there is a subgraph on $m$ vertices and at least $(a+ c)(m(m-1)/2)$ edges, where $c = c(a)$ does not depend on $e$ or $m$. The Erd\H{o}s-Stone theorem implies that for $q=1$ every $a \in [0,1)$ is a jump. The problem of determining the set of jumps for $q \geq 2$ appears to be much harder. In a sequence of papers by Erd\H{o}s, Brown, Simonovits and separately Sidorenko, the authors established that every $a$ is a jump for $q = 2$ leaving the question whether the same is true for $q \geq 3$ unresolved. A later result of R\"{o}dl and Sidorenko gave a negative answer, establishing that for $q \geq 4$ some values of $a$ are not jumps. The problem of whether or not every $a \in [0,3)$ is a jump for $q = 3$ has remained open. We give a partial positive result in this dissertation, proving that every $a \in [0,2)$ is a jump for all $q \geq 3$. Additionally, we extend the results of R\"{o}dl and Sidorenko by showing that, given any rational number $r$ with $0 < r \leq 1$, that $(q - r)$ is not a jump for any $q$ sufficiently large. This is joint work with Paul Horn and Vojt\v{e}ch R\"{o}dl.\\ \\ Given two (hyper)graphs $T$ and $S$, the Ramsey number $r(T,S)$ is the smallest integer $n$ such that, for any two-coloring of the edges of $K_n$ with red and blue, we can find a red copy of $T$ or a blue copy of $S$. Similarly, the induced Ramsey number, $r_{\mathrm{ind}}(T,S)$, is defined to be the smallest integer $N$ such that there exists a (hyper)graph $R$ with the following property: In any two-coloring of the edges of $R$ with red and blue, we can always find a red \emph{induced} copy of $T$ or a blue \emph{induced} copy of $S$. In this dissertation we will discuss bounds for $r(K^{(k)}_{t,\dots,t}, K_s^{(k)})$ where $K^{(k)}_{t,\dots,t}$ is the complete $k$-partite $k$-graph with partition classes of size $t$. We also present new upper bounds for $r_{\mathrm{ind}}(S, T)$, where $T \subseteq K^{(k)}_{t,\dots,t}$ and $S \subseteq K_s^{(k)}$. This is based on joint work with D.~Dellamonica and V.~R\"odl. |
See All Seminars