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:
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.
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?
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.
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.
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.
A graph matroid family
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.)
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.
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
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.
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
We conclude with an overview of the open questions that arise from this perspective.
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
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.
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
By Boege et al. (2019), the Lagrangian Grassmannian is parameterized into the projective space of dimension
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
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.
The
therefore one can ask if the same holds true in the
A Steiner system is characterized with the subsets (called blocks) satisfying that all
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.
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.
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.
Given
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
We prove that, for any integer
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.
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.
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.
A sequence of nonnegative real numbers
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.
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.
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.
We use two dual Lawrence polytopes
A binary function is a function
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.
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
This talk is based on joint work with Luis Ferroni.
A valuation of a matroid
The Dressian
We show that if
and
For uniform matroids
that follow a previously known construction of valuations of
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.
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.
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
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.
A matroid is frame if it may be extended such that it possesses a basis
We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element
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.
A
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.
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
As a corollary, we prove that every graph with no
This is joint work with Jungho Ahn, Pascal Gollin, and Tony Huynh.
Let
A tripod in
This talk presents a proof that tripods in directed graphs exhibit the Erdős-Pósa property.
More precisely, there is a function
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.
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.