Towards the 0-statement of the Kohayakawa-Kreuter conjecture

preprint2022arXivOpen access

Abstract

In this paper, we study asymmetric Ramsey properties of the random graph Gn,pG_{n,p}. Let r∈Nr \in \mathbb{N} and H1,…,HrH_1, \ldots, H_r be graphs. We write Gn,p→(H1,…,Hr)G_{n,p} \to (H_1, \ldots, H_r) to denote the property that whenever we colour the edges of Gn,pG_{n,p} with colours from the set [r]:={1,…,r}[r] := \{1, \ldots, r\} there exists i∈[r]i \in [r] and a copy of HiH_i in Gn,pG_{n,p} monochromatic in colour ii. There has been much interest in determining the asymptotic threshold function for this property. Rödl and Ruciński determined the threshold function for the general symmetric case; that is, when H1=⋯=HrH_1 = \cdots = H_r. A conjecture of Kohayakawa and Kreuter, if true, would fully resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij. Building on work of Marciniszyn, Skokan, Spöhel and Steger, we reduce the 0-statement of Kohayakawa and Kreuter's conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the 0-statement for all such pairs of graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.