Events

Title: Constructing graphs with no independent transversals

Abstract: An independent transversal in a vertex-partitioned graph is an independent set of the graph that contains one vertex from each partition class. There are many theorems guaranteeing the existence of an independent transversal when the class sizes are sufficiently large compared to the maximum degree of the graph. I will describe an effective combinatorial method for constructing graphs with no independent transversals that are extremal for these theorems. I will then present an application to graph list coloring based on color degree. This is joint work with Penny Haxell.

Title: Quasi-partition algebras representations, planar Quasi-partition algebras and Characters of the Motzkin-Riordan algebra

Abstract: Daugherty and Orellana introduced a new diagram algebra called Quasipartition algebras in 2014. In this talk we will construct quasi-partition algebras and half quasi-partition algebras using an idempotent. Then using set-valued tableaux we give a description of a complete set of simple modules.Planar (half) quasi-partition algebras are sub-algebras of (half) quasi-partition algebras. The set-valued tableaux cannot be used in this setting, but for certain values of $x$, this sub-algebra is isomorphic to the Motzkin-Riordan algebra in which it is easier to find the representations. Finally, we use some idempotents of the Motzkin-Riordan algebra to compute the character table.

Title: Graph Theory and Quantum Computing

Abstract: I will present some the work I have done with my group during my time (37 years +) in the C&O department, and try to explain how perfectly innocent questions in graph theory lead me to work on questions arising in quantum computing.

There will be a reception following the seminar in MC 5511.

Title: Colored unstable map enumeration from random noncommutative geometries

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

Abstract: The enumeration of maps originates from a series of works by Tutte in the 1960’s. This work later went on to find uses in physics in the enumeration of Feynman diagrammatic expansions of matrix integrals.

In this talk I will discuss how maps with colored edges glued from 2-cells with one or two boundaries arise in recent work in the construction of path integrals over finite dimensional noncommutative spaces. Explicit formulae for the enumeration of such planar maps can be found by solving generalizations of Tutte’s equations. The generating functions of higher genus maps can also be computed from planar map generating functions using a process called Topological Recursion. This talk is based on joint work with Hamed Hessam and Masoud Khalkhali.

Title: An Optimal Algorithm for Online Bipartite Matching 

Abstract: We consider the bipartite matching problem in the online setting where vertices on the left arrive in an arbitrary order along with all their edges. Once a vertex arrives, the algorithm has to match the vertex (or can choose to not match it) and this decision cannot be changed later. Karp, Vazirani, and Vazirani give an algorithm for this problem with a competitive ratio of 1-1/e and also show it is optimal.

Title: Refined Absorption: A New Proof of the Existence Conjecture

Abstract: The study of combinatorial designs has a rich history spanning nearly two centuries.  In a recent breakthrough, the notorious Existence Conjecture for Combinatorial Designs dating back to the 1800s was proved in full by Keevash via the method of randomized algebraic constructions. Subsequently Glock, Kühn, Lo, and Osthus provided an alternate purely combinatorial proof of the Existence Conjecture via the method of iterative absorption.  We introduce a novel method of “refined absorption” for designs; in this talk, as our first application of the method we provide a new alternate proof of the Existence Conjecture. Joint work with Michelle Delcourt.

Title: Positive discrepancy, MaxCut and eigenvalues of graphs

Abstract: The positive discrepancy of a graph G of edge density p is defined as the maximum of e(U) - p|U|(|U|-1)/2, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is d-regular graph on n vertices and d = O(n^(1/9)), then the positive discrepancy of G is at least c*d^(1/2)n for some constant c.

We extend this result by proving lower bounds for the positive discrepancy with average degree d when d < (1/2 - \epsilon)*n. We prove that the same lower bound remains true when d < n^(2/3), while in the ranges n^(2/3) < d < n^(4/5) and n^(4/5) < d < (1/2 - \epsilon)*n we prove that the positive discrepancy is at least n^2/d and d^(1/4)n/log(n) respectively.

Title: The cyclic flats of L-polymatroids

Abstract: In recent years, q-polymatroids have drawn interest because of their connection with rank-metric codes. For a special class of q-polymatroids called q-matroids, the fundamental notion of a cyclic flat has been developed as a way to identify the key structural features of a q-matroid. In this talk, we will see a generalisation of the definition of a cyclic flat that can apply to q-polymatroids, as well as a further generalisation, L-polymatroids. The cyclic flats of an L-polymatroid is essentially a reduction of the data of an L-polymatroid such that the L-polymatroid can be retrieved from its cyclic flats. As such, in matroid theory, cyclic flats have been used to characterise numerous invariants.

Title: On the faces of the Kunz cone and the numerical semigroups within them

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

Abstract: A numerical semigroup is a subset of the natural numbers that is closed under addition, contains 0, and has finite complement. Each numerical semigroup $S$ with fixed smallest positive element $m$ corresponds to an integer point in a polyhedral cone $C_m \subset \mathbb{R}^{m-1}$ called the Kunz cone. Moreover, numerical semigroups corresponding to points on the same face $F$ of $C_m$ are known to share many properties, such as the number of minimal generators. But not all faces of the Kunz cone contain integer points corresponding to numerical semigroups. In this talk, we will classify all the faces that do contain such points. Additionally, we will present sharp bounds on the number of minimal generators of $S$ in terms of the dimension of the face of $C_m$ containing the point corresponding to $S$.

This is joint work with Levi Borevitz, Tara Gomes, Jiajie Ma, Christopher O'Neill, Daniel Pocklington, Rosa Stolk, Jessica Wang, and Shuhang Xue.

Title: Fujisaki-Okamoto - a recipe for post-quantum public key encryption.

Abstract: In this talk, I will give a short introduction to Fujisaki-Okamoto, a conversion that (intuitively) turns post-quantum hardness assumptions into post-quantum secure public-key encryption. Fujisaki-Okamoto featured prominently in NIST's post-quantum standardisation effort for public-key encryption, including the emerging new standard Kyber. If time permits, I will sketch open questions surrounding Fujisaki-Okamoto and potential improvements in security and efficiency.