Georgia Institute of Technology College of Sciences

A graph is ``strongly regular'' (SRG) if it is $k$-regular, and every pair of adjacent (resp. nonadjacent) vertices has exactly $\lambda$ (resp. $\mu$) common neighbors. Paradoxically, the high degree of regularity in SRGs inhibits their symmetry. Although the line-graphs of the complete graph and complete bipartite graph give examples of SRGs with $\exp(\Omega(\sqrt{n}))$ automorphisms, where $n$ is the number of vertices, all other SRGs have much fewer---the best bound is currently $\exp(\tilde{O}(n^{9/37}))$ (Chen--Sun--Teng, 2013), and Babai conjectures that in fact all primitive SRGs besides the two exceptional line-graph families have only quasipolynomially-many automorphisms. In joint work with Babai, Chen, Sun, and Teng, we make progress toward this conjecture by giving a quasipolynomial bound on the number of automorphisms for valencies $k > n^{5/6}$. Our proof relies on bounds on the vertex expansion of SRGs to show that a polylogarithmic number of randomly chosen vertices form a base for the automorphism group with high probability.

The problem in the talk is motivated by the following problem. Suppose we need to place sprinklers on a field to ensure that every point of the field gets certain minimal amount of water. We would like to find optimal places for these sprinklers, if we know which amount of water a point $y$ receives from a sprinkler placed at a point $x$; i.e., we know the potential $K(x,y)$. This problem is also known as finding the $N$-th Chebyshev constant of a compact set $A$. We study how the distribution of $N$ optimal points (sprinklers) looks when $N$ is large. Solving such a problem also provides an algorithm to approximate certain given distributions with discrete ones. We discuss connections of this problem to minimal discrete energy and to potential theory.

For every surface (sphere, torus, etc.) there is an associated graph called the curve graph. The vertices are curves in the surface and two vertices are connected by an edge if the curves are disjoint. The curve graph turns out to be very important in the study of surfaces. Even though it is well-studied, it is quite mysterious. Here are two sample problems: If you draw two curves on a surface, how far apart are they as edges of the curve graph? If I hand you a surface, can you draw two curves that have distance bigger than three? We'll start from the beginning and discuss these problems and some related computational problems on surfaces.