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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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.
- [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)
- [Section 3, Lemma 3.2] In the paragraph following Eq. (6), 'anb by Eq. (1)' should read 'and by Eq. (1)'.
- [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.
- [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.
- [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
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
assumptions (6)
- domain assumption Proposition 2.2: BC is closed under taking subgroups.
- 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.
- 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.
- domain assumption Proposition 1.2 (Estelyi and Pisanski): each Haar graph of D_{2n} is a Cayley graph iff n = 2, 3, 4, 5.
- 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.
- 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.
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
Reference graph
Works this paper leans on
-
[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
- [5]
-
[1]
I. Antonˇ ciˇ c, A. Hujdurovi´ c and K. Kutnar, A classification of pentavalent arc- transitive bicirculants, J. Algebraic Combin. 41 (2015), 643–668
work page 2015
-
[2]
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
work page 2012
-
[3]
Aschbacher, Finite group theory , Cambridge University Press, Cambridge, 1986
M. Aschbacher, Finite group theory , Cambridge University Press, Cambridge, 1986
work page 1986
-
[4]
L. Babai, On a conjecture of M. E. Watkins on graphical regular represe ntations of finite groups , Comp. Math. 37 (1978), 291–296. 13
work page 1978
-
[6]
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
work page 2015
-
[7]
T. Dobson and P. Spiga, Cayley numbers with arbitrarily many distinct prime factor s, J. Combin. Theory B. 122 (2017), 301–310
work page 2017
Show all 31 references
-
[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]
1901 arXiv
-
[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
2016
-
[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
1978
-
[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]
-
[13]
Hall and J.K
M. Hall and J.K. Senior, The Groups of Order 2n (n ≤ 6), Macmillan, New York, 1964
1964
-
[14]
Hladnik, Schur norms of bicirculant matrices , Lin
M. Hladnik, Schur norms of bicirculant matrices , Lin. Alg. Appl. 286 (1999), 261– 272
1999
-
[15]
Hladnik, D
M. Hladnik, D. Maruˇ siˇ c and T. Pisanski, Cyclic Haar graphs , Discrete Math. 244 (2002), 137–153
2002
-
[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
2018
-
[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
1969
-
[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
1976
-
[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
1974
-
[20]
Koike and I
H. Koike and I. Kov´ acs, Isomorphic tetravalent cyclic Haar graphs , Ars Math. Con- temp. 7 (2014), 215–235
2014
-
[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
2005
-
[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
2006
-
[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
2004
-
[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
1983
-
[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
1972
-
[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
1972
-
[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
1971
-
[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
2016
-
[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
2014
-
[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
2012
-
[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
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.