Contractors for flows

Garijo, Delia; Goodall, Andrew; Nešetřil, Jaroslav

doi:10.1090/S0002-9939-2012-11449-2

Contractors for flows
HTML articles powered by AMS MathViewer

by Delia Garijo, Andrew Goodall and Jaroslav Nešetřil

Proc. Amer. Math. Soc. 141 (2013), 1849-1861

DOI: https://doi.org/10.1090/S0002-9939-2012-11449-2

Published electronically: December 4, 2012

PDF | Request permission

Abstract:

We answer a question raised by Lovász and B. Szegedy [Contractors and connectors in graph algebras, J. Graph Theory 60:1 (2009)] asking for a contractor for the graph parameter counting the number of $B$-flows of a graph, where $B$ is a subset of a finite Abelian group closed under inverses. We prove our main result using the duality between flows and tensions and finite Fourier analysis.

References

Ilia Averbouch, Benny Godlin, and J. A. Makowsky, An extension of the bivariate chromatic polynomial, European J. Combin. 31 (2010), no. 1, 1–17. MR 2552585, DOI 10.1016/j.ejc.2009.05.006
Norman Biggs, Interaction models, London Mathematical Society Lecture Note Series, No. 30, Cambridge University Press, Cambridge-New York-Melbourne, 1977. Course given at Royal Holloway College, University of London, October–December 1976. MR 0674960, DOI 10.1017/CBO9780511662126
Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140
Matt DeVos, Jaroslav Ne et il, and André Raspaud, On edge-maps whose inverse preserves flows or tensions, Graph theory in Paris, Trends Math., Birkhäuser, Basel, 2007, pp. 109–138. MR 2279171, DOI 10.1007/978-3-7643-7400-6_{1}0
D. Garijo, A.J. Goodall and J. Nešetřil, On the number of $B$-flows of a graph, European J. Combin., to appear.
Pierre de la Harpe and François Jaeger, Chromatic invariants for finite graphs: theme and polynomial variations, Linear Algebra Appl. 226/228 (1995), 687–722. MR 1344593, DOI 10.1016/0024-3795(95)00248-P
Hamed Hatami and Serguei Norine, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc. 24 (2011), no. 2, 547–565. MR 2748400, DOI 10.1090/S0894-0347-2010-00687-X
W. Cary Huffman and Vera Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, 2003. MR 1996953, DOI 10.1017/CBO9780511807077
François Jaeger, Nowhere-zero flow problems, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 71–95. MR 1205397
László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
László Lovász and Balázs Szegedy, Contractors and connectors of graph algebras, J. Graph Theory 60 (2009), no. 1, 11–30. MR 2478356, DOI 10.1002/jgt.20343
Alexander Schrijver, Graph invariants in the spin model, J. Combin. Theory Ser. B 99 (2009), no. 2, 502–511. MR 2482968, DOI 10.1016/j.jctb.2008.10.003
Audrey Terras, Fourier analysis on finite groups and applications, London Mathematical Society Student Texts, vol. 43, Cambridge University Press, Cambridge, 1999. MR 1695775, DOI 10.1017/CBO9780511626265
B.L. van der Waerden, Die lange Reichweite der regelmässigen Atomanordnung in Mischkristallen, Z. Physik 118 (1941), 473–488.
Jay A. Wood, Duality for modules over finite rings and applications to coding theory, Amer. J. Math. 121 (1999), no. 3, 555–575. MR 1738408, DOI 10.1353/ajm.1999.0024