• home

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.

Abstract:
One of the $\geq 10^{10^{10}}$ things Erd\H{o}s did in 1982 was ask the following question: for which values $k$ do there exist a set of $k$ points on the plane, no three on a line and no four on a circle, such that for every $i \in \{1,\ldots,k-1\}$, there exists a pairwise distance between its points that occurs exactly $i$ times. A set satisfying the above property is called Erd\H{o}s-deep. Using this problem as a launch point, I will introduce a related problem about finding families of $s$ Erd\H{o}s-deep sets in $\mathbb{Z}_n$ that, as a family, also satisfy a version of the Erd\H{o}s-deep property. After building the context for this related problem, I will present an overview of our argument proving the classification of the case when $s=2$. I will then briefly mention a construction for square $s$ that leverages a nice binomial identity. Time permitting: A significant non-mathematical motivation for classifying Erd\H{o}s-deep families is that they have a nice musical interpretation as systems of rhythms, so if there is time, I hope to share some thoughts on that (and possibly a brief and humble .midi example!). Based on joint work with Peter Dukes.

Abstract: Is it possible to partition a disk in the plane into finitely many pieces and re-assemble those pieces (without distortion) to yield a partition of the square? This question was asked by Tarski back in 1925 and answered by Laczkovich some 65 years later. Spoiler alert: the answer is "yes."

Laczkovich's proof uses the Axiom of Choice in a strong way and so the pieces of his partition can be very hard to imagine. In 2017, two new proofs emerged which achieve pieces that are Lebesgue measurable or even Borel; the latter result is fully "constructive." We improve on these results by constructively achieving pieces which have (a) lower Borel complexity and (b) "small" boundaries. A benefit of the second condition is that, in contrast to the previous results, the pieces of our partition can, in some sense, be "visualized." The proof uses three concepts that are familiar to any graph-theorist: matchings, network flows and Euler circuits. Based on joint work with András Máthé and Oleg Pikhurko.

The talk will be live, in-person in Clearihue C115, and also available (livestreamed) on Zoom via the link below. The speaker will be in the seminar room.

Zoom link.

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.

The list homomorphism problem for a fixed signed graph $(H,\pi)$ takes as input a signed graph $(G, \sigma)$, equipped with lists $L(v) \subseteq V(H)$, $v \in V(G)$, of allowed images, and asks if there is a homomorphism $\varphi: (G, \sigma) \to (H, \pi)$ classify the computational complexity of this problem when $H$ is a tree (irreflexive, reflexive, and general). The polynomial targets exhibit interesting structures. The tools developed are useful for general targets, and the patterns discovered for trees suggest nice families (such as the bi-arc graphs which characterize the problem for graphs) may classify the polynomial cases in general.

This is joint work with Jan Bok, Tom\'{a}s Feder, Pavol Hell, and Nikola Jedli\v{c}kov\'{a}

Abstract: The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.

We will consider the property of constructing a fixed graph G as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 – 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.

This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.

Abstract: Given a graph G, a decomposition of G is a partition of its edges. A graph is (d, h)-decomposable if its edge set can be partitioned into a d-degenerate graph and a graph with maximum degree at most h. In this talk, we present results related to the (d,h)-decomposition problem of planar graphs.

Please contact the organizer if you need the Zoom link.

Please contact the organizer for the Zoom link.

Please contact the organizer for the Zoom link.

Aaron will speak on the paper "An introduction to the discharging method via graph coloring” by Dan Cranston and Doug West.

Abstract: In this talk, we will investigate the extensions of the cycle matroid of a complete graph. I will show that the number of these extensions is surprisingly large.

Please contact the organizer for the Zoom link.