The edge Folkman number $F_e(3,3;4)$ is greater than 19

Abstract

The set of the graphs which do not contain the complete graph on $q$ vertices $K_q$ and have the property that in every coloring of their edges in two colors there exist a monochromatic triangle is denoted by ${\mathcal{H}}_e(3,3;q)$. The edge Folkman numbers $F_e(3,3;q)=\min \{|V(G)|:G\in {\mathcal{H}}_e(3,3;q)\}$ are considered. Folkman proved in 1970 that $F_e(3,3;q)$ exists if and only if $q\ge 4$. From the Ramsey number $R(3,3)=6$ it becomes clear that $F_e(3,3;q)=6$ if $q\ge 7$. It is also known that $F_e(3,3;6)=8$ and $F_e(3,3;5)=15$. The upper bounds on the number $F_e(3,3;4)$ which follow from the construction of Folkman and from the constructions of some other authors are not good. In 1975 Erdos posed the problem to prove the inequality $F_e(3,3;4)<10^{10}$. This Erdos problem was solved by Spencer in 1978. The last upper bound on $F_e(3,3;4)$ was obtained in 2012 by Lange, Radziszowski and Xu, who proved that $F_e(3,3;4)\le 786$. The best lower bound on this number is 19 and was obtained 10 years ago by Radziszowski and Xu. In this paper, we improve this result by proving $F_e(3,3;4)\ge 20$. At the end of the paper, we improve the known bounds on the vertex Folkman number $F_v(2,3,3;4)$ by proving $20\le F_v(2,3,3;4)\le 24$.

References in corpus (2)

• Use of MAX-CUT for Ramsey Arrowing of Triangles
• Small minimal $(3,3)$-Ramsey graphs

Cited by in corpus (3)

• On the independence number of $(3,3)$-Ramsey graphs and the Folkman number $F_e(3,3;4)$
• Lower bounding the Folkman numbers $F_v(a_1,...,a_s;m-1)$
• New bounds on the vertex Folkman number $F_v(2,2,2,3;4)$