Disjoint Pairs in Set Systems and the Combinatorics of Low-Rank Matrices

Explore advanced combinatorial mathematics in this seminar lecture that addresses fundamental problems in set systems and low-rank matrix theory. Delve into the solution of several interconnected problems involving set families in 2^[n] with numerous disjoint pairs and low-rank matrices containing many zero entries. Examine the resolution of a longstanding question by Daykin and Erdős concerning the maximum number of disjoint set pairs, and discover the proof of a conjecture by Singer and Sudan that was motivated by the log-rank conjecture in communication complexity. Learn about tight bounds for a problem posed by Alon, Gilboa, and Gueron, which relates to enduring questions in coding theory regarding cover-free families. Understand how probabilistic methods, entropy techniques, and discrepancy theory combine to solve these problems, while uncovering surprising connections to additive combinatorics and coding theory. Gain insights into cutting-edge research that bridges discrete mathematics, theoretical computer science, and information theory through rigorous mathematical analysis and innovative proof techniques.