Multicolor Ramsey numbers via pseudorandom graphs

DOI10.37236/9071zbMATH Open1432.05067arXiv1910.06287OpenAlexW2980245002MaRDI QIDQ2294097FDOQ2294097

Authors: Xiaoyu He, Yuval Wigderson 

Publication date: 10 February 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1910.06287

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
• Multi-color Ramsey numbers of two bipartite graphs
• Title not available (Why is that?)
• 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)