 |
|
|
|
|
|
| Monday 24 | ||
|---|---|---|
| 9h | James OXLEY (Louisiana State University, USA) | |
| A matroid extension result | ||
| Let $(A,B)$ be a $3$-separation in a matroid $M$. If $M$ is representable, then, in the underlying projective space, there is a line where the subspaces spanned by $A$ and $B$ meet, and $M$ can be extended by adding elements from this line. In general, Geelen, Gerards, and Whittle proved that $M$ can be extended by an independent set $\{p,q\}$ such that $\{p,q\}$ is in the closure of each of $A$ and $B$. In this extension, each of $p$ and $q$ is freely placed on the line $L$ spanned by $\{p,q\}$. This talk will discuss a result that gives necessary and sufficient conditions under which a fixed element can be placed on $L$. | ||
| 9h25 | Csongor CSEHI (Budapest University of Technology and Economics, Hungary) | |
| Sufficient condition for almost irreducibility | ||
| A matroid $N$ is almost irreducible if for any decomposition to matroid union $M_1\vee M_2 = N$, $N$ is a series extension of a submatroid of one of the matroids $M_i \in \{M_1,M_2\}$. András Recski have given an equivalent characterization of almost irreducible graphic matroids. We give a sufficient condition of almost irreducibility for arbitrary matroids, using the lemmata of Recski's proof. We show that these results can be applied to some important matroids. As a consequence we are getting closer to the conjecture that the union of graphic matroids is graphic or nonbinary. | ||
| 9h50 | Rutger CAMPBELL (University of Waterloo, Canada) | |
| Representable orientable matroids that are not real-representable | ||
| For each odd prime power q>3, we construct a GF(q)-representable oriented matroid that is not real-representable. | ||
| 10h15 | Anna DE MIER (Universitat Politècnica de Catalunya, Spain) | |
| Approximating clutters with matroids | ||
| There are several clutters (antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. We study the following question: given an arbitrary clutter $\Lambda$, which are the matroidal clutters that are closest to $\Lambda$? To answer it we first decide on the meaning of closest, and select one of the different matroidal clutters. We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate $\Lambda$ and, moreover, that $\Lambda$ can be recovered from them by a suitable operation. We also link our work to results in lattice theory, and give algorithmic procedures to compute the approximations. We are also interested in the same questions when we further require that both the original clutter and the matroidal approximations have the same ground set. In this situation, it is often the case that $\Lambda$ cannot be recovered by the approximating matroidal clutters (if they exist), but we can characterize when it does. Although our initial interest was in matroids, our framework is general and applies in any situation when one wishes to decompose the clutter $\Lambda$ with members of a favourite family of clutters, not necessarily a matroidal one. | ||
| (Joint work with Jaume Martí-Farré and José Luis Ruiz. ) | ||
| 11h05 | Jim LAWRENCE (George Mason University, USA) | |
| The concatenation operation for uniform oriented matroids and simplicial (or simple) polytopes | ||
Some problems connected with the concatenation operation will be described. | ||
| 11h30 | Jesus DE LOERA (University of California, Davis, USA) | |
| Tverberg-type theorems with altered (nerves) intersection patterns. | ||
| Abstract: The classical Tverberg's theorem says that a set with sufficiently many points in $R^d$ can always be partitioned into m parts so that the (m - 1)-simplex is the (nerve) intersection pattern of the convex hulls of the parts. Our main results demonstrate that Tverberg's theorem is but a special case of a much more general situation. Given sufficiently many points, any tree or cycle, can also be induced by at least one partition of the point set. The proofs require a deep investigation of oriented matroids and order types. | ||
| (Joint work with Deborah Oliveros, Tommy Hogan, Dominic Yang (supported by NSF).) | ||
| 11h55 | Jürgen BOKOWSKI (Technische Universität Darmstadt, Germany) | |
| From a combinatorial input to a polyhedral realization, Hurwitz's regular map of genus 7 | ||
| Regular maps describe combinatorially 2-manifolds with a flag-transitive automorphism group. They are in this sense a generalization of the Platonic solids. For an old example of Hurwitz from 1893 the talk presents a polyhedral realization without self-intersections that was found recently in joint work with Michael Cuntz. The remaining question of whether such a realization can be found with some geometric symmetry (joint work with Gábor Gévay) will be discussed. This talk is related to a problem of "Computational Synthetic Geometry", see LNM 1355, J. Bokowski & B. Sturmfels. | ||
| (Joint work with Michael Cuntz, Hannover and Gábor Gévay, Szeged.) | ||
| 14h30 | Galen DORPALEN-BARRY (University of Minnesota, USA) | |
| Characteristic polynomials and chambers for cones in hyperplane arrangements | ||
| Zaslavsky's theorem counts the chambers of an affine or central hyperplane arrangement using the characteristic polynomial of its intersection semilattice. We examine a generalization that counts chambers within a cone of the arrangement using the semilattice of interior intersections. Particularly interesting is the case of the type A braid arrangement, where these chambers correspond to linear extensions of posets. For certain posets, this connects closely with Foata's theory of permutations of a multiset. | ||
| (Joint work with Victor Reiner.) | ||
| 14h55 | Anastasia CHAVEZ (University of California, Davis, USA) | |
| Dyck Paths and Positroids from Unit Interval Orders | ||
| It is well known that the number of non-isomorphic unit interval orders on $[n]$ equals the $n$-th Catalan number. Using work of Skandera and Reed and work of Postnikov, we show that each unit interval order on $[n]$ naturally induces a rank $n$ positroid on $[2n]$. We call the positroids produced in this fashion \emph{unit interval positroids}. We characterize the unit interval positroids by describing their associated decorated permutations, showing that each one must be a $2n$-cycle encoding a Dyck path of length $2n$. We also give a combinatorial description of the $f$-vectors of unit interval orders. | ||
| (This is joint work with Felix Gotti.) | ||
| 15h20 | Zur IZHAKIAN (University of Aberdeen, UK) | |
| Supertropical algebra and representations | ||
| Tropical mathematics is carried out over idempotent semirings, a weak algebraic structure that on one hand allows descriptions of objects having a discrete nature, but on the other hand, its lack of additive inverse prevents the access to basic mathematical notions. This drawback is overcome by using supertropical semirings whose structure is rich enough to permit a systematic development of algebraic theory, including analogues to many classical results and notions. Supertropical algebra provides a suitable algebraic framework that enables natural realizations of matroids and simplicial complexes, as well as representations of semigroups. | ||
| 16h05 | Marcel CELAYA (Georgia Tech, USA) | |
| Polyhedral representations of oriented matroids | ||
| What is the right analogue of a tropical linear space in the context of oriented matroids? In this talk I will discuss this question and how it relates to the Folkman-Lawrence Topological Representation Theorem and the Bohne-Dress Theorem. Along the way, I will describe a chirotope-based proof of the Bohne-Dress theorem, generalize McMullen's formula to non-convex zonotopes, and give a combinatorial characterization of the faces (in all dimensions) of the matroid polytope. | ||
| 16h30 | Ilda DA SILVA (Universidade de Lisboa, Portugal) | |
| How many cubes are orientable? | ||
| A cube is a matroid over $C^n=\{-1,+1\}^n$ that contains as circuits the usual rectangles of the real affine cube packed in such a way that the usual facets and skew-facets are hyperplanes of the matroid. How many cubes are orientable? So far, only one: the oriented real affine cube. We review the results obtained so far concerning this question. They follow two directions: 1) Identification of general obstructions to orientability in this class. (da Silva, EJC 30 (8), 2009, 1825-1832). 2) (work in collaboration with E. Gioan) Identification of algebraic and geometric properties of recursive families of non-negative integer vectors defining hyperplanes of the real affine cube and the analysis of this question and of las Vergnas cube conjecture in small dimensions. | ||
| Tuesday 25 | ||
| 9h | Nathan BOWLER (Universität Hamburg, Germany) | |
| Representing matroids over hyperfields | ||
| I'll explain how to simultaneously generalise the notions of linear subspaces, matroids, valuated matroids, and oriented matroids, as well as phased matroids in the sense of Anderson-Delucchi. All of these can be thought of as matroids represented in a certain sense over hyperfields. In fact, there are (at least) two natural notions of represented matroid in this context, and I will discuss both. I'll give “cryptomorphic” axiom systems for such matroids in terms of circuits, Grassmann-Plücker functions, and dual pairs, and explain some basic duality theorems. I'll also outline an argument that if the hyperfield F is doubly distributive then the two different notions of representation over F coincide. | ||
| (Joint work with Matt Baker) | ||
| 9h45 | Laura ANDERSON (Binghamton University, SUNY, USA) | |
| Vectors of matroids over hyperfields | ||
| This talk will expand on Nathan Bowler's talk on matroids over hyperfields. I will describe vector axioms for matroids over hyperfields. These axioms give a particularly direct way to see matroids over hyperfields as generalizing subspaces of a vector space $F^n$. In the case of oriented matroids, we get new signed vector axioms, equivalent to the usual ones but quite different (and arguably better!) both in appearance and in spirit. For general hyperfields, there are a number of unexpected surprises, and there are many open questions. | ||
| 10h10 | Rudi PENDAVINGH (Technische Universiteit Eindhoven, Netherlands) | |
| Matroids over skew hyperfields | ||
| Matroids over hyperfields are a common abstraction of oriented matroids and valuated matroids. We show how to generalize the theory of matroids over hyperfields (Baker and Bowler) to matroids over skew hyperfields, and we describe a matroid over a skew hyperfield which arises from an algebraic representation of a matroid. | ||
| 11h05 | James DAVIS (Indiana University, USA) | |
| Hyperfield Grassmannians | ||
| The Grassmannian of k-planes in $R^n$ is a classical object, useful in topology, geometry, and combinatorics. A hyperfield is a generalization of a field, with multivalued addition. Baker and Bowler have introduced the notion of a matroid over a hyperfield. Examples include the Krasner hyperfield, whose matroids are ordinary matroids, the Sign hyperfield, whose matroids are oriented matroids, and Viro's tropical real hyperfield, which can be used in tropical geometry and is a dequantization of the real number field. The hyperfield Grassmannian $Gr(k, F^n)$ is the set of all rank k matroids on n elements over a hyperfield F. Laura Anderson and I define the notion of a topological hyperfield and hence give the hyperfield Grassmannian a topology. This talk will give many examples of topological hyperfields, continuous maps between them, and discuss the basic topological, categorical, and combinatorial properties of hyperfield Grassmannians, as well as their connection with realization spaces. | ||
| (Joint work with Laura Anderson) | ||
| 11h50 | Emanuele DELUCCHI (University of Fribourg, Switzerland) | |
| Realization spaces of matroids over hyperfields | ||
| We study realization spaces of matroids over hyperfields. More precisely, given a matroid M and a hyperfield H we determine the space of all H-matroids over M. This can be seen as the matroid stratum of the hyperfield Grassmannians in the sense of Anderson-Davis. For an algebraically determined class of hyperfields we give different descriptions of these realization spaces (e.g., in terms of Tutte groups or cross-ratios), allowing for explicit computations. When the hyperfield at hand is topological, the realization spaces have a natural topology. In this case, our models carry the corret homeomorphism type. As applications of our methods we obtain a theorem on the existence of phased matroids that are not realizable over the complex numbers, as well as a result on the diffeomorphism type of complex hyperplane arrangements whose underlying matroid is uniform. | ||
| (Joint work with E. Saini and L. Hoessly. Supported by SNSF grant PP00P2-150552/1) | ||
| 14h30 | Victor CHEPOI (Université de la Méditerranée, Aix-Marseille II, France) | |
| COMs: Complexes of Oriented Matroids | ||
| In this talk we will give a blackboard introduction to Complexes of Oriented Matroids (abbreviated, COMs). COMs represent a common generalization of Oriented Matroids (OMs) and lopsided sets. These novel structures can be characterized in terms of three covectors axioms, generalizing the familiar characterization for oriented matroids (COMs can be also characterized via their cocircuits). We will describe a binary composition scheme by which every COM can successively be erected as a contractible cell complex whose cells are oriented matroids, in essentially the same way as a lopsided set can be glued together from its maximal hypercube faces. For this, we will define halfspaces, hyperplanes, and carriers of COMs, which arise in the theory of CAT(0) cube complexes, and which turn out to be also COMs. We will present two examples of COMs: realizable COMs and COMs arising from CAT(0) Coxeter zonotopal complexes. Realizable COMs are represented by hyperplane arrangements restricted to open convex sets. Relaxing realizability to local realizability, we capture a wider class of combinatorial objects: CAT(0) Coxeter zonotopal complexes give rise to locally realizable COMs. The talk is based on the paper H.-J. Bandelt, V. Chepoi, K. Knauer, COMs: complexes of oriented matroids, J. Combin. Theory Ser. A, 156 (2018), 195–237. | ||
| (Joint work with H.-J. Bandelt and K. Knauer. Supported in part by the ANR project TEOMATRO (ANR-10-BLAN-0207).) | ||
| 15h15 | Kolja KNAUER (Université Aix-Marseille, France) | |
| Tope graphs of Complexes of Oriented Matroids | ||
| We give two graph theoretical characterizations of tope graphs of (complexes of) oriented matroids. The first is in terms of excluded partial cube minors, the second is that all antipodal subgraphs are gated. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we obtain purely graph theoretic polynomial time recognition algorithms for tope graphs. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory. | ||
| (Based on joint work with Tilen Marc) | ||
| 16h | Arnau PADROL (Sorbonne Université, Paris, France) | |
| Back and forth with Gale duality | ||
| Gale duality is a correspondence that relates linear/affine properties of a vector/point configuration with those of its dual configuration. Through it, several results in discrete geometry have a double interpretation. I will review some classical theorems through this double glass. Although not widely known, several point-selection theorems also have such double interpretations, through the closely related theory of type cones. Some colorful theorems also have interpretations in terms of Minkowski sums, when looked from the point of view of Gale transforms of Cayley polytopes. | ||
| 16h25 | Michael FALK (Northern Arizona University, USA) | |
| Pairs of topes | ||
| The set of pairs of topes of an oriented matroid forms a poset that is homotopy equivalent to the Salvetti poset: their realizations are homotopy equivalent by an order-preserving map with cone fibers. The partial ordering can be interpreted via a notion of "oriented convexity" that may be of interest to (anti-)matroid theorists. | ||
| (Joint work with Emanuele Delucchi) | ||
| Wednesday 26 | ||
| 9h | Goran MALIC (Zagreb School of Economics And Management, Croatia) | |
| Delta-matroids of dessins d'enfants and an action of the absolute Galois group Gal(Q) | ||
| NB. The notation Gal(Q) stands for $Gal(\overline{\mathbb Q}/{\mathbb Q})$. This talk will be an overview of the research carried out in my PhD thesis, supervised by Prof Alexandre Borovik. A dessin d'enfant is a cellular embedding of a connected graph on a closed, connected and orientable surface X. Remarkably, such an embedding induces on X the structure of an algebraic curve defined over the algebraic numbers; therefore there is a natural action of Gal(Q) on the set of dessins d'enfants. A dessin d'enfant also defines a Lagrangian matroid (also known as a delta-matroid) on X and the action of Gal(Q) on a dessin d'enfant changes the matroid by changing the curve. The main goal of my PhD thesis was to make sense of how Gal(Q) interacts with the Lagrangian matroid of a dessin d'enfant, which proved to be very difficult, for the reasons that will be explained in the talk. If time permits, I will also say something about my ongoing research, joint with Prof Sibylle Schroll, on Brauer Graph Algebras associated to dessins d'enfants and the role of matroids in the representation theory of Brauer Graph Algebras. | ||
| 9h45 | Joseph BONIN (The George Washington University, Washington, USA) | |
| Delta-matroids as subsystems of sequences of Higgs lifts | ||
| Delta-matroids generalize matroids. In a delta-matroid, the counterparts of bases, which are called feasible sets, can have different sizes, but they satisfy a similar exchange property in which symmetric differences replace set differences. One way to get a delta-matroid is to take a matroid L, a quotient Q of L, and all of the Higgs lifts of Q toward L; the union of the sets of bases of these Higgs lifts is the collection of feasible sets of a delta-matroid, which we call a full Higgs lift delta-matroid. We give an excluded-minor characterization of full Higgs lift delta-matroids within the class of all delta-matroids. We introduce a class of full Higgs lift delta-matroids that arise from lattice paths and that generalize lattice path matroids. It follows from results of Bouchet that all delta-matroids can be obtained from full Higgs lift delta-matroids by removing certain feasible sets; to address which feasible sets can be removed, we give an excluded-minor characterization of delta-matroids within the more general structure of set systems. This result in turn yields excluded-minor characterizations of a number of related classes of delta-matroids. | ||
| (This is joint work with Carolyn Chun and Steve Noble.) | ||
| 10h10 | Steven NOBLE (Birkbeck University of London, UK) | |
| Excluded-minor results for vf-safe delta-matroids | ||
| Vf-safe delta-matroids are those which remain delta-matroids under a certain duality operation, namely twisted duality, that significantly extends duality in matroids. The class of vf-safe delta-matroids includes the classes of delta-matroids coming from binary matrices and from ribbon graphs. Determining the excluded minors for vf-safe delta-matroids seems to be difficult. We characterize vf-safe matroids using excluded minors. Vf-safe delta-matroids have three natural minor operations and we show that up to twisted duality there is only one excluded minor for the class of vf-safe delta-matroids within set systems under these three minor operations. | ||
| (Joint work with Joe Bonin, Carolyn Chun, Irene Pivotto and Gordon Royle) | ||
| 11h05 | Spencer BACKMAN (Hebrew University of Jerusalem, Israel) | |
| Geometric Bijections for Regular Matroids, Zonotopes, and Ehrhart Theory | ||
| Chip-firing is a simple game on graphs which arises in many different mathematical contexts. There is a group naturally associated to chip-firing which has cardinality equal to the number of spanning trees of a graph, and there exist many different bijections in the literature between these sets. Merino introduced a generalization of chip-firing for regular matroids which retains this enumerative correspondence. I will describe a family of bijections between the elements of the chip-firing group of a regular matroid and its bases via orientations. The proof of bijectivity makes use of the geometry of zonotopes and admits an Ehrhart theoretic interpretation. | ||
| (Joint work with Matt Baker and Chi Ho Yuen) | ||
| 11h30 | Chi Ho YUEN (Georgia Tech, USA) | |
| More on Geometric Bijections and Circuit-cocircuit Reversal Systems | ||
| This is the follow up of Spencer Backman's talk. I will describe a group action-tiling duality for regular matroids, and explain how it relates several seemingly unrelated results. I will also discuss geometric bijections and circuit-cocircuit reversal systems of general oriented matroids; in particular, I will prove the converse of Gioan's result: there are fewer reversal classes than bases whenever the underlying matroid is not regular. | ||
| (The talk includes joint works with Spencer Backman and Francisco Santos, and with Emeric Gioan.) | ||
| 11h55 | Raman SANYAL (Institut für Mathematik Goethe-Universität Frankfurt, Germany) | |
| Cone valuations, Gram's relation, and zonotopes | ||
| The Euler-Poincare formula is a cornerstone of the combinatorial theory of polytopes. It states that the number of faces of various dimensions of a convex polytope satisfy a linear relation and it is the only linear relation (up to scaling). Gram's relation generalizes the fact that the sum of (interior) angles at the vertices of a convex $n$-gon is $(n-2)\pi$. In dimensions $3$ and up, it is necessary to consider angles at all faces. This gives rise to the interior angle vector of a convex polytope and Gram's relation is the unique linear relation (up to scaling) among its entries. In this talk, we will consider generalizations of ``angles'' in the form of cone valuations. It turns out that the associated generalized angle vectors still satisfy Gram's relation and that it is the only linear relation, independent of the notion of ``angle''! To prove such a result, we rely on a very powerful connection to the combinatorics of zonotopes. The interior angle vector of a zonotope is independent of the chosen cone valuation and depends only on the associated lattice of flats. If time permits, we discuss flag-angles as a semi-discrete generalization of flag-vectors and their linear relations. | ||
| (Joint work with Spencer Backman, Sebastian Manecke) | ||
| Thurday 27 | ||
| 9h | Gary GORDON and Liz McMAHON (Lafayette College, USA) | |
| Generalizations of Crapo's Beta Invariant | ||
| Crapo's beta invariant was defined by Henry Crapo in the 1960s. For a matroid $M$, the invariant $\beta(M)$ is the non-negative integer that is the coefficient of the $x$ term of the Tutte polynomial. Crapo proved that $\beta(M)>0$ if and only if $M$ is connected and $M$ is not a loop, and Brylawski proved that $M$ is the matroid of a series-parallel network if and only if $M$ is a co-loop or $\beta(M)=1.$ In this talk, we present several generalizations of the beta invariant to combinatorial structures that are not matroids. We concentrate on posets, chordal graphs, and finite subsets of Euclidean space. In each case, our definition of $\beta$ measures the number of ``interior'' elements. | ||
| 9h45 | Alex FINK (Queen Mary University of London, UK) | |
| Some cryptomorphisms for valuated matroids and matroids over rings | ||
| I will present several new characterisations surrounding valuated matroids: (a) Submodular function axioms for valuated matroids (with Scott Kemp; work in progress). (b) A characterisation of transversal valuated matroids after Mason (with Jorge Alberto Olarte) (c) Polyhedron and Plücker-type axioms for matroids over a valuation ring (with Luca Moci). I will of course introduce matroids over a valuation ring first. | ||
| (Joint work with Luca Moci,Jorge Alberto Olarte, probably Scott Kemp, ) | ||
| 10h10 | Hiroshi HIRAI (University of Tokyo, Japan) | |
| Uniform semimodular lattice, valuated matroid, and Euclidean building | ||
| In this talk, we present a lattice-theoretic characterization for valuated matroids, which is an extension of the well-known cryptomorphic equivalence between matroids and geometric lattices (= atomistic semimodular lattices). We introduce a class of semimodular lattices, called uniform semimodular lattices, and establish a cryptomorphic equivalence between integer-valued valuated matroids and uniform semimodular lattices. Our result includes a coordinate-free lattice-theoretic characterization of integer points in tropical linear spaces, incorporates the Dress-Terhalle completion process of valuated matroids, and establishes a smooth connection with Euclidean buildings of type A. | ||
| (Supported by JSPS KAKENHI Grant Numbers JP17K00029.) | ||
| 11h05 | Iain MOFFATT (Royal Holloway University of London, UK) | |
| Tutte polynomials and bialgebras | ||
| The Tutte polynomial is one of the most important, and best studied, graph polynomials. It is important not only because it encodes a large amount of combinatorial information about a graph, but also because of its applications to areas such as statistical physics and knot theory. Because of its importance the Tutte polynomial has been extended to various classes of combinatorial object. For some objects there is more than one definition of a "Tutte polynomial", and for others is even unclear what a Tutte polynomial should look like. Taking as a starting point the deletion-contraction relations for the Tutte polynomial, I'll describe how the Tutte polynomial can be reformulated in a way that does not depend upon graph or matroid specific language. I'll go on to explain how this gives rise to a canonical construction of a ``Tutte polynomial'' for other types of combinatorial objects that incorporates various extensions of the Tutte polynomial from the literature. Finally, I'll explain how this elementary construction can be understood in terms of bialgebras. | ||
| (Includes some joint work with T. Krajewski, S. Huggett, B. Smith, and A. Tanasa) | ||
| 11h30 | Luca MOCI (Institut de Mathématiques de Jussieu, Paris, France) | |
| Graded bialgebras and deletion-contraction invariants | ||
| In this talk we expain how several meaningful invariants of combinatorial objects can be extracted from coalgebra or bialgebra structures. The Tutte polynomial is an invariant of graphs well known for the formula which computes it recursively by deleting and contracting edges, and for its universality with respect to similar recurrence. We generalize this to all classes of combinatorial objects with deletion and contraction operations, associating to each such class a universal Tutte character by a functorial procedure. We show that these invariants satisfy a universal property and convolution formulae similar to the Tutte polynomial. With this machinery we recover classical invariants for arithmetic matroids, knots, polymatroids, delta-matroids, matroid perspectives, relative and colored matroids. We also produce some new invariants along with new convolution formulae. | ||
| (Joint work with Clement Dupont and Alex Fink) | ||
| 14h30 | Federico ARDILA (San Francisco State University, USA) | |
| The geometry of geometries. | ||
| In recent years, the geometric roots of matroid theory have grown much deeper, bearing many new fruits. This talk will survey some recent successes. We will discuss three geometric models of matroids at the intersection of combinatorics, algebra, and geometry. Each has led to the development of intriguing combinatorics and to the solution of long-standing questions. | ||
| 15h35 | Karim ADIPRASITO (Hebrew University of Jerusalem, Israel) | |
| Combinatorial Hodge and Lefschetz theory | ||
| We will revisit combinatorial Hodge theory for matroids, which established that matroids satisfy deep algebraic principles with several important corollaries. Departing from there, we will construct intersection rings for other, related combinatorial objects, survey what algebraic principles can be proven for them, and discuss applications. I will focus in particular on cubical complexes and simplicial spheres. | ||
| 16h20 | Gaku LIU (Max-Planck-Institut für Mathematik, Germany) | |
| Cubical Pachner moves, generic immersions, and cobordisms | ||
| We study various analogues of theorems from PL topology for cubical complexes. In particular, we characterize when two PL homeomorphic cubulations are equivalent by Pachner moves by showing the question to be equivalent to the existence of cobordisms between generic immersions of hypersurfaces. This solves a question and conjecture of Habegger and Funar. The main tool is a theorem to show that any cubical PL decomposition of a disk is regular after some cubical stellar subdivision. This extends a result of Morelli, and answers a generalization of a question of Billera. | ||
| (Joint work with Karim Adiprasito) | ||
| Friday 28 | ||
| 9h | András RECSKI (Budapest University of Technology and Economics, Hungary) | |
| Generalized matroid matching -- a survey | ||
| Let M be a matroid on the underlying set E and suppose that E is the union of disjoint pairs. The matroid parity problem asks if a subset of E with given size exists which is independent in M and intersects each pair either by two or by no elements. This problem is a common generalization of the two-matroids-intersection problem and the graph matching problem, and has several engineering applications. The problem is non-polynomial in general but has a polynomial solution if M is represented over the field of the reals. Motivated by some engineering problems the following generalization is proposed: Let E be the union of disjoint k-element subsets. Let A be a non-empty subset of {0, 1, 2, ..., k}. Does there exist a subset of E with given size which is independent in M and its intersection with each k-element subset has cardinality belonging to A? Observe that this reduces to the original problem if k = 2 and A = {0, 2}. We survey the results in this area. | ||
| (Partly joint work with Jacint SZABO. ) | ||
| 9h45 | Kristóf BERCZI (Eötvös Loránd University, Hungary) | |
| Matroidal maximum term rank | ||
| Ryser's max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with matching number at least $\ell$. We present a generalization for the case when the degrees are constrained by upper and lower bounds. Then two other extensions are discussed: the first one is a matroidal model, while the second one settles the augmentation version. In fact, the two directions shall be integrated into one single framework. | ||
| (Joint work with András Frank.) | ||
| 10h40 | Csaba KIRALY (Eötvös Loránd University, Hungary) | |
| Packing arborescences with matroid constraints via matroid intersection | ||
| Katoh and Tanigawa characterized the rigidity of slider-pin frameworks. Their paper on the combinatorial details of this rigidity matroid initiated an intensive research in combinatorial optimization on packing arborescences with matroid constraints. Here a packing means edge-disjoint subgraphs. The first such result was due to Durand de Gevigney, Nguyen and Szigeti that gave an alternative proof for one of the main results of a paper by Katoh and Tanigawa through a matroid constrained arborescence packing result and an orientation result. This packing theorem generalized Edmonds' fundamental theorem on packing spanning arborescences. Later common generalizations of this matroid constrained packing result and other previous generalizations of Edmonds' theorem were discovered. It was also discovered by Edmonds that the original problem of packing spanning arborescences can be characterized through the matroid intersection theorem of Edmonds which also implies an efficient algorithm for the weighted case of the problem. In this talk, we show how a similar characterization can be given for the most recent results on arborescence packings. To define the matroid in the characterization, we also show how a new class of matroids can be defined by extending an earlier construction of matroids from intersecting submodular functions to bi-set functions based on an idea of Frank. | ||
| (Joint work with Zoltán Szigeti and Shin-ichi Tanigawa.) | ||
| 11h25 | Viktoria KASZANITZKY (Budapest University of Technology and Economics, Hungary) | |
| Highly connected rigidity matroids have unique underlying graphs | ||
| We consider the following problem: is there a (smallest) integer $k_d$ such that every graph $G$ is uniquely determined by its $d$-dimensional rigidity matroid, provided that this matroid is $k_d$-connected? Since the one-dimensional rigidity matroid of $G$ is isomorphic to the cycle matroid of $G$, a celebrated result of H. Whitney implies that $k_1=3$. We prove that if $G$ is 7-vertex-connected then it is uniquely determined by its two-dimensional rigidity matroid. We use this result to deduce that $k_2\leq 11$, which gives an affirmative answer for $d=2$. | ||
| (Joint work with Tibor Jordán.) | ||
| 11h50 | Lukas KUHNE (Hebrew University of Jerusalem, Israel) | |
| Parallel iterators and a database for integer root matroids. | ||
| This talk is concerned with the systematic generation of integer root matroids. These are matroids whose characteristic polynomial completely factors over the integers. Our study is motivated by questions of freeness of hyperplane arrangements in the area of Terao's conjecture. To parallely generate the more than 750.000 integer root matroids of rank 3 with up to 14 elements we have developed a general framework of parallelized iterators in HPC-GAP. Furthermore, we have saved these matroid in a soon publicly available ArangoDB database with additional stored properties such as representability, supersolvability etc. I will give a live demonstration of this database and present our enumerative results on these integer root matroids. | ||
| (Joint work with Mohamed Barakat, Reimer Behrends and Chris Jefferson) | ||
|
|
|
|
|
|