Small on-line Ramsey numbers---a new approach

  • Pawel Pralat Ryerson University
  • Przemyslaw Gordinowicz Lodz University of Technology
Keywords: on-line Ramsey numbers

Abstract

In this note, we revisit the problem of calculating small on-line Ramsey numbers R(G,H). A new approach is proposed that reduces the running time of the algorithm determining that R(K_3,K_4)=17 by a factor of at least 2*10^6 comparing to the previously used approach. Using high performance computing networks, we determined that R(K_4,K_4) <= 26, R(K_3,K_5) < 25, and that R(K_3,K_3,K_3) <= 20 for a natural generalization to three colours. All graphs on 3 or 4 vertices are investigated as well, including non-symmetric cases.

Author Biography

Pawel Pralat, Ryerson University

Associate Professor, Department of Mathematics

Assistant Director of Industry Liaison
The Fields Institute for Research in Mathematical Sciences

References

1. J. Beck, Achievement games and the probabilistic method, Combinatorics, Paul Erdős is Eighty, vol. 1, Bolyai Soc. Math. Stud., 1993, pp. 51-78.

2. D. Conlon, On-line Ramsey numbers, SIAM J. Discrete Math. 23 (2009), 1954-1963.

3. J. Cyman and T. Dzido, A note on on-line Ramsey numbers for quadrilaterals, Opuscula Mathematica 34 (2014), 463-468.

4. J. Cyman, T. Dzido, J. Lapinskas, and A. Lo, On-line Ramsey number of paths and cycles, Electronic Journal of Combinatorics 22 (2015), #P1.15.

5. E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński, and P. Tetali, Ramsey games against one-armed bandit, Combin. Probab. Comput. 12 (2003), 515-545.

6. P. Gordinowicz and P. Prałat, programs written in C/C++ can be downloaded from http://www.math.ryerson.ca/~pralat/ or http://im0.p.lodz.pl/~pgordin/.

7. J. Grytczuk, H. Kierstead, and P. Prałat, On-line Ramsey numbers for paths and stars, Discrete Mathematics and Theoretical Computer Science 10 (2008), 63-74.

8. A. Kurek and A. Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), no. 1-2, 141-149.

9. B. D. McKay, nauty Users Guide (Version 2.5), http://cs.anu.edu.au/~bdm/nauty/.

10. B. D. McKay, Practical graph isomorphism, Congressus Numerantium 30 (1981), 45-87.

11. B. D. McKay and A. Piperno, Practical graph isomorphism II, J. Symbolic Computation 60 (2013), 94-112.

12. P. Prałat, A note on small on-line Ramsey numbers for paths and their generalization, Australasian Journal of Combinatorics 40 (2008), 27-36.

13. P. Prałat, R(3; 4) = 17, Electronic Journal of Combinatorics 15 (2008), #R67, 13pp.

14. P. Prałat, A note on off-diagonal small on-line ramsey numbers for paths, Ars Combinatoria 107 (2012), 295-306.

15. S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. Dynamic Survey DS1 (2014), 94, revision #14.

16. D. B. West, Introduction to graph theory, 2nd ed., Prentice Hall, 2001.
Published
2018-12-31
Section
Articles