Georgia Institute of Technology College of Sciences

The Heisenberg projection problem asks whether there is an analogue of the Marstrand projection theorem in the first Heisenberg group, namely whether Hausdorff dimension of sets generically decreases under projection, for a natural family of projections arising from the group structure. This problem is still open, but I will discuss a recent improvement to the known bound obtained through a variable coefficient local smoothing inequality. 

Rather than going through the proof in detail, I will spend most of the talk introducing the problem and explaining the connection to averaging operators over curves, and explaining why these operators are Fourier integral operators satisfying Sogge's cinematic curvature condition. This condition was originally introduced by Sogge to generalise Bourgain's circular maximal theorem, but it turns out to have useful applications to projection theory. 

Suppose that a continuous-time, stochastic diffusion (i.e., the Susceptible-Infected process) spreads on an unknown graph. We only observe the time at which the diffusion reaches each vertex, i.e., the set of infection times. What can be learned about the unknown graph from the infection times? While there is far too little information to learn individual edges in the graph, we show that certain high-level properties -- such as the number of vertices of sufficiently high degree, or super-spreaders -- can surprisingly be determined with certainty. To achieve this goal, we develop a suite of algorithms that can efficiently detect vertices of degree asymptotically greater than sqrt(n) from infection times, for a natural and general class of graphs with n vertices. To complement these results, we show that our algorithms are information-theoretically optimal: there exist graphs for which it is impossible to tell whether vertices of degree larger than n^{1/2 - \epsilon} exist from vertices' infection times, for any \epsilon > 0. Finally, we discuss the broader implications of our ideas for change-point detection in non-stationary point processes. This talk is based on joint work with Anna Brandenberger (MIT) and Elchanan Mossel (MIT).

Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al. Our approach combines Sapozhenko’s graph container method with entropy techniques from information theory.

This is joint work with Krueger and Park.