Universal Strict Lifting (Hypergraph to Combinatorial)

In this PR we introduce a lifting from hypergraphs to combinatorial complexes which is universal with respect to a property (strictness) in the sense of category theory.

The Universal Strict Lifting does not introduce extra cells: every cell in the lifted CC corresponds to a hyperedge in the original hypergraph. Combinatorial complexes carry more information than hypergraphs, in the form of a rank function taking nonnegative values on each cell, satisfying a topological requirement (see [1]). The Universal Strict Lifting provides such a rank function in a deterministic manner.

Universality

Denote the categories* $$\mathrm{Hyper} := (\text{hypergraphs}, \text{hypergraph homomorphisms})$$ $$\mathrm{CC}:= (\text{Combinatorial complexes}, \text{CC-homomorphisms})$$

Let $\mathrm{CC^{\mathrm{strict}}}$ consist of the (full) subcategory of $\mathrm{CC}$ consisting of combinatorial complexes where the rank condition is strict, that is:

$$\text{If cells } x,y \text{ satisfy } x\subseteq y\text{ then }\mathrm{rk}(x)<\mathrm{rk}(y)$$

We note that the strict category naturally contains the category of cell and simplicial complexes, where the dimensions of the cells provide the ranks.

The simplest nontrivial example is the comparison of a square (2-cell) and a tetrahedron (3-cell), both of which have the same number of nodes. See the tutorial for details on the implementation.

*: A hypergraph homomorphism is a mapping of the nodes that sends hyperedges to hyperedges and respects hyperedge inclusions. See [1] for definitions about CCs.

Universal property of the Universal Strict Lifting

Theorem: Let $$\mathcal{L}: \mathrm{Hyper} \rightarrow \mathrm{CC^{\mathrm{strict}}} \text{ be \textbf{any} lifting which respects homomorphisms}$$

$$\mathcal{U}: \mathrm{Hyper} \rightarrow \mathrm{CC^{\mathrm{strict}}} \text{ be the Universal Strict lifting}$$

Then there exists a homomorphism-preserving $\mathcal{F} : \mathrm{CC^{\mathrm{strict}}} \rightarrow \mathrm{CC^{\mathrm{strict}}}$ such that $\mathcal{L} = \mathcal{F} \circ \mathcal{U}$.

In other words, we can express any lifting from hypergraphs to strict CCs as a composition of our universal lifting with something else. This implies that $\mathcal{U}$ introduces the strictly necessary information needed to obtain a combinatorial complex in $\mathrm{CC}^{\mathrm{strict}}$.

From https://github.com/pyt-team/challenge-icml-2024/pull/47