TUHH / Institut für Mathematik / Forschungsgebiete / Research Topic: Size-Ramsey Numbers Englische Flagge

Research Topic: Size-Ramsey Numbers

Collaborators (MAT): Dr. Dennis Clemens, Prof. Dr. Anusch Taraz

Collaborators (external): Barnaby Roberts, Guilherme Oliveira Mota, Mathias Schacht, Matthew Jenssen, Meysam Miralaei, Natasha Morrison, Yoshiharu Kohayakawa, Damian Reding

Given any graph \(H\), a natural question to ask is how large a Ramsey graph for \(H\) needs to be in terms of the number of edges. This leads to the definition of the size-Ramsey number \(\hat{r}(H)\), introduced in [EFRS1978], which is the smallest number of edges among all Ramsey graphs for \(H\).

Addressing a question posed by Erdős [Er1981], Beck [Be1983] proved that the size-Ramsey number of the path \(P_n\) on \(n\) vertices is linear in \(n\). That is, there exists a constant \(C>0\) such that \(\hat{r}(P_n)<Cn\) for all positive integers \(n\). We generalized this further by showing that powers of paths and cycles also have a linearly growing size-Ramsey number [CJKMMRR2019], which was extended even further in [BKMMMMP2019], [HJKMR2020], [KLWY2021].

Moreover, Rödl and Szemerédi [RS2000] conjectured that for every integer \(\Delta \geq 3\) there exists a positive real \(\varepsilon = \varepsilon(\Delta)\) such that \[ n^{1+\varepsilon} \leq \max \hat{r}(H) \leq n^{2-\varepsilon} \] for every large enough \(n\), where the maximum is taken over all \(H\) on \(n\) vertices and with maximum degree at most \(\Delta\). The upper bound of this conjecture was confirmed by Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS2011], but the lower bound remains an open problem. A natural candidate for proving the lower bound could be the grid \(G_{\lfloor \sqrt{n} \rfloor,\lfloor \sqrt{n} \rfloor}\) on (roughly) \(n\) vertices. While it is still unknown whether the grid supports the mentioned lower bound, we [CMRST2021] were able prove the currently best known upper bound on \(\hat{r}(G_{\lfloor \sqrt{n} \rfloor,\lfloor \sqrt{n} \rfloor})\), giving that

\[ \hat{r}(G_{\lfloor \sqrt{n} \rfloor,\lfloor \sqrt{n} \rfloor}) = O\left( n^{\frac{3}{2}+o(1)} \right)\, . \]

References

[Be1983] J. Beck, On size Ramsey number of paths, trees, and circuits. I, Journal of Graph Theory 7 (1), 115–129, 1983.

[BKMMMMP2019] S. Berger, Y. Kohayakawa, G. S. Maesaka, T. Martins, W. Mendonça, G. O. Mota, and O. Parczyk, The size‐Ramsey number of powers of bounded degree trees, Journal of the London Mathematical Society, 2019.

[CMRST2021] D. Clemens, M. Miralaei, D. Reding, M. Schacht and A. Taraz, On the size Ramsey number of grid graphs, Combinatorics, Probability and Computing, 1–16, 2021.

[CJKMMRR2019] D. Clemens, M. Jenssen, Y. Kohayakawa, N. Morrison, G. O. Mota, D. Reding and B. Roberts, The size-Ramsey number of powers of paths, Journal of Graph Theory 91(3), 290–299, 2019.

[Er1981] P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1), 25–42, 1981.

[EFRS1978] P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number, Periodica Mathematica Hungarica 9 (1-2), 145–161, 1978.

[HJKMR2020] J. Han, M. Jenssen, Y. Kohayakawa, G. O. Mota, and B. Roberts, The multicolour size-Ramsey number of powers of paths, Journal of Combinatorial Theory, Series B 145, 359-375, 2020.

[KLWY2021] N. Kamcev, A. Liebenau, D. R. Wood, and L. Yepremyan, The size Ramsey number of graphs with bounded treewidth. SIAM Journal on Discrete Mathematics 35(1), 281-293, 2021.

[KRSS2011] Y. Kohayakawa, V. Rödl, M. Schacht, and E. Szemerédi, Sparse partition universal graphs for graphs of bounded degree, Advances in Mathematics 226 (6), 5041–5065, 2011.

[RS2000] V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree, Combinatorica 20 (2), 257–262, 2000.