## 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

## Bibliographic Information

**Delia Garijo**- Affiliation: Department of Applied Mathematics I, University of Seville, Seville, Spain
- Email: dgarijo@us.es
**Andrew Goodall**- Affiliation: Department of Applied Mathematics (KAM) and Institute of Theoretical Computer Science (ITI), Charles University, Prague, Czech Republic
- Email: goodall.aj@gmail.com
**Jaroslav Nešetřil**- Affiliation: Department of Applied Mathematics (KAM) and Institute of Theoretical Computer Science (ITI), Charles University, Prague, Czech Republic
- Email: nesetril@kam.mff.cuni.cz
- Received by editor(s): January 13, 2011
- Received by editor(s) in revised form: September 15, 2011
- Published electronically: December 4, 2012
- Additional Notes: The first author’s research supported by projects O.R.I MTM2008-05866-C03-01 and PAI FQM-0164

The second and third authors’ research supported by ITI 1M0545 and the Centre for Discrete Mathematics, Theoretical Computer Science and Applications (DIMATIA) - Communicated by: Jim Haglund
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc.
**141**(2013), 1849-1861 - MSC (2010): Primary 05C21, 05C25; Secondary 05C99
- DOI: https://doi.org/10.1090/S0002-9939-2012-11449-2
- MathSciNet review: 3034412