#  SpecTra: Enhancing the Code Translation Ability of Language Models by
Generating Multi-Modal Specifications

Vikram Nitin
Department of Computer Science
Columbia University
New York, NY, USA
<EMAIL_ADDRESS>
&Baishakhi Ray
Department of Computer Science
Columbia University
New York, NY, USA
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

Large language models (LLMs) are increasingly being used for the task of
automated code translation, which has important real-world applications.
However, most existing approaches use only the source code of a program as an
input to an LLM, and do not consider the different kinds of specifications
that can be extracted from a program. In this paper, we propose SpecTra, a
multi-stage approach that uses a novel self-consistency filter to first
generate high-quality invariants, test cases, and natural language
descriptions from a given program, and then uses these along with the source
code to improve the quality of LLM-generated translations. We evaluate SpecTra
on two code translation tasks - C to Rust, and C to Go - and show that it can
enhance the performance of four popular LLMs on these tasks by up to 10
percentage points and a relative improvement of up to 23%. Our research
suggests that generating high-quality specifications could be a promising and
efficient way to improve the performance of LLMs for code translation.

##  1 Introduction

Code translation is the task of transforming code written in one programming
language to functionally identical code in another programming language. This
is an important task because new programming languages are frequently
developed to address the limitations of older languages. Code written in older
languages can be expensive to maintain, prone to security vulnerabilities, and
difficult to build upon. By some estimates Mims [2024], the “technical debt”
of maintaining legacy code costs the USA over a trillion dollars each year. So
there is an urgent need to translate legacy code into modern programming
languages.

Traditionally, translating code between languages has been accomplished with
transpilers Galois [2018], Feldman [1990]. These are rule-based systems that
use intricately designed algorithms and heuristics to produce code in the
target language that is guaranteed to be functionally identical to the code in
the source language. Although technically correct, this code is often non-
idiomatic, _i.e.,_ very different from typical human-written code. For
instance, it may have unusual control flow, use uninformative identifier
names, or call foreign functions from the original source language. This can
be hard to read and maintain, and often defeats the purpose of translating the
code in the first place.

Over the last few years, Large Language Models (LLMs) have been applied to
solve a variety of code-related tasks, including code generation, code
summarization, bug fixing, and test case generation Li et al. [2022], Ahmad et
al. [2022], Gao et al. [2023]. A growing body of research Roziere et al.
[2020], Ahmad et al. [2022], Roziere et al. [2021], Pan et al. [2024], Yang et
al. [2024] is dedicated to the problem of using LLMs to automatically
translate code from one language to another. In contrast to transpilers, LLMs
produce idiomatic but possibly incorrect translations.

In this paper, we propose SpecTra, an approach to enhance the code translation
ability of LLMs using multi-modal specifications. A program can be represented
through multiple modalities that are not just limited to its source code.
Static specifications, or invariants, express a relationship between the
inputs and outputs of a program that holds true for all inputs and outputs.
This is in contrast to dynamic specifications, or test cases, that correspond
to specific instances of inputs and outputs to the program. Static and dynamic
specifications are both representations of a program that can provide
additional information for downstream tasks like translation. Natural language
descriptions are also another representation of a program. These are usually
far less precise and have the potential for ambiguity, however, they too can
be used to augment the program with useful information. In the rest of this
paper, we will refer to static specifications as invariants, dynamic
specifications as tests, and natural language specifcations as descriptions.

Figure 1: Correct program specifications can improve program translation. This
is the output of gpt-4o on a C program from CodeNet Problem p03865, and will
serve as a running example throughout this paper.

Given an input program, SpecTra consists of two main steps. First, we use an
LLM to generate invariants, tests and descriptions, and validate them by
checking that they are consistent with the program. Next, we provide these
specifications one at a time to an LLM, along with the program’s source code,
and generate multiple candidate translations.

Validating test cases against the source code simply involves running the code
against the provided test case; however, validating invariants and
descriptions is non-trivial. To address this challenge, we propose a novel
approach based on self-consistency Min et al. [2023]. We prompt an LLM to re-
generate the source code given an invariant or description, and pick only
those invariants or descriptions from which the LLM is able to generate
correct source code.

We evaluate SpecTra on two code translation tasks - converting C to Rust, and
converting C to Rust. There is a lot of interest within the software
engineering community in converting between these pairs of languages Google
[2021a, b], and thus these tasks have direct real-world applicability. We find
that SpecTra is able to enhance the performance of 4 popular LLMs on these
tasks by up to 23% compared to a uni-modal baseline.

To summarize, our contributions are as follows:

  1. 1.

We propose a novel approach based on self-consistency to generate
specifications of a program in the form of invariants, test cases, and natural
language descriptions.

  2. 2.

We integrate these self-consistent specifications with the source code and
propose SpecTra, an approach that utilizes multi-modal specifications to
improve the quality of LLM-generated code translations.

  3. 3.

We evaluate SpecTra on two program translation tasks and four popular LLMs,
and show that SpecTra improves the performance of baseline models by up to 23%
(relative) and 10% (absolute).

##  2 Related Work

Figure 2: The first step of our approach involves generating multiple
candidate specifications from a given program. This is the actual output of
gpt-4o on our running example from Figure 1.

Our approach addresses the problem of code translation with LLMs, but also
draws on a long line of work on using LLMs for generating program
specifications.

###  2.1 Code Translation with LLMs

Roziere et al. [2020] proposed TransCoder, an early attempt to tackle code
translation using transformer models. They proposed Back Translation, a fully
unsupervised approach. Ahmad et al. [2022] refined Back Translation with the
addition of a code summarization task. In contrast to unsupervised learning,
supervised learning requires aligned parallel data across pairs of programming
languages, which is challenging to obtain at scale. Roziere et al. [2021]
address this challenge by generating synthetic aligned data using another
language model and filtering out incorrect translations using generated unit
tests. The last few years have seen the development of large foundation models
for code and natural language, that are pretrained on massive amounts of data
with an autoregressive objective function. These can perform a variety of
code-related tasks, including translation. Pan et al. [2024] and Yang et al.
[2024] perform thorough empirical evaluations of the translation ability of
these models.

###  2.2 Generating Program Specifications with LLMs

The three kinds of program specifications that we consider in this paper are
test cases, natural language descriptions, and invariants. There have been a
few recent papers that use LLMs to generate test cases for competitive coding
problems. EvalPlus Liu et al. [2023] uses ChatGPT to generate test cases, and
mutates them in order to rigorously test LLM-generated code solutions. CodeT
Chen et al. [2022] uses LLM-generated test cases to filter out code solutions
from a list of LLM-generated candidate solutions. Recently, Yang et al. [2024]
proposed to generate test cases, provide them along with the code to an LLM
for translation, and use test feedback to iteratively repair the generated
translation.

Separately, there has been a long line of work on using transformer models for
generating natural language descriptions of code Ahmad et al. [2022], Gao et
al. [2023], Gong et al. [2022], Gao and Lyu [2022], Wu et al. [2021], Tang et
al. [2021]. There has been comparatively less research into generating formal
invariants. Endres et al. [2023] transform natural language descriptions of
functions into assert statements and use these assertions to detect incorrect
code.

Parsel Zelikman et al. [2023] is a recent approach that generates and utilizes
multiple kinds of specifications. Starting with a problem description, Parsel
first generates a program sketch consisting of function-level descriptions and
test cases, and then generates code to complete the sketch.

##  3 Methodology

Figure 3: Filtering out incorrect specifications. We re-generate C code using
each specification, and pick the specifications corresponding to re-generated
C programs that pass the test case.

Suppose we have a program represented by $\mathcal{P}$, along with a test case
$(X,Y)$ such that $Y=\mathcal{P}(X)$, where $\mathcal{P}(X)$ denotes the
output of running $\mathcal{P}$ on input $X$. Assume that we have access to an
LLM $\mathcal{M}$, and multiple prompt-composing functions
$\\{\pi_{1},\pi_{2},...\\}$ that take programs and/or specifications and
create a text prompt using them.

At a high level, SpecTra has two main steps - generating high-quality multi-
model specifications, and using these specifications along with the code to
translate the program.

###  3.1 Generating Multi-Modal Specifications with Self-Consistency

The three types of specifications we generate are invariants, test cases, and
descriptions. In each case, we use an LLM to generate multiple candidates, and
pick a candidate that is consistent with the input program.

Generating Test Cases: We first use an LLM $\mathcal{M}$ to generate $k$
candidate test cases.

$(X^{\prime}_{1},Y^{\prime}_{1}),~{}...~{},~{}(X^{\prime}_{k},Y^{\prime}_{k})=\mathcal{M}~{}(~{}\pi_{\text{test-
gen}}(~{}\mathcal{P}~{})~{})$

Here $\pi_{\text{test-gen}}$ is a prompt-composing function takes a program
and creates a text prompt containing instructions to generate test inputs and
their corresponding outputs. Next, we pick the set $\mathbb{T}$ of tests that
are consistent with the source program.

$\mathbb{T}_{\mathcal{P}}=\\{(X^{\prime}_{i},Y^{\prime}_{i})~{}:~{}\mathcal{P}(X^{\prime}_{i})=Y^{\prime}_{i}\\}_{i=0}^{k}$

In practice, if we are unable to generate any consistent tests through this
approach, _i.e.,_ if $\mathbb{T}_{\mathcal{P}}=\phi$, then we augment it by
pairing each generated input with the actual program output, provided that the
program exits normally and doesn’t raise an error.

$\mathbb{T}_{\mathcal{P}}~{}:=~{}\mathbb{T}_{\mathcal{P}}~{}\cup~{}\\{~{}(X^{\prime}_{i},\mathcal{P}(X^{\prime}_{i}))~{}\\}_{i=0}^{k}$

Figure 4: Using different modalities of specifications to perform
specification-augmented translation. These are the actual prompts and
specifications generated by SpecTra.

Generating Invariants: First we use an LLM $\mathcal{M}$ to generate $k$
candidate invariants from the given program and test case.

$\mathcal{I}_{1},...,\mathcal{I}_{k}=\mathcal{M}~{}(~{}\pi_{\text{inv-
gen}}(~{}\mathcal{P},(X,Y)~{})~{})$

$\pi_{\text{inv-gen}}$ takes a program and test case, and creates a text
prompt containing instructions to generate an invariant. In the next step, we
use the same LLM to re-generate a program from each of the candidate
invariants.

$\mathcal{P}^{\prime}_{1},...,\mathcal{P}^{\prime}_{k}=\mathcal{M}~{}(~{}\pi_{\text{rev-
inv-
gen}}~{}(\mathcal{I}_{1})~{})~{},...~{},~{}\mathcal{M}~{}(~{}\pi_{\text{rev-
inv-gen}}~{}(\mathcal{I}_{k})~{})$

Here $\pi_{\text{rev-inv-gen}}$ takes an invariant and creates a text prompt
containing instructions to re-generate a source program. Finally, we pick a
set $\mathbb{I}_{\mathcal{P}}$ of invariants corresponding to re-generated
programs that pass the test case.

$\mathbb{I}_{\mathcal{P}}=\\{\mathcal{I}_{i}~{}:~{}\mathcal{P}^{\prime}_{i}(X)=Y\\}_{i=0}^{k}$

Generating Descriptions: Generating descriptions follows a similar process to
generating invariants, except that we use different prompt-composing functions
$\pi_{\text{desc-gen}}$ and $\pi_{\text{rev-desc-gen}}$.

$\mathcal{D}_{1},...,\mathcal{D}_{k}=\mathcal{M}~{}(~{}\pi_{\text{desc-
gen}}(~{}\mathcal{P},(X,Y)~{})~{})$
$\mathcal{P}^{\prime}_{1},...,\mathcal{P}^{\prime}_{k}=\mathcal{M}~{}(~{}\pi_{\text{rev-
desc-
gen}}~{}(\mathcal{D}_{1})~{})~{},...~{},~{}\mathcal{M}~{}(~{}\pi_{\text{rev-
desc-gen}}~{}(\mathcal{D}_{k})~{})$
$\mathbb{D}_{\mathcal{P}}=\\{\mathcal{D}_{i}~{}:~{}\mathcal{P}^{\prime}_{i}(X)=Y\\}_{i=0}^{k}$

While generating invariants and descriptions, we take the help of the provided
test cases; however our approach can also be extended to a setting where test
cases are not provided, by using the test cases that we generated in the first
step, in place of the provided tests. We defer this analysis to future work.

###  3.2 Specification-Augmented Translation

We now have three modes of specifications - invariants
$\mathbb{I}_{\mathcal{P}}$, test cases $\mathbb{T}_{\mathcal{P}}$ and
descriptions $\mathbb{D}_{\mathcal{P}}$ \- that are all consistent with the
source program $\mathcal{P}$. For each program, we pick one random
specification of each type, if there is at least one. Assume that we pick
$\mathcal{I}_{\mathcal{P}}$, $\mathcal{T}_{\mathcal{P}}$, and
$\mathcal{D}_{\mathcal{P}}$ from $\mathbb{I}_{\mathcal{P}}$,
$\mathbb{T}_{\mathcal{P}}$, and $\mathbb{D}_{\mathcal{P}}$ respectively. We
then use these specifications one at a time along with $\mathcal{P}$ to
translate $\mathcal{P}$ using an LLM. The vanilla translation without
specifications is given by

$\mathcal{P}_{\text{trans}}=\mathcal{M}~{}(~{}\pi_{\text{trans}}~{}(~{}\mathcal{P}~{})~{})$

where $\pi_{\text{trans}}$ creates a text prompt with an instruction to
translate the given program. For each type of specification, we create a
hybrid prompt containing both program and specification, and ask the LLM to
pay attention to the specification during generation.

$\displaystyle\mathcal{P}^{\mathcal{I}}_{\text{trans}}$
$\displaystyle=\mathcal{M}~{}(~{}\pi_{\text{inv-
trans}}~{}(~{}\mathcal{P},\mathcal{I}_{\mathcal{P}}~{})~{})$
$\displaystyle\mathcal{P}^{\mathcal{T}}_{\text{trans}}$
$\displaystyle=\mathcal{M}~{}(~{}\pi_{\text{test-
trans}}~{}(~{}\mathcal{P},\mathcal{T}_{\mathcal{P}}~{})~{})$
$\displaystyle\mathcal{P}^{\mathcal{D}}_{\text{trans}}$
$\displaystyle=\mathcal{M}~{}(~{}\pi_{\text{desc-
trans}}~{}(~{}\mathcal{P},\mathcal{D}_{\mathcal{P}}~{})~{})$

Here, $\pi_{\text{inv-trans}}$, $\pi_{\text{test-trans}}$, and
$\pi_{\text{desc-trans}}$ are functions that create a text prompt with an
instruction to translate the given program, aided by the given specification.
Examples of these three types of prompts are shown in Figure 4.

Given a program $\mathcal{P}$, we generate an ordered list of candidate
translations
$\left[\mathcal{P}^{\mathcal{I}}_{\text{trans}},\mathcal{P}^{\mathcal{T}}_{\text{trans}},\mathcal{P}^{\mathcal{D}}_{\text{trans}},\mathcal{P}_{\text{trans}}\right]$.
If we were unable to generate any of
$\mathcal{I}_{\mathcal{P}},\mathcal{T}_{\mathcal{P}}$ and
$\mathcal{D}_{\mathcal{P}}$, then we omit the corresponding translation from
the list of candidates. So we have between one and four candidate translations
for each program.

We hypothesize that the best translations are obtained using the most precise
and complete specifications, which is why we use the invariants first,
followed by the test cases, followed by the descriptions. Finally, we try a
vanilla translation with no specifications, which is, in theory, the least
likely to succeed. This conceptually corresponds to a pipeline, where we first
try translation with one kind of specification, and if it doesn’t work, move
on to another kind of specification, and so on.

##  4 Experimental Setup

Figure 5: A box plot of the number of attempts needed by gpt-4o to generate a successful specification, for the three types of specifications. |  | Invariants | Tests | Descriptions
---|---|---|---|---
| Programs with spec | 164 | 293 | 121
C to Rust | Without using spec | 106 (64.6%) | 158 (53.9%) | 75 (62%)
With spec | 109 (66.5%) | 180 (61.4%) | 76 (62.8%)
C to Go | Without using spec | 116 (70.7%) | 178 (60.6%) | 85 (70.2%)
With spec | 118 (72%) | 190 (64.8%) | 86 (71.1%)
Table 1: Effect of Individual Specification Modalities. All results are with
gpt-4o.

Datasets: We evaluate our approach on a subset of the CodeNet dataset Puri et
al. [2021]. CodeNet contains 4053 competitive coding problems, and over 13
million code submissions in a variety of languages including C. We filter out
the problems which either don’t have test cases, or don’t have a correct
solution in C, and select 300 random problems from the remaining ones. We pick
one random correct C solution from each of these problems. These 300 unique
problems and solutions comprise our evaluation dataset.

Models: We evaluate on 4 popular LLMs - gpt-4o and gpt-3.5-turbo from OpenAI,
claude-3-opus from Anthropic, and gemini-1.0-pro from Google. For all these
models, we run our experiments against a fixed checkpoint so that our results
don’t vary with new model releases. To generate multiple candidate
specifications, we use a temperature of 0.6. To generate a single candidate
translation, we use greedy decoding with temperature 0, and if we need
multiple candidate translations, we use a temperature of 0.3.

Evaluation: We compile each program into an executable, and run the executable
with the provided test input. If the output matches the provided test output,
then we mark this as correct. If the program doesn’t compile, or exits with an
error code, or if the output doesn’t match, then we mark this as incorrect. To
evaluate translations, we use the standard pass@k metric for
$k\in\\{1,2,3,4\\}$. Since our approach generates up to 4 candidate
translations in a specific order, we evaluate pass@k for the first $k$
translations in that same order. For example, for evaluating pass@2, we check
if the first or second candidate translations are correct, and so on.

##  5 Results

Figure 6: Venn Diagram showing the individual contributions of each
specification modality. The numbers indicate the number of successful
translations using that modality alone. All results are with gpt-4o for
translating C to Rust.

###  5.1 Evaluating the Generated Specifications

We would like to determine whether our specification generation process is
able to generate high-quality self-consistent specifications. To do this, we
check how many programs in our benchmark dataset we are able to generate self-
consistent specifications for. For each program, we generate up to $k=10$
candidate tests, and up to $k=6$ candidate invariants and descriptions. In all
the cases, we stop as soon as we find a self-consistent specification. We use
gpt-4o as our LLM for both the “forward” specification generation as well as
the “reverse” code generation process.

(a) gpt-4o, C to Rust

(b) claude-3-opus, C to Rust

(c) gpt-4o, C to Go

(d) claude-3-opus, C to Go

Figure 7: Pass@k for SpecTra versus a baseline, for multiple models and
language pairs. For the results with gpt-3.5-turbo and gemini-1.0-pro, please
see the Supplementary Material.

We find that gpt-4o is able to generate self-consistent invariants for 54.6%
of the solutions, self-consistent test cases for 97.7%, and self-consistent
descriptions for 40.3%. A box plot of the number of attempts needed to
generate a successful specification is shown in Figure 5

The average test coverage is 91.5%, which is an indicator that the tests are
of high quality. For the generated descriptions and invariants, the fact that
we are able to recover a functioning program from most of them is a strong
validation of their quality. We also manually inspected several of them and
confirmed that they are a good representation of the program’s behavior.
Examples of our generated specifications are shown in Figure 4.

###  5.2 Using these Specifications for Translation

Individual Modalities: First, we evaluate the efficacy of each specification
modality individually. We use gpt-4o as our translation model, and evaluate
$\mathcal{P}^{\mathcal{I}}_{\text{trans}}$ for all the programs $\mathcal{P}$
for which we are able to generate an invariant $\mathcal{I}_{\mathcal{P}}$. We
compare this with the performance of $\mathcal{P}_{\text{trans}}$ for those
same programs, again using gpt-4o. We repeat the same process for
$\mathcal{P}^{\mathcal{T}}_{\text{trans}}$ and
$\mathcal{P}^{\mathcal{D}}_{\text{trans}}$.

The results are shown in Table 1. We can see that each mode of specification
improves translation quality against the baseline, for both Rust and Go.

Our hypothesis was that different modalities would act in a complementary
fashion, whereby each modality might provide some extra information for
translation that the other modalities do not provide. To investigate this, we
plot a Venn Diagram in Figure 6 and visualize the contributions of each
individual specification modality. Although there is some overlap, the
different modalities are definitely complementary to a large extent.

Multiple Modalities: Our approach generates up to 4 ordered candidate
translations,
$\left[\mathcal{P}^{\mathcal{I}}_{\text{trans}},\mathcal{P}^{\mathcal{T}}_{\text{trans}},\mathcal{P}^{\mathcal{D}}_{\text{trans}},\mathcal{P}_{\text{trans}}\right]$,
for each program. We evaluate pass@k for $k\in\\{1,2,3,4\\}$ by checking if
any of the $k$ candidate translations are correct for each problem. Even if we
have less than $k$ candidates for a certain problem, we still check only the
candidates that we have. For the baseline, we generate 4 different options for
$\mathcal{P}_{\text{trans}}$ using a temperature of 0.3.

The results for gpt-4o and claude-3-opus are shown in Figure 7(d), and the
results for gemini-1.0-pro and gpt-3.5-turbo are in the Supplementary
Material. We can see that SpecTra outperforms the baseline pass@k rate except
on claude-3-opus C to Go translation. This is probably because of two reasons.
One, claude-3-opus is the best performing model out of the four LLMs for C to
Go translation, and so there is less room for improvement. Two, we are using
specifications generated by gpt-4o, and there may be some misalignment between
the two models as regards the kinds of specifications that they can use.

The largest absolute gain is on pass@2 for C to Rust translation with gpt-4o,
an increase of 10 percentage points from 57.6% to 67.6%. As expected, the
largest gains of SpecTra across all models and languages are with pass@1 and
pass@2, because those are calculated for candidates that use the best
specifications. On the other hand, the gains taper off for pass@3 and pass@4,
firstly because we don’t have up to 4 specifications for several programs, and
secondly because the last two candidates generated using descriptions and no
specifications respectively, add the least amount of extra information to aid
the LLM in performing translation.

The largest relative gain is on pass@1 with gemini-1.0-pro, a relative
increase of 23%. We highlight this in Table 2. We hypothesize that this is due
to the large gap in performance between these two models. High-quality
specifications generated using a well-performing model such as gpt-4o seem to
produce the largest relative improvement when used with inferior models. This
is in contrast to the relatively small improvement seen with claude-3-opus,
which is a well-performing model. Although there is still a large gap in
performance between gpt-4o and gemini-1.0-pro even with specifications, this
points to a promising and efficient way to improve the performance of LLMs
like gemini-1.0-pro at inference time with a one-time investment in generating
high-quality specifications.

Translation Model | Spec gen Model | pass@1 | pass@2 | pass@3 | pass@4
---|---|---|---|---|---
gemini-1.0-pro | None | 14.5% | 17.8% | 19.2% | 20.5%
gemini-1.0-pro | gpt-4o | 17.8% | 21.5% | 22.9% | 23.6%
Relative Improvement | 23.2% | 20.7% | 19.3% | 14.7%
gpt-4o | None | 53% | 57.7% | 61% | 64%
Table 2: High-quality specifications generated using a well-performing model
such as gpt-4o seem to produce the largest relative improvement when used with
inferior models like gemini-1.0-pro.

##  6 Conclusion

In this paper, we have presented SpecTra, an approach to 1) generate self-
consistent multi-modal specifications, and 2) use these specifications to
improve the program translation performance of large language models. We show
relative performance gains of up to 23% across multiple models and languages
pairs. Our results indicate the possibility for further research into
generating high-quality program specifications as a cheap and efficient way to
improve the performance of real-world LLMs on code translation. We see a few
concrete directions for future work. One limitation of our approach for
generating invariants is that these invariants are in natural language and
cannot be precisely validated against the source program. Future work could
explore generating invariants in formal language or assert statements, which
can then be automatically cross-verified against the source code. Another
promising direction is to use these specifications for downstream tasks other
than translation.

## References

  * Ahmad et al. [2022] Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang.  Summarize and generate to back-translate: Unsupervised translation of programming languages.  _arXiv preprint arXiv:2205.11116_ , 2022.
  * Chen et al. [2022] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen.  Codet: Code generation with generated tests.  _arXiv preprint arXiv:2207.10397_ , 2022.
  * Endres et al. [2023] Madeline Endres, Sarah Fakhoury, Saikat Chakraborty, and Shuvendu K Lahiri.  Formalizing natural language intent into program specifications via large language models.  _arXiv preprint arXiv:2310.01831_ , 2023.
  * Feldman [1990] Stuart I Feldman.  A fortran to c converter.  In _ACM SIGPLAN Fortran Forum_ , volume 9, pages 21–22. ACM New York, NY, USA, 1990.
  * Galois [2018] Galois.  C2Rust, 08 2018.  URL https://galois.com/blog/2018/08/c2rust/.
  * Gao et al. [2023] Shuzheng Gao, Cuiyun Gao, Yulan He, Jichuan Zeng, Lunyiu Nie, Xin Xia, and Michael Lyu.  Code structure–guided transformer for source code summarization.  _ACM Transactions on Software Engineering and Methodology_ , 32(1):1–32, 2023.
  * Gao and Lyu [2022] Yuexiu Gao and Chen Lyu.  M2ts: Multi-scale multi-modal approach based on transformer for source code summarization.  In _Proceedings of the 30th IEEE/ACM International Conference on Program Comprehension_ , pages 24–35, 2022.
  * Gong et al. [2022] Zi Gong, Cuiyun Gao, Yasheng Wang, Wenchao Gu, Yun Peng, and Zenglin Xu.  Source code summarization with structural relative position guided transformer.  In _2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)_ , pages 13–24. IEEE, 2022.
  * Google [2021a] Google.  Rust in the Android platform, 4 2021a.  URL https://security.googleblog.com/2021/04/rust-in-android-platform.html.
  * Google [2021b] Google.  Rust in the Linux kernel, 4 2021b.  URL https://security.googleblog.com/2021/04/rust-in-linux-kernel.html.
  * Li et al. [2022] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al.  Competition-level code generation with alphacode.  _Science_ , 378(6624):1092–1097, 2022.
  * Liu et al. [2023] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and LINGMING ZHANG.  Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation.  In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 21558–21572. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/43e9d647ccd3e4b7b5baab53f0368686-Paper-Conference.pdf.
  * Mims [2024] Christopher Mims.  The invisible $1.52 trillion problem: Clunky old software.  _The Wall Street Journal_ , March 2024.  URL https://www.wsj.com/tech/personal-tech/the-invisible-1-52-trillion-problem-clunky-old-software-f5cbba27.
  * Min et al. [2023] Marcus J Min, Yangruibo Ding, Luca Buratti, Saurabh Pujar, Gail Kaiser, Suman Jana, and Baishakhi Ray.  Beyond accuracy: Evaluating self-consistency of code large language models with identitychain.  _arXiv preprint arXiv:2310.14053_ , 2023.
  * Pan et al. [2024] Rangeet Pan, Ali Reza Ibrahimzada, Rahul Krishna, Divya Sankar, Lambert Pouguem Wassi, Michele Merler, Boris Sobolev, Raju Pavuluri, Saurabh Sinha, and Reyhaneh Jabbarvand.  Lost in translation: A study of bugs introduced by large language models while translating code.  In _Proceedings of the IEEE/ACM 46th International Conference on Software Engineering_ , pages 1–13, 2024.
  * Puri et al. [2021] Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladimir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, et al.  Codenet: A large-scale ai for code dataset for learning a diversity of coding tasks.  _arXiv preprint arXiv:2105.12655_ , 2021.
  * Roziere et al. [2020] Baptiste Roziere, Marie-Anne Lachaux, Lowik Chanussot, and Guillaume Lample.  Unsupervised translation of programming languages.  _Advances in neural information processing systems_ , 33:20601–20611, 2020.
  * Roziere et al. [2021] Baptiste Roziere, Jie M Zhang, Francois Charton, Mark Harman, Gabriel Synnaeve, and Guillaume Lample.  Leveraging automated unit tests for unsupervised code translation.  _arXiv preprint arXiv:2110.06773_ , 2021.
  * Tang et al. [2021] Ze Tang, Chuanyi Li, Jidong Ge, Xiaoyu Shen, Zheling Zhu, and Bin Luo.  Ast-transformer: Encoding abstract syntax trees efficiently for code summarization.  In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , pages 1193–1195. IEEE, 2021.
  * Wu et al. [2021] Hongqiu Wu, Hai Zhao, and Min Zhang.  Code summarization with structure-induced transformer.  In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1078–1090, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.93.  URL https://aclanthology.org/2021.findings-acl.93.
  * Yang et al. [2024] Zhen Yang, Fang Liu, Zhongxing Yu, Jacky Wai Keung, Jia Li, Shuo Liu, Yifan Hong, Xiaoxue Ma, Zhi Jin, and Ge Li.  Exploring and unleashing the power of large language models in automated code translation.  _arXiv preprint arXiv:2404.14646_ , 2024.
  * Zelikman et al. [2023] Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber.  Parsel: Algorithmic reasoning with language models by composing decompositions.  _Advances in Neural Information Processing Systems_ , 36:31466–31523, 2023.

##  Appendix A Pass@k for Other Models

(a) gpt-3.5-turbo, C to Rust

(b) gpt-3.5-turbo, C to Go

(c) gemini-1.0-pro, C to Rust

(d) gemini-1.0-pro, C to Go

Figure 8: Pass@k for SpecTra versus a baseline

##  Appendix B Error Type Analysis:

Figure 9: Distribution of Error Types for gpt-4o C to Rust translation.


Components of domino tilings under flips in toroidal grids111This work is
supported by NSFC (Grant No. 12271229).
Qianqian Liu, Yaxian Zhang, Heping Zhang222The corresponding author.
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu
730000,

P. R. China

Abstract: In a region $R$ consisting of unit squares, a (domino) tiling is a
collection of dominoes (the union of two adjacent squares) which pave fully
the region. The flip graph of $R$ is defined on the set of all tilings of $R$
where two tilings are adjacent if we change one from the other by a flip (a
$90^{\circ}$ rotation of a pair of side-by-side dominoes). Let $n\geq 1$ and
$m\geq 2$ be integers. In a recent paper it was proved that the flip graph of
$(2n+1)\times 2m$ quadriculated torus consists of two isomorphic components.
In this paper, we generalize the result to the toroidal grid $T(2n+1,2m,2r)$
which is obtained from an $(2n+1)\times 2m$ chessboard by sticking the left
and right sides and then identifying the top and bottom sides with a torsion
$2r$ squares for $1\leq r\leq m$. For a tiling $t$, we associate an integer
called forcing number as the minimum number of dominoes in $t$ that is
contained in no other tiling. As an application, we obtain that the forcing
numbers of all tilings of $T(2n+1,2m,2r)$ form an integer-interval. Moreover,
we prove that the maximum value of the interval is $\frac{m(2n+1)}{2}$ if
$\frac{m}{(r,m)}$ is even, and $\frac{m(2n+1)+(r,m)}{2}$ otherwise.

Keywords: Domino tiling; Flip; Perfect matching; Resonance graph; Forcing
number

##  1 Introduction

In a quadriculated region $R$ consisting of unit squares with vertices in
$\mathbb{Z}^{2}$, a _domino_ (or _dimer_) is the union of two adjacent
squares, and a (_domino_) _tiling_ is a covering of $R$ by dominoes with
disjoint interiors. In another language, $R$ can be transformed into a graph
$D(R)$ called _inner dual_ of $R$: vertices of $D(R)$ are unit squares in $R$
and two vertices are adjacent if their corresponding squares have an edge in
common. Then a domino of $R$ corresponds to an edge of $D(R)$ and a tiling
corresponds to a perfect matching of $D(R)$.

A classical model is to determine the number of ways of an $m\times n$
chessboard ($mn$ even) can be covered by dimers, known as _dimer problem_ [9],
which has important applications in both statistical mechanics and physical
system. In other words, dimer problem is to compute the number of perfect
matchings in its inner dual. For rectangle lattices, the dimer problem was
solved independently by Fisher [4], Kasteleyn [9], Temperley and Fisher [20].
Further, Cohn et al. [3] studied domino tilings of simply-connected regions of
arbitrary shape on the plane by a variational method. Especially, Thurston
[22] produced a necessary and sufficient condition for a simply connected
region in the plane to be tileable by dominoes. There are also some results of
dimer problem for 3-dimensional lattices [17, 18, 15, 13].

Given a tiling of a region $R$, a _flip_ is a local move: lifting two parallel
dominoes and then placing them back in a unique different position. Define the
_flip graph_ $\mathcal{T}(R)$ on the set of all tilings of $R$ where two
tilings are adjacent if we convert one from another by a flip. If $R$ is
simply connected, then $\mathcal{T}(R)$ is connected [22]. However, the result
is not necessarily hold for other regions. Liu et al. [14] obtained that the
flip graph of the $(2n+1)\times 2m$ quadriculated torus is disconnected and
consists of two isomorphic components. Saldanha et al. [19] obtained a
criterion for two tilings to belong to the same component of the flip graph.
In a 3-dimensional lattice, a domino is defined as a pair of adjacent unit
cubes. Freire et al. [6] characterized components of the flip graph of a
3-dimensional cubiculated region and torus using two topological invariants.

For a tiling $t$ of $R$, we associate it an integer called _forcing number_ ,
as the minimum number of dominoes in $t$ that is contained in no other tiling.
Liu et al. [14] obtained that forcing numbers of all tilings of $(2n+1)\times
2m$ quadriculated torus form an integer-interval.

In this paper, we concentrate on the flip graphs and forcing numbers of all
tilings of 4-regular quadriculated graphs on torus. Thomassen [21] classified
4-regular quadriculated graphs on torus and Klein bottle.

######  Theorem 1.1.

[21] Let $G$ be a connected 4-regular quadriculated graph on torus or Klein
bottle. Then $G$ is one of the graphs $Q_{k,m,r}$, $Q_{k,m,a}$, $Q_{k,m,b}$,
$Q_{k,m,c}$, $Q_{k,m,e}$, $Q_{k,m,f}$, $Q_{k,m,g}$ or $Q_{k,m,h}$, where
$Q_{k,m,r}$ and $Q_{k,m,e}$ are graphs on torus and the others are graphs on
Klein bottle.

Further, Li [12] proved that $Q_{k,m,r}$ and $Q_{k,m,e}$ can be induced into
one class of graphs.

######  Theorem 1.2.

[12] Any 4-regular quadriculated graph on torus is isomorphic to some toroidal
grid $T(n,m,r)$.

For $n,m\geq 2$, a _toroidal grid_ $T(n,m,r)$ is obtained from an $n\times m$
chessboard by sticking the left and right sides together and then identifying
the top and bottom sides with a torsion $r$ squares where $1\leq r\leq m$ (see
Fig. 1). Obviously, $T(n,m,m)$ is the $n\times m$ quadriculated torus.

Fig. 1: Toroidal grid $T(3,8,4)$.

By using graph-theoretical method, we obtain the following results.

######  Theorem 1.3.

$\mathcal{T}(T(2n+1,2m,2r))$ consists of two isomorphic components.

By Theorem 1.3, we obtain the following corollary.

######  Corollary 1.4.

Forcing numbers of all domino tilings of $T(2n+1,2m,2r)$ form an integer-
interval.

The _maximum forcing number_ of $R$, denoted by $F(R)$, is the maximum forcing
number of all domino tilings of $R$. Liu et al. [14] obtained that
$F(T(2n+1,2m,2m))=(n+1)m$. In general, we obtain the following result.

######  Theorem 1.5.

For $1\leq r\leq m$, we have

$F(T(2n+1,2m,2r))=\begin{cases}\frac{m(2n+1)+(r,m)}{2},&\quad{if\
\frac{m}{(r,m)}\ is\ odd};\\\ \frac{m(2n+1)}{2},&\quad{otherwise},\end{cases}$

where $(r,m)$ represents the maximum common factor of $r$ and $m$.

##  2 Properties of toroidal grids

In this section, we give some basic properties of $T(n,m,r)$. For an integer
$g\geq 1$, let $Z_{g}:=\\{0,1,\dots,g-1\\}$. According to the position of
vertices in the chessboard, we label the vertices of $T(n,m,r)$ as
$\\{v_{i,j}|i\in Z_{n},j\in Z_{m}\\}$ (see Fig. 2).

Fig. 2: Labels of vertices in $T(4,8,2)$.

Define $\varphi(v_{i,j})=v_{i,j+1}$ where $i\in Z_{n}$ and $j,j+1\in Z_{m}$.
Clearly, $\varphi$ is a translation of toroidal grid $T(n,m,r)$. By a simple
argument, we obtain the following result.

######  Lemma 2.1.

$\varphi$ is an automorphism on $T(n,m,r)$ which preserves the faces.

For $x\in Z_{m}$, let $v_{0,x}v_{1,x}\cdots v_{n-1,x}$ be a path called _$x$
-column_, and $v_{0,x}$ and $v_{n-1,x}$ are _initial_ and _terminal_ of
$x$-column. For convenience, we call $x$-column an _column_ for $x\in Z_{m}$.
For $x_{1}$\- and $x_{2}$-columns, if initial $v_{0,x_{2}}$ of $x_{2}$-column
is adjacent to terminal $v_{n-1,x_{1}}$ of $x_{1}$-column, that is,
$x_{2}\equiv x_{1}+r$ (mod $m$), then $x_{2}$-column is the _successor_ of
$x_{1}$-column. Let $x_{0}$-, $x_{1}$-, …, $x_{g-1}$-columns be pairwise
different such that $x_{i+1}$-column is the successor of $x_{i}$-column for
each $i\in Z_{g}$. Then these $g$ columns form a cycle, called an _$I$
-cycle_. According to the automorphism, each column lies on an $I$-cycle and
each $I$-cycle contains the same number of columns.

Let $p:Z_{m}\rightarrow Z_{m}$ be a permutation. If $p(i)=i+1$ for $i\in
Z_{m}$, then $p$ is a _$m$ -cycle_, denoted by $p=(01\cdots m-1)$. Example 2.3
in [2] implies the following result.

######  Lemma 2.2.

[2] Let $p=(01\cdots m-1)$ be a $m$-cycle. Then $p^{r}$ is the product of
$(m,r)$ cycles each of length $\frac{m}{(r,m)}$ for an positive integer $r\in
Z_{m}$.

By Lemma 2.2, we prove the following result.

######  Lemma 2.3.

$T(n,m,r)$ has $(r,m)$ $I$-cycles and each $I$-cycle contains
$\frac{m}{(r,m)}$ columns. Moreover, any consecutive $(r,m)$ columns lie on
different $I$-cycles.

###### Proof.

For $x\in Z_{m}$, we use $x$ to represent $x$-column of $T(n,m,r)$. Then there
is a one-to-one correspondence between $m$ columns of $T(n,m,r)$ and $Z_{m}$.
Thus $I$-cycles of $T(n,m,r)$ correspond to rotation decomposition of
$(01\cdots m-1)^{r}$. By Lemma 2.2, we have proved the first part.

By the automorphism in Lemma 2.1, it suffices to prove that any two ones from
0-, 1-, …, $((r,m)-1)$-columns do not lie on the same $I$-cycle. Suppose to
the contrary that $0$\- and $k$-column with $1\leq k\leq(r,m)-1$ lie on the
same $I$-cycle. That is to say, $k$-column lies on the $I$-cycle which
contains $0$-column. Then $k\equiv rt$ (mod $m$) for some $1\leq
t\leq\frac{m}{(r,m)}-1$. Since $k<rt$, we have $rt-k\equiv 0$ (mod $m$). Thus,
there exists a positive integer $u$ such that $um=rt-k$, i.e. $k=rt-um$. So
$1\leq rt-um\leq(r,m)-1$ and

$\frac{m}{(r,m)}\leq(rt-um)\cdot\frac{m}{(r,m)}=m(\frac{r}{(r,m)}\cdot
t-\frac{m}{(r,m)}\cdot u)\leq m-\frac{m}{(r,m)},$

which is a contradiction. ∎

For $i\in Z_{n}$ and $j\in Z_{m}$, we call $e_{i,j}=v_{i,j}v_{i,j+1}$ a
_horizontal edge_. For $j\in Z_{m}$, let $E_{j}=\\{e_{i,j}|i\in Z_{n}\\}$.
Then $E_{0}\cup E_{1}\cup\cdots\cup E_{m-1}$ is the set of all horizontal
edges of $T(n,m,r)$, and the others are _vertical_.

######  Observation 2.4.

All vertical edges of $T(n,m,r)$ form $(r,m)$ $I$-cycles and all horizontal
edges are these edges between two consecutive $I$-cycles.

Next we focus on studying $T(2n+1,2m,2r)$. By Lemma 2.3, $T(2n+1,2m,2r)$ has
$2(r,m)$ $I$-cycles and each $I$-cycle contains $\frac{m}{(r,m)}$ columns. For
$x\in Z_{2(r,m)}$, let $C_{x}$ be the $I$-cycle of $T(2n+1,2m,2r)$ containing
the $x$-column. Then $C_{x}$ consists of $x$-, $(x+2r)$-, …,
$(x+2r(\frac{m}{(r,m)}-1))$-columns, where subscripts take modulo $2m$. Since
each column contains $2n+1$ vertices, an $I$-cycle contains
$\frac{m(2n+1)}{(r,m)}$ vertices. In a direction, we label the vertices of
$C_{x}$ as $1^{x}$, $2^{x}$, …, $(\frac{m(2n+1)}{(r,m)})^{x}$ where
$1^{x}=v_{0,x}$, $2^{x}=v_{1,x}$, and so on. According to Observation 2.4, we
can draw $T(2n+1,2m,2r)$ into the $\frac{m(2n+1)}{(r,m)}\times 2(r,m)$
chessboard in which $C_{x}$ lie on the $(x+1)$-th column, and $C_{0}$ lie on
both the first and last columns. The previous columns in $C_{0}$ are arranged
as $0$-, $2r$-, $4r$-, …, $2r(\frac{m}{(r,m)}-1)$-columns from top to bottom
(see Fig. 3).

Fig. 3: Two drawings of $T(3,12,4)$.

We assume that these columns in last column are arranged as $2rk$-,
$2r(k+1)$-, …, $2r(\frac{m}{(r,m)}-1)$-, $0$-, …, $2r(k-1)$-columns from top
to bottom for some $0\leq k\leq\frac{m}{(r,m)}-1$. Since $2(r,m)$-column is
also $2rk$-column, we have $2(r,m)\equiv 2rk$ (mod $2m$). That is to say, $k$
is determined by the following equation.

$\displaystyle(r,m)\equiv rk\ \ (\text{mod\ }m).$ (2.1)

Obviously, the new drawing of $T(2n+1,2m,2r)$ is also a toroidal grid

$\displaystyle T((2r,2m),\frac{m}{(r,m)}(2n+1),(\frac{m}{(r,m)}-k)(2n+1)).$
(2.2)

According to labels of $I$-cycles, we obtain the relation of labels of two end
vertices of horizontal edges as follows.

######  Proposition 2.5.

Let $x^{i}y^{i+1}$ be a horizontal edge of $T(2n+1,2m,2r)$ where $i,i+1\in
Z_{(2r,2m)}$ and $1\leq x,y\leq(2n+1)\frac{m}{(r,m)}$. For $0\leq
i\leq(2r,2m)-2$, we have $x=y$. For $i=(2r,2m)-1$, we have

$y=\begin{cases}x+(2n+1)k,&\quad{if\ 1\leq x\leq(\frac{m}{(r,m)}-k)(2n+1)};\\\
x-(\frac{m}{(r,m)}-k)(2n+1),&\quad{otherwise}.\end{cases}$ (2.3)

###### Proof.

For $x\in Z_{(2r,2m)}$, all vertices of $(x+2rj)$-column are labeled as

$((2n+1)j+1)^{x},((2n+1)j+2)^{x},\dots,((2n+1)(j+1))^{x}\text{\ for\ }j\in
Z_{\frac{m}{(r,m)}}.$

So we have $x=y$ for $0\leq i\leq(2r,2m)-2$.

Now we assume that $i=(2r,2m)-1$. If $x^{i}y^{i+1}$ is a horizontal edge
connecting two vertices of $(i+2rj)$-column and $2r(k+j)$-column for $j\in
Z_{\frac{m}{(r,m)}-k}$, then $y=x+(2n+1)k$. If $x^{i}y^{i+1}$ is a horizontal
edge connecting two vertices of $(i+2r(\frac{m}{(r,m)}-k+j))$-column and
$2rj$-column for $j\in Z_{k}$, then $y=x-(2n+1)(\frac{m}{(r,m)}-k)$. Thus we
have $y=x+(2n+1)k$ for $1\leq x\leq(2n+1)(\frac{m}{(r,m)}-k)$; Otherwise, we
have $y=x-(2n+1)(\frac{m}{(r,m)}-k)$. ∎

If $\frac{m}{(r,m)}$ is an even number, then we have the following corollary.

######  Corollary 2.6.

If $\frac{m}{(r,m)}$ is an even number, then $k$ is odd, $x$ and $y$ have
different parity for a horizontal edge $x^{(2r,2m)-1}y^{0}$.

###### Proof.

By equation (2.1), we have $rk-(r,m)=mp$ for some non-negative integer $p$.
Thus $\frac{r}{(r,m)}k=\frac{m}{(r,m)}p+1$. Since $\frac{m}{(r,m)}$ is even,
$\frac{r}{(r,m)}\cdot k$ is odd and $k$ is an odd number. Hence
$\frac{m}{(r,m)}-k$ is an odd number. By (2.3) in Proposition 2.5, $x$ and $y$
have different parity. ∎

##  3 Proof of Theorem 1.3

In this section, we give the concept of resonance graphs and prove Theorem 1.3
by using theory of resonance graphs.

###  3.1 Resonance graphs

For a perfect matching $M$ of $G$, a cycle $C$ of $G$ is $M$-_alternating_ if
its edges appear alternately in $M$ and $E(C)\setminus M$. For an
$M$-alternating cycle $C$ of $G$, the _symmetric difference_ $M\oplus
E(C):=(M-E(C))\cup(E(C)-M)$ is another perfect matching of $G$ and such an
operation is called a _flip_ or _rotation_ of $M$ (along $C$).

Let $G$ be a graph 2-cell embedded on a closed surface, i.e. each face is
homeomorphic to an open disc in $\mathbb{R}^{2}$. The boundary of a face $f$
is denoted by $\partial f$. If $\partial f$ is a cycle, then we call it a
_facial cycle_. A face $f$ of $G$ is _even_ (resp. _odd_) if the length of
$\partial f$ is even (resp. odd). For convenience, sometimes we do not
distinguish a face with its boundary, and a cycle with its edge set.

The _resonance graph_ of $G$, denoted by $R_{t}(G)$, is defined on the set of
all perfect matchings of $G$ where two perfect matchings $M_{1}$ and $M_{2}$
are adjacent if and only if $M_{1}\oplus M_{2}$ forms the boundary of a face,
that is, $M_{2}$ is obtained from a rotation of $M_{1}$ along the boundary of
a face. The resonance graph was introduced independently many times under
different names by Grümdler [7], Zhang et al. [25], Randić [16] and Fournier
[5]. The study of resonance graphs mainly concentrates on some special plane
graphs such as hexagonal systems [7, 25, 16], polyominoes [23, 27] and plane
bipartite graphs [5, 26]. Readers may refer to a survey [24].

Note that the flip graph of a quadriculated region is isomorphic to the
resonance graph of its inner dual. Since $T(n,m,r)$ is a 4-regular
quadriculated graph on torus, so is its (inner) dual. By Theorem 1.2,
$D(T(n,m,r))$ is also a toroidal grid. Analyzing carefully, we find that inner
dual of $T(n,m,r)$ is itself. Hence, we have the following observation.

######  Observation 3.1.

The flip graph of $T(n,m,r)$ is the same as its resonance graph.

By Observation 3.1, it suffices to prove that $R_{t}(T(2n+1,2m,2r))$ has
exactly two components and such two components are isomorphic.

###  3.2 Preliminaries

For a non-empty subset $F\subseteq E(G)$, the subgraph of $G$ whose vertex set
is the set of end vertices of edges in $F$ and whose edge set is $F$ is called
the subgraph of $G$ _induced by_ $F$, denoted by $G[F]$. A _quadriculated
ribbon_ is obtained by connecting each vertex of a cycle with the
corresponding vertex on its copy with an edge.

Let $C_{i}$ and $C_{i+1}$ be two consecutive $I$-cycles of $T(2n+1,2m,2r)$ for
$i,i+1\in Z_{(2r,2m)}$. If $r\geq 1$, then the union of $E(C_{i})\cup
E(C_{i+1})$ and $E_{i}\cup E_{i+2r}\cup\cdots\cup E_{i+2r[\frac{m}{(r,m)}-1]}$
induces a subgraph isomorphic to a quadriculated ribbon, denoted by
$R_{i,i+1}$, where subscripts are modulo $2m$.

Let $M$ be a perfect matching of $T(2n+1,2m,2r)$ such that $C_{i}$ and
$C_{i+1}$ are $M$-alternating where $i,i+1\in Z_{2(r,m)}$. For $0\leq i\leq
2(r,m)-2$, if both $v_{0,i}v_{1,i}$ and $v_{0,i+1}v_{1,i+1}$ belong to $M$ or
neither $v_{0,i}v_{1,i}$ nor $v_{0,i+1}v_{1,i+1}$ belongs to $M$, then $C_{i}$
and $C_{i+1}$ _have the same form on $M$_. If both
$v_{0,2(r,m)-1}v_{1,2(r,m)-1}$ and $v_{0,2(r,m)}v_{1,2(r,m)}$ belong to $M$ or
neither $v_{0,2(r,m)-1}v_{1,2(r,m)-1}$ nor $v_{0,2(r,m)}v_{1,2(r,m)}$ belongs
to $M$, then $C_{2(r,m)-1}$ and $C_{0}$ _have the same form on $M$_. For a set
of $I$-cycles $\mathcal{C}$, if any two consecutive ones of $\mathcal{C}$ have
the same form on $M$, then we say that $\mathcal{C}$ _has the same form on
$M$_.

By a simple argument, we obtain the following lemma.

######  Lemma 3.2.

Let $M$ be a perfect matching of $R_{i,i+1}$ where $i,i+1\in Z_{(2r,2m)}$.

(i) If $M$ contains exactly one horizontal edge, then, by
$\frac{m(2n+1)-(r,m)}{2(r,m)}$ flips from $M$, we can obtain a perfect
matching of $R_{i,i+1}$ consisting of all horizontal edges.

(ii) If $M$ consists of vertical edges and $C_{i}$ and $C_{i+1}$ have the same
form on $M$, then, by $\frac{m(2n+1)}{2(r,m)}$ flips from $M$, we can obtain a
perfect matching of $R_{i,i+1}$ consisting of all horizontal edges.

(iii) Moreover, by $\frac{m(2n+1)}{2(r,m)}$ flips on the resulting perfect
matching of (ii), we can obtain a perfect matching $M^{\prime}=(E(C_{i})\cup
E(C_{i+1}))\oplus M$.

For a vertex subset $X\subseteq V(G)$, the set of edges with exactly one end
vertex in $X$ is written $\nabla(X)$. For a subgraph $G^{\prime}$ of $G$, we
write $\nabla(G^{\prime})$ instead of $\nabla(V(G^{\prime}))$. For a matching
$M$ of $G$, the vertices incident to edges of $M$ are called _saturated_ by
$M$ and the others are called _unsaturated_.

Let $M$ be a perfect matching of $T(2n+1,2m,2r)$. For $i\in Z_{2(r,m)}$, a
horizontal edge of $M\cap\nabla(C_{i})$ lies in either $R_{i-1,i}$ or
$R_{i,i+1}$ where $i-1,i+1\in Z_{2(r,m)}$. For $i\in\\{1,2\\}$, let $h_{i}$ be
a horizontal edge of $M\cap\nabla(C_{i})$ such that $x_{i}$ is the end vertex
of $h_{i}$ on $C_{i}$. We call $h_{1}$ and $h_{2}$ _consecutive_ if there
exists a path $P$ on $C_{i}$ connecting $x_{1}$ and $x_{2}$ such that all
intermediate vertices are saturated by $M\cap E(P)$. Assume that $h_{1}$ and
$h_{2}$ are consecutive. If $h_{1}$ and $h_{2}$ belong to $R_{i-1,i}$ or
$R_{i,i+1}$, simultaneously, then $h_{1}$ and $h_{2}$ _have the same
direction_. Otherwise, $h_{1}$ and $h_{2}$ _have different direction_.

By proof of Lemma 4.2 in [14], we have the following result.

######  Lemma 3.3.

Suppose that $M$ is a perfect matching of $T(2n+1,2m,2r)$. If there exist two
consecutive horizontal edges of $M\cap\nabla(C_{i})$ having the same
direction, then we can obtain a perfect matching $M^{\prime}$ of
$T(2n+1,2m,2r)$ by some flips from $M$ such that the number of horizontal
edges in $M^{\prime}$ is two less than that in $M$.

###  3.3 Proof

Let $M_{1}=E_{0}\cup E_{2}\cup\cdots\cup E_{2m-2}\text{ and }M_{2}=E_{1}\cup
E_{3}\cup\cdots\cup E_{2m-1}$ be two special perfect matchings of
$T(2n+1,2m,2r)$. Then we have the following lemma.

######  Lemma 3.4.

$M_{1}$ and $M_{2}$ lie in different components of $R_{t}(T(2n+1,2m,2r))$.

###### Proof.

Suppose to the contrary that $M_{1}$ and $M_{2}$ lie in a same component of
$R_{t}(T(2n+1,2m,2r))$. Then there is a path in $R_{t}(T(2n+1,2m,2r))$
connecting $M_{1}$ and $M_{2}$. That is, $M_{2}=M_{1}\oplus
S_{1}\oplus\cdots\oplus S_{k}$ where $S_{i}$ is the boundary of a face of
$T(2n+1,2m,2r)$ for $i=1,2,\dots,k$. For a face $f$, we denote by $\delta(f)$
the number of times $\partial f$ appeared in the sequence
$(S_{1},S_{2},\dots,S_{k})$.

Fig. 4: Some faces of $T(5,8,4)$.

For $1\leq i\leq 2n$, let $f_{i}$ and $f_{i+1}$ be the two faces of
$T(2n+1,2m,2r)$ having edge $e_{i,0}$ in common shown as Fig. 4. Since
$e_{i,0}\in M_{1}$ but $e_{i,0}\notin M_{2}$, $e_{i,0}$ appears odd times in
the sequence $(S_{1},S_{2},\dots,S_{k})$. Thus

$\displaystyle\delta(f_{i})+\delta(f_{i+1})\equiv 1\text{ (mod 2) }\text{for
}1\leq i\leq 2n.$ (3.1)

Let $g_{i}$ be a face of $T(2n+1,2m,2r)$ bounded by
$v_{0,i}v_{1,i}v_{1,i+1}v_{0,i+1}v_{0,i}$ for $1\leq i\leq 2r$. Then
$f_{2n+1}$ and $g_{2r}$ have exactly one edge $e_{0,2r}$ in common, and
$g_{i-1}$ and $g_{i}$ have the common edge $v_{0,i}v_{1,i}$ for $1\leq i\leq
2r$ where $g_{0}:=f_{1}$. Since $e_{0,2r}\in M_{1}$ but $e_{0,2r}\notin
M_{2}$, $e_{0,2r}$ appears odd times in the sequence
$(S_{1},S_{2},\dots,S_{k})$. So we have

$\displaystyle\delta(f_{2n+1})+\delta(g_{2r})\equiv 1\text{ (mod 2)}.$ (3.2)

Since $v_{0,i}v_{1,i}$ lies in neither $M_{1}$ nor $M_{2}$ for $1\leq i\leq
2r$, we obtain that

$\displaystyle\delta(g_{i-1})+\delta(g_{i})\equiv 0\text{ (mod 2)}\text{ for
}1\leq i\leq 2r.$ (3.3)

Thus, we obtain $2n+2r+1$ equalities in $(\ref{eq1})$-$(\ref{eq3})$, where
$2n+1$ equalities equal to 1 and the others equal to 0. But in such $2n+2r+1$
equalities, each $\delta(f)$ appears twice for
$f\in\\{f_{1},f_{2}\dots,f_{2n+1},g_{1},\dots,g_{2r}\\}$, which is a
contradiction. ∎

Lemma 3.4 states that $R_{t}(T(2n+1,2m,2r))$ has at least two components. In
the sequel, we shall prove that $R_{t}(T(2n+1,2m,2r))$ has at most two
components. That is to say, any perfect matching $M$ of $T(2n+1,2m,2r)$ can be
converted into the perfect matching $M_{1}$ or $M_{2}$. First of all, we prove
the case that $M$ consists of vertical edges.

######  Lemma 3.5.

If $M$ is a perfect matching of $T(2n+1,2m,2r)$ consisting of vertical edges,
then we can obtain the perfect matching $M_{1}$ or $M_{2}$ by a series of
flips from $M$.

###### Proof.

Since $M$ consists of vertical edges, each $I$-cycle is even and
$M$-alternating. Thus, $r\geq 1$. By Lemma 2.3, $T(2n+1,2m,2r)$ has
$t:=2(r,m)\geq 2$ $I$-cycles and any consecutive $t$ columns lie on different
$I$-cycles. Thus, $C_{0}$ consists of $0$-, $t$-, …,
$(\frac{m}{(r,m)}-1)t$-columns.

$x$-column and $y$-column are said to _have the same form on $M$_ if either
$\\{v_{0,x}v_{1,x},v_{0,y}v_{1,y}\\}$ or
$\\{v_{0,x}v_{2n,2m-2r+x},v_{0,y}v_{2n,2m-2r+y}\\}$ is contained in $M$, and
_have different form on $M$_ otherwise, where the second subscripts take
modulo $2m$. Because an $I$-cycle is $M$-alternating and each column contains
an odd number of vertices, it has half of columns being the same form on $M$
and the other half being the other form on $M$. Thus, there exist $x$\- and
$(x+t)$-columns having different form on $M$ for some $x\in Z_{2m}$. Without
loss of generality, assume that $x=0$ and
$\\{v_{0,0}v_{1,0},v_{0,t}v_{2n,2m-2r+t}\\}\subseteq M$.

$\text{Let
}\alpha=|M\cap\\{v_{0,1}v_{2n,2m-2r+1},v_{0,2}v_{2n,2m-2r+2},\dots,v_{0,t-1}v_{2n,2m-2r+t-1}\\}|.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

Then $0\leq\alpha\leq t-1$. We will prove the lemma by induction on $\alpha$.
For $\alpha=0$, all $t$ $I$-cycles have the same form on $M$. Since $M\cap
E(R_{2l,2l+1})$ is a perfect matching of $R_{2l,2l+1}$ for $0\leq
l\leq\frac{t}{2}-1$, by repeatedly applying Lemma 3.2(ii) $\frac{t}{2}$ times,
we can obtain the perfect matching $M_{1}$.

Fig. 5: Description of the proof of Lemma 3.5.

Next we assume that $\alpha\geq 1$. If there exist two positive integers $l$
and $s$ with $1\leq l<l+s\leq t$ satisfying
$\\{v_{0,l}v_{2n,2m-2r+l},v_{0,l+s}v_{2n,2m-2r+l+s}\\}$ and
$\\{v_{0,l+1}v_{1,l+1},\dots,v_{0,l+s-1}v_{1,l+s-1}\\}$ are contained in $M$
shown as Fig. 5(a), and $s-1$ is an even number, then
$\\{C_{l+1},C_{l+2},\dots,\\\ C_{l+s-1}\\}$ have the same form on $M$. For
$R_{l+1,l+2},R_{l+3,l+4},\dots,R_{l+s-2,l+s-1}$, we separately perform
$\frac{m(2n+1)}{(r,m)}$ flips from its perfect matching by Lemma 3.2(iii) and
last result in a perfect matching $M^{\prime}$ consisting of vertical edges.
Now $\\{C_{l},C_{l+1},\dots,C_{l+s}\\}$ have the same form on $M^{\prime}$. By
performing $\frac{m(2n+1)}{(r,m)}$ flips separately on
$R_{l,l+1},R_{l+2,l+3},\cdots,R_{l+s-1,l+s}$ by Lemma 3.2(iii), we result in a
perfect matching $M^{\prime\prime}$ which consists of vertical edges and
$\alpha^{\prime\prime}=\alpha-1$ or $\alpha-2$. By the induction hypothesis,
we can obtain the perfect matching $M_{1}$ or $M_{2}$ from $M^{\prime\prime}$
by some flips. Thus, $M_{1}$ or $M_{2}$ can be obtained from $M$ by a series
of flips.

Now we assume that $s-1$ is an odd number if there exist above $l$ and $s$.
Thus $v_{0,t-1}v_{1,t-1}\in M$. Since $\alpha\geq 1$, there exist the maximum
index $k$ with $1\leq k\leq t-2$ such that $v_{0,k}v_{2n,2m-2r+k}\in M$ shown
in Fig. 5(b). Then all edges of
$\\{v_{0,k+1}v_{1,k+1},\dots,v_{0,t-2}v_{1,t-2}\\}$ are contained in $M$. Take
$l=k$ and $l+s=t$. Since $s-1$ is an odd number, $s$ is an even number and so
is $k$. Let $i$ be the minimum index such that $v_{0,i}v_{2n,2m-2r+i}\in M$
where $1\leq i\leq t-2$. Then
$\\{v_{0,1}v_{1,1},\dots,v_{0,i-1}v_{1,i-1}\\}\subseteq M$ and $i$ is an even
number. Since $\\{v_{0,t-1}v_{1,t-1},v_{0,t}v_{2n,2m-2r+t}\\}\subseteq M$,
$C_{t-1}$ and $C_{0}$ have different form on $M$. Combining that
$v_{0,0}v_{1,0}\in M$, we have $v_{0,2m-1}v_{2n,2m-2r-1}\in M$. Now
$\\{C_{0},C_{1},\dots,C_{i-1}\\}$ have the same form on $M$. We perform
$\frac{m(2n+1)}{(r,m)}$ flips on each $R_{0,1},R_{2,3},\dots,R_{i-2,i-1}$ by
Lemma 3.2(iii) and result in a perfect matching $M^{\prime}$ consisting of
vertical edges. Then $\\{C_{t-1},C_{0},\dots,C_{i}\\}$ have the same form on
$M^{\prime}$. By repeatedly applying Lemma 3.2(iii) on each
$R_{t-1,0},R_{1,2},\dots,R_{i-1,i}$, we can obtain a perfect matching
$M^{\prime\prime}$ by some flips from $M^{\prime}$ such that
$\alpha^{\prime\prime}=\alpha$ but $v_{0,t-1}v_{2n,2m-2r+t-1}\in
M^{\prime\prime}$. Taking $l=t-1$ and $s=1$, we obtain that $s-1$ is an even
number. By previous argument, we have done. ∎

Now we prove that any perfect matching of $T(2n+1,2m,2r)$ can be converted
into the perfect matching $M_{1}$ or $M_{2}$ by a series of flips.

######  Lemma 3.6.

Let $M$ be a perfect matching of $T(2n+1,2m,2r)$. Then, by a series of flips
from $M$, we can obtain the perfect matching $M_{1}$ or $M_{2}$.

###### Proof.

Let $l$ represent the number of horizontal edges in $M$. Then $l\geq 0$. We
will prove the lemma by induction on $l$. For $l=0$, $M$ consists of vertical
edges. By Lemma 3.5, we have done. For $l=1$, each $I$-cycle contains an odd
number of vertices and $T(2n+1,2m,2r)$ has exactly two $I$-cycles. We assume
that the unique horizontal edge of $M$ belongs to $R_{0,1}$ (resp. $R_{1,0}$).
Then $M$ is uniquely determined, by Lemma 3.2(i), we can obtain the perfect
matching $M_{1}$ (resp. $M_{2}$) by $\frac{m(2n+1)-(r,m)}{2(r,m)}$ flips. Now
we assume that $l\geq 2$. We divide into the following two cases according to
the parity of the number of vertices in an $I$-cycle.

Case 1. An $I$-cycle contains an odd number of vertices.

For an $I$-cycle $C$, $|M\cap\nabla(C)|$ is odd. We assume that
$M\cap\nabla(C)$ contains exactly one edge for each $I$-cycle $C$. Then
$T(2n+1,2m,2r)$ has exactly $(r,m)$ horizontal edges in $M$. Without loss of
generality, we assume that $e_{i}$ is the unique horizontal edge of
$R_{2i,2i+1}$ for $i\in Z_{(r,m)}$. By Lemma 3.2(i), we can obtain a perfect
matching $M^{\prime}$ from $M$ by $\frac{m(2n+1)-(r,m)}{2(r,m)}$ flips such
that all horizontal edges of $R_{2i,2i+1}$ lie in $M^{\prime}$. Hence, by
$\frac{m(2n+1)-(r,m)}{2}$ flips from $M$, we can obtain the perfect matching
$M_{1}$. Now we assume that there exists an $I$-cycle $C_{i}$ of
$T(2n+1,2m,2r)$ such that $M\cap\nabla(C_{i})$ contains at least three edges
where $i\in Z_{(2r,2m)}$. Since an edge of $M\cap\nabla(C_{i})$ belongs to
either $R_{i-1,i}$ or $R_{i,i+1}$ where $i-1,i+1\in Z_{(2r,2m)}$ and
$|M\cap\nabla(C_{i})|$ is an odd number, $T(2n+1,2m,2r)$ contains two
consecutive horizontal edges belonging to $R_{i-1,i}$ or $R_{i,i+1}$,
simultaneously. That is to say, there exist two consecutive horizontal edges
of $M\cap\nabla(C_{i})$ having the same direction.

Case 2. An $I$-cycle contains an even number of vertices.

We will prove that there exists an $I$-cycle $C_{i}$ of $T(2n+1,2m,2r)$ and
two consecutive horizontal edges of $M\cap\nabla(C_{i})$ having the same
direction. Suppose to the contrary that any two consecutive horizontal edges
of $M\cap\nabla(C)$ have different direction for any $I$-cycle $C$. Since
$l\geq 2$, there exists an $I$-cycle $C_{i}$ such that
$M\cap\nabla(C_{i})\neq\emptyset$. Combining that $C_{i}$ is an even cycle,
$M\cap\nabla(C_{i})$ contains an even number of edges. Since any two
consecutive horizontal edges have different direction, $M$ contains horizontal
edges of $R_{i,i+1}$ and also those of $R_{i-1,i}$ and such two sets of
horizontal edges are equal in number. Hence, each $M\cap\nabla(C_{i})$
contains the same number of edges for $i\in Z_{(2r,2m)}$ and half of which
belong to $E(R_{i-1,i})$ and the others belong to $E(R_{i,i+1})$ where
$i-1,i+1\in Z_{(2r,2m)}$.

Since an $I$-cycle contains $\frac{m(2n+1)}{(r,m)}$ vertices,
$\frac{m}{(r,m)}$ is an even number. Label the vertices of $C_{x}$ as
$1^{x},2^{x},\dots,(\frac{m(2n+1)}{(r,m)})^{x}$ where $1^{x}=v_{0,x}$,
$2^{x}=v_{1,x}$ and so on. Then Proposition 2.5 and Corollary 2.6 hold.
Without loss of generality, assume that all edges of $M\cap E(R_{0,1})$ have
the form $x^{0}x^{1}$ and $x$ is an odd number. Then all edges of $M\cap
E(R_{1,2})$ have the form $y^{1}y^{2}$ where $y$ is an even number.
Successively, all edges of $M\cap E(R_{(2r,2m)-1,0})$ have the form
$l^{(2r,2m)-1}p^{0}$ where $l$ is an even number and $p$ is an odd number by
Corollary 2.6. Now end vertices of all edges of $M\cap\nabla(C_{0})$ on
$C_{0}$ are represented as $x^{0}$ and all $x$ are odd. Hence the other
vertices of $C_{0}$ are saturated by vertical edges, which is a contradiction.

By Cases 1 and 2, there exists two consecutive horizontal edges of
$M\cap\nabla(C_{i})$ having the same direction where $i\in Z_{(2r,2m)}$. By
Lemma 3.3, we obtain a perfect matching $M^{\prime}$ by some flips from $M$
such that $l^{\prime}=l-2$. By the induction hypothesis, we obtain the perfect
matching $M_{1}$ or $M_{2}$ from $M^{\prime}$ by some flips. Thus, by some
flips from $M$, we can obtain the perfect matching $M_{1}$ or $M_{2}$. ∎

By Lemmas 3.4 and 3.6, $R_{t}(T(2n+1,2m,2r))$ has exactly two components
containing $M_{1}$ and $M_{2}$ separately, which are denoted by $H_{1}$ and
$H_{2}$. By Lemma 2.1, $\varphi$ is an automorphism on $T(2n+1,2m,2r)$ which
preserves the faces. Since $\varphi(M_{1})=M_{2}$, by a similar proof as that
of Theorem 4.4 in [14], we know that $\varphi$ preserves the flip operation.
Thus, $\varphi$ induces an isomorphism from $H_{1}$ to $H_{2}$. $\square$

A graph is _trivial_ if it contains only one vertex; Otherwise, it is _non-
trivial_.

######  Remark 3.7.

$R_{t}(T(3,4,1))$ has 12 components, 8 of which are trivial.

Calculating by computer, $T(3,4,1)$ has 80 perfect matchings. By analysing
flip operations for each perfect matching, we obtain that $R_{t}(T(3,4,1))$
has eight trivial components and four non-trivial components. Vertices of
eight trivial components are:
$M_{7}=\\{v_{0,0}v_{1,0},v_{2,0}v_{0,1},v_{1,1}v_{2,1},v_{0,2}v_{1,2},v_{2,2}v_{0,3},v_{1,3}v_{2,3}\\}$,
$M_{15}=\\{v_{0,0}v_{1,0},v_{2,0}v_{2,3},v_{0,1}v_{0,2},v_{1,1}v_{2,1},\\\
v_{1,2}v_{1,3},v_{2,2}v_{0,3}\\}$,
$M_{26}=\\{v_{0,0}v_{0,1},v_{1,0}v_{2,0},v_{1,1}v_{1,2},v_{2,1}v_{0,2},v_{2,2}v_{2,3},v_{0,3}v_{1,3}\\}$,
$M_{36}=\\{v_{0,0}v_{0,1},\\\
v_{1,0}v_{1,3},v_{2,0}v_{2,1},v_{1,1}v_{1,2},v_{0,2}v_{0,3},v_{2,2}v_{2,3}\\}$,
$M_{51}=\\{v_{0,0}v_{0,3},v_{1,0}v_{1,1},v_{2,0}v_{0,1},v_{2,1}v_{2,2},v_{0,2}v_{1,2},\\\
v_{1,3}v_{2,3}\\}$,
$M_{52}=\\{v_{0,0}v_{0,3},v_{1,0}v_{1,1},v_{2,0}v_{2,3},v_{0,1}v_{0,2},v_{2,1}v_{2,2},v_{1,2}v_{1,3}\\}$,
$M_{64}=\\{v_{0,0}v_{2,3},v_{1,0}v_{2,0},\\\
v_{0,1}v_{1,1},v_{2,1}v_{0,2},v_{1,2}v_{2,2},v_{0,3}v_{1,3}\\}$,
$M_{76}=\\{v_{0,0}v_{2,3},v_{1,0}v_{1,3},v_{2,0}v_{2,1},v_{0,1}v_{1,1},v_{0,2}v_{0,3},v_{1,2}v_{2,2}\\}$,
respectively. Four non-trivial components contain respectively
$M_{28}=\\{v_{0,0}v_{0,1},v_{1,0}v_{1,1},v_{2,0}\\\
v_{2,1},v_{0,2}v_{1,2},v_{2,2}v_{0,3},v_{1,3}v_{2,3}\\}$,
$M_{59}=\\{v_{0,0}v_{0,3},v_{1,0}v_{1,3},v_{2,0}v_{2,3},v_{0,1}v_{1,1},v_{2,1}v_{0,2},v_{1,2}v_{2,2}\\}$,
$M_{4}\\\
=\\{v_{0,0}v_{1,0},v_{2,0}v_{2,1},v_{0,1}v_{1,1},v_{0,2}v_{1,2},v_{2,2}v_{2,3},v_{0,3}v_{1,3}\\}$,
$M_{71}=\\{v_{0,0}v_{2,3},v_{1,0}v_{1,1},v_{2,0}v_{0,1},v_{2,1}v_{0,2},\\\
v_{1,2}v_{1,3},v_{9}v_{0,3}\\}$, where the components containing $M_{28}$ and
$M_{59}$ respectively have 12 vertices and each of the other components has 24
vertices.

##  4 Proof of Corollary 1.4

To show Corollary 1.4, we need the following definitions. Let $M$ be a perfect
matching of $G$. A subset $S\subseteq M$ is a _forcing set_ of $M$ if $S$ is
contained only in $M$. The smallest cardinality of a forcing set of $M$ is the
_forcing number_ of $M$, denoted by $f(G,M)$. The forcing number of a perfect
matching was first introduced by Harary et al. [8] and by Klein and Randić
[10] in chemical literatures, which has important applications in resonance
theory. Afshani et al. [1] obtained the following result.

######  Lemma 4.1.

[1] If $M$ is a perfect matching of $G$ and $C$ is an $M$-alternating cycle of
length 4, then

$|f(G,M\oplus E(C))-f(G,M)|\leq 1.$

By corresponding relations between domino tilings of a quadriculated region
and perfect matchings of its inner dual, we obtain the following observation.

######  Observation 4.2.

The forcing number of a domino tiling in $T(2n+1,2m,2r)$ is equal to that of
the corresponding perfect matching in $T(2n+1,2m,2r)$.

By Observation 4.2, it suffices to prove that forcing numbers of all perfect
matchings of $T(2n+1,2m,2r)$ form an integer-interval. Now we prove Corollary
1.4.

By proof of Theorem 1.3, $R_{t}(T(2n+1,2m,2r))$ has exactly two components
$H_{1}$ and $H_{2}$. For $i\in\\{1,2\\}$, since any two perfect matchings of
$H_{i}$ can be obtained from each other by some flips, the forcing numbers of
all perfect matchings in $H_{i}$ form an integer-interval by Lemma 4.1.

Two perfect matchings $M^{1}$ and $M^{2}$ of graph $G$ are _equivalent_ if
there is an automorphism of $G$ such that it maps $M^{1}$ to $M^{2}$. By Lemma
2.1, $\varphi$ is an automorphism of $T(2n+1,2m,2r)$. Since
$\varphi(M_{1})=M_{2}$, $M_{1}$ and $M_{2}$ are equivalent. By the proof of
Theorem 1.3, $\varphi$ induces an isomorphism from $H_{1}$ to $H_{2}$. Thus,
for any perfect matching $M$ of $H_{1}$, there exists a perfect matching
$\varphi(M)$ of $H_{2}$ such that $M$ and $\varphi(M)$ are equivalent. Since
two equivalent perfect matchings have the same forcing number, the sets of
forcing numbers of perfect matchings in $H_{1}$ and $H_{2}$ are the same. Thus
forcing numbers of all perfect matchings of $T(2n+1,2m,2r)$ form an integer-
interval. $\square$

######  Remark 4.3.

By computing forcing numbers of all 18656 perfect matchings of $T(3,10,1)$ by
computer, we obtain a set $\\{3,5,6,7,8\\}$, which has one gap 4.

##  5 Proof of Theorem 1.5

The _maximum forcing number_ of $G$ is the maximum value of $f(G,M)$ over all
perfect matchings $M$ of $G$. By Observation 4.2, the maximum forcing number
of $T(2n+1,2m,2r)$ is equal to that of domino tilings of $T(2n+1,2m,2r)$.
Similar to the maximum forcing number of quadriculated regions, we denote the
maximum forcing number of $G$ by $F(G)$. It suffices to prove that the maximum
forcing number of $T(2n+1,2m,2r)$ is shown as Theorem 1.5. Recall that each
$I$-cycle contains $\frac{m}{(r,m)}$ columns. By the parity of
$\frac{m}{(r,m)}$, we need to prove the following two lemmas.

For a non-empty subset $T\subseteq V(G)$, the _subgraph induced by $T$_,
denoted by $G[T]$, is a graph with vertex set $T$ and edge set is the set of
those edges of $G$ that have both end vertices in $T$. The induced subgraph
$G[V(G)\setminus T]$ is denoted by $G-T$.

######  Lemma 5.1.

If $\frac{m}{(r,m)}$ is odd, then $F(T(2n+1,2m,2r))=\frac{m(2n+1)+(r,m)}{2}$.

###### Proof.

Let $G=T(2n+1,2m,2r)$ and $g:=\frac{m}{(r,m)}$. It suffices to prove that
$F(G)=\frac{m((2n+1)g+1)}{2g}$. Recall that $M_{1}=E_{0}\cup
E_{2}\cup\cdots\cup E_{2m-2}$. For $i\in Z_{\frac{m}{g}}$, let
$M^{i}=M_{1}\cap E(R_{2i,2i+1})$ be a perfect matching of $R_{2i,2i+1}$. It is
clear that $f(R_{2i,2i+1},M^{i})=\frac{(2n+1)g+1}{2}$. Thus,

$F(G)\geq f(G,M_{1})\geq\sum_{i\in
Z_{\frac{m}{g}}}f(R_{2i,2i+1},M^{i})=\frac{(2n+1)g+1}{2}\times\frac{m}{g}=\frac{m((2n+1)g+1)}{2g}.$

Next we prove that $F(G)\leq\frac{m((2n+1)g+1)}{2g}$.

For $i\in\\{0,2,\dots,\frac{2m}{g}-4\\}$, let

$X_{i}=\\{x^{i}|x=1,3,\dots,(2n+1)g-2\\}.$

Let $k$ be defined as equation (2.1) where $0\leq k\leq g-1$. If $k$ is odd,
take
$Y_{\frac{2m}{g}-2}=\\{y^{\frac{2m}{g}-2}|y=1,3,\dots,(g-k)(2n+1)-1,(g-k)(2n+1)+2,(g-k)(2n+1)+4,\dots,(2n+1)g-1\\}$.
Otherwise, let
$Y_{\frac{2m}{g}-2}=\\{y^{\frac{2m}{g}-2}|y=2,4,\dots,(2n+1)(g-k)-1,(2n+1)(g-k)+2,(2n+1)(g-k)+4,\dots,(2n+1)g\\}$.
Then $|X_{i}|=|Y_{\frac{2m}{g}-2}|=\frac{(2n+1)g-1}{2}$ for
$i\in\\{0,2,\dots,\frac{2m}{g}-4\\}$. Take marked vertices $T$ (shown in Fig.
6) as follows:

$T=X_{0}\cup X_{2}\cup\cdots\cup X_{\frac{2m}{g}-4}\cup Y_{\frac{2m}{g}-2}.$

Then $T$ is of size $\frac{m((2n+1)g-1)}{2g}$. For
$i\in\\{0,2,\dots,\frac{2m}{g}-4\\}$, in the $(i+1)$-th column of
$(2n+1)g\times\frac{2m}{g}$ chessboard, marked vertices are the vertices at
the odd position except for the last one. If $k$ is odd, then labels of
vertices on ${2rk}$-column from top to bottom are

$((2n+1)(k-1)+1)^{0},((2n+1)(k-1)+2)^{0},\dots,((2n+1)k)^{0}.$

That is to say, marked vertices in the last column of
$(2n+1)g\times\frac{2m}{g}$ chessboard are at even position in the first $g-k$
columns while odd position in the last $k$-columns. In order to avoid paths of
length 2 between marked vertices of $C_{\frac{2m}{g}-2}$ and $C_{0}$, vertices
in $Y_{\frac{2m}{g}-2}$ are taken into the marked vertices. Similarly, we take
the marked vertices for even number $k$.

Fig. 6: Marked vertices of $T(3,18,6)$ and $T(3,12,8)$.

For any perfect matching $M$ of $G$, we define

$\displaystyle E_{T}=\\{e\in M\ |\ e\text{\ has an end vertex in }T\\}.$ (5.1)

Since $M$ is a matching and $T$ is an independent set, we have $|E_{T}|=|T|$.
We claim that $G[V(E_{T})]$ contains no $M$-alternating cycles. Suppose to the
contrary that $G[V(E_{T})]$ contains an $M$-alternating cycle. Since $T$ is an
independent set, an $M$-alternating cycle has exactly half vertices in $T$,
and marked vertices and unmarked vertices appear alternately. Thus we can
treat the $M$-alternating cycle as a union of paths of length two between
marked vertices.

Let $G^{\prime}$ be a subgraph of $G$ consisting of all paths of length two
between marked vertices. According to position of marked vertices, all edges
incident to vertices of $C_{\frac{2m}{g}-1}$ lie in no $G^{\prime}$. Besides,
there are at least two adjacent vertices of each $I$-cycle not in
$G^{\prime}$. Thus $G^{\prime}$ is a planar bipartite graph (see Fig. 6 as
bold lines). For any cycle $C^{\prime}$ of $G^{\prime}$, let $H$ be a subgraph
of $G$ induced by the vertices of $C^{\prime}$ and its interior. Then $H$ is
obtained by splicing some $2\times 2$ squares from left to right and from
bottom to top by two methods shown as (a) or (b) in Fig. 6. Since the interior
of a $2\times 2$ square has exactly one vertex and each time we add a $2\times
2$ square, the number of vertices in the interior of the resulting graph is
increased by 2 or 4. By induction, we can prove that the interior of $H$ has
an odd number of vertices. Thus, $C^{\prime}$ cannot be $M$-alternating which
is a contradiction.

By the claim, $M\setminus E_{T}$ is a forcing set of $M$ and

$f(G,M)\leq|M\setminus
E_{T}|=(2n+1)m-\frac{m((2n+1)g-1)}{2g}=\frac{m((2n+1)g+1)}{2g}.$

By the arbitrariness of $M$, we have $F(G)\leq\frac{m((2n+1)g+1)}{2g}$. ∎

######  Lemma 5.2.

If $\frac{m}{(r,m)}$ is even, then $F(T(2n+1,2m,2r))=\frac{m(2n+1)}{2}$.

###### Proof.

Let $G=T(2n+1,2m,2r)$ and $g:=\frac{m}{(r,m)}$. Recall that $M_{1}=E_{0}\cup
E_{2}\cup\cdots\cup E_{2m-2}$. For $i\in Z_{\frac{m}{g}}$, let
$M^{i}=M_{1}\cap E(R_{2i,2i+1})$ be a perfect matching of $R_{2i,2i+1}$. It is
clear that $f(R_{2i,2i+1},M^{i})\geq\frac{(2n+1)g}{2}$. Thus,

$F(G)\geq f(G,M_{1})\geq\sum_{i\in
Z_{\frac{m}{g}}}f(R_{2i,2i+1},M^{i})\geq\frac{(2n+1)g}{2}\cdot\frac{m}{g}=\frac{m(2n+1)}{2}.$

Let $M$ be a perfect matching of $G$. It suffices to prove that
$f(G,M)\leq\frac{(2n+1)m}{2}$. For $i\in Z_{\frac{2m}{g}}$, let
$X_{i}=\\{x^{i}|x=1,3,\dots,(2n+1)g-1\\}$ and
$X_{i}^{\prime}=X_{i}-{((2n+1)g-1)}^{i}$,
$Y_{i}=\\{y^{j}|j=2,4,\dots,(2n+1)g\\}$. Then we consider the following two
cases.

Case 1. All of $C_{1},C_{3},\dots,C_{\frac{2m}{g}-1}$ are not $M$-alternating.

Let $k=\lfloor\frac{m}{2g}\rfloor$. If $\frac{m}{g}=2k+1$, then we take

$T=X_{1}\cup X_{5}\cup\cdots\cup X_{4k+1}\cup Y_{3}\cup Y_{7}\cup\cdots\cup
Y_{4(k-1)+3}.$

If $\frac{m}{g}=2k$, then we take

$T=X_{1}\cup X_{3}\cup X_{7}\cup\cdots\cup X_{4(k-1)+3}\cup Y_{5}\cup
Y_{9}\cup\cdots\cup Y_{4(k-1)+1}.$

Then $T$ is of size $\frac{m(2n+1)}{2}$ and we call $T$ _marked vertices_
shown in Fig. 7.

Fig. 7: Marked vertices of $T(5,12,6)$ and $T(5,16,8)$.

Define the subset $E_{T}$ of $M$ as (5.1). Just as the proof of Lemma 5.1, we
look for paths of length two between marked vertices. Clearly, positions of
marked vertices on $I$-cycles $C_{1}$ and $C_{\frac{2m}{g}-1}$ are the same.
By Corollary 2.6, all edges incident with vertices of $C_{0}$ lie in no
$G^{\prime}$. If $\frac{m}{g}$ is an odd number, then all edges incident with
vertices of $C_{2}$, $C_{4}$,…,$C_{\frac{2m}{g}-2}$ lie in no $G^{\prime}$.
Hence all possible cycles in $G[V(E_{T})]$ are
$C_{1},C_{3},\dots,C_{\frac{2m}{g}-1}$, which is a contradiction. If
$\frac{m}{g}$ is an even number, then all edges incident with vertices of
$C_{4}$, $C_{6}$,…,$C_{\frac{2m}{g}-2}$ lie in no $G^{\prime}$. Hence all
possible cycles in $G[V(E_{T})]$ lie in the “seam”, that is, three consecutive
columns in which marked vertices are on the outside columns and lie up next to
each other (see $T(5,16,8)$ in Fig. 7 where the second, third and fourth
columns form a seam). By a similar argument as the proof of Theorem 4.5 in
[11], there is a placement of the seam such that $G[V(E_{T})]$ contains no
$M$-alternating cycles. Thus, $M\setminus E_{T}$ is a forcing set of $M$ and

$f(G,M)\leq|M\setminus E_{T}|=(2n+1)m-\frac{m(2n+1)}{2}=\frac{m(2n+1)}{2}.$

Case 2. At least one of $C_{1},C_{3},\dots,C_{\frac{2m}{g}-1}$ is
$M$-alternating.

Since any two $I$-cycles are equivalent, we assume that $C_{\frac{2m}{g}-1}$
is $M$-alternating and

$\\{(2s-1)^{\frac{2m}{g}-1}(2s)^{\frac{2m}{g}-1}|s=1,2,\dots,\frac{(2n+1)g}{2}\\}\subseteq
M.$

Take $T=X_{0}^{\prime}\cup X_{2}^{\prime}\cup\cdots\cup
X_{\frac{2m}{g}-2}^{\prime}\cup Y^{\prime}$ where
$Y^{\prime}=\\{((2n+1)g-1)^{j}|j=1,3,\dots,\frac{2m}{g}-1\\}$. Then $T$ is of
size $\frac{m(2n+1)}{2}$ and we call $T$ _marked vertices_ shown in Fig. 8(a).
Define the subset $E_{T}$ of $M$ as (5.1). Next we will prove that we can
place the marked vertices $T$ such that $G[V(E_{T})]$ contains no
$M$-alternating cycles. If we have done, then $M\setminus E_{T}$ is a forcing
set of $M$ and $f(G,M)\leq|M\setminus E_{T}|=\frac{m(2n+1)}{2}.$

Fig. 8: Two placement of marked vertices of $T(5,12,6)$.

Just as the proof of Lemma 5.1, we consider paths of length two between marked
vertices shown as bold lines in Fig. 8(a). We denote the subgraph of $G$
formed by union of all paths of length two between marked vertices by
$G^{\prime}$. Next we will prove that the unique possible $M$-alternating
cycle $C$ of $G^{\prime}$ is

$S=((2n+1)g-1)^{\frac{2m}{g}-1}((2n+1)g)^{\frac{2m}{g}-1}((2n+1)k)^{0}((2n+1)k-1)^{0}((2n+1)g-1)^{\frac{2m}{g}-1}.$

By previous proof of Lemma 5.1, $C$ contains the vertex
$((2n+1)g-1)^{\frac{2m}{g}-1}$. Since $C$ is $M$-alternating, it also contains
three edges

$((2n+1)g-1)^{\frac{2m}{g}-1}((2n+1)g)^{\frac{2m}{g}-1},((2n+1)g-1)^{\frac{2m}{g}-1}((2n+1)k-1)^{0},((2n+1)g)^{\frac{2m}{g}-1}((2n+1)k)^{0}$

where $k$ is defined as equation (2.1). If $C$ contains at least five
vertices, then let $G_{0}$ be the subgraph of $G$ induced by all vertices of
$C$ and its interior. Then

$H:=G_{0}-\\{((2n+1)g-1)^{\frac{2m}{g}-1},((2n+1)g)^{\frac{2m}{g}-1}\\}$

is a graph obtained by splicing some $2\times 2$ squares from left to right
and from bottom to top. Note that the number of vertices in the interior of
$H$ and $G_{0}$ is equal. By proof of Lemma 5.1, the interior of $G_{0}$ has
an odd number of vertices and thus $C$ is not $M$-alternating. Therefore, $C$
contains exactly four vertices which is the cycle $S$.

If $((2n+1)k)^{0}((2n+1)k-1)^{0}\notin M$, then $S$ is not $M$-alternating.
Hence all cycles of $G^{\prime}$ are not $M$-alternating and this placement is
what we required. So we assume that $((2n+1)k)^{0}((2n+1)k-1)^{0}\in M$.
Translating the marked vertices up by two rows shown in Fig. 8(b), by a
similar argument, it suffices to consider the case that
$((2n+1)k-2)^{0}((2n+1)k-3)^{0}\in M$. Thus, it suffices to consider the case
that $C_{0}$ and $C_{\frac{2m}{g}-1}$ have the same form on $M$. If we
translate the marked vertices $T$ to right by one column, then we only to
consider the case that $\\{C_{\frac{2m}{g}-1},C_{0},C_{1}\\}$ have the same
form on $M$. Go on like this, we suffice to consider the case that
$\\{C_{\frac{2m}{g}-1},C_{0},C_{1},\dots,C_{\frac{2m}{g}-2}\\}$ have the same
form on $M$. Then $C_{\frac{2m}{g}-2}$ and $C_{\frac{2m}{g}-1}$ have different
form on $M$. By previous argument, we have done. ∎

## References

  * [1] P. Afshani, H. Hatami, E. S. Mahmoodian, On the spectrum of the forced matching number of graphs, Australas. J. Combin. 30 (2004) 147-160.
  * [2] George P. Barker, Manifestations of Polya’s counting theorem, Linear Algebra Appl. 32 (1980) 209-232.
  * [3] H. Cohn, R. Kenyon, J. Propp, A variational principle for domino tilings, J. Amer. Math. Soc. 14(2) (2001) 297-346.
  * [4] M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Phys. Rev. 124 (1961) 1664-1672.
  * [5] J. C. Fournier, Combinatorics of perfect matchings in plane bipartite graphs and application to tilings, Theor. Comput. Sci. 303 (2003) 333-351.
  * [6] J. Freire, C. Klivans, P. H. Milet, N. C. Saldanha, On the connectivity of spaces of three-dimensional domino tilings, Trans. Amer. Math. Soc. 375(3) (2022) 1579-1605.
  * [7] W. Gründler, Signifikante Elektronenstrukturen fur benzenoide Kohlenwasserstoffe, Wiss. Z. Univ. Halle 31 (1982) 97-116.
  * [8] F. Harary, D. J. Klein, T. P. Živković, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem. 6(3) (1991) 295-306.
  * [9] P. W. Kasteleyn, The statistics of dimers on a lattice I. The number of dimer arrangements on a quadratic lattice, Physica 27(12) (1961) 1209-1225.
  * [10] K. J. Klein, M. Randić, Innate degree of freedom of a graph, J. Comput. Chem. 8(4) (1987) 516-521.
  * [11] S. Kleinerman, Bounds on the forcing numbers of bipartite graphs, Discrete Math. 306(1) (2006) 66-73.
  * [12] Q. Li, Study on the Matching Extension of Graphs in Surfaces, Ph.D. Thesis, Lanzhou University, 2012.
  * [13] F. Lin, A. Chen, J. Lai, Dimer problem for some three dimensional lattice graphs, Physica A 443 (2016) 347-354.
  * [14] Q. Liu, J. Wang, C. Li, H. Zhang, Components of domino tilings under flips in quadriculated cylinder and torus, preprint, 2022, https://arxiv.org/abs/2211.10935.
  * [15] M. Loebl, On the dimer problem and the ising problem in finite 3-dimensional lattices, Electron. J. Combin. 9 (2002) R30.
  * [16] M. Randić, Resonance in catacondensed benzenoid hydrocarbons, Int. J. Quantum Chem. 63(2) (1997) 585-600.
  * [17] T. Regge, R. Zecchina, Exact solusion of the ising model on group lattices of genus $g>1$, J. Math. Phys. 37 (1996) 2796-2814.
  * [18] T. Regge, R. Zecchina, Combinatoriacl and topological approach to the 3D ising model, J. Phys. A 33 (2000) 741-761.
  * [19] N. C. Saldanha, C. Tomei, M. A. Jr. Casarin, D. Romualdo, Spaces of domino tilings, Discrete Comput. Geom. 14(2) (1995) 207-233.
  * [20] H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics-an exact result, Phil. Mag. 6(8) (1961) 1061-1063.
  * [21] C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323(2) (1991) 605-635.
  * [22] W. P. Thurston, Conway’s tiling groups, Amer. Math. Monthly 97(8) (1990) 757-773.
  * [23] H. Zhang, The connectivity of Z-transformation graphs of perfect matchings of polyominoes, Discrete Math. 158(1-3) (1996) 257-272.
  * [24] H. Zhang, Z-transformation graphs of perfect matchings of plane bipartite graphs: a survey, MATCH Commun. Math. Comput. Chem. 56(3) (2006) 457-476.
  * [25] F. Zhang, X. Guo, R. Chen, Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72(1-3) (1988) 405-415.
  * [26] H. Zhang, F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105(1-3) (2000) 291-311.
  * [27] H. Zhang, F. Zhang, H. Yao, Z-transformation graphs of perfect matchings of plane bipartite graphs, Discrete Math. 276(1-3) (2004) 393-404.