Graphical designs find combinatorial structures

Zawad Chowdhury, University of Washington
-
PDL C-401 and via Zoom Link: https://washington.zoom.us/j/91547335974

Abstract:

Graphical designs are subsets of vertices of a graph that perfectly average a selected set of eigenvectors of the Graph Laplacian. We show that in highly-structured graphs, graphical designs can coincide with highly structured and well-known combinatorial objects: orthogonal arrays in hypercube graphs, combinatorial block designs and extremizers of the Erdős-Ko-Rado theorem in Johnson graphs, and \$t\$-wise uniform sets of permutations and symmetric subgroups in normal Cayley graphs on the symmetric group. These connections allow tools from spectral graph theory to bear on these combinatorial objects.

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.

The pre-seminar has the following title and abstract:

Title: Graphical designs from Gale duality
Abstract: The current state of the art for finding graphical designs of a specific graph is through Gale duality and the theory of polytopes, due to work of Catherine Babecki and Rekha Thomas. We will work through a concrete example of this computation. This pre-seminar talk will provide an introduction to graphical designs through a different lens than the one highlighted in the main talk.
 

Join Zoom Meeting: https://washington.zoom.us/j/91547335974
Meeting ID: 915 4733 5974

Event Type
Seminars
Event Subcalendar
Combinatorics and Geometry Seminar
Related People
Sara Billey
Gaku Liu
Ricky Liu
Isabella Novik
Dan Guyer
Related Fields
Algebraic Combinatorics
Algebraic Topology
Combinatorics
Discrete Geometry
Geometric Combinatorics
Graph Theory