Raphael Yuster (Haifa) — An entropy inequality and almost k-union closed set systems

Raphael Yuster (Haifa) — An entropy inequality and almost k-union closed set systems

Raphael Yuster (Haifa) — An entropy inequality and almost k-union closed set systems

Wednesday, November 13, 2024
  • Lecturer: Raphael Yuster
  • Organizer: Chaim Even Zohar
  • Location: 814 Amado
Abstract:
We consider the following inequality relating the entropy h(p) of a Bernoulli r.v. of a single positive outcome with the entropy h(p^k) of the corresponding r.v. of k positive outcomes: phi^{k-1} h(p^k) >= p^{k-1} h(p) where phi is the positive root of x^k+x-1. The case k=2 of this inequality was recently proved by Alweiss, Huang, and Sellke and by Boppana, and served, together with a breakthrough idea of Gilmer, an important ingredient in the proof of the stability version of Frankl's union-closed conjecture by Chase and Lovett. Other applications of this inequality were recently considered by Wakhare. We prove this inequality for all 3 <= k <= 20 and prove a variant for all k where phi^{k-1} is replaced with a slightly larger constant. In fact, we show that the inequality reduces to a conjecture about the number of real roots of an explicit polynomial. We use this result to prove the k-dimensional analogue of the Chase-Lovett theorem. Parts of this work is joint with Geva Yashfe.
Print to PDF