Events - October 2020

Title: Pseuodrandom Cliquefree Graphs, Finite Geometry, and Spectra

Abstract:

A regular graph is called optimally pseudorandom if its second largest eigenvalue in absolute value is, up to a constant factor, as small as possible. Determining the largest degree of an optimally pseudorandom graph without a clique of size s is a well-known open problem in extremal graph theory.

Title: Coxeter combinatorics and spherical Schubert geometry

Abstract:

This talk will introduce spherical elements in a finite Coxeter system. These spherical elements are a generalization of Coxeter elements, that conjecturally, for Weyl groups, index Schubert varieties in the flag variety G/B that are spherical for the action of a Levi subgroup.

Title: The Hepp bound of a matroid: flags, volumes and integrals

Abstract:

Invariants of combinatorial structures can be very useful tools that capture some specific characteristics, and repackage them in a meaningful way. For example, the famous Tutte polynomial of a matroid or graph tracks the rank statistics of its submatroids, which has many applications, and relations like contraction-deletion establish a very close connection between the algebraic structure of the invariant (e.g. Tutte polynomials) and the actual matroid itself.

Title: Generalization bounds for rational self-supervised learning algorithms

Abstract:

The generalization gap of a learning algorithm is the expected difference between its performance on the training data and its performance on fresh unseen test samples.Modern deep learning algorithms typically have large generalization gaps, as they use more parameters than the size of their training set. Moreover the best known rigorous bounds on their generalization gap are often vacuous.

Title: Efficient $(j,k)$-Domination

Abstract:

A function $f:V(G)\rightarrow\{0,\ldots,j\}$ is an efficient $(j,k)$-dominating function on $G$ if $\sum_{u\in N[v]}f(u)=k$ for all $v\in V(G)$ (here $N[v]=N(v)\cup\{v\}$ is the closed neighbourhood of $v$).