Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\Gamma=(G,E)$ be a connected undirected graph, with no loops or multiple edges. $G$ is finite or countably infinite. For each edge $e=\{x,y\}\in E$, we assign a positive, symmetric edge weight $c_e := c_{\{x,y\}} = c_{xy} = c_{yx}$. I would like to know for which graphs $\Gamma$ it is possible to choose $(c_e)_{e\in E}$ so that for each $x\in G$,

\begin{equation*} \sum_{y\sim x} c_{xy} = 1. \end{equation*}

For example, this is possible on any $d-$regular graph if one sets $c_e \equiv 1/d$. The graph with vertex set $\{x,y,z\}$ and edges $\{x,y\}$ and $\{y,z\}$ shows that it is not always possible.

share|improve this question
    
More generally, no leaf is allowed if $G$ has more than $2$ vertices. –  Did Mar 21 '11 at 23:49
    
Didier, this is wrong: a set of disjoint edges works fine. (This is the only counter-example to your statement.) –  JBL Mar 22 '11 at 0:03
    
@JBL Connected. –  Did Mar 22 '11 at 0:06
    
Whoops, fair enough. All those pesky adjectives like "positive" and "connected" .... My apologies. –  JBL Mar 22 '11 at 0:08
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
This proof applies only to finite graphs, because of the reliance on the permanent of the adjacency matrix, right? –  Gerry Myerson Mar 22 '11 at 4:27
    
With a bit of care, it's not too hard to extend it to the locally finite case with the same proof, but I'm not sure what happens when you allow vertices to have infinite degree (does the OP want to consider such cases?), there are convergence issues and what not. I'll think about it some more. –  Gjergji Zaimi Mar 22 '11 at 4:40
add comment

Edit: this is completely broken, sorry! I leave it up for the record.


Let $G$ be finite. Then a weighting of the desired form exists if and only if every edge of the graph is contained in a perfect matching.

First, suppose every edge is contained in a perfect matching. Simply take the convex combinations of the matchings (considered as weightings with weight 1 on the edges of the matching and weight 0 on the other edges) and win.

Now, suppose your graph has a weighting of the desired form. The given conditions imply that this weighting belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching. In particular, your weighting lies on the face of the polytope whose vertices are precisely the perfect matchings of the graph, and so it is a convex combination of perfect matchings. Since it is positive in every coordinate, there must be a vertex that is positive in every coordinate, i.e., every edge must be contained in some perfect matching.

An earlier version of this answer solved the problem in the case that "positive" is replaced by "nonnegative". In that case, the condition becomes "the graph contains a perfect matching".

share|improve this answer
    
The question asks for positive weights. –  Gjergji Zaimi Mar 21 '11 at 23:56
    
Well, it's not clear to me if the O.P. cares about the difference between positive and nonnegative, but it's easy to adjust the argument: you get strictly positive if and only if every edge is contained in a perfect matching. –  JBL Mar 21 '11 at 23:59
3  
Consider two $C_3$ connected by an edge. Not every edge is in a perfect matching, yet I can find weights satisfying the problem... –  Gjergji Zaimi Mar 22 '11 at 0:34
2  
@JBL Third paragraph: The given conditions imply that this weighting belongs to the matching polytope of the graph. Why? –  Did Mar 22 '11 at 0:38
1  
Maybe I am missing something, but suppose that each edge is contained in a perfect matching. Let $(a_e)_{e\in E}$ satisfy $a_e>0$ and $\sum_E a_e = 1$, and for each edge $e_j$, let $(c^{(e_j)}_e)_{e\in E}$ be an assignment of nonnegative edge weights with $c^{e_j}_{e_j}=1$ (i.e., using the perfect matching). Then $d_e = \sum_j a_{e_j}c^{(e_j)}_e$ is what we want, and satisfies $d_e>0$ for all $e\in E$. –  mfolz Mar 22 '11 at 1:32
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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