2024 Workshop on (Mostly) Matroids

19 Aug 2024, 09:00 → 23 Aug 2024, 18:00 Asia/Seoul

S236 (IBS Science Culture Center)

Spencer Backman (University of Vermont), Rutger Campbell (Discrete Mathematics Group), Dillon Mayhew (University of Leeds), Sang-il Oum (IBS Discrete Mathematics Group)

The 2024 Workshop on (Mostly) Matroids will be held in-person at the Institute for Basic Science (IBS), Daejeon, South Korea, from August 19, 2024 to August 23, 2024. We expect that most people would arrive on Sunday, August 18 and leave on Saturday, August 24.

Our hope is that this workshop will continue the tradition of previous workshops held in Sittard (2008), Maastricht (2010,2012), Princeton (2014), Eindhoven(2016), Waterloo (2017), and Baton Rouge (2019). The focus will be on all aspects of matroid theory, including its connection to graph theory, algebraic geometry, and other areas of mathematics.

There are no registration fees.

We will bring together 80~90 researchers from all over the world.

See the previous offerings of this workshop:

2017, 2016, 2014, 2012, 2010, 2008

Bus instructions for terminal 1.jpg

Hotel reservation form_ICC Hotel.doc

Monday, 19 August ¶

09:00 Coffee

1 Geometric methods for matroid theory¶

Convex geometry has played a role in matroid theory for at least fifty years, while toric and tropical geometry have been more recent contributors. Results over the last decade have highlighted the power of various geometric or geometrically inspired techniques in matroid theory.  I will survey some recent progress in this direction, with the aim of strengthening connections with other aspects of matroid theory.

Speaker: Graham Denham (Western University)

10:35 Coffee

2 Is There Hope?¶

We know the excluded minors for the matroids representable over GF(2), GF(3) and GF(4). What are the chances of explicitly finding the excluded minors for matroids representable over GF(5)?

We have an excellent understanding of the classes that arise when we consider matroids representable over GF(2) and other fields. We also have an algebraic understanding of the classes that arise for matroids representable over GF(3) and other fields. What are the chances of describing the classes for GF(4) and other fields?

Recent explicit descriptions of the excluded minors for the class of 2-regular matroids and 3-regular matroids (almost) can be thought of as baby steps towards the resolution of the questions posed above. But let's be real, is there genuine hope?

Speaker: Geoff Whittle (Victoria University)

3 Characterising matroids representable over all fields of size at least four¶

A matroid is regular if it is representable over every field. Characterisations of regular matroids are known (Tutte, 1958) in terms of excluded minors, having a totally unimodular representation, and representability over GF(2) and some field of characteristic not two. A matroid is near-regular if it is representable over every field of size at least three. Characterisations of near-regular matroids are known in terms of excluded minors (Hall, Mayhew, van Zwam, 2011), having a near-unimodular representation, and representability over each of {GF(3),GF(8)}, or each of {GF(3),GF(4),GF(5)} (Whittle 1997). In this talk, we consider matroids representable over all fields of size at least four. None of these three types of characterisation are known for this class, but I'll discuss some partial progress for each, and some related open problems. This will include joint work with James Oxley, Charles Semple, and Geoff Whittle; Rudi Pendavingh; and Rutger Campbell.

Speaker: Nick Brettell (Victoria University of Wellington)

11:45 Coffee

4 On the matroid representation over finite rings¶

Matroids introduced by H. Whitney abstract some properties of linear independence among vectors in a vector space over a field. Nevertheless, it is well-known that almost all matroids are non-representable as a set of vectors over a field. It is one of the most significant problems to determine whether a given matroid is representable over some field. In this talk, we propose some representations of matroids by using matrices over finite rings. We will provide a method to construct a matroid by a matrix over a finite ring and some conditions for a matrix over a finite ring to yield some matroid. We also show that some well-known non-representable matroids can be represented by a matrix over a finite ring by our construction.

Speaker: Koji Imamura (Kumamoto University)

12:30 Lunch

5 Towards Rota's conjecture for gain-graphic matroids¶

Rota's famous conjecture for representable matroids says that when F is a finite field, there are only finitely many minimal obstructions for the class of matroids that are linearly-representable using vectors with F as the field of scalars. A proof has been announced by Geelen, Gerards, and Whittle.

Gain-graphic matroids are analogues to matroids represented by vectors: instead of representing the matroid using numbers from a field, we use elements from a group. In order to represent a matroid using group elements, we require an intermediate object known as a gain-graph. Multiple theorems show us that finite-field-representable matroids and finite-gain-graphic matroids play symmetric roles in structural matroid theory: if we want to understand the structure of minor-closed families of matroids, we must understand both representable and gain-graphic classes. So it is natural to seek an analogue of Rota's conjecture for gain-graphic matroids: when H is a finite group, there are only finitely many minimal obstructions for the class of H-gain-graphic matroids.

In this talk I will outline our intended path towards Rota's conjecture for gain-graphic matroids. This is joint work with Daryl Funk.

Speaker: Dillon Mayhew (University of Leeds)

6 Rigidity and reconstruction in matroids of highly connected graphs¶

A graph matroid family $\mathcal{M}$ is a family of matroids $\mathcal{M}(G)$ defined on the edge set of each finite graph $G$ in a compatible and isomorphism-invariant way. We say that $\mathcal{M}$ has the Whitney property if there is a constant $c$ such that every $c$-connected graph $G$ is uniquely determined by $\mathcal{M}(G)$. Similarly, $\mathcal{M}$ has the Lovász-Yemini property if there is a constant $c$ such that for every $c$-connected graph $G$, $\mathcal{M}(G)$ has maximal rank among graphs on the same number of vertices.

In the talk, I will discuss old and new results about these notions. In particular, we will see that for "most" graph matroid families, the Whitney and the Lovász-Yemini properties are equivalent. I will also talk about how related ideas led to solutions of conjectures of Kriesell and Thomassen on highly connected graphs. (Partly based on joint work with Tibor Jordán, Csaba Király and Soma Villányi.)

Speaker: Dániel Garamvölgyi (Alfréd Rényi Institute of Mathematics, Budapest)

14:20 Coffee

7 Infinite matroids on lattices¶

There are at least two well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will give several cryptomorphic definitions of an object that generalizes a matroid in both these ways at once, and argue that they are (in some ways) nicer than the usual finite matroid axioms. This is joint work with Andrew Fulcher.

Speaker: Peter Nelson (University of Waterloo)

8 Unbounded matroids, polymatroids and subspace arrangements¶

The goal of the talk is to introduce the theory of unbounded matroids. These are possibly unbounded Polyhedra in R^d whose vertices are 01 whose edge directions are of the form $e_i-e_j$. We will explore some cryptomorphic variations of these definitions involving linear extensions of posets and relate them to matroids and polymatroids.  We will discuss how these objects can be used to study the geometry of subspace arrangements and present several questions inspired by classical results for matroids. Based on joint work with J. Berggren and J. Martin.

Speaker: José Samper (Pontifical Catholic University of Chile)

Tuesday, 20 August ¶

09:00 Coffee

9 Tropical Ideals¶

Tropical ideals are combinatorial objects introduced with the aim of giving tropical geometry a solid algebraic foundation. They can be thought of as combinatorial generalizations of the possible collections of subsets arising as the supports of all polynomials in an ideal of the polynomial ring. In general, the structure of tropical ideals is dictated by a sequence of 'compatible' matroids. In this talk I will introduce and motivate the notion of tropical ideals, explain their connection to matroid symmetric powers, and discuss work studying some of their main properties and their possible associated varieties.

Speaker: Felipe Rincon

10 Amalgams of matroids, fibre products and tropical graph correspondences¶

We discuss the interplay between certain properties of pairs of matroids and intersection theory of their Bergman fans, which has been extensively studied during the last decade. This provides another connection between tropical algebraic geometry and combinatorics of matroids.
In the first part of the talk, we formulate the theorem claiming that the proper amalgam of two matroids $M_1$ and $M_2$ along their common restriction $N$ exists if and only if the tropical fibre product of Bergman fans $B(M_1){\times }_{B(N)}B(M_2)$ is positive. In the second part of the talk, we introduce the notion of tropical correspondence. These correspondences are tropical subcycles in the product of Bergman fans, similar to their analogues in algebraic geometry. We define a "graph correspondence" for the maps of lattices of flats and prove that this construction is functorial in the case of "covering" maps of lattices. This is done via explicit combinatorial description involving generalization of Bergman fan which we name a "flag fan".
We conclude with an overview of the open questions that arise from this perspective.

Speaker: Dmitry Mineev (Bar-Ilan University, Ramat Gan, Israel)

10:35 Coffee

11 Speyer's g conjecture via external activity of a pair of matroids¶

In 2009, looking to bound the face vectors of matroid subdivisions and tropical linear spaces, Speyer introduced the g-invariant of a matroid. He proved its coefficients nonnegative for matroids representable in characteristic zero and conjectured this in general. Later, Shaw and Speyer and I reduced the question to positivity of the top coefficient. In work in progress with Berget, we prove the conjecture. This talk will overview the combinatorial ingredients of the proof. The principal ones are the restriction to the diagonal $D$ of the Dilworth truncation of a direct sum of two matroids, and a generalisation of external activity for $D$ using the two matroids it is constructed from.

Speaker: Alex Fink (Queen Mary University of London)

12 Symmetric tropical rank 2 matrices¶

In this talk, we discuss the tropicalization of the space of symmetric rank two matrices. Analogous to the result of Markwig and Yu for general tropical rank two matrices, it has a simplicial complex structure as the space of symmetric bicolored trees. As properties of this simplicial complex, we point out that this space is shellable and give several descriptions of the algebraic matroid of the space of symmetric rank two matrices. This is a joint work with May Cai and Josephine Yu.

Speaker: Kisun Lee (Clemson University)

11:45 Coffee

13 Baker-Bowler theory for Lagrangian Grassmannians¶

Baker and Bowler (2019) showed that the Grassmannian can be defined over a tract, a field-like structure generalizing both partial fields and hyperfields.
This notion unifies theories for matroids over partial fields, valuated matroids, and oriented matroids.
We extend Baker-Bowler theory to the Lagrangian Grassmannian which is the set of maximal isotropic subspaces in a $2n$-dimensional symplectic vector space.
By Boege et al. (2019), the Lagrangian Grassmannian is parameterized into the projective space of dimension $2^{n-2}(4+(\genfrac{}{}{0ex}{}{n}{2}))-1$ and its image is cut out by certain quadrics.
We simplify a list of quadrics so that these are apparently induced by the Laplace expansions only concerning principal and almost-principal minors of a symmetric matrix.
From the idea that the strong basis exchange axiom of matroids captures the combinatorial essence of the Grassmann-Pl\"{u}cker relations, we define matroid-like objects, called antisymmetric matroids, from the quadrics for the Lagrangian Grassmannian.
We also provide its cryptomorphic definition in terms of circuits capturing the orthogonality and maximality of vectors in a Lagrangian subspace.
We define antisymmetric matroids over tracts in two equivalent ways, which generalize both Baker-Bowler theory and the parameterization of the Lagrangian Grassmannian.
It provides a new perspective on the Lagrangian Grassmannian over hyperfields such as the tropical hyperfield and the sign hyperfield.
Our proof involves a homotopy theorem for graphs associated with antisymmetric matroids, generalizing Maurer's homotopy theorem for matroids.
We also prove that if a point in the projective space satisfies the $3$-/$4$-term quadratic relations for the Lagrangian Grassmannian and its supports form the bases of an antisymmetric matroid, then it satisfies all quadratic relations, which is motivated by the earlier work of Tutte (1958) for matroids and the Grassmannian.

Speaker: Donggyu Kim (KAIST)

12:30 Lunch

14 Direct sum of q-matroids and linear sets¶

q-Matroids, the q-analogue of matroids, have been intensively invest-
igated in recent years in coding theory due to their close connection with rank metric codes. Indeed, in 2018 it was shown by Jurrius and Pellikaan that a rank metric code induces a q-matroid that captures many of the code’s invariants. In this talk we will deal with the direct sum of q-matroids, a concept recently introduced by Ceria and Jurrius, with a particular focus on the question of representability. We will show that representing the direct sum of t uniform q-matroids is equivalent to constructing special linear sets which are almost scattered with respect to the hyperplanes. In addition, we will give explicit constructions of such linear sets, implying as a byproduct that the direct sum of uniform q-matroids is always representable. This is a joint work with Relinde Jurrius, Alessandro Neri and Ferdinando Zullo.

Speaker: Gianira Alfarano (University College Dublin)

15 Almost all q-matroids are not representable¶

The $q$-analoge of a combinatorial object arises by replacing finite sets with finite dimensional vector spaces. In particular we can view $q$-matroids as $q$-analogues of matroids. One motivation to study $q$-matroids stems from coding theory, as the representable $q$-matroids arise from rank-metric codes. In the matroidal setting Peter Nelson proved in 2018 that asymptotically almost all matroids are non-representable,
therefore one can ask if the same holds true in the $q$-analogue. In this talk we investigate this question and provide a positive answer to it. For this purpose we give a lower bound on the number of all fixed dimensional $q$-matroids, using the theory of constant dimension codes and an upper bound on the number of all representable $q$-matroids, using the concept of zero patterns.

Speaker: Sebastian Degen (Bielefeld University)

14:20 Coffee

16 On a q-analogue of perfect matroid designs¶

A Steiner system is characterized with the subsets (called blocks) satisfying that all $t$-subsets are included in exactly one block. A perfect matroid design (PMD) is a matroid whose flats of the same rank have the same size. Recently, E. Byrne et. al.  proposed a $q$-analogue of PMDs (namely $q$-PMDs) and constructed a non-trivial $q$-PMD from a $q$-analogue of a Steiner system. In this talk, we show some properties of $q$-PMDs and demonstrate that a certain class of $q$-PMDs induces a $q$-Steiner system.

Speaker: Shinya Kawabuchi (Kumamoto University)

17 The cyclic flats of L-polymatroids¶

In recent years, q-polymatroids have drawn interest because of their connection with rank-metric codes. For a special class of q-polymatroids called q-matroids, the fundamental notion of a cyclic flat has been developed as a way to identify the key structural features of a q-matroid. In this talk, we will see a generalisation of the definition of a cyclic flat that can apply to q-polymatroids, as well as a further generalisation, L-polymatroids. The cyclic flats of an L-polymatroid is essentially a reduction of the data of an L-polymatroid such that the L-polymatroid can be retrieved from its cyclic flats. As such, in matroid theory, cyclic flats have been used to characterise numerous invariants.

Speaker: Andrew Fulcher (University College Dublin)

Wednesday, 21 August ¶

09:00 Coffee

18 Graphs embedded on surfaces and their delta-matroids¶

By ``cutting out'' the edges and vertices of a graph cellularly embedded in a surface, we obtain a ribbon graph. A partial Petrial is obtained from a ribbon graph by selecting a subset of the ribbon edges adding a half-twist to each. Delta-matroids generalize ribbon graphs similarly to the way that matroids generalize graphs. The ribbon graph partial Petrial is the analogue of a more general delta-matroid operation. In this talk, we characterize the set of delta-matroids that is closed under this delta-matroid operation by a set of minimal obstructions.

Speaker: Carolyn Chun (University of Maryland)

19 Graphs in surfaces, their one-face subgraphs, and the critical group¶

Critical groups are groups associated with graphs. They are well-established in combinatorics; closely related to the graph Laplacian and arising in several contexts such as chip firing and parking functions. The critical group of a graph is finite and Abelian, and its order is the number of spanning trees in the graph, a fact equivalent to Kirchhoff’s Matrix--Tree Theorem.

What happens if we want to define critical groups for graphs embedded in surfaces, rather than for graphs in the abstract? 

In this talk I'll offer an answer to this question. I'll describe an analogue of the critical group for an embedded graph. We'll see how it relates to the classical critical groups, as well as to Chumtov's partial-duals, Bouchet's delta-matroids, and a Matrix--quasi-Tree Theorem of Macris and Pule.

This is joint work with Criel Merino and Steven D. Noble.

Speaker: Iain Moffatt (Royal Holloway University of London)

10:35 Coffee

20 Clique minors in dense matroids¶

Given $\ell$ and $t$ positive integers, we will give a singly exponential bound on the number of points a $U_{2,\ell }$-minor-free matroid with can have without containing $M(K_t)$ as a minor.

Speaker: Fernanda Rivera Omaña (University of Waterloo)

21 Chordal matroids arising from generalized parallel connections¶

In 1961, Dirac showed that chordal graphs are exactly the graphs that can be constructed from complete graphs by a sequence of clique-sums. By analogy with Dirac's result, we define the class of $GF(q)$-chordal matroids as those matroids that can be constructed from projective geometries over $GF(q)$ by a sequence of generalized parallel connections across projective geometries over $GF(q)$. We characterize the class of such matroids in terms of forbidden induced minors for all powers of $q$ and also in terms of forbidden flats whenever $q$ is prime. This talk is based on joint work with James Oxley.

Speaker: Dylan Douthitt (Louisiana State University)

11:45 Coffee

22 Connectivity systems, path-width, and well-quasi-ordering¶

We prove that, for any integer $k$, there are only finitely many excluded minors for the class of matroids of path-width $k$. This result is obtained as a consequence of a well-quasi-ordering result on connectivty systems of bounded path-width. This is joint work with Rutger Campbell.

Speaker: Jim Geelen (University of Waterloo)

12:30 Lunch

23 Average Hyperplane-Size in Complex-Representable Matroids¶

In 1941, Melchior proved that the average size of a line in a simple rank-3 real-representable matroid is less than three. A similar theorem for the complex-representable matroids was proved by Hirzebruch in 1983. In this talk, we discuss the problem of extending these results to flats of higher rank. We show that, in every simple rank-4 real-representable matroid which is not the direct sum of two lines, the average size of a plane is at most an absolute constant. We also present a generalization of this result to hyperplanes of arbitrary rank.

This talk is based on joint work with Rutger Campbell, Jim Geelen and Ben Lund.

Speaker: Matthew Kroeker (University of Waterloo)

24 Convex geometry of building sets¶

Building sets were introduced in the study of wonderful compactifications
of hyperplane arrangement complements and were later generalized to finite meet-
semilattices. Convex geometries, the duals of antimatroids, offer a robust combinatorial
abstraction of convexity. Supersolvable convex geometries and antimatroids appear in
the study of poset closure operators, Coxeter groups, and matroid activities. We prove
that the building sets on a finite meet-semilattice form a supersolvable convex geometry.
As an application, we demonstrate that building sets and nested set complexes respect
certain restrictions of finite meet-semilattices unifying and extending results of several
authors.

Speaker: Rick Danner (University of Vermont)

14:20 Coffee

25 Combinatorics of boundary algebras.¶

Boundary algebras are an important tool in the categorification, by Jensen--King--Su and by Pressland, of cluster structures on positroid varieties, defined by Scott and by Galashin--Lam. Each connected positroid has a corresponding boundary algebra. We give a combinatorial description of the set of algebras which arise as the boundary algebra of some positroid. Using this combinatorial structure, we give the first complete description of the minimal relations in the boundary algebra. This talk is based on joint work with Jonah Berggren.

Speaker: Jonathan Boretsky (MPI Leipzig)

Thursday, 22 August ¶

09:00 Coffee

26 Complexity of log-concave inequalities in matroids¶

A sequence of nonnegative real numbers $a_1,a_2,\dots ,a_n$, is log-concave if $a_i^2\ge a_{i-1}{a}_{i+1}$ for all $i$ ranging from 2 to $n-1$. Log-concavity naturally arises in various aspects of mathematics, each characterized by different underlying mechanisms. Examples range from inequalities that are readily provable, such as the binomial coefficients $a_i=(\genfrac{}{}{0ex}{}{n}{i})$, to intricate inequalities that have taken decades to resolve, such as the number of independent sets $a_i$ in a matroid $M$ with $i$ elements (otherwise known as Mason's conjecture). It is then natural to ask if it can be shown that the latter type of inequalities is intrinsically more challenging than the former. In this talk, we provide a rigorous framework to answer this type of questions, by employing a combination of combinatorics, complexity theory, and geometry. This is joint work with Igor Pak and is intended for a general audience.

Speaker: Swee Hong Chan (Rutgers University)

27 Chow rings and augmented Chow rings of matroids are equivariant γ-positive¶

Chow rings and augmented Chow rings of matroids were considered and played important roles in the settlement of the Heron-Rota-Welsh conjecture and the Dowling-Wilson top-heavy conjecture. Their Hilbert series have been extensively studied since then. It was shown by Ferroni, Mathern, Steven, and Vecchi, and indepedently by Wang, that the Hilbert series of Chow rings of matroids are γ-positive using inductive arguement from semismall decompositions. However, they do not have an interpretation for the coefficients in the γ-expansion. In the recent paper, Angarone, Nathanson, and Reiner conjectured that Chow ring of matroids are equivariant γ-positive under the action of groups of automorphisms of matroids. We prove this conjecture, showing that both Chow rings and augmented Chow rings of matroids are equivariant γ-positive. Moreover, we obtain explicit descriptions for the coefficients of the equivariant γ-expansions.

Speaker: Hsin-Chieh Liao (University of Miami)

10:35 Coffee

28 Representations on the cohomology of the moduli space of pointed rational curves, permutation representations and log concavity¶

The Chow ring of the graphical matroid of the complete graph with n-1 vertices (with respect to the minimal building set) is isomorphic to that of the moduli space of n-pointed rational curves. Therefore, it is naturally a graded representation of the n-th symmetric group.

In this talk, we provide a closed-form formula for this representation, in terms of weighted rooted trees, which we introduce as combinatorial gadgets. Using this, we explore the positivity of this representation as a permutation representation, and the asymptotic log concavity of the multiplicities of the trivial representation. We will also discuss about the multiplicities of the other irreducible representations.

Based on joint works with Jinwon Choi and Young-Hoon Kiem.

Speaker: Donggun Lee (Institute for Basic Science)

29 Intrinsic properties of the gamma vector and matroids¶

We’ll discuss the gamma vector, which is an invariant of (reciprocal) polynomials whose positivity lies somewhere between unimodality and real-rootedness. It shows up in many seemingly unrelated contexts including permutation statistics, signs of Euler characteristics vs. curvatures of (piecewise Euclidean) manifolds, and Chow rings of matroids. Before asking about positivity, a natural question to ask while trying to understand why this is the case is the question of what this invariant measures in the first place. While there are classes of objects collecting when positivity is observed (the second setting in particular), the invariant itself is rather poorly understood (except possibly the last component). We explore the question using an explicit formula for (an extension of) this invariant in terms of the input polynomial along with tools from algebraic geometry and geometric combinatorics. For example, we make observations that contrast with heuristics stated regarding the general lower bound behavior of h-vectors when it was originally defined. This perspective also leads to natural connections to convexity properties of polynomials specific to matroids and structures of matroid invariants coming from algebraic geometry.

Speaker: Soohyun Park (Hebrew University of Jerusalem)

11:45 Coffee

30 Lawrence polytopes and some invariants of a graph¶

We use two dual Lawrence polytopes $P$ and $P^{\ast }$ of a graph $G$ to study the graph. The $h$-vector of the graphic (resp. cographic) matroid complex associated to $G$ coincides with the $h^{\ast }$-vector of the Lawrence polytope $P$ (resp. $P^{\ast }$). In general, the $h$-vector is an invariant defined for an abstract simplicial complex, which encodes the number of faces of different dimensions. The $h^{\ast }$-vector, a.k.a. the $\delta$-polynomial, is an invariant defined for a rational polytope obtained by dilating the polytope. By dissecting the Lawrence polytopes, we may study the $h$-vectors associated to the graph $G$ at a finer level. In particular, we understand the reduced divisors of the graph $G$ in a more geometric way.

Speaker: Changxin Ding

12:30 Lunch

31 Matroids and binary functions¶

A binary function is a function $f:2^E\to \mathbb{C}$ for which $f(\mathrm{\varnothing })=1$, where $E$ is a finite ground set. Binary functions are closely related to quantum registers. They generalise binary matroids in the sense that any indicator function of a linear space over GF(2) is a $\{0,1\}$-valued binary function (using the natural correspondence between subsets of $E$ and their characteristic vectors in $\text{GF}(2{)}^E$); in fact, the author showed in 1993 that every matroid has an associated binary function, although it will not necessarily be just $\{0,1\}$-valued.

In a series of papers over 1993-2019, the author generalised some standard matroid transforms and operations — including rank, deletion, contraction, and duality (via the Hadamard transform) — to binary functions, and gave new versions of them that are parameterised by the complex numbers. In each of these settings, a theory of Tutte-Whitney polynomials was developed.

In this talk we review this work and discuss some recent results.

Speaker: Graham Farr (Monash University)

32 Tutte polynomials and split matroids¶

Surprisingly many interesting invariants of graphs, hyperplane arrangments and matroids are valuative. The two most prominent examples of valuative matroid invariants are the Tutte polynomial and the $\mathcal{G}$-invariant. The relevance of the $\mathcal{G}$-invariant steams from its universal property that any other valuative invariant can be obtained as a specialization. Nevertheless, the most intense studied invariant of matroids is clearly the Tutte polynomial as it respects deletion and contraction. An interesting question therefore is on which minor and duality closed classes of matroids is the Tutte polynomial universal. In my talk I will give answer to this question in which the well structured class of (elementary) split matroids plays a prominent role.

This talk is based on joint work with Luis Ferroni.

Speaker: Benjamin Schröter (KTH Royal Institute of Technology)

14:20 Coffee

33 Bounds on the number of cells of the Dressian¶

A valuation of a matroid $M$ with set of bases $\mathcal{B}$ is a function $\nu :\mathcal{B}\to \mathbb{R}$ so that

• (V) for all $B,B^{\prime }\in \mathcal{B}$ and all $e\in B\setminus B^{\prime }$ there exists an $f\in B^{\prime }\setminus B$ such that
  $\nu (B)+\nu (B^{\prime })\ge \nu (B-e+f)+\nu (B^{\prime }+e-f).$

The Dressian $\mathcal{D}(M)$ is defined as the set of all valuations of $M$. The Dressian of $M$ is the support of a polyhedral complex in ${\mathbb{R}}^{\mathcal{B}}$ whose cells are polyhedral cones. We investigate $\mathrm{\#}\mathcal{D}(M)$, the number of cells, and $\dim \mathcal{D}(M)$, the maximum dimension of any cell.

We show that if $M$ is a matroid on an $n$-element groundset of rank $r\ge t\ge 3$ , then

$\frac{\dim \mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})}\le \frac{max\{\dim \mathcal{D}(M/S),S\in (\genfrac{}{}{0ex}{}{E}{r-t})\text{ independent}\}}{(\genfrac{}{}{0ex}{}{n-r+t}{t})}\le \frac{3}{n-r+3}$

and

$\frac{{\log }_2\mathrm{\#}\mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})}\le \frac{max\{{\log }_2\mathrm{\#}\mathcal{D}(M/S):S\in (\genfrac{}{}{0ex}{}{E}{r-t})\text{ independent }\}}{(\genfrac{}{}{0ex}{}{n-r+t}{t})}O(\ln (n))\le \frac{O(\ln (n{)}^2)}{n}.$

For uniform matroids $M=U(r,n)$ these upper bounds may be compared to the lower bounds

$\frac{1}{n}\le \frac{\dim \mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})},\frac{1}{n}\le \frac{{\log }_2\mathrm{\#}\mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})}$

that follow a previously known construction of valuations of $U(r,n)$ from matroids of rank $r$ on $n$ elements. For non-uniform matroids, we also obtain somewhat tighter upper bounds in terms of the number of free generators of the Tutte group of $M$.

Our methods include an analogue of Shearers' Entropy Lemma for bounding the dimension of a linear subspace, and a container method for collections of linear subspaces.

Speaker: Rudi Pendavingh (Eindhoven Technical University)

34 Filtrations of tope spaces of oriented matroids¶

Oriented matroids are matroids with extra sign data, and they are useful in the tropical study of real algebraic geometry. In order to study the topology of real algebraic/tropical hypersurfaces constructed from patchworking, Renaudineau and Shaw introduced an algebraically defined filtration of the tope spaces of oriented matroids (for a real hyperplane arrangement, the tope space is the homology of its complement) based on Quillen filtration. We will prove the equivalence of their filtration and the topologically defined Kalinin filtration, as well as the combinatorially defined Gelfand-Varchenko dual degree filtration.

Speaker: Chi Ho Yuen

18:00 Banquet

Friday, 23 August ¶

09:00 Coffee

35 Contracting a Single Element in a Transversal Matroid¶

It is well known that the class of transversal matroids is not closed under contraction or duality. The complexity of deciding whether a minor or dual of a transversal matroid remains transversal is in ${\mathrm{\Sigma }}_2$ and thus far there has been no improvement on this bound. We explore this issue, providing a polynomial time algorithm for determining whether a single element contraction of a transversal matroid remains transversal. If so, our algorithm also provides a transversal representation. We then develop the techniques used in search of a polynomial time algorithm for determining whether the dual of a transversal matroid remains transversal.

Speaker: Sam Bastida (Victoria University of Wellington)

36 Cyclic matroids¶

Tutte showed that wheels and whirls are precisely the 3-connected matroids in which every element is contained in a 3-element circuit and a 3-element cocircuit. In fact, wheels and whirls have the stronger property that there is a circular ordering of their ground set such that every two consecutive elements are contained in a 3-element circuit and a 3-element cocircuit. In this talk, we investigate matroids satisfying this property and discuss some recent results. This is joint work with Nick Brettell, Deborah Chun, Tara Fife, and Gerry Toft.

Speaker: Charles Semple

10:35 Coffee

37 Frame matroids with a distinguished frame element¶

A matroid is frame if it may be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. This gives frame matroids natural graphical representations as biased graphs.
We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a polynomial time recognition algorithm for frame matroids with a distinguished frame element.

Speaker: James Davies (Cambridge)

38 Piecing together quasi-graphic matroids from graphic pieces¶

Quasi-graphic matroids provide a common generalisation of frame and lifted graphic matroids, with better algorithmic properties. We explain how to efficiently construct a framework for a quasi-graphic matroid given a schema for dividing that framework into pieces, each of which is graphic. This is joint work with James Davies, Daryl Funk, Jim Geelen and Peter Nelson.

Speaker: Nathan Bowler (University of Hamburg)

11:45 Coffee

39 Matroids of Symmetric Rigid Frameworks¶

A $2$-dimensional framework $(G,p)$ is an embedding of a graph $G=(V,E)$ into $2$-dimensional space, such that each vertex $v$ is assigned a pair of coordinates $p(v)=(x_v,y_v)\in {\mathbb{R}}^2$. A framework is rigid if the only motions of the vertices in the plane that preserve all edge lengths are isometries of the plane. It is well-known (since at least the 1920s) that when the set of coordinates $p(V)$ are algebraically independent over $\mathbb{Q}$, then the rigidity of the framework is determined by the rank of the rigidity matroid of the graph.

However, real-life structures are typically not generic, and often exhibit symmetry. In the last 30 years there has been a lot of research into extending the definition of the rigidity matroid to different symmetry groups. Many of these results first model the framework as a group-labelled graph and then define a matroid on the graph. In this talk, I'll present an approach that unifies many of these results. Unfortunately the main open problem in the area, characterising rigidity under even dihedral groups, still remains open.

Speaker: Katie Clinch (UNSW Sydney)

12:30 Lunch

40 A coarse Erdős-Pósa theorem¶

An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erdős-Pósa theorem to induced packings of cycles. More specifically, we show that there exists a function $f(k)=\mathcal{O}(k\log k)$ such that for every positive integer $k$, every graph $G$ contains either an induced packing of $k$ cycles or a set $X$ of at most $f(k)$ vertices such that the closed neighbourhood of $X$ intersects all cycles in $G$. Our proof is constructive and yields a polynomial-time algorithm finding either the induced packing of cycles or the set $X$. Furthermore, we show that for every positive integer $d$, if a graph $G$ does not contain two cycles at distance more than $d$, then $G$ contains sets $X_1,X_2\subseteq V(G)$ with $|X_1|\le 12(d+1)$ and $|X_2|\le 12$ such that after removing the ball of radius $2d$ around $X_1$ or the ball of radius $3d$ around $X_2$, the resulting graphs are forests.

As a corollary, we prove that every graph with no $K_{1,t}$ induced subgraph and no induced packing of $k$ cycles has tree-independence number at most $\mathcal{O}(tk\log k)$, and one can construct a corresponding tree-decomposition in polynomial time. This resolves a special case of a conjecture of Dallard et al. (arXiv:2402.11222), and implies that on such graphs, many NP-hard problems, such as Maximum Weight Independent Set, Maximum Weight Induced Matching, Graph Homomorphism, and Minimum Weight Feedback Vertex Set, are solvable in polynomial time. On the other hand, we show that the class of all graphs with no $K_{1,3}$ induced subgraph and no two cycles at distance more than $2$ has unbounded tree-independence number.

This is joint work with Jungho Ahn, Pascal Gollin, and Tony Huynh.

Speaker: O-joung Kwon (Hanyang university)

41 Erdős-Pósa property of tripods in directed graphs¶

Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$.
A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix.

This talk presents a proof that tripods in directed graphs exhibit the Erdős-Pósa property.
More precisely, there is a function $f:\mathbb{N}\to \mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$.

One of the tools applied to obtain this result is the matroid intersection theorem for gammoids.
The presented work is joint with Marcin Briański, Karolina Okrasa and Michał Pilipczuk.

Speaker: Meike Hatzel

14:20 Coffee

42 Reconfiguration of Basis Pairs in Regular Matroids¶

In recent years, combinatorial reconfiguration problems have attracted great attention due to their connection to various topics such as optimization, counting, enumeration, or sampling. One of the most intriguing open questions concerns the exchange distance of two matroid basis sequences, a problem that appears in several areas of computer science and mathematics. White (1980) proposed a conjecture for the characterization of two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to toric ideals and Gröbner bases. In this work, we verify White's conjecture for basis sequences of length two in regular matroids, a problem that was formulated as a separate question by Farber, Richter, and Shank (1985) and Andres, Hochstättler, and Merkel (2014). Most of previous work on White's conjecture has not considered the question from an algorithmic perspective. We study the problem from an optimization point of view: our proof implies a polynomial algorithm for determining a sequence of symmetric exchanges that transforms a basis pair into another, thus providing the first polynomial upper bound on the exchange distance of basis pairs in regular matroids. As a byproduct, we verify a conjecture of Gabow (1976) on the serial symmetric exchange property of matroids for the regular case.

Speaker: Tamás Schwarcz (ELTE Eötvös Loránd University)

15:05 Discussion