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:
Thursday, February 8, 2024 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics - Tim Miller

Title: Vertex models for the product of a Schur and Demazure polynomial

Speaker: Tim Miller
Affiliation: University of Waterloo
Location: MC 5479

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

Abstract: Demazure atoms and characters are polynomials that each form a Z-basis for polynomials in n variables. The product of a Schur polynomial with a Demazure atom (resp. character) expands into a linear combination of Demazure atoms (resp. characters) with positive integer structure coefficients. There are known combinatorial rules that compute these coefficients using "skyline tableaux" given by Haglund, Luoto, Mason and Willigenburg. I have found alternative rules using the theory of integrable vertex models, inspired by a technique introduced by Zinn-Justin.

Friday, February 9, 2024 12:00 pm - 1:30 pm EST (GMT -05:00)

C&O Reading Group - Janani Sundaresan

Title: Online Edge Coloring with Tree Recurrences

Speaker: Janani Sundaresan
Affiliation: University of Waterloo
Location: MC 6029

Abstract: We will talk about online edge coloring in the edge arrival model. The vertex set V is known, and each edge arrives one by one, where it has to be colored irrevocably immediately. I will present the results from Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC 2022] which gives an algorithm that colors the graph with (e/e-1 + o(1))\delta colors.

Monday, February 12, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Maxwell Levit

Title: Subconstituents of Drackns 

Speaker: Maxwell Levit
Affiliation: Simon Fraser University
Location: Please contact Sabrina Lato for Zoom link.

Abstract: For a distance-regular graph X and an arbitrary vertex v, we often find interesting structure in the subgraph of X induced on vertices at distance 2 from v.

For example:

Any strongly-regular graph with parameters (n,k,a,k/2) can be found at distance 2 from a vertex in a distance-regular graph of diameter 3.

Certain distance-regular graphs of diameter 3 can be found at distance 2 from a vertex in a Moore graph of girth 5.

These (and more) examples are known as second-subconstituents, and they can be studied using the Terwilliger (or subconstituent) algebra of X. I will discuss this theory in the case that X is a distance-regular antipodal cover of a complete graph (drackn). This setting generalizes the first example and includes the second.

I will describe some general techniques for studying the Terwilliger algebras of drackns and then restrict to drackns without triangles. In this setting I will explain how to compute the spectrum of the second-subconstituent of any triangle-free drackn, except possibly the second-subconstituent OF a second-subconstituent of a Moore graph of valency 57.

Tuesday, February 13, 2024 3:00 pm - 4:00 pm EST (GMT -05:00)

Graphs and Matroids - Sophie Spirkl

Title: Odd cycle transversal in P5-free graphs

Speaker: Sophie Spirkl
Affiliation: University of Waterloo
Location: MC 5417

Abstract: Odd cycle transversal is a fun computational problem, somewhere between colouring and independent set: we are (equivalently) looking for a bipartite induced subgraph of maximum weight. As one might expect, this is NP-hard; I will tell you how to solve this problem in polynomial time in P5-free graphs (and more). Joint work with Cece Henderson, Evelyne Smith-Roberge, and Rebecca Whitman.

Note: I am COVID-cautious and will bring masks for those willing to wear them. 

 

Thursday, February 15, 2024 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics - Karen Yeats

Title: More Martin and c2 details.

Speaker: Karen Yeats
Affiliation: University of Waterloo
Location: MC 5479

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.  Please also come to the pre-seminar to discuss what sorts of snacks and refreshments we might want going forward.

Abstract:  I'm going to tell you more of the details behind my Martin polynomial work last year with Erik Panzer which led to the proof of the c2 completion conjecture. I will actually describe the key bijection that proves it all, say some things about the permanent invariant, and cover other details that there hadn't been time for in the colloquium level presentation of the result.

Friday, February 16, 2024 12:00 pm - 1:00 pm EST (GMT -05:00)

C&O Reading Group - David Aleman

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

Speaker: David Aleman
Affiliation: University of Waterloo
Location: MC 6029

Abstract: In the Matroid Secretary problem the weighted elements of a matroid arrive one by one in a uniformly random order where an online algorithm observes the value of the element and must make an irrevocable decision of whether or not to include the element in its solution before the arrival of the next element. The goal is to maximize the total value of the chosen elements under the condition that they must constitute an independent set. Other than knowing the cardinality of the ground set and having access to an independence oracle, the algorithm has no further information about the matroid.

Monday, February 26, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Yuval Widgerson

Title: The limits of the inertia bound

Speaker: Yuval Widgerson
Affiliation: ETH Zürich
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Spectral graph theory provides us with a wide array of surprising results which relate graph-theoretic parameters to linear-algebraic parameters of associated matrices. Among the most well-known and useful of these is Hoffman’s ratio bound, which gives an upper bound on the independence number of a graph in terms of its eigenvalues.

Tuesday, February 27, 2024 3:00 pm - 4:00 pm EST (GMT -05:00)

Graphs and Matroids - Aristotelis Chaniotis

Title: Intersections of graphs and χ-boundedness: Interval graphs, chordal graphs, and χ-guarding graph classes

Speaker: Aristotelis Chaniotis
Affiliation: University of Waterloo
Location: MC 5417

Abstract: Following A. Gyárfás (1987), we say that a hereditary class of graphs is χ-bounded if there exists a function which provides an upper bound for the chromatic number of each graph of the class in terms of the graph's clique number. In this terminology, E. Asplund and B.Grünbaum (1960),  motivated by a question of A. Bielecski (1948), proved that the class of intersection graphs of axis parallel rectangles is χ-bounded, and J. P. Burling, in his Ph.D. thesis (1965), proved that the class of intersection graphs of axis parallel boxes in R^3 is not χ-bounded.

Thursday, February 29, 2024 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics - Leo Jiang

Title: Real matroid Schubert varieties, zonotopes, and virtual Weyl groups

Speaker: Leo Jiang
Affiliation: University of Toronto
Location: MC 5479

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

Abstract: Every linear representation of a matroid determines a matroid Schubert variety whose geometry encodes combinatorics of the matroid. When the representation is over the real numbers, we show that the topology of these varieties is completely determined by the combinatorics of zonotopes. As an application, we compute the fundamental groups. When the real matroid Schubert variety comes from a Coxeter arrangement, we show that the equivariant fundamental group is a “virtual” analogue of the corresponding Weyl group.

Friday, March 1, 2024 12:00 pm - 1:30 pm EST (GMT -05:00)

C&O Reading Group - David Aleman

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

Speaker: David Aleman
Affiliation: University of Waterloo
Location: MC 6029

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.