printable pdf
比利时vs摩洛哥足彩 ,
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

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