No Arabic abstract
We prove a common generalization of two results, one on rainbow fractional matchings and one on rainbow sets in the intersection of two matroids: Given $d = r lceil k rceil - r + 1$ functions of size (=sum of values) $k$ that are all independent in each of $r$ given matroids, there exists a rainbow set of $supp(f_i)$, $i leq d$, supporting a function with the same properties.
This is a survey paper on rainbow sets (another name for ``choice functions). The main theme is the distinction between two types of choice functions: those having a large (in the sense of belonging to some specified filter, namely closed up set of sets) image, and those that have a large domain and small image, where ``smallness means belonging to some specified complex (a closed-down set). The paper contains some new results: (1) theorems on scrambl
Let $M$ be a 3-connected matroid and let $mathbb F$ be a field. Let $A$ be a matrix over $mathbb F$ representing $M$ and let $(G,mathcal B)$ be a biased graph representing $M$. We characterize the relationship between $A$ and $(G,mathcal B)$, settling four conjectures of Zaslavsky. We show that for each matrix representation $A$ and each biased graph representation $(G,mathcal B)$ of $M$, $A$ is projectively equivalent to a canonical matrix representation arising from $G$ as a gain graph over $mathbb F^+$ or $mathbb F^times$. Further, we show that the projective equivalence classes of matrix representations of $M$ are in one-to-one correspondence with the switching equivalence classes of gain graphs arising from $(G,mathcal B)$.
We describe the structure of the monoid of natural-valued monotone functions on an arbitrary poset. For this monoid we provide a presentation, a characterization of prime elements, and a description of its convex hull. We also study the associated monoid ring, proving that it is normal, and thus Cohen-Macaulay. We determine its Cohen-Macaulay type, characterize the Gorenstein property, and provide a Grobner basis of the defining ideal. Then we apply these results to the monoid of quasi-arithmetic multiplicities on a uniform matroid. Finally we state some conjectures on the number of irreducibles for the monoid of multiplicities on an arbitrary matroid.
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
We construct minimal cellular resolutions of squarefree monomial ideals arising from hyperplane arrangements, matroids and oriented matroids. These are Stanley-Reisner ideals of complexes of independent sets, and of triangulations of Lawrence matroid polytopes. Our resolution provides a cellular realization of Stanleys formula for their Betti numbers. For unimodular matroids our resolutions are related to hyperplane arrangements on tori, and we recover the resolutions constructed by Bayer, Popescu and Sturmfels. We resolve the combinatorial problems posed in their paper by computing Mobius invariants of graphic and cographic arrangements in terms of Hermite polynomials.