Graph discrepancy, minimum bisections, and the log-rank conjecture
Graph discrepancy, minimum bisections, and the log-rank conjecture
-
Istvan Tomon, 女mea University
The discrepancy of a graph measures the maximum deviation of an induced subgraph from its expected size. I will talk about how to prove bounds on the discrepancy using semidefinite programming and spectral techniques.
With this, we:
(i) partially answer questions of Verstraete and Bollob谩s-Scott on positive and negative discrepancy;
(ii) greatly improve a result of Alon on the minimum bisection;
(iii) slightly improve Lovett鈥檚 bound on the log-rank conjecture.
Joint work with Eero R盲ty and Benny Sudakov.