Diagonal Ramsey via effective quasirandomness

DOI10.1215/00127094-2022-0048zbMATH Open1512.05389arXiv2005.09251OpenAlexW3026254307MaRDI QIDQ6046448FDOQ6046448

Authors: Ashwin Sah 

Publication date: 11 May 2023

Published in: Duke Mathematical Journal (Search for Journal in Brave)

Abstract: We improve the upper bound for diagonal Ramsey numbers to [R(k+1,k+1)leexp(-c(log k)^2)�inom{2k}{k}] for $kge3$. To do so, we build on a quasirandomness and induction framework for Ramsey numbers introduced by Thomason and extended by Conlon, demonstrating optimal "effective quasirandomness" results about convergence of graphs. This optimality represents a natural barrier to improvement.

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

Recommendations

• A new upper bound for diagonal Ramsey numbers
• Tidier examples for lower bounds on diagonal Ramsey numbers
• Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
• Lower bounds for small diagonal Ramsey numbers
• scientific article; zbMATH DE number 3946178

zbMATH Keywords

Ramsey numbersquasirandomnessgraphons

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Hypergraph regularity and the multidimensional Szemerédi theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some remarks on the theory of graphs
• Quasi-random graphs
• Extremal results in sparse pseudorandom graphs
• Extremal results for random discrete structures
• Independent sets in hypergraphs
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• A relative Szemerédi theorem
• A new upper bound for diagonal Ramsey numbers
• On the KŁR conjecture in random graphs
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Title not available (Why is that?)
• The sparse regularity lemma and its applications
• An upper bound for some ramsey numbers
• The hypergraph regularity method and its applications
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Recent developments in graph Ramsey theory
• Extremal regular graphs: independent sets and graph homomorphisms
• A reverse Sidorenko inequality

Cited In (17)

• Ramsey numbers for multiple copies of sparse graphs
• Computation of new diagonal graph Ramsey numbers
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Lower bounds for multicolor Ramsey numbers
• The minimum degree of minimal Ramsey graphs for cliques
• A new upper bound for diagonal Ramsey numbers
• Threshold Ramsey multiplicity for odd cycles
• On the use of senders for asymmetric tuples of cliques in Ramsey theory
• Ramsey numbers of sparse digraphs
• On a diagonal conjecture for classical Ramsey numbers
• Ramsey numbers of cliques versus monotone paths
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Interview with David Conlon
• The pigeonhole principle and multicolor Ramsey numbers
• Off-diagonal book Ramsey numbers
• F$F$‐factors in Quasi‐random Hypergraphs
• Ramsey functions for quasi-progressions

This page was built for publication: Diagonal Ramsey via effective quasirandomness

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