TMTheo McKenzie

Theo McKenzie

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Theo McKenzie has a total of 16 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • The Spectral Edge of Constant Degree Erdős–Rényi Graphs

    by Ella Hiesmayr, Theo McKenzie

    We show that for an Erdős–Rényi graph on vertices with expected degree satisfying , the largest eigenvalues can be precisely determined by small neighborhoods around vertices of close to maximal degree. Moreover, under the added condition that , the corresponding eigenvectors are localized, in that the mass of the eigenvector decays exponentially away from the high degree vertex. This dependence on local neighborhoods implies that the edge eigenvalues converge to a Poisson point process. These theorems extend a result of Alt, Ducatez, and Knowles, who showed the same behavior for satisfying and answer a question of Guionnet. To achieve high accuracy in the constant degree regime, instead of comparing the true eigenvector to that of a tree with more regularity, we examine the eigenvector equation at each vertex in a ball to deduce localization of the eigenvector and derive a continued fraction formula for the eigenvalue. This formula can be applied to any tree and could be of independent interest, especially for rooted trees with large central degree.


  • Open Access

    Arbitrary Spectral Edge of Regular Graphs

    by Dingding Dong, Theo McKenzie

    We prove that for each $d\geq 3$ and $k\geq 2$, the set of limit points of the first $k$ eigenvalues of sequences of $d$-regular graphs is \[ \{(μ_1,\dots,μ_k): d=μ_1\geq \dots\geq μ_{k}\geq2\sqrt{d-1}\}. \] The result for $k=2$ was obtained by Alon and Wei, and our result confirms a conjecture of theirs. Our proof uses an infinite random graph sampled from a distribution that generalizes the random regular graph distribution. To control the spectral behavior of this infinite object, we show that Huang and Yau's proof of Friedman's theorem bounding the second eigenvalue of a random regular graph generalizes to this model. We also bound the trace of the non-backtracking operator, as was done in Bordenave's separate proof of Friedman's theorem.

  • Open Access

    Explicit Two-Sided Unique-Neighbor Expanders

    by Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes

    We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes. Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product and the routed product of previous well-known works. To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing previously known results, which may be of independent interest. By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of (d1,d2)-biregular graphs (Gn)n≥ 1 (for large enough d1 and d2) where all sets S with fewer than a small constant fraction of vertices have Ω(d1· |S|) unique-neighbors (assuming d1 ≤ d2). Additionally, we can also guarantee that subsets of vertices of size up to exp(Ω(√log|V(Gn)|)) expand losslessly.


  • Open Access

    Optimal Eigenvalue Rigidity of Random Regular Graphs

    by Jiaoyang Huang, Theo McKenzie, Horng-Tzer Yau

    Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\geq 3$, and denote the eigenvalues as $λ_1=d/\sqrt{d-1}\geq λ_2\geqλ_3\cdots\geq λ_N$. We prove that the optimal (up to an extra $N^{{\rm o}_N(1)}$ factor, where ${\rm o}_N(1)$ can be arbitrarily small) eigenvalue rigidity holds. More precisely, denote $γ_i$ as the classical location of the $i$-th eigenvalue under the Kesten-Mckay law in decreasing order. Then with probability $1-N^{-1+{\rm o}_N(1)}$, \begin{align*} |λ_i-γ_i|\leq \frac{N^{{\rm o}_N(1)}}{N^{2/3} (\min\{i,N-i+1\})^{1/3}},\quad \text{ for all } i\in \{2,3,\cdots,N\}. \end{align*} In particular, the fluctuations of extreme eigenvalues are bounded by $N^{-2/3+{\rm o}_N(1)}$. This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble.

  • Nodal Decompositions of a Symmetric Matrix

    by Theo McKenzie, John Urschel

    Analyzing nodal domains is a way to discern the structure of eigenvectors of operators on a graph. We give a new definition extending the concept of nodal domains to arbitrary signed graphs, and therefore to arbitrary symmetric matrices. We show that for an arbitrary symmetric matrix, a positive fraction of eigenbases satisfy a generalized version of known nodal bounds for un-signed (that is classical) graphs. We do this through an explicit decomposition. Moreover, we show that with high probability, the number of nodal domains of a bulk eigenvector of the adjacency matrix of a signed Erdős-Rényi graph is |$\Omega (n/\log n)$| and |$o(n)$|⁠.


  • Open Access

    Explicit two-sided unique-neighbor expanders

    by Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes

    We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes. Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product in the work of Alon and Capalbo and the routed product in the work of Asherov and Dinur. To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing results of Kahale, which may be of independent interest. By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of $(d_1,d_2)$-biregular graphs $(G_n)_{n\ge 1}$ (for large enough $d_1$ and $d_2$) where all sets $S$ with fewer than a small constant fraction of vertices have $Ω(d_1\cdot |S|)$ unique-neighbors (assuming $d_1 \leq d_2$). Additionally, we can also guarantee that subsets of vertices of size up to $\exp(Ω(\sqrt{\log |V(G_n)|}))$ expand losslessly.

  • Open Access

    Nodal decompositions of a symmetric matrix

    by Theo McKenzie, John Urschel

    Analyzing nodal domains is a way to discern the structure of eigenvectors of operators on a graph. We give a new definition extending the concept of nodal domains to arbitrary signed graphs, and therefore to arbitrary symmetric matrices. We show that for an arbitrary symmetric matrix, a positive fraction of eigenbases satisfy a generalized version of known nodal bounds for un-signed (that is classical) graphs. We do this through an explicit decomposition. Moreover, we show that with high probability, the number of nodal domains of a bulk eigenvector of the adjacency matrix of signed a Erdős-Rényi graph is $Ω(n/\log n)$ and $o(n)$.

  • Open Access

    The Spectral Edge of Constant Degree Erdős-Rényi Graphs

    by Ella Hiesmayr, Theo McKenzie

    We show that for an Erdős-Rényi graph on $N$ vertices with expected degree $d$ satisfying $\log^{-1/9}N\leq d\leq \log^{1/40}N$, the largest eigenvalues can be precisely determined by small neighborhoods around vertices of close to maximal degree. Moreover, under the added condition that $d\geq\log^{-1/15}N$, the corresponding eigenvectors are localized, in that the mass of the eigenvector decays exponentially away from the high degree vertex. This dependence on local neighborhoods implies that the edge eigenvalues converge to a Poisson point process. These theorems extend a result of Alt, Ducatez, and Knowles, who showed the same behavior for $d$ satisfying $(\log\log N)^4\ll d\leq (1-o_{N}(1))\frac{1}{\log 4-1}\log N$. To achieve high accuracy in the constant degree regime, instead of attempting to guess an approximate eigenvector of a local neighborhood, we analyze the true eigenvector of a local neighborhood, and show it must be localized and depend on local geometry.

  • Open Access

    Support of closed walks and second eigenvalue multiplicity of graphs

    by 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/log1/5−o(1)n) for any Δ, and improve this to O(nlog1/2d/log1/4−o(1)n) for simple d-regular graphs when d≥ log1/4n. 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 2k 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.