pith. sign in

arxiv: 2606.03299 · v1 · pith:JWG7I3OWnew · submitted 2026-06-02 · 💻 cs.IT · math.CO· math.IT

Classification of independent sets in signed Johnson graphs and applications to kissing arrangements

Rustem Takhanov , Stanislav Yun This is my paper

Pith reviewed 2026-06-28 08:29 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords signed Johnson graphsindependent setskissing arrangementsconstant weight codesSteiner quadruple systemsmaximum independent setssphere packings
0
0 comments X

The pith

There are 1579 non-isomorphic maximum independent sets in the signed Johnson graph J±(12,4), each giving a distinct non-isometric kissing arrangement of 840 spheres in 12-dimensional space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies all maximum independent sets in signed Johnson graphs J±(n,4) for dimensions up to 12. These sets correspond to selections of vectors with four ±1 entries that have dot products at most 2, which directly translate to configurations of equal spheres touching a central one without overlapping. For n=12 the classification yields 1579 distinct types, most constructed in three specific ways and a few lifted from constant-weight codes. In certain dimensions the sets must come from Steiner quadruple systems, and the work also describes codes that allow non-standard constructions.

Core claim

We identify 1579 non-isomorphic maximum independent sets in J±(12,4), all corresponding to non-isometric kissing arrangements of size 840 in R^12. Structurally, 1575 of these independent sets arise from three different constructions, the rest are liftings of one of four (12,4,4)-codes. For n ≡ 2 or 4 mod 6, every maximum independent set arises from a Steiner quadruple system. We also obtain a characterization of the so-called nontrivially self-compatible codes, namely optimal (n,4,4)-codes from which non-classical maximum independent sets can be constructed.

What carries the argument

The signed Johnson graph J±(n,4) whose vertices are vectors with exactly four ±1 entries, with two vertices adjacent when their dot product equals 3; maximum independent sets in this graph define kissing arrangements.

If this is right

  • For n ≡ 2 or 4 mod 6 every maximum independent set in J±(n,4) arises from a Steiner quadruple system.
  • Non-classical maximum independent sets can be obtained by lifting nontrivially self-compatible optimal (n,4,4)-codes.
  • All 1579 independent sets in dimension 12 produce kissing arrangements of exactly 840 spheres that are pairwise non-isometric.
  • Complete lists of such sets up to signed-permutation symmetry exist for every n ≤ 12 except n = 11.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The observed variety implies that many more locally optimal sphere-kissing configurations exist in 12 dimensions than the handful previously catalogued.
  • The three explicit constructions may generalize to produce large families of independent sets in higher dimensions where full enumeration is impossible.
  • The characterization of nontrivially self-compatible codes supplies a concrete search criterion for new constant-weight codes with unusual lifting properties.
  • Kissing arrangements arising from these sets could be tested for global optimality or for use as seeds in higher-dimensional packing problems.

Load-bearing premise

The custom algorithm correctly enumerates every maximum independent set without omissions or overcounting once symmetry under signed permutations is quotiented out.

What would settle it

An explicit list or construction of one additional maximum independent set in J±(12,4) not isomorphic to any of the 1579 reported ones.

Figures

Figures reproduced from arXiv: 2606.03299 by Rustem Takhanov, Stanislav Yun.

Figure 1
Figure 1. Figure 1: 1-factorization of K6. Let us consider all sets of the form {x, y, z′ , t′} where the edges {x, y}, {z, t} are of the same colour in the graph with coloured edges given in [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Isomorphic quadruples. The following lemma gives a construction of an independent set in J±(12, 4). Lemma 5. Let A = {a, b, c, d, e, f}, B = {p, q, r, s, t, u} be two 6-element disjoint sets. We assume that quadruples {a, b, c, d} and {p, q, r, s} define sets B and D. Let M = {{a, b}, {c, d}, {e, f}} be a matching on A, and let N = {{p, q}, {r, s}, {t, u}} be a matching on B. Suppose that M and N are exten… view at source ↗
Figure 3
Figure 3. Figure 3: The transformation of Fano plane under π = (2, 3). There are only two non-isomorphic independent sets for n = 7. The first one is clearly classical. For the second one, we compared the corresponding kissing arrangement with the arrangement C7-126b, provided as supplementary material to [22], and verified that the two arrangements are isomorphic. The latter arrangement was originally discovered by [7]. Note… view at source ↗
read the original abstract

Johnson graph are a family of graphs that play an important role in the theory of constant-weight codes, extremal combinatorics, and combinatorial geometry. We study signed analogues of classical Johnson graphs, denoted by $J_\pm(n,k)$, whose vertices are vectors of the form $\pm e_{i_1}\pm\cdots\pm e_{i_k}$, where two vertices are adjacent whenever their dot product equals $k-1$. We are particularly interested in maximum independent sets in the case $k=4$. An example of such an independent set in $J_\pm(n,4)$, which we call \emph{classical}, is obtained by lifting an arbitrary optimal $(n,4,4)$-code. Such independent sets naturally define kissing arrangements in ${\mathbb R}^n$. We develop an algorithm that is practical for computing all maximum independent sets in $J_\pm(n,4)$ up to signed permutations for $n\le 12$, $n\ne 11$. In addition to obtaining complete lists, we provide structural characterizations of all types of maximum independent sets in these dimensions, excluding $n=5$ and $n=11$. Our most striking results concern the case $n=12$. We identify $1579$ non-isomorphic maximum independent sets in $J_\pm(12,4)$, all corresponding to non-isometric kissing arrangements of size $840$ in ${\mathbb R}^{12}$. Structurally, $1575$ of these independent sets arise from three different constructions, the rest are liftings of one of four $(12,4,4)$-codes. To our knowledge, this is the first dimension in which such a large diversity of potentially optimal kissing arrangements has been observed. Beyond this finite range, we prove that for $n\equiv 2$ or $4 \pmod 6$, every maximum independent set arises from a Steiner quadruple system. We also obtain a characterization of the so-called \emph{nontrivially self-compatible} codes, namely optimal $(n,4,4)$-codes from which non-classical maximum independent sets can be constructed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper introduces signed Johnson graphs J±(n,4) whose vertices are signed k-subset vectors with adjacency when the dot product is k-1. It develops a custom algorithm to enumerate all maximum independent sets up to signed-permutation symmetry for n≤12 (n≠11), supplies complete lists together with structural characterizations, and proves that for n≡2 or 4 (mod 6) every maximum independent set arises from a Steiner quadruple system. The headline computational result is the identification of 1579 non-isomorphic maximum independent sets in J±(12,4), all yielding non-isometric kissing arrangements of size 840 in R^12; of these, 1575 arise from three explicit constructions and the remaining four are liftings of (12,4,4)-codes. A characterization of nontrivially self-compatible optimal (n,4,4)-codes is also given.

Significance. If the enumeration is correct, the work establishes the first dimension in which a large number of combinatorially distinct, potentially optimal kissing arrangements appear, and supplies explicit constructions and a complete classification for n=12. The analytic proofs for the Steiner-quadruple-system case and the self-compatible-code characterization are parameter-free and therefore constitute a permanent contribution independent of the computational component.

major comments (1)
  1. [Enumeration algorithm and results for n=12] The section describing the enumeration algorithm and its output for n=12: the claim that there are exactly 1579 non-isomorphic maximum independent sets (1575 from three constructions, 4 from code liftings) is load-bearing for the central assertion of “first dimension with such diversity,” yet the manuscript supplies neither released source code, machine-checked certificates, exhaustive cross-checks on smaller n against known constant-weight-code tables, nor independent verification of the symmetry-quotienting and maximality steps. An undetected orbit or maximality error would directly falsify the reported count and the structural breakdown.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of the paper's significance and for the constructive comment on verification of the n=12 enumeration. We respond point by point below.

read point-by-point responses

  1. Referee: The section describing the enumeration algorithm and its output for n=12: the claim that there are exactly 1579 non-isomorphic maximum independent sets (1575 from three constructions, 4 from code liftings) is load-bearing for the central assertion of “first dimension with such diversity,” yet the manuscript supplies neither released source code, machine-checked certificates, exhaustive cross-checks on smaller n against known constant-weight-code tables, nor independent verification of the symmetry-quotienting and maximality steps. An undetected orbit or maximality error would directly falsify the reported count and the structural breakdown.

    Authors: We agree that computational enumerations of this scale require explicit verification to support the headline claim. The algorithm is fully described in the manuscript (including the symmetry-quotienting procedure via signed-permutation group actions and the maximality test via exhaustive neighbor search), and we performed internal consistency checks: the counts for n=6,8,10 recover the known numbers of optimal constant-weight codes and classical independent sets, while the structural partition into three constructions plus four code-liftings is corroborated by the independent analytic characterization of nontrivially self-compatible codes. Nevertheless, the manuscript does not currently include an external code repository or tabulated cross-checks against external tables. In the revised version we will (i) add a dedicated subsection tabulating the smaller-n verifications against the Brouwer–Etzion–Östergård tables and the known Johnson-graph independent-set enumerations, (ii) state the precise orbit-stabilizer and maximality invariants used, and (iii) make the source code (with deterministic random-seed reproduction) available via a public repository upon acceptance. Machine-checked certificates (e.g., Coq or Isabelle formalization of the entire search) lie beyond the scope of the present work but could be pursued separately; the combination of published algorithm, smaller-n cross-checks, and code release will allow independent reproduction and falsification of the 1579 count. revision: yes

Circularity Check

0 steps flagged

No circularity: enumeration outputs and independent combinatorial proofs

full rationale

The paper's central results consist of (a) complete lists of maximum independent sets in J±(n,4) for n≤12 (n≠11) obtained by running a custom enumeration algorithm up to signed-permutation symmetry, and (b) separate combinatorial proofs that, for n≡2 or 4 (mod 6), every such set arises from a Steiner quadruple system, plus a characterization of nontrivially self-compatible (n,4,4)-codes. Neither the reported count 1579 nor the structural partition (1575 from three constructions, 4 from codes) is obtained by fitting parameters to the same data or by any equation that equates the output to an input by definition. No self-citation is invoked as a load-bearing uniqueness theorem, and the algorithmic results are presented as direct computational outputs rather than predictions derived from prior fitted quantities. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of Johnson graphs and their signed analogues; no numerical parameters are fitted and no new mathematical objects beyond the signed graph itself are postulated.

axioms (2)
  • domain assumption Two signed k-vectors are adjacent in J±(n,k) precisely when their dot product equals k-1.
    This is the defining relation of the signed Johnson graph used throughout the classification.
  • domain assumption Maximum independent sets in J±(n,4) correspond to kissing arrangements of size equal to the independence number in R^n.
    The geometric interpretation is invoked to motivate the study and to translate combinatorial results into statements about sphere packings.

pith-pipeline@v0.9.1-grok · 5927 in / 1675 out tokens · 30593 ms · 2026-06-28T08:29:54.293183+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Structure of kissing arrangements in ${\mathbb R}^{12}$ and a place for the $841$st sphere

    cs.IT 2026-06 unverdicted novelty 6.0

    Kissing arrangements of 840 spheres in R^12 admit positive-dimensional families of non-isometric realizations via flexible 48-systems in each 60-point block with fixed bridges, enabling a numerical 841-sphere configur...

Reference graph

Works this paper leans on

25 extracted references · 4 canonical work pages · cited by 1 Pith paper

  1. [1]

    Forbidding just one intersection,

    P. Frankl and Z. F ¨uredi, “Forbidding just one intersection,”Journal of Combinatorial Theory, Series A, vol. 39, no. 2, pp. 160–176, 1985. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0097316585900354

    arXiv 1985

  2. [2]

    The complete intersection theorem for systems of finite sets,

    R. Ahlswede and L. H. Khachatrian, “The complete intersection theorem for systems of finite sets,”European Journal of Combinatorics, vol. 18, no. 2, pp. 125–136, 1997. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0195669885700923

    1997

  3. [3]

    Intersection theorems with geometric consequences,

    P. Frankl and R. M. Wilson, “Intersection theorems with geometric consequences,”Combinatorica, vol. 1, no. 4, pp. 357–368, Dec 1981. [Online]. Available: https://doi.org/10.1007/BF02579457

    work page doi:10.1007/bf02579457 1981

  4. [4]

    MacWilliams and N

    F. MacWilliams and N. Sloane,The Theory of Error-Correcting Codes, 2nd ed. North-holland Publishing Company, 1978

    1978

  5. [5]

    Classification of binary constant weight codes,

    P. R. J. ¨Osterg˚ard, “Classification of binary constant weight codes,”IEEE Trans. Inf. Theor., vol. 56, no. 8, p. 3779–3785, Aug. 2010. [Online]. Available: https://doi.org/10.1109/TIT.2010.2050922

    work page doi:10.1109/tit.2010.2050922 2010

  6. [6]

    Sphere packings and error-correcting codes,

    J. Leech and N. J. A. Sloane, “Sphere packings and error-correcting codes,”Canadian Journal of Mathematics, vol. 23, no. 4, p. 718–745, 1971

    1971

  7. [7]

    What are all the best sphere packings in low dimensions?

    J. H. Conway and N. J. A. Sloane, “What are all the best sphere packings in low dimensions?”Discrete & Computational Geometry, vol. 13, no. 3, pp. 383–403, Jun 1995. [Online]. Available: https://doi.org/10.1007/BF02574051

    work page doi:10.1007/bf02574051 1995

  8. [8]

    Variations on five-dimensional sphere packings,

    H. Cohn and I. Rajagopal, “Variations on five-dimensional sphere packings,” 2026. [Online]. Available: https://arxiv.org/abs/2412.00937

    arXiv 2026

  9. [9]

    Highly symmetric lines,

    M. Ganzhinov, “Highly symmetric lines,”Linear Algebra and its Applications, vol. 722, pp. 12–37, 2025. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S0024379525001946

    2025

  10. [10]

    Alphaevolve: A coding agent for scientific and algorithmic discovery,

    A. Novikov, N. V ˜u, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog, “Alphaevolve: A coding agent for scientific and algorithmic discovery,” 2025. [Online]. Available: https://arxiv.org/abs/2506.13131

    Pith/arXiv arXiv 2025

  11. [11]

    Some extreme forms defined in terms of abelian groups,

    E. S. Barnes and G. E. Wall, “Some extreme forms defined in terms of abelian groups,”Journal of the Australian Mathematical Society, vol. 1, no. 1, p. 47–63, 1959

    1959

  12. [12]

    Extremal problems for hypergraphs,

    G. O. H. Katona, “Extremal problems for hypergraphs,” inCombinatorics, M. Hall and J. H. van Lint, Eds. Dordrecht: Springer Netherlands, 1975, pp. 215–244

    1975

  13. [13]

    Binary codes with minimum distance four,

    M. R. Best, “Binary codes with minimum distance four,” Mathematical Centre, Amsterdam, The Netherlands, Tech. Rep. ZW 112/78, 1978

    1978

  14. [14]

    A(11,4,4) = 35 or some new optimal constant weight codes,

    M. Best, “A(11,4,4) = 35 or some new optimal constant weight codes,” Jan. 1977

    1977

  15. [15]

    ApS,The MOSEK optimization toolbox for MATLAB manual

    M. ApS,The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019. [Online]. Available: http://docs.mosek.com/9.0/toolbox/index.html

    2019

  16. [16]

    An automatic method of solving discrete programming problems,

    A. H. Land and A. G. Doig, “An automatic method of solving discrete programming problems,”Econometrica, vol. 28, no. 3, pp. 497–520, 1960. [Online]. Available: http://www.jstor.org/stable/1910129

    arXiv 1960

  17. [17]

    A fast algorithm for the maximum clique problem,

    P. R. ¨Osterg˚ard, “A fast algorithm for the maximum clique problem,”Discrete Applied Mathematics, vol. 120, no. 1, pp. 197– 207, 2002, special Issue devoted to the 6th Twente Workshop on Graphs and Combinatorial Optimization. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S0166218X01002906

    2002

  18. [18]

    Maximal and minimal coverings of (k — 1)-tuples by k-tuples,

    J. Kalbfleisch and R. Stanton, “Maximal and minimal coverings of (k — 1)-tuples by k-tuples,”Pacific Journal of Mathematics, vol. 26, no. 1, p. 131 – 140, 1968

    1968

  19. [19]

    The igraph software package for complex network research,

    G. Cs ´ardi and T. Nepusz, “The igraph software package for complex network research,”InterJournal, vol. Complex Systems, p. 1695, 2006. [Online]. Available: https://igraph.org

    2006

  20. [20]

    Exploring network structure, dynamics, and function using networkx,

    A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” inProceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15

    2008

  21. [21]

    Practical graph isomorphism, ii,

    B. D. McKay and A. Piperno, “Practical graph isomorphism, ii,”Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0747717113001193

    2014

  22. [22]

    Rigidity of spherical codes,

    H. Cohn, Y . Jiao, A. Kumar, and S. Torquato, “Rigidity of spherical codes,”Geometry & Topology, vol. 15, pp. 2235–2273, 2011

    2011

  23. [23]

    Uniqueness of certain spherical codes,

    E. Bannai and N. J. A. Sloane, “Uniqueness of certain spherical codes,”Canadian Journal of Mathematics, vol. 33, no. 2, p. 437–449, 1981

    1981

  24. [24]

    Upper bounds for constant weight error correcting codes,

    S. Johnson, “Upper bounds for constant weight error correcting codes,”Discrete Mathematics, vol. 3, no. 1, pp. 109–124, 1972. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0012365X72900271

    arXiv 1972

  25. [25]

    The completion determination of optimal(3,4)-packings,

    J. Bao and L. Ji, “The completion determination of optimal(3,4)-packings,”Des. Codes Cryptography, vol. 77, no. 1, p. 217–229, Oct. 2015. [Online]. Available: https://doi.org/10.1007/s10623-014-0001-2

    work page doi:10.1007/s10623-014-0001-2 2015