Vol. 9, No. 1, 2020

Download this article
Download this article For screen
For printing
Recent Issues
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Previously Published
To Appear
founded and published with the
scientific support and advice of the
Moscow Institute of
Physics and Technology
 
Other MSP Journals
Long monochromatic paths and cycles in 2-edge-colored multipartite graphs

József Balogh, Alexandr Kostochka, Mikhail Lavrov and Xujun Liu

Vol. 9 (2020), No. 1, 55–100
Abstract

We solve four similar problems: for every fixed s and large n, we describe all values of n1,,ns such that for every 2-edge-coloring of the complete s-partite graph Kn1,,ns there exists a monochromatic (i) cycle C2n with 2n vertices, (ii) cycle C2n with at least 2n vertices, (iii) path P2n with 2n vertices, and (iv) path P2n+1 with 2n + 1 vertices.

This implies a generalization for large n of the conjecture by Gyárfás, Ruszinkó, Sárközy and Szemerédi that for every 2-edge-coloring of the complete 3-partite graph Kn,n,n there is a monochromatic path P2n+1. An important tool is our recent stability theorem on monochromatic connected matchings.

Keywords
Ramsey number, Regularity Lemma, paths and cycles
Mathematical Subject Classification 2010
Primary: 05C15, 05C35, 05C38
Milestones
Received: 12 May 2019
Revised: 8 January 2020
Accepted: 22 January 2020
Published: 20 February 2020
Authors
József Balogh
Department of Mathematics
University of Illinois
Urbana, IL
United States
Moscow Institute of Physics and Technology
Dolgoprudny
Russia
Alexandr Kostochka
Department of Mathematics
University of Illinois
Urbana, IL
United States
Sobolev Institute of Mathematics
Novosibirsk
Russia
Mikhail Lavrov
Department of Mathematics
University of Illinois
Urbana, IL
United States
Xujun Liu
Department of Mathematics
University of Illinois
Urbana, IL
United States