Pith. sign in

REVIEW 5 major objections 5 minor 17 references

This paper proves that for every finite group G and every generating set S there is a 3-connected cubic graph D_{G,S} whose automorphism group is isomorphic to G and which carries an automorphism-invariant cycle double cover describing a po

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 11:34 UTC pith:Y6EHNCPY

load-bearing objection Clear new construction with a mostly solid automorphism proof, an underproved CDC half, and a minor false type claim — send to peer review. the 5 major comments →

arxiv 2607.19833 v1 pith:Y6EHNCPY submitted 2026-07-22 math.CO cs.DM

Polyhedral Maps of Cubic Graphs with given Automorphism Groups

Ugo Detaille , Meike Wei{\ss} , Reymond Akpanya , Alice C. Niemeyer This is my paper
classification math.CO cs.DM MSC 05C2505C10
keywords cubic graphsautomorphism groupspolyhedral mapscycle double coversCayley graphsvertex types3-connected graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The theorem at the center of the paper states that for every finite group G and every generating set S, one can construct a 3-connected cubic undirected graph D_{G,S} with Aut(D_{G,S}) ≅ G, together with a cycle double cover Z of D_{G,S} that describes a polyhedral map (any two cycles meet in at most one edge) and that is invariant under Aut(D_{G,S}). The construction starts from the directed, edge-coloured Cayley graph of G and replaces its vertices and directed edges by small cubic gadgets: blow-up graphs and chains whose ladder lengths encode the generator colours and orientation. The proof that the automorphism group is not enlarged runs through vertex types, triples of shortest cycle lengths through pairs of incident edges, which rigidly distinguish the different gadget vertices. The cycle double cover is assembled from inner face cycles, roof edge cycles, and base edge cycles, and its completeness and polyhedral property follow from the decomposition of G into left cosets of cyclic subgroups generated by products of the generators. A sympathetic reader would take the paper as establishing that arbitrary finite symmetry groups can be realized simultaneously at the graph level and at the level of a polyhedral embedding.

Core claim

The central claim is that a modified Cayley-graph construction yields a rigid, polyhedrally embeddable cubic graph: for every finite group G and generating set S, the graph D_{G,S} is cubic and 3-connected, its automorphism group is isomorphic to G via the left regular action, and there is an explicit cycle double cover Z = Z_i ∪ Z_r ∪ Z_b whose cycles form the faces of a polyhedral map and are permuted by all automorphisms of D_{G,S}. In addition, the roof and base cycles are not arbitrary: their vertex sets correspond exactly to left cosets of the cyclic subgroups generated by the product of all generators (for roof cycles) and by each individual generator (for base cycles). This coset str

What carries the argument

The load-bearing object is the gadget-substituted graph D_{G,S}. Each vertex g of the Cayley graph becomes a blow-up graph A_g made of s_d-blocks (connector and center vertices joined in a cycle), and each directed edge of colour d becomes a d-chain: a ladder of length d with an endgadget attached, whose endgadget connects to the neighbouring blow-up graphs. Rigidity is carried by vertex types, triples (λ1, λ2, λ3) of lengths of shortest cycles through pairs of incident edges, arranged in ascending order. The types in Table 1 are claimed to separate endgadget, ladder, connector, and center vertices, so an automorphism must move each blow-up graph and each chain as a whole, forcing left multi

Load-bearing premise

The rigidity argument depends on the unshown claim that the vertex-type triples in Table 1 are exactly as listed and mutually distinctive for the endgadget, ladder, connector, and center vertices; if any shortest-cycle computation differs, an automorphism could mix gadgets and Aut(D_{G,S}) ≅ G would not follow.

What would settle it

For a concrete small case, build D_{G,S} for G=C2 with S={s} (32 vertices, 48 edges) and enumerate all its automorphisms: if the automorphism group has more than two elements, the theorem fails. Alternatively, list all shortest cycles through pairs of incident edges at the ten endgadget vertices and compare the resulting type triples with Table 1; any mismatch would break the rigidity proof.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For any finite group, there exists a 3-connected cubic graph whose automorphism group, and whose polyhedral-map automorphism group, is isomorphic to that group.
  • The face cycles of the polyhedral map are permuted by the full automorphism group, so the group acts on the map itself, not merely on the underlying graph.
  • The explicit formulas give the number of cycles and the Euler characteristic in terms of n, k, and the orders of products of generators; for k=1 the resulting map is spherical.
  • Varying the ordering of a fixed generating set can produce non-isomorphic graphs with the same prescribed automorphism group, yielding distinct realizations.

Where Pith is reading between the lines

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

  • The left-coset description of roof and base cycles suggests a design principle the paper does not state: one could prescribe face lengths in the polyhedral map by choosing generators with specified orders and products, provided those orders are compatible with the group.
  • If the vertex-type table is verified, it gives a potential recognition algorithm for these graphs: scan a cubic graph for the endgadget/ladder/connector/center type signatures, and matching signatures would identify the blow-up graphs and chains, from which the group and generating set could be recovered up to ordering.
  • The paper says it is exploring k-regular analogues; a natural next step would be replacing the chain ladders with higher-degree carriers of more colours, though the vertex-type separation would need to be re-established for each degree.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

Summary. The paper proposes, for an arbitrary finite group G with generating set S, a cubic graph D_{G,S} obtained by modifying the directed coloured Cayley graph Cay(G,S): vertices are replaced by blow-up graphs A_g and each directed edge of colour d by a 'd-chain' (a ladder of length d plus an endgadget). The central claim is that D_{G,S} is 3-connected, Aut(D_{G,S}) is isomorphic to G, and a constructed set of cycles Z is a cycle double cover that induces a polyhedral map and is invariant under Aut(D_{G,S}). The automorphism claim is argued in Section 3.2 by vertex-type invariants; the CDC is constructed in Section 4 and its properties are discussed in Section 5.

Significance. If correct, the main theorem gives a strong finite realization result: every finite group occurs simultaneously as the automorphism group of a 3-connected cubic graph and of a polyhedral map carried by it, with face cycles preserved. The construction is explicit, includes vertex and cycle counts, connects roof/base cycles to left cosets, and is accompanied by GAP/Magma implementations; these are genuine strengths. It would improve on Babai's cubic graph construction, which is only 2-connected, and on the earlier CDC construction in [1] by controlling face intersections. The proof, however, is not complete in the submitted form.

major comments (5)
  1. [Section 3.2, after Table 1] The statement that every connector vertex has type (4,8,10) is not correct for k=1,2, and the sentence 'The remaining two cases simply follow by omitting the images of the non-existing center vertices' does not repair this. In the k=2 blow-up A_g depicted in Figure 5(b), the vertex a^{1,1}_g is incident with edges e1={a^{1,1}_g,a^{1,2}_g}, e2={a^{1,1}_g,a^{2,4}_g}, and e3={a^{1,1}_g,C[1,g,gs_1](u1)}. The cycle a^{1,1}_g - a^{1,2}_g - c^{1,1}_g - c^{2,1}_g - a^{2,3}_g - a^{2,4}_g - a^{1,1}_g has length 6 and contains e1 and e2, so the type is not (4,8,10). For k=1 the analogous pair is contained in the 4-cycle of A_g. Since Lemmas 3.4–3.6 use this invariant to force the partition V(A_G),V(C_G) and to determine d-chain images, the proof of Aut(D_{G,S}) is incomplete for k=1,2. The authors should either compute correct types for these cases or give a separate automorphism argument. Even for
  2. [Section 4.1] The inner face cycles are never formally defined; the text says 'Instead of providing a formal definition... describe the cycles and illustrate them graphically.' The subsequent claims that any two cycles in Z_i intersect in at most one edge and that every edge is contained in at least one cycle of Z_i are load-bearing for Theorem 5.2. A figure-based definition is not enough, especially because the paper itself notes the construction may not be planar and the 'green faces' are only described informally. Please provide an explicit list or algorithm and prove the intersection and coverage statements.
  3. [Section 4.2, Remark 4.1] The three properties that roof cycles are pairwise edge-disjoint, meet each inner face cycle in at most one edge, and cover exactly the stated set of edges are introduced with 'We only state these results without proof.' These properties are exactly what Theorem 5.2 needs; the same applies to base cycles by the sentence following Remark 4.1. Asserting them without proof is a gap, not a routine omission.
  4. [Section 5, Lemma 5.1 and Theorem 5.2] Lemma 5.1 is itself only sketched ('we only sketch the proof', 'observe that the same property still holds'), and Theorem 5.2 then invokes it to conclude completeness and correctness of the CDC. The proof of Theorem 5.2 does not verify the defining conditions of a CDC: it does not show every edge is contained in exactly two cycles, nor that every pair of cycles from the three families intersects in at most one edge. The sentence 'no roof edge cycle intersects with a base edge cycle, simply because they traverse different chain edges, as well as different blow-up graph vertices' addresses only one pair of families. This is a central part of the main theorem and needs a complete proof.
  5. [Section 5, Theorem 5.4] The invariance of Z under Aut(D_{G,S}) is one of the three stated properties of the main theorem, but the proof is only a prose paragraph ending 'Formally, we can prove...'. No formal argument is given. While this may follow from Lemmas 3.4–3.5 if the cycle families are characterized by local structure, the paper should spell out the argument, including why Z_i, Z_r, and Z_b are each invariant.
minor comments (5)
  1. [Section 3.2] In the first paragraph, 'the graph D_{G,S} from Theorem 3.1' should be 'Definition 3.1'.
  2. [Section 3.2] Cross-references are inconsistent: Lemmas 3.4 and 3.5 are sometimes called 'Theorem 3.4' and 'Theorem 3.5' in later proofs (e.g., in the proof of Lemma 3.5).
  3. [Section 5] In the proof of Theorem 5.2, 'Theorem 5.1' should be 'Lemma 5.1'.
  4. [Figure 5(b)] The k=2 case should state explicitly whether c^{1,1}_g and c^{2,1}_g are adjacent. The informal drawing is used in a load-bearing way, and the ambiguity affects the vertex-type computation.
  5. [Section 2] The expression 'd+1 modd k' is confusing; adding parentheses or a verbal explanation would help.

Circularity Check

0 steps flagged

No load-bearing circularity: the construction and automorphism proof are synthetic rather than derived from the theorem's conclusion; the main fragility is an unverified vertex-type computation, which is a correctness gap, not a circular step.

full rationale

The paper's central claim is not obtained by fitting a parameter to its own output or by importing an unverified uniqueness theorem from the same authors. The graph D_{G,S} is explicitly constructed from the Cayley graph of (G,S) in Definition 3.1, and the injection from G into Aut(D_{G,S}) is only one inclusion; the difficult direction, showing there are no extra automorphisms, is attempted through the local invariants in Section 3.2. The assertion that 'all connector vertices a^{d,i}_g have the type (4,8,10)' and that 'The values can be easily determined by reviewing Figures 4 to 6' is an invariant computation inside the constructed graph, not a premise that presupposes Aut(D_{G,S}) ≅ G. If that computation is wrong, especially for k=1,2, then the proof of Theorem 3.7 would be incomplete or invalid, but that is a factual/verification defect rather than circularity. Similarly, the CDC construction in Section 4 is an explicit set of cycles, and its correctness, completeness, and polyhedral property are argued in Section 5 through coset decompositions, not by assuming the conclusion. The citations to [1] and [6] include current authors, but they are used as background, motivation, or pointers to implementations; no load-bearing theorem is imported from them. There is therefore at most harmless self-citation, not a self-referential derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No fitted numeric parameters; the construction takes G and S as inputs. The axioms are standard background facts plus two unproved local combinatorial assertions. The gadget graphs (endgadget, d-chain, blow-up graph) are explicit construction components, not hidden postulates; no extra physical entities are introduced.

axioms (4)
  • standard math Aut(Cay_{G,S}) = L(G) for the edge-coloured directed Cayley graph.
    Used in Section 2 and Theorem 3.7 to translate left translations to graph automorphisms; standard result when generator colours are distinct.
  • domain assumption A cubic graph with a CDC inducing a polyhedral map is 3-connected (Mohar–Thomassen).
    Used in Section 2 to derive 3-connectedness from property (2); accepted from [13].
  • ad hoc to paper The vertex-type triples in Table 1 are correct and separate the vertex classes.
    The rigidity proof in Lemmas 3.4–3.6 depends on these types; the paper says they are easily determined but does not prove them.
  • ad hoc to paper The inner face cycles have pairwise intersections of at most one edge and cover every edge at least once.
    Assumed in Section 4.1 with 'straightforward to verify'; it is a load-bearing part of Z being a CDC/polyhedral map.

pith-pipeline@v1.3.0-alltime-deepseek · 15497 in / 17435 out tokens · 170093 ms · 2026-08-01T11:34:42.227333+00:00 · methodology

0 comments
read the original abstract

L. Babai introduced a method for constructing a cubic graph whose automorphism group is isomorphic to a given finite group $G$, obtained by modifying a corresponding Cayley graph of $G$. Building on this approach, we construct a cubic graph that admits a polyhedral map whose automorphism group, as well as the automorphism group of the polyhedral map itself, is isomorphic to $G$.

Figures

Figures reproduced from arXiv: 2607.19833 by Alice C. Niemeyer, Meike Wei{\ss}, Reymond Akpanya, Ugo Detaille.

Figure 1
Figure 1. Figure 1: The subgraph replacing the original Cayley graph edge [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The blow-up of a vertex g ∈ V (CayG,S) into a cycle of length 2k and its immediate neighbourhood [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The endgadget. Next, we define the undirected subgraph that replaces a directed edge of the Cayley graph, while preserving both the colour and orientation of the edge in CayG,S. For an edge (g, h) ∈ E(CayG,S) of colour d ∈ [k] with respect G = ⟨S⟩, we define the d-chain from g to h as the graph C[d,g,h] consisting of a ladder of length d combined with an endgadget, as depicted in [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 4
Figure 4. Figure 4: The chain C[d,g,h] . label in the set {ui , ℓi , j | i ∈ [d], j ∈ {0, . . . , 9}}. We always use the labels ui and ℓi for the vertices of the ladder, where u stands for upper and ℓ for lower. Clearly, this notation is well-defined and unique for every vertex. For 1 ≤ i < d, we refer to the edges of the form  C[d,g,h](ui), C[d,g,h](ui+1) [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The blow-up graph Ag for various k. In the final construction step of our cubic graph, we connect the blow-up graphs to the d-chains. Given an edge (g, h) of colour d in E(CayG,S), we connect the vertex a d.1 g to the vertex C[d,g,h](u1), and a d.2 g to C[d,g,h](ℓ1). Similarly, for an edge (h ′ , g) of colour d in the Cayley graph, we connect a d.4 g to C[d,h′ ,g](6), and a d.3 g to C[d,h′ ,g](9). We illus… view at source ↗
Figure 6
Figure 6. Figure 6: An sd-block (red) in g and its immediate neighbourhood for k ≥ 3. 3. E1 := S g∈G E(Ag) (the edges of the blow-up graphs for all g ∈ G), 4. E2 := S d∈[k] S (g,h)∈E(CayG,S ) C((g,h))=d E(C[d,g,h]) (the d-chain edges for all edges (g, h) ∈ E(CayG,S)), 5. E3 := S d∈[k] S (g,h)∈E(CayG,S ) C((g,h))=d a d.1 g , C[d,g,h](u1) [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The inner face cycles of Ag for k = 1 (a), k = 2 (b) and k = 4 (c). 4.2 The Roof Edge Cycles In this section, we describe a set that covers all roof edges of the gadgets, which motivates its name. The following edges lie in exactly one cycle of Zi and in exactly one cycle of Zr, the latter set being constructed in this subsection: 1. the upper chain edges, that are the edges  C[d,g,h](uj ), C[d,g,h](uj+1)… view at source ↗
Figure 8
Figure 8. Figure 8: The inner face cycles in a d-chain. 4. the upper connection edges, that are the edges of the form  a d.1 g , C[d,g,h](u1) [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The roof edge cycles (red) in the blow-up graphs [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The roof edge cycles (red) in a d-chain. The case that G is generated by one element (k = 1) is exceptional, as the graph DG,S does not contain any center vertices. Hence, we simply omit traversing the center vertices c d.1 g and only traverse the two connector vertices a d.2 g and a d.3 g . Similarly to the upper path, for an edge (g, h) ∈ E(CayG,S) of colour d, we define the unique lower path from a d.2… view at source ↗
Figure 11
Figure 11. Figure 11: The base edge cycles (green) in the blow-up graphs [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The base edge cycles (green) in a d-chain. Proof. We have to show three properties of the computed paths: The fact that they are cycles, as well as the completeness and correctness of Z. Firstly, it is easy to see that the roof edge cycles and the base edge cycles are indeed cycles. This follows immediately from (1) in Theorem 5.1. Seeing that we start in some a 1.1 g in a roof edge cycle, or in some a d.… view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

17 extracted references

  1. [1]

    Simplicial surfaces with given automorphism group

    Reymond Akpanya and Tom Goertzen. Simplicial surfaces with given automorphism group. Journal of Algebraic Combinatorics, 62, 07 2025

    2025

  2. [2]

    Mitchell, MichaelTorpey, MariaTsalakou, andWilf A

    JanDe Beule, Julius Jonušas, JamesD. Mitchell, MichaelTorpey, MariaTsalakou, andWilf A. Wilson. Digraphs - GAP package, version 1.10.0, Feb 2025

    2025

  3. [3]

    The Magma algebra system

    Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language. volume 24, pages 235–265. 1997. Computational algebra and number theory (London, 1993)

    1997

  4. [4]

    Polyhedral maps

    Ulrich Brehm and Egon Schulte. Polyhedral maps. In Jacob E. Goodman and Joseph O’Rourke, editors,Handbook of Discrete and Computational Geometry, chapter 20, pages 345–358. CRC Press, 1997

    1997

  5. [5]

    Construction of maps with prescribed automorphism group

    Robert Cori and Antonio Machì. Construction of maps with prescribed automorphism group. Theoret. Comput. Sci., 21(1):91–98, 1982

    1982

  6. [6]

    Implementation.https://github.com/MeikeWeiss/ PolyhedralMapsWithGivenGroup, 2025

    Ugo Detaille. Implementation.https://github.com/MeikeWeiss/ PolyhedralMapsWithGivenGroup, 2025

    2025

  7. [7]

    Herstellung von Graphen mit vorgegebener abstrakter Gruppe.Compositio Math., 6:239–250, 1939

    Robert Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe.Compositio Math., 6:239–250, 1939

    1939

  8. [8]

    Graphs of degree three with a given abstract group.Canadian Journal of Mathematics, 1(4):365–378, 1949

    Robert Frucht. Graphs of degree three with a given abstract group.Canadian Journal of Mathematics, 1(4):365–378, 1949

    1949

  9. [9]

    How I became interested in graphs and groups.J

    Roberto Frucht. How I became interested in graphs and groups.J. Graph Theory, 6(2):101– 104, 1982

    1982

  10. [10]

    The GAP Group.GAP – Groups, Algorithms & Programming, Vers. 4.12.2

  11. [11]

    Gross and Thomas W

    Jonathan L. Gross and Thomas W. Tucker.Topological graph theory. Dover Publications, Inc., Mineola, NY, 2001

    2001

  12. [12]

    North-Holland Publishing Co., Ams- terdam, second edition, 1993

    László Lovász.Combinatorial problems and exercises. North-Holland Publishing Co., Ams- terdam, second edition, 1993. p. 426

    1993

  13. [13]

    Johns Hopkins Studies in the Mathematical Sciences

    Bojan Mohar and Carsten Thomassen.Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001

    2001

  14. [14]

    Graphs with given group and given graph-theoretical properties.Canadian J

    Gert Sabidussi. Graphs with given group and given graph-theoretical properties.Canadian J. Math., 9:515–525, 1957

    1957

  15. [15]

    P. D. Seymour. Sums of circuits. InGraph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), pages 341–355. Academic Press, New York-London, 1979

    1977

  16. [16]

    Szekeres

    G. Szekeres. Polyhedral decompositions of cubic graphs.Bulletin of the Australian Mathe- matical Society, 8(3):367–387, 1973

    1973

  17. [17]

    Orientableandnonorientablemapswithgivenautomorphism groups.Australas

    JozefŠiráňandMartinŠkoviera. Orientableandnonorientablemapswithgivenautomorphism groups.Australas. J. Combin., 7:47–53, 1993. 17

    1993