On the Ramsey number of the triangle and the cube

DOI10.1007/S00493-015-3089-8zbMATH Open1374.05162arXiv1302.3840OpenAlexW1588853369MaRDI QIDQ519971FDOQ519971

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

Publication date: 31 March 2017

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

red/blue Ramsey numbers

Mathematics Subject Classification ID

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

Cites Work

• A Separator Theorem for Nonplanar Graphs
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Title not available (Why is that?)
• Ramsey goodness and beyond
• Ramsey-goodness -- and otherwise
• Hypergraph packing and sparse bipartite Ramsey numbers
• Density theorems for bipartite graphs and related Ramsey-type results
• Generalizations of a Ramsey-theoretic result of chvátal
• Ramsey numbers of cubes versus cliques

Cited In (8)

• Some Ramsey-type results for the \(n\)-cube
• Cube Ramsey numbers are polynomial
• Cycles in triangle-free graphs of large chromatic number
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• Ramsey theory on Steiner triples
• Ramsey numbers of cubes versus cliques
• Two Conjectures in Ramsey--Turán Theory
• Clique colourings of geometric graphs

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)