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

Distinguished Tutte Lecture - Jacob Fox

Title: Ramsey Cayley graphs, random graph models, and information theory

Speaker: Jacob Fox
Affiliation: Stanford University
Location: MC 5501

Abstract: A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph.

Friday, July 21, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Joint Tutte Colloquium & Algorithms and Complexity Seminar - Leonid Gurvits

Title: Combinatorial and complexity theoretic aspects of Stabilities and Controllabilities of linear switched systems(discrete and continuous time)

Speaker: Leonid Gurvits
Affiliation: The City College of New York
Location: MC 5501

Abstract: I will talk about my "pre-hyperbolic" research, some of it done jointly with Alex Samorodnitsky and Alex Olshevsky.

Friday, August 4, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Bill Jackson

Title: Rigidity of Simplicial Complexes

Speaker: Bill Jackson
Affiliation: Queen Mary University of London
Location: MC 5501

Abstract: A simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicial k-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).

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

Tutte Colloquium - Vida Dujmovic

Title: Proof of the Clustered Hadwiger Conjecture

Speaker: Vida Dujmovic
Affiliation: University of Ottawa
Location: MC 5501

Abstract: Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-minor-free graph is (h-1)-colourable with monochromatic components of bounded size.

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

Tutte Colloquium - Nikhil Kumar

Title: An Approximate Generalization of the Okamura-Seymour Theorem

Speaker: Nikhil Kumar
Affiliation: University of Waterloo
Location: MC 5501

Abstract: We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.

Friday, October 20, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Sepehr Assadi

Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams 

Speaker: Sepehr Assadi
Affiliation: University of Waterloo
Location: MC 5501

Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Friday, November 3, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Walaa Moursi

Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Speaker: Walaa Moursi
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Friday, November 10, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Distinguished Tutte Lecture - David B. Shmoys

Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics

Speaker: David B. Shmoys
Affiliation: Cornell University
Location: MC 5501

Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.

Friday, November 17, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Luke Postle

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

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

Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Friday, November 24, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Karen Yeats

Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

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

Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.