Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be useful. To be precise, I am referring to polyhedra and their higher-dimensional analogues. Might mathematicians have developed such a concept?

One idea that occurred to me was to use the number of Hamiltonian cycles. If the polytope is embedded in $\mathbb{R}^3$ this allows us to ask questions such as how many polytopes with distinct topology with $n$ vertices have less than $\lambda n!$ Hamiltonian cycles where $\lambda \in [0,1]$.

Another way of approaching this might be to think about compression algorithms and Kolmogorov Complexity. However, I haven't found much work applying notions of algorithmic complexity to problems in topology.


Ginestra Bianconi and Kartik Anand have formulated a more general problem: the challenge of defining an entropy measure for complex networks [3]. This problem is motivated in [3] as follows:

Following ten years of active research in the field of complex networks, the state of the art includes, a deep understanding of their evolution , an unveiling of the rich interplay between network topology and dynamics and a description of networks through structural characteristics. Nevertheless, we still lack the means to quantify, how complex is a complex network. In order to answer this question we need a new theory of information of complex networks.


  1. Elizabeth Drellich, Andrew Gainer-Dewar, Heather A. Harrington, Qijun He, Christine Heitsch, AND Svetlana Poznanovic. Geometric Combinatorics AND Computational Molecular biology: branching polytopes for RNA sequences. 2016.
  2. Paul M. Dodda, Pablo F. Damascenob and Sharon C. Glotzera. Universal folding pathways of polyhedron nets. PNAS. 2018.
  3. Kartik Anand & Ginestra Bianconi. Entropy measures for networks: Toward an information theory of complex topologies. Arxiv. 2009.
  4. Ginestra Bianconi. The entropy of network ensembles. Arxiv. 2008.
  • 2
    $\begingroup$ You should clarify what do you mean by "polytope". See e. g. the Wikipedia article. $\endgroup$ – Ivan Izmestiev Sep 8 '19 at 12:26
  • $\begingroup$ @IvanIzmestiev Thanks for pointing this out. I just clarified that I am referring to polyhedra and their higher-dimensional analogues. $\endgroup$ – Aidan Rocke Sep 8 '19 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.