Multicolor Ramsey numbers via pseudorandom graphs

DOI10.37236/9071MaRDI QIDQ2294097zbMATH OpenOpenAlexFDO

Authors Xiaoyu He, Yuval Wigderson

Publication date 10 February 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.06287, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p32

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: A weakly optimal $K_s$-free $(n,d,lambda)$-graph is a $d$-regular $K_s$-free graph on $n$ vertices with $d=Theta(n^{1-alpha})$ and spectral expansion $lambda=Theta(n^{1-(s-1)alpha})$, for some fixed $alpha>0$. Such a graph is called optimal if additionally $alpha=frac12s-3$. We prove that if $s_1,ldots,s_{k}ge3$ are fixed positive integers and weakly optimal $K_{s_i}$-free pseudorandom graphs exist for each $1leilek$, then the multicolor Ramsey numbers satisfy [ OmegaBig(frac{t^{S+1}}{log^{2S}t}Big)le r(s_{1},ldots,s_{k},t)le OBig(frac{t^{S+1}}{log^{S}t}Big), ] as $tightarrowinfty$, where $S=su{m}_{i=1}^k(s_i-2)$. This generalizes previous results of Mubayi and Verstra"ete, who proved the case $k=1$, and Alon and R"odl, who proved the case $s_1=cdots=s_k=3$. Both previous results used the existence of optimal rather than weakly optimal $K_{s_i}$-free graphs.

Recommendations

• Sharp bounds for some multicolour Ramsey numbers
• Multicolor Ramsey numbers for complete bipartite versus complete graphs
• Set-coloring of edges and multigraph Ramsey numbers
• An improved lower bound for multicolor Ramsey numbers and a problem of Erdős
• Multicolor Ramsey Numbers for Paths and Cycles

Cites work

• A construction for clique-free pseudorandom graphs
• A note on Ramsey numbers
• Coloring graphs with sparse neighborhoods
• Explicit Ramsey graphs and orthonormal labelings
• Sharp bounds for some multicolour Ramsey numbers
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The early evolution of the \(H\)-free process
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Triangle factors in sparse pseudo-random graphs

Cited in

(15)

• Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
• Multi-color Ramsey numbers of two bipartite graphs
• scientific article; zbMATH DE number 2196516 (Why is no real title available?)
• Ramsey-type results for Gallai colorings
• An improved lower bound on multicolor Ramsey numbers
• A clique-free pseudorandom subgraph of the pseudo polarity graph
• Multicolor list Ramsey numbers grow exponentially
• An improved lower bound for multicolor Ramsey numbers and a problem of Erdős
• The asymptotics of \(r(4,t)\)
• Anti-Ramsey colorings in several rounds
• Ramsey numbers involving an odd cycle and large complete graphs in three colors
• Cayley sum graphs and their applications to codebooks
• A lower bound for set‐coloring Ramsey numbers
• Making an H $H$‐free graph k $k$‐colorable
• A note on pseudorandom Ramsey graphs

This page was built for publication: Multicolor Ramsey numbers via pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294097)