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
Combinatorics and zeros of multivariate polynomials
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.). (Kombinatorik)ORCID iD: 0000-0002-2305-9764
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: urn:nbn:se:kth:diva-251303ISBN: 978-91-7873-210-4 (print)OAI: oai:DiVA.org:kth-251303DiVA, id: diva2:1314811
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
List of papers
1. Non-representable hyperbolic matroids
Open this publication in new window or tab >>Non-representable hyperbolic matroids
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
Keywords
Hyperbolic polynomial, Generalized Lax conjecture, Matroid, Hyperbolic matroid
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-233273 (URN)10.1016/j.aim.2018.03.038 (DOI)000440392700009 ()2-s2.0-85049357702 (Scopus ID)
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
2. Spectrahedrality of hyperbolicity cones of multivariate matching polynomials
Open this publication in new window or tab >>Spectrahedrality of hyperbolicity cones of multivariate matching polynomials
2018 (English)In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192Article in journal (Refereed) In press
Abstract [en]

The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. We prove the conjecture for a multivariate generalization of the matching polynomial. This is further extended (albeit in a weaker sense) to a multivariate version of the independence polynomial for simplicial graphs. As an application we give a new proof of the conjecture for elementary symmetric polynomials (originally due to Brändén). Finally we consider a hyperbolic convolution of determinant polynomials generalizing an identity of Godsil and Gutman.

Place, publisher, year, edition, pages
Springer, 2018
Keywords
matching polynomial, independence polynomial, generalized Lax conjecture, spectrahedral representation
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-250763 (URN)10.1007/s10801-018-0848-9 (DOI)
Note

QC 20190510

Available from: 2019-05-05 Created: 2019-05-05 Last updated: 2019-10-11Bibliographically approved
3. Stable multivariate generalizations of matching polynomials
Open this publication in new window or tab >>Stable multivariate generalizations of matching polynomials
(English)Manuscript (preprint) (Other academic)
Abstract [en]

The first part of this note concerns stable averages of multivariate matching polynomials. In proving the existence of infinite families of bipartite Ramanujan d-coverings, Hall, Puder and Sawin introduced the d-matching polynomial of a graph G, defined as the uniform average of matching polynomials over the set of d-sheeted covering graphs of G. We prove that a natural multivariate version of the d-matching polynomial is stable, consequently giving a short direct proof of the real-rootedness of the d-matching polynomial. Our theorem also includes graphs with loops, thus answering a question of said authors. Furthermore we define a weaker notion of matchings for hypergraphs and prove that a family of natural polynomials associated to such matchings are stable. In particular this provides a hypergraphic generalization of the classical Heilmann-Lieb theorem.

Keywords
generalized matching polynomial, stable polynomial, hypergraph
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-250765 (URN)
Note

QC 20190510

Available from: 2019-05-05 Created: 2019-05-05 Last updated: 2019-05-13Bibliographically approved
4. Equidistributions of mahonian statistics over pattern avoiding permutations
Open this publication in new window or tab >>Equidistributions of mahonian statistics over pattern avoiding permutations
2018 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 1, article id P1.7Article in journal (Refereed) Published
Abstract [en]

A Mahonian d-function is a Mahonian statistic that can be expressed as a linear combination of vincular pattern functions of length at most d. Babson and Ste- ingrímsson classified all Mahonian 3-functions up to trivial bijections and identified many of them with well-known Mahonian statistics in the literature. We prove a host of Mahonian 3-function equidistributions over permutations in Sn avoiding a single classical pattern in S3. Tools used include block decomposition, Dyck paths and generating functions.

Place, publisher, year, edition, pages
Australian National University Press, 2018
Keywords
Dyck path statistic, Equidistribution, Mahonian statistic, Pattern avoidance, Polyomino, St-Wilf equivalence
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-222257 (URN)000432155700008 ()2-s2.0-85040954000 (Scopus ID)
Note

QC 20180205

Available from: 2018-02-05 Created: 2018-02-05 Last updated: 2019-05-10Bibliographically approved
5. The cone of cyclic sieving phenomena
Open this publication in new window or tab >>The cone of cyclic sieving phenomena
2019 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 342, no 6, p. 1581-1601Article in journal (Refereed) Published
Abstract [en]

We study cyclic sieving phenomena (CSP) on combinatorial objects from an abstract point of view by considering a rational polyhedral cone determined by the linear equations that define such phenomena. Each lattice point in the cone corresponds to a non-negative integer matrix which jointly records the statistic and cyclic order distribution associated with the set of objects realizing the CSP. In particular we consider a universal subcone onto which every CSP matrix linearly projects such that the projection realizes a CSP with the same cyclic orbit structure, but via a universal statistic that has even distribution on the orbits.

Reiner et.al. showed that every cyclic action gives rise to a unique polynomial (mod q^n-1) complementing the action to a CSP. We give a necessary and sufficient criterion for the converse to hold. This characterization allows one to determine if a combinatorial set with a statistic gives rise (in principle) to a CSP without having a combinatorial realization of the cyclic action. We apply the criterion to conjecture a new CSP involving stretched Schur polynomials and prove our conjecture for certain rectangular tableaux. Finally we study some geometric properties of the CSP cone. We explicitly determine its half-space description and in the prime order case we determine its extreme rays.

Place, publisher, year, edition, pages
Elsevier, 2019
Keywords
cyclic sieving, stretched schur polynomial, convex polytope
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-250764 (URN)10.1016/j.disc.2019.01.037 (DOI)000466833400006 ()2-s2.0-85062678575 (Scopus ID)
Note

QC 20190510

Available from: 2019-05-05 Created: 2019-05-05 Last updated: 2019-05-29Bibliographically approved

Open Access in DiVA

fulltext(510 kB)59 downloads
File information
File name FULLTEXT01.pdfFile size 510 kBChecksum SHA-512
3105db5f504de20b1efcdbf7dcf7f0130782d41b6fe52c41928f9d845313a3f7787e9c54ad5a852817e454e9a68f73bd0eac841b7973a4c9a87792a3dbf34056
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Amini, Nima
By organisation
Mathematics (Div.)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 59 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 649 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