Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, March 8, 2024 3:30 pm - 4:30 pm EST (GMT -05:00)

Distinguished Tutte Lecture - Tal Rabin

Tal Rabin

Title: Information Theoretic MPC: Techniques That Age Well

Speaker: Tal Rabin
Affiliation: University of Pennsylvania
Location: MC 5501


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.

Monday, March 11, 2024 11:30 am - 12:30 pm EDT (GMT -04:00)

Algebraic Graph Theory - Josse van Dobben de Bruyn

Title: Gonality of graphs – a survey

Speaker: Josse van Dobben de Bruyn
Affiliation: Technical University of Denmark (DTU)
Location: Please contact Sabrina Lato for Zoom link.

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.

Tuesday, March 12, 2024 3:00 pm - 4:00 pm EDT (GMT -04:00)

Graphs and Matroids - Ronen Wdowinski

Title: Constructing graphs with no independent transversals

Speaker: Ronen Wdowinski
Affiliation: University of Waterloo
Location: MC 5417

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.

Thursday, March 14, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics - Nancy Wallace

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

Speaker: Nancy Wallace
Affiliation: York University
Location: MC 5479

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.

Friday, March 15, 2024 - Sunday, March 17, 2024 (all day)

Godsil75

We are pleased to announce a virtual workshop in honour of Chris Godsil's 75th 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.

Friday, March 15, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Chris Godsil

Title: Graph Theory and Quantum Computing

Speaker: Chris Godsil
Affiliation: University of Waterloo
Location: MC 5501

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.

Thursday, March 21, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics - Nathan Pagliaroli

Title: Colored unstable map enumeration from random noncommutative geometries

Speaker: Nathan Pagliaroli
Affiliation: Western University
Location: MC 5479

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.

Friday, March 22, 2024 12:00 pm - 1:30 pm EDT (GMT -04:00)

C&O Reading Group - Vihan Shah

Title: An Optimal Algorithm for Online Bipartite Matching 

Speaker: Vihan Shah
Affiliation: University of Waterloo
Location: MC 6029

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.

Friday, March 22, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Luke Postle

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

Speaker: Luke Postle
Affiliation: University of Waterloo
Location: MC 5501

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.

Monday, March 25, 2024 11:30 am - 12:30 pm EDT (GMT -04:00)

Algebraic Graph Theory - Eero Räty

Title: Positive discrepancy, MaxCut and eigenvalues of graphs

Speaker: Eero Räty
Affiliation: University of Umeå
Location: Please contact Sabrina Lato for Zoom link.

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.