On two problems in graph Ramsey theory
From MaRDI portal
Abstract: We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph contains a monochromatic copy of H. A famous result of Chv'atal, R"{o}dl, Szemer'edi and Trotter states that there exists a constant c(Delta) such that r(H) leq c(Delta) n for every graph H with n vertices and maximum degree Delta. The important open question is to determine the constant c(Delta). The best results, both due to Graham, R"{o}dl and Ruci'nski, state that there are constants c and c' such that 2^{c' Delta} leq c(Delta) leq 2^{c Delta log^2 Delta}. We improve this upper bound, showing that there is a constant c for which c(Delta) leq 2^{c Delta log Delta}. The induced Ramsey number r_{ind}(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. ErdH{o}s conjectured the existence of a constant c such that, for any graph H on n vertices, r_{ind}(H) leq 2^{c n}. We move a step closer to proving this conjecture, showing that r_{ind} (H) leq 2^{c n log n}. This improves upon an earlier result of Kohayakawa, Pr"{o}mel and R"{o}dl by a factor of log n in the exponent.
Recommendations
Cites work
- scientific article; zbMATH DE number 3243267 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- A conjecture of Erdős on graph Ramsey numbers
- A new upper bound for diagonal Ramsey numbers
- Density theorems for bipartite graphs and related Ramsey-type results
- Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
- Hypergraph packing and sparse bipartite Ramsey numbers
- Induced Ramsey numbers
- Induced Ramsey-type theorems
- Lower bounds of tower type for Szemerédi's uniformity lemma
- On Ramsey Numbers of Sparse Graphs
- On bipartite graphs with linear Ramsey numbers
- On graphs with linear Ramsey numbers
- On the Ramsey number of sparse 3-graphs
- Pseudo-random graphs
- Radius two trees specify χ‐bounded classes
- Ramsey numbers for sparse graphs
- Ramsey numbers of sparse hypergraphs
- Ramsey's theorem - a new lower bound
- Some remarks on the theory of graphs
- The Ramsey number of a graph with bounded maximum degree
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Two remarks on the Burr-Erdős conjecture
Cited in
(31)- A note on lower bounds for induced Ramsey numbers
- On induced Ramsey numbers for \(k\)-uniform hypergraphs
- Two extensions of Ramsey's theorem
- Ramsey numbers for multiple copies of sparse graphs
- A conjecture of Erdős on graph Ramsey numbers
- Ramsey-goodness -- and otherwise
- Ordered Ramsey numbers
- Ramsey good graphs with long suspended paths
- Monochromatic trees in random tournaments
- Induced Ramsey-type theorems
- Cycles Are Strongly Ramsey-Unsaturated
- Ramsey number of a connected triangle matching
- scientific article; zbMATH DE number 5717180 (Why is no real title available?)
- Two average value theorems on the Ramsey problem and an initial exploration of their applications
- scientific article; zbMATH DE number 2197902 (Why is no real title available?)
- The critical window for the classical Ramsey-Turán problem
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- A note on pseudorandom Ramsey graphs
- A note on induced Ramsey numbers
- Erdős-Hajnal-type theorems in hypergraphs
- Ramsey graphs induce subgraphs of many different sizes
- Sizes of induced subgraphs of Ramsey graphs
- An efficient container lemma
- A Canonical Ramsey Theorem
- Short proofs of some extremal results. II.
- Induced Ramsey-type theorems
- scientific article; zbMATH DE number 3863243 (Why is no real title available?)
- A precise threshold for quasi-Ramsey numbers
- scientific article; zbMATH DE number 1404122 (Why is no real title available?)
- On edge-ordered Ramsey numbers
- Monochromatic bounded degree subgraph partitions
This page was built for publication: On two problems in graph Ramsey theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377800)
