Computer Science/Discrete Mathematics Seminar I

In this talk, I will discuss the solution to several problems in two closely related settings: set families in 2^[n] with many disjoint pairs, and low-rank matrices with many zero entries.

Highlights include a resolution of an old question of Daykin and Erdős on the maximum number of disjoint set pairs, a proof of a conjecture by Singer and Sudan motivated by the log-rank conjecture in communication complexity, and tight bounds for a problem posed by Alon, Gilboa, and Gueron related to a long-standing question in coding theory about cover-free families.

Our proofs use probabilistic, entropy, and discrepancy methods, revealing connections to additive combinatorics and coding theory.

Joint with Z. Hunter, A. Milojević and I. Tomon.