pith. sign in

arxiv: 2604.05921 · v1 · submitted 2026-04-07 · 🧮 math.PR · math.CO

Simplicity of random hypergraphs

Yanna J. Kraakman , Clara Stegehuis This is my paper

Pith reviewed 2026-05-10 19:24 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random hypergraphsconfiguration modelself-loopsmulti-hyperedgesdegenerate hyperedgesasymptoticsdegree distributionsimplicity
0
0 comments X

The pith

Random hypergraphs generated by the configuration model have vanishing expected fractions of self-loops, multi-hyperedges, and degenerate hyperedges as the number of vertices grows.

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

The paper derives exact formulas for the expected counts of self-loops, multi-hyperedges, and degenerate hyperedges in both undirected and directed hypergraphs built from prescribed degree sequences. It then proves that these counts become negligible relative to the total number of hyperedges when the degree distribution meets mild moment conditions and the system size increases. A sympathetic reader would care because the result justifies treating large random hypergraphs as simple objects, just as one does for ordinary graphs, and supplies the precise expressions needed to check this for any finite instance.

Core claim

We derive exact, explicit expressions for the expected number of self-loops, multi-hyperedges and degenerate hyperedges in the configuration model for undirected and directed hypergraphs with prescribed vertex and hyperedge degrees. An asymptotic analysis shows that, under mild moment conditions on the degree distribution, the expected fraction of self-loops, multi-hyperedges and degenerate hyperedges vanishes as the number of vertices grows.

What carries the argument

The configuration model that pairs vertex stubs with hyperedge stubs according to given degree sequences, together with direct combinatorial counting of the events that produce self-loops, repeated vertices within an edge, or repeated edges.

If this is right

  • Exact closed-form expectations let one compute the precise probability of simplicity for any finite hypergraph instance without simulation.
  • The asymptotic vanishing result applies uniformly to both directed and undirected cases once the moment condition holds.
  • The same counting technique yields the expected number of any fixed-size forbidden subconfiguration, not only the three named defects.
  • Models that first generate a configuration-model hypergraph and then remove defects incur vanishing relative error for large systems.

Where Pith is reading between the lines

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

  • The vanishing result supplies a rigorous justification for using the configuration model as a null model when testing for higher-order motifs in empirical hypergraphs.
  • If an observed hypergraph has degree moments that satisfy the paper's condition, any excess of self-loops or multiples beyond the predicted expectation signals a structural deviation rather than a sampling artifact.
  • The same moment conditions that guarantee simplicity may also guarantee concentration of other global statistics, such as the number of connected components.

Load-bearing premise

The degree distribution has finite moments of sufficiently high order so that the second-moment calculations remain controlled.

What would settle it

A family of degree sequences whose second (or higher) moment grows fast enough with system size that the expected fraction of degenerate hyperedges stays bounded away from zero even as the number of vertices tends to infinity.

Figures

Figures reproduced from arXiv: 2604.05921 by Clara Stegehuis, Yanna J. Kraakman.

Figure 1
Figure 1. Figure 1: Illustration of the studied statistics on both an undirected and a directed hypergraph. In the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
read the original abstract

Random hypergraphs extend the classical notion of random graphs by allowing hyperedges to join more than two vertices, making them well-suited for modeling higher-order interactions in complex systems. Despite their broad applicability, many structural properties of random hypergraphs remain less understood than in the graph setting. One such property is simplicity: the absence of self-loops, multi-hyperedges, and, in the hypergraph context, degenerate hyperedges where hyperedges contain a copy of the same vertex at least twice. While the behaviour of the number of such self-loops and multi-hyperedges is well understood for random graphs through the configuration model, analogous results for hypergraphs are comparatively sparse. In this work, we study both undirected and directed hypergraphs generated by the configuration model with prescribed vertex and hyperedge degrees. We derive exact, explicit expressions for the expected number of self-loops, multi-hyperedges and degenerate hyperedges, extending classical results from the graph setting. In addition, an asymptotical analysis shows that, under mild moment conditions on the degree distribution, the expected fraction of self-loops, multi-hyperedges and degenerate hyperedges vanishes as the number of vertices grows. Our results provide a systematic understanding of simplicity in directed and undirected hypergraph models.

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 configuration model for both undirected and directed random hypergraphs with prescribed vertex and hyperedge degree sequences. It derives exact closed-form expressions for the expected number of self-loops, multi-hyperedges, and degenerate hyperedges (where a hyperedge repeats a vertex), extending the classical graph case via linearity of expectation on the stub-matching process. It then shows that, under mild moment conditions on the degree distribution, the expected fraction of these non-simple structures vanishes as the number of vertices n tends to infinity.

Significance. If the derivations are correct, the work supplies a direct and useful hypergraph analogue of the well-known configuration-model results on graph simplicity. The explicit expectations enable precise finite-n calculations, while the asymptotic vanishing result (under moment conditions) justifies treating large random hypergraphs as simple in applications to higher-order network modeling. The manuscript provides closed-form expressions rather than relying solely on simulations or indirect arguments, which strengthens its utility.

major comments (2)
  1. [§3] §3 (exact expectations): The derivation of the expected number of degenerate hyperedges appears to rely on counting the ways a single hyperedge can repeat vertices in its stub assignment. It would be helpful to see an explicit indicator-variable argument or combinatorial count that parallels the self-loop and multi-edge cases, to confirm it is not simply asserted by analogy.
  2. [§4] §4 (asymptotics): The vanishing result is stated under 'mild moment conditions' on the degree distribution. Because this condition is load-bearing for the o(1) claim on the fraction of degeneracies, the precise moment requirement (e.g., finite second moment of the vertex-degree distribution, or a uniform bound on the maximum degree) should be stated explicitly in the theorem statement rather than left as 'mild'.
minor comments (2)
  1. [Introduction / §2] The abstract and introduction use 'degenerate hyperedges' without an immediate formal definition; a one-sentence definition in the model section would improve readability.
  2. [§2] Notation for the hyperedge-size sequence and the total number of stubs should be introduced once and used consistently; currently the symbols for total stubs appear to vary between the directed and undirected cases.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and constructive suggestions. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (exact expectations): The derivation of the expected number of degenerate hyperedges appears to rely on counting the ways a single hyperedge can repeat vertices in its stub assignment. It would be helpful to see an explicit indicator-variable argument or combinatorial count that parallels the self-loop and multi-edge cases, to confirm it is not simply asserted by analogy.

    Authors: We agree that greater explicitness would strengthen the presentation. The derivation in §3 proceeds via linearity of expectation applied to indicator random variables I_e for each hyperedge e being degenerate (i.e., containing at least one repeated vertex in its stub assignment). The probability P(I_e=1) is obtained by enumerating the ways to assign the d_e stubs of e such that at least two land on the same vertex, which is a direct combinatorial count parallel to the self-loop (pairing two stubs of the same vertex) and multi-hyperedge (pairing stubs across distinct hyperedges) cases. In the revised manuscript we will expand this paragraph to write out the indicator definition, the exact expression for P(I_e=1) in terms of the degree sequence, and the subsequent summation, removing any appearance of analogy. revision: yes

  2. Referee: [§4] §4 (asymptotics): The vanishing result is stated under 'mild moment conditions' on the degree distribution. Because this condition is load-bearing for the o(1) claim on the fraction of degeneracies, the precise moment requirement (e.g., finite second moment of the vertex-degree distribution, or a uniform bound on the maximum degree) should be stated explicitly in the theorem statement rather than left as 'mild'.

    Authors: We accept the point. The proof of the asymptotic vanishing (Theorem 4.1) relies on the vertex-degree distribution having finite second moment, which controls the second-moment calculations in the expectation of the total number of degeneracies and ensures the o(1) bound after normalization by n. In the revised manuscript we will replace the phrase 'mild moment conditions' in both the abstract and the theorem statement with the explicit requirement 'assuming the vertex-degree distribution has finite second moment', and we will add a brief remark in the proof sketch indicating where this moment is used. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivations consist of direct applications of linearity of expectation to indicator variables over the stub-matching process in the configuration model, yielding exact closed-form expressions for the expected counts of self-loops, multi-hyperedges and degenerate hyperedges. The asymptotic vanishing result follows from standard moment conditions on the degree sequence that make collision probabilities vanish, exactly as in the classical graph configuration model. No load-bearing self-citations, fitted parameters renamed as predictions, self-definitional steps, or imported uniqueness theorems appear; the central claims are self-contained first-principles calculations from the model definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on the standard definition of the configuration model for hypergraphs and basic probabilistic counting arguments; no new free parameters are introduced or fitted, and no new entities are postulated.

axioms (2)
  • domain assumption The configuration model for hypergraphs with prescribed vertex and hyperedge degrees generates a uniform random hypergraph among those with the given degree sequence.
    This is the foundational modeling assumption invoked throughout the abstract.
  • domain assumption Standard moment conditions on the degree distribution suffice for the law of large numbers or concentration arguments used in the asymptotic analysis.
    Invoked for the vanishing-fraction result.

pith-pipeline@v0.9.0 · 5517 in / 1298 out tokens · 55022 ms · 2026-05-10T19:24:10.990647+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

3 extracted references · 3 canonical work pages

  1. [1]

    (2) Janson, S.Combinatorics, Probability and Computing2009,18, 205–225

    (1) Bollobás, B.European Journal of Combinatorics1980,1, 311–316. (2) Janson, S.Combinatorics, Probability and Computing2009,18, 205–225. (3) Angel, O.; Hofstad, R.; Holmgren, C.Annales de l’Institut Henri Poincaré, Probabilités et Statis- tiques2016,55, DOI:10.1214/18-AIHP926. (4) Molloy, M.; Reed, B.Random Structures & Algorithms1995,6, 161–180. (5) Van...

    work page doi:10.1214/18-aihp926

  2. [2]

    S.Journal of Complex Networks2020,8, cnaa018

    (6) Chodrow, P. S.Journal of Complex Networks2020,8, cnaa018. (7) Kraakman, Y.; Stegehuis, C.J. Complex Netw.2025. (8) Ascolese, M.; Lienau, M.; Schulte, M.; Taraz, A.arXiv preprint arXiv:2402.047372024. (9) Abuissa, M.; Riondato, M.; Upfal, E. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases, 2025, pp 57–74. (10) Kraak...

    work page arXiv 2025

  3. [3]

    (16) Miyashita, R.; Hironaka, S.; Shudo, K.arXiv preprint arXiv:2410.237992024

    (15) Ha, G.-G.; Neri, I.; Annibale, A.Chaos2024,34, DOI:10.1063/5.0188246. (16) Miyashita, R.; Hironaka, S.; Shudo, K.arXiv preprint arXiv:2410.237992024. (17) Purkait, P.; Chin, T.-J.; Ackermann, H.; Suter, D. InProceedings of the International Conference on Computer Vision,

    work page doi:10.1063/5.0188246