pith. sign in

arxiv: 2408.12874 · v2 · submitted 2024-08-23 · 🧮 math.CO

Enumeration of dihypergraphs with specified degrees and edge types

Catherine Greenhill , Tam\'as Makai This is my paper

Pith reviewed 2026-05-23 21:58 UTC · model grok-4.3

classification 🧮 math.CO
keywords dihypergraphsdirected hypergraphsasymptotic enumerationdegree sequenceshyperarc typesconfiguration modelcombinatorial counting
0
0 comments X

The pith

Asymptotic formulae count directed hypergraphs with given in-degree and out-degree sequences together with fixed head and tail sizes on every hyperarc.

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

The paper supplies asymptotic expressions for the number of dihypergraphs whose hyperarcs have prescribed head and tail cardinalities and whose vertices have prescribed in-degrees and out-degrees. These counts matter because dihypergraphs serve as models for chemical reaction networks and relational databases, where exact enumeration quickly becomes intractable. The expressions are valid once the largest out-degree, in-degree, head size and tail size remain bounded relative to the overall size of the structure. A reader would therefore obtain reliable estimates for the size of the space of such objects without enumerating them directly. The work extends classical configuration-model counting arguments from graphs and ordinary hypergraphs to this directed, typed setting.

Core claim

When the maximum out-degree, maximum in-degree, maximum head size and maximum tail size are all sufficiently small, the number of dihypergraphs realizing a given pair of degree sequences and a given sequence of head-tail sizes is asymptotically equal to the number of configurations divided by the product of the appropriate factorials that account for the labeling of heads and tails within each hyperarc.

What carries the argument

The configuration model for dihypergraphs with fixed arc types, whose asymptotic count is obtained by dividing the number of perfect matchings in an auxiliary bipartite graph by the product of factorials for head and tail permutations.

If this is right

  • The size of the space of chemical reaction networks with prescribed reaction arities and species degrees can be estimated without exhaustive search.
  • The number of relational database schemas with given arity constraints and participation degrees becomes accessible for large instances.
  • Random generation of dihypergraphs with the stated constraints can be performed with known success probability in the bounded-parameter regime.
  • Comparisons between observed dihypergraphs and the uniform model become feasible once the asymptotic count is known.

Where Pith is reading between the lines

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

  • The same configuration-model approach may extend to dihypergraphs whose head and tail sizes are drawn from a fixed finite set rather than fixed individually.
  • The formulae could be used to analyze the threshold for the appearance of certain substructures inside random dihypergraphs under these degree constraints.
  • If the boundedness condition is relaxed, one might still obtain logarithmic asymptotics by combining the present estimates with large-deviation techniques.

Load-bearing premise

The largest out-degree, in-degree, head size and tail size must all stay bounded or grow slowly enough that the usual error terms in the configuration-model analysis remain negligible.

What would settle it

An exact enumeration for a family of instances in which one of the four parameters grows linearly with the number of vertices, showing that the proposed asymptotic expression deviates from the true count by more than a constant factor.

Figures

Figures reproduced from arXiv: 2408.12874 by Catherine Greenhill, Tam\'as Makai.

Figure 1
Figure 1. Figure 1: The dihypergraph H (left) corresponds to the bipartite pair (G+, G−) (right). A pair of bipartite graphs (G+, G−) is called a bipartite pair if W+ ∩W− = ∅. Each bipar￾tite pair (G+, G−) which satisfies (1.3) uniquely defines an edge-labelled directed hypergraph by letting e + = NG+ (e) and e − = NG− (e) for all e ∈ E. See [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The edge sequence generation algorithm, Algorithm [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

A directed hypergraph (dihypergraph) consists of a set of vertices and a set of hyperarcs, where each hyperarc is partitioned into a head and a tail. Directed hypergraphs are useful in many applications, including the study of chemical reactions or relational databases. We provide asymptotic formulae for the number of directed hypergraphs with given in-degree sequence, out-degree sequence, and with the head and tail sizes of all hyperarcs specified. Our formulae hold when none of the following parameters are too large: the maximum out-degree, the maximum in-degree, the maximum head size and the maximum tail size.

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

0 major / 3 minor

Summary. The manuscript derives asymptotic formulae for the number of directed hypergraphs (dihypergraphs) with prescribed in-degree and out-degree sequences together with fixed head and tail sizes on every hyperarc. The formulae are obtained via a configuration-model argument whose error terms are controlled precisely when the maximum out-degree, maximum in-degree, maximum head size and maximum tail size remain bounded (or grow sufficiently slowly).

Significance. If the main theorem holds, the work supplies a concrete counting tool for directed hypergraphs that appears in applications such as chemical reaction networks and relational databases. The explicit statement of the boundedness hypothesis together with the configuration-model derivation and error analysis constitute a clear, falsifiable contribution to the enumeration literature.

minor comments (3)
  1. [Abstract] The abstract states the boundedness condition but does not display the leading-term expression; adding the explicit main-term formula would improve readability.
  2. Notation for the degree sequences and the head/tail-size vector is introduced only after the configuration model is defined; a short preliminary section collecting all parameters would help.
  3. [Main Theorem] The error-term analysis is referenced to the boundedness hypothesis, but the precise growth rate permitted for the maxima (e.g., o(log n) versus O(1)) is not restated in the statement of the main theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were listed in the report, so there are no specific points requiring a point-by-point response or manuscript changes at this stage.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives asymptotic enumeration formulae for dihypergraphs with prescribed in/out-degree sequences and fixed head/tail sizes via a configuration-model argument whose error terms are controlled under the stated boundedness hypotheses on maximum degrees and part sizes. This is a standard, self-contained analytic derivation that does not reduce any claimed prediction to a fitted parameter, self-citation, or definitional tautology; the central result is obtained directly from the model rather than presupposed by it. No load-bearing step matches any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger records the single explicit domain assumption stated there; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption The formulae hold when the maximum out-degree, maximum in-degree, maximum head size and maximum tail size are not too large.
    This boundedness condition is required for the asymptotic formulae to apply, as stated in the abstract.

pith-pipeline@v0.9.0 · 5623 in / 1152 out tokens · 32278 ms · 2026-05-23T21:58:40.243694+00:00 · methodology

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

25 extracted references · 25 canonical work pages

  1. [1]

    Ausiello and L

    G. Ausiello and L. Laura, Directed hypergraphs: Introduction a nd fundamental algo- rithms – A survey, Theoretical Computer Science 658 (2017), 293–306

    work page 2017

  2. [2]

    Barvinok, On the number of matrices and a random matrix with p rescribed row and column sums and 0–1 entries, Advances in Mathematics 224 (2010), 316–339

    A. Barvinok, On the number of matrices and a random matrix with p rescribed row and column sums and 0–1 entries, Advances in Mathematics 224 (2010), 316–339

    work page 2010

  3. [3]

    Bayati, J.-H

    M. Bayati, J.-H. Kim and A. Saberi, A sequential algorithm for gene rating random graphs, Algorithmica 58 (2010), 860–910

    work page 2010

  4. [4]

    A. R. Berg, B. Jackson and T. Jord´ an, Edge splitting and conne ctivity augmentation in directed hypergraphs, Discrete Mathematics 273 (2003), 71–84

    work page 2003

  5. [5]

    J. H. Blanchet, Efficient importance sampling for binary contingen cy tables, Annals of Applied Probability 19 (2009), 949–982

    work page 2009

  6. [6]

    Bodkin, A

    C. Bodkin, A. Liebenau and I. M. Wanless, Most binary matrices ha ve no small defining set, Discrete Mathematics 343 (2020), 112035

    work page 2020

  7. [7]

    Y. Chen, P. Diaconis, S. P. Holmes and J. S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, Journal of the American Statistical Association 100 (2005), 109–120

    work page 2005

  8. [8]

    Estrada and J

    E. Estrada and J. Rodr ´ ıguez-Vel´ azquez, Subgraph centrality and clustering in complex hyper-networks, Physica A 364 (2006), 581–594

    work page 2006

  9. [9]

    Ferber, M

    A. Ferber, M. Kwan, B. Narayanan, A. Sah and M. Sawhney, Frie ndly bisections of random graphs, Communications of the American Mathematical Society 2 (2022), 380– 416

    work page 2022

  10. [10]

    Frank, T

    A. Frank, T. Kir´ aly and Z. Kir´ aly, On the orientation of graphs and hypergraphs, Discrete Applied Mathematics 131 (2003), 385–400. 28

    work page 2003

  11. [11]

    Gallo, G

    G. Gallo, G. Longo, S. Pallottino and S. Nguyen, Directed hyperg raphs and applications, Discrete Applied Mathematics 42 (1993), 177–201

    work page 1993

  12. [12]

    Garcia-Chung, M

    A. Garcia-Chung, M. Berm´ udez-Monta˜ na, P. F. Stadler, J. Jost and G. Restrepo, Chemically-inspired Erd˝ os–R´ enyi hypergraphs,Journal of Mathematical Chemistry 62 (2024), 1357–1383

    work page 2024

  13. [13]

    Greenhill and B

    C. Greenhill and B. D. McKay, Random dense bipartite graphs an d directed graphs with specified degrees, Random Structures & Algorithms 35 (2009), 222–249

    work page 2009

  14. [14]

    Janson, T

    S. Janson, T. /suppress Luczak and A. Ruci´ nski,Random Graphs, Wiley, New York, 2000

    work page 2000

  15. [15]

    Klamt, U.-U

    S. Klamt, U.-U. Haus and F. Theis, Hypergraphs and cellular netw orks, PLoS Compu- tational Biology 5 (2009), e1000385

    work page 2009

  16. [16]

    Kraakman and C

    Y. Kraakman and C. Stegehuis, Configuration models for rando m directed hypergraphs, Preprint. arXiv:2402.06466

    work page arXiv

  17. [17]

    Liebenau and N

    A. Liebenau and N. Wormald, Asymptotic enumeration of digraph s and bipartite graphs by degree sequence, Random Structures & Algorithms 62 (2023), 259–286

    work page 2023

  18. [18]

    B. D. McKay, Personal communication, 2024

    work page 2024

  19. [19]

    B. D. McKay, Asymptotics for 0-1 matrices with prescribed line s ums, in Enumeration and Design , Academic Press, 1984, 225–238

    work page 1984

  20. [20]

    B. D. McKay, Subgraphs of random graphs with specified degre es, Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) . (2011) pp. 2489–2501

    work page 2010

  21. [21]

    Milenkovic, E

    O. Milenkovic, E. Soljanin and P. Whiting, Asymptotic spectra of t rapping sets in regular and irregular LDPC code ensembles, IEEE Transactions on Information Theory 53 (2007), 39–55

    work page 2007

  22. [22]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis , Cambridge University Press, Cambridge, 2005

    work page 2005

  23. [23]

    H. Moon, H. Kim, S. Kim and K. Shin, Four-set hypergraphlets fo r characterization of directed hypergraphs, Preprint. arxiv:2311.14289

    work page arXiv

  24. [24]

    Qian, Enumeration of unlabelled directed hypergraphs, Electronic Journal of Com- binatorics 20(1) (2013), #P.46

    J. Qian, Enumeration of unlabelled directed hypergraphs, Electronic Journal of Com- binatorics 20(1) (2013), #P.46

    work page 2013

  25. [25]

    Thakur and R

    M. Thakur and R. Tripathyi, Linear connectivity problems in direc ted hypergraphs, Theoretical Computer Science 410 (2009), 2592–2618. 29

    work page 2009