Generalized laminar matroids

DOI10.1016/J.EJC.2018.12.005MaRDI QIDQ2422233zbMATH OpenOpenAlexWikidataFDO

Authors Tara Fife, James Oxley

Publication date 18 June 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.06882

zbMATH Keywords

Nested matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: Nested matroids were introduced by Crapo in 1965 and have appeared frequently in the literature since then. A flat of a matroid $M$ is Hamiltonian if it has a spanning circuit. A matroid $M$ is nested if and only if its Hamiltonian flats form a chain under inclusion; $M$ is laminar if and only if, for every $1$-element independent set $X$, the Hamiltonian flats of $M$ containing $X$ form a chain under inclusion. We generalize these notions to define the classes of $k$-closure-laminar and $k$-laminar matroids. This paper focuses on structural properties of these classes noting that, while the second class is always minor-closed, the first is if and only if $kle3$. The main results are excluded-minor characterizations for the classes of 2-laminar and 2-closure-laminar matroids.

Recommendations

• Laminar matroids
• Lattice path matroids: structural properties
• On the matroids in which all hyperplanes are binary
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids
• scientific article; zbMATH DE number 1028231

Cites work

• A free subalgebra of the algebra of matroids
• A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Advances on matroid secretary problems: free order model and laminar case
• Gammoids and transversal matroids
• scientific article; zbMATH DE number 3762079 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Improved competitive ratio for the matroid secretary problem
• Laminar matroids
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Matroid secretary problem in the random-assignment model
• Matroids, secretary problems, and online mechanisms
• On the Vector Representation of Matroids
• Rapid mixing of some linear matroids and other combinatorial objects
• Secretary problems: laminar matroid and interval scheduling
• Single-element extensions of matroids
• The Catalan matroid
• The lattice of cyclic flats of a matroid

Cited in

(5)

• A matroid generalization of a result on row-Latin rectangles
• scientific article; zbMATH DE number 3997861 (Why is no real title available?)
• Laminar matroids
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids
• Generalized laminar families and certain forbidden matrices

This page was built for publication: Generalized laminar matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2422233)