Since the introduction of cluster algebras by Fomin and Zelevinsky in 2002, there has been significant interest in cluster algebras of surface type. These algebras are particularly noteworthy due to their ability to construct various combinatorial structures like snake graphs, T-paths, and posets, which are useful for proving key structural properties such as positivity or the existence of bases. In this talk, we will begin by presenting a cluster expansion formula that integrates the work of Musiker, Schiffler, and Williams with contributions from Wilson, utilizing poset representatives for arcs on triangulated surfaces. Using these posets and the expansion formula as tools, we will demonstrate skein relations, which resolve intersections or incompatibilities between arcs. Topologically, a skein relation replaces intersecting arcs or arcs with self-intersections with two sets of arcs that avoid the intersection differently. Additionally, we will show that all skein relations on punctured surfaces include a term that is not divisible by any coefficient variable. Consequently, we will see that the bangles and bracelets form spanning sets and exhibit linear independence. This work is done in collaboration with Esther Banaian and Elizabeth Kelley.

We provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs defined by polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs associated with Diophantine tuples and their generalizations from number theory. As an application, we provide new lower bounds on the clique number and independence number of general quasi-random graphs. In particular, we give a sufficient condition for the clique number of quasi-random graphs of order $n$ to be at least $(1-o(1))\log_{3.008}n$. Such a condition applies to many classical quasi-random graphs, including Paley graphs and Paley sum graphs, as well as some new Paley-like graphs we construct. If time permits, we also discuss some problems of diophantine tuples arising from number theory, which is our original motivation. This is joint work with Seoyoung Kim and Chi Hoi Yip.

We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth at least t. This is joint work with Sepher Hajebi and Sophie Spirkl.

A vertex colouring of a hypergraph is $c$-strong if every edge $e$ sees at least $\min\{c, |e|\}$ distinct colours. Let $\chi(t,c)$ denote the least number of colours needed so that every $t$-intersecting hypergraph has a $c$-strong colouring. In 2012, Blais, Weinstein and Yoshida introduced this parameter and initiated study on when $\chi(t,c)$ is finite: they showed that $\chi(t,c)$ is finite whenever $t \geq c$ and unbounded when $t\leq c-2$. The boundary case $\chi(c-1, c)$ has remained elusive for some time: $\chi(1,2)$ is known to be finite by an easy classical result, and $\chi(2,3)$ was shown to be finite by Chung and independently by Colucci and Gyárfás in 2013. In this talk, we present some recent work with Kevin Hendrey, Freddie Illingworth and Nina Kamčev in which we fill in this gap by showing that $\chi(c-1, c)$ is finite in general.

Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020, JACM 2022) to break a natural long-standing barrier in edge-weighted online bipartite matching. They posed two open questions, one of which was the following: Can we obtain n-way OCS for $n >2$, in which the algorithm can be given $n >2$ elements to choose from at each timestep? In this talk, we affirmatively answer this open question by presenting a three-way OCS which is simple to describe: it internally runs two instances of two-way OCS, one of which is fed with the output of the other. Contrast to its simple construction, we face a new challenge in analysis that the final output probability distribution of our three-way OCS is highly elusive since it requires the actual output distribution of two-way OCS. We show how we tackle this challenge by approximating the output distribution of two-way OCS by a flatter distribution serving as a safe surrogate. This is joint work with Hyung-Chan An.

Very little is known about critical properties of graphs in the hierarchy of monotone classes, i.e. classes closed under taking (not necessarily induced) subgraphs. We distinguish four important levels in this hierarchy and discuss possible new levels by focusing on the Hamiltonian cycle problem. In particular, we obtain a number of results for this problem on monotone classes.

A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. A cross-cap drawing of a graph G with g cross-caps can be used to represent an embedding of G on a non-orientable surface of genus g. Mohar conjectured that any triangulation of a non-orientable surface of genus g admits a cross-cap drawing with g cross-caps in which each edge of the triangulation enters each cross-cap at most once. Motivated by Mohar’s conjecture, Schaefer and Stefankovic provided an algorithm that computes a cross-cap drawing with a minimal number of cross-caps for a graph G such that each edge of the graph enters each cross-cap at most twice. In this talk, I will first outline a connection between cross-cap drawings and an algorithm coming from computational biology to compute the signed reversal distance between two permutations. This connection will then be leveraged to answer two computational problems on graphs embedded on surfaces. First, I show how to compute a “short” canonical decomposition for a non-orientable surface with a graph embedded on it. Such canonical decompositions were known for orientable surfaces, but the techniques used to compute them do not generalize to non-orientable surfaces due to their more complex nature. Second, I explain how to build a counter example to a stronger version of Mohar’s conjecture that is stated for pseudo-triangulations. This is joint work with Alfredo Hubard and Arnaud de Mesmay.

In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉. In this talk, we prove that Aharoni’s conjecture holds up to an additive constant. Specifically, we show that for each fixed r, there exists a constant c such that if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most n/r+c. This is joint work with Patrick Hompe.