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$
4
  • $\begingroup$ Maybe you should define "incidence matrix" in this context. $\endgroup$ Commented Jan 10, 2017 at 22:59
  • $\begingroup$ @BrendanMcKay I edited the post with the incidence matrix definition. $\endgroup$ Commented Jan 11, 2017 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$ Commented Jan 11, 2017 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$ Commented Jan 11, 2017 at 10:38

0

You must log in to answer this question.

Browse other questions tagged .