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.