Computation of new diagonal graph Ramsey numbers
Abstract
For various connected simple graphs G, we extend the table of diagonal graph Ramsey numbers R(G, G) in ‘An Atlas of Graphs.’ This is accomplished by first converting the calculation of R(G, G) into a satisfiability problem in propositional logic. Mathematical arguments and scientific computing are then used to calculate R(G, G).
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.17
References
S.A. Burr, Generalized Ramsey theory for graphs – A survey, Graphs and Combinatorics, Springer-Verlag, Berlin, 1974, pp. 52-75.
S.A. Burr, A survey of noncomplete Ramsey theory for graphs, Ann. New York Acad. Sci 328 (1979), 58-75.
S.A. Burr and P. Erdos, Extremal Ramsey theory for graphs, Utilitas Mathematica 9 (1976), 247-258.
G. Chartrand and P. Zhang, New directions in Ramsey theory, Discrete Math. Lett 6 (2021), 84-96.
V. Chvatal and F. Harary, Generalized Ramsey theory for graphs, III: small off-diagonal numbers, Pacific Journal of Mathematics 41 (1972), 335-345.
V. Chvatal and F. Harary, Generalized Ramsey theory for graphs, I: diagonal numbers, Periodica Mathematica Hungarica 3 (1973), 115-124.
D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170(2) (2009), 941-960.
R. Cowen, Deleting edges from Ramsey minimal examples, Amer. Math. Monthly 122(7) (2015), 681-683.
R. Cowen, Using Boolean computation to solve some problems from Ramsey theory, The Mathematica Journal, 2013. dx.doi.org/doi:10.3888/tmj.15-10.
C. Dalfó and M.A. Fiol, Graphs, friends and acquaintances, Electron. J. Graph Theory Appl 6(2) (2018), 282-305.
H.B. Enderton, A Mathematical Introduction to Logic, Second Edition. Academic Press, 2001.
R. Graham and S. Butler, Rudiments of Ramsey Theory, Second Edition. CBMS Regional Conference Series in Mathematics 123. American Mathematical Society, Providence, R.I., 2015. R. Graham, B. Rothschild, and J. Spencer, Ramsey Theory, Second Edition, Wiley, 2013.
J.W. Grossman, Some Ramsey numbers of unicyclic graphs, Ars Combin 8 (1979), 59-63.
C.J. Jayawardene, Diagonal Ramsey numbers in multipartite graphs related to stars, Electron. J. Graph Theory Appl 10(1) (2022), 227-237.
B.M. Landman and A. Robertson, Ramsey Theory on the Integers, Second Edition. Student Mathematical Library 73, American Mathematical Society, Providence, R.I., 2014.
C. Magnant and P.S. Nowbandegani, Topics in Gallai-Ramsey Theory, Springer International Publishing, 2020.
B.D. McKay and A. Piperno, Practical graph isomorphism, II. J. Symbolic Computation 60 (2013), 94-112.
S.P. Radziszowski, Small Ramsey numbers, Elect. J. Combin. 16 (2021), #DS1.
F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2) 30(4) (1929), 264-286.
R.C. Read and R.J. Wilson, An Atlas of Graphs, Oxford University Press, New York, 1998.
A. Robertson, Fundamentals of Ramsey Theory, First Edition, Chapman and Hall/CRC, 2021.
V. Rosta, Ramsey theory applications, Elect. J. Combin. (2004), #DS13.
A. Sah, Diagonal Ramsey via effective quasirandomness, preprint (arXiv: 2005.09251v1).
A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, Springer, New York, 2009.
B. Sudakov, Recent developments in extremal combinatorics: Ramsey and Turán type problems, Proceedings of the International Congress of Mathematics. Volume IV, 2579-2606, Hindustan Book Agency, New Delhi, 2010.
D.B. West, Introduction to Graph Theory, 2nd Ed., Pearson, 2017.
Wolfram Research, Inc., Mathematica, Version 12.3.1, Champaign, IL (2021).
X. Xu, M. Liang, and H. Luo, Ramsey Theory: Unsolved Problems and Results, University of Science and Technology of China Press, De Gruyter, Berlin/Boston, 2018.
X. Xu and S.P. Radziszowski, On some open questions for Ramsey and Folkman numbers, Graph Theory: Favorite Conjectures and Open Problems. Volume 1, 43-62, Probl. Books in Math., Springer, 2016.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.