Dense, irregular, yet always graphic $3$-uniform hypergraph degree sequences

Runze Li, István Miklós

TL;DR

While determining if a sequence of numbers can represent the degrees of a 3-uniform hypergraph is generally a "hard" (NP-complete) problem, this paper identifies a specific "sweet spot." The authors provide the first polynomial-time algorithm to construct realizations for dense, highly irregular degree sequences, proving that as long as the degrees fall within a specific quadratic range and satisfy a basic divisibility rule, a solution is guaranteed to exist.

What Problem Does This Paper Address?

In graph theory, the degree sequence problem asks: "Given a list of integers, can we build a graph where each vertex has exactly that many connections?" For simple graphs (where edges connect two nodes), this was solved decades ago with efficient algorithms like Havel-Hakimi.

However, the world gets much messier with hypergraphs, where a single "hyperedge" can connect three or more nodes. In a 3-uniform hypergraph, every edge connects exactly three vertices. Deciding if a degree sequence has a 3-uniform realization is NP-complete—meaning there is likely no general efficient algorithm. Until now, polynomial-time solutions only existed for very narrow cases, such as sequences where all degrees are nearly identical (regular) or very small (sparse). This paper tackles the "dense and irregular" gap: sequences where vertices have many connections ($\Omega(n^2)$) and the difference between the most and least connected nodes is large.

Methods

The authors employ a constructive proof strategy, meaning they don't just prove a solution exists; they provide a recipe to build it. Their approach relies on several key techniques:

  1. Tripartite Reduction: The core of the algorithm involves transforming a general degree sequence problem into a tripartite hypergraph problem. A tripartite hypergraph is one where vertices are split into three groups, and every edge must take exactly one vertex from each group.
  2. Hinge Flip Operations: The authors use "hinge flips"—local swaps that change the degrees of two vertices by 1 while keeping others constant. They prove that if a "base" sequence is graphic, any sequence reachable via "balancing" hinge flips is also graphic.
  3. Four-Phase Construction: To realize a general sequence $D$, the algorithm proceeds in stages:
  4. Phase 1: Handle "extra" vertices to ensure the remaining vertex count is divisible by 3.
  5. Phase 2: Distribute vertices into three classes and swap degrees between classes until their sums are nearly equal.
  6. Phase 3: Use hyperedges contained entirely within a single class to perfectly equalize the degree sums across the three classes.
  7. Phase 4: Apply a specialized algorithm for tripartite sequences to finish the construction.

Datasets

Not discussed in the paper. As a theoretical work in combinatorics and algorithmic graph theory, the paper relies on mathematical proofs and complexity analysis rather than empirical testing on external datasets.

Key Insights and Ideas

  • Density as an Advantage: Counter-intuitively, high density makes the problem easier. When a hypergraph is dense, there are so many possible edges that "local" adjustments (like hinge flips) are almost always possible without running into constraints.
  • The "Handshaking" Constraint: For a 3-uniform hypergraph, the sum of all degrees must be divisible by 3 (since each edge adds 1 to the degree of 3 different vertices). The authors show that for their specific range, this is the only global constraint needed.
  • Bridging the Gap: The authors successfully bridged the gap between highly structured tripartite hypergraphs and general hypergraphs by showing that a small number of "non-tripartite" edges can "tailor" any valid sequence into a tripartite one.

Key Results

  • The "Always Graphic" Range: The paper proves that any sequence $D$ is graphic if the number of vertices $n \ge 45$, the degree sum is divisible by 3, and every degree $d_i$ satisfies: $$\frac{2n^2}{63} + O(n) \le d_i \le \frac{5n^2}{63} - O(n)$$
  • Efficiency: The construction is guaranteed to run in polynomial time relative to the number of vertices.
  • Irregularity: Unlike previous work that required degrees to be very close to each other, this result allows for a "highly irregular" spread—the difference between the maximum and minimum degree can be as large as $\approx \frac{3n^2}{63}$.

Limitations and Future Work

  • Tightness of Bounds: The authors acknowledge that the range $[\frac{2}{63}n^2, \frac{5}{63}n^2]$ is likely not the absolute limit. They propose a conjecture that the true "always graphic" range is wider, potentially spanning from approximately $0.27n^2$ to $0.72n^2$.
  • Small $n$: The proof requires $n \ge 45$. While this is a constant, the behavior of very small hypergraphs remains an area for manual investigation or different proof techniques.
  • Higher Uniformity: The paper focuses strictly on 3-uniform hypergraphs. Extending these constructive polynomial-time algorithms to $k$-uniform hypergraphs (where $k > 3$) remains an open and significantly more complex challenge.

Summary updated

Abstract

A $3$-uniform hypergraph is a generalization of simple graphs where each hyperedge is a subset of vertices of size $3$. The degree of a vertex in a hypergraph is the number of hyperedges incident with it. The degree sequence of a hypergraph is the sequence of the degrees of its vertices. The degree sequence problem for $3$-uniform hypergraphs is to decide if a $3$-uniform hypergraph exists with a prescribed degree sequence. Such a hypergraph is called a realization. Recently, Deza \emph{et al.} proved that the degree sequence problem for $3$-uniform hypergraphs is NP-complete. Some special cases are easy; however, polynomial algorithms have been known so far only for some very restricted degree sequences. The main result of our research is the following. If all degrees are between $\frac{2n^2}{63}+O(n)$ and $\frac{5n^2}{63}-O(n)$ in a degree sequence $D$, further, the number of vertices is at least $45$, and the degree sum can be divided by $3$, then $D$ has a $3$-uniform hypergraph realization. Our proof is constructive and in fact, it constructs a hypergraph realization in polynomial time for any degree sequence satisfying the properties mentioned above. To our knowledge, this is the first polynomial running time algorithm to construct a $3$-uniform hypergraph realization of a highly irregular and dense degree sequence.
BibTeX
@misc{li2023dense,
  author = {Runze Li and István Miklós},
  title = {{Dense, irregular, yet always graphic $3$-uniform hypergraph degree sequences}},
  year = {2023},
  eprint = {2312.00555},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.00555},
}
Figure