Theta rank, levelness, and matroid minors

DOI10.1016/J.JCTB.2016.11.002zbMATH Open1354.05020arXiv1408.1262OpenAlexW2963821413MaRDI QIDQ505908FDOQ505908

Authors: Francesco Grande, Raman Sanyal 

Publication date: 26 January 2017

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

Abstract: The Theta rank of a finite point configuration $V$ is the maximal degree necessary for a sum-of-squares representation of a non-negative linear function on $V$. This is an important invariant for polynomial optimization that is in general hard to determine. We study the Theta rank and levelness, a related discrete-geometric invariant, for matroid base configurations. It is shown that the class of matroids with bounded Theta rank or levelness is closed under taking minors. This allows for a characterization of matroids with bounded Theta rank or levelness in terms of forbidden minors. We give the complete (finite) list of excluded minors for Theta-$1$ matroids which generalizes the well-known series-parallel graphs. Moreover, the class of Theta-$1$ matroids can be characterized in terms of the degree of generation of the vanishing ideal and in terms of the psd rank for the associated matroid base polytope. We further give a finite list of excluded minors for $k$-level graphs and matroids and we investigate the graphs of Theta rank $2$.

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

Recommendations

• The minimum rank of matrices and the equivalence class graph
• Cohen Macaulayness and arithmetical rank of generalized theta graphs
• Towards a matroid-minor structure theory
• Matroids and the minimum rank problem for matrix patterns
• On Matroid Representability and Minor Problems
• Rank-width and vertex-minors
• On the rank functions of \(\mathcal{H}\)-matroids
• A matroid generalization of theorems of Lewin and Gallai
• Matroid rank functions and discrete concavity
• A Tverberg type theorem for matroids

zbMATH Keywords

sum-of-squaresexcluded minor characterizationlevelnessmatroid base configurationstheta rank

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Polytopes of minimum positive semidefinite rank
• The Bergman complex of a matroid and phylogenetic trees
• Lifts of Convex Sets and Cone Factorizations
• A Combinatorial Model for Series-Parallel Networks
• Title not available (Why is that?)
• Matroid polytopes, nested sets and Bergman fans
• Minimally 2-connected graphs.
• On Minimal Blocks
• Theta bodies for polynomial ideals
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Constructions for projectively unique polytopes
• Compressed polytopes and statistical disclosure limitation
• Title not available (Why is that?)
• On Kalai's conjectures concerning centrally symmetric polytopes
• On series-parallel extensions of uniform matroids
• The regular matroids with no 5-wheel minor
• Flag enumerations of matroid base polytopes

Cited In (13)

• Slack matrices, \(k\)-products, and 2-level polytopes
• Recognizing Cartesian products of matrices and polytopes
• Two-level polytopes with a prescribed facet
• Projectively unique polytopes and toric slack ideals
• Tensor theta norms and low rank recovery
• Standard complexes of matroids and lattice paths
• Theta-ring graphs, \(\mathrm{I}{{\mathcal{O}}} \)-compatibility and \(\Delta \)-matroids
• Two double poset polytopes
• Extended formulations for independence polytopes of regular matroids
• Binary scalar products
• Many 2-level polytopes from matroids
• Four-dimensional polytopes of minimum positive semidefinite rank
• Extension complexity and realization spaces of hypersimplices

Uses Software

• Macaulay2

This page was built for publication: Theta rank, levelness, and matroid minors

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