Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Contractors for flows


Authors: Delia Garijo, Andrew Goodall and Jaroslav Nešetřil
Journal: Proc. Amer. Math. Soc. 141 (2013), 1849-1861
MSC (2010): Primary 05C21, 05C25; Secondary 05C99
Published electronically: December 4, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. I. Averbouch, B. Godlin and J. Makowsky, An extension of the bivariate chromatic polynomial, European J. Combin. 31 (2010), 1-17. MR 2552585 (2011c:05162)
  • 2. N.L. Biggs, Interaction Models, London Mathematical Society Lecture Notes Series 30, Cambridge Univ. Press, Cambridge, 1977. MR 0674960 (58:32647)
  • 3. N.L. Biggs.
    Algebraic Graph Theory.
    Cambridge Univ. Press, 2nd ed., 1993. MR 1271140 (95h:05105)
  • 4. M. DeVos, J. Nešetřil, and A. Raspaud. On edge-maps whose inverse preserves flows or tensions. In: Graph Theory in Paris (Proceedings of a Conference in Memory of Claude Berge), Trends in Mathematics, pp. 109-138. Birkhäuser, Basel, 2007. MR 2279171 (2007m:05133)
  • 5. D. Garijo, A.J. Goodall and J. Nešetřil, On the number of $ B$-flows of a graph, European J. Combin., to appear.
  • 6. P. de la Harpe and F. Jaeger.
    Chromatic invariants for finite graphs: theme and polynomial variations.
    Linear Algebra Appl. 226-228 (1995), 687-722. MR 1344593 (96i:05065)
  • 7. H. Hatami and S. Norine, Undecidability of linear inequalities in graph homomorphism densities, J. Amer. Math. Soc. 24 (2011), 547-565. MR 2748400
  • 8. W.C. Huffman and V. Pless.
    Fundamentals of Error-Correcting Codes,
    Cambridge Univ. Press, Cambridge, 2003. MR 1996953 (2004k:94077)
  • 9. F. Jaeger, Nowhere-zero flow problems. In: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory 3, pp. 71-95. Academic Press, New York, 1988. MR 1205397
  • 10. L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96:6 (2006), 933-957. MR 2274085 (2007m:05132)
  • 11. L. Lovász and B. Szegedy, Contractors and connectors of graph algebras, J. Graph Theory 60:1 (2009), 11-30. MR 2478356 (2010a:05098)
  • 12. A. Schrijver, Graph invariants in the spin model, J. Combin. Theory Ser. B 99 (2009), 502-511. MR 2482968 (2010g:05228)
  • 13. A. Terras, Fourier analysis on finite groups and applications, London Math. Soc. Student Texts 43, Cambridge Univ. Press, Cambridge, 1999. MR 1695775 (2000d:11003)
  • 14. B.L. van der Waerden, Die lange Reichweite der regelmässigen Atomanordnung in
    Mischkristallen, Z. Physik 118 (1941), 473-488.
  • 15. J. Wood, Duality for modules over finite rings and applications to coding theory, Amer. J. Math. 121:3 (1999), 555-575. MR 1738408 (2001d:94033)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C21, 05C25, 05C99

Retrieve articles in all journals with MSC (2010): 05C21, 05C25, 05C99


Additional 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

DOI: http://dx.doi.org/10.1090/S0002-9939-2012-11449-2
PII: S 0002-9939(2012)11449-2
Keywords: Graph homomorphism, Fourier transform, contractor, flows, tensions
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
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.