Do you want to publish a course? Click here

Matroids with a cyclic arrangement of circuits and cocircuits

56   0   0.0 ( 0 )
 Added by Nick Brettell
 Publication date 2018
  fields
and research's language is English




Ask ChatGPT about the research

For all positive integers $t$ exceeding one, a matroid has the cyclic $(t-1,t)$-property if its ground set has a cyclic ordering $sigma$ such that every set of $t-1$ consecutive elements in $sigma$ is contained in a $t$-element circuit and $t$-element cocircuit. We show that if $M$ has the cyclic $(t-1,t)$-property and $|E(M)|$ is sufficiently large, then these $t$-element circuits and $t$-element cocircuits are arranged in a prescribed way in $sigma$, which, for odd $t$, is analogous to how 3-element circuits and cocircuits appear in wheels and whirls, and, for even $t$, is analogous to how 4-element circuits and cocircuits appear in swirls. Furthermore, we show that any appropriate concatenation $Phi$ of $sigma$ is a flower. If $t$ is odd, then $Phi$ is a daisy, but if $t$ is even, then, depending on $M$, it is possible for $Phi$ to be either an anemone or a daisy.

rate research

Read More

100 - Georg Loho , Raman Sanyal 2019
Baranys colorful generalization of Caratheodorys Theorem combines geometrical and combinatorial constraints. Kalai-Meshulam (2005) and Holmsen (2016) generalized Baranys theorem by replacing color classes with matroid constraints. In this note, we obtain corresponding results in tropical convexity, generalizing the tropical colorful Caratheodory Theorem of Gaubert-Meunier (2010). Our proof is inspired by geometric arguments and is reminiscent of matroid intersection. In particular, we show that the topological approach fails in this setting. We also discuss tropical colorful linear programming and show that it is NP-complete. We end with thoughts and questions on generalizations to polymatroids, anti-matroids as well as examples and matroid simplicial depth.
We prove that the problem of counting the number of colourings of the vertices of a graph with at most two colours, such that the colour classes induce connected subgraphs is #P-complete. We also show that the closely related problem of counting the number of cocircuits of a graph is #P-complete.
131 - Jaeho Shin 2019
There is a trinity relationship between hyperplane arrangements, matroids and convex polytopes. We expand it as resolving the complexity issue expected by Mnevs universality theorem and conduct combinatorializing so the theory over fields becomes realization of our combinatorial theory. A main theorem is that for n less than or equal to 9 a specific and general enough kind of matroid tilings in the hypersimplex Delta(3,n) extend to matroid subdivisions of Delta(3,n) with the bound n=9 sharp. As a straightforward application to realizable cases, we solve an open problem in algebraic geometry proposed in 2008.
Cycle polytopes of matroids have been introduced in combinatorial optimization as a generalization of important classes of polyhedral objects like cut polytopes and Eulerian subgraph polytopes associated to graphs. Here we start an algebraic and geometric investigation of these polytopes by studying their toric algebras, called cycle algebras, and their defining ideals. Several matroid operations are considered which determine faces of cycle polytopes that belong again to this class of polyhedral objects. As a key technique used in this paper, we study certain minors of given matroids which yield algebra retracts on the level of cycle algebras. In particular, that allows us to use a powerful algebraic machinery. As an application, we study highest possible degrees in minimal homogeneous systems of generators of defining ideals of cycle algebras as well as interesting cases of cut polytopes and Eulerian subgraph polytopes.
134 - Duksang Lee , Sang-il Oum 2020
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.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا