***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Istvan Tomon (Ůmea U)

Thursday 2nd May, 3:00 in Fine Hall 224.

Title: Graph discrepancy, minimum bisections, and the log-rank conjecture
    
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’s bound on the log-rank conjecture. 

Joint work with Eero Räty and Benny Sudakov.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)