kth.sePublikationer KTH
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Counting matchings via capacity-preserving operators
CUNY City Coll, New York, NY USA..
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).ORCID-id: 0000-0003-4123-4949
2021 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, nr 6, s. 956-981Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Cambridge University Press (CUP) , 2021. Vol. 30, nr 6, s. 956-981
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-309280DOI: 10.1017/S0963548321000122ISI: 000753894400008Scopus ID: 2-s2.0-85105592971OAI: oai:DiVA.org:kth-309280DiVA, id: diva2:1640536
Anmärkning

QC 20220224

Tillgänglig från: 2022-02-24 Skapad: 2022-02-24 Senast uppdaterad: 2022-06-25Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Leake, Jonathan

Sök vidare i DiVA

Av författaren/redaktören
Leake, Jonathan
Av organisationen
Matematik (Inst.)
I samma tidskrift
Combinatorics, probability & computing
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 42 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf