Ramsey numbers of sparse hypergraphs
From MaRDI portal
Abstract: We give a short proof that any k-uniform hypergraph H on n vertices with bounded degree Delta has Ramsey number at most c(Delta, k)n, for an appropriate constant c(Delta, k). This result was recently proved by several authors, but those proofs are all based on applications of the hypergraph regularity method. Here we give a much simpler, self-contained proof which uses new techniques developed recently by the authors together with an argument of Kostochka and R"odl. Moreover, our method demonstrates that, for k geq 4, c(Delta, k) leq 2^{2^{Ddots^{2^{c Delta}}}}, where the tower is of height k and the constant c depends on k. It significantly improves on the Ackermann-type upper bound that arises from the regularity proofs, and we present a construction which shows that, at least in certain cases, this bound is not far from best possible. Our methods also allows us to prove quite sharp results on the Ramsey number of hypergraphs with at most m edges.
Recommendations
Cites work
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- A few remarks on Ramsey--Turán-type problems
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- A new upper bound for diagonal Ramsey numbers
- Combinatorial Theorems on Classifications of Subsets of a Given Set
- Density theorems for bipartite graphs and related Ramsey-type results
- Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
- scientific article; zbMATH DE number 3494449 (Why is no real title available?)
- Hypergraph packing and sparse bipartite Ramsey numbers
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems
- On bipartite graphs with linear Ramsey numbers
- On graphs with linear Ramsey numbers
- On graphs with small Ramsey numbers
- On Ramsey Numbers of Sparse Graphs
- On Ramsey numbers of uniform hypergraphs with given maximum degree
- On the Ramsey number of sparse 3-graphs
- Ramsey numbers for sparse graphs
- Regularity Lemma for k-uniform hypergraphs
- The counting lemma for regular k‐uniform hypergraphs
- The Ramsey number of a graph with bounded maximum degree
Cited in
(34)- On the Ramsey number of sparse 3-graphs
- On the Ramsey-Turán numbers of graphs and hypergraphs
- The Ramsey number of Fano plane versus tight path
- Phase transitions in Ramsey-Turán theory
- Boolean lattices: Ramsey properties and embeddings
- Dependent random choice
- A hypergraph blow-up lemma
- A counting lemma for sparse pseudorandom hypergraphs
- Hypergraph packing and sparse bipartite Ramsey numbers
- Hypergraph Ramsey numbers
- On two problems in graph Ramsey theory
- Ramsey numbers of 3-uniform loose paths and loose cycles
- Monochromatic loose-cycle partitions in hypergraphs
- Globally sparse vertex‐ramsey graphs
- On Ramsey Numbers of Sparse Graphs
- Monochromatic bounded degree subgraph partitions
- On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
- Diagonal Ramsey numbers of loose cycles in uniform hypergraphs
- Partitioning edge-colored hypergraphs into few monochromatic tight cycles
- Simplicial homeomorphs and trace-bounded hypergraphs
- Ramsey numbers of ordered graphs
- Clique-factors in graphs with sublinear -independence number
- Erdős-Szekeres theorem for multidimensional arrays
- Ramsey numbers for multiple copies of sparse graphs
- On ordered Ramsey numbers of tripartite 3-uniform hypergraphs
- Canonical Ramsey numbers of sparse graphs
- Polynomial bounds for monochromatic tight cycle partition in \(r\)-edge-coloured \(K_n^{(k)}\)
- Ramsey numbers of hypergraphs with a given size
- Lower bounds for Ramsey numbers of bounded degree hypergraphs
- Minimal ordered Ramsey graphs
- Sparse Ramsey graphs
- On Ramsey numbers of uniform hypergraphs with given maximum degree
- Ramsey goodness and beyond
- Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
This page was built for publication: Ramsey numbers of sparse hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5893929)
