Events

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

Title: Tight bounds for reconstructing graphs from distance queries

Abstract: Suppose you are given the vertex set of a graph and you want to discover the edge set. An oracle can tell you, given two vertices, what the distance is between these vertices in the graph. (For example, in a computer network, this would represent the minimum number of communication links needed to send a message from one computer to another.) Based on the answer, you may select the next query. The (labelled) graph is reconstructed when there is a single edge set compatible with the answers. How many queries are needed, in the worst case? The question becomes interesting for bounded degree graphs. We provide tight bounds for various classes of graphs, improving both the lower and upper bound, in both the randomized and deterministic setting.