
A graph $G$ is Ramsey for a graph $H$ if every 2-colouring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a `sparse' graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.
Following the release of our original preprint, a positive answer to our Question 5.2 has been given in arXiv:1907.03466 . Also an alternative proof of Theorem 1.3 has been provided by Jonathan Rollin, which we added to the preprint. Subsequently concluding remarks have been changed, the remaining changes are minor
Ramsey numbers, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Ramsey number, anzsrc-for: 46 Information and Computing Sciences, anzsrc-for: 4613 Theory Of Computation, anzsrc-for: 0101 Pure Mathematics, anzsrc-for: 4904 Pure Mathematics, Trees, 4613 Theory Of Computation, 46 Information and Computing Sciences, FOS: Mathematics, Mathematics - Combinatorics, anzsrc-for: 0802 Computation Theory and Mathematics, 000, 4901 Applied Mathematics, Ramsey theory, 4904 Pure Mathematics, Generalized Ramsey theory, bounded-degree trees, 004, anzsrc-for: 49 Mathematical Sciences, 49 Mathematical Sciences, size ramsey number, Density (toughness, etc.), anzsrc-for: 4901 Applied Mathematics, Combinatorics (math.CO), size Ramsey number, bounded treewidth, Computer Science - Discrete Mathematics
Ramsey numbers, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Ramsey number, anzsrc-for: 46 Information and Computing Sciences, anzsrc-for: 4613 Theory Of Computation, anzsrc-for: 0101 Pure Mathematics, anzsrc-for: 4904 Pure Mathematics, Trees, 4613 Theory Of Computation, 46 Information and Computing Sciences, FOS: Mathematics, Mathematics - Combinatorics, anzsrc-for: 0802 Computation Theory and Mathematics, 000, 4901 Applied Mathematics, Ramsey theory, 4904 Pure Mathematics, Generalized Ramsey theory, bounded-degree trees, 004, anzsrc-for: 49 Mathematical Sciences, 49 Mathematical Sciences, size ramsey number, Density (toughness, etc.), anzsrc-for: 4901 Applied Mathematics, Combinatorics (math.CO), size Ramsey number, bounded treewidth, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
