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, 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.

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

Tutte Colloquium - Sanjeev Khanna

Title: A Faster Combinatorial Algorithm for Maximum Bipartite Matching          

Speaker: Sanjeev Khanna
Affiliation: University of Pennsylvania
Location: MC 5501

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.

Monday, March 4, 2024 3:15 pm - 4:15 pm EST (GMT -05:00)

C&O Special Seminar - Jane Gao

Title: Evolution of random representable matroids

Speaker: Jane Gao
Affiliation: University of Waterloo
Location: MC 5417

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? 

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

C&O Reading Group - Jacob Skitsko

Title: Online Matroid Intersection: Beating Half for Random Arrival

Speaker: Jacob Skitsko
Affiliation: University of Waterloo
Location: MC 6029

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 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.

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.