printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

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

math 269 - combinatorics

xujun liu

university of illinois at urbana-champaign

monochromatic connected matchings, paths and cycles in $2$-edge-colored multipartite graphs

abstract:

for every fixed $s$ and large $n$, we describe all values of $n_1,\ldots,n_s$ such that for every $2$-edge-coloring of the complete $s$-partite graph $k_{n_1,\ldots,n_s}$ there exists a monochromatic (i) cycle $c_{2n}$ with $2n$ vertices, (ii) cycle $c_{\geq 2n}$ with at least $2n$ vertices, (iii) path $p_{2n}$ with $2n$ vertices, and (iv) path $p_{2n+1}$ with $2n+1$ vertices. this implies a generalization of the conjecture by gy\' arf\' as, ruszink\' o, s\' ark\h ozy and szemer\' edi that for every $2$-edge-coloring of the complete $3$-partite graph $k_{n,n,n}$ there is a monochromatic path $p_{2n+1}$. an important tool is our recent stability theorem on monochromatic connected matchings (a matching $m$ in $g$ is connected if all the edges of $m$ are in the same component of $g$). we will also talk about exact ramsey-type bounds on the sizes of monochromatic connected matchings in $2$-colored multipartite graphs. joint work with j\' ozsef balogh, alexandr kostochka and mikhail lavrov.

host: ruth luo

november 12, 2019

1:00 pm

ap&m 7321

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