Category Archives: Spectral Graph Theory

Strong blocking sets and minimal codes from expander graphs

Posted on May 25, 2023 by Anurag Bishnoi

Finite geometry is often used to construct graphs with certain extremal properties. For example, the Norm graphs are one of the best-known constructions in extremal graph theory (see this for a geometrical description of these graphs). Similarly, generalized polygons, and … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Spectral Graph Theory | Tagged , , , , , , , , , | Leave a comment

Kopparty’s graph

Posted on December 18, 2019 by Anurag Bishnoi

Alon’s construction of optimal pseudorandom graphs from 1994 is useful for obtaining several interesting combinatorial results in various areas of mathematics, some of which are highlighted in this survey of Noga from last year (also see my previous post). In … Continue reading →

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

Spectral proofs of theorems on the boolean hypercube

Posted on July 27, 2019 by Anurag Bishnoi

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

Pseudorandom clique-free graphs

Posted on May 15, 2019 by Anurag Bishnoi

Pseudorandom graphs are graphs that in some way behaves like a random graph with the same edge density. One way in which this happens is as follows. In the random graph , with , a direct application of Chernoff bound … Continue reading →

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

The cage problem and generalized polygons (part 1)

Posted on August 9, 2017 by Anurag Bishnoi

This post is a continuation of my previous post on the cage problem. Just to recall the main problem, for any given integers and , we want to find the least number of vertices in a simple undirected graph which … Continue reading →

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry, Spectral Graph Theory | Tagged , , , , | Leave a comment

Expander Mixing Lemma in Finite Geometry

Posted on April 2, 2017 by Anurag Bishnoi

In this post I will discuss some nice applications of the expander mixing lemma in finite incidence geometry, including a new result that I have obtained recently. In many of the applications of the lemma in finite geometry, the graph is bipartite, and … Continue reading →

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

Incidence Bounds and Interlacing Eigenvalues

Posted on September 26, 2016 by Anurag Bishnoi

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