Skip to main content
added 503 characters in body
Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an appropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.


Perhaps it is a bit more clear if we phrase it in the following way. When restricting to bipartite graphs, the property of each edge being contained in a disjoint cycle cover is equivalent to every edge being in a perfect matching (there are no odd cycles). Now the result above follows because weights on our graph induce weights on its bipartite double cover which sum to 1 at each vertex. A disjoint cycle cover of a graph is equivalent to a perfect matching of its bipartite double cover.

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an appropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an appropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.


Perhaps it is a bit more clear if we phrase it in the following way. When restricting to bipartite graphs, the property of each edge being contained in a disjoint cycle cover is equivalent to every edge being in a perfect matching (there are no odd cycles). Now the result above follows because weights on our graph induce weights on its bipartite double cover which sum to 1 at each vertex. A disjoint cycle cover of a graph is equivalent to a perfect matching of its bipartite double cover.

added 13 characters in body
Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_ij$$a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an apropriatedappropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_ij$ in $A$ which means that there is a permutation matrix with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an apropriated convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an appropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.

Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_ij$ in $A$ which means that there is a permutation matrix with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an apropriated convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.