And though it's irrelevant to Jim's question, I'm irresistably reminded of the proof by induction that all horses are the same colour(s): plainly true for n = 1 horse; for n > 1 , remove each horse in turn and invoke case n-1 on the remaining subset. QED ... On 1/29/20, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< Another pseudoexample is the number of nonempty subsets of a finite set, ... >>
--- of a nonempty finite set, perhaps? WFL
On 1/29/20, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are:
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.
BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even.
But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed…
- Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun