ELibM Journals • ELibM Home • EMIS Home • EMIS Mirrors

  EMIS Electronic Library of Mathematics (ELibM)
The Open Access Repository of Mathematics
  EMIS ELibM Electronic Journals

JOURNAL OF
ALGEBRAIC
COMBINATORICS
  Editors-in-chief: C. A. Athanasiadis, T. Lam, A. Munemasa, H. Van Maldeghem
ISSN 0925-9899 (print) • ISSN 1572-9192 (electronic)
 

Planar flows and quadratic relations over semirings

Vladimir I. Danilov , Alexander V. Karzanov and Gleb A. Koshevoy
Central Institute of Economics and Mathematics of the RAS, 47, Nakhimovskii Prospect, 117418, Moscow, Russia

DOI: 10.1007/s10801-012-0344-6

Abstract

Adapting Lindström's well-known construction, we consider a wide class of functions which are generated by flows in a planar acyclic directed graph whose vertices (or edges) take weights in an arbitrary commutative semiring. We give a combinatorial description for the set of “universal” quadratic relations valid for such functions. Their specializations to particular semirings involve plenty of known quadratic relations for minors of matrices (e.g., Plücker relations) and the tropical counterparts of such relations. Also some applications and related topics are discussed.

Pages: 441–474

Keywords: plücker relation; dodgson condensation; tropicalization; semiring; planar graph; network flow; lindström's lemma; Schur function; Laurent phenomenon

Full Text: PDF

References

Akian, M., Gaubert, S., Guterman, A.: Linear independence over tropical semirings and beyond. In: Litvinov, G.L., Sergeev, S.N. (eds.) Tropical and Idempotent Mathematics. Contemporary Mathematics, vol. 495, pp. 1-38 (2009) CrossRef Berenstein, A., Fomin, S., Zelevinsky, A.: Parametrizations of canonical bases and totally positive matrices. Adv. Math. 122, 49-149 (1996) CrossRef Brenti, F.: Combinatorics and total positivity. J. Comb. Theory, Ser. A 71, 175-218 (1995) CrossRef Danilov, V., Karzanov, A., Koshevoy, G.: Tropical Plücker functions and their bases. In: Litvinov, G.L., Sergeev, S.N. (eds.) Tropical and Idempotent Mathematics. Contemporary Mathematics, vol. 495, pp. 127-158 (2009) CrossRef Danilov, V., Karzanov, A., Koshevoy, G.: Plücker environments, wiring and tiling diagrams, and weakly separated set-systems. Adv. Math. 224, 1-44 (2010) CrossRef Dodgson, C.L.: Condensation of determinants. Proc. R. Soc. Lond. 15, 150-155 (1866) CrossRef Fomin, S., Zelevinsky, A.: The Laurent phenomenon. Adv. Appl. Math. $28(2)$, 119-144 (2002) CrossRef Fulmek, M.: Bijective proofs for Schur function identities. arXiv:0909.5334v1 [math.CO] (2009) Fulmek, M., Kleber, M.: Bijective proofs for Schur function identities which imply Dodgson's condensation formula and Plücker relations. Electron. J. Comb. $8(1)$, 16 (2001) Fulton, W.: Young Tableaux. London Math. Soc. Student Text, vol.
35. Cambridge University Press, Cambridge (1997) Gessel, I.M., Viennot, X.: Determinants, paths, and plane partitions. Preprint (1989) Lindström, B.: On the vector representation of induced matroids. Bull. Lond. Math. Soc. 5, 85-90 (1973) CrossRef Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. Graduate Text in Mathematics, vol.
227. Springer, Berlin (2005) Postnikov, A.: Total positivity, Grassmannians, and networks. arXiv:math.CO/0609764 (2006) Talaska, K.: A formula for Plücker coordinates associated with a planar network. arXiv:0801.4822 [math.CO] (2008)



© 1992–2009 Journal of Algebraic Combinatorics
© 2012 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition