1
$\begingroup$

what are the necessary conditions for a weighted directed hypergraph to have an incidence matrix of full rank?

In this context, we can define the incidence matrix as follows:

Let $V = \{v_1,v_2,...,v_m\}$ be the set of vertices and $E = \{e_1,e_2,...,e_n\}$ be the set of hyperedges (possibly connecting more than two vertices) of the weighted directed hypergraph $H$. The $m \times n$ incidence matrix is $A = (a_{ij})$ where

$$ a_{ij} = \begin{cases} w_{ij}, & \text{if}\ v_{i} \in e_j \\ 0, & \text{otherwise} \end{cases} $$

where $w_{ij} \ne 0$ is the weight that can be negative because of the direction of the hyperedge. Each column of $A$ has at least one positive entry and one negative entry, so it has at least two entries.

For directed graphs it is well known that the rank of the incidence matrix is equal to $m - c$, where $c$ is the number of connected components of the graph. Lets consider that the hypergraph $H$ has only one connected component ($c = 1$).

This question is a generalization of this one: Which graphs have incidence matrices of full rank?

$\endgroup$
  • $\begingroup$ Maybe you should define "incidence matrix" in this context. $\endgroup$ – Brendan McKay Jan 10 '17 at 22:59
  • $\begingroup$ @BrendanMcKay I edited the post with the incidence matrix definition. $\endgroup$ – Hugo Dourado Jan 11 '17 at 0:40
  • $\begingroup$ Thanks, but I suspect it is not correct. An edge produces a column with two non-zero entries of opposite sign, right? It isn't what you wrote. $\endgroup$ – Brendan McKay Jan 11 '17 at 7:48
  • $\begingroup$ @BrendanMcKay There are only two non-zero entries if it is an graph, since it's a hypergraph it admits edges connecting more than two vertices. It is possible to define hypergrahs containing edges connecting only one or zero vertices, but for the sake of simplicity I'll exclude this in the definition. I'll also make clear that in each column there is at least one negative and one positive element. $\endgroup$ – Hugo Dourado Jan 11 '17 at 10:38

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.