Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T23:22:19.714Z Has data issue: false hasContentIssue false
  • English
  • Français

A Graph Integral Formulation of the Circuit Partition Polynomial

Published online by Cambridge University Press:  11 October 2011

CRISTOPHER MOORE  and
ALEXANDER RUSSELL
CRISTOPHER MOORE
Affiliation:
Computer Science Department, University of New Mexico, Albuquerque, NM 87131, USA and The Santa Fe Institute, Santa Fe, NM 87501, USA (e-mail: moore@santafe.edu)
ALEXANDER RUSSELL
Affiliation:
Department of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USA (e-mail: acr@cse.uconn.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present a simple graph integral equivalent to a multiple of the circuit partition polynomial. Let G be a directed graph, and let k be a positive integer. Associate with each vertex v of G an independent, uniformly random k-dimensional complex vector xv of unit length. We define q(G;k) to be the expected value of the product, over all edges (u, v), of the inner product 〈xu, xv〉. We show that q(G;k) is proportional to G's cycle partition polynomial, and therefore that computing q(G;k) is #P-complete for any k > 1. We also study the natural variants that arise when the xv are real or drawn from the Gaussian distribution.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 6 , November 2011 , pp. 911 - 920
Copyright
Copyright © Cambridge University Press 2011

References

[1]Arratia, R., Bollobás, B. and Sorkin, G. (2000) The interlace polynomial: A new graph polynomial. In Proc. 11th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 237–245.Google Scholar
[2]Austin, A. (2007) The circuit partition polynomial with applications and relation to the Tutte and interlace polynomials. Rose-Hulman Undergraduate Mathematics J. 8.Google Scholar
[3]Bollobás, B. (2002) Evaluations of the circuit partition polynomial. J. Combin. Theory Ser. B 85 261–268.CrossRefGoogle Scholar
[4]Bouchet, A. (1991) Tutte–Martin polynomials and orienting vectors of isotropic systems. Graphs Combin. 7 235–252.CrossRefGoogle Scholar
[5]Brauer, R. (1937) On algebras which are connected with the semisimple continuous groups. Ann. of Math. 38 857–872.CrossRefGoogle Scholar
[6]Brightwell, G. R. and Winkler, P. (2005) Counting Eulerian circuits is #P-complete. In Proc. 7th ALENEX & 2nd ANALCO: Vancouver (Demetrescu, C., Sedgewick, R. and Tamassia, R., eds), SIAM, pp. 259–262.Google Scholar
[7]Ellis-Monaghan, J. A. (1998) New results for the Martin polynomial. J. Combin. Theory Ser. B 74 326–352.CrossRefGoogle Scholar
[8]Ellis-Monaghan, J. A. and Sarmiento, I. (2007) Distance hereditary graphs and the interlace polynomial. Combin. Probab. Comput. 16 947–973.CrossRefGoogle Scholar
[9]Isserlis, L. (1918) On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika 12 134–139.CrossRefGoogle Scholar
[10]Jaeger, F. (1988) On Tutte polynomials and cycles of plane graphs. J. Combin. Theory Ser. B 44 127–146.CrossRefGoogle Scholar
[11]Martin, P. (1977) Enumérations eulériennes dans les multigraphes et invariants de Tutte–Grothendieck. Thesis, Grenoble.Google Scholar
[12]Las Vergnas, M. (1979) On Eulerian partitions of graphs. Research Notes in Mathematics 34 62–75.Google Scholar
[13]Las Vergnas, M. (1988) On the evaluation at (3, 3) of the Tutte polynomial of a graph. J. Combin. Theory Ser. B 44 367–372.CrossRefGoogle Scholar
[14]Vertigan, D. (2006) The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput. 35 690–712.CrossRefGoogle Scholar
[15]Wenzl, H. (1988) On the structure of Brauer's centralizer algebras. Ann. of Math. 128 173–193.CrossRefGoogle Scholar
[16]Wick, G.-C. (1950) The evaluation of the collision matrix. Phys. Rev. 80 268–272.CrossRefGoogle Scholar