Codes and Expansions (CodEx) Seminar


Stefan Steinerberger (University of Washington)
Graphical Designs

Spherical Designs are sets of points on the sphere with the property that the average of a low-degree polynomial over the points is the same as the global average of the polynomial on the sphere. As it turns out, the definition can be suitably interpreted to make sense on a finite combinatorial Graph as well.  The arising structures are breathtaking (many pictures will be shown) and can be interpreted as the natural analogue of Gaussian quadrature points on graphs. Graphs can have many more symmetries than Euclidean space and, correspondingly, some of these point structures can integrate gigantic eigenspaces of functions exactly. Graphs can be hyperbolic while the Euclidean space is always flat allowing for all sorts of new fun.  This is also naturally related to Extremal Combinatorics where classical Theorems (the Erdos-Ko-Rado Theorem, the Deza-Frankl theorem)  suddenly turn into beautiful special cases of these "Graphical  Designs".   If we specialize to the hypercube graph \(\{0,1\}^d\), we naturally encounter problems from coding theory.   There will be pictures, a survey of recent results by C. Babecki, K. Golubev, D. Shiroma, R. Thomas and many, many open problems.