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 13, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

CANCELLED Tutte Colloquium - Nicolas Trotignon

Title: Widths in even-hole-free graphs

Speaker: Nicolas Trotignon
Affiliation: École Normale Supérieure de Lyon
Room: MC 5501

Abstract:

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are more restricted.

Friday, May 8, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Ricardo Fukasawa

Zoom (for information email emma.watson@uwaterloo.ca

Title: Hardness of set-partitioning formulation for the vehicle routing problem with stochastic demands

Speaker: Ricardo Fukasawa
Affiliation: University of Waterloo
Location: Online (Zoom)

Abstract:

The vehicle routing problem considers the cheapest way to serve a set of customers using a fixed set of vehicles. When a vehicle serves a customer, it picks up its demand which is given as an input, and the total demand picked up cannot exceed the vehicle’s capacity. This classical combinatorial optimization problem combines aspects of routing (like a traveling salesman problem) and packing (like a knapsack problem).

Thursday, May 14, 2020 10:00 am - 10:00 am EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Oliver Schnetz

Title: Combinatorial masters in QED

Speaker: Oliver Schnetz
Affiliation: Friedrich-Alexander Universität Erlangen
Zoom: Contact Karen Yeats

Abstract:

Calculations in perturbative QED (and also in QCD) use a reduction from Feynman integrals to `master integrals'. In general, the reduction to master integrals is performed by excessive use of computer power.

Friday, May 15, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Daniel Grier

Zoom (for information email emma.watson@uwaterloo.ca

Title: Permanent Hardness from Linear Optics

Speaker: Daniel Grier
Affiliation: University of Waterloo
Location: Online (Zoom)

Abstract:

One of the great accomplishments in complexity theory was Valiant's 1979 proof that the permanent of a matrix is #P-hard to compute.  Subsequent work simplified Valiant's ideas and even began to recast them as problems in quantum computing.  In 2011, this culminated in a striking proof by Aaronson, based solely on quantum linear optics, of the #P-hardness of the permanent.

Thursday, June 4, 2020 2:30 pm - 2:30 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Lukas Nabergall

Title: Weighted generating functions for weighted chord diagrams

Speaker: Lukas Nabergall
Affiliation: University of Waterloo
Zoom: Contact Karen Yeats

Abstract:

Motivated by the universal property of the Connes-Kreimer Hopf algebra of rooted trees and Hopf subalgebras arising from so-called combinatorial Dyson-Schwinger equations, we introduce a class of two-variable recursive functional equations involving Hochschild 1-cocycle operators.

Friday, June 5, 2020 1:00 pm - 1:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Cedric Koh

Title: A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality

Speaker: Cedric Koh
Affiliation: London School of Economics and Political Science
Zoom: Contact Sharat Ibrahimpur

Abstract:

In this talk, I will present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality. The algorithm is based on the Newton–Dinkelbach method for fractional combinatorial optimization, and extends previous work of Madani (2002).

Friday, June 5, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Distinguished Tutte Lecture - Lauren K. Williams

Lauren K. Williams

Title: Matroids, tropical geometry, and positivity

Speaker: Lauren K. Williams
Affiliation: Harvard University & Radcliffe Institute
Zoom: Please email Emma Watson.

Abstract: 

The theory of matroids -- a class of combinatorial objects which simultaneously generalize graphs as well as vectors in a vector space -- was pioneered by William Tutte in his 1948 PhD thesis. Matroids are also closely connected to the Grassmannian and the tropical Grassmannian.  In recent years, mathematicians and physicists have been exploring positive notions of all of these objects, finding applications to scattering amplitudes and shallow water waves.  In my talk I will give an introduction to matroids, tropical geometry, and positivity, and survey some of the beautiful results and applications.

Thursday, June 11, 2020 2:30 pm - 2:30 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Steve Melczer

Title: An Upper Bound on Graphical Partitions

Speaker: Steve Melczer
Affiliation: UQAM/CRM
Zoom Contact Karen Yeats

Abstract:

An integer partition is called graphical if it can be realized as the size-ordered degree sequence of a simple graph (with no loops or multiple edges).  In his 1736 paper on the Königsberg bridge problem, arguably the origin of graph theory, Euler gave a necessary condition for a partition to be graphical: its sum must be even.

Friday, June 12, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Vishnu V. Narayan

Title: One Dollar Each Eliminates Envy

Speaker: Vishnu V. Narayan
Affiliation: McGill University
Zoom: Contact Sharat Ibrahimpur

Abstract:

We study the fair division of a collection of $m$ indivisible goods amongst a set of $n$ agents. Whilst envy-free allocations typically do not exist in the indivisible goods setting, envy-freeness can be achieved if some amount of a divisible good (money) is introduced.

Thursday, June 18, 2020 1:03 pm - 1:03 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Julián Romero

Title: Graph coloring of graphs with large girth is hard for the Nullstellensatz

Speaker: Julián Romero
Affiliation: University of Waterloo
Zoom: Contact Sharat Ibrahimpur

Abstract:

In this talk we will discuss a method to solve combinatorial problems using hierarchies of systems of linear equations using Hilbert's Nullstellensatz. In particular, we will study the behaviour of these hierarchies for deciding the non-$k$-colorabilty of graphs.