
Disjoint Pairs in Set Systems and the Combinatorics of Low-Rank Matrices
Benjamin Sudakov of ETH Zürich presents this Institute for Advanced Study discrete mathematics seminar on extremal set theory and matrix combinatorics. He covers the resolution of a longstanding question posed by Daykin and Erdős on the maximum number of disjoint pairs among set families in 2^[n], a proof of a conjecture by Singer and Sudan tied to the log-rank conjecture in communication complexity, and tight bounds for a problem raised by Alon, Gilboa, and Gueron connected to cover-free families in coding theory. Sudakov walks through the probabilistic, entropy, and discrepancy arguments underlying these results, drawing out links to additive combinatorics along the way. The work is joint with Z. Hunter, A. Milojević, and I. Tomon. Delivered to a research audience at the Simonyi Hall, the talk assumes familiarity with combinatorics and gives a condensed tour of several recently solved open problems.