4 ms·
This is in fact a very common proof strategy in combinatorics, often known as the probabalistic method. Naturally it was invented by Paul Erdos
by bodhiandphysics 4y ago
This 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.