• home

Abstract:
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the girl-optimal (boy-pessimal) stable matching. The classical boy-proposal deferred-acceptance algorithm returns the supremum of the lattice, that is, the boy-optimal stable matching. In this paper, we study the smallest group of girls, called the minimum winning coalition of girls, that can act strategically, but independently, to force the boy-proposal deferred-acceptance algorithm to output the girl-optimal stable matching. We characterize the minimum winning coalition in terms of stable matching rotations and show that its cardinality can take on any value between $0$ and $\floor{\frac{n}{2}}$, for instances with $n$ boys and $n$ girls. Our two main results concern the random matching model. First, the expected cardinality of the minimum winning coalition is small, specifically $(\frac{1}{2}+o(1))\log{n}$. This resolves a conjecture of Kupfer. Second, in contrast, a randomly selected coalition must contain nearly every girl to ensure it is a winning coalition asymptotically almost surely. Equivalently, for any $\varepsilon>0$, the probability a random group of $(1-\varepsilon)n$ girls is not a winning coalition is at least $\delta(\varepsilon)>0$. This is joint work with Sergey Norin and Adrian Vetta.

Abstract: A spanning tree is a connected subgraph of a graph with no cycles. I will explain some well-known connection between such collection of trees and some Poissonian collection of loops, and a magical algorithm (known as Wilson's alorithm) to sample such trees very fast. Then I will try to explain a recent extension to the multiply connected setting, and pose an open question in the end. Joint work with N. Berestycki and B. Laslier.

Abstract: A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that a graph with average degree O(k^2) guarantees the existence of a K_k-subdivision. We study two directions extending this result.

Firstly, Verstraëte conjectured in 2002 that the quadratic bound O(k^2) would guarantee already two vertex-disjoint isomorphic copies of a K_k-subdivision. Secondly, Thomassen conjectured in 1984 that for each k \in \mathbb{N} there is some d = d(k) such that every graph with average degree at least d contains a balanced subdivision of K_k. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d(k) remains open.

In this talk, we show that the quadratic bound O(k^2) suffices to force a balanced K_k-subdivision. This gives the optimal bound on d(k) needed in Thomassen's conjecture and implies the existence of O(1) many vertex-disjoint isomorphic K_k-subdivisions, confirming Verstraëte's conjecture in a strong sense.

Abstract:
In the biased Hamilton Cycle Maker-Breaker game, two players alternate choosing edges from a complete graph. In the game with bias b, Maker chooses one previously unchosen edge in each turn and Breaker chooses b. The game is Maker-win for the given bias if Maker can ensure she chooses the edges of a Hamilton Cycle and Breaker-win otherwise.

Letting n be the number of vertices, if the bias is 0 then Maker wins the game in n moves. On the other hand, if the bias b=b(n) is {n choose 2}-1 then Breaker wins. Furthermore, if Breaker wins for some bias b, then she also wins for bias b+1. We discuss the threshold at which the game becomes Breaker win, and the number of moves maker needs to ensure she wins for b below this threshold, which is called the speed of the game.

Warmup: What bounds can you obtain on the threshold and speed without a literature search? Any ideas how to proceed?

Abstract: Achievement games are a class of combinatorial games in which two players take turns selecting points from a set (the board), with the goal of being the first to occupy one of the previously designated "winning" subsets. In this talk, we will consider the avoidance variant, in which the first player to occupy such a set loses the game. As a strategy-stealing argument can be used to show that an achievement game cannot be a second-player win, one might expect that the avoidance variant cannot be a first-player win. However, it turns out that we can find transitive avoidance games that are first-player wins for all board sizes which are not primes or powers of two. This talk is based on the paper "Transitive Avoidance Games" by J. Robert Johnson, Imre Leader, and Mark Walters.

Abstract: A graph is $P_4$-sparse if every set of five vertices induces at most one $P_4$. $P_4$-sparse graphs generalize cographs and admit a tree representation. We consider the problem of deciding whether a $P_4$-sparse graph can be partitioned into two forests (or equivalently, has vertex arboricity 2). We give a characterization in terms of minimal obstructions for $P_4$-sparse graphs of vertex arboricity 2. We also show how these minimal obstructions can be extended for constructing $P_4$-sparse graphs of higher vertex arboricity.

Zoom link.

Zoom link.

Abstract: Thomassen famously showed that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable. These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex is contained. I will present a local choosability theorem that unifies the two theorems of Thomassen mentioned above. This is joint work with Luke Postle.