Bounding Ramsey numbers through large deviation inequalities

DOI10.1002/rsa.3240070204zbMath0835.05047OpenAlexW2131309366WikidataQ105583258 ScholiaQ105583258MaRDI QIDQ4847400

Michael Krivelevich

Publication date: 20 September 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240070204

zbMATH Keywords

Ramsey numbersinduced subgraphprobabilistic methodLovász local lemmalarge deviation inequalities

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Generalized Ramsey theory (05C55)

Related Items (30)

Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs ⋮ On the Ramsey-Turán number with small \(s\)-independence number ⋮ Constructive bounds for a Ramsey-type problem ⋮ A lower bound for irredundant Ramsey numbers ⋮ Packing nearly optimal Ramsey \(R(3,t)\) graphs ⋮ Bounds on Ramsey games via alterations ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ Local and global colorability of graphs ⋮ Unnamed Item ⋮ Ramsey numbers involving large dense graphs and bipartite Turán numbers ⋮ On vertex Ramsey graphs with forbidden subgraphs ⋮ On generalized Ramsey numbers of Erdős and Rogers ⋮ On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers ⋮ Ramsey numbers of some bipartite graphs versus complete graphs ⋮ Online Ramsey Numbers and the Subgraph Query Problem ⋮ Expanders Are Universal for the Class of All Spanning Trees ⋮ \(K_4\)-free graphs without large induced triangle-free subgraphs ⋮ Short Proofs of Some Extremal Results ⋮ When does the K₄‐free process stop? ⋮ Dense induced bipartite subgraphs in triangle-free graphs ⋮ Coloring H-free hypergraphs ⋮ A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function ⋮ Dependent random choice ⋮ Ramsey numbers involving graphs with large degrees ⋮ Ramsey, Paper, Scissors ⋮ The triangle-free process ⋮ On the minimal number of edges in color-critical graphs ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets ⋮ On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs ⋮ On the Stability of the Graph Independence Number

Cites Work

• Constructive bounds for a Ramsey-type problem
• Counting extensions
• Poisson approximation for large deviations
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• The Construction of Certain Graphs

This page was built for publication: Bounding Ramsey numbers through large deviation inequalities