Asymmetric Ramsey properties of random graphs involving cliques and cycles

Liebenau, Anita; Mattos, Letícia; Mendonca Dos Santos, Walner; Skokan, Jozef

Asymmetric Ramsey properties of random graphs involving cliques and cycles

Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 62(4), 1035–1055.

Download

2023_RandomStructureAlgorithms_Liebenau.pdf 1.36 MB [Published Version]

DOI

10.1002/rsa.21106

Journal Article | Published | English

Scopus indexed

Author

Liebenau, Anita; Mattos, Letícia; Mendonca dos Santos, Walner^ISTA; Skokan, Jozef

Department

Kwan Group

Abstract

We say that (Formula presented.) if, in every edge coloring (Formula presented.), we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy of (Formula presented.). The well-known states that the threshold for the property (Formula presented.) is equal to (Formula presented.), where (Formula presented.) is given by (Formula presented.) for any pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.). In this article, we show the 0-statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques.

Publishing Year

2023

Date Published

2023-07-01

Journal Title

Random Structures and Algorithms

Publisher

Wiley

Acknowledgement

This work was started at the thematic program GRAPHS@IMPA (January–March 2018), in Rio de Janeiro. We thank IMPA and the organisers for the hospitality and for providing a pleasant research environment. We thank Rob Morris for helpful discussions, and the anonymous referees for their careful reading and many helpful suggestions. Open Access funding enabled and organized by Projekt DEAL. A. Liebenau was supported by an ARC DECRA Fellowship Grant DE170100789. L. Mattos was supported by CAPES and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). W. Mendonça was supported by CAPES project 88882.332408/2010-01.

Volume

Issue

Page

1035-1055

ISSN

1042-9832

eISSN

1098-2418

IST-REx-ID

11706

Cite this

Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 2023;62(4):1035-1055. doi:10.1002/rsa.21106

Liebenau, A., Mattos, L., Mendonca dos Santos, W., & Skokan, J. (2023). Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.21106

Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” Random Structures and Algorithms. Wiley, 2023. https://doi.org/10.1002/rsa.21106.

A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric Ramsey properties of random graphs involving cliques and cycles,” Random Structures and Algorithms, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.

Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 62(4), 1035–1055.

Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” Random Structures and Algorithms, vol. 62, no. 4, Wiley, 2023, pp. 1035–55, doi:10.1002/rsa.21106.

All files available under the following license(s):

Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0):