Events

Title: Adventures in Enumeration

Abstract: We make the argument that by combining pure mathematical tools with computational insights and applications from a vast array of disciplines, combinatorics is the perfect area to see all the wonders of math on display. Applications discussed include the analysis of classical algorithms, restricted permutations, models predicting the shape of biomembranes, queuing theory, random walks, ratchet models for gene expression, maximum likelihood degree in algebraic statistics, transcendence of zeta values, sampling algorithms for perfect matchings in bipartite graphs, and parallel synthesis for DNA storage.

Title: Reconstructing Shredded Random Matrices

Abstract: The Graph Reconstruction Conjecture states that if we are given the set of vertex-deleted subgraphs of some graph, then there is a unique graph G that can be reconstructed from them. This conjecture has been open since the 60s, and has only been solved for certain classes of graphs with not much progress towards the general case. We instead study adjacent reconstruction problems, for example, studying matrices instead of graphs:  Given some binary matrix M, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the original matrix and will it be unique? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that for matrices with entries that are i.i.d. Bernoulli(p), that for p >2log(n)/n that the matrix is indeed unique with high probability. This is a joint work with Caelan Atamanchuk and Luc Devroye.

Title: Integrable systems on the dual space of Lie algebras arising from log-canonical cluster structures

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

Abstract: Let $(X, \{~,~\})$ be an (affine) Poisson variety. A log-canonical cluster structure on $X$ is a cluster structure on the coordinate ring of $X$ such that $\{\phi, \psi\} = \text{const} \cdot \phi \psi$ whenever $\phi, \psi$ are cluster variables which belong to the same cluster. When the Poisson bivector vanishes at some point $x \in X$, the tangent space $T_x X$ comes equipped with a Poisson bracket $\{~,~\}^{\text{lin}}$, the linearization of $\{~,~\}$.  Given a function $\phi$ on $X$, we propose a way of linearizing it to get a function $\phi^{\text{lin}}$ on $T_x X$. Very often, when $\{\phi_1, \cdots, \phi_n\}$ is a cluster in a log-canonical cluster structure on $(X, \{~,~\})$, $\{\phi_1^{\text{lin}}, \cdots, \phi_n^{\text{lin}}\}$ is an integrable system on $(T_x X, \{~,~\}^{\text{lin}})$.  We present two scenarios where this is the case.

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 2

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Fulkerson 100 is a workshop organized by the Dept. of Combinatorics & Optimization (C&O) from July 17-19, 2024 at the University of Waterloo, to celebrate Fulkerson's legacy and impact in discrete mathematics, especially in the fields of graph theory, optimization, and operations research. Fulkerson 100 will feature invited talks in graph theory, combinatorics, optimization, and theoretical computer science, given by some of the foremost researchers in these areas, as well as lightning talks and a poster session devoted to students and postdocs. By bringing together various leading researchers in discrete mathematics with junior researchers and students, the workshop aims to boost research in the areas pioneered by Fulkerson, while commemorating his vision and contributions.