Use of MAX-CUT for Ramsey Arrowing of Triangles

Authors Alexander Lange, Xiaodong Xu, Stanisław P. Radziszowski

Publication date 25 April 2014

Full work available at URL https://arxiv.org/abs/1207.3750

Folkman graphs MAX-CUT semidefinite programming relaxation

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Structural characterization of families of graphs (05C75) Semidefinite programming (90C22)

Abstract: In 1967, ErdH{o}s and Hajnal asked the question: Does there exist a

K_{4}

-free graph that is not the union of two triangle-free graphs? Finding such a graph involves solving a special case of the classical Ramsey arrowing operation. Folkman proved the existence of these graphs in 1970, and they are now called Folkman graphs. ErdH{o}s offered

100 f o r d e c i d i n g i f o n e e x i s t s w i t h l e s s t h a n

10^{10}

v e r t i c e s . T h i s p r o b l e m r e m a i n e d o p e n u n t i l 1988 w h e n S p e n c e r, i n a s e m i n a l p a p e r u s i n g p r o b a b i l i s t i c t e c h n i q u e s, p r o v e d t h e e x i s t e n c e o f a F o l k m a n g r a p h o f o r d e r

3 imes 10^9$ (after an erratum), without explicitly constructing it. In 2008, Dudek and R"{o}dl developed a strategy to construct new Folkman graphs by approximating the maximum cut of a related graph, and used it to improve the upper bound to 941. We improve this bound first to 860 using their approximation technique and then further to 786 with the MAX-CUT semidefinite programming relaxation as used in the Goemans-Williamson algorithm.

Recommendations

Cited in

(10)

This page was built for publication: Use of MAX-CUT for Ramsey Arrowing of Triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5412357)