Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be a directed graph which contains $N$ vertices, and which satisfies the following condition: each vertex of $G$ has at least one incoming edge.

(For clarity, a vertex $V_1$ has an "incoming edge" if there is an edge $E$ which connects $V_1$ to some other vertex on the graph, $V_2$, for which $E$ is directed from $V_2$ to $V_1$)

Then I believe it follows that $G$ contains a closed cycle. The reason I am posting this is because the result seems straightforward/obvious, and yet it would apparently solve an open problem on MO regarding zero sum subsets, so I am concerned that I may have a mistake. (To be frank, I am not comfortable posting on MO)

The basic idea is to show that starting with a set of $N$ vertices, and no edges. That it is impossible to construct a directed graph with no closed cycles by adding one (directed) edge at a time.

Let a set of $N$ vertices be given, and let us attempt to construct a directed graph with no closed cycle by adding one directed edge at a time. Choose some arbitrary vertex $V_1 \in G$, then by the defining condition of $G$, $V_1$ must have an incoming edge, say from $V_2$. It's clear that $V_2$ has an incoming edge, if this edge originates from $V_1$, then the graph would have a closed cycle, so we choose some other vertex which connects to $V_2$: and in this way we are forced to create a chain of $N-1$ vertices, $V_1$, has an edge coming from $V_2$, which has an edge coming from $V_3, \ldots, V_{N-2}$, which has an edge coming from $V_{N-1}$. It's clear that if any of the vertices in this chain has an incoming edge originating from another vertex on the chain, that $G$ will contain a closed cycle. So once we construct a chain of $N-1$ distinct vertices, there is one vertex left, and since this vertex must have an incoming edge originating from another vertex which is already on the chain, $G$ must contain a closed cycle.

Now let me explain why I think this fairly trivial result solves the open zero sum subset problem on MO.

This question asks: given a finite set of real numbers $S$ with the property that every number in the set can be written as the sum of two numbers in the set (not necessarily different), if there exists a subset $S$ which sums to zero.

Well, clearly a set $S$ which satisfies the condition of the problem stated above corresponds to a directed graph for which each vertex has at least one incoming edge (each real number in the set $S$ is associated with a vertex, and if given three numbers $a,b,c \in S$, with $a = b + c$, then the vertex associated with $a$ will have incoming edges from the vertices associated with $b$ and $c$). Therefore the graph corresponding to an arbitrary S which satisfies the condition contains a closed cycle. By adding the numbers in the closed cycle, we obtain a sum of the form:

$a + b + c + \ldots = a$, hence it follows that $b + c + \ldots = 0$, i. e. a set $S$ which satisfies the condition must contain a zero sum subset. Have I made a mistake somewhere, or does this solve the problem?

share|improve this question
2  
The case where a = b + b causes problems. –  whuber Sep 14 '10 at 20:13
    
For the first part: wouldn't it be simpler to argue as follows: pick $v_1$; having selected $v_k$, let $v_{k+1}$ be a vertex such that $(v_{k+1},v_k)$ is an edge. This gives you a sequence of vertices $v_1,v_2,\ldots$. Since $G$ is finite, there exist $n\lt m$ such that $v_n = v_m$, and $v_n,v_{n+1},\ldots,v_m=v_n$ is your cycle; (assuming you do not allow loops; if you do, then presumably a loop is a closed cycle, or a disjoint union of loops would be a counterexample) –  Arturo Magidin Sep 14 '10 at 20:26
1  
@Whuber: I think I see what you are saying: I need to deal with the case that the sum b + c + ... = 0 has repeated elements (for example b = c). –  Matt Calhoun Sep 14 '10 at 20:37
    
Exactly! –  whuber Sep 14 '10 at 20:50
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.