pith. sign in

arxiv: 2605.17376 · v1 · pith:DVISGBZInew · submitted 2026-05-17 · 🧮 math.CO

Equitable partitions of regular graphs, and perfect sets in normal Cayley graphs

R. A. Bailey , Peter J. Cameron , Sanming Zhou This is my paper

Pith reviewed 2026-05-19 23:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords equitable partitionsregular graphsperfect setsnormal Cayley graphsirreducible charactersgroup representations
0
0 comments X

The pith

Necessary conditions for (a,b)-perfect sets in normal Cayley graphs are expressed using irreducible characters of the group.

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

The paper derives general necessary conditions for regular graphs to admit two equitable partitions. As a corollary, it gives necessary conditions for an (a,b)-perfect set relative to any equitable partition in a regular graph. These results are then used to find necessary conditions for (a,b)-perfect sets in normal Cayley graphs expressed in terms of the irreducible characters of the underlying group. Sympathetic readers would care because this provides algebraic tools to investigate the existence of these special subsets in symmetric graphs.

Core claim

We first derive general necessary conditions for a regular graph to admit two equitable partitions. As a corollary we obtain necessary conditions for the existence of an (a,b)-perfect set in a regular graph in terms of an arbitrary equitable partition. With the help of these results we then obtain necessary conditions for the existence of an (a,b)-perfect set in a normal Cayley graph in terms of the irreducible characters of the underlying group.

What carries the argument

Equitable partitions of the vertex set, which induce a block structure on the adjacency matrix that can be analyzed using the irreducible characters for normal Cayley graphs.

If this is right

  • If a regular graph admits two equitable partitions, then the parameters of the partitions must satisfy certain equations derived from the common refinement or the quotient graph.
  • The existence of an (a,b)-perfect set requires that the vector indicating the set is an eigenvector or satisfies orthogonality conditions with other partitions.
  • For normal Cayley graphs, the character values must vanish or take specific values on the elements corresponding to the perfect set.

Where Pith is reading between the lines

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

  • These character conditions could be checked computationally for small groups to find new examples of graphs with perfect sets.
  • The results might apply to finding designs or codes that correspond to such perfect sets in Cayley graphs.
  • Extending the method to other classes of graphs with known representation theory could yield similar necessary conditions.

Load-bearing premise

The graph is assumed to be regular, allowing the equitable partitions to be analyzed through the eigenvalues and eigenvectors of the adjacency matrix or the group representations.

What would settle it

Construct or identify a regular graph or normal Cayley graph that has an (a,b)-perfect set but violates one of the derived necessary conditions involving the equitable partitions or character values.

read the original abstract

An equitable partition of a graph $\Ga$ is a partition $\{V_1, \ldots, V_m\}$ of its vertex set such that for each pair $i, j$ all vertices in $V_i$ have the same number of neighbours in $V_j$. When $m=2$, $V_1$ is called an $(a, b)$-perfect set in $\Ga$, where $a$ is the number of neighbours in $V_1$ of each vertex in $V_1$, and $b$ is the number of neighbours in $V_1$ of each vertex in $V_2$. In this paper we first derive general necessary conditions for a regular graph to admit two equitable partitions. As a corollary we obtain necessary conditions for the existence of an $(a,b)$-perfect set in a regular graph in terms of an arbitrary equitable partition. With the help of these results we then obtain necessary conditions for the existence of an $(a,b)$-perfect set in a normal Cayley graph in terms of the irreducible characters of the underlying group.

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 / 1 minor

Summary. The paper derives necessary conditions for a regular graph to admit two equitable partitions. As a corollary, it obtains necessary conditions for an (a,b)-perfect set in a regular graph relative to an arbitrary equitable partition. It then specializes these results to normal Cayley graphs, obtaining necessary conditions for the existence of an (a,b)-perfect set in terms of the irreducible characters of the underlying group, using that the adjacency operator lies in the center of the group algebra with eigenvalues lambda_chi = chi(S)/chi(1).

Significance. If the derivations hold, the results provide a representation-theoretic lens on equitable partitions and perfect sets in Cayley graphs by connecting equitable partition conditions to character values. This builds directly on standard facts about equitable partitions and the diagonalization of the adjacency matrix in normal Cayley graphs via irreps, offering potentially useful necessary conditions that could be checked via character tables. The approach is grounded in established tools rather than ad-hoc constructions.

major comments (1)
  1. [specialization to normal Cayley graphs and the corollary for (a,b)-perfect sets] The translation of the two-equitable-partition conditions into statements solely about irreducible characters for normal Cayley graphs (in the specialization following the general corollary) rests on the indicator vectors of the parts of an arbitrary equitable partition projecting in a manner that depends only on characters. However, an arbitrary equitable partition need not be compatible with the conjugacy classes or orbital structure, so the indicator vectors are not necessarily class functions and their projections onto irreps generally involve full matrix coefficients. Please clarify how the conditions reduce to character values alone without an implicit invariance assumption on the partition.
minor comments (1)
  1. [abstract and introduction] The abstract and introduction could more explicitly state whether the equitable partitions in the Cayley-graph case are required to be group-invariant or how the arbitrary partition is handled.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive major comment. We address the point below and have revised the manuscript to incorporate additional clarification on the specialization step.

read point-by-point responses

  1. Referee: [specialization to normal Cayley graphs and the corollary for (a,b)-perfect sets] The translation of the two-equitable-partition conditions into statements solely about irreducible characters for normal Cayley graphs (in the specialization following the general corollary) rests on the indicator vectors of the parts of an arbitrary equitable partition projecting in a manner that depends only on characters. However, an arbitrary equitable partition need not be compatible with the conjugacy classes or orbital structure, so the indicator vectors are not necessarily class functions and their projections onto irreps generally involve full matrix coefficients. Please clarify how the conditions reduce to character values alone without an implicit invariance assumption on the partition.

    Authors: We thank the referee for highlighting this subtlety. The general necessary conditions are derived from the requirement that the subspace spanned by the indicator vectors of the parts is invariant under the adjacency operator A. In the normal Cayley case, A lies in the center of the group algebra and therefore acts as the scalar λ_χ = χ(S)/χ(1) on each entire isotypic component of the regular representation. Consequently, A-invariance of the subspace imposes that the squared norms of the projections of the indicator vectors onto the distinct isotypic components must satisfy explicit relations determined solely by these scalars. These norms are in turn expressible via the ordinary character inner products ⟨1_V, χ⟩ because the projection operator onto an isotypic component is given by the central idempotent (χ(1)/|G|) ∑_g χ(g^{-1}) L_g; the resulting scalar conditions therefore involve only the character values and do not require the individual matrix coefficients of the representations. No additional invariance of the partition (beyond the equitable property itself) is assumed. We have added a clarifying paragraph immediately after the statement of the corollary in the specialization section, together with a short illustrative computation for a small normal Cayley graph, to make this reduction explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations apply standard equitable partition and representation theory facts independently

full rationale

The paper begins with the definition of an equitable partition and derives necessary conditions for two such partitions in a regular graph via direct application to the adjacency matrix. The corollary for an (a,b)-perfect set follows immediately from specializing to m=2. For normal Cayley graphs the adjacency operator is known to lie in the center of the group algebra and is therefore diagonalized by irreducible characters with eigenvalues chi(S)/chi(1); this is an external algebraic fact, not derived from or fitted to the paper's own results. No equation reduces a claimed prediction to a fitted parameter by construction, no self-citation is load-bearing for the central claim, and the derivation remains self-contained against external benchmarks in algebraic graph theory and group representation theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard facts from representation theory of finite groups and the definition of normal Cayley graphs; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Irreducible characters of the underlying group determine the eigenvalues or orbital structure relevant to equitable partitions in normal Cayley graphs.
    Invoked when translating partition conditions into character values for the final result.
  • domain assumption The graph is vertex-transitive and regular, allowing equitable partitions to be analyzed via group actions.
    Stated as the setting for both the general and Cayley-graph results.

pith-pipeline@v0.9.0 · 5724 in / 1345 out tokens · 35905 ms · 2026-05-19T23:02:47.816668+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    R. A. Bailey, P. J. Cameron, A. L. Gavrilyuk and S. V. Goryainov, Equitable partitions of Latin- square graphs,J. Combin. Des.27 (2019), no. 3, 142–160

    work page 2019

  2. [2]

    R. A. Bailey, P. J. Cameron, D. Ferreira, S. S. Ferreira and C. Nunes, Designs for half-diallel experiments with commutative orthogonal block structure,J. Statist. Plann. Inference231 (2024), 106139

    work page 2024

  3. [3]

    E. A. Bespalov, D. S. Krotov, A. A. Matiushev and K. V. Vorob’ev, Perfect 2-colorings of Hamming graphs,J Combin Des.29 (2021), no. 6, 367–396

    work page 2021

  4. [4]

    N. L. Biggs, Perfect codes in graphs,J. Combin. Theory Ser. B15 (1973) 289–296

    work page 1973

  5. [5]

    D. M. Cardoso, An overview of (κ, τ)-regular sets and their applications,Discrete Appl. Math.269 (2019) 2–10

    work page 2019

  6. [6]

    J. Chen, Y. Wang and B. Xia, Characterization of subgroup perfect codes in Cayley graphs,Discrete Math.343 (2020), no. 5, 111813

    work page 2020

  7. [7]

    I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs,Discrete Appl. Math.129 (2003) 319–328. 21

    work page 2003

  8. [8]

    Diaconis and M

    P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions,Z. Wahrscheinlichkeitstheor. Verw. Geb.57(2) (1981) 159–179

    work page 1981

  9. [9]

    Etienne, Perfect codes and regular partitions in graphs and groups,European J

    G. Etienne, Perfect codes and regular partitions in graphs and groups,European J. Combin.8 (1987), no. 2, 139–144

    work page 1987

  10. [10]

    Feit,Characters of Finite Groups, Benjamin, 1967

    W. Feit,Characters of Finite Groups, Benjamin, 1967

    work page 1967

  11. [11]

    R. Feng, H. Huang and S. Zhou, Perfect codes in circulant graphs,Discret. Math.340 (2017) 1522– 1527

    work page 2017

  12. [12]

    D. G. Fon-Der-Flaas, Perfect 2-colorings of a hypercube,Siberian Math. J.48 (2007), no. 4, 740–745. (Translated fromSibirsk. Mat. Zh., 48 (2007), no. 4, 923–930.)

    work page 2007

  13. [13]

    A. L. Gavrilyuk and S. V. Goryainov, On perfect 2-colorings of Johnson graphsJ(v,3),J. Combin. Des.21 (2013), no. 6, 232–252

    work page 2013

  14. [14]

    Godsil,Algebraic Combinatorics, Chapman and Hall, New York, 1993

    C. Godsil,Algebraic Combinatorics, Chapman and Hall, New York, 1993

    work page 1993

  15. [15]

    Godsil and G

    C. Godsil and G. Royle,Algebraic Graph Theory, Springer-Verlag, New York, 2001

    work page 2001

  16. [16]

    T. W. Haynes, S. T. Hedetniemi and P. Slater,Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998

    work page 1998

  17. [17]

    Heden, A survey of perfect codes,Adv

    O. Heden, A survey of perfect codes,Adv. Math. Commun.2 (2008) 223–247

    work page 2008

  18. [18]

    Huang, B

    H. Huang, B. Xia and S. Zhou, Perfect codes in Cayley graphs,SIAM J. Discrete Math.32 (2018) 548–559

    work page 2018

  19. [19]

    D. S. Krotov, On weight distributions of perfect colorings and completely regular codes,Des. Codes Cryptogr.61 (2011), no. 3, 315–329

    work page 2011

  20. [20]

    D. S. Krotov and V. N. Potapov, Completely regular codes and equitable partitions, in:Completely Regular Codes in Distance Regular Graphs, 1–84, Monogr. Res. Notes Math., CRC Press, Boca Raton, FL, 2025

    work page 2025

  21. [21]

    Lee, Independent perfect domination sets in Cayley graphs,J

    J. Lee, Independent perfect domination sets in Cayley graphs,J. Graph Theory37 (2001) 213–219

    work page 2001

  22. [22]

    X. Liu, S. Zhou, Eigenvalues of Cayley graphs,Electron. J. Combin.29 (2) (2022) Paper No. 2.9, 164 pp

    work page 2022

  23. [23]

    X. Ma, G. L. Walls, K. Wang and S. Zhou, Subgroup perfect codes in Cayley graphs,SIAM J. Discrete Math.34 (2020), no.3, 1909–1921

    work page 2020

  24. [24]

    Meyerowitz, Cycle-balance conditions for distance-regular graphs,Discrete Math.264 (2003), no

    A. Meyerowitz, Cycle-balance conditions for distance-regular graphs,Discrete Math.264 (2003), no. 1-3, 149–165

    work page 2003

  25. [25]

    Mogilnykh and A

    I. Mogilnykh and A. Valyuzhenich, Equitable 2-partitions of the Hamming graphs with the second eigenvalue,Discrete Math.343 (2020), no. 11, 112039

    work page 2020

  26. [26]

    Neumaier, Completely regular codes,Discrete Math.106/107 (1992) 353–360

    A. Neumaier, Completely regular codes,Discrete Math.106/107 (1992) 353–360

    work page 1992

  27. [27]

    Rothaus and J

    O. Rothaus and J. G. Thompson, A combinatorial problem in the symmetric group,Pacific J. Math. 18 (1966) 175–178

    work page 1966

  28. [28]

    Szab´ o and A

    S. Szab´ o and A. Sands,Factoring Groups into Subsets, CRC Press, Boca Raton, FL, 2009

    work page 2009

  29. [29]

    Y. Wang, B. Xia and S. Zhou, Regular sets in Cayley graphs,J. Algebraic Combin.57 (2023), no. 2, 547–558

    work page 2023

  30. [30]

    Wang, S-J

    X. Wang, S-J. Xu and S. Zhou, On regular sets in Cayley graphs,J. Algebraic Combin.59 (2024), no. 3, 735–759

    work page 2024

  31. [31]

    J. H. van Lint, A survey of perfect codes,Rocky Mountain J. Math.5 (1975) 199–224

    work page 1975

  32. [32]

    Zhang and S

    J. Zhang and S. Zhou, On subgroup perfect codes in Cayley graphs,European J. Combin.91 (2021) 103228. (Corrigenda:European J. Combin.101 (2022) 103461)

    work page 2021

  33. [33]

    Zhou, Total perfect codes in Cayley graphs,Des

    S. Zhou, Total perfect codes in Cayley graphs,Des. Codes Cryptogr.81 (2016), no. 3, 489–504

    work page 2016

  34. [34]

    Zhou, Cyclotomic graphs and perfect codes,J

    S. Zhou, Cyclotomic graphs and perfect codes,J. Pure Appl. Algebra223 (2019) 931–947

    work page 2019

  35. [35]

    P. H. Zieschang, Cayley graphs of finite groups,J. Algebra118(2) (1988) 447–454. 22

    work page 1988