Decomposition of regular matroids

From MaRDI portal

Publication:1144028

Jump to:navigation, search

DOI10.1016/0095-8956(80)90075-1zbMath0443.05027OpenAlexW2040101882WikidataQ56209792 ScholiaQ56209792MaRDI QIDQ1144028

P. D. Seymour

Publication date: 1980

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(80)90075-1

zbMATH Keywords

binary matroids sums regular matroid circuit matroid cocircuit matroid linear independence matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Recognizing Even-Cycle and Even-Cut Matroids, Even circuits in oriented matroids, Unnamed Item, Binary group and Chinese postman polyhedra, On sign-representable matroids, Covering Vectors by Spaces: Regular Matroids, Some Local Extremal Connectivity Results for Matroids, Regular Matroids Have Polynomial Extension Complexity, The Null Space Problem I. Complexity, Some Small Circuit-Cocircuit Ramsey Numbers for Matroids, Non-Binary Matroids Having At Most Three Non-Binary Elements, Unnamed Item, Polyhedral Combinatorics in Combinatorial Optimization, A splitter theorem for elastic elements in 3-connected matroids, On combinatorial properties of binary spaces, The Hilbert basis of the cut cone over the complete graph K 6, Counting vertices of integral polytopes defined by facets, Recognizing even-cycle and even-cut matroids, Short rainbow cycles in graphs and matroids, Odd Solutions to Systems of Inequalities Coming From Regular Chain Groups, Advances on strictly \(\varDelta \)-modular IPs, Supereulerian regular matroids without small cocircuits, A binary-matroid analogue of a graph connectivity theorem of Jamison and Mulder, Geometry. Abstracts from the workshop held June 12--18, 2022, The work of June Huh, Small separations in pinch-graphic matroids, Recognizing pinch-graphic matroids, Generating simple near‐bipartite bricks, Minimal tropical bases for Bergman fans of matroids, On Connectivity in Matroids and Graphs, Unnamed Item, Cobiased graphs: single-element extensions and elementary quotients of graphic matroids, Structural properties and recognition of restricted and strongly unimodular matrices, Packing and covering with integral feasible flows in integral supply-demand networks, On Matroids Representable over 𝐺𝐹(3) and Other Fields, A Characterization of Graphic Matroids Based on Circuit Orderings, Binary Supersolvable Matroids and Modular Constructions, ON TANGLES AND MATROIDS, On ideal clutters, metrics and multiflows, A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices, Growth Rates and Critical Exponents of Classes of Binary Combinatorial Geometries, A new proof for a result of Kingan and Lemos', A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid, Subdeterminants and Concave Integer Quadratic Programming, The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids, Bounds of characteristic polynomials of regular matroids, On the computational complexity of the Jones and Tutte polynomials, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, The equivariant volumes of the permutahedron, A Characterization of Almost-Planar Graphs, Polyhedral techniques in combinatorial optimization I: Theory, On deformation and classification of ∨-systems, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Unnamed Item, Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices, Polynomial algorithms for a class of linear programs, On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes), Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces, On the basis pair graphs of signed-graphic matroids, On Crapo's Beta Invariant for Matroids, A generalisation of uniform matroids, Minors of 3-connected matroids, Edge-disjoint odd cycles in 4-edge-connected graphs, Polyhedral proof methods in combinatorial optimization, Semi-duality and the cycle double cover conjecture, A decomposition theory for matroids. II. Minimal violation matroids, A decomposition theory for matroids. III. Decomposition conditions, Triples in matroid circuits, On chains of 3-connected matroids, Decomposition and optimization over cycles in binary matroids, A survey on flows in graphs and matroids, On ternary transversal matroids, Extended formulations for sparsity matroids, Adjacency in binary matroids, Short cocircuits in binary matroids, Towards a splitter theorem for internally 4-connected binary matroids. IX. The theorem., Circuits and cocircuits in regular matroids, Extended formulations for independence polytopes of regular matroids, The excluded minors for the class of matroids that are graphic or bicircular lift, Enumerating orientations of the free spikes, On internally 4-connected non-regular binary matroids, A forbidden-minor characterization for the class of regular matroids which yield the cographic es-splitting matroids, Testing additive integrality gaps, On the circuit-cocircuit intersection conjecture, Axioms for infinite matroids, Inequivalent representations of matroids over prime fields, Towards a splitter theorem for internally 4-connected binary matroids. III, Towards a splitter theorem for internally 4-connected binary matroids. IV, Towards a splitter theorem for internally 4-connected binary matroids. V, Dominating circuits in regular matroids, A base exchange property for regular matroids, A splitter theorem relative to a fixed basis, Strong splitter theorem, On the sum of a parallelotope and a zonotope, The structure of 2-separations of infinite matroids, Signed graphs whose signed Colin de Verdière parameter is two, Minor relations for quadrangulations on the sphere, An upgraded Wheels-and-Whirls theorem for 3-connected matroids, Stability, fragility, and Rota's conjecture, Detecting minors in matroids through triangles, Matroids with at least two regular elements, Capturing matroid elements in unavoidable 3-connected minors, Clones in 3-connected frame matroids, An Erdős-Gallai theorem for matroids, Generating an internally 4-connected binary matroid from another, Discovering all associations in discrete data using frequent minimally infrequent attribute sets, Combinatorial geometries representable over GF(3) and GF(q). II: Dowling geometries, Spanning cycles in regular matroids without small cocircuits, On 3-connected minors of 3-connected matroids and graphs, Unimodular systems of vectors are embeddable in the \((0, 1)\)-cube, Maintaining 3-connectivity relative to a fixed basis, Delta-wye reduction of almost-planar graphs, Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs, Relations between the circumference and \(e\)-circumference of a matroid, A decomposition theorem for binary matroids with no prism minor, Weak orientability of matroids and polynomial equations, Characterizing binary matroids with no \(P_9\)-minor, Constructive characterizations of 3-connected matroids of path width three, Towards a splitter theorem for internally 4-connected binary matroids. VII, Minimally 3-connected binary matroids, Displaying blocking pairs in signed graphs, Unimodular binary hierarchical models, A characterization of some graph classes using excluded minors, The signed-graphic representations of wheels and whirls, Contracting an element from a cocircuit, Some open problems on excluding a uniform matroid, Tutte polynomials computable in polynomial time, Planar graphs with no 6-wheel minor, The anti-join composition and polyhedra, \(k\)-sum decomposition of strongly unimodular matrices, On the excluded minors for regular matroids which yield cographic splitting matroids, Comparing perfect and 2nd Voronoi decompositions: the matroidal locus, The 3-connected matroids with circumference 6, Almost-graphic matroids, Ideal clutters, Restrictions as stabilizers, Torsion formulas for signed graphs, Clonal sets in \(GF(q)\)-representable matroids, A conjecture of Welsh revisited, A chain theorem for internally 4-connected binary matroids, The regular matroids with no 5-wheel minor, Removing circuits in 3-connected binary matroids, A simpler proof for the two disjoint odd cycles theorem, The decomposition of the hypermetric cone into \(L\)-domains, On clone sets of \(GF(q)\)-representable matroids, Linear quadratic programming in oriented matroids, On the intersections of circuits and cocircuits in matroids, Combinatorial optimization with 2-joins, The 3-connected binary matroids with circumference 6 or 7, Circuit-difference matroids, On the representability of totally unimodular matrices on bidirected graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Recent trends in combinatorial optimization, A note on nongraphic matroids, A decomposition theory for matroids. I: General results, A hierarchy of totally unimodular matrices, On theories of Whitney and Tutte, A characterization of the ternary matroids with no \(M(K_ 4)\)-minor, Stabilizer theorems for even cycle matroids, A circuit characterization of graphic matroids, Matroids having the same connectivity function, On binary matroids without a \(P_{10}\)-minor, On rounded five-element lines of matroids, A construction for binary matroids, Compositions for matroids with the Fulkerson property, Decomposition of wheel-and-parachute-free balanced bipartite graphs, Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix, Recognizing max-flow min-cut path matrices, A decomposition theory for matroids. V: Testing of matrix total unimodularity, Strong unimodularity for matrices and hypergraphs, Optima of dual integer linear programs, Splitting formulas for Tutte polynomials, Note on inseparability graphs of matroids having exactly one class of orientations, Chordal characterization of graphic matroids, The incidence structure of subspaces with well-scaled frames, A characterization of a class of non-binary matroids, A generalization of a graph result of D. W. Hall, Quasiregular matroids, Base exchange properties of graphic matroids, A longest cycle version of Tutte's wheels theorem, Staircase compatibility and its applications in scheduling and piecewise linearization, Directed submodularity, ditroids and directed submodular flows, Turán's triangle theorem and binary matroids, On 3-connected matroids, Recognizing claw-free perfect graphs, Star-cutsets and perfect graphs, On contractible and vertically contractible elements in 3-connected matroids and graphs, Subspaces with well-scaled frames, A short proof of the Truemper-Tseng theorem on max-flow min-cut matroids, Large circuits in binary matroids of large cogirth. I, Flows, view obstructions, and the lonely runner, A splitter for graphs with no Petersen family minor, A splitter theorem on 3-connected matroids, Improving a chain theorem for triangle-free 3-connected matroids, Algebraic flows in regular matroids, Complement total unimodularity, On Tutte's extension of the four-colour problem, On the minor-minimal 3-connected matroids having a fixed minor., Non total-unimodularity neutralized simplicial complexes, Alpha-balanced graphs and matrices and GF(3)-representability of matroids, Matroids and multicommodity flows, Decomposition of group flows in regular matroids, Separating cocircuits in binary matroids, On minors of non-binary matroids, The class of binary matroids with no \(M\)(\(K_{3,3}\))-, \(M^{*}\)(\(K_{3,3}\))-, \(M\)(\(K_{5}\))- or \(M^{*}\)(\(K_{5}\))-minor., A simple theorem on 3-connectivity, An appraisal of computational complexity for operations researchers, \(k\)-elimination property for circuits of matroids, Classification of external zonotopal algebras, Triangles in 3-connected matroids, Ternary paving matroids, On minors avoiding elements in matroids, Matroids with many small circuits and cocircuits, Minimal \(k\)-connected non-Hamiltonian graphs, On the computational behavior of a polynomial-time network flow algorithm, Integer programs for logic constraint satisfaction, Structural properties and decomposition of linear balanced matrices, On almost-planar graphs, Short cycle covers and the cycle double cover conjecture, Extensions of Tutte's wheels-and-whirls theorem, A decomposition theory for matroids. VII: Analysis of minimal violation matrices, A decomposition theory for matroids. VI: Almost regular matroids, Discrete convexity and unimodularity. I., Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Towards a splitter theorem for internally 4-connected binary matroids. VI, Pseudocodeword-free criterion for codes with cycle-free Tanner graph, Some extremal connectivity results for matroids, A characterization of certain excluded-minor classes of matroids, Biased graphs whose matroids are special binary matroids, On an excluded-minor class of matroids, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Weak maps and stabilizers of classes of matroids, Large circuits in binary matroids of large cogirth. II, The Tutte polynomial of a ported matroid, Counterexamples to conjectures on 4-connected matroids, Linear programs for constraint satisfaction problems, A decomposition of the matroids with the max-flow min-cut property, Odd cycles and matrices with integrality properties, Four problems on graphs with excluded minors, Master polytopes for cycles of binary matroids, Stabilizers of classes of representable matroids, Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions, Decomposition of balanced matrices, On the efficiency of representability tests for matroids, A good submatrix is hard to find, On the structure of 3-connected matroids and graphs, Intersections of circuits and cocircuits in binary matroids, Triads and triangles in 3-connected matroids, On matroids without a non-Fano minor, Generalized \(\Delta\text{--}Y\) exchange and \(k\)-regular matroids, The excluded minors for GF(4)-representable matroids, On the excluded minors for quaternary matroids, Balanced \(0,\pm 1\) matrices. I: Decomposition, Matroid 4-connectivity: A deletion-contraction theorem, Totally free expansions of matroids., Generating internally four-connected graphs, On the connectivity function of a binary matroid, On extremal connectivity properties of unavoidable matroids, Maximal unimodular systems of vectors, Cycle cover ratio of regular matroids, Projective-Planar Graphs with No K3, 4-Minor, Decomposition of 3-connected graphs, Notes on \(\{a,b,c\}\)-modular matrices, A characterization of graphic matroids using non-separating cocircuits, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond, Small Chvátal rank, Recognizing binet matrices, A decomposition theory for matroids. IV: Decomposition of graphs, Projective-planar signed graphs and tangled signed graphs, Generating bricks, Hall-Type Results for 3-Connected Projective Graphs, Decompositions of signed-graphic matroids, The hypertoric intersection cohomology ring, Inequivalent representations of ternary matroids, Excluding Kuratowski graphs and their duals from binary matroids, Even-cycle decompositions of graphs with no odd-\(K_4\)-minor, Unbreakable matroids, On the structure of triangle-free 3-connected matroids, Hilbert bases of cuts, Binary matroids without prisms, prism duals, and cubes, Signed-graphic matroids with all-graphic cocircuits, A short proof of Shih's isomorphism theorem on graphic subspaces, On characterizing the class of cographic signed-graphic matroids, Reconstruction of infinite matroids from their 3-connected minors, Unnamed Item, Binary signed-graphic matroids: representations and recognition algorithms, Local 2-separators, On density-critical matroids, A splitter theorem for 3-connected 2-polymatroids, Sparse recovery with integrality constraints, An upper bound for the circumference of a 3-connected binary matroid, Implementation of a unimodularity test, Graph theory. Abstracts from the workshop held January 2--8, 2022, Hepp's bound for Feynman graphs and matroids, Balanced matrices, Combinatorial aspects of generalized complementary basic matrices, On two classes of nearly binary matroids, Splitter theorems for 4-regular graphs, On a base exchange game on bispanning graphs, Matroid connectivity and singularities of configuration hypersurfaces, A sharp bound on the size of a connected matroid, Pairs of largest circuits in 3-connected matroids, The universal Poisson deformation of hypertoric varieties and some classification results, Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, A note on binary matroid with no \(M(K_{3,3})\)-minor, Bounding the beta invariant of 3-connected matroids, The Regular Excluded Minors for Signed-Graphic Matroids, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, Cuboids, a class of clutters, Graver basis and proximity techniques for block-structured separable convex integer minimization problems, On the notion of generalized minor in topological network theory and matroids, Wild triangles in 3-connected matroids, The contributions of W.T. Tutte to matroid theory, The minimal \(\mathbb{Z}_n\)-symmetric graphs that are not \(\mathbb{Z}_n\)-spherical, Generating weakly 4-connected matroids, Recognising graphic and matroidal connectivity functions, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, Unnamed Item, Partial matroid representations, Complexity results on restricted instances of a paint shop problem for words, Equivalence-free exhaustive generation of matroid representations, Brace generation, The Internally 4-Connected Binary Matroids With No 𝑀(𝐾_{3,3})-Minor., Thomas H. Brylawski (1944--2007), Unavoidable parallel minors of regular matroids, Obstructions to a binary matroid being graphic, The excluded minors for the class of matroids that are binary or ternary, A note on clone sets in representable matroids, Characterizing 3-connected planar graphs and graphic matroids, On powers of Plücker coordinates and representability of arithmetic matroids, Contractible edges in 3-connected graphs that preserve a minor, \(N\)-detachable pairs in 3-connected matroids. I: Unveiling \(X\), \(N\)-detachable pairs in 3-connected matroids. II: Life in \(X\), Elastic elements in 3-connected matroids, The behavior of Tutte polynomials of graphs under five graph operations and its applications, Graph minor theory, A Characterization of $K_{2,4}$-Minor-Free Graphs, \(N\)-critical matroids, Circle graph obstructions under pivoting, Unavoidable Connected Matroids Retaining a Specified Minor, On the recognition of \(\{a,b,c\}\)-modular matrices, On the regularity of orientable matroids, Characterizing matroids whose bases form graphic delta-matroids, \(N\)-detachable pairs in 3-connected matroids. III: The theorem, On Vertices and Facets of Combinatorial 2-Level Polytopes, Generating 5-regular planar graphs, A polynomial recognition algorithm for balanced matrices, Families of matroids induced by classes of graphs, Interpretations of the Tutte polynomials of regular matroids, A Characterization of Graphs with No Octahedron Minor, The structure of equivalent 3-separations in a 3-connected matroid, Recent work in matroid representation theory, Generation of simple quadrangulations of the sphere, Matroid 3-connectivity and branch width, Special issue in honour of James Oxley, Obstacles to decomposition theorems for sixth-root-of-unity matroids, Internally 4-connected binary matroids without a prism+\(e\) minor, On regular matroids without certain minors, On Seymour's decomposition theorem, Linear Balanceable and Subcubic Balanceable Graphs*

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1144028&oldid=13196795"