Speaker
Igor Balla
(Leipzig University)
Description
In this talk, we will present a proof of the fact that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We will also discuss further structural results about Boolean matrices of bounded $\gamma_2$-norm and applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics.
As a key application, we establish a theorem for MaxCut which contrasts a celebrated result of Edwards. In particular, we show that if the MaxCut of a graph with $m$ edges is at most $m/2 + O(\sqrt{m})$, then it must contain a clique of size $\Omega(\sqrt{m})$.
Authors
Igor Balla
(Leipzig University)
Istvan Tomon
(Umeå university)
Dr
Lianna Hambardzumyan
(University of Copenhagen)