Distributive lattices, polyhedra, and generalized flows. (English) Zbl 1205.06007
Summary: A \(D\)-polyhedron is a polyhedron \(P\) such that if \(x\), \(y\) are in \(P\) then so are their componentwise maxima and minima. In other words, the point set of a \(D\)-polyhedron forms a distributive lattice with the dominance order. We provide a full characterization of the bounding hyperplanes of \(D\)-polyhedra.
Apart from being a nice combination of geometric and order-theoretic concepts, \(D\)-polyhedra are a unifying generalization of several distributive lattices which arise from graphs. In fact, with a \(D\)-polyhedron we associate a directed graph with arc-parameters such that points in the polyhedron correspond to vertex potentials on the graph. Alternatively, an edge-based description of the points of a \(D\)-polyhedron can be given. In this model the points correspond to the duals of generalized flows, i.e., duals of flows with gains and losses.
These models can be specialized to yield distributive lattices that have been previously studied. Particular specializations are: flows of planar digraphs (Khuller, Naor and Klein), \(\alpha \)-orientations of planar graphs (Felsner), \(c\)-orientations (Propp) and \(\Delta \)-bonds of digraphs (Felsner and Knauer). As an additional application we identify a distributive lattice structure on the generalized flow of breakeven planar digraphs.
Apart from being a nice combination of geometric and order-theoretic concepts, \(D\)-polyhedra are a unifying generalization of several distributive lattices which arise from graphs. In fact, with a \(D\)-polyhedron we associate a directed graph with arc-parameters such that points in the polyhedron correspond to vertex potentials on the graph. Alternatively, an edge-based description of the points of a \(D\)-polyhedron can be given. In this model the points correspond to the duals of generalized flows, i.e., duals of flows with gains and losses.
These models can be specialized to yield distributive lattices that have been previously studied. Particular specializations are: flows of planar digraphs (Khuller, Naor and Klein), \(\alpha \)-orientations of planar graphs (Felsner), \(c\)-orientations (Propp) and \(\Delta \)-bonds of digraphs (Felsner and Knauer). As an additional application we identify a distributive lattice structure on the generalized flow of breakeven planar digraphs.
Keywords:
\(D\)-polyhedron; distributive lattice; dominance order; bounding hyperplanes; directed graph; vertex potentials; generalized flowsReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice Hall Inc.: Prentice Hall Inc. Englewood Cliffs, NJ · Zbl 1201.90001 |
| [2] | Birkhoff, G., Rings of sets, Duke Math. J., 3, 443-454 (1937) · Zbl 0017.19403 |
| [3] | Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M., (Oriented Matroids. Oriented Matroids, Encyclopedia of Mathematics and its Applications, vol. 46 (1993), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0773.52001 |
| [4] | E. Brehm, 3-orientations and Schnyder 3-tree-decompositions, Diplomarbeit, Freie Universität, Berlin, 2000.; E. Brehm, 3-orientations and Schnyder 3-tree-decompositions, Diplomarbeit, Freie Universität, Berlin, 2000. |
| [5] | Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103 |
| [6] | Davey, B.; Priestley, H., Introduction to Lattices and Order (1991), Cambridge University Press · Zbl 0701.06001 |
| [7] | P. de Mendez, Orientations bipolaires, Ph.D. Thesis, Paris, 1994.; P. de Mendez, Orientations bipolaires, Ph.D. Thesis, Paris, 1994. |
| [8] | Felsner, S., Lattice structures from planar graphs, Electron. J. Combin., 11 (2004), 24 pp. Research Paper 15 · Zbl 1056.05039 |
| [9] | Felsner, S.; Knauer, K. B., ULD-Lattices and \(\Delta \)-Bonds, Combinatorics, Probab. Comput., 18, 707-724 (2009) · Zbl 1194.06002 |
| [10] | Fleischer, L. K.; Wayne, K. D., Fast and simple approximation schemes for generalized flow, Math. Program., 91, 215-238 (2002) · Zbl 1049.90105 |
| [11] | Gilmer, P. M.; Litherland, R. A., The duality conjecture in formal knot theory, Osaka J. Math., 23, 229-247 (1986) · Zbl 0591.57001 |
| [12] | Giménez, O.; de Mier, A.; Noy, M., On the number of bases of bicircular matroids, Ann. Comb., 9, 35-45 (2005) · Zbl 1059.05030 |
| [13] | Giménez, O.; Noy, M., On the complexity of computing the Tutte polynomial of bicircular matroids, Combin. Probab. Comput., 15, 385-395 (2006) · Zbl 1094.05013 |
| [14] | Joswig, M.; Kulas, K., Tropical and ordinary convexity combined, Adv. Geom., 10, 333-352 (2010) · Zbl 1198.14060 |
| [15] | Khuller, S.; Naor, J.; Klein, P., The lattice structure of flow in planar graphs, SIAM J. Discrete Math., 6, 477-490 (1993) · Zbl 0782.90033 |
| [16] | Lam, P. C.B.; Zhang, H., A distributive lattice on the set of perfect matchings of a plane bipartite graph, Order, 20, 13-29 (2003) · Zbl 1025.05050 |
| [17] | Lam, T.; Postnikov, A., Alcoved polytopes. I, Discrete Comput. Geom., 38, 453-478 (2007) · Zbl 1134.52019 |
| [18] | J. Linde, C. Moore, M.G. Nordahl, An \(n\); J. Linde, C. Moore, M.G. Nordahl, An \(n\) |
| [19] | Matthews, L. R., Bicircular matroids, Quart. J. Math. Oxford Ser., 2, 28, 213-227 (1977) · Zbl 0386.05022 |
| [20] | McNulty, J.; Neudauer, N. A., On cocircuit covers of bicircular matroids, Discrete Math., 308, 4008-4013 (2008) · Zbl 1148.05022 |
| [21] | Oxley, J. G., Matroid Theory (1992), Oxford Science Publications: Oxford Science Publications New York, The Clarendon Press, Oxford University Press · Zbl 0784.05002 |
| [22] | J. Propp, Lattice structure for orientations of graphs, 1993 arXiv:math/0209005v1; J. Propp, Lattice structure for orientations of graphs, 1993 arXiv:math/0209005v1 |
| [23] | Rémila, E., The lattice structure of the set of domino tilings of a polygon, Theoret. Comput. Sci., 322, 409-422 (2004) · Zbl 1068.68157 |
| [24] | Schrijver, A., Theory of linear and integer programming, (Wiley-Interscience Series in Discrete Mathematics (1986), John Wiley & Sons Ltd: John Wiley & Sons Ltd Chichester), A Wiley-Interscience Publication · Zbl 0665.90063 |
| [25] | Simões Pereira, J. M.S., On subgraphs as matroid cells, Math. Z., 127, 315-322 (1972) · Zbl 0226.05016 |
| [26] | Stanley, R. P., Two poset polytopes, Discrete Comput. Geom., 1, 9-23 (1986) · Zbl 0595.52008 |
| [27] | Thurston, W. P., Conway’s tiling groups, Amer. Math. Monthly, 97, 757-773 (1990) · Zbl 0714.52007 |
| [28] | Truemper, K., On max flows with gains and pure min-cost flows, SIAM J. Appl. Math., 32, 450-456 (1977) · Zbl 0352.90069 |
| [29] | Ziegler, G., (Lectures on Polytopes. Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (1995), Springer-Verlag: Springer-Verlag New York) · Zbl 0823.52002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
