pith. sign in

arxiv: 2605.16741 · v1 · pith:SIYD6NTKnew · submitted 2026-05-16 · 🧮 math.CO

Hypermaps with hyperedges of length at most 3

Robert Cori , G\'abor Hetyei This is my paper

Pith reviewed 2026-05-19 21:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypermapsWhitney polynomialspanning hypertreesdeletion-contractionreliability polynomialrandom cluster modelhypergraphs
0
0 comments X

The pith

For hypermaps with hyperedges of length at most 3, the Whitney polynomial and spanning hypertree counts depend only on the underlying multi-hypergraph structure.

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

The paper focuses on hypermaps where each hyperedge connects at most three points. For this restricted class the Whitney polynomial and the count of spanning hypertrees turn out to be determined solely by the multi-hypergraph itself rather than by any particular embedding on a surface. The authors supply deletion-contraction relations that treat six kinds of generalized loops and bridges, and they establish special substitutions that simplify the polynomial. They also extend the classical reliability polynomial and the random-cluster model to hypermaps so that both can be evaluated with the Whitney polynomial. As a concrete application they give explicit formulas for the number of spanning hypertrees in the reciprocals of plane graphs whose vertices all have degree at most three.

Core claim

We study the computation of our recently introduced Whitney polynomial and the enumeration of the spanning hypertrees for hypermaps whose hyperedges have length at most 3. This is a class of hypermaps where the computation of the above invariants depends only on the underlying (multi)hypergraph structure. We develop deletion-contraction formulas involving six types of generalized loops and bridges, and we prove results on special substitutions into our Whitney polynomial. We generalize the reliability polynomial and the random cluster model to hypermaps in general in such a way that they can be computed using our Whitney polynomial. Finally we explicitly count the spanning hypertrees in the

What carries the argument

Deletion-contraction formulas involving six types of generalized loops and bridges applied to the Whitney polynomial.

If this is right

  • The Whitney polynomial for these hypermaps can be evaluated recursively by deletion and contraction.
  • Spanning hypertree counts reduce to ordinary hypergraph enumeration.
  • The reliability polynomial of a hypermap is obtained directly from its Whitney polynomial.
  • The random-cluster model on hypermaps is computable via the same polynomial.
  • Spanning hypertrees in reciprocals of degree-at-most-3 plane graphs admit explicit closed-form counts.

Where Pith is reading between the lines

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

  • The restriction to short hyperedges may make algorithmic computation feasible for larger families of maps that can be reduced to this case.
  • The same independence from embedding might hold for other polynomial invariants defined on hypermaps.
  • The generalized random-cluster model could connect hypermap enumeration to statistical-mechanics problems on surfaces with bounded face sizes.

Load-bearing premise

The computation of the Whitney polynomial and the enumeration of spanning hypertrees for this class of hypermaps depends only on the underlying (multi)hypergraph structure rather than on the embedding.

What would settle it

Two distinct embeddings of the same multi-hypergraph with all hyperedges of length at most 3 that produce different Whitney polynomial values or different numbers of spanning hypertrees.

Figures

Figures reproduced from arXiv: 2605.16741 by G\'abor Hetyei, Robert Cori.

Figure 1
Figure 1. Figure 1: A hypermap with short hyperedges and its associated two￾colored map If (σ, α) is a hypermap with short hyperedges then the associated collection of two￾colored maps (Sα(σ), Aα(α)) is a map. More generally we have the following result. Proposition 7.4. Let (σ, α) be a collection of hypermaps with short hyperedges. Then then the associated collection of maps satisfies κ(σ, α) = κ(Sα(σ), Aα(α)). Proof. Using … view at source ↗
Figure 2
Figure 2. Figure 2: The collection of maps (Sα(σ), Rα(β)) for β = (4, 5)(7, 8) Consider the hypermap (σ, α) introduced in Example 7.3 and the refinement β = (4, 5)(7, 8) of α. The cycle (6, 7, 8) of α is replaced by (7, 8) in β and (3, 6) becomes an isolated vertex of (σ, β). Correspondingly, we delete the edge (6, 6 ′ ) in (Sα(σ), Aα(α)) and this turns the black vertex (3, 6) also into an isolated point. The collection of ma… view at source ↗
Figure 3
Figure 3. Figure 3: The collection of maps (Sα(σ), θ′′) for θ = (4, 5)(6, 7, 8) (σ, θ) such that S(θ) = S1. The map (σ, θ) 7→ H(σ, θ) [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An unreachable spanning tree obtain that the number of all spanning hypertrees of (σ, θ) is given by X S1⊆W(σ,α) X S2⊆W(σ,α)−S (−3)|S2| s [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The map (σ, α) and the two-colored graph G(α, σ) [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: G(α, σ) for (σ, α) whose underlying graph is K4 Example 9.4. If the underlying graph of (σ, α) is the complete graph K4 then the associated two-colored graph G(α, σ) is shown in [PITH_FULL_IMAGE:figures/full_fig_p022_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The map (σ6, α6) and the associated two-colored graph G(α6, σ6) We illustrate the effect of removing some white vertices in [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: Components arising after the removal of the deleted and bridge edges (1) Graphs, whose bounded faces all have 8 sides. An example of such a graph is shown on the left hand side of [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A generalized pencil graph Definition 9.8. For m ≥ 1 let a1, a2, . . . , am and t be positive integers. We define the generalized pencil graph P(a1, . . . , am;t) as the following graph on the vertex set {u, v1, v2, . . . , vm}: (1) There are ai parallel edges between u and vi for i = 1, . . . , m. (2) If m ≥ 2 then there are t parallel edges between vi and vi+1 for i = 1, 2, . . . , m−1. The following st… view at source ↗
read the original abstract

We study the computation of our recently introduced Whitney polynomial and the enumeration of the spanning hypertrees for hypermaps whose hyperedges have length at most $3$. This is a class of hypermaps where the computation of the above invariants depends only on the underlying (multi)hypergraph structure. We develop deletion-contraction formulas involving six types of generalized loops and bridges, and we prove results on special substitutions into our Whitney polynomial. We generalize the reliability polynomial and the random cluster model to hypermaps in general in such a way that they can be computed using our Whitney polynomial. Finally we explicitly count the spanning hypertrees in reciprocals of plane graphs in which every vertex has degree at most $3$.

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

2 major / 2 minor

Summary. The paper studies the Whitney polynomial and spanning hypertree enumeration for hypermaps whose hyperedges have length at most 3. It asserts that these invariants depend only on the underlying multi-hypergraph (not the embedding), develops deletion-contraction formulas using six types of generalized loops and bridges, proves substitution results for the Whitney polynomial, generalizes the reliability polynomial and random cluster model to hypermaps, and gives explicit counts of spanning hypertrees for reciprocals of plane graphs with maximum vertex degree 3.

Significance. If the central claims hold, the work supplies deletion-contraction recurrences that reduce the Whitney polynomial and hypertree counts to ordinary multi-hypergraph data for this restricted class, together with concrete generalizations of reliability and random-cluster models and explicit enumerations for a family of reciprocal graphs. These results would extend standard graph-theoretic tools to a natural subclass of hypermaps while preserving computability from the underlying structure.

major comments (2)
  1. [section on deletion-contraction formulas] The load-bearing claim that the six generalized deletion-contraction relations render the Whitney polynomial independent of the rotation system (for hyperedges of length exactly 3) is asserted in the abstract and introduction but lacks a detailed case-by-case verification that none of the six relations inadvertently retains cyclic-order information around a length-3 hyperedge. If any relation encodes embedding data, the reduction to the underlying multi-hypergraph fails.
  2. [proof of independence from embedding] The proof that the Whitney polynomial and spanning-hypertree enumeration depend only on the multi-hypergraph structure (rather than the embedding) is the central reduction; the manuscript must exhibit an explicit argument or computation showing that distinct embeddings of the same multi-hypergraph yield identical polynomials under the six relations.
minor comments (2)
  1. A compact table summarizing the six types of generalized loops and bridges, together with their deletion and contraction rules, would improve readability.
  2. The generalization of the random-cluster model to hypermaps would benefit from a short paragraph contrasting the hypermap version with the classical graph case.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the independence argument can be made more explicit. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [section on deletion-contraction formulas] The load-bearing claim that the six generalized deletion-contraction relations render the Whitney polynomial independent of the rotation system (for hyperedges of length exactly 3) is asserted in the abstract and introduction but lacks a detailed case-by-case verification that none of the six relations inadvertently retains cyclic-order information around a length-3 hyperedge. If any relation encodes embedding data, the reduction to the underlying multi-hypergraph fails.

    Authors: We agree that an explicit verification strengthens the presentation. The six relations are defined in Section 3 using only the incidence data of each hyperedge (its vertices and multiplicity) and the local connectivity after deletion or contraction; the rotation system is never consulted in the statements or proofs of the relations. For length-3 hyperedges the possible combinatorial types are finite and enumerated in the definitions of the generalized loops and bridges. We will insert a new subsection that performs the case analysis for each of the six relations, confirming that the resulting recurrence depends solely on the multi-hypergraph. revision: yes

  2. Referee: [proof of independence from embedding] The proof that the Whitney polynomial and spanning-hypertree enumeration depend only on the multi-hypergraph structure (rather than the embedding) is the central reduction; the manuscript must exhibit an explicit argument or computation showing that distinct embeddings of the same multi-hypergraph yield identical polynomials under the six relations.

    Authors: The independence is obtained because every application of the six relations replaces a hyperedge by a combination of smaller hyperedges or by deletion/contraction steps whose combinatorial effect is recorded only in the incidence matrix of the underlying multi-hypergraph. Consequently any two rotation systems on the same multi-hypergraph produce identical sequences of reductions and therefore the same polynomial value. To make this fully explicit we will add a short inductive argument (on the number of hyperedges) together with a direct comparison of the two embeddings at the base cases; this will be placed immediately after the statement of the deletion-contraction theorem. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior Whitney polynomial definition; central deletion-contraction results are new and independent

full rationale

The paper cites its own prior introduction of the Whitney polynomial but develops fresh deletion-contraction relations for the length-at-most-3 case and proves embedding-independence directly from those relations rather than reducing the target quantities to fitted parameters or self-referential definitions. No step equates a derived quantity to an input by construction, and the enumeration results for spanning hypertrees rest on explicit combinatorial arguments rather than imported uniqueness theorems or ansatzes from the authors' earlier work. This yields only a low-level self-citation that does not bear the load of the main claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed from abstract alone; no explicit free parameters, invented entities, or additional axioms beyond the stated domain restriction are visible.

axioms (1)
  • domain assumption For hypermaps whose hyperedges have length at most 3 the Whitney polynomial and spanning-hypertree counts depend only on the underlying multi-hypergraph.
    Directly asserted in the abstract as the defining property of the class under study.

pith-pipeline@v0.9.0 · 5639 in / 1387 out tokens · 41388 ms · 2026-05-19T21:30:08.974253+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

25 extracted references · 25 canonical work pages

  1. [1]

    Arratia, B

    R. Arratia, B. Bollob´ as and G.B. Sorkin, The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), 237–245, ACM, New York, 2000

    work page 2000

  2. [2]

    Bernardi, A characterization of the Tutte polynomial via combinatorial embeddings,Ann

    O. Bernardi, A characterization of the Tutte polynomial via combinatorial embeddings,Ann. Comb.12(2008), 139–153

    work page 2008

  3. [3]

    Bollob´ as, Evaluations of the circuit partition polynomial,J

    B. Bollob´ as, Evaluations of the circuit partition polynomial,J. Combin. Theory Ser. B85(2002), 261–268

    work page 2002

  4. [4]

    Un code pour les Graphes Planaires et ses applications,

    R. Cori, “Un code pour les Graphes Planaires et ses applications,”Asterisque27(1975)

    work page 1975

  5. [5]

    Cori, Codage d’une carte planaire et hyperarbres recouvrants, Colloques Internat

    R. Cori, Codage d’une carte planaire et hyperarbres recouvrants, Colloques Internat. C.N.R.S, Orsay (1976)

    work page 1976

  6. [6]

    Cori and G

    R. Cori and G. Hetyei, Spanning hypertrees, vertex tours and meanders,European J. Combin. 119(2024), Paper No. 103805, 29 pp

    work page 2024

  7. [7]

    Cori and G

    R. Cori and G. Hetyei, A Whitney polynomial for hypermaps,Adv. in Appl. Math.171(2025), Paper No. 102951, 35 pp

    work page 2025

  8. [8]

    Cori and A

    R. Cori and A. Mach` ı, Flows on hypermaps,Glasgow Math. J.30(1988), 17–29

    work page 1988

  9. [9]

    Cori and J-G

    R. Cori and J-G. Penaud, The complexity of a planar hypermap and that of its dual, Combinatorics 79 (Proc. Colloq., Univ. Montr´ eal, Montreal, Que., 1979), Part II.Ann. Discrete Math.9(1980), 53–62

    work page 1979

  10. [10]

    J. A. Ellis-Monaghan, New results for the Martin polynomial,J. Combin. Theory Ser. B74 (1998), 326–352

    work page 1998

  11. [11]

    J. A. Ellis-Monaghan, Martin polynomial miscellanea, in: Proceedings of the Thirtieth South- eastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999),Congr. Numer.137(1999), 19–31

    work page 1999

  12. [12]

    J. A. Ellis-Monaghan, Identities for circuit partition polynomials, with applications to the Tutte polynomial, Special issue on the Tutte polynomial,Adv. in Appl. Math.32(2004), 188–197

    work page 2004

  13. [13]

    J. A. Ellis-Monaghan, Exploring the Tutte-Martin connection,Discrete Math.281(2004), 173– 187

    work page 2004

  14. [14]

    C. M. Fortuin and P. W. Kasteleyn, On the random-cluster model, I. Introduction and relation to other models,Physica57(1972), 536–564

    work page 1972

  15. [15]

    Jacques, Sur le genre d’une paire de substitutions,C

    A. Jacques, Sur le genre d’une paire de substitutions,C. R. Acad. Sci. Paris267(1968), 625–627

    work page 1968

  16. [16]

    D. M. Jackson, The lattice of noncrossing partitions and the Birkhoff-Lewis equations,European J. Combin.15(1994), 245–250

    work page 1994

  17. [17]

    Kreweras, Sur les partitions non crois´ ees d’un cycle,Discrete Math.1(1972), 333–350

    G. Kreweras, Sur les partitions non crois´ ees d’un cycle,Discrete Math.1(1972), 333–350

    work page 1972

  18. [18]

    Mach` ı, On the complexity of a hypermap,Discrete Math.42(1982), 221–226

    A. Mach` ı, On the complexity of a hypermap,Discrete Math.42(1982), 221–226

    work page 1982

  19. [19]

    Martin, Enum´ erations eul´ eriennes dans les multigraphes et invariants de Tutte-Grothendieck, Thesis, Grenoble, 1977

    P. Martin, Enum´ erations eul´ eriennes dans les multigraphes et invariants de Tutte-Grothendieck, Thesis, Grenoble, 1977

    work page 1977

  20. [20]

    Martin, Remarkable valuation of the dichromatic polynomial of planar multigraphs, J

    P. Martin, Remarkable valuation of the dichromatic polynomial of planar multigraphs, J. Combin. Theory Ser. B24(1978), 318–324

    work page 1978

  21. [21]

    (2024), The On-Line Encyclopedia of Integer Sequences, Published elec- tronically athttps://oeis.org

    OEIS Foundation Inc. (2024), The On-Line Encyclopedia of Integer Sequences, Published elec- tronically athttps://oeis.org

    work page 2024

  22. [22]

    Simion, Noncrossing partitions,Discrete Math.217(2000), 367–409

    R. Simion, Noncrossing partitions,Discrete Math.217(2000), 367–409

    work page 2000

  23. [23]

    T. R. S. Walsh, Hypermaps versus bipartite maps,J. Combinatorial Theory Ser. B18(1975), 155–163. 32 ROBERT CORI AND G ´ABOR HETYEI

    work page 1975

  24. [24]

    D. Welsh, The Tutte polynomial, in: Statistical physics methods in discrete probability, combi- natorics, and theoretical computer science (Princeton, NJ, 1997).Random Structures Algorithms 15(1999), 210–228. Labri, Universit´e Bordeaux 1, 33405 Talence Cedex, France. WWW:http://www.labri.fr/perso/cori/. Department of Mathematics and Statistics, UNC Charl...

    work page 1997

  25. [25]

    WWW:http://webpages.uncc.edu/ghetyei/

    work page