4 ms·
Most of this proof is very dense. But Theorem 7 seems like an interesting tactic that allows the authors to infer nonexistence from rarity: >Theorem 7. If ther
by scythe 4y ago
Most of this proof is very dense. But Theorem 7 seems like an interesting tactic that allows the authors to infer nonexistence from rarity:
>Theorem 7. If there is a map L which cannot be 4-coloured then only an exponentially small fraction of the maps with n edges can be 4-coloured.
It's one of those things that seems obvious in retrospect — of course large random graphs should be likely to contain any particular graph! But it hadn't occurred to me in my own (very amateur) considerations of the problem.
Will be interesting to see if it's correct. We've gone from an argument too long for a human to read to one in just seven pages.
- bodhiandphysics 4y agoThis is in fact a very common proof strategy in combinatorics, often known as the probabalistic method. Naturally it was invented by Paul Erdos
- sweezyjeezy 4y agoI think that's a bit different - in the probabilistic method you show that if you randomly sample a graph (say) then the probability of it having some property is > 0 - therefore there must exist some graph having the property. Theorem 7 in their paper is trying to count the number of graphs that contain a hypothetical 4-color counterexample if it exists. It's done by hitting a suitable generating function with a big analysis hammer to bound its coefficients, not by probabilistic means.