Here are the two problems presented by Ehud Friedgut. The first arose by Friedgut, Kindler, and me in the context of studying Lionel Levine’s infamous hat problem. The second is Lionel Levine’s infamous hat problem.
Ehud Friedgut with a few hats
Problem 1: Independence numbers for random induced subgraphs
For a graph let be its independence number, namely the maximum size of an independent set of vertices in . Now consider a random subset of the set of vertices of . A vertex belongs to with probability 1/2, independently. Now let be the induced graph from on . Denote by the expected value of over all such random induced subgraphs .
Conjecture: For every real number , there is such that if then .
If we look at the example of the complete graph on 1/τ vertices we get that . The reason is that the independence number of is always 1 except in one case occurring with probability where is empty.
An example coming from a random graph gives that and the strong conjecture is that can be taken to be . (Here, are constants.)
Problem 2: Lionel Levine’s infamous hat problem.
Warm up problem:
people are assigned at random white/black hats, Each person sees the hats of the other and need to guess the color of her own hat. They can decide in advance on the guessing strategy and their aim is maximize the probability that they all guessed correctly. How well they can do?
It turns out that there is a strategy with 50% chance of winning. They all need to assume that there are overall an even number of black hats.
The real infamous hat problem by Lionel Levine
Now every player has an infinite tower of hats on her head and, again, the hats are taken to be white or black at random. Again each players see all the hats of other players and again the players can plan in advance a strategy for success, This time each player has to point to one of the hats on her head and the players WIN if all these hats are black.
Again, based on the hats of all others the k-th player says something like “I think the 7th hat on my head is black” or “I think the 3rd hat on my head is black” and the players win if all these statement are correct.
Conjecture: As the number of players grows the probability for success tends to zero.
Let be the success probability for players. (Remark: instead of having infinite number of hats we can assume that is fixed, each player has hats, and then let goes to infinity.
Ehud explained why . He challenged the audience to prove that which is unknown.
The problem was presented in this 2011 post on Tanya Khovanova’s Math Blog. Tanya also offered a new variant of her own. It was also July 2016 riddle further discussed here on the math riddles site “Using your head is permitted”