Toby Johnson

Papers

Quantitative small subgraph conditioning. arXiv

With Elliot Paquette.

In the early nineties, Robinson and Wormald invented something called the small subgraph conditioning method to prove that almost all regular graphs contain a Hamiltonian cycle. Janson explained that their method actually proves the contiguity of two related models of random regular graphs, which means that events that occur for one model with probability approaching 1 do so for the other model as well. All of these results are asymptotic: they don't say anything about a random regular graph of degree d on n vertices until you let n approach infinity.

We rework the method so that it's quantitative and makes non-asymptotic statements. Among other things, this lets us vary d and n simultaneously. We estimate how quickly the probability of containing a Hamiltonian cycle tends to 1. We also compute the limiting distribution of number of Hamiltonian cycles when d grows with n (Janson computed it for fixed d), and we prove that you can approximately count the number of Hamiltonian cycles as a function of a graph's eigenvalues for almost all regular graphs.

Cycles and eigenvalues of sequentially growing random regular graphs.arXiv

With Soumik Pal. To appear in Annals of Probability.

It's possible to embed random regular graphs of all sizes as a single stochastic process of growing random graphs. This is analogous to looking not just at a single random matrix, but at a sequence of random matrix minors, whose eigenvalues converge (after the right rescalings) to the Gaussian free field, the usual limiting object of random surfaces. The goal of this paper is to find out if the same thing is true for random regular graphs. The answer, roughly speaking, is yes.

Exchangeable pairs, switchings, and random regular graphs. arXiv

Submitted.

The previous paper, Functional limit theorems for random regular graphs, looked at a model of random regular graph built up from random permutations. Combinatorialists most commonly look at random regular graphs drawn uniformly from the set of all regular graphs. This paper extends those results on linear eigenvalue fluctuations to this model. In the course of this, we explore a connection between Stein's method and the combinatorial method of switchings, both of which are used for distributional approximation.

Functional limit theorems for random regular graphs. arXiv

With Ioana Dumitriu, Soumik Pal, and Elliot Paquette.
Probab. Theory Related Fields, 156(3–4):921–975, 2013.

In 1981, McKay found the limiting empirical spectral distribution of a random regular graph as its number of vertices tends to infinity. This lets you compute limits of linear eigenvalue statistics, which are the quantities obtained by applying a function to each of the graph's eigenvalues and summing. These limits are deterministic, even though the graph is random, just as the limiting proportion of coin flips that come up heads is deterministic.

We look at the fluctuations of linear eigenvalue statistics from their limits. This sort of thing is usually Gaussian in the limit, but when the degree of the random graph remains fixed as the number of vertices grows, we find a different limiting distribution. When the degree grows, we do get Gaussian fluctuation. The main motivation of this work is comparing the spectral behavior of random regular graphs to Wigner matrices. Our approach to proving all of this is to analyze the combinatorial structure of the graph using Stein's method.

The Marčenko-Pastur law for sparse random bipartite biregular graphs. arXiv

With Ioana Dumitriu. Submitted.

The spectral behavior of random regular graphs is something like that of Wigner matrices, the simplest model of random symmetric matrix. So, what about the bipartite graph analogue of random regular graphs? The answer is that they act like Wishart matrices, whose limiting empirical spectral distributions are given by the Marčenko-Pastur law.

On universal cycles for multisets. arXiv

With Glenn Hurlbert and Josh Zahl. Discrete Math., 309::5321–5327, 2009.

I wrote this as an undergraduate after spending the summer doing an REU at East Tennessee State University with Anant Godbole. Anant is a wonderful person and I had a great time there. The paper gives three different proofs that for certain values of k, l, and n, you can construct a length n string from the alphabet {1, ..., l} such that as a length k window slides down the string, every k-multiset of {1, ..., l} appears exactly once.

Cache-Oblivious Traversals of an Array's Pairs. pdf

Unpublished.

Suppose you want to perform some operation on every pair of elements in a list. As you go through the list, your computer caches its elements. What order of traversal through the array's pairs optimizes the algorithm? We give a theoretical answer to this question. This answer actually works faster in practice, too.

This was my undergraduate senior project, done under the supervision of Dan Spielman. It's not published, so I wanted to put it up somewhere to preserve it.