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

Earlier problems in this series: #1 Nati Linial; #2 Chaya Keller; videotaped session.

## 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”

A nice comment on twitter

For the full thread:

The problem that Huck Bennett mentions has a concrete form due to Boris Bukh (see the “brain” tab of his webpage), namely, that That’s a very nice problem.

In problem #1, when G is the complete graph, shouldn’t \alpha^-(G) be equal to (1-2^{-1/\tau}), acc. to the definition?

GK: You are right! corrected.Regarding Problem 2: As noted in the paper by Kariv, val Alten, and Yeroshkin, Chris Freiling showed with a clever “hint” technique that p_2 = 0.35 as n -> \infty. (Freiling described his upper bound in June 2015 at the Summer Symposium in Real Analysis in Northfield, MN.) In Dec 2014 (unpublished) I adapted Freiling’s upper bound and showed that p_3 <= 89/256 < 0.348 \infty). This result and numerous other partial results flew back and forth in e-mails between a number of us working on variants of Levine’s problem in 2014 and 2015.

Crikey, my previous comment got garbled, maybe because of some special character. It’s known that p_2 is at least 0.35 as n becomes infinite, and Freiling showed that p_2 is at most 81/224 \approx 0.362. I adapted Freiling’s upper bound in Dec 2014 to show that p_3 is at most 89/256, which is less than 0.348, hence strictly less than p_2 for all large enough n. This is unpublished, but I could dig up the details.

Pingback: To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols | Combinatorics and more