• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Fan, C. (Fan, C..) [1] | Lin, Q. (Lin, Q..) [2] | Yan, Y. (Yan, Y..) [3]

Indexed by:

Scopus

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:

Book Ramsey number refined regularity lemma

Community:

  • [ 1 ] [Fan C.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, China
  • [ 2 ] [Lin Q.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, China
  • [ 3 ] [Yan Y.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Combinatorics Probability and Computing

ISSN: 0963-5483

Year: 2024

0 . 9 0 0

JCR@2023

Cited Count:

WoS CC 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:

Online/Total:91/10137841
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1