yes. indeed there is a complexity class PPA (“Polynomial Parity Argument”) of problems like Another Hamiltonian Path where we are given one one odd-degree vertex in a graph and we then know that another one exists. It turns out that we can always reduce such arguments to graphs where the maximum degree is 2, so that the graph consists of open and closed spaghetti strands (plus maybe a few degree-zero two meatballs). - Cris
On Jan 31, 2020, at 6:36 AM, James Propp <jamespropp@gmail.com> wrote:
I like the image of a bowl of spaghetti with one spaghetti-end sticking out of the mass of pasta. Spaghetti-ends come in pairs, so you know there’s got to be another one somewhere in there!
Jim Propp
On Fri, Jan 31, 2020 at 5:06 AM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 31/01/2020 00:41, Bernie Cosell wrote:
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more?
Of course -- but for that you must first have proved the "fundamental theorem of algebra", to establish that the number of complex roots equals the degree of the polynomial. And you need the slight extra subtlety of counting by multiplicity. It seems to me that the prerequisites for the parity-based proof are much harder than the sign-change proof is by itself.
-- g
_______________________________________________ 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