# Research Topic: Minimal Ramsey Graphs

### Collaborators (MAT): Dr.Â Dennis Clemens

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

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

## References

[1] S. Boyadzhiyska, D. Clemens, and P. Gupta. Minimal Ramsey graphs with many vertices of small degree, submitted, available on arXiv: 2009.04159

[2] S. A. Burr, P. ErdĹ‘s, and L. LovĂˇsz, On graphs of Ramsey type, *Ars Combinatoria* 1 (1), 167â€“190, 1976.

[3] D. Clemens, A. Liebenau, and D. Reding. On minimal Ramsey graphs and Ramsey equivalence in multiple colours, *Combinatorics, Probability and Computing* 29(4), 537â€“554, 2020.

[4] D. Clemens, and Y. Person. Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs, *Combinatorics, Probability and Computing* 25, 850â€“869, 2016

[5] J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. SzabĂł, What is Ramsey-equivalent to a clique?, *Journal of Combinatorial Theory, Series B* 109, 120â€“133, 2014.

[6] J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. SzabĂł, On the minimum degree of minimal Ramsey graphs for multiple colours, *Journal of Combinatorial Theory, Series B* 120, 64â€“82, 2016.

[7] J. Fox and K. Lin, The minimum degree of Ramsey-minimal graphs, *Journal of Graph Theory* 54 (2), 167-177, 2017.

[8] A. Grinshpun, Some problems in graph Ramsey theory, Ph.D.Â thesis, Massachusetts Institute of Technology, 2015.

[9] T. SzabĂł, P. Zumstein, and S. ZĂĽrcher, On the minimum degree of minimal Ramsey graphs, *Journal of Graph Theory* 64 (2), 150â€“164, 2010.