Homogeneous multivariate polynomials with the half-plane property

DOI10.1016/S0196-8858(03)00078-2zbMATH Open1054.05024arXivmath/0202034OpenAlexW3123082523WikidataQ56893243 ScholiaQ56893243MaRDI QIDQ1432999FDOQ1432999

Authors: Young-Bin Choe, Alan D. Sokal, David G. Wagner, James Oxley 

Publication date: 15 June 2004

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A polynomial P in n complex variables is said to have the "half-plane property" (or Hurwitz property) if it is nonvanishing whenever all the variables lie in the open right half-plane. Such polynomials arise in combinatorics, reliability theory, electrical circuit theory and statistical mechanics. A particularly important case is when the polynomial is homogeneous and multiaffine: then it is the (weighted) generating polynomial of an r-uniform set system. We prove that the support (set of nonzero coefficients) of a homogeneous multiaffine polynomial with the half-plane property is necessarily the set of bases of a matroid. Conversely, we ask: For which matroids M does the basis generating polynomial P_{B(M)} have the half-plane property? Not all matroids have the half-plane property, but we find large classes that do: all sixth-root-of-unity matroids, and a subclass of transversal (or cotransversal) matroids that we call "nice". Furthermore, the class of matroids with the half-plane property is closed under minors, duality, direct sums, 2-sums, series and parallel connection, full-rank matroid union, and some special cases of principal truncation, principal extension, principal cotruncation and principal coextension. Our positive results depend on two distinct (and apparently unrelated) methods for constructing polynomials with the half-plane property: a determinant construction (exploiting "energy" arguments), and a permanent construction (exploiting the Heilmann-Lieb theorem on matching polynomials). We conclude with a list of open questions.

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

Recommendations

• Polynomials with the half-plane property and matroid theory
• Polynomials with the half-plane property and the support theorems
• Discrete concavity and the half-plane property
• On the half-plane property and the Tutte group of a matroid
• A criterion for the half-plane property

zbMATH Keywords

matching polynomialmatroidreliability polynomialspanning treematrix-tree theoremHurwitz polynomialLee-Yang theoremhalf-plane propertyBrown-Colbourn conjecturepositive rational functionHurwitz property

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Computational synthetic geometry
• Title not available (Why is that?)
• Theory of monomer-dimer systems
• Title not available (Why is that?)
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Vector Representation of Matroids
• Title not available (Why is that?)
• Theorems on the Partition Functions of the Heisenberg Ferromagnets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• A combinatorial approach to matrix algebra
• The \(P(\phi )_{2}\) Euclidean (quantum) field theory.
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• Title not available (Why is that?)
• Permanents
• A Generalization of a Theorem of Bôcher
• Mathematics for the Analysis of Algorithms.
• The excluded minors for GF(4)-representable matroids
• The dissection of rectangles into squares
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Sur la complexité du principe de Tarski-Seidenberg
• Title not available (Why is that?)
• The dependence graph for bases in matroids
• On the combinatorial and algebraic complexity of quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• An Affine Representation for Transversal Geometries
• New results on stable multidimensional polynomials-Part I: Continuous case
• Roots of the Reliability Polynomials
• Synthesis of a Finite Two-terminal Network whose Driving-point Impedance is a Prescribed Function of Frequency
• The membership problem in jump systems
• Title not available (Why is that?)
• Complexity of deciding Tarski algebra
• A characterisation of the matroids representable over GF(3) and the rationals
• Partial fields and matroid representation
• On Matroids Representable over 𝐺𝐹(3) and Other Fields
• On the Eneström-Kakeya theorem and its sharpness
• Matrix tree theorems
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• Zeros of Reliability Polynomials and f-vectors of Matroids
• Some remarks on the location of zeroes of the partition function for lattice systems
• Zeros of the partition function for generalized ising systems
• Eigenvalues and partitionings of the edges of a graph
• On Fundamental Transversal Matroids
• A characterization of transversal independence spaces
• Title not available (Why is that?)
• Generalized \(\Delta\text{--}Y\) exchange and \(k\)-regular matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the excluded minors for quaternary matroids
• Title not available (Why is that?)
• On matroids without a non-Fano minor
• On maximum-sized \(k\)-regular matroids
• Title not available (Why is that?)
• On quadratic Hurwitz forms. I
• Wang algebra and matroids

Cited In (85)

• Strictness of the log-concavity of generating polynomials of matroids
• Interpolation of holomorphic functions and surjectivity of Taylor coefficient multipliers
• Matchings on infinite graphs
• The Chow form of a reciprocal linear space
• Lee-Yang problems and the geometry of multivariate polynomials
• Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
• Polynomials with the half-plane property and matroid theory
• Matroids on Eight Elements with the Half-Plane Property and Related Concepts
• Lee-Yang theorems and the complexity of computing averages
• On the stability of independence polynomials
• Discrete concavity and the half-plane property
• Weighted enumeration of spanning subgraphs with degree constraints
• A little statistical mechanics for the graph theorist
• Non-representable hyperbolic matroids
• A converse to the Grace–Walsh–Szegő theorem
• Lorentzian polynomials
• Positively hyperbolic varieties, tropicalization, and positroids
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Correlation bounds for fields and matroids
• Matroids arising from electrical networks
• Euler type partial differential operators on real analytic functions
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
• Hyperbolic polynomials, interlacers, and sums of squares
• Determinantal probability measures
• Combinatorics and preservation of conically stable polynomials
• Discrete concavity and zeros of polynomials
• Strict log-concavity of the Kirchhoff polynomial and its applications to the strong Lefschetz property
• On the roots of domination polynomials
• On real-valued homogeneous polynomials with many variables
• Negative Correlation in Graphs and Matroids
• Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
• Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
• Obstructions to determinantal representability
• A combinatorial proof of the Rayleigh formula for graphs
• A criterion for the half-plane property
• Surjectivity of Euler type differential operators on spaces of smooth functions
• Real fibered morphisms and Ulrich sheaves
• Matroids -- the engineers' revenge
• Complete monotonicity for inverse powers of some combinatorially defined polynomials
• A generalization of the Heine-Stieltjes theorem
• A note on the hyperbolicity cone of the specialized Vámos polynomial
• On the roots of total domination polynomial of graphs
• On the roots of all-terminal reliability polynomials
• On the number of matchings of graphs formed by a graph operation
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products
• The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
• A logician's view of graph polynomials
• Negative dependence in sampling
• The separating semigroup of a real curve
• On the half-plane property and the Tutte group of a matroid
• Multivariate stable polynomials: theory and applications
• Negative dependence and the geometry of polynomials
• The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• Non-representable hyperbolic matroids (Extended abstract)
• Hyperbolic polynomials and generalized Clifford algebras
• Smooth hyperbolicity cones are spectrahedral shadows
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Matroid inequalities from electrical network theory
• Polynomials with the half-plane property and the support theorems
• Introduction to the combinatorial atlas
• Positive matrix representations of rational positive real functions of several variables
• Amalgamation of real zero polynomials
• Classification theorems for operators preserving zeros in a strip
• A short survey on stable polynomials, orientations and matchings
• Spectral linear matrix inequalities
• Special issue in honour of James Oxley
• Blowup polynomials and delta-matroids of graphs
• Paving property for real stable polynomials and strongly Rayleigh processes
• Log-concave poset inequalities
• On stability of spanning tree degree enumerators
• Semantic equivalence of graph polynomials definable in second order logic
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• Multivariate Eulerian polynomials and exclusion processes
• Lee-Yang polynomials and ground states of spin systems
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• Surjectivity of Hadamard type operators on spaces of smooth functions
• Global right inverses for Euler type differential operators on the space of smooth functions
• Gap distributions of Fourier quasicrystals with integer weights via Lee-Yang polynomials
• Generalizations of the matching polynomial to the multivariate independence polynomial
• Total nonnegativity and stable polynomials
• Configuration polynomials under contact equivalence
• Counting matchings via capacity-preserving operators

This page was built for publication: Homogeneous multivariate polynomials with the half-plane property

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