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

# Research Topic: Size-Ramsey Numbers

### 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

[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.