Matroids, delta-matroids and embedded graphs
From MaRDI portal
Publication:2318477
Graph polynomials (05C31) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)
Abstract: Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the connections between embedded graphs and delta-matroids can be exploited. Also, in direct analogy with the fact that The Tutte polynomial is matroidal, we show that several polynomials of embedded graphs from the literature, including the Las Vergnas, Bollabas-Riordan and Krushkal polynomials, are in fact delta-matroidal.
Recommendations
Cites work
- A characterization of partially dual graphs
- A Decomposition for Combinatorial Geometries
- A note on the production of matroid minors
- A polynomial invariant of graphs on orientable surfaces
- A polynomial of graphs on surfaces
- A quasi-tree expansion of the Krushkal polynomial
- A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
- A spanning tree expansion of the Jones polynomial
- Alternating sum formulae for the determinant and other link invariants
- An Upper Bound on the Number of Edges of a 2-Connected Graph
- Binary matroids and local complementation
- Binary nullity, Euler circuits and interlace polynomials
- Circle graph obstructions
- Circle graph obstructions under pivoting
- Connectivity in Matroids
- Coverings and delta-coverings
- Delta matroids whose fundamental graphs are bipartite
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Evaluations of topological Tutte polynomials
- Excluded minors and the ribbon graphs of knots
- Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial
- Graph minors. XX: Wagner's conjecture
- Graph polynomials and their applications. I: The Tutte polynomial
- Graphs on surfaces. Dualities, polynomials, and knots
- Graphs, Links, and Duality on Surfaces
- Greedy algorithm and symmetric matroids
- Hopf algebras and Tutte polynomials
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 4162893 (Why is no real title available?)
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 3739583 (Why is no real title available?)
- scientific article; zbMATH DE number 67324 (Why is no real title available?)
- scientific article; zbMATH DE number 3512135 (Why is no real title available?)
- scientific article; zbMATH DE number 3627205 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 5251649 (Why is no real title available?)
- scientific article; zbMATH DE number 3257167 (Why is no real title available?)
- scientific article; zbMATH DE number 3049182 (Why is no real title available?)
- Inductive tools for connected delta-matroids and multimatroids
- Interlace polynomials for multimatroids and delta-matroids
- Isotropic matroids. II: Circle graphs
- Knot invariants and the Bollobás-Riordan polynomial of embedded graphs
- Lectures on matroids
- Maps and -matroids
- Multimatroids. III: Tightness and fundamental graphs
- Non-orientable quasi-trees for the Bollobás-Riordan polynomial
- Nullity and loop complementation for delta-matroids
- On the interplay between embedded graphs and delta-matroids
- On the interplay between graphs and matroids
- On the ribbon graphs of links in real projective space
- On the Tutte Polynomial of a Morphism of Matroids
- Partial duals of plane graphs, separability and the graphs of knots
- Polynomial invariants of graphs on surfaces
- Quasi-tree expansion for the Bollobás-Riordan-Tutte polynomial
- Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
- Separability and the genus of a partial dual
- Structure in minor-closed classes of matroids
- The delta-sum of matching delta-matroids
- The group structure of pivot and loop complementation on graphs and set systems
- The linear delta-matroid parity problem
- The transition matroid of a 4-regular graph: an introduction
- THISTLETHWAITE'S THEOREM FOR VIRTUAL LINKS
- Tutte-Whitney polynomials: some history and generalizations
- Twisted duality for embedded graphs
Cited in
(50)- Sorting by reversals and the theory of 4-regular graphs
- The structure of delta-matroids with width one twists
- Hopf algebras and Tutte polynomials
- A convolution formula for Tutte polynomials of arithmetic matroids and other combinatorial structures
- Matroidal frameworks for topological Tutte polynomials
- Lagrangian subspaces, delta-matroids, and four-term relations
- An extension of Stanley's chromatic symmetric function to binary delta-matroids
- The excluded 3-minors for vf-safe delta-matroids
- Delta-matroids as subsystems of sequences of Higgs lifts
- A 2-isomorphism theorem for delta-matroids
- On a conjecture of Gross, Mansour and Tucker
- Eulerian and bipartite binary delta-matroids
- Partial duality of hypermaps
- Irreducibility of the Tutte polynomial of an embedded graph
- Characterization of regular checkerboard colourable twisted duals of ribbon graphs
- Inductive tools for connected delta-matroids and multimatroids
- Interlacement and activities in delta-matroids
- Maps and -matroids
- Twist polynomials of delta-matroids
- The number of quasi-trees in fans and wheels
- Handle slides for delta-matroids
- Observations on maps and Δ-matroids
- The Las Vergnas polynomial for embedded graphs
- The universal valuation of Coxeter matroids
- Bollobás-Riordan and relative Tutte polynomials
- Topological graph theory through matroid theory
- Transition polynomial as a weight system for binary delta-matroids
- Partial-dual polynomials and signed intersection graphs
- Delta-matroids for graph theorists
- On the interplay between embedded graphs and delta-matroids
- New dualities from old: generating geometric, Petrie, and Wilson dualities and trialities of ribbon graphs
- From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
- Blowup polynomials and delta-matroids of graphs
- Partial-twuality polynomials of delta-matroids
- Delta-matroids whose twist polynomials are monomials
- Signed permutohedra, delta‐matroids, and beyond
- On the handle slide operation and universality polynomial invariants for binary -matroids
- Strong log-convexity of genus sequences
- Twist monomials of binary delta-matroids
- A primer on delta-matroids and multimatroids
- Constructing a Tutte polynomial for graphs embedded in surfaces
- Partial duality for ribbon graphs
- The critical group of a combinatorial map
- Twist polynomial as a weight system for set systems
- Orthogonal matroids over tracts
- An activities expansion of the transition polynomial of a multimatroid
- Rank functions and invariants of delta-matroids
- Polynomial graph invariants induced from the \(\mathfrak{gl} \)-weight system
- Introducing a vertex polynomial invariant for embedded graphs
- Graph polynomials and local graph operations
This page was built for publication: Matroids, delta-matroids and embedded graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2318477)
