Lower bounding the Folkman numbers $F_v(a_1,...,a_s;m-1)$

Abstract

For a graph $G$ the expression $G\stackrel{v}{\to }(a_1,...,a_s)$ means that for every $s$-coloring of the vertices of $G$ there exists $i\in \{1,...,s\}$ such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers $$F_v(a_1, ..., a_s; m - 1) = \min\{\vert V(G)\vert : G \overset{v}{\rightarrow} (a_1, ..., a_s) \mbox{ and } K_{m - 1} \not\subseteq 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\}\le 6$ and also the number $F_v(2,2,7;8)=20$. In \cite{BN15a} 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)\ge 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\le F_v(2,2,2,4;5)$ and $29\le F_v(7,7;8)$.

References in corpus (3)

• The edge Folkman number $F_e(3,3;4)$ is greater than 19
• The vertex Folkman numbers $F_v(a_1,...,a_s;m-1)=m+9$, if $\max \{a_1,...,a_s\}=5$
• Modified vertex Folkman numbers