Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-11T09:10:25.070Z 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: [email protected])
ALEXANDER RUSSELL
Affiliation:
Department of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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