Construction of simplicial complexes with prescribed degree-size sequences

Area of Science:

• Network Science
• Computational Topology
• Discrete Mathematics

Background:

• Simplicial complexes are fundamental structures in network science and topology.
• Understanding the realizability of simplicial complexes from degree and facet size distributions is crucial for network generation and analysis.
• The computational complexity of the s-uniform variant (s≥3) is known to be NP-complete.

Purpose of the Study:

• To investigate the realizability of simplicial complexes given specific node degree and facet size distributions.
• To develop efficient algorithms for constructing simplicial complexes from these distributions.
• To explore the relationship between node degrees and the number of loops in simplicial complexes.

Main Methods:

• Developed a novel recursive algorithm to solve the simplicial complex realizability problem.
• Utilized a sampler for the simplicial configuration model to generate simplicial ensembles.
• Analyzed the impact of varying node degree distributions on the resulting complex structures.

Main Results:

• Identified two populations of input sequences for which realizability can be determined in polynomial time.
• Demonstrated efficient sampling of simplicial ensembles from arbitrary degree and size distributions.
• Found that increasing node degrees unexpectedly decreases the number of loops in simplicial complexes, contrary to dyadic network expectations.

Conclusions:

• The study presents a significant advancement in constructing and analyzing simplicial complexes.
• A fundamental constraint relating degree and size sequences in simplicial complexes has been uncovered.
• The findings provide a basis for further research into higher-order phenomena and local structures in complex networks.