Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.15989 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909229984514048 |
|---|---|
| author | Czédli, Gábor |
| author_facet | Czédli, Gábor |
| contents | 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 $ϕ$ and $ψ$ 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$, $ϕ,ψ$, $\mathbb A, b)$ if whenever $a_i$ is the ``all-or-nothing-flow'' capacity of the edge $ϕ(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'$, $ψ',ϕ'$, $\mathbb A, b)$, where $H'$ and $G'$ are the ``two-outer-facet'' duals of $H$ and $G$, respectively, and $ψ'$ and $ϕ'$ are defined naturally. We prove that $P$ and $P'$ have the same solutions. This result implies George Hutchinson's self-duality theorem on submodule lattices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15989 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Duality for pairs of upward bipolar plane graphs and submodule lattices Czédli, Gábor Combinatorics 06C05, 05C21 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 $ϕ$ and $ψ$ 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$, $ϕ,ψ$, $\mathbb A, b)$ if whenever $a_i$ is the ``all-or-nothing-flow'' capacity of the edge $ϕ(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'$, $ψ',ϕ'$, $\mathbb A, b)$, where $H'$ and $G'$ are the ``two-outer-facet'' duals of $H$ and $G$, respectively, and $ψ'$ and $ϕ'$ are defined naturally. We prove that $P$ and $P'$ have the same solutions. This result implies George Hutchinson's self-duality theorem on submodule lattices. |
| title | Duality for pairs of upward bipolar plane graphs and submodule lattices |
| topic | Combinatorics 06C05, 05C21 |
| url | https://arxiv.org/abs/2406.15989 |