Indexed by:
Abstract:
For graphs G and H, the Ramsey number r(G, H) is the smallest positive integer N such that any red/blue edge colouring of the complete graph KN contains either a red G or a blue H. A book Bn is a graph consisting of n triangles all sharing a common edge. Recently, Conlon, Fox, and Wigderson conjectured that for any 0 < α < 1, the random lower bound r(B⌈αn⌉, Bn) ≥ (√α + 1)2n + o(n) is not tight. In other words, there exists some constant β > (√α + 1)2 such that r(B⌈αn⌉, Bn) ≥ βn for all sufficiently large n. This conjecture holds for every α < 1/6 by a result of Nikiforov and Rousseau from 2005, which says that in this range r(B⌈αn⌉, Bn) = 2n + 3 for all sufficiently large n. We disprove the conjecture of Conlon, Fox, and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every 1/4 ≤ α ≤ 1. Moreover, we show that for any 1/6 ≤ α ≤ 1/4 and large n, r(B⌈αn⌉, Bn) ≤ (3/2 + 3α) n + o(n), where the inequality is asymptotically tight when α = 1/6 or 1/4. We also give a lower bound of r(B⌈αn⌉, Bn) for 1/6 ≤ α < 52-16√3/121 ≈ 0.2007, showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox, and Wigderson holds in this interval. © The Author(s), 2024. Published by Cambridge University Press.
Keyword:
Reprint 's Address:
Email:
Source :
Combinatorics Probability and Computing
ISSN: 0963-5483
Year: 2024
0 . 9 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: