Online Talk: Dillon Mayhew

Posted on November 3, 2021 by Shayla Redlin Hume

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

YouTube: https://youtu.be/iXt7d31m3PM

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 October 27, 2021 by Shayla Redlin Hume

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

YouTube: https://youtu.be/tgTc9R5ZZUw

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 October 20, 2021 by Shayla Redlin Hume

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

YouTube: https://youtu.be/oxWKnYpAzKk

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.