Multicolor list Ramsey numbers grow exponentially

被引:0
作者
Fox, Jacob [1 ]
He, Xiaoyu [1 ]
Luo, Sammy [1 ]
Xu, Max Wenqiang [1 ]
机构
[1] Stanford Univ, Dept Math, Stanford, CA 94305 USA
基金
美国国家科学基金会;
关键词
chromatic number; list coloring; local lemm; Ramsey theory; GRAPHS;
D O I
10.1002/jgt.22832
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The list Ramsey number R-l(H,k), recently introduced by Alon, Bucic, Kalvari, Kuperwasser, and Szabo, is a list-coloring variant of the classical Ramsey number. They showed that if H is a fixed r-uniform hypergraph that is not r-partite and the number of colors k goes to infinity, e(Omega(root k)) <= R-l(H,k) <= e(O(k)). We prove that R-l(H,k) = e(Theta(k)) if and only if H is not r-partite.
引用
收藏
页码:389 / 396
页数:8
相关论文
共 19 条
  • [1] Alon N., 2008, The probabilistic method, V3rd ed.
  • [2] List Ramsey numbers
    Alon, Noga
    Bucic, Matija
    Kalvari, Tom
    Kuperwasser, Eden
    Szabo, Tibor
    [J]. JOURNAL OF GRAPH THEORY, 2021, 96 (01) : 109 - 128
  • [3] Burr S. A., 1976, Ars Combin, V1, P167
  • [4] Conlon D., 2015, . London Mathematical Society Lecture Note Series, V424, P49, DOI DOI 10.1017/CBO9781316106853
  • [5] Erdos P., 1978, Periodica Mathematica Hungarica, V9, P145, DOI 10.1007/BF02018930
  • [6] ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED GRAPHS
    ERDOS, P
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 1964, 2 (03) : 183 - &
  • [7] ERDOS P, 1971, PAC J MATH, V37, P45
  • [8] PARTITION RELATIONS FOR CARDINAL NUMBERS
    ERDOS, P
    HAJNAL, A
    RADO, R
    [J]. ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1965, 16 (1-2): : 93 - &
  • [9] Degree Ramsey numbers for cycles and blowups of trees
    Jiang, Tao
    Milans, Kevin G.
    West, Douglas B.
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (02) : 414 - 423
  • [10] Decomposition of bounded degree graphs into C4-free subgraphs
    Kang, Ross J.
    Perarnau, Guillem
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2015, 44 : 99 - 105