Ramsey numbers of cubes versus cliques
From MaRDI portal
Publication:519968
DOI10.1007/S00493-014-3010-XzbMATH Open1374.05222arXiv1208.1732OpenAlexW2137574596MaRDI QIDQ519968FDOQ519968
Authors: David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov 
Publication date: 31 March 2017
Published in: Combinatorica (Search for Journal in Brave)
Abstract: The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^n vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. Burr and Erdos in 1983 asked whether the simple lower bound r(Q_n, K_s) >= (s-1)(2^n - 1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.
Full work available at URL: https://arxiv.org/abs/1208.1732
Recommendations
Cites Work
- Title not available (Why is that?)
- Graph minors. XX: Wagner's conjecture
- The extremal function for complete minors
- Homomorphiesätze für Graphen
- Title not available (Why is that?)
- An extremal function for contractions of graphs
- Lower bound of the Hadwiger number of graphs by their average degree
- A separator theorem for string graphs and its applications
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- On Graphs that do not Contain a Thomsen Graph
- Ramsey Numbers Involving Graphs with Long Suspended Paths
- Title not available (Why is that?)
- Ramsey goodness and beyond
- Separators for sphere-packings and nearest neighbor graphs
- Ramsey-goodness -- and otherwise
- Cube Ramsey numbers are polynomial
- Dependent random choice
- Title not available (Why is that?)
- Title not available (Why is that?)
- On graphs with linear Ramsey numbers
- On bipartite graphs with linear Ramsey numbers
- The tail is cut for Ramsey numbers of cubes
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Density theorems for bipartite graphs and related Ramsey-type results
- Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
- On graphs with small Ramsey numbers
- Generalizations of a Ramsey-theoretic result of chvátal
- The Ramsey number of the clique and the hypercube
- Title not available (Why is that?)
- What can we hope to accomplish in generalized Ramsey theory ?
- Title not available (Why is that?)
- On the Ramsey number of the triangle and the cube
Cited In (10)
- Some Ramsey-type results for the \(n\)-cube
- Cube Ramsey numbers are polynomial
- A remark on the Ramsey number of the hypercube
- Title not available (Why is that?)
- Ramsey goodness of paths
- The Ramsey number of the clique and the hypercube
- Ramsey goodness of cycles
- Title not available (Why is that?)
- On the Ramsey number of the triangle and the cube
- Ramsey goodness of bounded degree trees
This page was built for publication: Ramsey numbers of cubes versus cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519968)
