| Title:
|
Duality for pairs of upward bipolar plane graphs and submodule lattices (English) |
| Author:
|
Czédli, Gábor |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0011-4642 |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
151 |
| Issue:
|
3 |
| Year:
|
2026 |
| Pages:
|
427-448 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $G$ and $H$ be acyclic, upward bipolarly oriented plane graphs with the same number $n$ of edges. While $G$ can symbolize a flow network, $H$ has only a controlling role. Let $\phi $ and $\psi $ be bijections from $\{1,\dots ,n\}$ to the edge set of $G$ and that of $H$, respectively; their role is to define, for each edge of $H$, the corresponding edge of $G$. Let $b$ be an element of an Abelian group $\mathbb A$. An $n$-tuple $(a_1,\dots ,a_n)$ of elements of $\mathbb A$ is a solution of the paired-bipolar-graphs problem $P:=(G,H,\phi ,\psi ,\mathbb A, b)$ if whenever $a_i$ is the ``all-or-nothing-flow'' capacity of the edge $\phi (i)$ for $i=1,\dots , n$ and $\vec e$ is a maximal directed path of $H$, then by fully exploiting the capacities of the edges corresponding to the edges of $\vec e$ and neglecting the rest of the edges of $G$, we have a flow process transporting $b$ from the source (vertex) of $G$ to the sink of $G$. Let $P':=(H',G',\psi ',\phi ',\mathbb A, b)$, where $H'$ and $G'$ are the ``two-outer-facet'' duals of $H$ and $G$, respectively, and $\psi '$ and $\phi '$ are naturally defined. We prove that $P$ and $P'$ have the same solutions. This result implies George Hutchinson's self-duality theorem on submodule lattices. (English) |
| Keyword:
|
upward plane graph |
| Keyword:
|
edge capacity |
| Keyword:
|
George Hutchinson's self-duality theorem |
| Keyword:
|
lattice identity |
| MSC:
|
05C21 |
| MSC:
|
06C05 |
| DOI:
|
10.21136/MB.2025.0072-24 |
| . |
| Date available:
|
2026-08-24T07:52:11Z |
| Last updated:
|
2026-08-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/153716 |
| . |
| Reference:
|
[1] Auer, C., Bachmaier, C., Brandenburg, F. J., Gleissner, A., Hanauer, K.: Upward planar graphs and their duals.Theoret. Comput. Sci. 571 (2015), 36-49. Zbl 1312.68156, MR 3303953, 10.1016/j.tcs.2015.01.003 |
| Reference:
|
[2] Czédli, G.: A characterization for congruence semi-distributivity.Universal Algebra and Lattice Theory Lecture Notes in Mathematics 1004. Springer, Berlin (1983), 104-110. Zbl 0525.08006, MR 0716177, 10.1007/BFb0063432 |
| Reference:
|
[3] Czédli, G.: Mal'cev conditions for Horn sentences with congruence permutability.Acta Math. Hung. 44 (1984), 115-124. Zbl 0541.08005, MR 0759039, 10.1007/BF01974108 |
| Reference:
|
[4] Czédli, G.: Horn sentences in submodule lattices.Acta Sci. Math. 51 (1987), 17-33. Zbl 0635.08004, MR 0911555 |
| Reference:
|
[5] Czédli, G., Day, A.: Horn sentences with (W) and weak Mal'cev conditions.Algebra Univers. 19 (1984), 217-230. Zbl 0549.08003, MR 0758319, 10.1007/BF01190431 |
| Reference:
|
[6] Czédli, G., Takách, G.: On duality of submodule lattices.Discuss. Math., Gen. Algebra Appl. 20 (2000), 43-49. Zbl 0973.06008, MR 1782084, 10.7151/dmgaa.1004 |
| Reference:
|
[7] Battista, G. Di, Eades, P., Tamassia, R., Tollis, I. G.: Algorithms for drawing graphs: An annotated bibliography.Comput. Geom. 4 (1994), 235-282. Zbl 0804.68001, MR 1303232, 10.1016/0925-7721(94)00014-X |
| Reference:
|
[8] Hutchinson, G.: A duality principle for lattices and categories of modules.J. Pure Appl. Algebra 10 (1977), 115-119. Zbl 0366.18009, MR 0460416, 10.1016/0022-4049(77)90014-7 |
| Reference:
|
[9] Hutchinson, G., Czédli, G.: A test for identities satisfied in lattices of submodules.Algebra Univers. 8 (1978), 269-309. Zbl 0384.06009, MR 0469840, 10.1007/BF02485400 |
| Reference:
|
[10] Miller, G. L., Naor, J.: Flow in planar graphs with multiple sources and sinks.SIAM J. Comput. 24 (1995), 1002-1017. Zbl 0836.68087, MR 1350755, 10.1137/S0097539789162997 |
| Reference:
|
[11] Platt, C. R.: Planar lattices and planar graphs.J. Comb. Theory, Ser. B 21 (1976), 30-39. Zbl 0332.05103, MR 0429672, 10.1016/0095-8956(76)90024-1 |
| . |
