Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of each dimension. What I want is to find the possible complexes with these numbers of cells. This really is not my field of expertise (if anything is), so I turn to your collective wisdom.

So suppose I am given a vector of positive integers, e.g. $(8,12,6,1)$. What simplicial complexes can I build with number of $k$-cells given by the vector? In the example, I want 8 0-cells, 12 1-cells, etc.

I expect that for most such vectors there would be several possible complexes one could build out of them, but I have no idea if (a) this is true, or (b) how to find them, or even (c) to find the number of possibilities. Has anyone done anything similar before? Is anything known about this? I'd appreciate any suggestions or references.

  • 3
    $\begingroup$ Your vector of positive integers is known as the "f-vector" of the complex. The Kruskal-Katona theorem en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem characterizes the f-vectors which arise from simplicial complexes, but you want something more detailed. $\endgroup$ – j.c. May 27 '11 at 13:21
  • 3
    $\begingroup$ What exactly do you plan to do with the answer? I ask, because the numbers are not going to be small: for example, for the vector $(v, e)$, corresponding to graphs with $v$ vertices and $e$ edges, the number will be the number of all subsets of cardinality $e$ from a set of cardinality $(v^2 - v)/2,$ so fairly numerous. $\endgroup$ – Igor Rivin May 27 '11 at 13:59

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.