Georgia Institute of Technology College of Sciences

Previous work of Chan-Church-Grochow and Baker-Wang shows that the set of spanning trees in a plane graph $G$ is naturally a torsor for the Jacobian group of $G$. Informally, this means that the set of spanning trees of $G$ naturally forms a group, except that there is no distinguished identity element. We generalize this fact to graphs embedded on orientable surfaces of arbitrary genus, which can be identified with ribbon graphs. In this generalization, the set of spanning trees of $G$ is replaced by the set of spanning quasi-trees of the ribbon graph, and the Jacobian group of $G$ is replaced by the Jacobian group of the associated regular orthogonal matroid $M$.

Our proof shows, more generally, that the family of "BBY torsors'' constructed by Backman-Baker-Yuen and later generalized by Ding admit natural generalizations to regular orthogonal matroids. In addition to shedding light on the role of planarity in the earlier work mentioned above, our results represent one of the first substantial applications of orthogonal matroids to a natural combinatorial problem about graphs. 

 Joint work with Matt Baker and Donggyu Kim. 

The smooth fine curve graph of a surface provides a combinatorial perspective to study the action of maps on smooth curves in the surface. It is natural to guess that the automorphism group of the smooth fine curve graph is isomorphic to the diffeomorphism group of the surface. But it has recently been shown that this is not the case. In this talk, I will give several more examples with increasingly wild behavior and give a characterization of this automorphism group for the particular case of continuously differentiable curves.

Committee:

• Dan Margalit (advisor)
• John Etnyre
• Jen Hom
• Igor Belegradek 
• Michael Wolf

Suppose that particles are randomly distributed in $R^d$, and they are subject to identical stochastic motion independently of each other. The Smoluchowski process describes fluctuations of the number of particles in an observation region over time. The goal is to infer on particle displacement process from such count data. We discuss probabilistic properties of the Smoluchowski processes and consider related statistical problems for two different models of the particle displacement process: the undeviated uniform motion (when a particle moves with random constant velocity along a straight line) and the Brownian motion displacement. In these settings we develop estimators with provable accuracy guarantees.

Primitive integral Apollonian circle packings are fractal arrangements of tangent circles with integer curvatures.  The curvatures form an orbit of a 'thin group,' a subgroup of an algebraic group having infinite index in its Zariski closure.  The curvatures that appear must fall into a restricted class of residues modulo 24. The twenty-year-old local-global conjecture states that every sufficiently large integer in one of these residue classes will appear as a curvature in the packing. We prove that this conjecture is false for many packings, by proving that certain quadratic and quartic families are missed. The new obstructions are a property of the thin Apollonian group (and not its Zariski closure), and are a result of quadratic and quartic reciprocity, reminiscent of a Brauer-Manin obstruction. Based on computational evidence, we formulate a new conjecture.  This is joint work with Summer Haag, Clyde Kertzer, and James Rickards.  Time permitting, I will discuss some new results, joint with Rickards, that extend these phenomena to certain settings in the study of continued fractions.

Randomized Kaczmarz methods — popular special case of the sketch-and-project optimization framework — solve linear systems through iterative projections onto randomly selected equations, resulting in exponential expected convergence via cheap, local updates. While known to be effective in highly overdetermined problems or under the restricted data access, identifying generic scenarios where these methods are advantageous compared to classical Krylov subspace solvers (e.g., Conjugate Gradient, LSQR, GMRES) remained open. In this talk, I will present our recent results demonstrating that properly designed randomized Kaczmarz (sketch-and-project) methods can outperform Krylov methods for both square and rectangular systems complexity-wise. In addition, they are particularly advantageous for approximately low-rank systems common in machine learning (e.g., kernel matrices, signal-plus-noise models) as they quickly capture the large outlying singular values of the linear system. Our approach combines novel spectral analysis of randomly sketched projection matrices with classical numerical analysis techniques, such as including momentum, adaptive regularization, and memoization.

What is the smallest number of edges that a graph can have if it contains all $D$-degenerate graphs on $n$ vertices as subgraphs? A counting argument shows that this number is at least of order $n^{2−1/D}$, assuming n is large enough. We show that this is tight up to a polylogarithmic factor.

Joint work with Peter Allen and Julia Böttcher.