6
$\begingroup$

Let $A$ be a 0-1 matrix whose columns are maximal. We can associate its rows with vertices and columns with simplices in an abstract simplicial complex. Conversely, given an ASC, we can encode it in a 0-1 matrix.

What is the name of this matrix? Surely it must be used in the literature, but I can't seem to find an instance.

$\endgroup$
7
$\begingroup$

That sounds to me very like the encoding of a relation between two sets. By old work of Dowker there are two ASCs that correspond to such and their realisations are homotopically equivalent. There is extensive use of this and variants in which not just 0 and 1 are used but values between 0 and 1. I do not know of any special name. It is related to Chu spaces in computer science and category theory.

One particular use is in a paper by Abels and Holz, in which starting from a group and a family of subgroups they build an ASC and can interpret the homotopy groups of this ASC in terms of syzygies of group presentations. (I give a summary of this in a chapter in my menagerie notes that can be accessed via the nLab. The paper is: H. Abels and S. Holz, Higher generation by subgroups, J. Alg, 160, (1993), 311– 341.)

I know of other applications in a variety of mathematical and non-mathematical areas, but will limit the list to having one entry! (Some of the non-mathematical ones are a bit suspect methodologically!

Edit: Steve asked for the reference to Dowker's work, which I forgot to give, so here it is :

C. H. Dowker, Homology Groups of Relations, Annals of Maths, 56, (1952), 84 – 95.

$\endgroup$
  • $\begingroup$ You might like :A Spatial View of Information, Theoretical Computer Science, 365, (2006), pp. 206 - 215. by myself and Jonathan Gratus which looks at the Chu space aspect. $\endgroup$ – Tim Porter Apr 26 '18 at 19:38
  • $\begingroup$ After quickly going through cites, I see that Rob Ghrist calls this the "Dowker complex." $\endgroup$ – Steve Huntsman Apr 26 '18 at 20:24
  • $\begingroup$ That would be my preference for a term, but my roots are in algebraic topology and category theory so I look to those disciplines fro terminology and, as others have remarked, the array naturally occurs in other contexts. $\endgroup$ – Tim Porter Apr 27 '18 at 6:16
  • $\begingroup$ The paper with Jonathan Gratus that I mentioned is a cut down version of two earlier notes that are available from Dagstuhl. E-mail me if you want more on this. $\endgroup$ – Tim Porter Apr 27 '18 at 6:52
  • $\begingroup$ I forgot to mention that there was a related question here: mathoverflow.net/questions/108310/… $\endgroup$ – Tim Porter Apr 27 '18 at 12:32
2
$\begingroup$

It might be that it is simply referred to as the vertex-facet incidence matrix, at least in some polytope papers like https://arxiv.org/pdf/math/0006225.pdf

$\endgroup$
2
$\begingroup$

This looks like the incidence matrix of a clutter or hypergraph (whose edges are precisely the facets of your complex). It shows up quite a bit in optimization and combinatorial commutative algebra. For example see this question for some interesting conjectures. If you are interested in this area, the key words are: max-flow min-cut, packing problem, facet ideals, etc.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.