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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Apr 26, 2018 at 19:38
  • $\begingroup$ After quickly going through cites, I see that Rob Ghrist calls this the "Dowker complex." $\endgroup$
    – Steve Huntsman
    Commented Apr 26, 2018 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
    Commented Apr 27, 2018 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
    Commented Apr 27, 2018 at 6:52
  • $\begingroup$ I forgot to mention that there was a related question here: mathoverflow.net/questions/108310/… $\endgroup$
    – Tim Porter
    Commented Apr 27, 2018 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

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .