Events

Title: On the use of senders in Ramsey Theory

Abstract: In this talk I will introduce and investigate some parameters in Graph Ramsey theory, beyond the traditional Ramsey numbers. A crucial ingredient for their analysis is the existence of gadget graphs, called signal senders, that were initially developed by Burr, Erdős and Lovász in 1976. I will explain their origin, properties, and try to convey their surprising strength. Using probabilistic methods, we will see how to build such gadgets, and how to use them to prove some theorems, previously out of reach without these tools.

Title: A relaxation of Woodall’s conjecture

Abstract: In a directed graph, a directed cut (dicut for short) is a cut where all arcs are directed from one shore to the other; a directed join (dijoin for short) is a set of arcs whose contraction makes the digraph strongly connected. The celebrated Lucchesi–Younger theorem states that for any directed graph the size of the smallest dijoin equals the maximum number of pairwise disjoint dicuts. Woodall’s conjecture posits that the size of the smallest dicut equals the maximum number of pairwise disjoint dijoins. 

Title: Bipartite Perfect Matching is in Quasi-NC, Part II

Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.

Title: Supersingular isogeny graphs, modular curves and Galois Representations.

Abstract: In this talk we will discuss the remarkable interconnection among supersingular elliptic curves, modular curves and Galois representations with a focus on cryptographic applications.

Title: Contracts for Functions Based on Graphs

Abstract: We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions; and the outcome is either a success or failure. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized.

Title: Approximating Graphic TSP with matchings

Abstract: Revisiting defining character of the field of algorithm design and complexity, TSP!. While the problem itself is NP-Hard and difficult to approximate, various formulations, such as the Metric version, have yielded notable approximation algorithms. The classical 1.5-approximation algorithm by Christofides, leveraging matchings, stood as the best-known result for decades. However, recent breakthroughs have pushed these boundaries further.

Title: Combinatorial models in enumerative geometry

Abstract: How many circles are tangent to three given circles in the plane?  How many lines lie on a smooth cubic surface? How many lines intersect four given lines in 3-space? These are classical questions in enumerative geometry, a field at least as old as Apollonius of Perga, to whom the question about tangent circles is attributed in the third century BCE.  It is not hard to see that the answers to these questions may depend on the choice of circles, surface, or lines, respectively. It is harder to see that, in each case, there is a "typical" answer. 

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.

Title: Two variations of the chromatic symmetric function

Abstract: The /chromatic symmetric function/ is a symmetric function generalization of the chromatic polynomial that encodes the ways to color a graph such that no two adjacent vertices get the same color. We will discuss two different analogues of the chromatic symmetric function: a K-theoretic analogue called the /Kromatic symmetric function/, and a categorification called the /chromatic symmetric homology/. We show that certain properties of a graph can be recovered given its Kromatic symmetric function, and we give some formulas for special cases of the chromatic symmetric homology.

Title: Nearly-linear stable sets

Abstract: The Gyárfás-Sumner conjecture says that for every forest 𝐻 and complete graph 𝐾, there exists 𝑐 such that every {𝐻,𝐾}-free graph (that is, containing neither of 𝐻,𝐾 as an induced subgraph) has chromatic number at most 𝑐. This is still open, but we have proved that every {𝐻,𝐾}-free graph 𝐺 has chromatic number at most |𝐺|^o(1).