A vertex of J±(n, 4) is a vector with four entries ±1 and the rest 0; two vertices are joined exactly when their caps would overlap. A maximum independent set, together with the 2n axial points ±2eᵢ, is therefore a kissing arrangement. In ℝ¹² most of the 1579 maximum independent sets come from one recipe built on the complete graph K₆.
Construction 1 for n = 12. The twelve coordinates are two copies of {1, …, 6}, each carrying the same 1-factorisation of K₆: five colours, three edges each. A bridge block joins an edge on the left to an edge of the same colour on the right, so there are 5 · 3 · 3 = 45 of them; each copy also holds a free zone, 48 points of J±(6, 4) inside {1, …, 6}. With classical free zones these are three more blocks, every block carries all 16 sign vectors, and the count is 45 · 16 + 6 · 16 + 24 = 840. Highlighted: the block {3, 4, 2′, 5′}. View full size
Axial points 24
±2eᵢ for the twelve coordinates. A block’s 16 points and its 8 axial points form a 24-cell.
Bridge blocks 45 × 16
An edge {x, y} on the left and an edge {z′, t′} of the same colour on the right.
Free zones 2 × 48
Any maximum independent set of J±(6, 4) in each copy. These choices give 1157 of the 1579 classes.
The 1579 maximum independent sets of J±(12, 4), up to signed permutations
1,157 Construction 1
278 a second set of 45 quadruples
140 interchange
4 classical
1,579 in all
Two codes glued along x₁ = 0
Lemma 3 in a free zone. The codes C and C′, complements of the matchings {12, 34, 56} and {12, 35, 46}, share the block {3, 4, 5, 6} that avoids coordinate 1. Points with x₁ = +1 come from C, points with x₁ = −1 from C′. Each globe is an exact 3-dimensional slice through one block, with its twelve cuboctahedral sites: half of the block’s sites stay empty, yet every orthant still meets exactly 51 points, as Theorem 1 requires.
Why independence is the kissing condition
For two vertices u, v of J±(n, 4), u · v is an integer from −4 to 4. The value 3, an angle of 41.41°, is exactly an edge of the graph; every other value keeps the points at least 60° apart, and an axial point ±2eᵢ meets a vertex only at 0 or ±2. So all 1579 arrangements use only the cosines ½, ¼, 0, −¼, −½, −¾ and −1.
Reading the drawings
Exact. Every count, colour class and slice is computed from the definitions. The 840-point arrangements behind the drawings pass a check of all 352,380 inner products; the largest is ½.
Globes. A globe is a genuine 3-dimensional slice of ℝ¹². Its caps have their true angular radius, 30°, and touch at 60°; dashed circles are empty sites.
Hubs. Each coloured hub stands for the 3 × 3 pairings of its colour; it is not a point of the arrangement.
4-cube. The 16 points of a block differ in signs only. Points one sign apart touch; two signs apart they are orthogonal.
All drawings are original and computed from the definitions in the paper. Research source
About this paper
Classifies maximum independent sets in signed Johnson graphs and reveals a rich family of kissing arrangements.
An enumeration up to signed permutations finds 1,579 non-isometric 840-point arrangements in twelve dimensions. Structural results connect these independent sets with constant-weight codes and Steiner quadruple systems.
Citation
BibTeX
@misc{takhanov2026signedjohnsongraphs,
title = {Classification of independent sets in signed Johnson graphs and applications to kissing arrangements},
author = {Takhanov, Rustem and Yun, Stanislav},
year = {2026},
eprint = {2606.03299},
archivePrefix = {arXiv},
url = {https://arxiv.org/pdf/2606.03299}
}