2023/07/31 by Bowtell, Candida, Hancock, Robert, Hyde, Joseph
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.16760
For graphs G, H1,…,Hr, write G → (H1, …, Hr) to denote the property that whenever we r-colour the edges of G, there is a monochromatic copy of Hi in colour i for some i ∈ \1,…,r\. Mousset, Nenadov and Samotij proved an upper bound on the threshold function for the property that Gn,p → (H1,…,Hr), thereby resolving the 1-statement of the Kohayakawa--Kreuter conjecture. We reduce the 0-statement of the Kohayakawa--Kreuter conjecture to a natural deterministic colouring problem and resolve this problem for almost all cases, which in particular includes (but is not limited to) when H2 is strictly 2-balanced and either has density greater than 2 or is not bipartite. In addition, we extend our reduction to hypergraphs, proving the colouring problem in almost all cases there as well.