7
$\begingroup$

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.

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

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This proof applies only to finite graphs, because of the reliance on the permanent of the adjacency matrix, right? $\endgroup$ Mar 22, 2011 at 4:27
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2011 at 4:40
2
$\begingroup$

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".

$\endgroup$
13
  • $\begingroup$ The question asks for positive weights. $\endgroup$ Mar 21, 2011 at 23:56
  • $\begingroup$ 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. $\endgroup$
    – JBL
    Mar 21, 2011 at 23:59
  • 3
    $\begingroup$ Consider two $C_3$ connected by an edge. Not every edge is in a perfect matching, yet I can find weights satisfying the problem... $\endgroup$ Mar 22, 2011 at 0:34
  • 2
    $\begingroup$ @JBL Third paragraph: The given conditions imply that this weighting belongs to the matching polytope of the graph. Why? $\endgroup$
    – Did
    Mar 22, 2011 at 0:38
  • 1
    $\begingroup$ 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$. $\endgroup$
    – mfolz
    Mar 22, 2011 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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