Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Non-representable hyperbolic matroids
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2018 (English)In: Advances in Mathematics, ISSN 0001-8708, E-ISSN 1090-2082, Vol. 334, p. 417-449Article in journal (Refereed) Published
Abstract [en]

The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. Hyperbolic polynomials give rise to a class of (hyperbolic) matroids which properly contains the class of matroids representable over the complex numbers. This connection was used by the second author to construct counterexamples to algebraic (stronger) versions of the generalized Lax conjecture by considering a non-representable hyperbolic matroid. The Vamos matroid and a generalization of it are, prior to this work, the only known instances of non-representable hyperbolic matroids. We prove that the Non-Pappus and Non-Desargues matroids are non-representable hyperbolic matroids by exploiting a connection between Euclidean Jordan algebras and projective geometries. We further identify a large class of hyperbolic matroids which contains the Vamos matroid and the generalized Vamos matroids recently studied by Burton, Vinzant and Youm. This proves a conjecture of Burton et al. We also prove that many of the matroids considered here are non representable. The proof of hyperbolicity for the matroids in the class depends on proving nonnegativity of certain symmetric polynomials. In particular we generalize and strengthen several inequalities in the literature, such as the Laguerre Turan inequality and an inequality due to Jensen. Finally we explore consequences to algebraic versions of the generalized Lax conjecture.

Place, publisher, year, edition, pages
Academic Press, 2018. Vol. 334, p. 417-449
Keywords [en]
Hyperbolic polynomial, Generalized Lax conjecture, Matroid, Hyperbolic matroid
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-233273DOI: 10.1016/j.aim.2018.03.038ISI: 000440392700009Scopus ID: 2-s2.0-85049357702OAI: oai:DiVA.org:kth-233273DiVA, id: diva2:1239622
Funder
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Note

QC 20180817

Available from: 2018-08-17 Created: 2018-08-17 Last updated: 2019-05-10Bibliographically approved
In thesis
1. Combinatorics and zeros of multivariate polynomials
Open this publication in new window or tab >>Combinatorics and zeros of multivariate polynomials
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of five papers in algebraic and enumerative combinatorics. The objects at the heart of the thesis are combinatorial polynomials in one or more variables. We study their zeros, coefficients and special evaluations. Hyperbolic polynomials may be viewed as multivariate generalizations of real-rooted polynomials in one variable. To each hyperbolic polynomial one may associate a convex cone from which a matroid can be derived - a so called hyperbolic matroid. In Paper A we prove the existence of an infinite family of non-representable hyperbolic matroids parametrized by hypergraphs. We further use special members of our family to investigate consequences to a central conjecture around hyperbolic polynomials, namely the generalized Lax conjecture. Along the way we strengthen and generalize several symmetric function inequalities in the literature, such as the Laguerre-Tur\'an inequality and an inequality due to Jensen. In Paper B we affirm the generalized Lax conjecture for two related classes of combinatorial polynomials: multivariate matching polynomials over arbitrary graphs and multivariate independence polynomials over simplicial graphs. In Paper C we prove that the multivariate $d$-matching polynomial is hyperbolic for arbitrary multigraphs, in particular answering a question by Hall, Puder and Sawin. We also provide a hypergraphic generalization of a classical theorem by Heilmann and Lieb regarding the real-rootedness of the matching polynomial of a graph. In Paper D we establish a number of equidistributions between Mahonian statistics which are given by conic combinations of vincular pattern functions of length at most three, over permutations avoiding a single classical pattern of length three. In Paper E we find necessary and sufficient conditions for a candidate polynomial to be complemented to a cyclic sieving phenomenon (without regards to combinatorial context). We further take a geometric perspective on the phenomenon by associating a convex rational polyhedral cone which has integer lattice points in correspondence with cyclic sieving phenomena. We find the half-space description of this cone and investigate its properties.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2019. p. 42
Series
TRITA-SCI-FOU ; 2019:33
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-251303 (URN)978-91-7873-210-4 (ISBN)
Public defence
2019-05-24, D3, Lindstedsvägen 5, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20190510

Available from: 2019-05-10 Created: 2019-05-09 Last updated: 2019-05-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Amini, NimaBrändén, Petter
By organisation
Mathematics (Div.)
In the same journal
Advances in Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 257 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf