(After I wrote this post Lance tweeted a pointer to a great talk by Ronald de Wolf with more examples, and also examples of quantum proofs, see here.)
I was teaching the prob method for lower bounds on Ramsey Numbers (see my slides here).
As often happens, a student said:
That's not a new technique--- you're just counting.
My response
1) For this example, it can be rephrased as counting, but there is no advantage in that.
2) There are other examples where either
a) You could rephrase it as counting but it's MUCH EASIER to use probability, or
b) You really CANNOT rephrase as counting.
And I came prepared-I presented the following result (see my slides here):
Theorem: Let \(G\) be a graph on \(n\) vertices where every vertex has degree \( \ge d \). Then \(G\) has a dominating set of size
\( \le n \frac{\ln(d+1)+1}{d+1} \).
The proof uses that \( E(X+Y)=E(X)+E(Y) \). I cannot see a way to make the argument into a counting argument. Clearly 2a is true. It may even be that 2b is true, though that would be hard to formalize.
The student admitted that yes, the Dom Set Theorem either could not be rephrased as a counting argument or it would be hard to do so.
Can you make it into a counting argument? Would you want to bother?
No comments:
Post a Comment