Characterizations of bipartite and Eulerian partial duals of orientable hypermaps
Yufan Han, Metrose Metsidik · 2026
Read Characterizations of bipartite and Eulerian partial duals of orientable hypermaps by Yufan Han, Metrose Metsidik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30071.txt.
Introduction
Yufan Han and Metrose Metsidik extend two classic graph results to hypermaps. Hypermaps generalize ribbon graphs, which encode surfaces with edges as ribbons. A partial dual flips only some edges of such a structure. Deng and colleagues characterized when partial duals are bipartite or Eulerian. Han and Metsidik prove the matching statements for orientable hypermaps.
They work in a two-permutation model of hypermaps. First they rewrite a known three-permutation formula in that model. Partial duality then acts cleanly: it preserves each hyperedge's support and length. It reverses only the cycles tied to selected hyperedges. Using the medial map, they link state circles to partial dual vertices. A partial dual is Eulerian exactly when every state circle has even length. Bipartite and Eulerian characterizations follow from crossing directions on the medial map. One new obstruction appears: bipartite cases force every hyperedge to have even length.
Catalog record
| CREATOR | Yufan Han, Metrose Metsidik |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30071
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Characterizations of bipartite and Eulerian partial duals of orientable hypermaps Yufan Han, Metrose Metsidik Abstract For ribbon graphs, Deng et al. established two classical characterizations: a partial dual is bipartite if and only if the dualizing set consists of all c c -edges induced by some all-crossing direction of the medial graph, and a partial dual is Eulerian if and only if the dualizing set consists of all d d -edges induced by some crossing-total direction, possibly together with some t t -edges. In this paper we extend both results to hypermaps in the ( σ , α ) (\sigma,\alpha) model, restricting attention to partial duality with respect to subsets of hyperedges. We first rewrite the Chmutov and Vignes-Tourneret’s three-permutation formula as an explicit hyperedge-partial-duality formula in the two-permutation model, and show that in this model partial duality acts exactly by preserving the support and length of every hyperedge while reversing the α \alpha -cycles corresponding to the selected hyperedges. Next, using the Cori and Hetyei’s construction of the medial map, we define for each hyperedge subset E ′ ⊆ E ( H ) E^{\prime}\subseteq E(H) a black/white smoothing state S E ′ S_{E^{\prime}} , and prove rigorously that the state circles of S E ′ S_{E^{\prime}} are in bijection with the vertices of the partial dual H E ′ H^{E^{\prime}} . Consequently, H E ′ H^{E^{\prime}} is Eulerian if and only if every state circle has even length. On this basis we prove the following two main theorems: H E ′ is Eulerian \displaystyle H^{E^{\prime}}\text{ is Eulerian} ⟺ ∃ a crossing-total direction Ω of M ( H ) \displaystyle\Longleftrightarrow\exists\text{ a crossing-total direction $\Omega$ of }M(H) such that E ′ = D ( Ω ) ∪ T ′ , T ′ ⊆ T ( Ω ) , \displaystyle\text{such that }E^{\prime}=D(\Omega)\cup T^{\prime},\quad T^{\prime}\subseteq T(\Omega), H E ′ is bipartite \displaystyle H^{E^{\prime}}\text{ is bipartite} ⟺ ∃ an all-crossing direction Φ of M ( H ) \displaystyle\Longleftrightarrow\exists\text{ an all-crossing direction $\Phi$ of }M(H) such that E ′ = C ( Φ ) . \displaystyle\text{such that }E^{\prime}=C(\Phi). Here D ( Ω ) D(\Omega) , T ( Ω ) T(\Omega) and C ( Φ ) C(\Phi) denote, respectively, the sets of all d d -type, t t -type and c c -type hyperedges. Unlike the ribbon-graph case, the hypermap setting exhibits a genuine new obstruction: if some hyperedge-partial dual is bipartite, then every hyperedge of the original hypermap must have even length. Keywords. hypermap; partial duality; medial map; state circle; bipartite; Eulerian 1 Introduction Let G be a ribbon graph and let A\subseteq E(G) . In the planar setting, Huggett and Moffatt first extended the classical correspondence between Eulerian graphs and bipartite geometric duals to partial duality, and obtained a medial-graph characterization of bipartite partial duals of plane graphs. Metsidik and Jin then characterized Eulerian partial duals of plane graphs. Deng, Jin and Metsidik subsequently generalized both results to arbitrary ribbon graphs and expressed them uniformly in terms of all-crossing and crossing-total directions of medial graphs [ 9 , 12 , 5 ] . These results show that global properties of partial duals can be completely controlled by local orientation data on the medial graph. A hypermap can be viewed as a hypergraph embedded in a surface; when every hyperedge has length 2 , it reduces to a ribbon graph. Classical combinatorial models for hypermaps go back to Cori, Walsh, Jones, and Singerman, Lando, and Zvonkin [ 3 , 13 , 10 , 11 ] . Chmutov and Vignes-Tourneret extended partial duality to general hypermaps and gave an explicit formula in the orientable three-permutation model [ 2 ] ; Cori and Hetyei, in their study of the Whitney polynomial of a hypermap, systematically employed a permutation-based construction of the medial map [ 4 ] . These works provide a natural technical foundation for the present paper. We restrict throughout to orientable hypermaps and consider only partial duality with respect to subsets of hyperedges. In this setting, the orientation of the underlying surface yields a canonical checkerboard coloring of the medial map, so the x/y -labeling according to whether the black face lies on the left or on the right of an oriented edge is well defined. Our main contributions can be summarized as follows: 1. We give a rigorous and unambiguous formula for hyperedge partial duality in the two-permutation (\sigma,\alpha) model. 2. We provide a complete proof of the correspondence “state circles \leftrightarrow vertices of a partial dual,” which is the common core of both main theorems. 3. We extend the crossing-total and all-crossing characterizations from ribbon graphs to the hypermap setting, where medial vertices may have arbitrary valence. 4. We isolate a hypermap-specific even-length obstruction: if some hyperedge-partial dual is bipartite, then every hyperedge of the original hypermap must have even length. We outline the structure of this paper in detail. In Section 2, we start with fundamental notations of orientable hypermaps under the two-permutation model, transform the existing three-permutation partial duality formula into a new form adapted for hyperedges, and discuss elementary properties of Eulerian and bipartite hypermaps. Section 3 is devoted to the permutation definition of medial maps, their checkerboard colorings, and the construction of states and state circles from smoothing operations. The key bijection linking state circles to vertices of partial duals is rigorously proved in Section 4. Based on this correspondence, Section 5 proves the characterization theorem for Eulerian partial duals with respect to crossing-total directions, while Section 6 addresses bipartite partial duals and all-crossing directions. Section 7 demonstrates all theoretical conclusions through a concrete hypermap example, and compares our results with the known results on ribbon graphs. We also explain why non-orientable hypermaps are not considered in this work. The appendix contains additional figures visualizing Eulerian and bipartite partial duals of the example hypermap. 2 Orientable hypermaps and hyperedge partial duality 2.1 The two-permutation (\sigma,\alpha) model Throughout the paper, permutations are composed from right to left. We adopt the permutation model used by Cori and Hetyei in [ 4 , §1.1] . Let D=[n]=\{1,2,\dots,n\} be a finite set of darts. A connected orientable hypermap is a pair of permutations H=(\sigma,\alpha)\in S_{n}\times S_{n}, acting transitively on D . It encodes a hypergraph embedded in an orientable surface without boundary: the cycles of \sigma correspond to vertices, the cycles of \alpha correspond to hyperedges, and the faces correspond to the cycles of the permutation \phi:=\alpha^{-1}\sigma. The degree of a vertex or a hyperedge is defined as the length of the corresponding cycle. For i\in D , let v(i) denote the \sigma -cycle containing i , and let e(i) denote the \alpha -cycle containing i . Definition 2.1 . Let H=(\sigma,\alpha) be an orientable hypermap. 1. Following Euler’s classical terminology for graphs of even degree [ 7 ] , we say that H is Eulerian if every cycle of \sigma has even length. 2. A hypermap is bipartite if its vertices admit a 2-coloring such that adjacent vertices receive distinct colors. Equivalently, H is bipartite iff its vertex-adjacency graph \Gamma(H) [ 1 ] is bipartite, where \Gamma(H) is the graph whose vertices are the vertices of H , and for