2
$\begingroup$

When reading proofs in the probabilistic method, it always seems like magic to me: Why should we invoke a probabilistic argument to prove facts about discrete objects?! So I decided to try to replace the probabilistic argument with a simpler counting argument.

To be concrete, consider the first example in the Wikipedia page: there is a complete graph on $n=5$ vertices, and we wish to show that it is possible to color its edges in two colors so that there is no complete subgraph on $r=4$ vertices which is monochromatic.

My counting argument is the following:

  • The total number of $r$-subgraphs is ${n \choose r}$.
  • Each $r$-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.
  • Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
  • Hence, the total number of colorings that are bad for all subgraphs is at most $2 {n \choose r}$.
  • Since $2^{r \choose 2} > 2 {n \choose r}$ for the numbers chosen, there must be at least one coloring which is not 'bad' for any subgraph.

This counting proof is very similar to the probabilistic proof, but it is simpler because it does not require any knowledge of probability definitions and theorems (such as the theorem about the expectation of the sum of random variables). All it requires is counting, which is a very basic human activity, so it can potentially be understood by a larger audience.

MY QUESTION IS: Is there a general equivalence between probabilistic-method and counting arguments? I.e., is it possible to convert any proof in the probabilistic method to a counting-based proof that does not use probability?

$\endgroup$
  • 1
    $\begingroup$ Why would a discrete probability distribution not be able to prove anything about discrete objects? Personally, I found Erdős's proof much easier to follow than yours (so much so that I never figured out whether yours is correct), but if you like, it could be considered a counting proof too (since taking discrete probabilities over sets of coin tosses amount to counting possible outcomes). $\endgroup$ – David K Nov 5 '14 at 19:19
  • $\begingroup$ Probability is counting. $\endgroup$ – copper.hat Nov 5 '14 at 19:27
  • $\begingroup$ One reason I think my counting proof is simpler, is because it does not rely on any previous theorems. On the contrary, the proof of Erdős relies on the theorem saying that the expectation of the sum of random variables is the sum of expectations. Why should we invoke a theorem from probability theory, when all we need is deterministic counting? $\endgroup$ – Erel Segal-Halevi Nov 6 '14 at 5:42
  • $\begingroup$ Note that linearity of expectation isn't a very hard theorem, especially in this kind of discrete case; it's basically just another way of saying "addition is commutative." $\endgroup$ – Micah Nov 6 '14 at 6:08
  • 2
    $\begingroup$ Everything is better than a counting argument. $\endgroup$ – Asaf Karagila Nov 6 '14 at 6:59
4
$\begingroup$

The first probabilistic proof on that Wikipedia page is kind of a special case, in that the probability model it uses is "each edge exists with probability 1/2", which means the distribution on the set of labeled graphs with $n$ vertices is uniform. So rephrasing it in terms of pure counting is fairly natural.

In general (and, in fact, for the second proof on that page) your random graph model is going to select different graphs with nonuniform probability. You could rewrite this without talking about probability, but it would involve defining some kind of weight function dependent on the specific properties of a graph, and then showing that the sum of the weights of all graphs that satisfy your desired property is eventually nonzero.

If you're using this kind of argument to show the existence of something, you probably want the weight of each graph to be non-negative (otherwise, there might be some kind of weird cancelation that prevents you from detecting what you're looking for). And if you're assigning a non-negative real-valued weight to each graph, you might as well normalize those weights and call them "probabilities", to leverage pre-existing theorems and intuition about how probability works...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.