MATH Seminar
| Title: Topics in Ramsey Theory |
|---|
| Defense: Dissertation |
| Speaker: Domingos Dellamonica Jr. of Emory University |
| Contact: Domingos Dellamonica Jr., ddellam@emory.edu |
| Date: 2012-04-03 at 4:00PM |
| Venue: W304 |
| Download Flyer |
| Abstract: In this thesis we discuss two results in Ramsey Theory.\\ \\ Result I: the size-Ramsey number of a graph $H$ is the smallest number of edges a graph $G$ must have in order to force a monochromatic copy of $H$ in every $2$-coloring of the edges of $G$. In 1990, Beck studied the size-Ramsey number of trees: he introduced a tree invariant $\beta(\cdot)$, and proved that the size-Ramsey number of a tree $T$ is at least $\beta(T)/4$. Moreover, Beck showed an upper bound for this number involving $\beta(T)$, and further conjectured that the size-Ramsey number of any tree~$T$ is of order $\beta(T)$. We answer his conjecture affirmatively. Our proof uses the expansion properties of random bipartite graphs.\\ \\ Result II: We prove the following metric Ramsey theorem. For any connected graph $G$ endowed with a linear order on its vertex set, there exists a graph $R$ such that in every coloring of the $t$-sets of vertices of $R$ it is possible to find a copy $G'$ of $G$ inside $R$ satisfying the following two properties:\\ \begin{itemize} \item the distance between any two vertices $x, y \in V(G')$ in the graph $R$ is the same as their distance within $G'$; \item the color of each $t$-set in $G'$ depends only on the graph-distance metric induced in $G'$ by the ordered $t$-set. \end{itemize} |
See All Seminars