4
$\begingroup$

Consider a "complete" signed graph on $n$ vertices indexed by $1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge. For each pair of vertices $i$ and $j$, write $v_{ij}=1$ or $-1$ depending on whether the connecting edge goes from $i$ to $j$ or from $j$ to $i$, respectively, and $v_{ii}=0$. The corresponding adjacency matrix $V=(v_{ij})_{1\le i,j\le n}$ is a skew-symmetric matrix with entries $\pm1$ only outside the main diagonal. In particular, its determinant is 0 for $n$ odd and nonnegative for $n$ even; by a simple parity argument it can be shown that $\det(V)$ is odd (hence positive) in the latter case. On the other hand, $\det(V)$ seems to assume all possible odd positive values restricted only by Hadamard's_inequality.

My general question is whether the condition $\det(V)=1$ imposes some known combinatorial structure in the set of complete signed oriented graphs (or maybe in a reasonable subset of this set). Some kind of related questions is whether the matrix $V$ in general imposes some interesting combinatorial structure of the underlying graph (I even do not the answer in the case when $v_{ij}$ depends only on the distance $i-j$, that is, $v_{ij}=\epsilon_{i-j}$).

$\endgroup$
6
  • $\begingroup$ This combinatorial structure (a complete graph with an orientation) is known as a tournament. Also, as a skew-symmetric matrix, $\det(V)$ is a square (the square of the Pfaffian of $V$). $\endgroup$ Commented Jun 16, 2010 at 8:28
  • $\begingroup$ Robin, I provide the required links which explain that $\det(V)$ is the square of the Pfaffian. I can even compute the Pfaffian as a single determinant of a $(n/2)\times(n/2)$ matrix in the case $v_{ij}=\epsilon_{i-j}$. A tournament is another way to say a complete signed (oriented) graph, but I am looking for a structure of graphs satisfying $\det(V)=1$. $\endgroup$ Commented Jun 16, 2010 at 9:09
  • 1
    $\begingroup$ Wadim, Robin was commenting on your statement that "det(V) seems to assume all possible odd positive values restricted only by Hadamard's_inequality": there is an additional requirement that det(V) be a perfect square (or you should say Pfaffian). $\endgroup$ Commented Jun 16, 2010 at 14:18
  • $\begingroup$ Victor and Robin, thanks for notifying this mistake. Yes, of course, I meant that only the squares have to be taken in the range. $\endgroup$ Commented Jun 16, 2010 at 14:25
  • 1
    $\begingroup$ Did you try to interpret the determinant as generating function for non-intersecting lattice paths via Stembridge's theorem (Advances in Mathematics 83, Nonintersecting Paths, Pfaffians, and Plane Partitions)? $\endgroup$ Commented Jun 16, 2010 at 16:08

0

You must log in to answer this question.

Browse other questions tagged .