Enumeration of interval graphs and d-representable complexes

2022/03/22 by Bukh, Boris, R. Amzi Jeffs, Jeffs, R. Amzi
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Markov Chains and Monte Carlo Methods #Advanced Combinatorial Mathematics

paper · pdf · doi:10.48550/arxiv.2203.12063

Abstract

For each fixed d≥ 1, we obtain asymptotic estimates for the number of d-representable simplicial complexes on n vertices as a function of n. The case d=1 corresponds to counting interval graphs, and we obtain new results in this well-studied case as well. Our results imply that the d-representable complexes comprise a vanishingly small fraction of d-collapsible complexes.

Related

• Generalizations of interval and proper interval graphs for simplicial complexes
• Representability and boxicity of simplicial complexes
• A lower bound on the number of homotopy types of simplicial complexes on n vertices
• On the Complexity of Embeddable Simplicial Complexes
• Large Simple d-Cycles in Simplicial Complexes