Let $R$ be a 0-1 matrix whose rows or columns are maximal.

Q1. Is there a name for such a matrix (or, e.g., a corresponding relation)?

From 0-1 matrix corresponding to an abstract simplicial complex, we know that $R$ corresponds to an abstract simplicial complex, viz. the Dowker complex $D(R)$.

One has maps $\begin{pmatrix} 0 & R \\ R^T & 0 \end{pmatrix} \overset{\pi}{\rightarrow} R \overset{D}{\rightarrow} D(R)$, where $D(R)$ is the Dowker complex of $R$. The involutions $\begin{pmatrix} 0 & R \\ R^T & 0 \end{pmatrix} \overset{\sigma}{\mapsto} \begin{pmatrix} 0 & R^T \\ R & 0 \end{pmatrix}$, $R \overset{T}{\mapsto} R^T$, and $D(R) \overset{*}{\mapsto} D^*(R) := D(R^T)$ (with the last one a homotopy equivalence) are such that $D \circ \pi = \mathcal{N}$, where the RHS indicates the neighborhood complex as in section 2.2 of Lovász's notes.

[In the electrical engineering and machine learning literature (and ignoring the distinction between an adjacency matrix and a graph), the inverse image of $\pi$ is called a "factor graph."]

Q2. Is there a canonical reference for all of these correspondences that includes the perspective of bipartite graphs?

Note in particular that we immediately get a rich homology theory for bipartite graphs from the Dowker homology of $R$ (or, if the extra step is desired, the simplicial homology of the Dowker complex).

I have found various papers that mention two of the three threads above, e.g., the correspondence between relations and Dowker complexes is in Dowker's original paper and its various cites, and a weighted version is in "A functorial Dowker theorem and persistent homology of asymmetric networks." Bipartite graphs and neighborhood complexes are also discussed in "Construction of and efficient sampling from the simplicial configuration model". But I haven't found any reference that ties all three together.

  • $\begingroup$ Sorry if it may sound trivial, but what do you mean by "the columns are maximal"? $\endgroup$ – Luca Ghidelli Jul 24 '18 at 14:10
  • $\begingroup$ @LucaGhidelli No column has all its entries less than or equal to those in another column. $\endgroup$ – Steve Huntsman Jul 24 '18 at 19:20

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.