A resolution of the Kohayakawa--Kreuter conjecture for the majority of cases

EUROCOMB’23

Candida Bowtell Robert Hancock Joseph Hyde

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-025

PDF
Abstract
For graphs $G, H_1,\dots,H_r$, write $G \to (H_1, \ldots, H_r)$ to denote the property that whenever we $r$-colour the edges of $G$, there is a monochromatic copy of $H_i$ in colour $i$ for some $i \in \{1,\dots,r\}$. Mousset, Nenadov and Samotij proved an upper bound on the threshold function for the property that $G(n,p) \to (H_1,\dots,H_r)$, thereby resolving the $1$-statement of the Kohayakawa-Kreuter conjecture. We show that to prove the $0$-statement it suffices to prove a deterministic colouring result, which says that if $G$ is not too dense then $G \not \to (H_1,\dots,H_r)$. We extend upon the many partial results for the $0$-statement, by resolving it for a large number of cases, which in particular includes (but is not limited to) when $r \geq 3$, when $H_2$ is strictly $2$-balanced and not bipartite, or when $H_1$ and $H_2$ have the same $2$-densities.

Pages:
178–185
References

B. Bollobás and A.G. Thomason, Threshold functions, Combinatorica 7 (1987), 3538.
https://doi.org/10.1007/BF02579198

L. Gugelmann, R. Nenadov, Y. Person, N. .kori¢, A. Steger and H. Thomas, Symmetric and asymmetric Ramsey properties in random hypergraphs, Forum Math. Sigma 5 (2017).
https://doi.org/10.1017/fms.2017.22

J. Hyde, Towards the 0-statement of the Kohayakawa-Kreuter conjecture, Comb. Probab. Comput. 32 (2021), 225268.
https://doi.org/10.1017/S0963548322000219

Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), 245276.
https://doi.org/10.1002/(SICI)1098-2418(199710)11:3<245::AID-RSA3>3.0.CO;2-0

Y. Kohayakawa, M. Schacht and R. Spöhel, Upper bounds on probability thresholds for asymmetric Ramsey properties, Random Structures Algorithms 44(1) (2014), 128.
https://doi.org/10.1002/rsa.20446

A. Liebenau, L. Mattos, W. Mendonça and J. Skokan, Asymmetric Ramsey properties of random graphs for cliques and cycles, Random Structures Algorithms, to appear.

M. Marciniszyn, J. Skokan, R. Spöhel and A. Steger, Asymmetric Ramsey properties of random graphs involving cliques, Random Structures Algorithms 34(4) (2009), 419453.
https://doi.org/10.1002/rsa.20239

F. Mousset, R. Nenadov and W. Samotij, Towards the KohayakawaKreuter conjecture on asymmetric Ramsey properties, Combin. Probab. Comput. 29(6) (2020), 943955.
https://doi.org/10.1017/S0963548320000267

R. Nenadov, Y. Person, N. .kori¢ and A. Steger, An algorithmic framework for obtaining lower bounds for random Ramsey problems, J. Combin. Theory Ser. B 124 (2017), 1 38.
https://doi.org/10.1016/j.jctb.2016.12.007

R. Nenadov and A. Steger, A short proof of the random Ramsey theorem, Combin. Probab. Comput. 25(1) (2016), 130-144.
https://doi.org/10.1017/S0963548314000832

V. Rödl and A. Ruci«ski, Lower bounds on probability thresholds for Ramsey properties, Combinatorics, Paul Erdos is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest (1993), 317346.

V. Rödl and A. Ruci«ski, Random graphs with monochromatic triangles in every edge coloring, Random Structures Algorithms 5 (1994), 253270.
https://doi.org/10.1002/rsa.3240050202

V. Rödl and A. Ruci«ski, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), 917942.
https://doi.org/10.1090/S0894-0347-1995-1276825-6

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Candida Bowtell, Robert Hancock, Joseph Hyde

PDF