Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Andrzej Dudek

Western Michigan University

Ramsey Properties of Random Graphs and Hypergraphs

Abstract:

First we focus on the size-Ramsey number of a path $P_n$ on $n$ vertices. In particular, we show that $5n/2 - 15/2 \le \hat{r}(P_n)\le 74n$ for $n$ sufficiently large. This improves the previous lower bound due to Bollob\'{a}s, and the upper bound due to Letzter. \medskip Next we study long monochromatic paths in edge-colored random graph $G(n,p)$ with $pn\to\infty$. Recently, Letzter showed that a.a.s. any 2-edge coloring of $G(n, p)$ yields a monochromatic path of length $(2/3-o(1))n$, which is optimal. Extending this result, we show that a.a.s. any 3-edge coloring of $G(n, p)$ yields a monochromatic path of length $(1/2-o(1))n$, which is also optimal. We also consider a related problem and show that for any $r\ge 2$, a.a.s. any $r$-edge coloring of $G(n, p)$ yields a monochromatic connected subgraph on $(1/(r-1)-o(1))n$ vertices, which is also tight. \medskip Finally, we discuss some extensions of the above results for random hypergraphs. In particular, we obtain a random analog of a result of Gy\'arf\'as, S\'ark\'ozy, and Szemer\'edi on the longest monochromatic loose cycle in $2$-colored complete $k$-uniform hypergraphs. \medskip This is joint work with Pawel Pralat and also with Patrick Bennett, Louis DeBiasio, and Sean English.

Hosts: Pawel Pralat and Jacques Verstraete

October 3, 2017

4:00 PM

AP&M 7321

****************************