Skip to content

Hypergraph Properties

Beyond hypergraph traversals, the HGL algorithms module provides a suite of lightweight, functional utilities to evaluate the global structural properties of a hypergraph. These algorithms allow you to quickly determine bounds, uniformity, and regularity across the topology.

These algorithms are grouped into four primary categories:

  • Vertex Degree Bounds: Functions for evaluating the minimum and maximum connectivity of vertices.
  • Hyperedge Size Bounds: Functions for evaluating the scale of hyperedges (Rank and Corank).
  • Regularity: Functions to check if all vertices share the same degree.
  • Uniformity: Functions to check if all hyperedges contain the same number of vertices.

Algorithmic Complexity

All property algorithms in this module operate by requesting a degree_map() or hyperedge_size_map() from the underlying hypergraph structure, and then performing a linear \(\mathcal{O}(N)\) reduction (like std::ranges::max_element or a constant-check loop). Thus, the actual performance of these algorithms is entirely dictated by the complexity of generating the size/degree map, which varies depending on your chosen Representation Layout.

Vertex Degree Bounds

These functions evaluate the minimum and maximum degrees present within the hypergraph.

Formal Definitions

For an undirected hypergraph \(H = (V, E)\):

  • Maximum Degree \(\Delta(H)\): The largest degree of any vertex in the hypergraph. \(\Delta(H) = \max\limits_{v \in V} deg(v)\)
  • Minimum Degree \(\delta(H)\): The smallest degree of any vertex in the hypergraph. \(\delta(H) = \min\limits_{v \in V} deg(v)\)

For BF-directed hypergraphs, these concepts are further split into in-degree (the number of incoming/head hyperedges) and out-degree (the number of outgoing/tail hyperedges).

Available Functions

Undirected & Directed (Total Degree):

BF-Directed Specifically:

Note: If the hypergraph is empty, these functions safely return 0.

Hyperedge Size Bounds (Rank & Corank)

Unlike standard graphs where all edges have a size of exactly 2, hyperedges can encompass any number of vertices. The bounds of these sizes define the hypergraph's Rank and Corank.

Formal Definitions

For an undirected hypergraph \(H = (V, E)\):

  • Rank \(r(H)\): The maximum size (cardinality) of any hyperedge in the hypergraph. \(r(H) = \max\limits_{e \in E} |e|\)
  • Corank \(cr(H)\): The minimum size (cardinality) of any hyperedge in the hypergraph. \(cr(H) = \min\limits_{e \in E} |e|\)

Available Functions

Undirected & Directed (Total Size):

BF-Directed Specifically:

Regularity

A hypergraph is evaluated based on the consistency of its vertices' connectivity.

Formal Definitions

  • \(k\)-Regular: A hypergraph \(H\) is \(k\)-regular if every vertex \(v \in V\) is incident to exactly \(k\) hyperedges: \((\forall v \in V)(deg(v) = k)\)
  • Regular: A hypergraph is structurally regular if there exists some integer \(k\) such that the hypergraph is \(k\)-regular (i.e., all vertices have the exact same degree): \((\exists k \in \mathbb{N})(\forall v \in V)(deg(v) = k)\)

Available Functions

Undirected & Directed (Total Degree):

BF-Directed Specifically:

Uniformity

A hypergraph is evaluated based on the consistency of its hyperedges' sizes.

Formal Definitions

  • \(k\)-Uniform: A hypergraph \(H\) is \(k\)-uniform if every hyperedge \(e \in E\) contains exactly \(k\) vertices: \((\forall e \in E)(|e| = k)\) Note: A 2-uniform undirected hypergraph is equivalent to a standard undirected graph.
  • Uniform: A hypergraph is structurally uniform if there exists some integer \(k\) such that the hypergraph is \(k\)-uniform (i.e., all hyperedges have the exact same size): \((\exists k \in \mathbb{N})(\forall e \in E)(|e| = k)\)

Available Functions

Undirected & Directed (Total Size):

BF-Directed Specifically: