A class of Ramsey-extremal hypergraphs

Document Type : Research Paper

Author

Australian National University

Abstract

In 1991‎, ‎McKay and Radziszowski proved that‎, ‎however each $3$-subset of a $13$-set is assigned one of two colours‎, ‎there is some $4$-subset whose four $3$-subsets have the same colour‎. ‎More than 25 years later‎, ‎this remains the only non-trivial classical Ramsey number known for hypergraphs‎. ‎In this article‎, ‎we find all the extremal colourings of the $3$-subsets of a 12-set and list some of their properties‎. ‎We also provide an answer to a question of Dudek‎, ‎La Fleur‎, ‎Mubayi and R\"odl about the size-Ramsey numbers of hypergraphs‎.

Keywords

Main Subjects

References

[1] A. Dudek, S. La Fleur, D. Mubayi and V. Rodl, On the size-Ramsey numb er of hyp ergraphs, J. Graph Theory, to app ear, 2015, https://arxiv.org/abs/1503.06304.
[2] J. R. Isb ell, R (4;4;3)≥13, J. Combin. Th., 6 (1969).
[3] B. D. McKay, Combinatorial data, Online at, http://users.cecs.anu.edu.au/  b dm/data/ramsey.html.
[4] B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms, 26 (1998) 306-324.
[5] B. D. McKay and A. Pip erno, Practical Graph Isomorphism, II, J. Symbolic Comput., 60 (2014) 94-112.
[6] B. D. McKay and S. P. Radziszowski, The rst classical Ramsey number for hypergraphs is computed, Pro ceedings of the Second Annual ACM-SIAM Symp osium on Discrete Algorithms, SODA'91, San Francisco, (1991) 304-308.
[7] B. D. McKay and S. P. Radziszowski, R(4;5)=25, J. Graph Theory, 19 (1995) 309-322.
[8] S. P. Radziszowski, Small Ramsey Numb ers, Electron. J. Combin., 1 (1994) pp. 30.
Transactions on Combinatorics
Volume 6, Issue 3 - Serial Number 3
September 2017
Pages 37-43

Files

History

  • Receive Date: 04 December 2016
  • Revise Date: 30 December 2016
  • Accept Date: 05 January 2017
  • Published Online: 01 September 2017

Share

How to cite

Statistics