Arrow Research search

Author name cluster

Theo McKenzie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers
1 author row

Possible papers

3

STOC Conference 2021 Conference Paper

Support of closed walks and second eigenvalue multiplicity of graphs

  • Theo McKenzie
  • Peter Michael Reichstein Rasmussen
  • Nikhil Srivastava

We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded by O ( n Δ 7/5 /log 1/5− o (1) n ) for any Δ, and improve this to O ( n log 1/2 d /log 1/4− o (1) n ) for simple d -regular graphs when d ≥ log 1/4 n . In fact, the same bounds hold for the number of eigenvalues in any interval of width λ 2 /log Δ 1− o (1) n containing the second eigenvalue λ 2 . The main ingredient in the proof is a polynomial (in k ) lower bound on the typical support of a closed random walk of length 2 k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.

Details