Suppose you color the edges of a graph with as many colors as possible, subject to one rule: no path on $k$ vertices may be rainbow, meaning every edge on it gets a different color. The largest number of colors you can use is the anti-Ramsey number $ar(G, P_k)$. Computing it is NP-hard for every $k \ge 3$. The only nontrivial family where it is known to be tractable is trees. This proposal asks what happens on the most symmetric graphs there are: circulant and Cayley graphs, where every vertex looks like every other.
The question matters for graph learning as much as for combinatorics. A graph neural network that respects the graph's symmetries (an equivariant network, whose outputs move consistently when the graph is relabeled) cannot tell apart two edges that an automorphism swaps. On a vertex-transitive graph, it can therefore only output colorings whose color classes are permuted among themselves by the symmetries. Whether such networks can even represent an optimal coloring therefore reduces to a crisp combinatorial question. Does some optimal $P_k$-free coloring survive under a large subgroup of the automorphism group? We propose to measure this "symmetry gap" exactly on small Cayley hosts, prove tractability results for sparse circulants, and use the answer to decide how much symmetry breaking a learned colorer actually needs.
Core Claim
For a host graph $G$, a subgroup $H$ of its automorphism group, and a path length $k$, let $ar_H(G,P_k)$ be the maximum palette over $P_k$-free colorings whose partition into color classes is $H$-stable. $H$-stable means every $h \in H$ maps each color class onto some color class. Define the symmetry gap
$$\Delta_H(G,k) = ar(G,P_k) - ar_H(G,P_k) \ge 0.$$
An equivariant model that decides "same color or not" for each pair of edges can only reach $ar_{\mathrm{Aut}(G)}$, or less if its message passing cannot separate orbits. Our hypothesis is that on circulant and small Cayley hosts, $\Delta_H$ is large for $H = \mathrm{Aut}(G)$ but drops to zero for subgroups of small index. The known extremal colorings of complete graphs point this way: they are far from fully symmetric but are fixed by the stabilizer of a few vertices. If the hypothesis holds, a model needs only coset-level symmetry breaking, not arbitrary random identifiers. Exact search can also be restricted to $H$-stable colorings, which shrinks the number of variables by roughly $|H|$.
There is also a structural result that makes sparse circulants tractable. Call two edges co-path if some path on $k$ vertices contains both. Splitting any color class into its connected components under the co-path relation keeps the coloring $P_k$-free: two same-colored edges on a common path are co-path, so they stay together. The split also never lowers the palette. Hence some optimal coloring has every class co-path connected. This generalizes the "color connected coloring" lemma behind the linear-time tree algorithm in Complexity of computing the anti-Ramsey numbers for paths.
On a circulant $C_n(S)$ with a fixed connection set $S$ of largest element $s$, every path on $k$ vertices lies inside a window of $(k-1)s$ consecutive vertices. A dynamic program can therefore sweep around the cycle, tracking only the equality pattern among edges inside the current window. Run as a max-plus transfer matrix, it computes $ar(C_n(S),P_k)$ in time linear in $n$. Standard max-plus cyclicity then implies that the sequence is eventually periodic in $n$. The state space is a Bell number in the window size, so this is practical only for tiny $S$ and $k$. It is still the first exact algorithm we know of beyond trees, and it supplies ground truth at sizes no SAT solver reaches.
Relation to Prior Work
The anti-Ramsey side comes from one line of work. Complexity of computing the anti-Ramsey numbers for paths proves NP-hardness for all fixed $k \ge 3$ via gadget reductions from maximum independent set. It shows $n^{-1/2-\epsilon}$ inapproximability for $P_3$ on 3-partite graphs and an exponential-time lower bound for the precolored version, and gives the $O(|V(T)|k^4)$ tree algorithm. That paper motivates this one, because it leaves symmetric hosts open. It also constrains it: its gadgets are asymmetric, so hardness on symmetric graphs is genuinely unknown rather than implied.
The bounded-treewidth results in On the complexity of rainbow coloring problems rely on monadic second-order logic, a formal language whose formulas yield linear-time algorithms on bounded-treewidth graphs. That method needs a fixed number of colors. The palette here is unbounded, so our window dynamic program does not follow from it. Locally Rainbow Paths shows that locality in the rainbow condition is what separates tractable walks from hard paths. This supports exploiting the bounded span of $P_k$ on sparse circulants.
The symmetry side supplies technique. The Lovász number of random circulant graphs uses the cyclic group to diagonalize a semidefinite program with the Fourier transform, turning it into a linear program. We borrow the logic in a weaker form. Any linear-programming relaxation of the anti-Ramsey integer program has an $\mathrm{Aut}(G)$-invariant optimum, because averaging a feasible solution over the group preserves feasibility and objective. Upper bounds on larger instances can therefore be computed in orbit space. Unlike that paper, we expect no closed-form spectral answer, and the relaxation may be loose.
The algebraic encoding in An Algebraic Characterization of Rainbow Connectivity maps rainbow conditions to roots of unity and Nullstellensatz certificates, but never uses automorphisms. We use plain SAT encodings instead, since its own analysis notes worst-case blowup in certificate degree.
The learning side is represented by Interpretable Graph Networks Formulate Universal Algebra Conjectures. Its interpretable graph network forces node embeddings through a discrete bottleneck of concept tokens, which a linear classifier reads. In this way it rediscovered the forbidden sublattices $M_3$ and $N_5$ and generalized from 8-node to 50-node lattices. We reuse that bottleneck, moved from nodes to edge pairs, to surface the recurring local merge patterns in optimal colorings. That paper itself flags that its network struggles with non-local, non-structural properties. Anti-Ramsey optima are partly non-local, so this transfer is a risk we test rather than assume.
Constructive neural solvers, Learning Combinatorial Optimization Algorithms over Graphs and BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, generalize across scale on vertex cover and routing problems. BQ-NCO notes that early choices with cascading infeasibility are hard for such methods. That is exactly the anti-Ramsey situation, which is why our learned colorer always ends with a repair step.
Research Program
The first component is exact ground truth. We encode $P_k$-free colorings as SAT and integer programs, with one variable for each edge pair saying "same color" plus transitivity and rainbow-path clauses. We solve them on circulants up to about $n=30$ with $|S|\le 4$ and $k\in\{3,4,5\}$. We add dihedral Cayley graphs and the small 4-valent tri-Cayley graphs over cyclic groups constructed in The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group and classified in A Classification of 4-Degree Tri-Cayley Graphs Over a Group of Order 𝑝q. For each instance, we compute $ar$ and $ar_H$ for every subgroup $H$ of the cyclic or regular part of the automorphism group. This is cheap for $\mathbb{Z}_n$, whose subgroups are indexed by the divisors of $n$. The result is a table of symmetry gaps across groups, densities and $k$, the central empirical object of the project.
The second component is theory. We will prove the co-path connectivity lemma and the transfer-matrix algorithm for fixed $S$, and validate it against the exact solver on overlapping sizes. We will then attempt either a hardness reduction or a gap-zero theorem for dense circulants, guided by the table. Concretely, if $\Delta_H$ vanishes for index-two subgroups, $H$-stable colorings live on a half-size quotient, and we would try to prove that this restriction is lossless.
The third component is learning. We train an edge-pair "same color" decoder on top of a message-passing network at three controlled levels of symmetry breaking. The first is none, so the network is fully equivariant. The second is coset marks, where each vertex is tagged by its coset of a chosen subgroup $H$. The third is independent random identifiers. Every output goes through a repair procedure that keeps finding rainbow $P_k$ and merging two of its classes, so all outputs are valid colorings. The theory predicts that the equivariant model is capped at $ar_{\mathrm{Aut}}$, and that coset marks for the right $H$ match random identifiers while generalizing better from $n\le 20$ to $n\approx 60$. Separately, an edge-level concept bottleneck in the style of the interpretable graph network is trained to predict which edges share a class in optimal colorings. Its concept tokens are inspected and turned into candidate structural lemmas, which the exact solver then checks.
Baselines
The naive reference point is a greedy colorer. It starts from a rainbow coloring and, in random edge order, merges classes whenever a rainbow $P_k$ appears, keeping the best of 100 restarts. It costs almost nothing and sets the floor every learned method must clear.
The strongest exact competitor is a SAT or integer-programming solver with standard lexicographic symmetry-breaking clauses, run on identical encodings, hardware and wall-clock limits as our orbit-restricted search. No paper in the file reports anti-Ramsey computations with such solvers. In fact, no reported result found on Lacuna for computing $ar(G,P_k)$ empirically on any graph family; the literature is purely theoretical. Beating this baseline means one of two things. Either the orbit-restricted search certifies the same optimum on instances where the plain solver times out, or the transfer-matrix algorithm gives exact values at sizes beyond its reach.
The strongest heuristic competitor is simulated annealing over partitions with merge, split and move operations. It gets the same time budget as the neural model plus repair, and is tuned on the training sizes. A constructive neural solver in the style of Learning Combinatorial Optimization Algorithms over Graphs is adapted to sequential merge decisions, with the same training data and repair. That paper reports vertex-cover approximation ratios "very close to 1.0", but on a different problem, so it serves as context rather than a target. A learned method beats these baselines if it achieves a higher repaired palette, measured as the fraction of the exact or transfer-matrix optimum, on held-out sizes at least twice the training size.
The key ablation varies only the symmetry-breaking input (none, coset marks for each candidate $H$, random identifiers) with architecture and tuning budget fixed. It tests whether performance tracks the measured $\Delta_H$ as predicted.
Why not just…?
Why not just run a SAT solver with symmetry breaking and skip the rest? For small instances we do exactly that, and it is our ground truth. But generic symmetry breaking only removes duplicate search. It does not say whether the optimum lies in a symmetric subspace, which is the scientific question here. The exponential lower bound for the precolored problem in Complexity of computing the anti-Ramsey numbers for paths also suggests the plain solver will stall quickly as $n$ grows. The head-to-head timing comparison will show whether orbit restriction buys real scale; if it does not, we will say so.
Why not just add random node identifiers, the standard fix for equivariant networks? This is a genuine threat. If random identifiers generalize as well as coset marks, the subgroup analysis has no practical consequence for learning, and the contribution reduces to the combinatorial table and the algorithm. The ablation settles it directly. Our prediction rests on random identifiers forcing the model to learn the symmetric structure from scratch at each size, which should hurt extrapolation from $n\le 20$ to $n\approx 60$.
Why not use tree-decomposition dynamic programming? For sparse circulants with fixed $S$, our transfer matrix essentially is such a program. Its correctness requires the co-path lemma, because the palette is unbounded and the fixed-color logic methods of On the complexity of rainbow coloring problems do not apply. For dense circulants and Cayley graphs, the window and treewidth grow with $n$, so this approach is unavailable exactly where the open problem lives.
Why not inspect the optimal colorings by hand instead of training a concept network? With hundreds of instances across groups and path lengths, hand inspection is slow but possible, and we will do some of it. The concept network is only worth keeping if it beats a simple model on hand-built edge features: orbit index, difference value, and the edge's position on short paths. The bar is predicting same-color pairs on held-out larger hosts, measured by accuracy and by the palette after repair. If it does not beat that model, we drop it.
Proposed Experiments
The decisive check is the symmetry-gap table. If $\Delta_{\mathrm{Aut}}=0$ on most instances, fully equivariant models suffice and the subgroup story is moot. If $\Delta_H>0$ for every nontrivial $H$, the coset-symmetry-breaking prediction fails. We expect an intermediate pattern that depends on density and $k$, and we report whichever pattern appears.
The second check validates the transfer-matrix algorithm against SAT on all overlapping sizes and reports the period of $ar(C_n(S),P_k)$ in $n$ for small $S$. The third reports orbit-space linear-programming upper bounds next to the best constructions on circulants up to $n\approx 200$, stating the remaining gap honestly. The fourth runs the learning ablation, scoring repaired palette as a fraction of the certified optimum or of the best upper bound. Its training data uses $n\le 20$ and its test data uses $n$ up to 60 on circulants and the tri-Cayley families. Every number reported is our own, since the file contains no prior empirical anti-Ramsey results to compare against.
References
- Complexity of computing the anti-Ramsey numbers for paths
- On the complexity of rainbow coloring problems
- Locally Rainbow Paths
- The Lovász number of random circulant graphs
- An Algebraic Characterization of Rainbow Connectivity
- Interpretable Graph Networks Formulate Universal Algebra Conjectures
- Learning Combinatorial Optimization Algorithms over Graphs
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group
- A Classification of 4-Degree Tri-Cayley Graphs Over a Group of Order 𝑝q