Name: 2024 Workshop on (Mostly) Matroids
Start: 2024-08-19T09:00:00+09:00
End: 2024-08-23T18:00:00+09:00
Location: IBS Science Culture Center

2024 Workshop on (Mostly) Matroids

from Monday, 19 August 2024 (09:00) to Friday, 23 August 2024 (18:00)

Monday, 19 August 2024

09:00 Coffee
Coffee
09:00 - 09:45
Room: S236
09:45 Geometric methods for matroid theory - Graham Denham (Western University)
Geometric methods for matroid theory
- Graham Denham (Western University)
09:45 - 10:35
Room: S236 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.
10:35 Coffee
Coffee
10:35 - 10:55
Room: S236
10:55 Is There Hope? - Geoff Whittle (Victoria University)
Is There Hope?
- Geoff Whittle (Victoria University)
10:55 - 11:20
Room: S236 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?
11:20 Characterising matroids representable over all fields of size at least four - Nick Brettell (Victoria University of Wellington)
Characterising matroids representable over all fields of size at least four
- Nick Brettell (Victoria University of Wellington)
11:20 - 11:45
Room: S236 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.
11:45 Coffee
Coffee
11:45 - 12:05
Room: S236
12:05 On the matroid representation over finite rings - Koji Imamura (Kumamoto University)
On the matroid representation over finite rings
- Koji Imamura (Kumamoto University)
12:05 - 12:30
Room: S236 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.
12:30 Lunch
Lunch
12:30 - 13:30
Room: IBS Research Building
13:30 Towards Rota's conjecture for gain-graphic matroids - Dillon Mayhew (University of Leeds)
Towards Rota's conjecture for gain-graphic matroids
- Dillon Mayhew (University of Leeds)
13:30 - 13:55
Room: S236 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.
13:55 Rigidity and reconstruction in matroids of highly connected graphs - Dániel Garamvölgyi (Alfréd Rényi Institute of Mathematics, Budapest)
Rigidity and reconstruction in matroids of highly connected graphs
- Dániel Garamvölgyi (Alfréd Rényi Institute of Mathematics, Budapest)
13:55 - 14:20
Room: S236 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.)
14:20 Coffee
Coffee
14:20 - 14:40
Room: S236
14:40 Infinite matroids on lattices - Peter Nelson (University of Waterloo)
Infinite matroids on lattices
- Peter Nelson (University of Waterloo)
14:40 - 15:05
Room: S236 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.
15:05 Unbounded matroids, polymatroids and subspace arrangements - José Samper (Pontifical Catholic University of Chile)
Unbounded matroids, polymatroids and subspace arrangements
- José Samper (Pontifical Catholic University of Chile)
15:05 - 15:30
Room: S236 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.
Tuesday, 20 August 2024

09:00 Coffee
Coffee
09:00 - 09:45
Room: S236
09:45 Tropical Ideals - Felipe Rincon
Tropical Ideals
- Felipe Rincon
09:45 - 10:10
Room: S236 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.
10:10 Amalgams of matroids, fibre products and tropical graph correspondences - Dmitry Mineev (Bar-Ilan University, Ramat Gan, Israel)
Amalgams of matroids, fibre products and tropical graph correspondences
- Dmitry Mineev (Bar-Ilan University, Ramat Gan, Israel)
10:10 - 10:35
Room: S236 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.
10:35 Coffee
Coffee
10:35 - 10:55
Room: S236
10:55 Speyer's g conjecture via external activity of a pair of matroids - Alex Fink (Queen Mary University of London)
Speyer's g conjecture via external activity of a pair of matroids
- Alex Fink (Queen Mary University of London)
10:55 - 11:20
Room: S236 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.
11:20 Symmetric tropical rank 2 matrices - Kisun Lee (Clemson University)
Symmetric tropical rank 2 matrices
- Kisun Lee (Clemson University)
11:20 - 11:45
Room: S236 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.
11:45 Coffee
Coffee
11:45 - 12:05
Room: S236
12:05 Baker-Bowler theory for Lagrangian Grassmannians - Donggyu Kim (KAIST)
Baker-Bowler theory for Lagrangian Grassmannians
- Donggyu Kim (KAIST)
12:05 - 12:30
Room: S236 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+{n\choose 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.
12:30 Lunch
Lunch
12:30 - 13:30
Room: IBS Research Building
13:30 Direct sum of q-matroids and linear sets - Gianira Alfarano (University College Dublin)
Direct sum of q-matroids and linear sets
- Gianira Alfarano (University College Dublin)
13:30 - 13:55
Room: S236 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.
13:55 Almost all $q$-matroids are not representable - Sebastian Degen (Bielefeld University)
Almost all $q$-matroids are not representable
- Sebastian Degen (Bielefeld University)
13:55 - 14:20
Room: S236 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.
14:20 Coffee
Coffee
14:20 - 14:40
Room: S236
14:40 On a $q$-analogue of perfect matroid designs - Shinya Kawabuchi (Kumamoto University)
On a $q$-analogue of perfect matroid designs
- Shinya Kawabuchi (Kumamoto University)
14:40 - 15:05
Room: S236 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.
15:05 The cyclic flats of L-polymatroids - Andrew Fulcher (University College Dublin)
The cyclic flats of L-polymatroids
- Andrew Fulcher (University College Dublin)
15:05 - 15:30
Room: S236 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.
Wednesday, 21 August 2024

09:00 Coffee
Coffee
09:00 - 09:45
Room: S236
09:45 Graphs embedded on surfaces and their delta-matroids - Carolyn Chun (University of Maryland)
Graphs embedded on surfaces and their delta-matroids
- Carolyn Chun (University of Maryland)
09:45 - 10:10
Room: S236 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.
10:10 Graphs in surfaces, their one-face subgraphs, and the critical group - Iain Moffatt (Royal Holloway University of London)
Graphs in surfaces, their one-face subgraphs, and the critical group
- Iain Moffatt (Royal Holloway University of London)
10:10 - 10:35
Room: S236 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.
10:35 Coffee
Coffee
10:35 - 10:55
Room: S236
10:55 Clique minors in dense matroids - Fernanda Rivera Omaña (University of Waterloo)
Clique minors in dense matroids
- Fernanda Rivera Omaña (University of Waterloo)
10:55 - 11:20
Room: S236 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.
11:20 Chordal matroids arising from generalized parallel connections - Dylan Douthitt (Louisiana State University)
Chordal matroids arising from generalized parallel connections
- Dylan Douthitt (Louisiana State University)
11:20 - 11:45
Room: S236 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.
11:45 Coffee
Coffee
11:45 - 12:05
Room: S236
12:05 Connectivity systems, path-width, and well-quasi-ordering - Jim Geelen (University of Waterloo)
Connectivity systems, path-width, and well-quasi-ordering
- Jim Geelen (University of Waterloo)
12:05 - 12:30
Room: S236 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.
12:30 Lunch
Lunch
12:30 - 13:30
Room: IBS Research Building
13:30 Average Hyperplane-Size in Complex-Representable Matroids - Matthew Kroeker (University of Waterloo)
Average Hyperplane-Size in Complex-Representable Matroids
- Matthew Kroeker (University of Waterloo)
13:30 - 13:55
Room: S236 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.
13:55 Convex geometry of building sets - Rick Danner (University of Vermont)
Convex geometry of building sets
- Rick Danner (University of Vermont)
13:55 - 14:20
Room: S236 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.
14:20 Coffee
Coffee
14:20 - 14:40
Room: S236
14:40 Combinatorics of boundary algebras. - Jonathan Boretsky (MPI Leipzig)
Combinatorics of boundary algebras.
- Jonathan Boretsky (MPI Leipzig)
14:40 - 15:05
Room: S236 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.
Thursday, 22 August 2024

09:00 Coffee
Coffee
09:00 - 09:45
Room: S236
09:45 Complexity of log-concave inequalities in matroids - Swee Hong Chan (Rutgers University)
Complexity of log-concave inequalities in matroids
- Swee Hong Chan (Rutgers University)
09:45 - 10:10
Room: S236 A sequence of nonnegative real numbers $a_1, a_2, \ldots, a_n$, is log-concave if $a_i^2 \geq 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 = {n\choose 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.
10:10 Chow rings and augmented Chow rings of matroids are equivariant γ-positive - Hsin-Chieh Liao (University of Miami)
Chow rings and augmented Chow rings of matroids are equivariant γ-positive
- Hsin-Chieh Liao (University of Miami)
10:10 - 10:35
Room: S236 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.
10:35 Coffee
Coffee
10:35 - 10:55
Room: S236
10:55 Representations on the cohomology of the moduli space of pointed rational curves, permutation representations and log concavity - Donggun Lee (Institute for Basic Science)
Representations on the cohomology of the moduli space of pointed rational curves, permutation representations and log concavity
- Donggun Lee (Institute for Basic Science)
10:55 - 11:20
Room: S236 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.
11:20 Intrinsic properties of the gamma vector and matroids - Soohyun Park (Hebrew University of Jerusalem)
Intrinsic properties of the gamma vector and matroids
- Soohyun Park (Hebrew University of Jerusalem)
11:20 - 11:45
Room: S236 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.
11:45 Coffee
Coffee
11:45 - 12:05
Room: S236
12:05 Lawrence polytopes and some invariants of a graph - Changxin Ding
Lawrence polytopes and some invariants of a graph
- Changxin Ding
12:05 - 12:30
Room: S236 We use two dual Lawrence polytopes $P$ and $P^*$ 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^*$-vector of the Lawrence polytope $P$ (resp. $P^*$). 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^*$-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.
12:30 Lunch
Lunch
12:30 - 13:30
Room: IBS Research Building
13:30 Matroids and binary functions - Graham Farr (Monash University)
Matroids and binary functions
- Graham Farr (Monash University)
13:30 - 13:55
Room: S236 A *binary function* is a function $f:2^E\rightarrow\mathbb{C}$ for which $f(\emptyset)=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 $\hbox{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.
13:55 Tutte polynomials and split matroids - Benjamin Schröter (KTH Royal Institute of Technology)
Tutte polynomials and split matroids
- Benjamin Schröter (KTH Royal Institute of Technology)
13:55 - 14:20
Room: S236 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.
14:20 Coffee
Coffee
14:20 - 14:40
Room: S236
14:40 Bounds on the number of cells of the Dressian - Rudi Pendavingh (Eindhoven Technical University)
Bounds on the number of cells of the Dressian
- Rudi Pendavingh (Eindhoven Technical University)
14:40 - 15:05
Room: S236 A *valuation* of a matroid $M$ with set of bases $\mathcal{B}$ is a function $\nu:\mathcal{B}\rightarrow\mathbb{R}$ so that - **(V)** for all $B, B'\in \mathcal{B}$ and all $e\in B\setminus B'$ there exists an $f\in B'\setminus B$ such that $ \nu(B)+\nu(B')\geq \nu(B-e+f)+\nu(B'+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 $\#\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\geq t\geq 3$ , then $\qquad\qquad\qquad\qquad\frac{\dim \mathcal{D}(M)}{{n\choose r}}\leq \frac{\max\{\dim\mathcal{D}(M/S), ~S\in {E\choose r-t}\text{ independent}\}}{{n-r+t\choose t}}\leq \frac{3}{n-r+3}$ and $\qquad\qquad\qquad\frac{\log_2 \#\mathcal{D}(M)}{{n\choose r}}\leq \frac{\max\{\log_2 \#\mathcal{D}(M/S): ~S\in {E\choose r-t}\text{ independent }\}}{{n-r+t\choose t}}O(\ln(n))\leq \frac{O\left(\ln(n)^2\right)}{n}.$ For uniform matroids $M=U(r,n)$ these upper bounds may be compared to the lower bounds $\qquad\qquad\qquad\qquad\qquad\qquad\frac{1}{n}\leq \frac{\dim \mathcal{D}(M)}{{n\choose r}},\qquad \frac{1}{n}\leq \frac{\log_2 \#\mathcal{D}(M)}{{n\choose 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.
15:05 Filtrations of tope spaces of oriented matroids - Chi Ho Yuen
Filtrations of tope spaces of oriented matroids
- Chi Ho Yuen
15:05 - 15:30
Room: S236 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.
18:00 Banquet
Banquet
18:00 - 21:00
Room: S236
Friday, 23 August 2024

09:00 Coffee
Coffee
09:00 - 09:45
Room: S236
09:45 Contracting a Single Element in a Transversal Matroid - Sam Bastida (Victoria University of Wellington)
Contracting a Single Element in a Transversal Matroid
- Sam Bastida (Victoria University of Wellington)
09:45 - 10:10
Room: S236 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 $\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.
10:10 Cyclic matroids - Charles Semple
Cyclic matroids
- Charles Semple
10:10 - 10:35
Room: S236 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.
10:35 Coffee
Coffee
10:35 - 10:55
Room: S236
10:55 Frame matroids with a distinguished frame element - James Davies (Cambridge)
Frame matroids with a distinguished frame element
- James Davies (Cambridge)
10:55 - 11:20
Room: S236 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.
11:20 Piecing together quasi-graphic matroids from graphic pieces - Nathan Bowler (University of Hamburg)
Piecing together quasi-graphic matroids from graphic pieces
- Nathan Bowler (University of Hamburg)
11:20 - 11:45
Room: S236 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.
11:45 Coffee
Coffee
11:45 - 12:05
Room: S236
12:05 Matroids of Symmetric Rigid Frameworks - Katie Clinch (UNSW Sydney)
Matroids of Symmetric Rigid Frameworks
- Katie Clinch (UNSW Sydney)
12:05 - 12:30
Room: S236 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.
12:30 Lunch
Lunch
12:30 - 13:30
Room: IBS Research Building
13:30 A coarse Erdős-Pósa theorem - O-joung Kwon (Hanyang university)
A coarse Erdős-Pósa theorem
- O-joung Kwon (Hanyang university)
13:30 - 13:55
Room: S236 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|\leq 12(d+1)$ and $|X_2|\leq12$ 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.
13:55 Erdős-Pósa property of tripods in directed graphs - Meike Hatzel
Erdős-Pósa property of tripods in directed graphs
- Meike Hatzel
13:55 - 14:20
Room: S236 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\colon \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.
14:20 Coffee
Coffee
14:20 - 14:40
Room: S236
14:40 Reconfiguration of Basis Pairs in Regular Matroids - Tamás Schwarcz (ELTE Eötvös Loránd University)
Reconfiguration of Basis Pairs in Regular Matroids
- Tamás Schwarcz (ELTE Eötvös Loránd University)
14:40 - 15:05
Room: S236 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.
15:05 Discussion
Discussion
15:05 - 18:00
Room: S236