It seems a lot of impossibility theorems - the type that the ancient Greeks would have understood - can be proven using algebraic topology. Perhaps Sperner's lemma can be seen as an algebraic topology theorem? I don't personally know.
PollardsRho 294 days ago [-]
Thanks for sharing this proof! As someone who enjoys math but never got myself through enough Galois theory to finish the standard proof, it's fantastic to see a proof that's more elementary while still giving a sense of why the group structure is important.
xyzzyz 294 days ago [-]
Sperner lemma is very much an algebraic topology theorem. The ideas involved in it form the basis for the theory of simplicial homology, which in turn will lead you to general homology and cohomology theories.
akoboldfrying 294 days ago [-]
> To show that detM
is non-zero, we can show that its 2-adic valuation is nonzero.
I think the last word in that sentence should be "finite"?
Also do I understand correctly that "face" means "maximal line segment"? (I see some other comments discussing this and concluding that "face" means "edge", but to me, an "edge" doesn't permit "intermediate" vertices.)
erooke 293 days ago [-]
> Also do I understand correctly that "face" means "maximal line segment"?
In the statement of Sperners lemma this seems to be how he means it. You have a triangle who's faces have been subdivided. The face he is referring to is the face before subdivision I think.
This lines up with the usual statement I'm familiar with for Sperners lemma which involves triangulating an n-simplex.
hswanson 292 days ago [-]
Yep, you're right on both counts; I've updated the page with those corrections. Thanks!
prof-dr-ir 294 days ago [-]
> no face of P, nor any face of one of the Ti, contains vertices of all three colors
That should be 'edge', not 'face', no? Otherwise I do not understand what is happening at all with the examples.
dmurray 294 days ago [-]
Yes, this would more normally be called "edge". It's not incorrect to call it a face, by analogy with higher-dimensional solids, but confusing.
FabHK 293 days ago [-]
Maybe they called it "face" and not "edge" because an edge is normally understood to be what's between two vertices (of a graph; so an edge has two vertices, beginning and end), while here "face" is what's between two corners of a given triangle (so a face can contain more than two vertices, and so multiple edges).
See the bottom "face" of the top centre triangle in the 4 examples.
hswanson 292 days ago [-]
Yeah, that's exactly it! "Face" is the term used in the original paper, so that's what I was using. I've updated the page to make the distinction clearer. Thanks!
drewcoo 293 days ago [-]
They're dealing with planar graphs, graphs embedded in planes. Faces are not edges.
It seems a lot of impossibility theorems - the type that the ancient Greeks would have understood - can be proven using algebraic topology. Perhaps Sperner's lemma can be seen as an algebraic topology theorem? I don't personally know.
I think the last word in that sentence should be "finite"?
Also do I understand correctly that "face" means "maximal line segment"? (I see some other comments discussing this and concluding that "face" means "edge", but to me, an "edge" doesn't permit "intermediate" vertices.)
In the statement of Sperners lemma this seems to be how he means it. You have a triangle who's faces have been subdivided. The face he is referring to is the face before subdivision I think.
This lines up with the usual statement I'm familiar with for Sperners lemma which involves triangulating an n-simplex.
That should be 'edge', not 'face', no? Otherwise I do not understand what is happening at all with the examples.
See the bottom "face" of the top centre triangle in the 4 examples.
https://en.wikipedia.org/wiki/Planar_graph#Euler's_formula