LOWER BOUNDING THE FOLKMAN NUMBERS $F_v(a_1, . . . , a_s;m − 1)$

Abstract

For a graph $G$ the expression $G\overset{v}{\rightarrow}(a_1,...,a_s)$ means that for every $s$-coloring of the vertices of $G$ there exists $i\in\{1,2,...,s\}$ there exists a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers \[ F_v(a_1,...,a_s;m-1) =\min\{|V(G)|:G\overset{v}{\rightarrow}(a_1,...,a_s)\text{ and }K_m-1\nsubseteq G\}\] are considered, where $m = \sum_{i=1}^{s}(a_i - 1) + 1$. We know the exact values of all the numbers $F_v(a_1, . . . , a_s;m − 1)$ when $max\{a_1, . . . , a_s\} \leq 6$ and also the number $F_v(2, 2, 7; 8) = 20$. In [1] we present a method for obtaining lower bounds on these numbers. With the help of this method and a new improved algorithm, in the special case when $max\{a_1, . . . , a_s\} = 7$ we prove that $F_v(a_1, . . . , a_s;m − 1) \geq m + 11$ and this bound is exact for all m. The known upper bound for these numbers is $m + 12$. At the end of the paper we also prove the lower bounds $19 \leq F_v(2, 2, 2, 4; 5)$ and $29 \leq F_v(7, 7; 8)$.