Tag Archives: interlacing

Spectral proofs of theorems on the boolean hypercube

In a recent breakthrough Hao Huang proved the sensitivity conjecture, that had remained open for past 30 years despite some serious effort from various computer scientists and mathematicians. The proof can be described in a single tweet (if you have … Continue reading

Posted in Combinatorics, Extremal Combinatorics, Spectral Graph Theory | Tagged , , , , , , , | 5 Comments

Incidence Bounds and Interlacing Eigenvalues

The Szemerédi–Trotter theorem is one of the central results in discrete geometry which gives us a (tight) bound on the number of incidences, i.e., the number of point-line pairs with the point lying on the line, between finite sets of points and lines … Continue reading

Posted in Combinatorics, Finite Geometry, Incidence Geometry, Spectral Graph Theory | Tagged , , , , , , | 5 Comments