Pith. sign in

REVIEW 4 major objections 4 minor 31 references

Existence of non-Cayley Haar graphs

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read This paper proves that every finite non-abelian group except five small exceptions has a Haar graph that is not a Cayley graph.

desk verdict Complete classification resolving Estelyi and Pisanski's 2016 problem; the theorem is likely right, but the referee should demand the Magma code behind the small-case checks. read the letter →

arxiv 1908.04551 v1 pith:VPUWGJ3N submitted 2019-08-13 math.CO

classification math.CO MSC 05E1820B25
keywords HaargraphCayleybi-Cayleyvertex-transitivenon-abeliangroupgraphicalregularrepresentation2-groupclassification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper settles a classification question left open in 2016: which finite non-abelian groups have the property that every Haar graph is a Cayley graph? A Haar graph of a group $H$ is a bipartite graph made from two copies of $H$, with edges from $h_0$ to $(sh)_1$ determined by a subset $S \subseteq H$. The answer is exactly five groups: the dihedral groups $D_6$, $D_8$, $D_{10}$, the quaternion group $Q_8$, and the direct product $Q_8 \times \mathbb{Z}_2$. Every other finite non-abelian group admits at least one Haar graph that is not a Cayley graph. Since abelian groups are already known to have the property, the theorem gives the complete boundary between the two classes of graphs.

What carries the argument

The load-bearing object is the class $BC$ of groups all of whose Haar graphs are Cayley graphs, together with the normalizer description of automorphisms of a connected Haar graph: $N_{\mathrm{Aut}(\Gamma)}(R(H))$ is either $R(H) \rtimes F$ or $R(H)\langle F, \delta_{\alpha,x,y}\rangle$, depending on whether a certain set $I$ is empty. This description lets the authors force $R(H)$ to be the full automorphism group. The other engine is a structural reduction from an earlier paper: groups in $BC$ are solvable, have abelian Sylow $p$-subgroups for odd $p$, and contain a subgroup isomorphic to $D_6$, $D_8$, $D_{10}$ or $Q_8$. The classification then splits into non-abelian $2$-groups and non-abelian $\{2,p\}$-groups; in each case explicit connection sets $S$ are chosen so that counting $4$-cycles through the vertex $1_0$ forces the stabilizer of $1_0$ to be trivial and the graph to have two orbits.

What would settle it

Take any non-abelian group not isomorphic to $D_6$, $D_8$, $D_{10}$, $Q_8$ or $Q_8 \times \mathbb{Z}_2$—for example the dihedral group of order 16—and enumerate all Haar graphs $H(H,S)$ with $1 \in S$ up to isomorphism, checking for each whether it is a Cayley graph. The theorem predicts at least one non-Cayley Haar graph; exhibiting one such group with all Haar graphs Cayley would disprove the classification.

Watch

Extended reading notes

Core claim

The central claim is the classification theorem: if $H$ is a finite non-abelian group and every Haar graph $H(H,S)$ is a Cayley graph, then $H$ is isomorphic to $D_6$, $D_8$, $D_{10}$, $Q_8$ or $Q_8 \times \mathbb{Z}_2$; conversely, each of these five groups does have the property. The proof proves the converse partly by a subgroup argument: a disconnected Haar graph over $Q_8 \times \mathbb{Z}_2$ splits into Cayley components, and connected ones are checked computationally; the dihedral cases come from the earlier dihedral classification. The necessity is shown by assuming a group in the class $BC$ and using a structural reduction to narrow it to non-abelian $2$-groups and non-abelian $\{2,p\}$-groups, then constructing, for every remaining candidate, a specific Haar graph whose automorphism group is exactly the right-translation group $R(H)$, so the graph has two orbits and cannot be a Cayley graph.

Load-bearing premise

The case analysis rests on an earlier structural theorem saying that any group whose Haar graphs are all Cayley graphs is solvable, has abelian Sylow $p$-subgroups for every odd prime $p$, and contains a subgroup isomorphic to $D_6$, $D_8$, $D_{10}$ or $Q_8$; if that theorem failed, the reductions could miss groups.

Editorial extensions

If this is right

  • For every finite non-abelian group outside the five listed, there is a concrete Haar graph that is not a Cayley graph, so non-Cayleyness is the rule rather than the exception among Haar graphs of non-abelian groups.
  • Combined with the known fact that every Haar graph of an abelian group is a Cayley graph, the theorem gives a complete dichotomy: a finite group has only Cayley Haar graphs exactly when it is abelian or is one of $D_6$, $D_8$, $D_{10}$, $Q_8$, $Q_8 \times \mathbb{Z}_2$.
  • The five exceptional groups have no Haar graph whose full automorphism group is isomorphic to the group itself, and the paper notes they are the only known non-abelian groups with no such Haar graph.
  • The non-Cayley Haar graphs constructed here are not vertex-transitive, so the same construction cannot produce vertex-transitive non-Cayley Haar graphs; the vertex-transitive version of the problem remains open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The connection sets used in the paper's constructions have at most eight elements, which suggests the obstruction to being Cayley is already present in small, local configurations rather than requiring large or elaborate connection sets.
  • A natural test of the classification is to enumerate all Haar graphs of every non-abelian group of order 16 or 32; the theorem predicts each has a non-Cayley Haar graph, so any group outside the five with all Haar graphs Cayley would pinpoint a gap in the structural reduction.
  • Because the proof makes the stabilizer $A_{1_0}$ trivial, a vertex-transitive non-Cayley Haar graph would have to come from a different mechanism, one where the automorphism group is larger than $R(H)$ but still lacks a regular subgroup.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper solves Problem 1.1 of Estélyi and Pisanski by classifying the finite non-abelian groups H with the property that every Haar graph of H is a Cayley graph. The main theorem states that the only such groups are D6, D8, D10, Q8 and Q8 × Z2. The proof has two parts: Section 3 constructs non-vertex-transitive Haar graphs that are therefore non-Cayley, using two infinite families (Lemmas 3.1 and 3.2) and a table of nine small examples (Lemma 3.3); Section 4 gives structural reductions within the class BC, first for non-abelian 2-groups (Lemma 4.1) and then for non-abelian {2,p}-groups (Lemma 4.2), before the final argument in Theorem 1.4 handles groups with several odd prime divisors. The analytic portions are detailed stabilizer computations, while several finite checks are delegated to Magma without supplying code or output.

Significance. If the computational assertions are correct, Theorem 1.4 resolves a natural open problem and extends the previously known cases for dihedral groups and inner-abelian groups. The paper also gives the first complete list of non-abelian groups with no GHRR, which is relevant to Problem 1.6. The hand-written parts are substantial and careful: Lemma 3.1 is proved by an explicit stabilizer argument, Lemma 3.2 contains a long analytic proof for p ≥ 7, and the reduction scheme in Section 4 is structurally sound, making good use of the published BC framework from [10]. The main weakness is reproducibility: Lemma 3.2 for p = 3, 5, the nine rows of Lemma 3.3, and the connected case of Lemma 4.1 for Q8 × Z2 are asserted only as Magma computations, with no code, transcript, or detailed output. These checks are load-bearing for the central classification, so the manuscript as submitted is not fully independently verifiable.

major comments (4)
  1. [Section 3, Lemma 3.2] For p = 3 and 5 the proof is contained entirely in the sentence 'The lemma holds for p = 3 and 5 by Magma [5]'. These two primes are not covered by the analytic argument that follows, which assumes p ≥ 7, and no code, input data, or output is supplied. Since Lemma 3.2 is used to rule out Q8 × Zp for all odd p in Lemma 4.2 Case 1 and hence in Theorem 1.4, please replace this assertion by a hand proof or supply the Magma program and a transcript of its output for p = 3 and 5.
  2. [Section 3, Lemma 3.3] Lemma 3.3 asserts, for nine explicitly presented groups, that the corresponding Haar graph is not vertex-transitive and that the group is not in BC, with the only justification being that this 'can be checked easily by the computer software Magma'. These rows are load-bearing: rows 1-4 eliminate four of the six order-16 candidates in Lemma 4.1 Case 2, row 5 eliminates Q8 × Z2 × Z2 in Lemma 4.1 Case 3, and rows 6, 8 and 9 eliminate Q8 ⋊ Z3, F20 and Zp^2 ⋊ Z2 in Lemma 4.2. As written, the proof of Theorem 1.4 is not independently verifiable without recomputing all nine rows; please include code and full output, or give explicit stabilizer arguments, for each row.
  3. [Section 4, Lemma 4.1] In the proof of the sufficiency for Q8 × Z2, the connected case is dispatched by 'a computation by Magma [5] shows that all connected Haar graphs of Q8 × Z2 are Cayley graphs'. This is a finite but nontrivial enumeration, since S ranges over subsets of Q8 × Z2 containing the identity and generating the whole group, and a single missed non-Cayley example would remove Q8 × Z2 from the classification in Theorem 1.4. Please provide the Magma code, the exact list of connected S values, and the output confirming that each resulting Haar graph is Cayley, or provide a conceptual proof.
  4. [Section 2, Proposition 2.3] Proposition 2.3 is the structural backbone of the proof of Theorem 1.4: it supplies solvability, the condition on odd Sylow subgroups, and the existence of a D6/D8/D10/Q8 subgroup. Since it is quoted from [10], an earlier paper by the same authors, I ask that the authors indicate precisely which results in [10] yield each of (i)-(iii) and state why those results are independent of the classification completed in the present paper. I do not see a circularity in the statements themselves, but the manuscript should make the logical dependency explicit for the reader.
minor comments (4)
  1. [Section 3, Lemma 3.2] In the paragraph following Eq. (6), 'anb by Eq. (1)' should read 'and by Eq. (1)'.
  2. [Section 3, Lemma 3.3, row 6] The presentation 'ac = b^{±1}, bc = a^{±1}b' is ambiguous; please specify whether both signs are allowed simultaneously or whether a single choice is meant.
  3. [Section 4, Lemma 4.2, Case 2, Claim 1] The equality 'P2 = C_H(P2) = N_H(P2)' when P2 is abelian, of prime index, and not normal is correct, but it deserves a one-line justification because it is the step that triggers Burnside's p-nilpotency criterion.
  4. [Section 1, paragraph 4] The sentence 'It seems difficulty to construct vertex-transitive non-Cayley Haar graphs' should read 'It seems difficult to construct ...'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the classification proof is independent of its inputs; self-cited structural theorems and finite Magma checks do not reduce the target result to itself.

full rationale

This paper is not circular. Theorem 1.4 is a classification theorem: every non-abelian group in the class BC must be one of D6, D8, D10, Q8, or Q8×Z2, and each listed group is shown to lie in BC by independent verification. The proof does not assume the theorem. It imports Proposition 2.3 from the authors' earlier paper [10], which is a self-citation, but Proposition 2.3 is a structural statement about BC—solvability, abelian odd-order Sylow subgroups, and existence of a small non-abelian subgroup—not the final classification list. It is parameter-free, published separately, and does not contain the conclusion of Theorem 1.4. The sufficiency direction is constructive: Lemmas 3.1–3.3 exhibit explicit Haar graphs and prove, or verify by asserted Magma computations, that they are not vertex-transitive and hence not Cayley; Lemmas 4.1 and 4.2 and the final proof combine these examples with subgroup closure and prior dihedral and inner-abelian classifications. The Magma assertions in Lemmas 3.2, 3.3, and 4.1 are finite verifications for specific finite groups, not fitted parameters or renamed inputs; the absence of shipped code is a reproducibility concern, not circular reasoning. No equation or definition in the paper reduces the target claim to itself, and no prediction is forced by construction from fitted data.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on a small number of structural theorems from earlier papers, partly by the same authors, and on unshipped Magma computations. There are no free parameters and no invented entities; the new mathematical content is the explicit construction of two infinite families of non-Cayley Haar graphs and the case analysis reducing all other groups to those families or to known exceptions.

assumptions (6)
  • domain assumption Proposition 2.2: BC is closed under taking subgroups.
    Proved in [10, Lemma 3.1]; used throughout to pass from H to its subgroups, for example in Lemmas 4.1 and 4.2 and Theorem 1.4. The reader must accept this external result.
  • domain assumption Proposition 2.3: If H is in BC then H is solvable, each Sylow p-subgroup for p >= 3 is abelian, and H has a subgroup D6, D8, D10, or Q8.
    Structural backbone of the proof, cited from [10, Theorem 1.3 and Corollary 4.6]. It drives the reductions that cut the classification down to 2-groups and {2,p}-groups.
  • domain assumption Proposition 2.1: the normalizer of R(H) in Aut(H(H,S)) is R(H) ⋊ F, possibly extended by an involution δ, with transitivity consequences.
    Taken from Zhou and Feng [28, Theorem 1.1 and Lemma 3.2]; used in Lemmas 3.1 and 3.2 to rule out vertex-transitive automorphism groups.
  • domain assumption Proposition 1.2 (Estelyi and Pisanski): each Haar graph of D_{2n} is a Cayley graph iff n = 2, 3, 4, 5.
    Used to exclude dihedral groups D16, D8p, D30, etc., and to confirm D6, D8, D10 are in BC.
  • domain assumption Proposition 1.3 (Feng, Kovacs, Yang): for inner abelian H, all Haar graphs are Cayley graphs iff H is isomorphic to D6, D8, D10, or Q8.
    Used for the sufficiency direction and for the base cases in Lemma 4.1.
  • domain assumption Magma computations in Lemma 3.2 (p = 3, 5), Lemma 3.3, and Lemma 4.1 verify the statements for the listed finite groups.
    The paper states these finite checks are done in Magma, but no code or certificates are provided. The reader cannot inspect the computation directly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Existence of non-Cayley Haar graphs." pith.science (2026). https://pith.science/paper/VPUWGJ3N

@misc{pith2026190804551,
  author       = {Pith},
  title        = {Pith review of: Existence of non-Cayley Haar graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VPUWGJ3N}},
  note         = {Machine review of arXiv:1908.04551}
}
abstract

A Cayley graph of a group $H$ is a finite simple graph $\Gamma$ such that its automorphism group ${\rm Aut}(\Gamma)$ contains a subgroup isomorphic to $H$ acting regularly on $V(\Gamma)$, while a Haar graph of $H$ is a finite simple bipartite graph $\Sigma$ such that ${\rm Aut}(\Sigma)$ contains a subgroup isomorphic to $H$ acting semiregularly on $V(\Sigma)$ and the $H$-orbits are equal to the partite sets of $\Sigma$. It is well-known that every Haar graph of finite abelian groups is a Cayley graph. In this paper, we prove that every finite non-abelian group admits a non-Cayley Haar graph except the dihedral groups $D_6$, $D_8$, $D_{10}$, the quaternion group $Q_8$ and the group $Q_8\times\mathbb{Z}_2$. This answers an open problem proposed by Est\'elyi and Pisanski in 2016.

Figures

Figures reproduced from arXiv: 1908.04551 by the authors.

Figure 1
Figure 1. The subgraph of Γ induced by the vertices at distance at m [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An induced subgraph of Γ. {(b −1 )1,(bc2 )1} setwise because these two vertices are antipodal to c1 in C3 and C4 respec￾tively, and since |Ah0 | = |Ak1 | for any h, k ∈ H, we have A10 = Ac1 . We first prove that A10 fixes the 4-cycle C1 setwise. Recall that A10 fixes {C1, C2} setwise. Suppose to the contrary that α ∈ A10 interchanges C1 and C2. Then {11,(bc)1} α = {a1,(abc−1 )1}, and since A10 fixes {(b −1 )1,(bc2 )… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [10]

    Y.-Q. Feng, I. Kov´ acs and D.-W. Yang,On groups all of whose Haar graphs are Cayley graphs, J. Algebraic Combin. (2019). https://doi.org/10.1007/s10801-0 19-00894-7

  2. [5]

    Bosma, C

    W. Bosma, C. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235–265

  3. [1]

    Antonˇ ciˇ c, A

    I. Antonˇ ciˇ c, A. Hujdurovi´ c and K. Kutnar, A classification of pentavalent arc- transitive bicirculants, J. Algebraic Combin. 41 (2015), 643–668

  4. [2]

    Araluze, I

    A. Araluze, I. Kov´ acs, K. Kutnar, L. Mart ´ ınez and D. Maruˇ siˇ c,Partial sum quadruples and bi-abelian digraphs , J. Combin. Theory Ser. A 119 (2012), 1811–1831

  5. [3]

    Aschbacher, Finite group theory , Cambridge University Press, Cambridge, 1986

    M. Aschbacher, Finite group theory , Cambridge University Press, Cambridge, 1986

  6. [4]

    Babai, On a conjecture of M

    L. Babai, On a conjecture of M. E. Watkins on graphical regular represe ntations of finite groups , Comp. Math. 37 (1978), 291–296. 13

  7. [6]

    Conder, I

    M. Conder, I. Est´ elyi and T. Pisanski, Vertex-transitive Haar graphs that are not Cayley graphs , In: Conder, M., Deza, A., Weiss, A. (eds.) Discrete Geometry and Symmetry. GSC 2015. Springer Proceedings in Mathematics & Statis tics, Vol 234, pp. 61–70. Springer, Cham, 2018

  8. [7]

    Dobson and P

    T. Dobson and P. Spiga, Cayley numbers with arbitrarily many distinct prime factor s, J. Combin. Theory B. 122 (2017), 301–310

Show all 31 references
  1. [8]

    Du, Y.-Q

    J.-L. Du, Y.-Q. Feng and P. Spiga, A Classification of the m-graphical regular repre- sentation of finite groups , preprint arXiv:1901.07133 [math.CO]

  2. [9]

    Est´ elyi and T

    I. Est´ elyi and T. Pisanski, Which Haar graphs are Cayley graphs , Electronic J. Com- bin. 23 (2016), #P3.10

  3. [11]

    Godsil, GRR’s for non-solvable groups , in: Algebraic methods in graph theory, Vol

    C.D. Godsil, GRR’s for non-solvable groups , in: Algebraic methods in graph theory, Vol. I, II Szeged (1978), pp. 221–239, Colloq. Math. Soc. J´ anos Bolyai, Amsterdam- New York 1981

  4. [12]

    Y.-Q. Feng, K. Kutnar, D. Maruˇ siˇ c and D.-W. Yang,On cubic symmetric non-Cayley graphs with solvable automorphism groups , preprint arXiv:1607.02618 [math.CO]

  5. [13]

    Hall and J.K

    M. Hall and J.K. Senior, The Groups of Order 2n (n ≤ 6), Macmillan, New York, 1964

  6. [14]

    Hladnik, Schur norms of bicirculant matrices , Lin

    M. Hladnik, Schur norms of bicirculant matrices , Lin. Alg. Appl. 286 (1999), 261– 272

  7. [15]

    Hladnik, D

    M. Hladnik, D. Maruˇ siˇ c and T. Pisanski, Cyclic Haar graphs , Discrete Math. 244 (2002), 137–153

  8. [16]

    Hujdurovi´ c, K

    A. Hujdurovi´ c, K. Kutnar and D. Maruˇ siˇ c,On normality of n-Cayley graphs , Appl. Math. Comput. 332 (2018), 469-476

  9. [17]

    Imrich, Graphs with transitive abelian automorphism group , in: Combinatorial theory and its applications, Balatonf¨ ured, 1969 (P

    W. Imrich, Graphs with transitive abelian automorphism group , in: Combinatorial theory and its applications, Balatonf¨ ured, 1969 (P. ErdHos et. a l eds.), pp. 651–656, Coll. Math. Soc. J´ anos Bolyai 4, North-Holland 1969

  10. [18]

    Imrich, Graphical regular representations of groups of odd order , in Combinatorics (A

    W. Imrich, Graphical regular representations of groups of odd order , in Combinatorics (A. Hajnal and V. T. S´ os eds.), pp. 611–621, Coll. Math. Soc. J´ anos Bolyai 18, North- Holland 1976

  11. [19]

    Imrich and M

    W. Imrich and M. E. Watkins, On graphical regular representation of cyclic extension of groups , Pacific J. Math. 55 (1974), 461–477. 14

  12. [20]

    Koike and I

    H. Koike and I. Kov´ acs, Isomorphic tetravalent cyclic Haar graphs , Ars Math. Con- temp. 7 (2014), 215–235

  13. [21]

    Li and ´A

    C.H. Li and ´A. Seress, On vertex-transitive non-Cayley graphs of square-free ord er, Des. Codes Cryptogr. 34 (2005), 265–281

  14. [22]

    Z.P. Lu, C.Q. Wang and M.Y. Xu, Semisymmetric cubic graphs constructed from bi-Cayley graphs of An, Ars Combin. 80 (2006), 177–187

  15. [23]

    Z.P. Lu, C.Q. Wang and M.Y. Xu, On semisymmetric cubic graphs of order 6p2, Sci. China Ser. A 47 (2004), 1–17

  16. [24]

    Maruˇ siˇ c,Cayley properties of vertex symmetric graphs , Ars Combin

    D. Maruˇ siˇ c,Cayley properties of vertex symmetric graphs , Ars Combin. 16 (1983), 297–302

  17. [25]

    Nowitz and M.E

    L.A. Nowitz and M.E. Watkins, On graphical regular representations of non-abelian groups I , Canad. J. Math. 24 (1972), 993–1008

  18. [26]

    Nowitz and M.E

    L.A. Nowitz and M.E. Watkins, On graphical regular representations of non-abelian groups II , Canad. J. Math. 24 (1972), 1009–1018

  19. [27]

    Watkins, On the action of non-abelian groups on graphs , J

    M.E. Watkins, On the action of non-abelian groups on graphs , J. Combin. Theory 11 (1971), 95–104

  20. [28]

    Zhou and Y.-Q

    J.-X. Zhou and Y.-Q. Feng, The automorphisms of bi-Cayley graphs , J. Combin. Theory Ser. B 116 (2016), 504–532

  21. [29]

    Zhou and Y.-Q

    J.-X. Zhou and Y.-Q. Feng, Cubic bi-Cayley graphs over abelian groups , European J. Combin. 36 (2014), 679–693

  22. [30]

    Zhou, Tetravlent vertex-transitive graphs of order 4p, J

    J.-X. Zhou, Tetravlent vertex-transitive graphs of order 4p, J. Graph Theory 71 (2012), 402–415

  23. [31]

    Zhou, Every finite group has a normal bi-Cayley graph , Ars Math

    J.-X. Zhou, Every finite group has a normal bi-Cayley graph , Ars Math. Contemp. 14 (2018), 177-186. 15

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.