Proofs of parity results via the Handshaking lemma - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T04:10:52Z http://mathoverflow.net/feeds/question/77906 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma Proofs of parity results via the Handshaking lemma Fedor Petrov 2011-10-12T08:33:09Z 2011-10-13T03:41:46Z <p>I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).</p> <p>Let me mention three results of such nature:</p> <ol> <li><p>If the graph $G$ has even number of vertices and all of them have even degree, then it has even number of spanning trees. It may be proved by using the matrix-tree theorem, though not immediately, I mean the following elementary argument: consider the new graph, in which spanning trees of $G$ serve as vertices, and two trees $T$, $T'$ are joined iff they differ by one edge (i.e. all edges of $T$ except one edge are also edges of $T'$). Then all degrees in new graph are odd and we are done.</p></li> <li><p>(This argument is due to Andrew Thomason). Given vertices $x$, $y$ in a finite graph $G$, in which all vertices except $x$, $y$ have odd degree ($x$ and $y$ may have both even degree or moth odd, it does not matter), then the number of Hamiltonian paths from $x$ to $y$ is even. For proving this, consider all Hamiltonian paths starting in $y$ in the graph $G-x$. Join two such paths if they differ by one edge (i.e. all edges of the first path except one are also edges of the second). Then the degree of a path $yz\dots v$ in new graph is one less then degree of $v$ in $G-x$. So, it is odd iff $v$ is joined to $x$, and odd vertices of our new graph correspond to Hamiltonian paths from $x$ to $y$ in $G$.</p></li> <li><p>(This is due to László Lovász). Let $G=(V,E)$ be a finite graph. Call a subset $A\subset V$ dominating if any vertex $v\in V\subset A$ has at least one neighbor in $A$. Then any non-empty graph has odd number of dominating sets. We prove that the number of non-dominating non-empty subsets of $V$ is even. They are vertices of a new graph, and two of them $B_1,B_2$ are joined iff there are no edges between $B_1$ and $B_2$ in $G$. All degrees are odd (degree of $B$ equals $2^k-1$, where $k$ is the number of vertices in $V\subset B$ not joined with $B$), and we are done again. </p></li> </ol> <p>I have general question: what are other examples of such flavor? Of course, proving of parity by partitioning onto pairs formally is particular case (corresponding to the graph with degrees 1), and by partitioning onto even subsets too, but I rather ask about more involved graphs used in the proof:)</p> <p>And one specific question: may Redei's result that any tournament have odd number of Hamiltonian paths be proved by such techniques?</p> http://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma/77912#77912 Answer by Gjergji Zaimi for Proofs of parity results via the Handshaking lemma Gjergji Zaimi 2011-10-12T10:11:02Z 2011-10-13T03:41:46Z <p>Another very famous example is <a href="http://en.wikipedia.org/wiki/Sperner%27s_lemma" rel="nofollow">Sperner's lemma</a>. Other examples are Chevalley's theorem for $p=2$, <a href="http://en.wikipedia.org/wiki/Tucker%27s_lemma" rel="nofollow">Tucker's lemma</a>, the fact that the number of decompositions into Hamiltonian cycles is even etc. (See the paper below). The continuous analogs of some of these are also derived from the same proofs, therefore you could count Brower's fixed point theorem (from Sperner's lemma) and <a href="http://en.wikipedia.org/wiki/Borsuk%E2%80%93Ulam_theorem" rel="nofollow">Borsuk-Ulam theorem</a> and the <a href="http://en.wikipedia.org/wiki/Ham_sandwich_theorem" rel="nofollow">Ham-Sandwich theorem</a> (from Tucker's lemma), as following from the handshake lemma.</p> <p>On the other hand you may be interested in the complexity classes <a href="http://en.wikipedia.org/wiki/PPA_%28complexity%29" rel="nofollow">PPA</a> and <a href="http://en.wikipedia.org/wiki/PPAD_%28complexity%29" rel="nofollow">PPAD</a> which provide one possible formalization of your question. There are a lot of papers (in complexity theory) that study such examples, but I can't comment further since I'm not very familiar with the literature. One place to start is the article by Christos Papadimitriou (1994), <a href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="nofollow">"On the complexity of the parity argument and other inefficient proofs of existence"</a>. Journal of Computer and System Sciences 48 (3): 498–532. I thought this was relevant since you mention that you want problems which can be solved by a parity argument but the graph involved is complex enough that it is not easy to exhibit an involution.</p> http://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma/77920#77920 Answer by Tony Huynh for Proofs of parity results via the Handshaking lemma Tony Huynh 2011-10-12T12:34:58Z 2011-10-12T12:47:43Z <p>The following puzzle can be solved by the same technique. A <em>mountain range</em> is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for all $c \in (a,b)$. There is hiker $A$ at the point $(a,0)$ and a hiker $B$ at the point $(b,0)$. The two hikers begin moving along the mountain range, the only restriction being that they must always be at the same elevation. Prove that $A$ and $B$ can always meet at some point of the mountain range. </p> <p>On a slightly more serious note, I vaguely remember that the existence of Nash equilibria can be proved by a parity argument (via Sperner's lemma). </p> http://mathoverflow.net/questions/77906/proofs-of-parity-results-via-the-handshaking-lemma/77931#77931 Answer by Timothy Chow for Proofs of parity results via the Handshaking lemma Timothy Chow 2011-10-12T16:04:46Z 2011-10-12T16:04:46Z <p>There is a nice paper by Kathie Cameron and Jack Edmonds, <a href="http://aif.cedram.org/item?id=AIF_1999__49_3_815_0" rel="nofollow">Some graphic uses of an even number of odd nodes</a>, with several examples of the use of the handshaking lemma to prove various graph-theoretic facts.</p> <p>Gjergi Zaimi already mentioned the relevance of the complexity classes PPA and PPAD. In addition to Papadimitriou's paper, <a href="http://www.cse.ucsd.edu/users/russell/search.ps" rel="nofollow">this paper</a> by Beame et al. is a useful reference.</p> <p>I seem to remember that the <a href="http://en.wikipedia.org/wiki/Chevalley%E2%80%93Warning_theorem" rel="nofollow">Chevalley-Warning theorem</a> can be proven by this method, but I can't reconstruct the argument, so maybe I'm confused.</p>