Timeline for Problems where we can't make a canonical choice, solved by looking at all choices at once
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2010 at 16:15 | comment | added | Zev Chonoles | I suppose I was only really looking for examples of this kind of argument, not only cases where it was necessary. Though of course it's quite interesting that there are other proofs - perhaps there's a general process for turning any instance of an averaging argument like this one into a constructive argument, like the one gowers mentions, or a canonical choice, like the one Tony mentions. | |
| Dec 21, 2010 at 13:45 | comment | added | Tony Huynh | I would have to agree with gowers. There is a canonical choice. Namely, just take a colouring with the most bicoloured edges. Then it is easy to prove that at least half the edges are bicoloured. If not, then some white vertex v has more white neighbours than black neighbours. Switch the colour of v to obtain a contradiction. For the historical record, this problem is known as the affirmative action problem. See this applet if you want to experiment with Tim's idea | |
| Dec 21, 2010 at 9:36 | comment | added | gowers | I'm not sure this argument quite fits the bill because there are other proofs. For example, add a vertex one at a time and choose its colour to be different from already added neighbours at least as often as it is the same. Thus, in this case averaging is somehow not essential, even if it happens to work very neatly. | |
| Dec 21, 2010 at 5:53 | comment | added | Zev Chonoles | I agree; that's why I felt this answer was particularly good (given Steven's added explanation), because it isn't arguing about an intuitive/probabilistic notion of "average" choice, and it isn't trying to construct a canonical 2-coloring such that (etc.) for every graph - it really is looking at the collection of all colorings at once, and deducing the existence of a specific coloring. Admittedly, since I could not clearly put into words what I was thinking of, I think I should be flexible with what answers could be deemed as answering my question. | |
| Dec 21, 2010 at 5:20 | comment | added | Qiaochu Yuan | Zev, it seems to me the point of the probabilistic method is not that one is trying to avoid making non-canonical choices but that one is trying to avoid making choices that are too simple: at least in many applications, the search space is very complicated and it is easier to search it randomly than deterministically. | |
| Dec 21, 2010 at 5:00 | comment | added | Zev Chonoles | Very neat! Exactly the kind of result I was thinking of. | |
| Dec 21, 2010 at 4:59 | comment | added | Steven Landsburg | Correction: The average of those numbers is exactly equal to E/2. If the average of a set of numbers is exactly E/2, then at least one of those numbers is at least E/2. | |
| Dec 21, 2010 at 4:58 | comment | added | Steven Landsburg | To each coloring, we associate a number --- the number of edges that are bicolored. The average of these numbers is at least equal to E/2, where E is the number of edges in the graph. If the average of a set of numbers is at least E/2, then at least one of those numbers is at least E/2. | |
| Dec 21, 2010 at 4:54 | comment | added | Zev Chonoles | Though could you clarify how we pass from the "average" coloring to at least one coloring? | |
| Dec 21, 2010 at 4:52 | comment | added | Zev Chonoles | This is a great example! | |
| Dec 21, 2010 at 4:43 | history | answered | Steven Landsburg | CC BY-SA 2.5 |