Cayley-Sum Constructions for Triangle Ramsey Numbers

Definitions and mathematical statement

For an integer $k\geq 3$, let $R(3,k)$ be the least integer $N$ such that every finite simple graph on $N$ vertices contains a triangle or an independent set of size $k$. Write $\alpha(G)$ for the independence number of a graph $G$, and use the convention that $\log$ denotes the natural logarithm.

For a positive integer $d$, let $V_d={\mathbb{F}}_2^d$. A set $S\subseteq V_d$ is sum-free if there are no $a,b,c\in S$, with repetitions allowed, satisfying $a+b=c$. In particular, $0\notin S$. Define the Cayley-sum graph $G_d(S)$ on vertex set $V_d$ by joining distinct vertices $x,y$ exactly when $x+y\in S$. If $S$ is sum-free, then $G_d(S)$ is triangle-free. Thus $\alpha(G_d(S))<k$ implies $R(3,k)>2^d$.

Construction question, conditional on specifying the process. Can the sum-free process intended by the source produce sum-free sets $S_j\subseteq{\mathbb{F}}_2^{d_j}$, for integers $d_j\to\infty$ and $k_j\to\infty$, such that \[ \alpha\left(G_{d_j}(S_j)\right)<k_j, \qquad 2^{d_j}\geq\left(\frac12-\varepsilon_j\right)\frac{k_j^2}{\log k_j}, \qquad \varepsilon_j\geq0,\quad \varepsilon_j\longrightarrow0? \] These conditions express an existential construction yielding the requested Ramsey lower bound along an infinite sequence. They do not specify a probability of success. The supplied record does not define the sum-free process, its selection probabilities, its stopping rule, or whether the intended assertion is existence, positive probability, or probability tending to one. Consequently, this is a conditional formulation of the target, not a complete specification of the proposed random construction.

Scope and source qualifications. The original excerpt also appears to state the broader conjecture \[ R(3,k)=\left(\frac12+o(1)\right)\frac{k^2}{\log k} \qquad (k\to\infty), \] but its displayed formula is corrupted in the supplied transcription. The clean statement asks only about the proposed Cayley-sum construction and a lower bound along an infinite sequence; it does not request a matching upper bound.

The excerpt separately describes sampling a random graph on $n/(\log n)^2$ vertices at density $p_0=\alpha_0(\log n/n)^{1/2}$, removing triangles, taking a blow-up, and running a modified triangle-free process. It describes manually steering that process, attributes a simpler proof of an earlier lower bound to the version without the seed step, and suggests that combining randomness with structure may improve on the natural triangle-free process. These are supplied contextual claims. The excerpt supplies neither the parameter restrictions and rounding conventions nor the cleaning, blow-up, steering, and stopping rules needed to define that construction, and it does not explain its relationship to the proposed sum-free process. It expressly says that the authors were unable to provide a construction attaining the proposed constant $1/2$.

Short English statement

The question asks whether a specified sum-free process on ${\mathbb{F}}_2^d$ can produce triangle-free Cayley-sum graphs with sufficiently small independent sets to witness the Ramsey lower bound with asymptotic constant $1/2$ along infinitely many values of $k$. The process and its intended success probability are missing. The supplied open status and dated literature assessment require independent review.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json, permanent ID $30006401$, source problem code catalogue entry, title Cayley-Sum Constructions for Triangle Ramsey Numbers. The supplied record lists proposed year 2025 and no named proposer.
• Supplied source citation: Combinatorics, Probability and Computing (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/42, pp. 2243--2322. https://doi.org/10.4171/owr/2025/42. The literature-source list labels this same reference Oberwolfach Report 42/2025.
• Supplied literature source: Improving R(3,k) in just two bites. https://arxiv.org/abs/2510.19718.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that the conjectured asymptotic for $R(3,k)$ remains unresolved, with a lower-bound constant of one half in the 2025--2026 literature but no matching upper bound. This is supplied dated curation, not independently verified. It does not establish that the specific Cayley-sum construction achieves that constant.
• The original excerpt cites references [3] and [8], Theorem 1, and a lower bound numbered (1), without supplying their identities or complete statements. The registry labels the statement corrected_verified and describes its changes as typographical; this supplied label does not constitute independent mathematical verification.