4
$\begingroup$

Consider fundamental cycles (say $k$ of them) of a specific spanning tree of a simple graph (with $m$ edges) which is also connected and has no one-edge bonds.

Make the graph directed (in an arbitrary way) and each cycle directed (to follow consistently one of the two possible orientations); then create a matrix C with $k$ rows and $m$ columns whose elements indicate whether an edge is a part of the cycle (by $1$ or $-1$ when the two orientations agree or not, respectively) or not (by 0).

How would one prove the following:

Selecting $k$ columns of the matrix, the corresponding sub-determinant equals to $1$ or $-1$ when the corresponding edges contain no bond, equals to 0 otherwise.

A bit more challenging would be to prove that C is totally unimodular.

(My original contention that there was a unique bijection between edges of a cotree and fundamental cycles a potentially different spanning tree has been disproved below).

$\endgroup$
18
  • 1
    $\begingroup$ I am sorry, the previous (and accepted) answer was wrong in one direction. Actually the claim simply does not hold: if the bijection exists, it may be not a cotree. $\endgroup$ Apr 27 at 7:05
  • 1
    $\begingroup$ well, i see. Then it remains to do two things: prove the uniqueness when $S$ is a cotree; prove that $S$ is a cotree when the bijections exists and is unique. $\endgroup$ Apr 28 at 13:30
  • 1
    $\begingroup$ hm, it looks that it is not always unique, please check my example $\endgroup$ Apr 28 at 19:59
  • 1
    $\begingroup$ I added the proof of total unimodularity $\endgroup$ May 2 at 8:27
  • 1
    $\begingroup$ Edge $e$ which goes from $u$ to $v$ correspinds to $v-u$. This extends to an isomorphism between the span of edges of a tree and the hyperplane "sum of coordinates equals 0" in the span of vertices. $\endgroup$ May 3 at 6:21
2
$\begingroup$

Fix a spanning tree $T\subset E$ in a connected graph $G=(V,E)$. It defines fundamental cycles $C_1,\ldots,C_k$, $k=|E|-|T|$: for any $e\in E\setminus T$ take the unique cycle in $T\cup \{e\}$.

Let first $k$ columns of C correspond to the edges in $E\setminus T$. Then the first $k$ columns form a matrix with $\pm 1$ on the diagonal and zeros outside the diagonal. Consider an $r\times r$ minor of C, we should prove that it either 0 or $\pm 1$. By the structure of the first $k$ columns, this reduces to the case when all $r$ columns of the minor correspond to $r$ edges $e_1,\ldots,e_r$ of a tree, let $r$ its rows correspond to $f_1,\ldots,f_r$ of $E\setminus T$. We contract all edges of $T$ except $e_1,\ldots,e_r$. I claim that if the set $f_1,\ldots,f_r$ does not contain a cycle, the corresponding rows are linearly independent over any field (thus the minor is $\pm 1$), and if they do contain a cycle, the rows are dependent with the coefficients $\pm 1$ (thus the minor is 0). For seeing this, we embed the span of the edges $e_1,\ldots,e_r$ to the hyperplane in the vertex space of the (new) tree $\tilde{T}$: each edge $e_i=uv$ corresponds to the vector $v-u$. With this embedding, the row which correspond to edge $f_j=uv$ corresponds to $\pm(v-u)$. The above claim is now clear.

Below is a couple of claims concerning the previous version of the question.

We have the following

Theorem 1. If set $S\subset E$ is a cotree (a complement of a spanning tree), then there exists a bijection $f\colon S\to \{1,\ldots,k\}$ such that $e\in C_{f(e)}$ for all $e\in S$.

Proof. To prove that such a bijection exists, by Hall lemma (for the natural bipartite graph with parts $S$ and $\{1,\ldots,k\}$ corresponding to a relation $(e,i):e\in C_i$) it suffices to prove that the union $C_0$ of any $m=1,2,\ldots,k$ fundamental cycles contain at least $m$ elements of $S$. Denote $T_0=T\cap C_0$. Then $T_0$ is a forest, and it is an inclusion-maximal subforest of $C_0$ (since after adding to $T_0 $any edge in $C_0\setminus T$ you get a fundamental cycle). Assume that on the contrary $|S\cap C_0|\leqslant m-1$, this is equivalent to $|(E\setminus S)\cap C_0|\geqslant |C_0|-m+1=r+1$. But $E\setminus S$ is a tree, then $(E\setminus S)\cap C_0$ is a subforest of $C_0$, and it has more edges than an inclusion-maximal subforest $T_0$ of $C_0$. A contradiction.

The converse does not hold. For example, consider the graphon the picture (the black edges constitute a spanning tree, take the edge $e_1$ in the fundamental cycle $C_1$ and $e_2$ in $C_2$. The set $\{e_1,e_2\}$ is not a cotree, however.)

Also, the bijection is not always unique.Here (the spanning tree is black) three edges $e_1,e_2,e_3$ may be paired with fundamental cycles by different ways.

Finally, I prove

Theorem 2. Assume that set $S\subset E$ is such that there exists unique bijection $f\colon S\to \{1,\ldots,k\}$ such that $e\in C_{f(e)}$ for all $e\in S$. Then $S$ is a cotree.

Proof. Consider the cut matroid of $G$: the bases are cotrees, the independent sets are subsets of cotrees. Let $e_1,\ldots,e_k$ be all elements of $E\setminus T$ enumerated so that $e_i\in C_i$. Note that $f\in C_i$ if and only if $(T\cup e_i)\setminus f$ is a tree, that is, $((E\setminus T)\setminus e_i)\cup f=f\cup \{e_j:j\ne i\}$ is a cotree. That is, if $f$ does not belong to a flat generated by $\{e_j:j\ne i\}$. Our matroid is a vector matroid, so this may be said as "the coefficient of $e_i$ in the expansion of $f$ in the basis $\{e_1,\ldots,e_k\}$ is non-zero". That is, we are given that the matrix of vectors of $S$ in the basis $\{e_1,\ldots,e_k\}$ has unique generalized diagonal with non-zero elements. This yields that the determinant of this matrix is non-zero, so, it is non-singular and $S$ constitutes a basis.

$\endgroup$
1
$\begingroup$

Consider 2 different spanning trees of the graph, and the corresponding cotrees and fundamental cycles. Then $$C_2=C_2|S_1*C_1$$ spells out the algebraic details of the following well-known fact: every fundamental cycle of Type 2 is a linear combination of fundamental cycles of Type 1 with coefficients from the ${0,1,-1}$ set; $C_2|S_1$ implies selecting only those columns/edges of $C_2$ which are in the first cotree (these are the coefficients of the linear combinations).

Now, selecting only columns which are in $S_2$ from each side of this equation yields $$C_2|S_2=C_2|S_1*C_1|S_2$$ Since the determinant of the LHS matrix is equal to either $1$ or $-1$ (there is exactly one way of matching each edge of a cotree with the corresponding fundamental cycle, only one of the $k!$ term of the determinant is non-zero). This implies that (integer-valued) determinants of each of the RHS matrices have the same property (being equal to $1$ or $-1$).

When the $k$ edges contain a bond, there is a linear combination of the corresponding columns of C (with coefficients from the $1,-1$ set) which yields a zero vector (a bond has to be traversed both ways by each cycle - the two contributions always cancel). This implies that these columns are linearly dependent and the corresponding determinant is thus equal to $0$.

The totally unimodular issue: It's know (and I take it for granted) that C is unimodular if and only if it's possible to find a linear combination of any selection of its rows such that (i) the coefficients are either $1$ or $-1$, (ii) the resulting elements are all from the $0,1,-1$ set.

To find such coefficients, one must first simply add the selected rows and apply 'mod 2' to each component of the answer (getting a vector of ones and zeros); this defines an undirected closed trail (revisiting vertices is allowed). Give this trail a consistent orientation (there may be several ways of doing it) by changing the sign of some of the $1$ components; the corresponding sign of the unique co-tree component of each row of C tells us whether the row should be added or subtracted - the answer will match the already constructed directed trail.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.