Events

Title: The heroes of digraphs: coloring digraphs with forbidden induced subgraphs

Abstract: The chromatic number is one of the most studied graph invariants in graph theory. $\chi$-boundedness, for instance, studies the induced subgraphs present in graphs with large chromatic number and small clique number. Neumann-Lara introduced an analog directed version of this graph invariant: the dichromatic number of digraphs.

Title: Quantum Algorithms and Mutually Unbiased Bases

Abstract: Mutually unbiased bases are fundamental to quantum information theory, showing up in quantum key distribution, quantum error correction, and quantum entanglement measures. They likewise might be familiar to algebraic graph theorists, thanks to their connection to equiangular lines and association schemes.

Title: Sets that Support a Joint Distribution

Abstract: Given a closed set on the plane and two probability distributions on the real line, when are there random variables with the given distributions whose joint distribution is supported by the given set?

Title: A Primal-Dual Extension of the Goemans and Williamson Algorithm for Weighted Fractional Cut Cover

Abstract: A cut in a graph G = (V, E) is a set of edges which has one endpoint in S, for a given subset S of V. The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. Beyond its role as part of Šámal's work on cut continuous functions, this graph parameter also arises as the gauge dual of the maximum cut problem.

Title: On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme

Abstract:  Graph classes in the Johnson, Grassmann and Hamming association scheme have received a considerable amount of attention over the last decades. Although several (NP-hard) graph parameters have been investigated for these families, many remain unknown. In this talk, we establish the diameter of generalized Grassmann graphs, extending previous results for generalized Johnson graphs.

Title: Orthogonal basis of eigenvectors for the Johnson and Kneser graphs

Abstract: The Johnson and Kneser graphs have the same eigenspaces. How explicitly can we describe these eigenspaces? 

Title: The matching polytope has exponential extension complexity

Abstract: This Friday we will build off of some previous results by looking at the paper “The matching polytope has exponential extension complexity” by Thomas Rothvoss! At the beginning of the semester, we saw that the matching (and TSP) polytopes cannot be expressed by a polynomial sized symmetric LP.

Title: A brief introduction to lattice-based cryptography

Abstract: A brief introduction to lattice-based cryptography, one of the leading candidates for building quantum-resistant cryptosystems.

Title: Snake decomposition of lattice path matroids

Abstract: Lattice path matroids (LPMs) are positroids whose base polytopes have a nice decomposition. We provide a geometric perspective to this decomposition in terms of fences and their order polytopes, which correspond to a certain class of LPMs we call snakes.

Title: Lorentzian polynomials

Abstract: Lorentzian polynomials on cones are intimately connected to Hodge theory, matroid theory and the geometry of zeros of polynomials.