The entropy method has been used in many recent works in extremal combinatorics. With the help of Shannon entropy, significant progress has been made on several classical problems, such as the union-closed conjecture and the Sidorenko conjecture. In our recent work, we use the entropy method to give new proofs of the Kruskal–Katona theorem and Turán’s theorem, as well as some of their generalizations. The new ingredient in our approach is a method for upper bounding the sum of $2^{\mathbb{H}(X_i)}$ for random variables $X_1,\cdots,X_k$ whose supports do not overlap too much. We call this method the mixture bound, and it can be viewed as an entropic version of double counting. In this talk, I will introduce the mixture bound and show some examples of how it can be applied on colorful versions of the Kruskal–Katona theorem. Base on joint work with Maya Sankar and Hung-Hsun Hans Yu.
Ting-Wei Chao (趙庭偉) gave a talk on the number of points that are intersections of d linearly independent lines among given n lines in the d-dimensional space at the Discrete Math Seminar
On December 12, 2023, Ting-Wei Chao (趙庭偉) from Carnegie Mellon University gave a talk at the Discrete Math Seminar on the number of points that are intersections of d linearly independent lines among given n lines in the d-dimensional space. The title of his talk was “Tight Bound on Joints Problem and Partial Shadow Problem“.
Ting-Wei Chao (趙庭偉), Tight Bound on Joints Problem and Partial Shadow Problem
Given a set of lines in $\mathbb R^d$, a joint is a point contained in d linearly independent lines. Guth and Katz showed that N lines can determine at most $O(N^{3/2})$ joints in $\mathbb R^3$ via the polynomial method.
Yu and I proved a tight bound on this problem, which also solves a conjecture proposed by Bollobás and Eccles on the partial shadow problem. It is surprising to us that the only known proof of this purely extremal graph theoretic problem uses incidence geometry and the polynomial method.