Events

Title: A O(log log (rank) ) - competitive algorithm for the matroid secretary problem - Part 2

Abstract: In this talk we continue to review a O(log log(rank) ) - competitive algorithm for the matroid secretary problem (MSP) due to  Feldman, Svensson and Zenklusen, where rank denotes the rank of the given matroid.

Title: A Faster Combinatorial Algorithm for Maximum Bipartite Matching          

Abstract: The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in $O(m \sqrt{n})$ time on a graph with $n$ vertices and $m$ edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of $O(n^{2.371})$. These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs.

Title: Evolution of random representable matroids

There will be light refreshments starting at 3:00 pm.

Abstract: Inspired by the classical random graph process introduced by Erdos and Renyi in 1960, we introduce two analogous processes for random representable matroids. In the talk we address the following questions, with answers to some already established in existing literature, while others stem from recent research findings:

How does the rank of the random matroid evolve in the process?

When does the first k-circuit appear for each integer k? 

What is the length of the first circuit appearing in the process?

How does the connectivity of the matroid change?

What is the growth rate of the critical number (c.f. chromatic number of graphs) in the process?

When do given (small and large) matroid minors occur in the process?

How about the appearance of submatroids? 

Title: Online Matroid Intersection: Beating Half for Random Arrival

Abstract: We'll take a gander at the paper Online Matroid Intersection: Beating Half for Random Arrival by Guruganesh and Singla. We're given two matroids defined on elements of a common ground set, and elements will arrive one-by-one in a uniformly random order. Whenever an element arrives we'll need to decide to keep them or tell them goodbye forever. The greedy algorithm gives us a competitive ratio of 1/2, but can we do better? Yes! (Slightly, with a simple randomized algorithm). We'll first take a look at the special case of bipartite matching. The results also extend in a natural way to the intersection of k matroids, and non-bipartite matching. If I don't ramble too much, we'll also get to (briefly) discuss a recent improvement for the intersection of 2 matroids.

Title: Information Theoretic MPC: Techniques That Age Well

Abstract: The talk will be self-contained and discuss multiparty protocols and their applications. This lecture is presented jointly by Women in Mathematics and the Department of Combinatorics and Optimization and is part of the Dean’s Distinguished Lecture Series.

Title: Gonality of graphs – a survey

Abstract: Over the past 30 or so years, the realization that graphs can be viewed as discrete analogues of Riemann surfaces has led to a fruitful interplay between algebraic geometry, tropical geometry, and graph theory. Among other things, this has led to the study of new graph parameters, including various notions of the gonality of a graph. In addition to its ties with algebraic and tropical geometry, graph gonality also turns out to have connections with chip-firing games, structural graph theory, and parametrized complexity. In this talk, I will introduce the two most common types of graph gonality (namely, divisorial gonality and stable gonality) and survey the most important results and open problems in this field, including the connections with the aforementioned topics.

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.

We are pleased to announce a virtual workshop in honour of Chris Godsil's 75^th birthday. Chris Godsil's imprint on mathematics goes beyond algebraic combinatorics to merge theory and application, emerging research areas and well-developed mathematical tools. Chris Godsil is a research leader in discrete mathematics and he continues to be influential in a wide range of mathematical subdisciplines and communities around the world.  He has long been a prominent member of the Canadian combinatorial community, working first at Simon Fraser University and then playing a leadership role in the Department of Combinatorics and Optimization at the University of Waterloo; as a result, Chris Godsil has influenced multiple generations of mathematicians in Canada and abroad.

The goal of this workshop is not just to honour Chris Godsil's contributions and his impact on mathematics, but also to also bring together researchers in discrete math whose work has been influenced by Chris Godsil. We invite researchers in combinatorics, matrix theory, and quantum information theory from all over the world to join us, and will have sessions to accomodate a range of time zones.

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.