Printable PDF
Department of Mathematics,
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

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