Counterexamples to the interpolating conjecture on partial-dual genus polynomials of ribbon graphs

Qi Yan
School of Mathematics
China University of Mining and Technology
P. R. China
Xian’an Jin¹¹1Corresponding author.
School of Mathematical Sciences
Xiamen University
P. R. China
Email:[email protected]; [email protected]

Abstract

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They showed that the partial-dual genus polynomial for an orientable ribbon graph is interpolating and gave an analogous conjecture: The partial-dual Euler-genus polynomial for any non-orientable ribbon graph is interpolating. In this paper, we first give some counterexamples to the conjecture. Then motivated by these counterexamples, we further find two infinite classes of counterexamples.

keywords:

Ribbon graph, partial-dual genus polynomial, conjecture, counterexample.

MSC:

05C10, 05C30, 05C31, 57M15

^†^†journal: European J. Combin.

1 Introduction

We assume that the readers are familiar with the basic knowledge of topological graph theory and in particular the ribbon graphs and partial duals, and we refer the readers to [1, 2, 3, 5]. Let $G$ be a ribbon graph and $A\subseteq E(G)$ . We denote by $G^{A}$ the partial dual of $G$ with respect to $A$ .

Gross, Mansour and Tucker [4] introduced the partial-dual orientable genus polynomials for orientable ribbon graphs and the partial-dual Euler genus polynomials for arbitrary ribbon graphs.

Definition 1.

[4] The partial-dual Euler genus polynomial of any ribbon graph $G$ is the generating function

{}^{\partial}\varepsilon_{G}(z)=\sum_{A\subseteq E(G)}z^{\varepsilon(G^{A})}

that enumerates partial duals by Euler genus. The partial-dual orientable genus polynomial of an orientable ribbon graph $G$ is the generating function

{}^{\partial}\Gamma_{G}(z)=\sum_{A\subseteq E(G)}z^{\gamma(G^{A})}

that enumerates partial duals by orientable genus.

They posed some research problems and made some conjectures. Conjecture 5.3 in their paper states that

Conjecture 2.

[4] (Interpolating). The partial-dual Euler-genus polynomial ${}^{\partial}\varepsilon_{G}(z)$ for any non-orientable ribbon graph $G$ is interpolating.

In this paper, we first give some counterexamples to Conjecture 2. Motivated by these counterexamples, we then find two infinite classes of counterexamples to the conjecture.

2 Some counterexamples

A bouquet is a ribbon graph having only one vertex. A signed rotation of a bouquet is a cyclic ordering of the half-edges at the vertex and if the edge is an untwisted loop, then we give the same sign $+$ to the corresponding two half-edges, and give the different signs (one $+$ , the other $-$ ) otherwise. The sign $+$ is always omitted. See Figure 1 for an example. Sometimes we will use the signed rotation to represent the bouquet itself. A signed rotation is called prime if it can not be cut into two parts such that the two half-edges of each edge belong to a single part. We shall only consider prime counterexamples.

Example 3.

Let $B$ be the bouquet with the signed rotation

(-1,-2,3,4,2,1,3,4)

as shown in Figure 1. We have ${}^{\partial}\varepsilon_{B}(z)=4z^{2}+12z^{4}$ (see Table 1 for details).

Refer to caption — Figure 1: The signed rotation of the bouquet is $(-1,-2,3,4,2,1,3,4)$ .

$A$	$\varepsilon(A)$	$\varepsilon(A^{c})$	$\varepsilon(B^{A})$
$\emptyset$	0	4	4
$\{1\}$	1	3	4
$\{2\}$	1	3	4
$\{3\}$	0	2	2
$\{4\}$	0	2	2
$\{1,2\}$	2	2	4
$\{1,3\}$	2	2	4
$\{1,4\}$	2	2	4
$\{2,3\}$	2	2	4
$\{2,4\}$	2	2	4
$\{3,4\}$	2	2	4
$\{1,2,3\}$	2	0	2
$\{1,2,4\}$	2	0	2
$\{1,3,4\}$	3	1	4
$\{2,3,4\}$	3	1	4
$\{1,2,3,4\}$	4	0	4

Table 1: Euler genera of all partial duals of

(-1,-2,3,4,2,1,3,4)

Example 3 is the first counterexample we found, and there are no counterexamples having fewer edges. We then found more counterexamples to Conjecture 2 as listed in Table 2 with the help of computer.

The signed rotation of $B$	${}^{\partial}\varepsilon_{B}(z)$
$(-1,2,3,4,5,1,4,5,2,3)$	$8z^{2}+16z^{4}+8z^{5}$
$(-1,-2,3,1,4,2,5,4,3,5)$	$2z+10z^{3}+8z^{4}+12z^{5}$
$(-1,2,3,2,4,5,6,1,5,6,3,4)$	$8z^{2}+32z^{4}+16z^{5}+8z^{6}$
$(-1,2,1,3,4,5,6,2,5,6,3,4)$	$16z^{3}+40z^{5}+8z^{6}$
$(-1,-2,3,1,4,2,5,4,3,6,5,6)$	$2z+14z^{3}+12z^{4}+28z^{5}+8z^{6}$
$(-1,-2,3,4,5,6,2,1,5,6,3,4)$	$8z^{2}+24z^{4}+32z^{6}$
$(-1,2,3,2,4,3,5,6,7,1,6,7,4,5)$	$8z^{2}+48z^{4}+16z^{5}+40z^{6}+16z^{7}$
$(-1,2,3,4,5,6,7,1,6,7,4,5,2,3)$	$16z^{2}+48z^{4}+48z^{6}+16z^{7}$
$(-1,2,1,3,4,3,5,6,7,2,6,7,4,5)$	$16z^{3}+80z^{5}+16z^{6}+16z^{7}$
$(-1,2,3,4,5,6,7,1,4,5,6,7,2,3)$	$32z^{4}+64z^{6}+32z^{7}$
$\cdots\cdots$	$\cdots\cdots$

Table 2: Other counterexamples to Conjecture 2.

3 Two infinite classes of counterexamples

In this section, motivated by examples in Table 2, we further give two infinite classes of counterexamples to Conjecture 2. The following lemma will be used.

Lemma 4.

[4] Let $B$ be a bouquet, and let $A\subseteq E(B)$ . Then

\varepsilon(B^{A})=\varepsilon(A)+\varepsilon(A^{c}).

In addition, a technique called band move in knot theory [6] will be used, that is, a deformation of the bouquet by sliding one of the two ends of a ribbon along the boundary of the bouquet over other ribbons. This move does not change the number of boundary components. See Figures 3 and 4.

3.1 Infinite class 1

For each $n\geq 1$ , let $B_{2n+1}$ be the bouquet with the signed rotation

(1,2,3,\cdots,2n,2n+1,-1,2n,2n+1,\cdots,2,3),

as shown in Figure 2.

Note that the edge $1$ is interlaced with all other edges and $2i,2i+1$ are interlaced with each other for $1\leq i\leq n$ . Let $A\subseteq E(B_{2n+1})$ and $1\leq i\leq n$ . If $\{2i,2i+1\}\subseteq A$ , we call $\{2i,2i+1\}$ double ribbons of $A$ . If $2i\in A$ but $2i+1\notin A$ (or $2i+1\in A$ but $2i\notin A$ ), we call $2i$ (or $2i+1$ ) a single ribbon of $A$ .

Lemma 5.

Let $A\subseteq E(B_{2n+1})$ and let $s(A)$ be the number of single ribbons of $A$ . Then

\displaystyle\varepsilon({B_{2n+1}}^{A})=\left\{\begin{array}[]{ll}2n+1,&\mbox{when}~{}s(A)=0;\\ 2n-2s(A)+2,&\mbox{when}~{}s(A)>0.\end{array}\right.

Proof.

First observe that $s(A^{c})=s(A)$ . We can assume that $1\in A$ and let $f(B)$ denote the number of boundary components of a bouquet $B$ .

If the maximum labelled edge of the signed rotation of $A^{c}$ appears as double ribbons, that is, $A^{c}=(P,2i,2i+1,2i,2i+1,Q)$ , where $P$ and $Q$ are strings, then $f(A^{c})=f(P,Q)$ . If the maximum labelled edge of the signed rotation of $A^{c}$ appears as a single ribbon, that is, $A^{c}=(P,2i,2i,Q)$ or $A^{c}=(P,2i+1,2i+1,Q)$ , then $f(A^{c})=f(P,Q)+1$ . Repeating the previous argument leads to $f(A^{c})=s(A^{c})+1=s(A)+1$ .

If the minimum labelled edge except 1 of the signed rotation of $A$ appears as a single ribbon, that is, $A=(1,2j,P,-1,Q,2j)$ (or $A=(1,2j+1,P,-1,Q,2j+1)$ ), then $f(A)=f(P,2j,1,2j,-1,Q)$ as shown in Figure 3.

Since both $P$ and $Q$ do not contain edge $1$ and $s(P,Q)=s(A)-1$ , it follows that

f(A)=f(P,Q)=s(P,Q)+1=s(A).

If the minimum labelled edge except 1 of the signed rotation of $A$ appears as double ribbons, that is, $A=(1,2j,2j+1,P,-1,Q,2j,2j+1)$ , then

f(A)=f(2j,2j+1,2j,2j+1,1,P,-1,Q)

as shown in Figure 4. If $s(A)=0$ , then

	$\displaystyle f(A)$	$\displaystyle=$	$\displaystyle f(2j,2j+1,2j,2j+1,1,P,-1,Q)$
		$\displaystyle=$	$\displaystyle f(1,P,-1,Q)=\cdots=f(1,-1)=1.$

Otherwise, $s(A)>0$ , then repeat the above process, we have $f(A)=s(A).$ Therefore,

\displaystyle f(A)=\left\{\begin{array}[]{ll}1,&\mbox{when}~{}s(A)=0;\\ s(A),&\mbox{when}~{}s(A)>0.\end{array}\right.

Since $\varepsilon({B_{2n+1}}^{A})=\varepsilon(A)+\varepsilon(A^{c})$ by Lemma 4 and

1-|A|+f(A)=2-\varepsilon(A),1-|A^{c}|+f(A^{c})=2-\varepsilon(A^{c})

by the Euler formulas, it follows that

	$\displaystyle\varepsilon({B_{2n+1}}^{A})$	$\displaystyle=$	$\displaystyle\|A\|+\|A^{c}\|-f(A)-f(A^{c})+2$
		$\displaystyle=$	$\displaystyle\left\{\begin{array}[]{ll}2n+1,&\mbox{when}~{}s(A)=0;\\ 2n-2s(A)+2,&\mbox{when}~{}s(A)>0.\end{array}\right.$

∎

Theorem 6.

The partial-dual Euler genus polynomial for $B_{2n+1}$ is given by the formula

{}^{\partial}\varepsilon_{B_{2n+1}}(z)=2^{n+1}z^{2n+1}+\sum_{s=1}^{n}2^{n+1}\dbinom{n}{s}z^{2n-2s+2}.

Proof.

By Lemma 5, we have the following two cases:

1.

$\varepsilon({B_{2n+1}}^{A})=2n+1$ if and only if $s(A)=0$ . Then we can choose $A$ in $2^{n+1}$ ways.
2.

$\varepsilon({B_{2n+1}}^{A})=2n-2s+2$ where $1\leq s\leq n$ if and only if $s(A)=s$ . Then we can choose $s$ single edges for the ribbon subset $A$ in $\dbinom{n}{s}2^{s}$ ways and then select the remaining double edges in $2^{n-s}$ ways, and $A$ may or may not contain the edge $1$ . Hence, we can choose $A$ in $2^{n+1}\dbinom{n}{s}$ ways.

We obtain the formula. ∎

Remark 7.

By Theorem 6, $B_{2n+1}$ is a counterexample for each $n\geq 2$ .

3.2 Infinite class 2

For each $n\geq 1$ , let $C_{2n+2}$ be the bouquet with the signed rotation

(1,2,3,4,\cdots,2n+1,2n+2,-2,-1,2n+1,2n+2,\cdots,3,4)

as shown in Figure 5.

Note that the edges $1,2$ are interlaced with all other edges but $1,2$ are not interlaced with each other and $2i+1,2i+2$ are interlaced with each other for $1\leq i\leq n$ . Let $A\subseteq E(C_{2n+2})$ and $1\leq i\leq n$ . If $\{2i+1,2i+2\}\subseteq A$ , we call $\{2i+1,2i+2\}$ double ribbons of $A$ . If $2i+1\in A$ but $2i+2\notin A$ (or $2i+2\in A$ but $2i+1\notin A$ ), we call $2i+1$ (or $2i+2$ ) a single ribbon of $A$ .

Lemma 8.

Let $A\subseteq E(C_{2n+2})$ and let $s(A)$ be the number of single ribbons of $A$ . Then $\varepsilon({C_{2n+2}}^{A})=$

\displaystyle\left\{\begin{array}[]{ll}2n+2,&\mbox{if one of 1, 2 is in}~{}A~{}\mbox{and the other is in}~{}A^{c}~{}\mbox{and}~{}s(A)=0;\\ 2n-2s(A)+4,&\mbox{if one of 1, 2 is in}~{}A~{}\mbox{and the other is in}~{}A^{c}~{}\mbox{and}~{}s(A)>0;\\ 2n-2s(A)+2,&\mbox{if 1, 2 are both in}~{}A~{}\mbox{or both in}~{}A^{c}.\end{array}\right.

Proof.

We know that $s(A)=s(A^{c})$ . If one of 1, 2 is in $A$ and the other is in $A^{c}$ , then, as in the proof of Lemma 5, we have

\displaystyle f(A)=f(A^{c})=\left\{\begin{array}[]{ll}1,&\mbox{when}~{}s(A)=0;\\ s(A),&\mbox{when}~{}s(A)>0.\end{array}\right.

If $1,2\in A$ , then $f(A^{c})=s(A)+1$ .

If the minimum labelled edge except 1, 2 of the signed rotation of $A$ appears as a single ribbon, that is, $A=(1,2,2j+1,P,-2,-1,Q,2j+1)$ (or $A=(1,2,2j+2,P,-2,-1,Q,2j+2)$ ), then

f(A)=f(P,2j+1,1,2,2j+1,-2,-1,Q).

Since both $P$ and $Q$ do not contain edges $1,2$ and $s(P,Q)=s(A)-1$ , it follows that

	$\displaystyle f(A)$	$\displaystyle=$	$\displaystyle f(P,Q)+f(2j+1,1,2,2j+1,-2,-1)-1$
		$\displaystyle=$	$\displaystyle f(P,Q)+1=(s(P,Q)+1)+1=s(A)+1.$

If the minimum labelled edge except 1, 2 of the signed rotation of $A$ appears as double ribbons, that is,

A=(1,2,2j+1,2j+2,P,-2,-1,Q,2j+1,2j+2),

then

f(A)=f(2j+1,2j+2,2j+1,2j+2,1,2,P,-2,-1,Q).

If $s(A)=0$ , then

	$\displaystyle f(A)$	$\displaystyle=$	$\displaystyle f(2j+1,2j+2,2j+1,2j+2,1,2,P,-2,-1,Q)$
		$\displaystyle=$	$\displaystyle f(1,2,P,-2,-1,Q)=\cdots=f(1,2,-2,-1)=1.$

Otherwise, $s(A)>0$ , then repeat the above process, we have $f(A)=s(A)+1.$ Therefore, we can see that $f(A)=s(A)+1$ for $0\leq s(A)\leq n.$

Since $\varepsilon({C_{2n+2}}^{A})=\varepsilon(A)+\varepsilon(A^{c})$ by Lemma 4 and

1-|A|+f(A)=2-\varepsilon(A),1-|A^{c}|+f(A^{c})=2-\varepsilon(A^{c}),

it follows that $\varepsilon({C_{2n+2}}^{A})=|A|+|A^{c}|-f(A)-f(A^{c})+2=$

\displaystyle\left\{\begin{array}[]{ll}2n+2,&\mbox{if one of 1, 2 is in}~{}A~{}\mbox{and the other is in}~{}A^{c}~{}\mbox{and}~{}s(A)=0;\\ 2n-2s(A)+4,&\mbox{if one of 1, 2 is in}~{}A~{}\mbox{and the other is in}~{}A^{c}~{}\mbox{and}~{}s(A)>0;\\ 2n-2s(A)+2,&\mbox{if 1, 2 are both in}~{}A~{}\mbox{or both in}~{}A^{c}.\end{array}\right.

∎

Theorem 9.

The partial-dual Euler genus polynomial for $C_{2n+2}$ is given by the formula

{}^{\partial}\varepsilon_{C_{2n+2}}(z)=2^{n+1}(n+2)z^{2n+2}+\sum_{s=2}^{n}2^{n+1}\left(\dbinom{n}{s}+\dbinom{n}{s-1}\right)z^{2n-2s+4}+2^{n+1}z^{2}.

Proof.

By Lemma 8, we have the following three cases:

1.

$\varepsilon({C_{2n+2}}^{A})=2n+2$ if and only if one of $1,2$ is in $A$ and the other is in $A^{c}$ and $A$ has no single ribbons (or only one single ribbon) or $1,2$ are both in $A$ or both in $A^{c}$ and $A$ has no single ribbons. Then we can choose $A$ in $2^{n+1}+2^{n+1}\dbinom{n}{1}+2^{n+1}=2^{n+1}(n+2)$ ways.
2.

$\varepsilon({C_{2n+2}}^{A})=2n-2s+4$ where $2\leq s\leq n$ if and only if one of $1,2$ is in $A$ and the other is in $A^{c}$ and $A$ has $s$ single ribbons or $1,2$ are both in $A$ or both in $A^{c}$ and $A$ has $s-1$ single ribbons. Then we can choose $A$ in $2^{n+1}\left(\dbinom{n}{s}+\dbinom{n}{s-1}\right)$ ways.
3.

$\varepsilon({C_{2n+2}}^{A})=2$ if and only if $1,2$ are both in $A$ or both in $A^{c}$ and $A$ has $n$ single ribbons. Then we can choose $A$ in $2^{n+1}$ ways.

∎

Remark 10.

By Theorem 9, $C_{2n+2}$ is a counterexample for each $n\geq 1$ . In particular, when $n=1$ , $C_{4}$ is exactly the bouquet in Example 3.

4 Acknowledgements

This work is supported by NSFC (Nos. 12171402, 12101600) and the Fundamental Research Funds for the Central Universities (Nos. 20720190062, 2021QN1037). We thank the referees sincerely for their valuable comments.

References

[1] B. Bollobás and O. Riordan, A polynomial of graphs on surfaces, Math. Ann. 323(1) (2002) 81–96.
[2] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, J. Combin. Theory Ser. B 99 (2009) 617–638.
[3] J. A. Ellis-Monaghan and I. Moffatt, Graphs on Surfaces, Springer New York, 2013.
[4] J. L. Gross, T. Mansour and T. W. Tucker, Partial duality for ribbon graphs, I: Distributions, European J. Combin. 86 (2020) 103084.
[5] J. L. Gross and T. W. Tucker, Topological Graph Theory, John Wiley & Sons, Inc. New York, 1987.
[6] C. Livingston, Knot Theory, The Mathematical Association of America, 1993.