kth.sePublications KTH
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
Counting matchings via capacity-preserving operators
CUNY City Coll, New York, NY USA..
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).ORCID iD: 0000-0003-4123-4949
2021 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 6, p. 956-981Article in journal (Refereed) Published
Abstract [en]

The notion of the capacity of a polynomial was introduced by Gurvits around 2005, originally to give drastically simplified proofs of the van der Waerden lower bound for permanents of doubly stochastic matrices and Schrijver's inequality for perfect matchings of regular bipartite graphs. Since this seminal work, the notion of capacity has been utilised to bound various combinatorial quantities and to give polynomial-time algorithms to approximate such quantities (e.g. the number of bases of a matroid). These types of results are often proven by giving bounds on how much a particular differential operator can change the capacity of a given polynomial. In this paper, we unify the theory surrounding such capacity-preserving operators by giving tight capacity preservation bounds for all nondegenerate real stability preservers. We then use this theory to give a new proof of a recent result of Csikvari, which settled Friedland's lower matching conjecture.

Place, publisher, year, edition, pages
Cambridge University Press (CUP) , 2021. Vol. 30, no 6, p. 956-981
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-309280DOI: 10.1017/S0963548321000122ISI: 000753894400008Scopus ID: 2-s2.0-85105592971OAI: oai:DiVA.org:kth-309280DiVA, id: diva2:1640536
Note

QC 20220224

Available from: 2022-02-24 Created: 2022-02-24 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Leake, Jonathan

Search in DiVA

By author/editor
Leake, Jonathan
By organisation
Mathematics (Dept.)
In the same journal
Combinatorics, probability & computing
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 42 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