• Letter

Construction of simplicial complexes with prescribed degree-size sequences

Tzu-Chi Yen
Phys. Rev. E 104, L042303 – Published 28 October 2021
PDFHTMLExport Citation

Abstract

We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and the facet size distribution, respectively. While the s-uniform variant of the problem is NP-complete when s3, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [J.-G. Young et al., Phys. Rev. E 96, 032312 (2017)], we facilitate the efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing the nodes' degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analyses of higher-order phenomena based on local structures.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 31 May 2021
  • Accepted 30 September 2021

DOI:https://doi.org/10.1103/PhysRevE.104.L042303

©2021 American Physical Society

Physics Subject Headings (PhySH)

NetworksInterdisciplinary Physics

Authors & Affiliations

Tzu-Chi Yen*

  • Department of Computer Science, University of Colorado, Boulder, Colorado 80309, USA

  • *tzuchi.yen@colorado.edu

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 104, Iss. 4 — October 2021

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×