Skip to main content
MathOverflow

Return to Answer

The original proof minimized $sum_{e \in E(G)} w(e)$. In order to ensure that this sum cannot be arbitrarily small, we instead minimize $\sum_{e \in E(G): w(e) \ge 0} w(e)$. In order to then ensure the existence of the edge $f$ with $w(f) \ge 1$, we restrict our attention to strongly conn graphs
Source Link
Paul Wollan
Paul Wollan
  • 677
  • 5
  • 7

The answer to 2. is "yes" if we assume the graph has every edge contained in a cycle. First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that if $G$ has the property that every edge is contained in a cycle, then any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G)} w(e)$$\sum_{e \in E(G): w(e) \ge 0} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that this preserves the property that every edge is contained in a cycle, and it also holds that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. It follows that there must exist an edge $f$ with $w(f) \ge 1$. Fix such an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G)} w''(e)$$\sum_{e \in E(G): w''(e) \ge 0} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

The answer to 2. is "yes". First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G)} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. Fix an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G)} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

The answer to 2. is "yes" if we assume the graph has every edge contained in a cycle. First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that if $G$ has the property that every edge is contained in a cycle, then any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G): w(e) \ge 0} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that this preserves the property that every edge is contained in a cycle, and it also holds that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. It follows that there must exist an edge $f$ with $w(f) \ge 1$. Fix such an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G): w''(e) \ge 0} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

deleted 2 characters in body
Source Link
Paul Wollan
Paul Wollan
  • 677
  • 5
  • 7

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that each loop must have positive weight 0 in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that each loop must have positive weight 0 in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that each loop must have positive weight in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Source Link
Paul Wollan
Paul Wollan
  • 677
  • 5
  • 7

I assume that when you say the weight of any circuit is positive, you mean that for every directed cycle $C$, $\sum_{e \in E(C)} w(e) > 0$. There's a similar model of group labeled graphs where you calculate the weight of a circuit by either adding or subtracting $w(e)$ depending on whether you traverse the edge according to the direction or not.

The answer to 2. is "yes". First, observe that it suffices to prove it for rational weights - just subtract a tiny epsilon from each edge to make it's weight rational without altering the fact that each cycle has positive weight.

Your operation for finding an equivalent weight function on the edges can be generalized: if we take any edge cut $\delta(U)$ for a subset $U \subseteq V(G)$ and a value $m \in \mathbb{R}$, then if we add $m$ to all the edges of $\delta^{in}(U)$ and subtract $m$ from $\delta^{out}(U)$, we won't change the weight of any cycle. Call this operation $resigning~on~a~cut$. (In fact, resigning on a cut $\delta(U)$ for a subset of vertices $U$ is the same as repeatedly resigning by the same value on each of vertices in $U$). Say two weight functions are $flip~equivalent$ if one can be obtained from the other by repeatedly re-signing on a cut.

A weight function is $non-negative$ if the weight of any cycle is not negative. We claim that any non-negative rational weight function is flip equivalent to one where every edge has non-negative weight. Assume the claim is false. It suffices to prove the claim for integer weight functions by re-scaling. Pick a counterexample on a minimal number of vertices, and subject to that, to minimize $\sum_{e \in E(G)} w(e)$. If there exists a cycle $C$ such that $w(C) = 0$, then there exists a weight function $\bar{w}$ which is flip-equivalent to $w$ such that $\bar{w}(e) = 0$ for all edges $e \in E(C )$. To see this, number the edges of $C$ $e_1, \dots, e_k$ so that they occur in that order on $C$. We can force $e_i$ for $1 \le i \le k-1$ to have weight 0 by sequentially resigning on $\delta(v_{i+1})$. After doing so, the weight on $e_k$ will be the weight of the cycle, namely 0.

Consider the graph $G'$ obtained by contracting the cycle $C$ to a single vertex and deleting any loops which arise. Note that each loop must have positive weight 0 in $\bar{w}$. Let $w'$ be the weight function obtained by restricting $\bar{w}$ to the edges of $G'$. Then $G'$ has no negative weight circuit, since any such circuit could be rerouted through $C$ to give a negative weight cycle in $G$. Thus, $w'$ on $G'$ can be made non-negative by repeatedly resigning on cuts. Since each cut of $G'$ is a cut of $G$ as well, it follows that $\bar{w}$ can be made non-negative by repeatedly resigning on cuts.

Thus, we may assume that every cycle has strictly positive weight, and consequently, weight at least 1. Fix an edge $f$, and let $w''$ be the weight function with $w''(e) = w(e)$ for all $e \neq f$ and let $w''(f) = w(f) - 1$. By construction, $w''$ is a non-negative since the weight of any cycle decreases by at most $1$. Moreover, $\sum_{e \in E(G)} w''(e)$ has strictly decreased, so by our choice of counterexample, there exists a weight function which is flip equivalent to $w''$ where every edge has non-negative weight. By resigning on the same series of cuts, we find a weight function which is flip equivalent to $w$ where every edge has non-negative weight, contradicting our choice of counterexample.

Now to see that the same result holds for rational weight functions where every cycle has strictly positive weight, let $z$ be such a weight function. By above there exists a weight function $z'$ which is flip-equivalent to $z$ such that every edge has $z'(e) \ge 0$. Pick such a $z'$ to have has few edges of weight zero as possible. The function $z'$ does not have any cycles where every edge has weight 0 in $z'$. Thus, if there are any edges $z'(e) = 0$, it follows that there is a vertex $v$ such that $v$ has some out edge of weight zero and no in edge of weight zero. If we let $\epsilon= min_{e \in \delta(v)} z'(e)$, then adding $\epsilon/2$ to each of the out edges of $v$ and subtracting $\epsilon/2$ from all the in edges will maintain the property of being a non-negative weighting and strictly decrease the number of edges of weight zero, a contradiction.