On the Ramsey number of the triangle and the cube

DOI10.1007/S00493-015-3089-8MaRDI QIDQ519971zbMATH OpenOpenAlexFDO

Authors Simon Griffiths, Robert Morris, Gonzalo Fiz Pontiveros, David Saxton, J. Skokan

Publication date 31 March 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3840, http://eprints.lse.ac.uk/62348/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Skokan%2C%20J_On%20the%20Ramsay%20number_Skakon_On_the_Ramsey_number.pdf

zbMATH Keywords

red/blue Ramsey numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and ErdH{o}s conjectured that r(K_3,Q_n) = 2^{n+1} - 1 for every n in N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) le 7000 cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n o infty.

Recommendations

• Some Ramsey-type results for the \(n\)-cube
• On the Ramsey-Turán density of triangles
• Ramsey numbers of cubes versus cliques
• The Ramsey number of the clique and the hypercube
• scientific article; zbMATH DE number 3880754
• scientific article; zbMATH DE number 1127885
• Ramsey numbers and triangle-free Cayley graphs
• A Ramsey-type result for the hypercube
• The size‐Ramsey number of cubic graphs
• scientific article; zbMATH DE number 2192153

Cites work

• scientific article; zbMATH DE number 3545699 (Why is no real title available?)
• A Separator Theorem for Nonplanar Graphs
• Density theorems for bipartite graphs and related Ramsey-type results
• Generalizations of a Ramsey-theoretic result of chvátal
• Hypergraph packing and sparse bipartite Ramsey numbers
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Ramsey goodness and beyond
• Ramsey numbers of cubes versus cliques
• Ramsey-goodness -- and otherwise

Cited in

(11)

• The Ramsey number of the clique and the hypercube
• Ramsey numbers of cubes versus cliques
• A remark on the Ramsey number of the hypercube
• Clique colourings of geometric graphs
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Two Conjectures in Ramsey--Turán Theory
• scientific article; zbMATH DE number 1372026 (Why is no real title available?)
• Cube Ramsey numbers are polynomial
• Some Ramsey-type results for the \(n\)-cube
• Cycles in triangle-free graphs of large chromatic number
• Ramsey theory on Steiner triples

This page was built for publication: On the Ramsey number of the triangle and the cube

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