What This Research Is About
Imagine you have a graph (a collection of dots, or vertices, connected by lines, or edges). Now imagine you want to write numbers on each edge, using every number from 1 to the total number of edges exactly once.
For each dot, add up all the numbers on edges touching it. The question is: can you arrange the edge numbers so that every dot gets a uniquely different sum, and those sums form a perfectly spaced sequence?
That's an (a,d)-antimagic labeling. The "a" is the starting sum, and "d" is the spacing between consecutive sums. Think of it like tuning a musical instrument: you're trying to make all the notes land exactly where they should.
Why Complete Graphs?
A complete graph K_n connects every dot to every other dot, like a round-robin tournament where every team plays every other team exactly once. For odd n (5, 7, 9, 11, ...), these graphs have a beautiful round-robin decomposition that makes the problem tractable.
The open question was: for every odd K_n, can you always find valid antimagic labelings for every possible spacing d from 1 to the maximum?
Two Approaches: Theory + Computation
The research combined pure mathematics with computational verification:
Theory side: We developed an "affine block synthesis" framework, a systematic method to construct labelings by controlling the sum of labels in each round. This required new algebraic gadgets, including a novel "slope-1 two-block gadget" that finally covered a boundary slope that previous methods couldn't reach.
We also proved a no-go theorem: one natural construction approach is impossible for n ≥ 5, which redirected the work toward the block synthesis method.
Computation side: We built a constraint solver (using Google's OR-Tools CP-SAT) to verify that valid labelings actually exist for K_5, K_7, K_9, ..., K_25. All 77 baseline test cases returned OPTIMAL, confirming existence.
The Conjecture
Based on the theoretical framework and computational evidence, the work supports the conjecture that valid (a,d)-antimagic labelings exist for every odd n and every slope d from 1 to the maximum. The computation confirms this for all n ≤ 25. The general proof remains open.
Research Focus (Technical)
An (a,d)-antimagic labeling of a graph assigns distinct integers 1 through |E| to its edges such that the vertex sums (the sum of labels on edges incident to each vertex) form an arithmetic progression (a, a+d, a+2d, ...). The central question: for odd complete graphs K_n with t = (n−1)/2, does a valid (a,d)-antimagic labeling exist for every slope d from 1 to t?
No-Go Theorem
The first structural result was a proof that scalar-identity-based round sum control is fundamentally impossible for odd n ≥ 5. Specifically, no edge-bijective labeling can satisfy the identity s_f(v) = ΣW(r) − W(2v) across all vertices, because summing over all vertices forces n = 3. This ruled out a natural but flawed shortcut and redirected the approach toward block synthesis.
Affine Block-Synthesis Framework
The core theoretical contribution is an affine block-synthesis model that decomposes the m = nt edge labels into t blocks of size n, then controls round sums W(r) = C_d + d(r+1) through three algebraic gadgets:
- Pair gadget: two permutations summing to a constant (n+1)
- Triple gadget: three permutations summing to a constant (3(n+1)/2)
- Slope-1 two-block gadget (new): two permutations with sum (t+1)+(r+1), covering the boundary slope d = t−1 for the first time
These gadgets combine into four template types that together cover every slope d from 1 to t for all odd n:
| Template | Slope covered |
|---|---|
| Synchronous | d = t |
| Boundary-slope (new) | d = t−1 |
| Even-remainder | t−d even |
| Odd-remainder | t−d odd, n ≥ 9 |
Computational Pipeline
I built a modular Python and OR-Tools CP-SAT solver pipeline with:
- AllDifferent constraints on edge labels (bijection) and vertex progression indices
- Symmetry-breaking constraints (x_0 = 1, t_0 = 0) to prune the search space
- Math-based pruning that rules out infeasible (n, d) pairs before invoking the solver, using divisibility conditions on a and degree-based weight bounds
- Parallel execution across 28 workers for large-n experiments
- Independent verification of every found labeling
- Seed retry strategy with up to 3 retries using prime-offset seeds for robustness
Results
All 77 baseline instances for odd n ≤ 25 and d from 1 to t returned OPTIMAL:
| n | Slopes verified | Slowest solve |
|---|---|---|
| 5–13 | d = 1 to t | < 2 sec |
| 15–19 | d = 1 to t | < 54 sec |
| 21 | d = 1–10 | 371 sec |
| 23 | d = 1–11 | 1,934 sec |
| 25 | d = 1–12 | 1,378 sec |
Robustness was confirmed for n = 19 with 10 independent seeds across all 9 slopes: 90/90 runs returned OPTIMAL. Across all experiment phases, 2,288 total cases were executed (K_n and K(m,n) combined).
Conjecture
Based on these results, the work supports the conjecture that for every odd n = 2t+1 ≥ 5 and every d from 1 to t, a valid (a,d)-antimagic labeling of K_n exists. Computationally established for all n ≤ 25; the general proof for template-to-labeling realizability remains an open problem.