The probabilistic Kirchhoff polynomials and a problem of Kontsevich.

Format:

Book

Thesis/Dissertation

Author/Creator:

Yang, Chao.

Contributor:

Chung, Fan R. K., 1949- advisor.

University of Pennsylvania.

Language:

English

Subjects (All):

Computer science.

Mathematics.

0405.

0984.

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Local Subjects:

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

0405.

0984.

Physical Description:

99 pages

Contained In:

Dissertation Abstracts International 60-04B.

System Details:

Mode of access: World Wide Web.

text file

Summary:

For an undirected graph G, each of its edges is assigned a variable as its weight. The weight of a tree is defined to be the product of the weights on all its edges, while the Kirchhoff polynomial of a graph is defined to be the sum of the weights over all its spanning trees. The problem of interest is to determine the probability function Pk( G) that makes the Kirchhoff polynomial of a graph G equals 0, provided that all variables are random, independent and uniformly distributed over a finite field F . We also want to know if this function is a universal polynomial in 1/ ∣F∣ as proposed by M. Kontsevich.

In literature, the case for complete graphs has been investigated from several viewpoints. Pk( Pk&parl0;Kn&parr0; was given explicitly as a universal polynomial in 1/ ∣F∣ . But for general graphs, no deterministic algorithm is known by now to be able to compute these probability functions except by brute force, which usually takes O&parl0;2n2&parr0; steps for a graph on n vertices.

In this thesis, we apply the matrix-tree theorem and the symmetric Gaussian elimination method to study the problem. An efficient O( n) algorithm is given to compute the probabilistic Kirchhoff functions of general families of graphs such as the outerplanar graphs, the outerplanar graphs with apexes added, and "almost complete" graphs (e.g. Kn -- forest). The Kontsevich Conjecture is verified for these cases. Stanley's conjecture on the explicit formula for Kn-Km is settled, his two-apex condition is relaxed and improved. The polynomials are also derived for small graphs with no more than 6 vertices, and Fano graphs Fano(2,3) and Fano*(2,3).

Notes:

Thesis (Ph.D. in Mathematics) -- University of Pennsylvania, 1999.

Source: Dissertation Abstracts International, Volume: 60-04, Section: B, page: 1646.

Supervisor: Fan Chung Graham.

Local Notes:

School code: 0175.

ISBN:

9780599259836

Access Restriction:

Restricted for use by site license.