Events

Title: Distance-regular graphs that support a uniform structure

Abstract: Given a connected bipartite graph $G$, the adjacency matrix $A$ of $G$ can be decomposed as  $A=L+R$, where $L=L(x)$ and $R=R(x)$ are respectively the  lowering and the raising matrices with respect to a certain vertex $x$. The graph $G$ has a \textit{uniform structure} with respect to $x$ if the matrices $RL^2$, $LRL$, $L^2R$, and $L$ satisfy a certain linear dependency.

Title: Linear relations and Lorentzian property of chromatic symmetric functions

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.

Abstract: The chromatic symmetric function (CSF) of Dyck paths of Stanley and its Shareshian Wachs q-analogue (q-CSF) have important connections to Hessenberg varieties, diagonal harmonics and LLT polynomials. In the, so called, abelian case they are related to placements of non-attacking rooks by results of Stanley-Stembridge (1993) and Guay-Paquet (2013).

Title: Multiplicative Weight Update (MWU) Method for Solving Packing/Covering LPs

Abstract: I will present an overview of the MWU technique for solving Packing/Covering LPs easily and efficiently. The talk will be based on a combination of results from the following resources: (1) https://epubs.siam.org/doi/pdf/10.1137/1.9781611976014.11 (2) https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Title: Quantum Automorphism Groups of Trees

Abstract: We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum version of Jordan’s theorem for the automorphism groups of trees. This is one of the first characterisations of quantum automorphism groups of a natural class of graphs with quantum symmetry. This talk is based on the following preprint: https://arxiv.org/abs/2311.04891

Title: Filtered deformations of commutative algebras

Note: There will be no pre-seminar.

Abstract: We’ll look at different ways of deforming the multiplicative structure of “classical” algebras to obtain new algebras and explain how this algebraic structure can often be understood combinatorially.  We’ll then look at a special class of algebras one can produce this way called filtered deformations and we’ll discuss a conjecture of Etingof which asserts that in positive characteristic that filtered deformations of commutative rings should be in some natural sense very close to being commutative themselves. Not much background will be assumed.

Title: Several Gyrafas-Sumner-type results for treewidth

Abstract: For a graph parameter which goes unbounded at both ends of a robust sparsity spectrum, one naturally asks if it is bounded anywhere in the middle. This is modelled after a well-known conjecture of Gyarfas and Sumner, asking the above question for the chromatic number as the parameter and the girth as the measure of sparsity. We look through this lens at the treewidth as the parameter and present a number of recent results answering the corresponding question in various settings. If time permits, we’ll try to sketch a proof as well as some directions for future work.

This is joint work with Bogdan Alecu, Maria Chudnovsky, Sophie Spirkl and partly with Tara Abrishami.

Title: Online Convex Optimization

Abstract: Online learning (OL) is a theoretical framework for learning with data online. Moreover, we usually make no assumptions on the distribution of the data, allowing it even to be adversarial to the learner. Maybe surprisingly, we can still design algorithms that, in some sense, “successfully learn” in this setting. This level of generality makes many of the ideas, algorithms, and techniques from OL useful in applications in theoretical computer science, optimization in machine learning, and control. In this talk I will give a brief introduction to the key concepts in online learning and  mention a few topics within or adjacent to online learning that I believe cover fundamental ideas in OL and/or with interesting open research questions.

Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.

Title: On the intersection density of transitive groups with degree 3p

Abstract: Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a subset $\mathcal{F}\subset G$ is intersecting if any two elements of $\mathcal{F}$ agree on some elements of $\Omega$. The \emph{intersection density} of $G$ is the rational number $\rho(G)$ given by the maximum ratio $\frac{|\mathcal{F}|}{|G|/|\Omega|}$, where $\mathcal{F}$ runs through all intersecting sets of $G$.

Most results on the intersection density focus on particular families of transitive groups. One can look at problems on the intersection density from another perspective. Given an integer $n\geq 3$, we would like to determine the possible intersection densities of transitive groups of degree $n$. This problem turns out to be extremely difficult even in the case where $n$ is a product of two primes.