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.