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

author:

Fan, Chunchao (Fan, Chunchao.) [1] | Lin, Qizhong (Lin, Qizhong.) [2] (Scholars:林启忠)

Indexed by:

Scopus SCIE

Abstract:

In 1983, Burr and Erd6s initiated the study of Ramsey goodness problems. Nikiforov and Rousseau (2009) resolved almost all goodness questions raised by Burr and Erd6s, in which the bounds on the parameters are of tower type since their proofs rely on the regularity lemma. Let Bk,n be the book graph on n vertices which consists of n - k copies of Kk +1 all sharing a common Kk, and let H = Kp(a1, . . . , ap) be the complete p-partite graph with parts of sizes a1, . . . , ap. Recently, avoiding use of the regularity lemma, Fox, He and Wigderson (2023) revisit several Ramsey goodness results involving books. They comment that it would be very interesting to see how far one can push these ideas. In particular, they conjecture that for all integers k, p, t & GE; 2, there exists some & delta; > 0 such that for all n & GE; 1, 1 < a1 < & BULL; & BULL; & BULL; < ap-1 < t and ap < & delta; n, we have r(H, Bk,n) = (p - 1)(n - 1) + dk(n, Ka1,a2 ) + 1, where dk(n, Ka1,a2 ) is the maximum d for which there is an (n +d -1)-vertex Ka1,a2-free graph in which at most k - 1 vertices have degree less than d. They verify the conjecture when a1 = a2 = 1. We disprove the conjecture of Fox et al. (2023). Building upon the work of Fox et al., we make a substantial step by showing that for every k, p, t & GE; 2, there exists & delta; > 0 such that the following holds for all large n. Let 1 < a1 < & BULL; & BULL; & BULL; < ap-1 < t and ap < & delta;n be positive integers. If a1 = 1, then r(H, Bk,n) < (p - 1)(n - 1) + k(p - 1)(a2 - 1) + 1. The inequality is tight if a2 (n - 1 - k). Moreover, we prove that for every k, a & GE; 1 and p & GE; 2, there exists & delta; > 0 such that for all large n and b < & delta; ln n, r(Kp(1, a, b, ..., b), Bk,n) = (p -1)(n -1) + k(p -1)(a -1) +1

Keyword:

Book Ramsey goodness Stability-supersaturation lemma

Community:

  • [ 1 ] [Fan, Chunchao]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China
  • [ 2 ] [Lin, Qizhong]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China

Reprint 's Address:

Show more details

Version:

Related Keywords:

Source :

JOURNAL OF COMBINATORIAL THEORY SERIES A

ISSN: 0097-3165

Year: 2023

Volume: 199

0 . 9

JCR@2023

0 . 9 0 0

JCR@2023

ESI Discipline: MATHEMATICS;

ESI HC Threshold:13

JCR Journal Grade:2

CAS Journal Grade:2

Cited Count:

WoS CC Cited Count: 4

SCOPUS Cited Count: 4

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:47/10137382
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