Open problem session of HUJI-COMBSEM: Problem #3, Ehud Friedgut – Independent sets and Lionel Levine’s infamous hat problem.

Posted on December 12, 2020 by Gil Kalai

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 G let \alpha (G) be its independence number, namely the maximum  size of an independent set of vertices in G. Now consider a random subset W of the set V of vertices of G. A vertex v \in V belongs to W with probability 1/2, independently.  Now let H be the induced graph from G on W. Denote by \alpha^-(G) the expected value of \alpha (H) over all such random induced subgraphs H.

Conjecture: For every real number \tau, 0<\tau<1 there is \epsilon(\tau ) >0 such that if \alpha (G) =\tau n then \alpha^-(G) \le (\tau-\epsilon(\tau ))n.

If we look at the example G of the complete graph on 1/τ vertices we get that \alpha^-(G) =  (1-2^{-1/\tau}). The reason is that the independence number of G is always 1 except in one case occurring with probability 2^{-1/\tau} where W is empty.

An example coming from a random graph G(n,p)  gives that \epsilon (\tau)  = \tau (1-2^{c(-1/\tau)\cdot (\log (1/\tau)}) and the strong conjecture is that \epsilon(\tau ) can be taken to be 2^{C(-1/\tau)\cdot  (\log (1/\tau)}. (Here, c,C are constants.)

LIONEL LEVINE

Problem 2: Lionel Levine’s infamous hat problem.

Warm up problem:

n 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 p_k be the success probability for k players. (Remark: instead of having infinite number of hats we can assume that k is fixed, each player has n hats, and then let n goes to infinity.

Ehud explained why 1/3 \le p_2 \le 3/8. He challenged the audience to prove that p_3 < p_2 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”

Below: Ehud and Guy

This entry was posted in Combinatorics, Computer Science and Optimization, Probability and tagged , , . Bookmark the permalink.

7 Responses to Open problem session of HUJI-COMBSEM: Problem #3, Ehud Friedgut – Independent sets and Lionel Levine’s infamous hat problem.

  1. Gil Kalai says:
    December 12, 2020 at 11:47 pm

    A nice comment on twitter

    Reply
  2. Ross K says:
    December 13, 2020 at 12:51 pm

    The problem that Huck Bennett mentions has a concrete form due to Boris Bukh (see the “brain” tab of his webpage), namely, that Exp(\chi(G_{1/2})) \ge c \chi(G)/\log\chi(G). That’s a very nice problem.

    Reply
  3. Nikhil says:
    December 14, 2020 at 10:44 am

    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.

    Reply
  4. Jim Roche says:
    December 27, 2020 at 6:15 am

    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.

    Reply
  5. Jim Roche says:
    December 27, 2020 at 6:28 am

    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.

    Reply

  6. 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

Leave a comment