[FOM] Re: Ham sandwiches and expanders

[Timothy Y. Chow]

Jeff Hirst emailed me some interesting comments about my question
regarding ham sandwiches and expanders.  In light of his comments,
I thought I would clarify a few things.

First of all, my choice of theorems (0-1 law for graphs, ham sandwiches,
Ramanujan graphs) wasn't arbitrary.  One way to try to find theorems that
can't be proved using weak axioms is to try to construct them specifically
with that purpose in mind.  The other way is to look around for "naturally
occurring" theorems that might fit the bill.  I was trying the latter
approach.  Combinatorialists, particularly algebraic combinatorialists,
spend a fair amount of their time considering theorems that have been
proved using techniques from other areas of mathematics and trying to find
new proofs that are more combinatorial.  This activity is not exactly the
same as reverse mathematics because there is no underlying precise
definition of what "more combinatorial" means.  However, it seems to me
that there is probably some correlation, and so I decided to look for
theorems that so far have resisted people's attempts to find combinatorial
proofs for them.

The Akiyama-Alon result is one that looks purely combinatorial but whose
only known proof, as far as I know, makes use of the ham sandwich theorem.
So it seems like a natural example to think about when trying to figure
out the proof-theoretic strength of the ham sandwich theorem.

The 0-1 law for graphs has a little bit of the flavor of the pioneering
Paris-Harrington theorem.  Namely, an ostensibly finitary question is
solved by considering a countably infinite analogue and deriving a
finitary corollary.  The proof of this theorem is simple enough that
it ought to be pretty tractable to analyze.

Maybe the best example is the existence of Ramanujan graphs.  Ramanujan
graphs are currently known only to exist for certain choices of the degree
of the graph.  In a fairly recent tour de force, Joel Friedman managed to
give a very sophisticated probabilistic proof that "almost-Ramanujan"
graphs exist for (if I remember correctly) any degree.  I can believe that
this proof could form the basis of a proof in a very weak system.  But
even Joel Friedman's proof doesn't prove the existence of Ramanujan
graphs.  As far as I know, all the proofs of the existence of Ramanujan
graphs rely on deep results about modular forms, despite a lot of effort
to find purely combinatorial proofs.

The necessary facts about modular forms follow from Deligne's proof of the
Weil conjectures.  Although the full strength of Deligne's theorem is not
needed for the existence of Ramanujan graphs, it is suggestive (at least
to me) that again, in spite of intensive efforts, Deligne's proof is the
only proof known of the (hardest of the) Weil conjectures.  In particular,
the high-powered machinery of l-adic cohomology developed in SGA4 seems to
be unavoidable.

Psychological difficulty and complexity are not, of course, the same as
proof-theoretic strength, but again I think there might be a correlation.

Tim