Some remarks on Folkman graphs for triangles

Abstract

Folkman's theorem asserts the existence of graphs $G$ which are $K_4$-free, but which have the property that every two-coloring of $E(G)$ contains a monochromatic triangle. The quantitative aspects of $f(2,3,4)$, the least $n$ such that there exists an $n$-vertex graph with both properties above, are notoriously difficult; a series of improvements over the span of two decades witnessed the solution to two $100 Erdős problems, and the current record due to Lange, Radziszowski, and Xu now stands at $f(2,3,4)\le 786$,with another $100 problem of Graham asking for a proof that $f(2,3,4)<100$. In this paper, we study Folkman-like properties of a sequence $H_q$ of finite geometric graphs constructed using Hermitian unitals in projective planes and present some evidence that the graph $H_3$, which has 63 vertices, might contain a Folkman graph as a proper subgraph. More precisely, we first prove that for all prime powers $q\ge 3$, there exists a system ${\mathcal{T}}_q$ of triangles in $H_q$ such that no four span a $K_4$ in $H_q$, but every two-coloring of $E(H_q)$ induces a monochromatic triangle in ${\mathcal{T}}_q$. We then show that a certain random alteration of $H_q$ which destroys all of its $K_4$'s will, for large $q$, maintain the Ramsey property with high probability.

17 pages, two figures; v4 includes a new author and a discussion of a number of computational experiments performed on the graph $H_3$