Random bipartite Ramsey numbers of long cycles

被引:0
作者
Liu, Meng [1 ]
Li, Yusheng [2 ]
机构
[1] Anhui Univ, Ctr Pure Math, Sch Math Sci, Hefei 230601, Peoples R China
[2] Tongji Univ, Sch Math Sci, Shanghai 200092, Peoples R China
关键词
Bipartite Ramsey number; Random graph; Sparse regularity lemma for multipartite; graphs; PARTITION UNIVERSAL; TRIPLE; GRAPHS; PATHS;
D O I
10.1016/j.dam.2023.12.024
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For graphs G and H, let G -> H-k signify that any k-edge coloring of G contains a monochromatic H as a subgraph. Let G(K-2(N),p) be random graph spaces with edge probability p, where K-2(N) is the complete N x N bipartite graph. Let K-2(N) be a cycle of length 2n and let k = 2,3. It is shown for any is an element of > 0, there exists T = T(is an element of) > 0 such that if np > T, then Pr[G(K-2((k + is an element of)n),p)-> kC(2n)]-> 1 as n -> infinity, for which the proof relies heavily on the sparse regularity lemma for multipartite graphs.
引用
收藏
页码:39 / 47
页数:9
相关论文
共 38 条
  • [1] Alon Noga, 1992, The Probabilistic Method
  • [2] Araújo P, 2024, Arxiv, DOI arXiv:2208.13028
  • [3] The 3-colored Ramsey number of even cycles
    Benevides, Fabricio Siqueira
    Skokan, Jozef
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (04) : 690 - 708
  • [4] Bondy J. A., 1973, J COMB THEORY B, V14, P46, DOI DOI 10.1016/J.JCTB.2008.12.002
  • [5] 3-Color bipartite Ramsey number of cycles and paths
    Bucic, Matija
    Letzter, Shoham
    Sudakov, Benny
    [J]. JOURNAL OF GRAPH THEORY, 2019, 92 (04) : 445 - 459
  • [6] Bucic M, 2019, ELECTRON J COMB, V26
  • [7] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS
    CHERNOFF, H
    [J]. ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04): : 493 - 507
  • [8] THE RAMSEY NUMBER OF A GRAPH WITH BOUNDED MAXIMUM DEGREE
    CHVATAL, C
    RODL, V
    SZEMEREDI, E
    TROTTER, WT
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (03) : 239 - 243
  • [9] Multicolour Ramsey numbers of paths and even cycles
    Davies, E.
    Jenssen, M.
    Roberts, B.
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2017, 63 : 124 - 133
  • [10] ON SOME MULTICOLOR RAMSEY PROPERTIES OF RANDOM GRAPHS
    Dudek, Andrzej
    Pralat, Pawel
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) : 2079 - 2092