The active bijection for graphs
From MaRDI portal
Abstract: The active bijection forms a package of results studied by the authors in a series of papers in oriented matroids. The present paper is intended to state the main results in the particular case, and more widespread language, of graphs. We associate any directed graph, defined on a linearly ordered set of edges, with one particular of its spanning trees, which we call its active spanning tree. For any graph on a linearly ordered set of edges, this yields a surjective mapping from orientations onto spanning trees, which preserves activities (for orientations in the sense of Las Vergnas, for spanning trees in the sense of Tutte), as well as some partitions (or filtrations) of the edge set associated with orientations and spanning trees. It yields a canonical bijection between classes of orientations and spanning trees, as well as a refined bijection between all orientations and edge subsets, containing various noticeable bijections [...]. Several constructions of independent interest are involved. The basic case concerns bipolar orientations, which are in bijection with their fully optimal spanning trees, as proved in a previous paper, and as computed in a companion paper. We give a canonical decomposition of a directed graph on a linearly ordered set of edges into acyclic/cyclic bipolar directed graphs. Considering all orientations of a graph, we obtain an expression of the Tutte polynomial in terms of products of beta invariants of minors, a remarkable partition of the set of orientations into activity classes, and a simple expression of the Tutte polynomial using four orientation activity parameters. We derive a similar decomposition theorem for spanning trees. We also provide a general deletion/contraction framework for these bijections and relatives.
Recommendations
- Activity preserving bijections between spanning trees and orientations in graphs
- The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
- Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids
- The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
- A bijection for Eulerian-equivalence classes of totally cyclic orientations
Cites work
- scientific article; zbMATH DE number 3885920 (Why is no real title available?)
- scientific article; zbMATH DE number 3869362 (Why is no real title available?)
- scientific article; zbMATH DE number 3821756 (Why is no real title available?)
- scientific article; zbMATH DE number 4002104 (Why is no real title available?)
- A Contribution to the Theory of Chromatic Polynomials
- A convolution formula for the Tutte polynomial
- A higher invariant for matroids
- A linear programming construction of fully optimal bases in graphs and hyperplane arrangements
- Activity preserving bijections between spanning trees and orientations in graphs
- Acyclic and totally cyclic orientations of combinatorial geometries
- Acyclic orientations and chromatic generating functions
- Acyclic orientations and the chromatic polynomial
- Acyclic orientations of graphs
- Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids
- Bijective proofs of two broken circuit theorems
- Combinatorial problems of commutation and rearrangements
- External and internal elements of a matroid basis
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- Fourientation activities and the Tutte polynomial
- Fourientations and the Tutte polynomial
- Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids
- Generalized activities and the Tutte polynomial
- Interval partitions and activities for the greedoid Tutte polynomial
- On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids
- On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
- Oriented Matroids
- Partitions ofN-Space by Hyperplanes
- Sinks in acyclic orientations of graphs
- The Dichromate and Orientations of a Graph
- The Tutte polynomial
- The Tutte polynomial of a morphism of matroids. V: Derivatives as generating functions of Tutte activities
- The Tutte polynomial of matroid perspectives
- The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
- The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
- Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
- \(G\)-parking functions, acyclic orientations and spanning trees
Cited in
(13)- The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region
- On the activities and partitions of the vertex subsets of graphs
- Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
- The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
- On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids
- Activity preserving bijections between spanning trees and orientations in graphs
- A linear programming construction of fully optimal bases in graphs and hyperplane arrangements
- A bijection for Eulerian-equivalence classes of totally cyclic orientations
- Geometric bijections between spanning trees and break divisors
- Computing the fully optimal spanning tree of an ordered bipolar directed graph
- Geometric bijections between spanning subgraphs and orientations of a graph
- From spanning forests to edge subsets
- scientific article; zbMATH DE number 7203409 (Why is no real title available?)
This page was built for publication: The active bijection for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670651)
