TUHH / Institut für Mathematik / Forschungsgebiete / Research Topic: Minimal Ramsey Graphs

# Research Topic: Minimal Ramsey Graphs

### Collaborators (external): Anita Liebenau, Anurag Bishnoi, Shagnik Das, Simona Boyadzhiyska, Yury Person

Burr, Erd?s and Lovász [2] initiated the systematic study of structural properties of minimal Ramsey graphs for a given graph $$H$$. Here, a minimal Ramsey graph for $$H$$ is defined to by a graph $$G$$ such that $$G\rightarrow H$$ holds, while $$G'\not\rightarrow H$$ for every proper subgraph of $$G$$. Surprisingly, while the famous Ramsey number $$r(K_n)$$ has not been determined yet, even though the problem exists for more than 70 years, Burr et al. where able to determine the minima of other graph parameters among all minimal Ramsey graphs of $$K_n$$.

In particular, a parameter attracting a lot of attention over the last years is the smallest possible minimum degree $$s_2(H)$$ over all minimal Ramsey graphs for $$H$$, see e.g. [1,4,5,6,7,8,9]. Burr et al. proved that $$s_2(K_n)=(n-1)^2$$, which is rather surprising given the known bounds on the Ramsey number. We generalized their result further [1] by showing that there exist minimal Ramsey graphs with arbitrarily many vertices of that minimum degree, giving also extensions to other graphs $$H$$ and to the analogous problem which considers colourings with more than two colours.

In general, it can be seen easily that $$s_2(H)\geq 2\delta(H)-1$$ holds, where $$\delta(H)$$ denotes the minimum degree of $$H$$. A graph $$H$$ is said to be Ramsey-simple if this lower bound is tight, and it has been conjectured that all bipartite graphs [9] and even all triangle-free graphs [8] are Ramsey-simple. Although these conjectures remain widely open, partial results were given in [8,9] supporting that these conjectures could be true. Currently, we are studying the behaviour of $$s_2(H)$$ and the question about Ramsey-simplicity if instead $$H$$ is a random graph.

Additionally, Szabó, Zumstein and Zürcher [9] asked to classify graphs by their Ramsey behaviour. To be more precise, they called two graphs $$H_1$$ and $$H_2$$ Ramsey-equivalent if the families of their minimal Ramsey graphs are equal. Rather surprisingly, it was shown by Fox et al. [5] that the clique $$K_n$$ is not equivalent to any other connected graph. Since then it has been conjectured that any two non-isomorphic connected graphs are non-equivalent. This conjecture still remains open. However, recently we proved that the conjecture were true if restricted to 3-connected graphs instead [3].