Spectral graph bounds and expansion

Let A be the adjacency matrix. Every row sums to d, so the all-ones vector is an eigenvector of eigenvalue d. Order the remaining real eigenvalues decreasingly. To estimate edges between two disjoint vertex sets, split each indicator vector into its constant mean and a mean-zero part. The constant components produce the predicted d times the product of the set sizes divided by the graph order. The mean-zero components produce an error bounded using the operator norm on that subspace.

That norm is the largest absolute value of any nontrivial eigenvalue, not merely the second largest algebraic eigenvalue. A connected bipartite regular graph has an eigenvalue minus d, making the absolute bound as large as possible. Its alternating structure is therefore not quasirandom in the ordinary nonbipartite sense. In the mixing inequality below, the sets are disjoint and crossing edges are counted once; overlapping-set conventions need an ordered adjacency count and should be stated separately.

Define conductance as the minimum number of edges leaving a nonempty set, divided by d times its size, over sets containing at most half the vertices. Set gamma equal to one minus the second largest adjacency eigenvalue divided by d. Cheeger's inequalities compare gamma with conductance: gamma divided by two is a lower bound, while the square root of twice gamma is an upper bound. The upper bound may exceed one and then is weaker than the elementary conductance bound.

The algebraic second eigenvalue is appropriate for this bottleneck question even when the graph is bipartite. Connectivity makes gamma positive in a regular graph, but it does not keep the negative extreme eigenvalue away from minus d. Consequently expansion and absence of periodicity are different properties. Adding a holding probability to a random walk replaces A/d by a lazy transition matrix, which removes the bipartite sign oscillation while preserving its uniform stationary distribution.

An expander family needs a uniform positive expansion bound as the number of vertices grows, usually with a fixed degree or uniformly bounded degrees. Every connected finite graph has some positive boundary ratio, so calling a single graph connected does not establish the family property. Cycles illustrate the distinction: they remain connected and regular, but a long consecutive half-cycle has only two outgoing edges, making conductance tend to zero as the order grows.

Spectral information can also bound independent sets and certify that large sets cannot avoid each other. However, an inequality is informative only when its error term is smaller than the main term. For very small sets, the square-root error can dominate. In applications, compare the two scales numerically rather than treating a small relative eigenvalue as a universal guarantee at every set size. Spectral certificates summarize a graph, but a two-state illustrative chain is not a generator of graphs realizing a desired eigenvalue list.