APPLICATIONS OF GAUSSIAN FIELDS TO THE PERMANENT AND THE MATCHING POLYNOMIAL

In this thesis, we explore applications of Gaussian fields to the problems of approximating the permanent of a matrix and to the theory of the matching polynomial of a graph. In the first part of this thesis, we introduce a new randomized algorithm that leverages a form of Wick's theorem to estimate the permanent of a real matrix. In particular, we do this by viewing the permanent as the expectation of a product of centered joint Gaussian random variables with a particular covariance matrix C. The algorithm outputs the empirical mean S_{N} of this product after sampling N times. Our algorithm runs in polynomial time and we provide an error analysis to bound the failure probability. We compare our procedure to a previous procedure due to Gurvits. We discuss how to find a particular covariance matrix C using a semidefinite program and a relation to the Max-Cut problem and cut norms. In the second part of this thesis, we use these techniques to prove a new identity for the matching polynomial P_{G}(x) of a graph G. In doing so, we introduce a random procedure for estimating the coefficients of P_{G}(x) and provide a new proof of a duality result due to Godsil.

Grantor dc:publisher

Temple University. Libraries

Year dc:date.issued

2024

Author dc:creator

• Mukerji, Tantrik

Advisor dc:contributor.advisor

• Yang, Wei-shih, 1954-

Committee members dc:contributor.committeemember

• Yilmaz, Atilla
• Queisser, Gillian
• Shi, Yuan

• Mathematics

Statement dc:rights

• IN COPYRIGHT- This Rights Statement can be used for an Item that is in copyright. Using this statement implies that the organization making this Item available has determined that the Item is in copyright and either is the rights-holder, has obtained permission from the rights-holder(s) to make their Work(s) available, or makes the Item available under an exception or limitation to copyright (including Fair Use) that entitles it to make the Item available.

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/20.500.12613/10622

OAI identifier oai:identifier

oai:scholarshare.temple.edu:20.500.12613/10622