Events

Title: Bridging the gap between Linear and Integer Programming

Abstract: Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.

Title: New strongly regular graphs from optimal line packings

Abstract: In this talk, we'll explore several new constructions of strongly regular graphs. Specifically, we will show how some known optimal line packings can be coerced into generating new families of SRGs. We will also introduce a new construction of optimal line packings, yielding additional infinite families of SRGs.

Title: Analytic Methods and Combinatorial Plants

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

Abstract: In this talk, I will present the results of my masters thesis. I examine three applications of analytic methods to problems in combinatorics. By coincidence, each problem involves a combinatorial structure named for a plant--AVL trees, cactus graphs, and sunflowers--which we refer to collectively as combinatorial plants.

Title: Abelian covers of association schemes with applications to SIC-POVM

Abstract: Godsil and Hensel (1992) developed a theory of abelian covers of complete graphs to construct antipodal distance-regular graphs of diameter 3. More recently, Coutinho, Godsil, Shirazi and Zhan (2016) showed that equiangular tight frames can be constructed from covers of complete graphs in terms of cyclic groups of prime order. In this talk, we introduce covers of (not necessarily symmetric) association scheme of d classes in terms of an (not necessarily cyclic) abelian group G of order d.

Title: Lorentzian polynomials

Abstract: Lorentzian (aka completely log-concave) polynomials were recently developed by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to settle Mason's conjectures on the log-concavity of the number of size-k independent sets of a matroid. In this talk, we will define these polynomials and sketch the proof of these conjectures. Along the way we will also state other results which will demonstrate the very strong connection between matroids and Lorentzian polynomials.

Title: Deza graphs and vertex connectivity

Abstract: A k-regular graph on v vertices is called a Deza graph with parameters (v, k, b, a), b ≥ a if the number of common neighbors of any two distinct vertices takes two values: a or b. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular.

In this talk we will discuss the enumeration of strictly Deza graphs and the enumeration of special subclass of strictly Deza graphs called divisible design graphs. We will also describe the constructions of divisible design graphs found during the enumeration.

Title: Stochastic  Oracles and Where to Find Them

Abstract: Continuous optimization is a mature field, which has recently undergone major expansion and change. One of the key new directions is the development of methods that do not require exact information about the objective function. Nevertheless, the majority of these methods, from stochastic gradient descent to "zero-th order" methods use some kind of approximate first order information. We will overview different methods of obtaining this information, including simple stochastic gradient via sampling, robust gradient estimation in adversarial settings, traditional and randomized finite difference methods and more.

We will discuss what key properties of these inexact, stochastic first order oracles are useful for convergence analysis of optimization methods that use them. 

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.