Author Archives: Shayla Redlin Hume

Online Talk: Nathan Bowler

Posted on by
Reply

Tuesday, Nov 16, 3pm ET (8pm GMT, 9am Wed NZDT)
Nathan Bowler, University of Hamburg
Infinite Maker-Breaker games

 
Abstract:
Consider a game played on a countably infinite complete graph, in which two players, called Maker and Breaker, alternately claim edges. Maker’s aim is that after infinitely many moves she should have claimed all edges of some infinite complete subgraph, and Breaker’s aim is to prevent this. Marit Emde recently found a winning strategy for Maker in this game. We’ll investigate a number of variants of this basic game, and the kinds of winning strategies Maker and Breaker have in them.

Online Talk: Dillon Mayhew

Posted on by
Reply

Tuesday, Nov 9, 3pm EST (8pm GMT, 9am Wed NZDT)
Dillon Mayhew, Victoria University of Wellington
Matroids that are transversal and cotransversal

 
Abstract:
Transversal matroids can be understood geometrically as those matroids obtained by placing points as freely as possible on the faces of a simplex. Transversal matroids have been studied extensively since their discovery in 1965. This study is made more challenging by the fact that the class of transversal matroids is not closed under duality or under taking minors.
 
Less work has been done on the matroids that are both transversal and cotransversal (a matroid is cotransversal if its dual is transversal). My belief is that the class of such matroids should behave a little like matroids representable over a finite field. I will talk about this class with reference to decidable theories, well-quasi-ordering, and the complexity of testing membership. I would also like to know more about minor-closed classes of matroids that are transversal and cotransversal. I have many more questions than answers.

Online Talk: Relinde Jurrius

Posted on by
Reply

Tuesday, Nov 2, 3pm EDT (7pm GMT, 8am Wed NZDT)
Relinde Jurrius, Netherlands Defence Academy
The direct sum of q-matroids

 
Abstract:
For classical matroids, the direct sum is one of the most straightforward methods to make a new matroid out of existing ones. This talk focusses on the direct sum of q-matroids, the q-analogues of matroids. This is a lot less straightforward than in the classical case, as I will try to convince the audience. We will see a definition of the direct sum for q-matroids, using q-polymatroids and matroid union. As a motivation for this definition, I will list several desirable properties of this construction.

For a handwaving and colorful introduction to q-matroids, see the blog post here: https://matroidunion.org/?p=3518. This talk will use roughly the same amount of handwaving and colors and does not assume any prior knowledge about q-matroids.

This talk is based on joint work with Michela Ceria.

Online Talk: Natalie Behague

Posted on by
Reply

Tuesday, Oct 26, 3pm ET (8pm BST, 8am Wed NZST)
Natalie Behague, Ryerson University
Subgraph Games in the Semi-random Graph Process

 
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 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 Prałat and Andrzej Ruciński.