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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3865318 (Why is no real title available?)
- scientific article; zbMATH DE number 3910431 (Why is no real title available?)
- scientific article; zbMATH DE number 3946178 (Why is no real title available?)
- scientific article; zbMATH DE number 4099362 (Why is no real title available?)
- scientific article; zbMATH DE number 3494449 (Why is no real title available?)
- scientific article; zbMATH DE number 3545699 (Why is no real title available?)
- scientific article; zbMATH DE number 1131467 (Why is no real title available?)
- A Separator Theorem for Nonplanar Graphs
- A Separator Theorem for Planar Graphs
- A separator theorem for string graphs and its applications
- An extremal function for contractions of graphs
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Cube Ramsey numbers are polynomial
- Density theorems for bipartite graphs and related Ramsey-type results
- Dependent random choice
- Generalizations of a Ramsey-theoretic result of chvátal
- Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
- Graph minors. XX: Wagner's conjecture
- Homomorphiesätze für Graphen
- Lower bound of the Hadwiger number of graphs by their average degree
- On Graphs that do not Contain a Thomsen Graph
- On bipartite graphs with linear Ramsey numbers
- On graphs with linear Ramsey numbers
- On graphs with small Ramsey numbers
- On the Ramsey number of the triangle and the cube
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Ramsey Numbers Involving Graphs with Long Suspended Paths
- Ramsey goodness and beyond
- Ramsey-goodness -- and otherwise
- Separators for sphere-packings and nearest neighbor graphs
- The Ramsey number of the clique and the hypercube
- The extremal function for complete minors
- The tail is cut for Ramsey numbers of cubes
- What can we hope to accomplish in generalized Ramsey theory ?
Cited in
(10)- Ramsey goodness of bounded degree trees
- Some Ramsey-type results for the \(n\)-cube
- Cube Ramsey numbers are polynomial
- A remark on the Ramsey number of the hypercube
- scientific article; zbMATH DE number 1372026 (Why is no real title available?)
- Ramsey goodness of paths
- The Ramsey number of the clique and the hypercube
- Ramsey goodness of cycles
- scientific article; zbMATH DE number 3880754 (Why is no real title available?)
- On the Ramsey number of the triangle and the cube
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)
