Ramsey properties of Cayley graphs

Ramsey properties of Cayley graphs

Definitions and mathematical statement

Let $A$ be a finite abelian group, written additively, with $N=|A|\geq2$ and identity $0$. For a set $S\subseteq A\setminus\{0\}$ satisfying $S=-S$, define the simple undirected Cayley graph $\operatorname{Cay}(A,S)$ on vertex set $A$ by joining distinct $x,y$ exactly when $y-x\in S$. Symmetry of $S$ makes adjacency independent of the order of the two vertices. The set $S$ is not required to generate $A$.

A clique is a vertex set all of whose distinct pairs are adjacent; an independent set has no adjacent pair. Their maximum sizes are denoted $\omega(G)$ and $\alpha(G)$, respectively. The conjecture asks whether there is an absolute real constant $c>0$ such that \[ \forall A\quad\exists S=-S\subseteq A\setminus\{0\}: \max\{\omega(\operatorname{Cay}(A,S)), \alpha(\operatorname{Cay}(A,S))\}\leq c\log N. \] Here $\log$ is the natural logarithm; changing its base only changes the permitted constant. The same $c$ must work for groups of every order and every isomorphism type, whereas $S$ may depend on the group. No probabilistic construction is mandated. The restriction $N\geq2$ removes the zero-logarithm boundary case and leaves the asymptotic problem unchanged. Both homogeneous-set bounds must hold for the same chosen Cayley graph.

Short English statement

Can every finite abelian group support a Cayley graph with neither a clique nor an independent set larger than a constant times the logarithm of its order?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature, conventions and plan.

The question in [S2] is an existence problem for difference Cayley graphs. Green's primary paper [R1] concerns random Cayley sum graphs; on groups of exponent two, sums and differences coincide. It shows that the simplest random model there need not achieve the desired logarithmic clique bound. Thus a random-edge heuristic cannot settle the question for every abelian group. We instead prove a weaker uniform existence bound by controlling all character eigenvalues, and locate exactly where that bound loses the required scale.

An elementary random spectral construction.

Partition $A\setminus\{0\}$ into inverse orbits $O=\{s,-s\}$, allowing singleton orbits. Include each entire orbit independently in $S$ with probability $1/2$. The graph is automatically simple and undirected. For a character $\chi:A\to\mathbb C^\times$, its adjacency eigenvalue is \[ \lambda_\chi=\sum_O B_Ow_O,\qquad w_O=\sum_{s\in O}\chi(s)\in\mathbb R, \] where $B_O$ is a fair Bernoulli variable. Character orthogonality gives $\mathbb E\lambda_\chi=-1/2$ for every nontrivial character. For the trivial character the eigenvalue is the degree $d$, with expectation $(N-1)/2$. The characters form an orthogonal eigenbasis, so all nonprincipal eigenvalues are covered by this calculation.

Since $|w_O|\le|O|\le2$, we have $\sum_Ow_O^2\le2(N-1)\le2N$. For the centered sum $Z=\sum_O(B_O-1/2)w_O$, independence and $\cosh u\le\exp(u^2/2)$ yield \[ \mathbb E e^{tZ}=\prod_O\cosh(tw_O/2) \le\exp(t^2N/4). \] Markov's inequality followed by optimization in $t>0$ gives $\Pr(|Z|\ge u)\le2\exp(-u^2/N)$. The same bound applies to the trivial character. Taking $u=\sqrt{N\log(8N)}$ and a union bound over all $N$ characters leaves failure probability at most $1/4$. Consequently some inverse-closed $S$ satisfies simultaneously \[ |d-(N-1)/2|\le u,\qquad |\lambda_\chi+1/2|\le u\quad(\chi\ne1). \] For $N\ge1024$, these inequalities give $d\ge N/4$ and also $N-1-d\ge N/4$. For example, $\log(8N)\le N/32$ throughout this range, which immediately implies the two degree estimates.

From eigenvalues to both homogeneous-set bounds.

Set $\Lambda=u+1/2$. For an independent set $I$ of size $a$, center its indicator by $z=1_I-(a/N)1$. Since the graph is $d$-regular, \[ z^TAz=-da^2/N,\qquad z^Tz=a-a^2/N. \] Every nonprincipal eigenvalue is at least $-\Lambda$, so $da^2/N\le\Lambda(a-a^2/N)$. For $a>0$, rearrangement gives \[ a\le\frac{N\Lambda}{d+\Lambda}\le4\Lambda. \] The complement is also a Cayley graph. Its nonprincipal eigenvalues are $-1-\lambda_\chi$, which have the same bound $\Lambda$, and its degree is at least $N/4$. Applying the independent-set estimate to that graph bounds cliques in the original one. We have therefore proved \[ \max(\alpha,\omega)\le4\sqrt{N\log(8N)}+2 \qquad(N\ge1024). \] Increasing an absolute constant handles smaller groups. This is a uniform existence result, but it is much weaker than $C\log N$.

Why independent-edge counting fails.

In $A=\mathbb F_2^m$, let $H$ be a $d$-dimensional subgroup. Its $2^d$ vertices form a clique precisely when every nonzero element of $H$ belongs to $S$. That event has probability $2^{-(2^d-1)}$, rather than $2^{-\binom{2^d}{2}}$. The corresponding independent-set event has the same probability. All edges with the same difference are tied to a single random choice. This exact calculation explains why applying the usual binomial random-graph union bound to Cayley edges would be invalid. It does not alone prove a high-probability obstruction: that would also require control of overlaps among subgroups, as addressed by more substantial work such as [R1].

Verification and final status.

All estimates treat elements of order two as singleton orbits, and complementation preserves the same identity-free convention. The spectral bound uses an actual simultaneous event of positive probability, not independently chosen graphs for the two homogeneous-set conditions. UNRESOLVED. The first missing step is a construction or counting argument reducing the square-root-scale bound to logarithmic size uniformly over all abelian groups. The independent character estimates proved here do not supply that improvement.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3147 (OPG-372), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Ramsey properties of Cayley graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/ramsey_properties_of_cayley_graphs.

• R1 Ben Green, Counting sets with small sumset, and the clique number of random Cayley graphs, 2003. Primary abstract checked 1 October 2026; its sum-graph convention is distinguished in the text. https://arxiv.org/abs/math/0304183.