---
OA_place: repository
OA_type: green
_id: '22153'
abstract:
- lang: eng
  text: "A weakly optimal Ks-free (n,d,λ)-graph is a d-regular Ks-free graph on n
    vertices with d=Θ(n1−α) and spectral expansion λ=Θ(n1−(s−1)α), for some fixed
    α>0. Such a graph is called optimal if additionally α=12s−3. We prove that if
    s1,…,sk≥3 are fixed positive integers and weakly optimal Ksi-free pseudorandom
    graphs exist for each 1≤i≤k, then the multicolor Ramsey numbers satisfy\r\nΩ(tS+1log2St)≤r(s1,…,sk,t)≤O(tS+1logSt),\r\nas
    t→∞, where S=∑ki=1(si−2). This generalizes previous results of Mubayi and Verstraëte,
    who proved the case k=1, and Alon and Rödl, who proved the case s1=⋯=sk=3. Both
    previous results used the existence of optimal rather than weakly optimal Ksi-free
    graphs."
article_number: P1.32
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: He X, Wigderson Y. Multicolor Ramsey numbers via pseudorandom graphs. <i>The
    Electronic Journal of Combinatorics</i>. 2020;27(1). doi:<a href="https://doi.org/10.37236/9071">10.37236/9071</a>
  apa: He, X., &#38; Wigderson, Y. (2020). Multicolor Ramsey numbers via pseudorandom
    graphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal
    of Combinatorics. <a href="https://doi.org/10.37236/9071">https://doi.org/10.37236/9071</a>
  chicago: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
    Graphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal
    of Combinatorics, 2020. <a href="https://doi.org/10.37236/9071">https://doi.org/10.37236/9071</a>.
  ieee: X. He and Y. Wigderson, “Multicolor Ramsey numbers via pseudorandom graphs,”
    <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1. The Electronic
    Journal of Combinatorics, 2020.
  ista: He X, Wigderson Y. 2020. Multicolor Ramsey numbers via pseudorandom graphs.
    The Electronic Journal of Combinatorics. 27(1), P1.32.
  mla: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
    Graphs.” <i>The Electronic Journal of Combinatorics</i>, vol. 27, no. 1, P1.32,
    The Electronic Journal of Combinatorics, 2020, doi:<a href="https://doi.org/10.37236/9071">10.37236/9071</a>.
  short: X. He, Y. Wigderson, The Electronic Journal of Combinatorics 27 (2020).
date_created: 2026-06-29T10:47:47Z
date_published: 2020-02-07T00:00:00Z
date_updated: 2026-07-08T07:27:57Z
day: '07'
doi: 10.37236/9071
extern: '1'
external_id:
  arxiv:
  - '1910.06287'
intvolume: '        27'
issue: '1'
language:
- iso: eng
month: '02'
oa_version: Preprint
publication: The Electronic Journal of Combinatorics
publication_identifier:
  issn:
  - 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multicolor Ramsey numbers via pseudorandom graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2020'
...