Events

Title: Ramsey with purple edges

Abstract: Motivated by a question of David Angell, we study a variant of Ramsey numbers where some edges are coloured with both red and blue colours, (i.e. are called ‘purple’ edges). Specifically, we are interested in the largest number g = g(s, t, n), for some s and t and n < R(s, t), such that there exists a red-blue-purple colouring of Kn with g purple edges, without a red-purple Ks and without a blue-purple Kt. We determine g asymptotically for a large family of parameters. The talk will be introductory in nature. Since the concept of double-coloured edges is new in this context, there is a plethora of open questions. Joint work with Anita Liebenau and Nye Taylor.

Title: Graph theory and Feynman integrals

Abstract: Feynman integrals are one of the most versatile tools in theoretical physics. They are used to compute perturbative solutions for various interacting systems. Examples include scattering amplitudes in quantum field theory, gravitational waves at black hole mergers, and the scaling behavior in statistical physics at critical points. Every Feynman integral is defined in terms of a corresponding Feynman graph, and besides the concrete physical application, it is interesting to study the number theory of Feynman integrals and how they are related to combinatorial properties of the underlying graph. What can we know about the value of the integral from examining the graph alone? In particular: Under which conditions will the Feynman integrals of two non-isomorphic graphs evaluate to the same number?

Title: Shellability of complexes over lattices

Abstract: In this work, we introduce the notion of power lattices, which are a more general class of ranked lattices with additional properties. Then we generalize the concept of shellable simplicial complexes in the lattice of subsets to P-shellable P-complexes in a power lattice P. We show that when the P-complex is P-shellable, its order complex is a shellable simplicial complex. We demonstrate that these P-complexes can be constructed by generalizing the concept of matroids to matroids in a power lattice P. This provides various constructions of posets with desirable topological and algebraic properties. In the particular class of lattices of multiset subsets, we show how to construct shellable 'multicomplexes' from weighted graphs. Finally, we illustrate how shellable multicomplexes give rise to rings that are sequentially Cohen-Macaulay.

Title: Bipartite Perfect Matching is in Quasi-NC

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: Combinatorial proof of a Non-Renormalization Theorem

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

Abstract: In "Higher Operations in Perturbation Theory", Gaiotto, Kulp, and Wu discussed Feynman integrals that controls certain deformations in quantum field theory. These integrals themselves are differential forms, and the authors conjectured that one class of them squares to zero. This phenomenon can be interpreted as absence of quantum corrections in topological quantum field theories with more than one topological direction, or as an analogue of Kontsevich's formality theorem. In my talk, I will present a purely combinatorial proof of the conjecture for arbitrary graphs. It is based on graph matrices and graph polynomials, and a careful analysis of the involved signs and multiplicities. No knowledge or intution of the underlying physics is required.

In the preseminar, I will review the necessary definitions and properties of graph polynomials, and how they are typically applied in Feynman integrals. If time permits, I might also comment on the physical background.

Title: Graph Embeddings and Map Colorings

Abstract: The famous  Map Color Theorem says that the chromatic number of a surface of Euler characteristic $c<0$ is equal to $\displaystyle \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This was proved in 1969 by Ringel and Youngs who showed that $K_n$ can be embedded on surfaces of Euler characteristic $c$ such that $\displaystyle n= \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This leads to the study about the  genus distribution of a graph $G$, that is, the number of embeddings of $G$ on surfaces. This talk will go through some recent results about genus distributions of bouquets and cubic graphs.  Some results and conjectures will also be given about the distribution of the  chromatic number of a random map on a given surface.

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.