(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?
E(.) operator is counting again.
ReplyDeleteHow do you prove this using the linearity of expectation? You need to upper bound the probability that a fixed vertex is not covered, then union bound over all of them...
ReplyDeleteI think this counts as a counting proof:
ReplyDeleteConsider a greedy algorithm that always adds to the solution a node whose addition would dominated the largest number of yet undominated nodes (note that such a node could have been already dominated itself, and the algorithm would still select it).
We claim that in each iteration the number of undominated nodes drops by a factor of (d+1)/n. That is, if after some steps we are left with k undominated nodes, then in the next step we need to pick a node that dominates at least k(d+1)/n new nodes. Consider pairs (u, v) such that u is an undominated node and v is in its closed neighborhood – i.e., picking v would put u in the set of dominated nodes. Each u has at least d+1 v's. So the number of such pairs is at least k(d+1). On the other hand, there are at most n v's, so an average v dominates at least k(d+1)/n u's, and hence also the best v dominates at least that many.
Using this claim, after t steps we are left with at most n(1-(d+1)/n)^t undominated nodes. Plugging in t=nln(d+1)/(d+1) leaves us with n/(d+1) nodes, which then get dominated in at most n/(d+1) more steps.
This is (a condensed version of) a proof that ChatGPT spits out. It can be also found in some slides available online, e.g., https://people.willamette.edu/~jlaison/Domination-Jose.pdf (pages 19–20).
I am hereby posting these subject infer of method thank you so
ReplyDelete