Timeline for Assigning positive edge weights to a graph so that the weight incident to each vertex is 1.
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2011 at 6:34 | comment | added | Did | @mfolz For each edge $e$, one chooses any matching $M_e$ which contains $e$. Then $c_e=\sum_fa_f[e\in M_f]$ defines a positive weight $c_e$ for every edge $e$ and, for every vertex $x$, $\sum_ec_e[x\in e]=\sum_fa_f\sum_e[x\in e, e\in M_f]=\sum_fa_f=1$. Allright. Thanks. | |
| Mar 22, 2011 at 1:32 | comment | added | mfolz | 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$. | |
| Mar 22, 2011 at 1:07 | comment | added | Did | @mfolz How is it sufficient for infinite graphs? One would need each edge to belong to at least one matching from a finite collection. Is the existence of such a finite collection obvious? | |
| Mar 22, 2011 at 0:54 | comment | added | mfolz | Well, it is certainly a sufficient condition, in both the finite and countably infinite settings. | |
| Mar 22, 2011 at 0:49 | comment | added | JBL | @Didier Piau, good question! | |
| Mar 22, 2011 at 0:44 | history | edited | JBL | CC BY-SA 2.5 |
added 88 characters in body
|
| Mar 22, 2011 at 0:38 | comment | added | Did | @JBL Third paragraph: The given conditions imply that this weighting belongs to the matching polytope of the graph. Why? | |
| Mar 22, 2011 at 0:36 | comment | added | mfolz | Thanks for the answer, JBL. The distinction between positive and nonnegative is actually significant in this instance. For the infinite case, it seems that one can just as easily take an infinite, strictly positive, convex combination of matchings. | |
| Mar 22, 2011 at 0:34 | comment | added | Gjergji Zaimi | Consider two $C_3$ connected by an edge. Not every edge is in a perfect matching, yet I can find weights satisfying the problem... | |
| Mar 22, 2011 at 0:21 | history | edited | JBL | CC BY-SA 2.5 |
added 222 characters in body
|
| Mar 22, 2011 at 0:15 | comment | added | JBL | Yes, that's correct. I'll edit to make it clearer. | |
| Mar 22, 2011 at 0:13 | comment | added | Did | @JBL The OP did write positive. So, in the end, your necessary and sufficient condition is that for every edge, there exists a perfect matching which contains this edge, is that correct? | |
| Mar 22, 2011 at 0:04 | comment | added | JBL | This proof is restricted to the finite case; I have no idea what happens with an infinite graph. | |
| Mar 22, 2011 at 0:02 | history | edited | JBL | CC BY-SA 2.5 |
added 489 characters in body
|
| Mar 21, 2011 at 23:59 | comment | added | JBL | 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. | |
| Mar 21, 2011 at 23:56 | comment | added | Gjergji Zaimi | The question asks for positive weights. | |
| Mar 21, 2011 at 23:55 | history | answered | JBL | CC BY-SA 2.5 |