{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T15:07:12Z","timestamp":1648998432761},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2011,10,11]],"date-time":"2011-10-11T00:00:00Z","timestamp":1318291200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>We present a simple graph integral equivalent to a multiple of the circuit partition polynomial. Let <jats:italic>G<\/jats:italic> be a directed graph, and let <jats:italic>k<\/jats:italic> be a positive integer. Associate with each vertex <jats:italic>v<\/jats:italic> of <jats:italic>G<\/jats:italic> an independent, uniformly random <jats:italic>k<\/jats:italic>-dimensional complex vector <jats:italic>x<\/jats:italic><jats:sub><jats:italic>v<\/jats:italic><\/jats:sub> of unit length. We define <jats:italic>q<\/jats:italic>(<jats:italic>G;k<\/jats:italic>) to be the expected value of the product, over all edges (<jats:italic>u, v<\/jats:italic>), of the inner product \u3008<jats:italic>x<\/jats:italic><jats:sub><jats:italic>u<\/jats:italic><\/jats:sub>, <jats:italic>x<\/jats:italic><jats:sub><jats:italic>v<\/jats:italic><\/jats:sub>\u3009. We show that <jats:italic>q<\/jats:italic>(<jats:italic>G;k<\/jats:italic>) is proportional to <jats:italic>G<\/jats:italic>'s cycle partition polynomial, and therefore that computing <jats:italic>q<\/jats:italic>(<jats:italic>G;k<\/jats:italic>) is #<jats:italic>P<\/jats:italic>-complete for any <jats:italic>k<\/jats:italic> &gt; 1. We also study the natural variants that arise when the <jats:italic>x<\/jats:italic><jats:sub><jats:italic>v<\/jats:italic><\/jats:sub> are real or drawn from the Gaussian distribution.<\/jats:p>","DOI":"10.1017\/s0963548311000393","type":"journal-article","created":{"date-parts":[[2011,10,11]],"date-time":"2011-10-11T03:51:28Z","timestamp":1318305088000},"page":"911-920","source":"Crossref","is-referenced-by-count":0,"title":["A Graph Integral Formulation of the Circuit Partition Polynomial"],"prefix":"10.1017","volume":"20","author":[{"given":"CRISTOPHER","family":"MOORE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER","family":"RUSSELL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,10,11]]},"reference":[{"key":"S0963548311000393_ref12","first-page":"62","article-title":"On Eulerian partitions of graphs","volume":"34","author":"Las Vergnas","year":"1979","journal-title":"Research Notes in Mathematics"},{"key":"S0963548311000393_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008723"},{"key":"S0963548311000393_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90079-2"},{"key":"S0963548311000393_ref11","unstructured":"[11] Martin P. (1977) Enum\u00e9rations eul\u00e9riennes dans les multigraphes et invariants de Tutte\u2013Grothendieck. Thesis, Grenoble."},{"key":"S0963548311000393_ref9","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/12.1-2.134"},{"key":"S0963548311000393_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90083-4"},{"key":"S0963548311000393_ref7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1853"},{"key":"S0963548311000393_ref5","doi-asserted-by":"publisher","DOI":"10.2307\/1968843"},{"key":"S0963548311000393_ref16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.80.268"},{"key":"S0963548311000393_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446797"},{"key":"S0963548311000393_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01787630"},{"key":"S0963548311000393_ref6","first-page":"259","volume-title":"Proc. 7th ALENEX and 2nd ANALCO: Vancouver","author":"Brightwell","year":"2005"},{"key":"S0963548311000393_ref2","article-title":"The circuit partition polynomial with applications and relation to the Tutte and interlace polynomials","volume":"8","author":"Austin","year":"2007","journal-title":"Rose-Hulman Undergraduate Mathematics J."},{"key":"S0963548311000393_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2102"},{"key":"S0963548311000393_ref15","doi-asserted-by":"publisher","DOI":"10.2307\/1971466"},{"key":"S0963548311000393_ref1","unstructured":"[1] Arratia R. , Bollob\u00e1s B. and Sorkin G. (2000) The interlace polynomial: A new graph polynomial. In Proc. 11th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 237\u2013245."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T23:41:05Z","timestamp":1556322065000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000393\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,11]]},"references-count":16,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["S0963548311000393"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000393","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,11]]}}}