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:
Monday, September 26, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Dave Witte Morris

Title: Automorphisms of direct products of some circulant graphs

Speaker: Dave Witte Morris
Affiliation: University of Lethbridge
Location: contact Sabrina Lato for Zoom link

Abstract: The direct product of two graphs X and Y is denoted X x Y. Its automorphism group contains a copy of the direct product of Aut(X) and Aut(Y), but it is not known when this inclusion is an equality, even for the special case where X is a circulant graph and Y = K_2 is a connected graph with only 2 vertices.

Friday, September 30, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - David Kalichman

Title: Stochastic Probing with Applications

Speaker: David Kalichman
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Friday, September 30, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Penny Haxell

Title: The Integrality Gap for the Santa Claus Problem

Speaker: Penny Haxell
Affiliation: University of Waterloo
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: 

In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of   indivisible resources, such that the minimum utility among all players is maximized.  In the restricted variant, also known as the Santa Claus Problem,  each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy
jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Monday, October 3, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Nathan Lindzey

Title: Jack Derangements

Speaker: Nathan Lindzey
Affiliation: Technion
Location: Contact  Sabrina Lato for Zoom link

Abstract: For each integer partition $\lambda \vdash n$ we give a simple combinatorial formula for the sum of the Jack character $\theta^\lambda_\alpha$ over the integer partitions of $n$ with no singleton parts. For $\alpha = 1,2$ this gives closed forms for the eigenvalues of the permutation and perfect matching derangement graphs, resolving an open question in algebraic graph theory. Our proofs center around a Jack analogue of a hook product related to Cayley's $\Omega$--process in classical invariant theory, which we call \emph{the principal lower hook product}.

Thursday, October 6, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics - Jean-Philippe Labbé

Title: Lineup polytopes and applications in quantum physics

Speaker: Jean-Philippe Labbé
Affiliation: Université du Québec
Location: MC 5479 contact Olya Mandelshtam for Zoom link

Abstract:  To put it simply, Pauli's exclusion principle is the reason why we can't walk through walls without getting hurt. Pauli won the Nobel Prize in Physics in 1945 for the formulation of this principle. A few years later, this principle received a geometrical formulation that is still overlooked today. This formulation uses the eigenvalues of certain matrices (which represent a system of elementary particles, for example electrons). These eigenvalues form a symmetric geometric object obtained by cutting a hypercube: it is a hypersimplex.

Friday, October 7, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Paul Lawrence

Title: On the Adaptivity Gap of Stochastic Orienteering

Speaker: Paul Lawrence
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution.

Friday, October 7, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Richard Peng

Title: Bipartite Matching in Almost-Linear Time and More

Speaker: Yang Peng
Affiliation: University of Waterloo
Location: MC 5501, please contact Amanda Lutz for Zoom link

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.

Friday, October 14, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Jonathan Leake

Title: Approximate Counting via Lorentzian Polynomials and Entropy Optimization

Speaker: Jonathan Leake
Affiliation: University of Waterloo
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: Over the past 20 years, Lorentzian and real stable polynomials have been used to derive a number of combinatorial theorems, from log-concavity statements to counting and volume bounds. One significant thread of this research lies in the utilization of entropy optimization methods to approximately count certain combinatorial objects, such as the matchings of a bipartite graph, the intersection of the sets of bases of two matroids, and the integer points of various polytopes in general. In this talk, we will discuss various results one can achieve using such methods.

Monday, October 17, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Harmony Zhan

Title: An introduction to discrete quantum walks

Speaker: Harmony Zhan
Affiliation: Simon Fraser University
Location: please contact Sabrina Lato for Zoom link

Abstract: A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris and me.

Thursday, October 20, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Sheila Sundaram

Title: Quasisymmetric functions,  descent sets, immaculate tableaux, and 0-Hecke modules

Speaker: Shelia Sundaram
Affiliation:  
Location: MC 5479 or contact Olya Mandelshtam for Zoom link

Abstract:

The first half of this talk will be expository and devoted to a discussion of (quasi)symmetric functions and tableaux.

We define new families of quasisymmetric functions, in particular the new basis of row-strict dual immaculate functions, with an associated cyclic, indecomposable 0-Hecke algebra module. Our row-strict immaculate functions are related to the dual immaculate functions of Berg-Bergeron-Saliola-Serrano-Zabrocki (2014-15) by the involution \psi on the ring Qsym of quasisymmetric functions. We uncover the remarkable properties of the immaculate Hecke poset induced by the 0-Hecke action on standard immaculate tableaux, revealing other submodules and quotient modules, often cyclic and indecomposable.