# TaCo: Enhancing Cross-Lingual Transfer for Low-Resource Languages in LLMs
through Translation-Assisted Chain-of-Thought Processes

Bibek Upadhayay1 and Vahid Behzadan, Ph.D.2 1Bibek Upadhayay is a graduate
student at the University of New Haven, West Haven, CT, USA
<EMAIL_ADDRESS>2Vahid Behzadan, Ph.D. is an assistant professor of
computer science at the University of New Haven, West Haven, CT, USA
<EMAIL_ADDRESS>
###### Abstract

LLMs such as ChatGPT and PaLM can be utilized to train on a new language and
revitalize low-resource languages. However, it is evidently very costly to
pretrain pr fine-tune LLMs to adopt new languages. Another challenge is the
limitation of benchmark datasets and the metrics used to measure the
performance of models in multilingual settings. This paper proposes cost-
effective solutions to both of the aforementioned challenges. We introduce the
Multilingual Instruction-Tuning Dataset (MITS), which is comprised of the
translation of Alpaca-52K, Dolly-15K, and Vicuna Benchmark in 132 languages.
Also, we propose a new method called _TaCo: Translation-Assisted Cross-
Linguality_ , which make uses of translation in a chain-of-thought process to
instruction-tune LLMs on a new languages through a curriculum learning
process. As a proof of concept, we experimented with the instruction-tuned
Guanaco-33B model and performed further instruction tuning using the TaCo
method in three low-resource languages and one high-resource language. Our
results show that the TaCo method impresses the GPT-4 with 82% for a low-
resource language in the Vicuna Benchmark dataset, and boosts performance by
double in contrast to the performance of instruction tuning only. Our results
show that TaCo is a promising method for creating multilingual LLMs, even for
low-resource languages. We have released our datasets and the model
adapters111https://github.com/UNHSAILLab/TaCo, and encourage the research
community to make use of these resources towards advancing work on
multilingual LLMs.

##  I Introduction

Languages are not only communication tools but also rich repositories of
cultural heritage, historical archives, mediums for preserving traditions, and
unique cognitive abilities of human beings. Languages encapsulate ancestral
knowledge, traditions, and unique worldviews, providing insights into day-to-
day lives and socio-cultural diversities. Consequently, the current rate of
language extinction signifies a global crisis, with rare languages reportedly
fading into oblivion approximately every week [1]. A promising approach to the
preservation of these languages is to leverage Large Language Models (LLMs).
As the size of the LLMs increases, they are shown to improve in downstream
tasks not only in English but also in non-English languages [2] [3] [4].
OpenAI’s GPT-4 performs across 26 languages, achieving state-of-the-art scores
in the MMLU[5]dataset. LLMs can be used to analyze and revitalize low-resource
and endangered languages by teaching them vocabulary, grammar, and utilizing
available texts and resources. These non-English LLMs can facilitate the
generation of additional language resources, enhance linguistic research, and
create interactive applications to attract more users to utilize these
systems, thereby providing a technological safeguard against language
extinction. However, it is not always the case that sufficient resources are
available to train LLMs in non-English languages, especially low-resource
languages.

However, there is a scarcity of rich datasets available to train these LLMs on
non-English languages. Proprietary models such as PaLM[6] and GPT-4 [3] are
capable of understanding and performing downstream tasks in non-English
languages, but their closed model architecture and post-processed datasets are
not readily accessible to the research community. This limits academics and
independent researchers from building upon, innovating, or aligning models for
specific usage. Furthermore, these models are restricted to a limited number
of non-English languages. For example, GPT-4 only provides evaluations on the
MMLU dataset[5] for 26 languages [7], and the original technical report
remains unclear about its performance in other low-resource languages. In our
experiments, we observed that GPT 3.5 is able to handle some of the languages
not listed in their evaluation report, however the model often generates
responses mixed with other similar languages. For instance, when testing with
the Sanskrit language, the model generated responses in a mixture of Sanskrit
and Hindi. Similarly, as of the time of this study, Google’s Bard based on
PaLM [6] does not respond in certain low-resource languages. When prompted in
Sanskrit, the model states that it has only been trained to respond in a
subset of languages. Besides the challenge posed by closed models, a further
bottleneck is the limited availability of datasets for training models in low-
resource languages such as Sanskrit, Nepali, and Maithili. Although there are
a handful of datasets available for machine translation tasks, they are shown
to be insufficient for adoption by LLMs via pretraining.

The open-source community has been releasing LLMs with the model weights that
are challenging the performance of ChatGPT. Open-sourced models are pretrained
with a smaller percentage of non-English data, which limits their performance
and tends to enhance their proficiency in English only.Recently, the positive
progression towards the multilingual models can be observed with models such
BLOOM [8], POLYLM [9] , and Glot-500 [10] that are pretrained with the
inclusion of non-English languages in the training dataset. Further, fine-
tuning these models with instruction pairs enable the models to generate
responses in non-English languages as well [11].

Multilingualism in LLMs is a challenging task that requires significant
resources. The pretraining of LLMs is costly, and replicating such work is not
feasible in university labs. In addition to the challenges of pretraining and
acquiring multilingual data for pretraining, there exists the curse of
multilinguality [12], which states that as the number of languages increases,
the performance in low-resource languages decreases. Another challenge in
multilingualism is that aligning two languages with identical structures but
inverted word order is more difficult [13]. An alternative approach is the
instruction tuning with the translated dataset in a particular language to the
pre-trained base models, such as LLaMA models. Results show that these models
are capable of generating responses in non-English languages [14] [15].
However, the performance of these models are very limited. Our experimental
analysis indicate that the such models fail to provide decent performance on
benchmarks such as Vicuna Benchmark. Despite these challenges, better
multilingualism is observable in proprietary models with prompt engineering.
Huang et al. [16] introduced the Cross-Lingual Thought prompt (XLT), which
aims to enhance the multilingual capabilities of LLMs. XLT is a template
prompt designed to stimulate cross-lingual and logical reasoning skills,
thereby improving task performance across multiple languages. As a generic and
language-independent prompt, it eliminates the need to update model
parameters.

Motivated by the theory of parameter-efficient fine-tuning using LoRA[17] and
the chain-of-thought [18] process, we propose a new method called TaCo that
uses translation in the chain-of-thought process to create a multilingual
model. In this work, we used the chain-of-thought process to teach language
models to first translate the instruction to English and generate the required
response in English, and then translate it back to the low-resource languages.
The TaCo method leverages two established properties of LLMs: (1) LLMs can
show emergent capabilities with an increase in size [19], and (2) chain-of-
thought prompting elicits reasoning behaviors in the model [18]. Furthermore,
we employed a curriculum learning strategy in training [20] by utilizing the
Guanaco-33B model [21] fine-tuned on OASST1 dataset [22], and then instruction
tuning using the TaCo method via Low-Rank Adaptation (LoRA) for parameter-
efficient fine-tuning [17].

In contrast to other models trained with LoRA adapters such as Bactrian [14]
for multilingualism, or where instruction tuning is performed on the LLaMA
base model [15], we used the fine-tuned Guanaco-33B model. The open-source
Guanaco models are fine-tuned with QLoRa tuning [21] of the LLAMA base model
on the OASST1 dataset [22]. The main reason for this approach is to instruct
the existing state-of-the-art model on how to translate and elicit responses
in the respective languages. Additionally, it reduces the need to fine-tune
the model from scratch, thereby saving on overall training costs.

We present our contribution as follows:

  1. 1.

We present the Multilingual Instruction-Tuning Dataset (MITDS), which consists
of the translated Alpaca-52K [11] and Dolly-15K [23]. These datasets,
translated using Google Cloud Translation, cover 132 languages.

  2. 2.

We propose a new method called TaCo for instruction-tuning LLMs to learn new
languages.

  3. 3.

We also present the Multilingual Vicuna Benchmark, which is a dataset
comprised of translation of the Vicuna Benchmark [24] in 132 languages and
made them publicly available.

  4. 4.

We evaluate four TaCo models on the Vicuna Benchmark, for 3 low-resource
languages (Nepali, Sanskrit, and Maithili), as well as a high-resource
language: Persian.

  5. 5.

We release the adapters for the aforementioned four language models for public
use.

##  II Preliminaries

###  II-A Instruction Tuning

Instruction tuning refers to the fine-tuning of the model on a mixture of
tasks expressed via natural language instructions. The fundamental idea is to
increase the ability of language models to follow instructions, even for
unseen tasks. As presented by Wei et al. [25], instruction tuning on the 175B
parameter model FLAN resulted in superior performance on zero-shot tasks. An
example of instruction tuning is: _’Please translate the following sentence
into Nepali: ”Mount Everest is 8848 meters high.”’_.

###  II-B PeFT LoRA

Parameter-Efficient Fine-Tuning (PeFT) is a library that allows for the
further training of pre-trained LLMs more efficiently. Instead of fine-tuning
the entire model’s weights, PeFT methods only fine-tune a small number of
model parameters. This approach significantly decreases the computational and
storage costs. LoRA [17] is a method for parameter-efficient fine-tuning that
freezes the pre-trained model’s weights and injects trainable rank
decomposition matrices into each layer of the transformer architecture, thus
reducing the number of training parameters. LoRA allows a pre-trained model to
be shared and used to build small modules for different tasks. This shared
model can be frozen and can efficiently switch tasks by replacing the
adapters.

###  II-C chain-of-thought

Wie et al. [18] introduced a technique to improve the reasoning ability of
LLMs by prompting them to generate a series of intermediate steps before the
final answer, a method known as Chain-of-Thought (CoT). This process mimics
the rationale of human thought processes when solving complex reasoning tasks,
such as arithmetic problems, where the problem can be broken down into
intermediate steps and solved accordingly. In addition to decomposing multi-
step problems into intermediate steps, chain-of-thought also provides insights
into the model’s behavior, showing how it arrived at a specific answer. When
applied to LLMs, the chain-of-thought technique demonstrated that chain-of-
thought is an emergent property of model scaling, increasing the model’s
ability to solve arithmetic reasoning tasks, commonsense reasoning tasks, and
symbolic reasoning tasks.

###  II-D Evaluating LLMs using GPT-4: The Vicuna Benchmark

Chiang et al. [26] proposed using large language models (LLMs) as alternatives
to human evaluation for assessing texts. Their study compared the results of
LLM evaluations with expert human evaluations in two NLP tasks: open-ended
story generation and adversarial attacks. They found that LLM evaluations were
consistent with human evaluations, highlighting the potential use of LLMs for
quality assessment while acknowledging the associated limitations and ethical
considerations. Chiang et al. [24] also introduced the Vicuna Benchmark, which
includes 80 questions from nine different categories, to evaluate LLMs by
asking GPT-4 to serve as the judge. The categories are 1) generic, 2)
knowledge, 3) roleplay, 4) common-sense, 5) Fermi, 6) counterfactual, 7)
coding, 8) math, and 9) writing.

##  III Related Work

There are two broad categories of approaches for training LLMs for
multilingual purposes: 1) pretraining on multilingual data, and 2) fine-tuning
in a new language. Devlin et al. [27] proposed multilingual-BERT pretrained
model based on masked language modeling. Conneau et al. [12] presents the _(_
curse of multilinguality) in terms of the trade off, as they increase the
number of languages leads to the better performance on low-resource languages.
However, there was a point beyond which adding more languages starts to
degrade the overall performance on both monolingual and cross-lingual tasks.
Authors trained XLM-R model by increasing the training examples and training
the cross-lingual presentations from more than 2 terabytes of Common Crawl
data. Chi et al. [28] further improved these models using two discriminative
pretraining tasks: multilingual replaced token detection that replaces tokens
in multilingual sentences, and translation replaced token detection that build
input sequences by replacing tokens in translation pairs. In this approach,
the model learns to distinguish the replaced tokens in the corrupted input
sequences in contrast to recovering masked tokens. As a result the XLM-E model
obtained better cross-lingual transferability with less computation cost.
Dufter et al. [13] used small BERT models and trained on the synthetic data
along with natural data to create multilingual BERT using a multilingual
pretraining setup that modifies the masking strategy using VecMap which is an
unsupervised embedding alignment.

Goyal et al. [2] trained two models of 3.5B and 10.7B parameters called XLM-
RXL and XLM-RXXL to show that the larger models are better on cross-lingual
understating benchmarks and perform in competitive manner.The experiment
suggested that the crosslingual large language models show the zero shot
learning capabilities in low resource language as well. However, the fine-
tuned performance is significantly better than the zero-shot capabilities
performances.

Scao et al. [8] created an open source multi langauge model called Bloom
consist of 176B-parameter. BLOOM is a decoder-only Transformer language model
that was trained on the ROOTS corpus, a dataset comprising hundreds of sources
in 46 natural and 13 programming languages. Authors trained the model in six
different sizes and also performed multitask finetuning (similar to T0 and
FLAN model) and contrastive finetuning. Muennighoff et al. [29] performed
multitask prompted finetuning to the BLOOM and mT5 model families and produced
BLOOMZ and mT0 variants. Authors experiment showed that finetuning large
language models on English tasks with English prompts also allowed for task
generalization to non-English language that were appeared only in the
pretraining corpus. And, showed that finetuning with the machine-translated
prompts in non-English language leads to the better performance. BLOOM [8]
itself was pretrained with 46 natural languages, Muennighoff et al. extended
the by adding additional tasks such as translation tasks and program
synthesis. In terms of task generalization authors found that the even in
multilingual large language models finetuned on prompted multitask mixtures
generalizes to unseen tasks.

Haonan et al. [14] trained the two models $Bactrian-X_{l}lama$ and $Bactrian-
X_{b}loom$ with LoRA approach. The model is trained with instruction dataset
presented in 52 languages, Authors, measured the performance of this model
against the models such as LLaMA-7B, Alpaca-LoRA-7B, LLaMA-13B, Alpaca-
LoRA-13B, BLOOM-7B, and BLOOM-13B.

Wei et al. [9] trained and released a 13-B Polyglot Large Language Model
(POLYLM) pretrained with 640B tokens with 32% of non-English multilingual
languages. The authors used a curriculum strategy Authors proposed a
curriculum strategy. The training process is divided into two parts, in the
first one the whole pre-training dataset was used to train a base model to
learn commonsense generalization and in the second stage , a high quality
subset of the pre-training data was used to make model learn multilingualism.

Imanigooghari et al. [10] pretrained the Glot500-m model that is pretrained
with 511 predominantly low-resource languages.Authors collected the corpus of
more than thousand languages and used the subset of the language to pretrained
the model. The evaluation of the multilingual model is a challenging task, the
authors validate their work with …

Kudugunta et al. [30] used the Semi-Supervised LangID approach by Caswell et.
al .[31] to train a document-level LangID model on 498 languages and obtained
CommonCrawl annotations to create document-level monolingual dataset. Authors
performed manual auditing of the dataset to remove the noisy data. The dataset
was used to train the multilingual machine translation models ranging in
different sizes up to 10.7B parameters. Authors fine-tuned the model by
randomly mixing the original and the back translated data to discourage
hallucinations.

##  IV Dataset

We first translated the Alpaca-52K-GPT4 and Dolly-15K datasets using the
Google Cloud Translation service into 132 languages. However, due to
limitations in computational resources available to us, our experiment
continued with a selection of three low-resource languages (Sanskrit, Nepali,
and Maithili), as well as one high-resource language (Persian). As machine
learning translations are prone to _translationese_ , where the translated
text deviates from the native language norms due to overly literal
translation, foreign syntax, redundancies, and unusual phrases or word choices
[32], we performed a manual evaluation of the translation quality. Initially,
we sampled 1000 sentences from each language and calculated the BLEU score
using ScarceBLEU [33], ChrF [34], and the Translation Error Rate (TER) [35]
through a round-trip process from English to the target language (en-xx) and
back from the target to English (xx-en). We provide the evaluation metric
scores for these three low-resource languages in Table I.

Language | BLEU | CHRF++ | TER
---|---|---|---
Sanskrit | 65.23 | 84.62 | 19.43
Nepali | 69.68 | 87.37 | 15.02
Persian | 62.42 | 80.72 | 20.61
Maithili | 63.65 | 84.88 | 19.58
TABLE I: Translation Evaluation Metrics for Low Resources Languages

For the purposes of our multilingual fine-tuning process, we transformed each
pair of the translated instruction dataset into the style of the chain-of-
thought. In chain-of-thought prompting, the model is shown how to decompose a
complex problem into reasoning steps. We consider the issue of cross-
linguality as a complex problem and decompose it by introducing step-by-step
translation, similar to a chain of thought. We combine the English dataset
with a new language to create question-answer pairs, called TaCo datasets. In
TaCo datasets, the instruction is in a non-English language and the output
comprises responses in both English and the non-English language. The output
process starts with translating the instruction to English, creating the
response in English, and then translating the response back into the non-
English language. The structure of a single data point is as follows:

Prompt Input: Translate the following instructions from xx to English,
formulate a response in English, and then translate that response back into
xx.

{
’instruction’: _instruction in xx_ ,
’input’: _input in xx_ ,
’output’: ’Instruction in English: _instruction in en_.
Response in English: _response in en_
Response in xx: _response in xx_
}

In the above example prompt, the input instructs the model to first translate
the instruction into English, then provide the response in English, and
finally, translate the English response into the target language. The _input_
of the prompt is in the target language, while the _output_ consists of the
instruction in English, the response in English, and finally, the response in
the non-English target language. Simply put, the model is asked to generate
these three elements for each question, thereby being forced to learn
translation as well as to understand another language. We refrain from
translating the _input_ in the target language (xx) into English in the
_output_ , as this approach encourages the model to understand and use them.

We merged the Alpaca-52K and Dolly-15K datasets, resulting in a collection of
67K question-answer prompts.

##  V Training

Our training follows a curriculum learning strategy where we train the _pre_
-fine-tuned model which has already produced state-of-the-art results in
generating responses in English. Accordingly, we selected the Gaunaco-33B
fine-tuned model and further instruction-tuned it with our TaCo method. We
transformed the dataset to align with our TaCo method as mentioned in Section
IV. The hyperparameters for the model’s training are presented in Table II,
while the hyperparameters for the LoRa configuration are depicted in Table II.
Our training targeted four LoRA modules: q_proj, k_proj, v_proj, and o_proj.We
present our evaluation loss a in Figure 1.

Parameter | Value
---|---
batch_size | 128
micro_batch_size | 4
learning_rate | 3e-4
cutoff_len | 2000
val_set_size | 2000
TABLE II: Training Parameters Parameter | Value
---|---
lora_r | 32
lora_alpha | 64
lora_dropout | 0.05
lora_target_modules | q_proj, k_proj, v_proj, o_proj
TABLE III: LoRA Hyperparameters Figure 1: Evaluation Loss over steps for four
different TaCo models.

##  VI Evaluation with GPT-4 as Judge

In our model evaluation we used Vicuna Benchmark [24], however, the benchmark
is available only in English. We translated the benchmark dataset into 132
languages using Google Cloud Translation and have made them publicly
available. To evaluate our TaCo models, we followed the single answer
evaluation method in which we asked the GPT-4 model to judge the answers
generated by our models. We generated answers for the questions in the
following four languages: Nepali, Persian, Sanskrit, and Maithili. An example
of the output generated from the model is depicted in the Fig. 2.

Figure 2: Instruction and the response generated using TaCo method.

As we can see, the input to the model is in the native language, with the
system prompt provided in English. This is because the underlying model being
used was fine-tuned in the English language and is therefore capable of
understanding the system prompt and acting accordingly. In the model’s
response, we can observe that the instruction in Nepali is initially
translated to English, and then a response is generated in English followed by
a response in Nepali. One of the main challenges faced in this approach is the
token limit while generating responses. Open-ended question responses are
generally longer, and when implemented using the TaCo method, need to be first
generated in English and then translated into the respective language, often
exceeding the maximum token limit in the LLaMA model, i.e., 2048 [36].

This typically results in longer English response generation and incomplete
response generation in the native language due to model token limitations. We
resolved this by appending a simple instruction to the prompt, specifying that
the model response should not exceed six sentences. After exhaustive trials,
we found that six sentences is the sweet spot. Moreover, we also modified the
system prompt in the evaluation benchmark by adding an extra line: ’Do not
allow the length of the responses to influence your evaluation’, which will
make the GPT-4 not judge based on the length of the answer. The evaluation
results are presented in Table IV.

##  VII Results

We present our Vicuna Benchmark results in Table IV, along with a breakdown of
the results by category and language, as well as a graph in Fig 3. We obtained
an average score of 88% for Nepali, 80% for Sanskrit, 82% for Maithili, and
84% for the Persian model combining all nine categories. It can be seen that
all TaCo models score higher than 7, except in math. The Sanskrit model has
the lowest performance in the math category. Since programming language is
typically written in English, we removed coding from the overall score to
better assess the models’ performance.

Category | Nepali | Sanskrit | Persian | Maithili
---|---|---|---|---
common sense | 8.55 | 8.30 | 8.60 | 7.80
counterfactual | 8.90 | 8.30 | 8.46 | 8.30
fermi | 7.70 | 7.70 | 8.20 | 7.50
generic | 9.00 | 9.13 | 9.00 | 9.30
knowledge | 9.55 | 9.42 | 9.25 | 8.80
math | 9.67 | 3.33 | 6.33 | 7.00
roleplay | 8.35 | 8.90 | 8.60 | 7.80
writing | 8.80 | 8.95 | 8.65 | 9.30
Overall average | 8.81 | 8.00 | 8.39 | 8.22
TABLE IV: Performance of different categories across languages. Category | Nep-IT | Nep-TaCo | Per-IT | Per-TaCo
---|---|---|---|---
common-sense | 4.00 | 8.55 | 6.30 | 8.60
counterfactual | 1.80 | 8.90 | 4.60 | 8.46
fermi | 3.10 | 7.70 | 3.00 | 8.20
generic | 6.30 | 9.00 | 4.40 | 9.00
knowledge | 4.70 | 9.55 | 5.25 | 9.25
math | 4.33 | 9.67 | 5.67 | 6.33
roleplay | 3.60 | 8.35 | 3.85 | 8.60
writing | 3.60 | 8.80 | 4.10 | 8.65
Overall Average | 3.93 | 8.81 | 4.65 | 8.39
TABLE V: Comparison of Instruction Tuned (IT) models vs TaCo models

##  VIII Ablation Study

To test the TaCo method, we evaluated the models by simply performing the
instruction-tuning. We selected one low-resource language, Nepali, and one
high-resource language, Persian, and trained the Guanaco-33B model. Both
models were instruction-tuned with the respective language translations of the
Alpaca-52K and Dolly-15K datasets, using the same hyperparameters. As seen in
Table V, our TaCo method significantly outperforms the conventional approach,
with almost double the average score. We also present the results in Figure 3,
showing scores in each category.

Figure 3: Comparison of Vicuna Benchmark scores by categories for different
TaCo models and the Instruction Tuned (IT) model.

##  IX Discussion

As the size of Language Learning Models (LLMs) increases, so does their
performance in downstream tasks. Shi et al. [37] used chain-of-thought
reasoning to solve multilingual grade school math problems, demonstrating that
the chain-of-thought approach could also be applied to other common-sense
problems, utilizing Palm-540B. The authors leveraged few-shot transfers to
exhibit the model’s capabilities when pre-trained on a multilingual dataset.
Similarly in our work, we initially experimented with few-shot examples
through the chain-of-thought process in the base model, Guanaco-33B. However,
our preliminary experiment with less than 25 samples disclosed that the model
was unable to generate responses in the requested non-English language. This
inability could be attributed to the lack of exposure or the extremely limited
presence of a specific language dataset during the base model’s training. As a
result, the model cannot respond in a language it has not encountered.
Nonetheless, further LoRA instruction tuning revealed the model’s capability
to generate responses in that particular language.

Another preliminary experiment revealed that the instruction-tuned model,
capable of generating responses in non-English languages, encountered several
issues such as broken grammar, lack of information (like facts, history, and
significant events), hallucinations, and repetitive sentences during
generation. However, most of these issues were resolved when we implemented
our proposed TaCo method. This improvement is evident in our average results,
which display an accuracy of 80% or above for each language and an average
accuracy of 80% in the common sense category across all four languages.

The concept behind the curriculum learning strategy is to start with basic
principles and gradually progress towards more complicated ones. Similarly, we
equate learning to answer in English as an easier task and answering in a low-
resource language as a more challenging one. Hence, we used the existing
state-of-the-art Guanaco-33B model. Once the model successfully generates
responses in English, the second part is to train it to answer in other
languages. This process mirrors how the human brain works when a person is
learning a second language. Initially, they analyze the question in their
native language, process the answer in their native language, and finally
articulate the answer in English. This process may evolve as the person
becomes more fluent in English. Likewise, our TaCo method follows a similar
strategy. The first step is to translate into English, then generate the
answer in English, and finally translate it back into the non-English
language. This approach abides by the structure of the chain-of-thought
process, where we dissect a complicated problem into a sequence of simpler
tasks, with translation being the first and last steps.

The advantage of this approach is that it utilizes the pre-training knowledge
from the English language and leverages it to generate responses in non-
English. This allows the model to scan its parameters for more factual
information and avoid hallucinations. As a result, we observe an average of
92% accuracy in the knowledge category across the four languages.

Despite the model’s proficiency in answering non-English questions and
achieving an impressive score of 83% by GPT-4 standards, this approach has its
limitations. The first limitation is the token limit. Since the model needs to
generate answers in both languages, the number of tokens required often
exceeds the maximum token limit. This can prevent the model from providing
lengthy responses. Secondly, the model loses its native-language creativity,
such as creating poems or rhyming sentences in the target language. The model
will answer every query only from the perspective of the English language.

Additionally, there are two significant challenges associated with
multilinguality: 1) token counts, and 2) time required for response
generation. The number of tokens needed to generate a single sentence in non-
English languages might be much larger than in English. We observed that this
was notably true for the four languages we examined. As the number of tokens
increases, so does the cost and the time taken to generate the response.

In Fig 4, we display the time taken to generate first six question response in
different languages. We can compare the time difference between English and
the other languages. The English response was generated by the base model,
meaning it does not employ the TaCo method. As a rough estimate, we can double
the time taken in English to compare it with the other languages, as the model
utilizes the TaCo method for generation. However, even in these cases, the
time taken for the other languages is significantly higher.

Figure 4: Time taken by six question form Vicuna Benchmark to generate
response in corresponding language.

##  X Conclusion

In this work, we introduced a new approach called TaCo to create a
multilingual model by utilizing translation in the chain-of-thought process.
Our TaCo method impresses the GPT-4, achieving an average accuracy of 82% on
the Vicuna Benchmark dataset. The results demonstrate that TaCo can
effectively generate a multilingual model at a reasonable cost. We have
released the model weights and datasets. However, we acknowledge the
limitations of this paper, including the lack of robustness and toxicity
tests. Additionally, the challenge of the token limit remains. Our released
models are large, and future work will focus on achieving better results with
smaller models. In conclusion, the emergent behavior of LLMs, amplified by
translation in the chain-of-thought process, can enable multilingualism within
these models.

## References

  * [1] UNESCO International Institute for Higher Education in Latin America and the Caribbean (IESALC), “A decade to prevent the disappearance of 3,000 languages,” https://www.iesalc.unesco.org/en/2022/02/21/a-decade-to-prevent-the-disappearance-of-3000-languages/, 2022, accessed: 2023-04-01.
  * [2] N. Goyal, J. Du, M. Ott, G. Anantharaman, and A. Conneau, “Larger-scale transformers for multilingual masked language modeling,” _arXiv preprint arXiv:2105.00572_ , 2021.
  * [3] OpenAI, “Gpt-4 technical report,” 2023.
  * [4] A. Conneau and G. Lample, “Cross-lingual language model pretraining,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [5] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt, “Measuring massive multitask language understanding,” _arXiv preprint arXiv:2009.03300_ , 2020.
  * [6] R. Anil, A. M. Dai, O. Firat, M. Johnson, D. Lepikhin, A. Passos, S. Shakeri, E. Taropa, P. Bailey, Z. Chen _et al._ , “Palm 2 technical report,” _arXiv preprint arXiv:2305.10403_ , 2023.
  * [7] OpenAI, “Gpt-4 research,” 2023. [Online]. Available: https://openai.com/research/gpt-4
  * [8] T. L. Scao, A. Fan, C. Akiki, E. Pavlick, S. Ilić, D. Hesslow, R. Castagné, A. S. Luccioni, F. Yvon, M. Gallé _et al._ , “Bloom: A 176b-parameter open-access multilingual language model,” _arXiv preprint arXiv:2211.05100_ , 2022.
  * [9] X. Wei, H. Wei, H. Lin, T. Li, P. Zhang, X. Ren, M. Li, Y. Wan, Z. Cao, B. Xie _et al._ , “Polylm: An open source polyglot large language model,” _arXiv preprint arXiv:2307.06018_ , 2023.
  * [10] A. ImaniGooghari, P. Lin, A. H. Kargaran, S. Severini, M. J. Sabet, N. Kassner, C. Ma, H. Schmid, A. F. Martins, F. Yvon _et al._ , “Glot500: Scaling multilingual corpora and language models to 500 languages,” _arXiv preprint arXiv:2305.12182_ , 2023.
  * [11] B. Peng, C. Li, P. He, M. Galley, and J. Gao, “Instruction tuning with gpt-4,” _arXiv preprint arXiv:2304.03277_ , 2023.
  * [12] A. Conneau, K. Khandelwal, N. Goyal, V. Chaudhary, G. Wenzek, F. Guzmán, E. Grave, M. Ott, L. Zettlemoyer, and V. Stoyanov, “Unsupervised cross-lingual representation learning at scale,” _arXiv preprint arXiv:1911.02116_ , 2019.
  * [13] P. Dufter and H. Schütze, “Identifying elements essential for bert’s multilinguality,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2020, pp. 4423–4437.
  * [14] H. Li, F. Koto, M. Wu, A. F. Aji, and T. Baldwin, “Bactrian-x: A multilingual replicable instruction-following model with low-rank adaptation,” _arXiv preprint arXiv:2305.15011_ , 2023.
  * [15] tloen, “alpaca-lora,” 2023.
  * [16] H. Huang, T. Tang, D. Zhang, W. X. Zhao, T. Song, Y. Xia, and F. Wei, “Not all languages are created equal in llms: Improving multilingual capability by cross-lingual-thought prompting,” _arXiv preprint arXiv:2305.07004_ , 2023\.
  * [17] E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen, “Lora: Low-rank adaptation of large language models,” _arXiv preprint arXiv:2106.09685_ , 2021.
  * [18] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou _et al._ , “Chain-of-thought prompting elicits reasoning in large language models,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 24 824–24 837, 2022.
  * [19] J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler _et al._ , “Emergent abilities of large language models,” _arXiv preprint arXiv:2206.07682_ , 2022.
  * [20] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, “Curriculum learning,” in _Proceedings of the 26th annual international conference on machine learning_ , 2009, pp. 41–48.
  * [21] T. Dettmers, A. Pagnoni, A. Holtzman, and L. Zettlemoyer, “Qlora: Efficient finetuning of quantized llms,” _arXiv preprint arXiv:2305.14314_ , 2023.
  * [22] A. Köpf, Y. Kilcher, D. von Rütte, S. Anagnostidis, Z.-R. Tam, K. Stevens, A. Barhoum, N. M. Duc, O. Stanley, R. Nagyfi _et al._ , “Openassistant conversations–democratizing large language model alignment,” _arXiv preprint arXiv:2304.07327_ , 2023.
  * [23] M. Conover, M. Hayes, A. Mathur, J. Xie, J. Wan, S. Shah, A. Ghodsi, P. Wendell, M. Zaharia, and R. Xin. (2023) Free dolly: Introducing the world’s first truly open instruction-tuned llm. [Online]. Available: https://www.databricks.com/blog/2023/04/12/dolly-first-open-commercially-viable-instruction-tuned-llm
  * [24] W.-L. Chiang, Z. Li, Z. Lin, Y. Sheng, Z. Wu, H. Zhang, L. Zheng, S. Zhuang, Y. Zhuang, J. E. Gonzalez _et al._ , “Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality,” _See https://vicuna. lmsys. org (accessed 14 April 2023)_ , 2023.
  * [25] J. Wei, M. Bosma, V. Y. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le, “Finetuned language models are zero-shot learners,” _arXiv preprint arXiv:2109.01652_ , 2021.
  * [26] C.-H. Chiang and H.-y. Lee, “Can large language models be an alternative to human evaluations?” _arXiv preprint arXiv:2305.01937_ , 2023.
  * [27] J. D. M.-W. C. Kenton and L. K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of naacL-HLT_ , vol. 1, 2019, p. 2.
  * [28] Z. Chi, S. Huang, L. Dong, S. Ma, B. Zheng, S. Singhal, P. Bajaj, X. Song, X.-L. Mao, H. Huang, and F. Wei, “XLM-E: Cross-lingual language model pre-training via ELECTRA,” in _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Dublin, Ireland: Association for Computational Linguistics, May 2022, pp. 6170–6182. [Online]. Available: https://aclanthology.org/2022.acl-long.427
  * [29] N. Muennighoff, T. Wang, L. Sutawika, A. Roberts, S. Biderman, T. L. Scao, M. S. Bari, S. Shen, Z.-X. Yong, H. Schoelkopf _et al._ , “Crosslingual generalization through multitask finetuning,” _arXiv preprint arXiv:2211.01786_ , 2022.
  * [30] S. Kudugunta, I. Caswell, B. Zhang, X. Garcia, C. A. Choquette-Choo, K. Lee, D. Xin, A. Kusupati, R. Stella, A. Bapna _et al._ , “Madlad-400: A multilingual and document-level large audited dataset,” _arXiv preprint arXiv:2309.04662_ , 2023.
  * [31] I. Caswell, T. Breiner, D. van Esch, and A. Bapna, “Language id in the wild: Unexpected challenges on the path to a thousand-language web text corpus,” _arXiv preprint arXiv:2010.14571_ , 2020.
  * [32] A. Borah, “Translationese: A brief introduction,” https://anganaborah.medium.com/translationese-a-brief-introduction-db4575c0ee69, accessed: 16-Sep-2022.
  * [33] M. Post, “A call for clarity in reporting bleu scores,” _arXiv preprint arXiv:1804.08771_ , 2018.
  * [34] M. Popović, “chrf++: words helping character n-grams,” in _Proceedings of the second conference on machine translation_ , 2017, pp. 612–618.
  * [35] M. Snover, B. Dorr, R. Schwartz, L. Micciulla, and J. Makhoul, “A study of translation edit rate with targeted human annotation,” in _Proceedings of the 7th Conference of the Association for Machine Translation in the Americas: Technical Papers_ , 2006, pp. 223–231.
  * [36] “Llama — transformers 4.7.0 documentation.” [Online]. Available: https://huggingface.co/docs/transformers/model˙doc/llama
  * [37] F. Shi, M. Suzgun, M. Freitag, X. Wang, S. Srivats, S. Vosoughi, H. W. Chung, Y. Tay, S. Ruder, D. Zhou _et al._ , “Language models are multilingual chain-of-thought reasoners,” _arXiv preprint arXiv:2210.03057_ , 2022.


# The size of the betti table of binomial edge ideals

Antonino Ficarra, Emanuele Sgroi  Antonino Ficarra, Department of mathematics
and computer sciences, physics and earth sciences, University of Messina,
Viale Ferdinando Stagno d’Alcontres 31, 98166 Messina, Italy
<EMAIL_ADDRESS>Emanuele Sgroi, Department of mathematics and computer
sciences, physics and earth sciences, University of Messina, Viale Ferdinando
Stagno d’Alcontres 31, 98166 Messina, Italy<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite simple graph with $n$ non isolated vertices, and let
$J_{G}$ its binomial edge ideal. We determine all pairs
$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))$,
where $G$ ranges over all finite simple graphs with $n$ non isolated vertices,
for any $n$.

###### Key words and phrases:

binomial edge ideals, betti tables, projective dimension, regularity

###### 2020 Mathematics Subject Classification:

Primary 13F20; Secondary 13H10

.

## Introduction

One never-ending source of inspiration in Combinatorial Commutative Algebra is
the study of the minimal free resolutions of graded ideals. Let
$R=K[x_{1},\dots,x_{n}]$ be the standard graded polynomial ring, with $K$ a
field, and let $I\subset R$ a graded ideal. The behaviour of the minimal
resolution of $I$ is hard to predict. Two important homological invariants of
$I$, that provide a measure of the complexity of its minimal resolution, are
the projective dimension, $\operatorname{proj\phantom{,}\\!dim}(I)$, and the
regularity, $\operatorname{reg}(I)$. The pair
$(\operatorname{proj\phantom{,}\\!dim}(I),\operatorname{reg}(I))$ determines
the size of the Betti table of $I$.

A central question is the following. For a given class $\mathcal{C}$ of graded
ideals of $R$, can we determine the set of the sizes of the Betti tables of
the ideals in $\mathcal{C}$? That is, can we determine all pairs
$(\operatorname{proj\phantom{,}\\!dim}(I),\operatorname{reg}(I))$,
$I\in\mathcal{C}$? Such a problem is very difficult, and the behaviour of
these pairs is quite mysterious. On the other hand, if the graded ideals in
$\mathcal{C}$ arise from combinatorics, as it happens in many cases, then
their combinatorial nature helps us to better understand and sometimes also
answer such a question.

A problem of this type is considered in [8]. Hereafter, for a graph $G$ we
mean a finite simple graph. Recall that the edge ideal $I(G)$ of $G$ is the
ideal generated by the monomials $x_{i}x_{j}$ where $\\{i,j\\}$ is an edge of
$G$. In [8], Hà and Hibi studied the question of determining all admissible
pairs $(\operatorname{proj\phantom{,}\\!dim}(I(G)),\operatorname{reg}(I(G)))$,
as $G$ ranges over all graphs with a given number of vertices. This question
is related to the search of a max min vertex cover and a min max independent
set. In turn, these classical problems of graph theory are known to be NP-
hard, and they received a lot of attention lately [2, 3, 4, 9]. On the other
hand, the combinatorics of $G$ yields the following surprising lower bound:
$\operatorname{proj\phantom{,}\\!dim}(I(G))\geq 2\sqrt{n}-3$. The authors
determined all pairs
$(\operatorname{proj\phantom{,}\\!dim}(I(G)),\operatorname{reg}(I(G)))$ when
the projective dimension reaches this lower bound, and also when the
regularity reaches its minimal possible value, namely
$\operatorname{reg}(I(G))=2$. The same question was posed and completely
solved by Erey and Hibi in [6], for the class of connected bipartite graphs.
Similar problems are treated in [12, 13, 14, 15, 16, 17, 19] and the
references therein.

Another family of graded ideals arising from graphs is that of binomial edge
ideals. In 2010, Herzog, Hibi, Hreinsdóttir, Kahle and Rauh in [10], and
independently, Ohtani in [24], introduced the binomial edge ideal. Let $G$ be
a graph with $n$ vertices $1,\dots,n$. Then $J_{G}$ is defined to be the
graded ideal of $S=K[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]$ generated by the
binomials $x_{i}y_{j}-x_{j}y_{i}$ for all edges $\\{i,j\\}$ of $G$. This class
of ideals generalizes the classical determinantal ideals. Indeed, $J_{G}$ may
be seen as the ideal generated by an arbitrary set of maximal minors of a
$(2\times n)$-matrix of indeterminates. An huge effort has been made to
understand the homological properties of binomial edge ideals. Consult the
survey [23] for the current state of art.

In this article, we address Hà and Hibi problem for the class of binomial edge
ideals. One would guess, as in the case of edge ideals, that this problem is
difficult, and that answering this question in an explicit fashion may not be
possible. Quite surprisingly, we succeed to deliver a fairly comprehensive and
explicit solution.

Let $n\geq 1$ be an integer. Denote by $\textup{Graphs}(n)$ the class of all
finite simple graphs with $n$ non isolated vertices. Then, we define

$\textup{pdreg}(n)\ =\
\big{\\{}(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G})):G\in\textup{Graphs}(n)\big{\\}},$

which is the set of the sizes of the Betti tables of $J_{G}$, as $G$ ranges
over all graphs with $n$ non isolated vertices. Our main result in the article
is the following theorem.
Theorem 3.1 For all $n\geq 3$,

$\displaystyle\textup{pdreg}(n)\ =\
\big{\\{}(n-2,2),(n-2,n)\big{\\}}\cup\bigcup_{r=3}^{\lfloor\frac{n}{2}\rfloor+1}\big{(}\bigcup_{p=n-r}^{2n-5}\\{(p,r)\\}\big{)}\
\cup$
$\displaystyle\cup\bigcup_{r=\lceil\frac{n}{2}\rceil+1}^{n-2}\big{(}\bigcup_{p=r-2}^{2n-5}\\{(p,r)\\}\big{)}\cup
A_{n},$

where $A_{n}=\\{(p,r)\in\textup{pdreg}(n):r=n-1\\}$.

The reader may see that when the regularity is $n-1$ we leave the set $A_{n}$
not determined. Indeed, our experiments show a quite unexpected behaviour.
Conjecture 3.4 Let $G$ be a graph with $n\geq 7$ non isolated vertices.
Suppose that $\operatorname{reg}(J_{G})=n-1$. Then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq n$.

The article is structured as follows. In Section 1, we state some general
bounds for the projective dimension and the regularity of binomial edge
ideals. The proof of Theorem 3.1 is by induction on the number of vertices of
the graph. On the other hand, there are some special graphs giving some of the
pairs $(p,r)\in\textup{pdreg}(n)$ that we did not obtain by inductive
arguments. In Section 2, we discuss these special classes of graphs. They give
the pairs $(p,r)\in\textup{pdreg}(n)$ with $p=2n-5,2n-6$, or $r=3,n-2$.
Section 3 contains the main result in the article. Our answer is nearly
complete. Indeed, only for the graphs with almost maximal regularity, namely
$\operatorname{reg}(J_{G})=n-1$, we do not know yet the projective dimension.
It would be interesting to classify the binomial edge ideals with almost
maximal regularity.

We gratefully acknowledge the use of Macaulay2 [7] and in particular of the
package NautyGraphs [21].

##  1\. General bounds for the betti table of binomial edge ideals

Let $I$ be a graded ideal of a standard graded polynomial ring
$R=K[x_{1},\dots,x_{n}]$, where $K$ is a field. Then $I$ posses a unique
minimal graded free resolution

${\mathbb{F}}\ \ :\ \ \cdots\rightarrow F_{i}\rightarrow
F_{i-1}\rightarrow\dots\rightarrow F_{1}\rightarrow F_{0}\rightarrow
I\rightarrow 0,$

with $F_{i}=\bigoplus_{j}R(-j)^{\beta_{i,j}(I)}$, where the $\beta_{i,j}(I)$
are the graded Betti numbers of $I$. The projective dimension and the
regularity of $I$, are, respectively,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(I)\ $ $\displaystyle=\
\max\\{i:\beta_{i,j}(I)\neq 0,\ \text{for some}\ j\\},$
$\displaystyle\operatorname{reg}(I)\ $ $\displaystyle=\
\max\\{j-i:\beta_{i,j}(I)\neq 0,\ \text{for some}\ i\ \text{and}\ j\\}.$

Throughout the article, we consider only finite simple graphs. Hence we will
refer to them simply as graphs. Let $G$ be a graph. By $V(G)$ we denote the
vertex set of $G$, and by $E(G)$ the edge set of $G$. Two vertices $u$ and $v$
are adjacent if $\\{u,v\\}\in E(G)$. A vertex $u$ is called isolated if
$\\{u,v\\}\notin E(G)$ for all $v\in V(G)\setminus\\{u\\}$.

Let $K$ be a field and $G$ be a graph with vertex set $\\{1,\dots,n\\}$. The
binomial edge ideal $J_{G}$ of $G$ is the following binomial ideal of
$S=K[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]$:

$J_{G}=(x_{i}y_{j}-x_{j}y_{i}\ :\ \\{i,j\\}\in E(G)).$

Let $G$ be a graph. If $W$ is a subset of $V(G)$ we denote by $G_{W}$ the
induced subgraph of $G$ on $W$, that is $V(G_{W})=W$ and
$E(G_{W})=\\{\\{u,v\\}\in E(G):u,v\in W\\}$. It is known by [20, Corollary
2.2] that

$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq\operatorname{proj\phantom{,}\\!dim}(J_{G_{W}})\
\ \text{and}\ \ \operatorname{reg}(J_{G})\geq\operatorname{reg}(J_{G_{W}}),$

for all subsets $W$ of $V(G)$. We will use freely this fact.

Suppose that $G$ is connected. Then, we say that $G$ is $\ell$-vertex-
connected if for all subsets $W$ of $V(G)$ with $|W|<\ell$, the induced
subgraph $G_{V(G)\setminus W}$ is connected. The vertex-connectivity of $G$,
denoted by $\ell(G)$, is the maximum integer $\ell$ such that $G$ is
$\ell$-vertex-connected. It is clear that $\ell(G)\geq 1$.

######  Theorem 1.1.

Let $G$ be a graph with $n\geq 3$ non isolated vertices. Then

$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-5.$

Furthermore, if $G$ is connected, then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2$.

###### Proof.

By the work of [26, Theorem 5.2] it is known that
$\operatorname{depth}(S/J_{G})\geq 4$ for all graphs $G$. Therefore, by the
Auslander–Buchsbaum formula we have

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(S/J_{G})-1=2n-\operatorname{depth}(S/J_{G})-1\leq
2n-5.$

Suppose now that $G$ is connected. Then, by [1, Theorems 3.19 and 3.20] we
have
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(S/J_{G})-1\geq
n+\ell(G)-3$. Since $\ell(G)\geq 1$, we obtain
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2$, as desired.

We denote by $K_{n}$ the complete graph with $n$ vertices, that is
$V(K_{n})=\\{1,\dots,n\\}$ and $\\{i,j\\}\in E(K_{n})$ for all $i,j\in
V(K_{n})$, $i\neq j$. Whereas, by $P_{n}$ we denote the path of length $n$,
that is $V(P_{n})=\\{1,\dots,n\\}$ and
$E(P_{n})=\\{\\{1,2\\},\\{2,3\\},\ldots,\\{n-1,n\\}\\}$.

######  Theorem 1.2.

Let $G$ be a graph with $n\geq 3$ non isolated vertices. Then

$2\leq\operatorname{reg}(J_{G})\leq n.$

Moreover,

  1. (i)

$\operatorname{reg}(J_{G})=2$ if and only if $G=K_{n}$ and, in this case,
$\operatorname{proj\phantom{,}\\!dim}(J_{K_{n}})=n-2$.

  2. (ii)

$\operatorname{reg}(J_{G})=n$ if and only if $G=P_{n}$ and, in this case,
$\operatorname{proj\phantom{,}\\!dim}(J_{P_{n}})=n-2$.

###### Proof.

Since $J_{G}$ is generated in degree two, $\operatorname{reg}(J_{G})\geq 2$.
By [20, Theorem 1.1], $\operatorname{reg}(J_{G})\leq|V(G)|=n$. Statement (i)
follows from [28, Theorem 2.1], while statement (ii) follows from [18, Theorem
3.2].

The following observation will be used several times.

######  Remark 1.3.

Suppose $G=G_{1}\sqcup G_{2}\sqcup\dots\sqcup G_{c}$ is a graph without
isolated vertices and $c$ connected components $G_{i}$, $i=1,\dots,c$. Let
$S_{i}=K[x_{v},y_{v}:v\in V(G_{i})]$ and $n_{i}=|V(G_{i})|$, for all $i$. Then
$\sum_{i=1}^{c}n_{i}=n$ and $J_{G_{i}}$ is a binomial ideal of $S_{i}$. Since
the polynomial rings $S_{i}$ are in pairwise disjoint sets of variables, we
have

$S/J_{G}\cong\bigotimes_{i=1}^{c}S_{i}/J_{G_{i}}.$

Hence,
$\operatorname{proj\phantom{,}\\!dim}(S/J_{G})=\sum_{i=1}^{c}\operatorname{proj\phantom{,}\\!dim}(S_{i}/J_{G_{i}})$
and
$\operatorname{reg}(S/J_{G})=\sum_{i=1}^{c}\operatorname{reg}(S_{i}/J_{G_{i}})$.
Taking into account that for a graded ideal $I$ of a polynomial ring $R$ we
have
$\operatorname{proj\phantom{,}\\!dim}(R/I)=\operatorname{proj\phantom{,}\\!dim}(I)+1$
and $\operatorname{reg}(R/I)=\operatorname{reg}(I)-1$, we obtain the following
useful identities,

(1) $\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})\ $
$\displaystyle=\
\sum_{i=1}^{c}\operatorname{proj\phantom{,}\\!dim}(J_{G_{i}})+(c-1),$ (2)
$\displaystyle\operatorname{reg}(J_{G})\ $ $\displaystyle=\
\sum_{i=1}^{c}\operatorname{reg}(J_{G_{i}})-(c-1).$

The lower bound given in Theorem 1.1 for the projective dimension, can be
refined in terms of the regularity.

######  Proposition 1.4.

Let $n\geq 3$, $r$ be positive integers such that $3\leq
r\leq\lfloor\frac{n}{2}\rfloor+1$. Then

$n-r\leq\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-5,$

for all graphs $G$ with $n$ non isolated vertices.

###### Proof.

The upper bound for $\operatorname{proj\phantom{,}\\!dim}(J_{G})$ is stated in
Theorem 1.1. To prove the lower bound, assume the notation of Remark 1.3. By
formula (2) and Theorem 1.2,

$\displaystyle r\ $ $\displaystyle=\
\sum_{i=1}^{c}\operatorname{reg}(J_{G_{i}})-(c-1)\geq\sum_{i=1}^{c}2-(c-1)$
$\displaystyle=\ 2c-c+1=c+1.$

Therefore, $c\leq r-1$. The upper bound $c\leq
r-1\leq\lfloor\frac{n}{2}\rfloor$ we determined, agrees with the fact that the
number of connected components of $G$ is at most $\lfloor\frac{n}{2}\rfloor$.

Now, by formula (1) and Theorem 1.1,

(3) $\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})$
$\displaystyle=\
\sum_{i=1}^{c}\operatorname{proj\phantom{,}\\!dim}(J_{G_{i}})+(c-1)$
$\displaystyle\geq\ \sum_{i=1}^{c}(n_{i}-2)+(c-1)$ $\displaystyle=\
\sum_{i=1}^{c}n_{i}-2c+c-1$ $\displaystyle=\ n-c-1\geq n-r,$

since $c\leq r-1$.

######  Proposition 1.5.

Let $n\geq 3$, $r$ be positive integers such that
$\lceil\frac{n}{2}\rceil+1\leq r\leq n-1$. Then

$r-2\leq\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-5,$

for all graphs $G$ with $n$ non isolated vertices.

###### Proof.

The upper bound follows from Theorem 1.1. For the proof of the lower bound,
assume the notation of Remark 1.3. By formula (2) and Theorem 1.2,

$\displaystyle r\ $ $\displaystyle=\
\sum_{i=1}^{c}\operatorname{reg}(J_{G_{i}})-(c-1)\leq\sum_{i=1}^{c}n_{i}-(c-1)$
$\displaystyle=\ n-c+1.$

Thus, $c\leq n-r+1$. Note that $c\leq n-r+1\leq
n-(\lceil\frac{n}{2}\rceil+1)+1=n-\lceil\frac{n}{2}\rceil=\lfloor\frac{n}{2}\rfloor$.
Therefore, the upper bound $c\leq n-r+1$ agrees with the fact that the number
of connected components of $G$ is at most $\lfloor\frac{n}{2}\rfloor$.

Using the computation in (3), we obtain

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})\ $
$\displaystyle\geq\ n-c-1\geq r-2,$

since $c\leq n-r+1$.

##  2\. Special classes of graphs

In this section, we determine some classes of graphs that have a given
projective dimension or a given regularity. These families will be used to get
our main result.

Let $G_{1},G_{2}$ be two graphs with different vertex sets $V_{1}$ and $V_{2}$
and edge sets $E_{1}$ and $E_{2}$. The join of $G_{1}$ and $G_{2}$ is defined
to be the graph $G_{1}*G_{2}$ with vertex set $V_{1}\cup V_{2}$ and edge set
$E_{1}\cup E_{2}\cup\\{\\{v_{1},v_{2}\\}:v_{1}\in V_{1},v_{2}\in V_{2}\\}$.

The following formula due to Madani and Kiani ([29, Theorem 2.1]) plays a
pivotal role in our article. Suppose $G_{1}$ and $G_{2}$ are graphs with
disjoint vertex sets $V_{1}$ and $V_{2}$, and that not both of them are
complete. Then,

(4)
$\operatorname{reg}(J_{G_{1}*G_{2}})=\max\\{\operatorname{reg}(J_{G_{1}}),\operatorname{reg}(J_{G_{2}}),3\\}.$

It is worth mentioning that, even if $G_{1}$ and $G_{2}$ may have isolated
vertices, all vertices in $G_{1}*G_{2}$ are non isolated, and $G_{1}*G_{2}$ is
always a connected graph. Moreover, if $G_{1}\neq K_{1}$ and $G_{2}=K_{1}$,
then $G_{1}*G_{2}$ is called a cone.

###  2.1. Graphs with projective dimension $2n-5$

In [26, Theorem 5.3], Malayeri, Madani and Kiani have characterized all graphs
$G$ that have minimal depth possible, _i.e._ ,
$\operatorname{depth}(S/J_{G})=4$. For such graphs, by the Auslander–Buchsbaum
formula we have maximal projective dimension:

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(S/J_{G})-1=2n-\operatorname{depth}(S/J_{G})-1=2n-5.$

Hereafter, for a positive integer $m\geq 1$, we denote by $mK_{1}$ a graph
consisting of $m$ isolated vertices.

######  Theorem 2.1.

Let $G$ be a graph with $n\geq 5$ non isolated vertices. Then, the following
conditions are equivalent.

  1. (i)

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5$.

  2. (ii)

$G=\widetilde{G}*2K_{1}$ for some graph $\widetilde{G}$ with $n-2$ vertices.

######  Corollary 2.2.

Let $G$ be a graph with $n\geq 5$ non isolated vertices such that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5$. Then,

$3\leq\operatorname{reg}(J_{G})\leq n-2.$

Furthermore, given $r\in\\{3,\dots,n-2\\}$, there exists a graph $G$ with $n$
non isolated vertices such that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5$ and
$\operatorname{reg}(J_{G})=r$.

###### Proof.

By the previous theorem, $G=\widetilde{G}*2K_{1}$ for some graph
$\widetilde{G}$ with $n-2$ vertices. Since $2K_{1}$ is not complete and
$J_{2K_{1}}=(0)$, by formula (4),

$\operatorname{reg}(J_{G})=\max\\{\operatorname{reg}(J_{\widetilde{G}}),\operatorname{reg}(J_{2K_{1}}),3\\}=\max\\{\operatorname{reg}(J_{\widetilde{G}}),3\\}.$

Hence $\operatorname{reg}(J_{G})\geq 3$. Moreover, by Theorem 1.2,
$\operatorname{reg}(J_{\widetilde{G}})\leq|V(\widetilde{G})|=n-2$ and so
$\operatorname{reg}(J_{G})\leq n-2$, since $n-2\geq 3$.

Now, let $r\in\\{3,\dots,n-2\\}$. Set $\widetilde{G}=P_{r}\sqcup(n-2-r)K_{1}$
and $G=\widetilde{G}*2K_{1}$. Then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5$, by the previous theorem.
Moreover,

$\operatorname{reg}(J_{G})=\max\\{\operatorname{reg}(J_{\widetilde{G}}),\operatorname{reg}(J_{2K_{1}}),3\\}=\max\\{r,3\\}=r,$

since $J_{\widetilde{G}}=J_{P_{r}}$ has regularity $r$ by Theorem 1.2(ii).

###  2.2. Graphs with projective dimension $2n-6$

After the case of minimal depth, Malayeri, Madani and Kiani classified in [27,
Theorem 5, Section 5] the graphs $G$ with $\operatorname{depth}(S/J_{G})=5$,
that is $\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$.

To state their result, we introduce the following class of graphs. Hereafter,
if $n$ is a positive integer, we denote by $[n]$ the set $\\{1,2,\dots,n\\}$.
If $v$ is a vertex of a graph $G$, $N_{G}(v)=\\{u\in
V(G)\setminus\\{v\\}:\\{u,v\\}\in E(G)\\}$ is the neighbourhood of $v$ in $G$.

######  Definition 2.3.

Let $T\subset[n]$ with $|T|=n-2$. The family $\mathcal{G}_{T}$ consists of all
graphs $G$ with vertex set $[n]$ such that there exist two non adjacent
vertices $u$ and $v$ of $G$ with $u,v\in[n]\setminus T$, and three disjoint
subsets of $T$, say $V_{0}$, $V_{1}$ and $V_{2}$ with
$V_{1},V_{2}\neq\emptyset$ and $V_{0}\cup V_{1}\cup V_{2}=T$, such that the
following conditions hold:

  1. (a)

$N_{G}(u)=V_{0}\cup V_{1}$ and $N_{G}(v)=V_{0}\cup V_{2}$

  2. (b)

$\\{v_{1},v_{2}\\}\in E(G)$, for every $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$.

Now, we introduce the class of $D_{5}$-type graphs.

######  Definition 2.4.

Let $G$ be a graph with $n$ vertices such that $G\neq H*2K_{1}$, for all
graphs $H$. $G$ is called a $D_{5}$-type graph, if one of the following
conditions holds:

  1. (a)

$G=\widetilde{G}*3K_{1}$, for some graph $\widetilde{G}$.

  2. (b)

$G=\widetilde{G}*(K_{1}\sqcup K_{2})$, for some graph $\widetilde{G}$.

  3. (c)

$G\in\mathcal{G}_{T}$, for some $T\subset V(G)$ with $|T|=n-2$.

######  Theorem 2.5.

Let $G$ be a graph with $n\geq 5$ non isolated vertices. Then, the following
conditions are equivalent.

  1. (i)

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$.

  2. (ii)

$G$ is a $D_{5}$-type graph.

The following observation will be useful later.

######  Remark 2.6.

Let $n\geq 5$. By Theorems 2.1 and 2.5, it follows that all graphs $G$ with
$n\geq 5$ non isolated vertices such that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5$ or
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$ are connected.

For the proof of the next result, we need a lemma of Ohtani [24, Lemma 4.8],
see also [19, Lemma 3.1] and formula (1) in the same article.

We recall that a clique of a graph $G$ is a subset $W$ of $V(G)$ such that
$G_{W}$ is an induced complete subgraph of $G$. A maximal clique of $G$ is a
clique of $G$ that is not contained in any other clique of $G$. A vertex $v\in
V(G)$ is called simplicial if $N_{G}(v)$ is a clique of $G$, otherwise is
called internal. Let $v\in V(G)$. We denote $G_{V(G)\setminus\\{v\\}}$ by
$G\setminus v$. Whereas, by $G_{v}$ we denote the graph with vertex set $V(G)$
and edge set $E(G)\cup\\{\\{w_{1},w_{2}\\}:w_{1},w_{2}\in N_{G}(v)\\}$.

Let $v$ be an internal vertex of a graph $G$. Then Ohtani lemma, see also
formula (1) in [19], implies that the following short sequence is exact:

(5)
$0\rightarrow\frac{S}{J_{G}}\longrightarrow\frac{S}{(x_{v},y_{v},J_{G\setminus
v})}\oplus\frac{S}{J_{G_{v}}}\longrightarrow\frac{S}{(x_{v},y_{v},J_{G_{v}\setminus
v})}\rightarrow 0.$

In the next proposition we also use freely the following upper bound for the
regularity proved in [5, Theorem 2.1], see also formula (3) in the same
article. For a connected graph $G$ with $n$ vertices,

$\operatorname{reg}(J_{G})\leq n+2-|W|,\ \ \ \text{for any clique}\ W\
\text{of}\ G.$

######  Proposition 2.7.

Let $G$ be a graph with $n\geq 6$ non isolated vertices such that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$. Then,

$3\leq\operatorname{reg}(J_{G})\leq n-2.$

###### Proof.

By the previous theorem, $G$ is a $D_{5}$-type graph. Therefore $G$ is not a
complete graph. By Theorem 1.2(i), $\operatorname{reg}(J_{G})\geq 3$.

Let us prove the upper bound. Firstly, suppose $G=\widetilde{G}*3K_{1}$ or
$G=\widetilde{G}*(K_{1}\sqcup K_{2})$, for some graph $\widetilde{G}$ with
$n-3$ vertices. Then, arguing as in Corollary 2.2 we obtain
$\operatorname{reg}(J_{G})\leq n-3$ in this case.

Suppose now that $G\in\mathcal{G}_{T}$ for some $T\subset V(G)$ with
$|T|=n-2$. Then $V(G)=\\{u,v\\}\cup V_{0}\cup V_{1}\cup V_{2}$ where the union
is disjoint, $V_{1},V_{2}\neq\emptyset$, $u$ and $v$ are non adjacent,
$N_{G}(u)=V_{0}\cup V_{1}$, $N_{G}(v)=V_{0}\cup V_{2}$ and
$\\{v_{1},v_{2}\\}\in E(G)$ for all $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$.

Let us show that $\operatorname{reg}(J_{G})\leq n-2$. We distinguish three
cases.
Case 1. Suppose both $u$ and $v$ are simplicial vertices of $G$. Then,
$T=V_{0}\cup V_{1}\cup V_{2}$ is a maximal clique of $G$. Therefore,
$\operatorname{reg}(J_{G})\leq n+2-|T|=4\leq n-2$ as $n\geq 6$.
Case 2. Suppose that $u$ is a simplicial vertex, but $v$ is internal. Then
$\\{u\\}\cup V_{0}\cup V_{1}$ is a clique of $G$. Since $v$ is internal, we
can apply Ohtani lemma. By the short exact sequence (5) we have

$\operatorname{reg}(J_{G})\leq\max\\{\operatorname{reg}(x_{v},y_{v},J_{G\setminus
v}),\operatorname{reg}(J_{G_{v}}),\operatorname{reg}(x_{v},y_{v},J_{G_{v}\setminus
v})+1\\}.$

Since $x_{v},y_{v}$ do not divide any generator of $J_{G\setminus v}$ and
$J_{G_{v}\setminus v}$, we obtain

(6) $\operatorname{reg}(J_{G})\leq\max\\{\operatorname{reg}(J_{G\setminus
v}),\operatorname{reg}(J_{G_{v}}),\operatorname{reg}(J_{G_{v}\setminus
v})+1\\}.$

Note that $G\setminus v$ is not a path. Indeed $N_{G}(u)=V_{0}\cup V_{1}$ is
non empty, as $V_{1}\neq\emptyset$. Hence, if $N_{G}(u)=\\{w\\}$ then
$|V_{2}|=|T|-1=n-3\geq 3$. Recall that all vertices of $V_{1}$ and $V_{2}$ are
adjacent. Then $w$ would be adjacent to at least three vertices, which can not
happen in a path. Otherwise, if $|N_{G}(u)|\geq 2$ and $w_{1},w_{2}\in
N_{G}(u)$, then $G$ has an induced cycle with vertices $u,w_{1},w_{2}$. But a
path does not have induced cycles. It follows that $G\setminus v$ is not a
path. Thus, by Theorem 1.2(ii),

(7) $\operatorname{reg}(J_{G\setminus v})\ \leq\ |V(G\setminus v)|-1=n-2.$

Note that in the graphs $G_{v}$ and $G_{v}\setminus v$, the set $T=V_{0}\cup
V_{1}\cup V_{2}$ is a clique of size $n-2$. Therefore, since $n\geq 6$ we have

(8) $\displaystyle\operatorname{reg}(J_{G_{v}})\ $ $\displaystyle\leq\
n+2-|T|=4\leq n-2,$ (9) $\displaystyle\operatorname{reg}(J_{G_{v}\setminus
v})+1\ $ $\displaystyle\leq\ (n-1)+2-|T|+1=4\leq n-2.$

Combining (6) with (7), (8) and (9) we obtain $\operatorname{reg}(J_{G})\leq
n-2$, as desired.
Case 3. Suppose that both $u$ and $v$ are internal vertices. We first apply
Ohtani lemma to $v$ and get the inequality,

(10) $\operatorname{reg}(J_{G})\leq\max\\{\operatorname{reg}(J_{G\setminus
v}),\operatorname{reg}(J_{G_{v}}),\operatorname{reg}(J_{G_{v}\setminus
v})+1\\}.$

As in the previous case, $G\setminus v$ is not a path. Indeed
$N_{G}(u)=V_{0}\cup V_{1}$ is non empty. If $N_{G}(u)=\\{w\\}$ then
$|V_{2}|=|T|-1=n-3\geq 3$. Then $w$ would be adjacent to at least three
vertices, which can not happen in a path. Otherwise, if $|N_{G}(u)|\geq 2$ let
$w_{1},w_{2}\in N_{G}(u)$. If $w_{1},w_{2}$ are adjacent, then $G$ has an
induced cycle with vertices $u,w_{1},w_{2}$. Otherwise, let $w_{3}\in V_{2}$,
then $G$ has an induced cycle with vertices $u,w_{1},w_{2},w_{3}$. But a path
does not have induced cycles. Thus, by Theorem 1.2(ii),

(11) $\operatorname{reg}(J_{G\setminus v})\leq n-2.$

Since $u$ and $v$ are non adjacent in $G$ and in $G_{v}$, $u$ is internal
(simplicial) in $G_{v}$ if and only if $u$ is internal (simplicial) in
$G_{v}\setminus v$. We distinguish the two cases.
Subcase 3.1. Suppose $u$ is simplicial in $G_{v}$ and $G_{v}\setminus v$. Then
$T=V_{0}\cup V_{1}\cup V_{2}$ is a clique of size $n-2$ in both graphs.
Therefore,

(12) $\displaystyle\operatorname{reg}(J_{G_{v}})\ $ $\displaystyle\leq\
n+2-|T|=4\leq n-2,$ (13) $\displaystyle\operatorname{reg}(J_{G_{v}\setminus
v})+1\ $ $\displaystyle\leq\ (n-1)+2-|T|+1=4\leq n-2.$

Combining (10) with (11), (12) and (13), we obtain
$\operatorname{reg}(J_{G})\leq n-2$, as desired.
Subcase 3.2. Suppose $u$ is internal in $G_{v}$ and $G_{v}\setminus v$. We
apply Ohtani lemma to get

(14) $\displaystyle\operatorname{reg}(J_{G_{v}})\ $ $\displaystyle\leq\
\max\\{\operatorname{reg}(J_{G_{v}\setminus
u}),\operatorname{reg}(J_{(G_{v})_{u}}),\operatorname{reg}(J_{(G_{v})_{u}\setminus
u})+1\\},$ (15) $\displaystyle\operatorname{reg}(J_{G_{v}\setminus v})\ $
$\displaystyle\leq\
\max\\{\operatorname{reg}(J_{G_{v}\setminus\\{u,v\\}}),\operatorname{reg}(J_{(G_{v}\setminus
v)_{u}}),\operatorname{reg}(J_{(G_{v}\setminus v)_{u}\setminus u})+1\\}.$

The graph $G_{v}\setminus u$ is easily seen to be not a path. Hence,
$\operatorname{reg}(J_{G_{v}\setminus u})\leq|V(G_{v}\setminus u)|-1=n-2$.
Moreover, in $(G_{v})_{u}$ the set $T$ is a clique of size $n-2$, and the same
calculation as in (12) gives $\operatorname{reg}(J_{(G_{v})_{u}})\leq n-2$.
Finally, in $(G_{v})_{u}\setminus u$, $T$ is a clique. The same calculation as
in (13) gives $\operatorname{reg}(J_{(G_{v})_{u}\setminus u})+1\leq n-2$.
These calculations and equation (14) yield

(16) $\operatorname{reg}(J_{G_{v}})\leq n-2.$

We have
$\operatorname{reg}(J_{G_{v}\setminus\\{u,v\\}})\leq|V(G_{v}\setminus\\{u,v\\})|=n-2$.
Note that in $(G_{v}\setminus v)_{u}$, $T$ is a clique. As before, we have
$\operatorname{reg}(J_{(G_{v}\setminus v)_{u}})\leq n-2$. Moreover,
$(G_{v}\setminus v)_{u}\setminus u$ is a complete graph. Consequently,
$\operatorname{reg}(J_{(G_{v}\setminus v)_{u}\setminus u})+1=3\leq n-2$. Thus,

(17) $\operatorname{reg}(J_{G_{v}\setminus v})\leq n-2.$

Finally, combining (10) with (11), (16) and (17) we obtain that
$\operatorname{reg}(J_{G})\leq n-2$, as desired. The proof is complete.

######  Corollary 2.8.

Let $n\geq 5$ and $3\leq r\leq n-2$ be positive integers. Then, there exists a
graph $G$ with $n$ non isolated vertices such that

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6\ \ \ \text{and}\ \ \
\operatorname{reg}(J_{G})=r.$

###### Proof.

Let $3\leq r\leq n-3$, and set $\widetilde{G}=P_{r}\sqcup(n-r-3)K_{1}$ and
$G=\widetilde{G}*3K_{1}$. Then, by Theorem 2.5,
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$, and by formula (4),
$\operatorname{reg}(J_{G})=\operatorname{reg}(J_{\widetilde{G}})=\operatorname{reg}(J_{P_{r}})=r$.

Let now $r=n-2$. Let $G$ be the graph with vertex set
$V(G)=\\{u,v,1,\dots,n-2\\}$ and edge set

$E(G)=\big{\\{}\\{i,i+1\\},\\{i,u\\}:i=1,\dots,n-3\big{\\}}\cup\big{\\{}\\{i,v\\}:i=1,\dots,n-4\big{\\}}\cup\\{\\{n-2,v\\}\\}.$

Then, setting $T=\\{1,\dots,n-2\\}$, we have that $G\in\mathcal{G}_{T}$. To
see why this is true, using the same notation as in Definition 2.3, just take
$V_{0}=\\{1,\dots,n-4\\}$, $V_{1}=\\{n-3\\}$ and $V_{2}=\\{n-2\\}$. Therefore,
by Theorem 2.5, $\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$. Note that
the induced subgraph $P=G_{\\{1,\dots,n-2\\}}$ is a path with $n-2$ vertices.
Hence, $\operatorname{reg}(J_{G})\geq\operatorname{reg}(J_{P})=n-2$. On the
other hand, by Proposition 2.7, $\operatorname{reg}(J_{G})\leq n-2$.
Consequently, $\operatorname{reg}(J_{G})=n-2$ and $G$ is the graph we are
looking for.

###  2.3. Graphs with regularity 3

We quote the following result [29, Theorem 3.2].

######  Theorem 2.9.

Let $G$ be a non-complete graph with $n$ non isolated vertices. Then
$\operatorname{reg}(J_{G})=3$ if and only if one of the following conditions
holds:

  1. (i)

$G=K_{r}\sqcup K_{s}$ with $r,s\geq 2$ and $r+s=n$, or

  2. (ii)

$G=G_{1}*G_{2}$, where $G_{i}$ is a graph with $n_{i}<n$ vertices such that
$n_{1}+n_{2}=n$ and $\operatorname{reg}(J_{G_{i}})\leq 3$, for $i=1,2$.

######  Remark 2.10.

If $G$ is a graph with $\operatorname{reg}(J_{G})=3$ and
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2$, then $G$ must be
connected. Suppose by contraddiction that there exists a disconnected graph
$G=G_{1}\sqcup\dots\sqcup G_{c}$ with regularity $3$ and projective dimension
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2$. Arguing as in
Proposition 1.4 we obtain $c\leq r-1=2$. Thus $c=2$ and by formula (2) we must
have $\operatorname{reg}(J_{G_{1}})+\operatorname{reg}(J_{G_{2}})-1=3$. This
formula holds if and only if
$\operatorname{reg}(J_{G_{1}})=\operatorname{reg}(J_{G_{2}})=2$. Thus
$G=K_{r}\sqcup K_{s}$ as in Theorem 2.9(i). But then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=n-3$, a contradiction.

######  Corollary 2.11.

Let $n\geq 4$ be an integer. Then, for all $n-3\leq p\leq 2n-5$, there exists
a graph $G$ with $n$ non isolated vertices such that

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=p\ \ \ \text{and}\ \ \
\operatorname{reg}(J_{G})=3.$

###### Proof.

We proceed by induction on $n\geq 4$. Suppose $n=4$. Then, the binomial edge
ideals of the graphs $2K_{2}$, $(P_{2}\sqcup K_{1})*K_{1}$, $P_{2}*2K_{1}$
have regularity $3$ and projective dimension, respectively, 1, 2 and 3.

Suppose now $n>4$. If $p=2n-5$ or $p=2n-6$, then a graph $G$ with $n$ non
isolated vertices such that $\operatorname{proj\phantom{,}\\!dim}(J_{G})=p$
and $\operatorname{reg}(J_{G})=3$ exists by Corollaries 2.2, 2.8. Therefore,
we can assume $n-3\leq p\leq 2n-7$. If $p=n-3$, then the binomial edge ideal
of $K_{r}\sqcup K_{s}$ with $r,s\geq 2$ and $r+s=2$ has projective dimension
$n-3$ and regularity 3, by using Theorem 2.9(i). Now, let $n-2\leq p\leq
2n-7$. Then $(n-1)-3\leq p-2\leq 2(n-1)-7<2(n-1)-5$. Hence, by induction there
exists a graph $\widetilde{G}$ with
$\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})=p-2$ and
$\operatorname{reg}(J_{\widetilde{G}})=3$. Let $G=\widetilde{G}*K_{1}$. If
$p-2=(n-1)-3$, then $\widetilde{G}$ is disconnected. By Lemma 3.2 in the next
section,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})$
$\displaystyle=\max\\{\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2,n-3\\}$
$\displaystyle=\max\\{p,n-3\\}=\max\\{n-2,n-3\\}=n-2.$

Otherwise, if $p-2\geq(n-1)-2$, then $\widetilde{G}$ is connected by Remark
2.10. Then, by Lemma 3.2,
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2=p$.
The induction is complete and the assertion follows.

###  2.4. Graphs with regularity $n-2$

In the next result, we consider graphs $G$ with $n$ non isolated vertices
having regularity $r=\operatorname{reg}(J_{G})=n-2$. If $n=5$, then $r=3$ and
we can apply Corollary 2.11. Therefore, we assume $n\geq 6$. In this case
$r=n-2\geq\lceil\frac{n}{2}\rceil+1$. Thus, by Proposition 1.5, the projective
dimension for such graphs varies as follows:
$r-2=n-4\leq\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-5$.

For the next result, we need the concept of decomposable graph introduced by
Rauf and Rinaldo in [25]. A graph $G$ is called decomposable if there exist
two graphs $G_{1}$ and $G_{2}$ such that $V(G)=V(G_{1})\cup V(G_{2})$,
$V(G_{1})\cap V(G_{2})=\\{v\\}$ where $v$ is a simplicial vertex for both
$G_{1}$ and $G_{2}$, and such that $E(G)=E(G_{1})\cup E(G_{2})$. In such case,
we write $G=G_{1}\cup_{v}G_{2}$ and say that $G$ is obtained by gluing $G_{1}$
and $G_{2}$ along $v$. By [11, Proposition 1.3] it follows that

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})\ $ $\displaystyle=\
\operatorname{proj\phantom{,}\\!dim}(J_{G_{1}})+\operatorname{proj\phantom{,}\\!dim}(J_{G_{2}})+1,$
$\displaystyle\operatorname{reg}(J_{G})\ $ $\displaystyle=\
\operatorname{reg}(J_{G_{1}})+\operatorname{reg}(J_{G_{2}})-1.$

######  Lemma 2.12.

Let $G$ be the graph with vertex set $V(G)=[n]$ and edge set

$E(G)=\big{\\{}\\{i,j\\}:1\leq i<j\leq
n-1\big{\\}}\cup\big{\\{}\\{m,n\\},\\{m+1,n\\},\dots,\\{n-1,n\\}\big{\\}},$

for some $m\in[n-1]$. Then $\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq
2n-m-3$ and $\operatorname{reg}(J_{G})\leq 3$.

###### Proof.

For the regularity, note that in $G$ the set $W=[n-1]$ is a clique. Therefore,
$\operatorname{reg}(J_{G})\leq n+2-|W|=3$. For the projective dimension, we
proceed by descending induction on $m\leq n-1$, starting with $m=n-1$. In such
a case, $G$ is decomposable: $G=G_{[n-1]}\cup_{n-1}G_{\\{n-1,n\\}}$. Note that
$G_{[n-1]}$ is a complete graph and $J_{G_{\\{n-1,n\\}}}$ is a principal
ideal. Thus,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})$
$\displaystyle=\operatorname{proj\phantom{,}\\!dim}(J_{{G_{[n-1]}}})+\operatorname{proj\phantom{,}\\!dim}(J_{G_{\\{n-1,n\\}}})+1$
$\displaystyle=(n-1)-2+0+1=n-2.$

Since $m=n-1$, then $2n-m-3=n-2$. Hence the base case is verified.

Suppose now $m<n-1$. Then, $m$ is an internal vertex of $G$, because it
belongs to two different maximal cliques, namely $[n-1]$ and
$\\{m,m+1,\dots,n\\}$. Applying Ohtani lemma to $m$, by the short exact
sequence (5) we obtain

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq$ $\displaystyle\
\ \ \leq\max\\{\operatorname{proj\phantom{,}\\!dim}(x_{m},y_{m},J_{G\setminus
m}),\operatorname{proj\phantom{,}\\!dim}(J_{G_{m}}),\operatorname{proj\phantom{,}\\!dim}(x_{m},y_{m},J_{G_{m}\setminus
m})-1\\}.$

By induction, $\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus m})\leq
2(n-1)-m-3=2n-m-5$. Therefore,

$\operatorname{proj\phantom{,}\\!dim}(x_{m},y_{m},J_{G\setminus
m})=\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus m})+2\leq 2n-m-3.$

For the other two inequalities, note that $G_{m}$ and $G_{m}\setminus m$ are
complete graphs with $n$ and $n-1$ vertices, respectively. Hence,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G_{m}})$
$\displaystyle=n-2,$
$\displaystyle\operatorname{proj\phantom{,}\\!dim}(x_{m},y_{m},J_{G_{m}\setminus
m})-1$ $\displaystyle=\operatorname{proj\phantom{,}\\!dim}(J_{G_{m}\setminus
m})+2-1=n-3+1=n-2.$

But $n-2\leq 2n-m-3$ because $m\leq n-1$, by construction. Finally, all the
inequalities obtained show that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-m-3$, as desired.

We need the following technique. Let $e=\\{u,v\\}\in E(G)$. By $G\setminus e$
we denote the graph with $V(G\setminus e)=V(G)$ and $E(G\setminus
e)=E(G)\setminus\\{e\\}$. Whereas, by $G_{e}$ we denote the graph with
$V(G_{e})=V(G)$ and $E(G_{e})=E(G)\cup\\{\\{w_{1},w_{2}\\}:w_{1},w_{2}\in
N_{G}(u)\ \text{or}\ w_{1},w_{2}\in N_{G}(v)\\}$. Set
$f_{e}=x_{u}y_{v}-x_{v}y_{u}$. Then, we a short exact sequence

(18) $0\rightarrow\frac{S}{(J_{G\setminus
e}:f_{e})}(-2)\longrightarrow\frac{S}{J_{G\setminus
e}}\longrightarrow\frac{S}{J_{G}}\rightarrow 0.$

By [22, Theorem 3.7], we have

(19) $J_{G\setminus e}:f_{e}=J_{(G\setminus e)_{e}}+I_{G},$

where

$I_{G}=(g_{P,t}:P:u,u_{1},\dots,u_{s},v\ \textit{is a path between}\ u\
\textit{and}\ v\ \textit{in}\ G\ \textit{and}\ 0\leq t\leq s),$

with $g_{P,0}=x_{u_{1}}\cdots x_{u_{s}}$ and $g_{P,t}=y_{u_{1}}\cdots
y_{u_{t}}x_{u_{t+1}}\cdots x_{u_{s}}$ for every $1\leq t\leq s$.

######  Proposition 2.13.

Let $n\geq 6$ be a positive integer. Then, for all $n-4\leq p\leq 2n-5$, there
exists a graph $G$ with $n$ non isolated vertices, such that

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=p\ \ \ \text{and}\ \ \
\operatorname{reg}(J_{G})=n-2.$

###### Proof.

If $p=n-4$, then $G=P_{2}\sqcup P_{2}\sqcup P_{n-4}$ has
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=n-4$ and
$\operatorname{reg}(J_{G})=n-2$. If $p=n-3$, then $G=K_{3}\sqcup P_{n-3}$ has
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=n-3$ and
$\operatorname{reg}(J_{G})=n-2$. If $p=n-2$, then consider the graph depicted
below

1234$\cdots$$n-3$$n-2$$n-1$$n$

It is clear that $G$ is decomposable as
$(G_{\\{1,2,n-1\\}}\cup_{2}G_{\\{2,3,n\\}})\cup_{3}G_{\\{3,4,\dots,n-2\\}}$.
We set $G_{1}=G_{\\{1,2,n-1\\}}$, $G_{2}=G_{\\{2,3,n\\}}$ and
$G_{3}=G_{\\{3,4,\dots,n-2\\}}$. $G_{1}$ and $G_{2}$ are complete graphs with
three vertices each, while $G_{3}$ is a path with $n-4$ vertices. Therefore,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})$
$\displaystyle=\sum_{i=1}^{3}\operatorname{proj\phantom{,}\\!dim}(J_{G_{i}})+2=1+1+n-6+2=n-2,$
$\displaystyle\operatorname{reg}(J_{G})$
$\displaystyle=\sum_{i=1}^{3}\operatorname{reg}(J_{G_{i}})-2=2+2+n-4-2=n-2.$

It remains to consider the case $n-1\leq p\leq 2n-5$. For this purpose, let
$m\in\\{1,\dots,n-3\\}$ and consider the graph $G$ depicted below.

12$\cdots$$m-1$$m$$m+1$$\cdots$$n-3$$n-2$$n$$n-1$$\cdots$$\cdots$

That is, $V(G)=[n]$ and

$\displaystyle E(G)\ =$ $\displaystyle\
\big{\\{}\\{i,i+1\\}:i=1,\dots,n-3\big{\\}}$ $\displaystyle\cup$
$\displaystyle\ \big{\\{}\\{i,n-1\\}:i=m,\dots,n-2\big{\\}}$
$\displaystyle\cup$ $\displaystyle\
\big{\\{}\\{i,n\\}:i=1,\dots,n-2\big{\\}}.$

We claim that $\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-m-4$ and
$\operatorname{reg}(J_{G})=n-2$. Since

$\\{2n-m-4:m=1,\dots,n-3\\}=\\{n-1,n,\dots,2n-5\\},$

the claim will conclude the proof.

Firstly, we note that if $m=1$, then $G=G_{[n-2]}*G_{\\{n-1,n\\}}$. Since
$G_{[n-2]}$ is a path with $n-2$ vertices and $G_{\\{n-1,n\\}}$ consists of
two isolated vertices, by Theorem 2.1 and formula (4) we obtain

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-5,\ \ \
\operatorname{reg}(J_{G})=n-2,$

in this case.

If $m=2$, then $G$ is a $D_{5}$-type graph. Indeed, $G\in\mathcal{G}_{[n-2]}$.
To see why this is true, using the notation of Definition 2.3, it is enough to
set $u=n-1$, $v=1$, $V_{0}=\\{2\\}$, $V_{1}=\\{3,\dots,n-2\\}$ and
$V_{2}=\\{n\\}$. Hence $\operatorname{proj\phantom{,}\\!dim}(J_{G})=2n-6$.
Furthermore,
$\operatorname{reg}(J_{G})\geq\operatorname{reg}(J_{G_{[n-2]}})=n-2$, but also
$\operatorname{reg}(J_{G})\leq n-2$ by Proposition 2.7.

Thus our claim holds for $m=1,2$. Now, we proceed by induction on $n\geq 5$.
If $n=5$, then $m\in\\{1,2\\}$ and there is nothing to prove. Suppose $n\geq
6$ and let $m\in\\{3,\dots,n-3\\}$. Set $e=\\{1,n\\}$ and let
$f_{e}=x_{1}y_{n}-x_{n}y_{1}$. Then, by the short exact sequence (18), see
also [18, Proposition 2.1(a)], we have

(20) $\operatorname{reg}(J_{G})\leq\max\\{\operatorname{reg}(J_{G\setminus
e}),\operatorname{reg}(J_{G\setminus e}:f_{e})+1\\}.$

Note that $G\setminus e$ is decomposable as $G\setminus
e=G_{\\{1,2\\}}\cup_{2}G_{\\{2,\dots,n\\}}$. Using the induction on
$G_{\\{2,\dots,n\\}}$ we have

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus e})$
$\displaystyle=\operatorname{proj\phantom{,}\\!dim}(J_{G_{\\{1,2\\}}})+\operatorname{proj\phantom{,}\\!dim}(J_{G_{\\{2,\dots,n\\}}})+1$
(21) $\displaystyle=2(n-1)-(m-1)-4+1$ $\displaystyle=2n-m-4,$ (22)
$\displaystyle\operatorname{reg}(J_{G\setminus e})$
$\displaystyle=\operatorname{reg}(J_{G_{\\{1,2\\}}})+\operatorname{reg}(J_{G_{\\{2,\dots,n\\}}})-1=2+n-3-1=n-2.$

By equation (19), $J_{G\setminus e}:f_{e}=J_{(G\setminus e)_{e}}+I_{G}$. Note
than any path in $G$ from $1$ to $n$ different from the path $1,n$ must pass
through the vertex 2. Hence $I_{G}=(x_{2},y_{2})$. Consequently,
$J_{G\setminus e}:f_{e}=(J_{\widetilde{G}},x_{2},y_{2})$, where
$\widetilde{G}$ is the graph $(G\setminus e)_{e}\setminus\\{2\\}$ with
$V(\widetilde{G})=\\{3,\dots,n\\}$ and

$\displaystyle E(\widetilde{G})\ =$ $\displaystyle\ \big{\\{}\\{i,j\\}:3\leq
i<j\leq n-2\big{\\}}$ $\displaystyle\cup$ $\displaystyle\
\big{\\{}\\{i,n\\}:i=3,\dots,n-2\big{\\}}$ $\displaystyle\cup$ $\displaystyle\
\big{\\{}\\{j,n-1\\}:j=m,\dots,n-2\big{\\}}.$

Therefore, using Lemma 2.12 applied on $\widetilde{G}$ we get

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus e}:f_{e})$
$\displaystyle=\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}},x_{2},y_{2})=\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2$
(23) $\displaystyle\leq 2(n-2)-m-3+2$ $\displaystyle=2n-m-5,$ (24)
$\displaystyle\operatorname{reg}(J_{G\setminus e}:f_{e})+1$
$\displaystyle=\operatorname{reg}(J_{\widetilde{G}})+1\leq 4\leq n-2,$

as $n\geq 6$. By (21) and (23) we have
$\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus
e}:f_{e})<\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus e})$. Thus, using
the short exact sequence (18) we obtain

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(J_{G\setminus
e})=2n-m-4.$

Whereas, combining (20) with (22) and (24) we obtain
$\operatorname{reg}(J_{G})\leq n-2$. Since also
$\operatorname{reg}(J_{G})\geq\operatorname{reg}(J_{G_{[n-2]}})=n-2$, as
$G_{[n-2]}$ is a path with $n-2$ vertices, we obtain the equality. The
inductive proof is complete.

######  Remark 2.14.

Note that the graphs constructed in the previous proposition, for $p\geq n-2$,
are all connected.

###  2.5. The size of betti tables of binomial edge ideals of small graphs.

By putting together all results in this section we can determine the set

$\textup{pdreg}(n)\ =\
\big{\\{}(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G})):G\in\textup{Graphs}(n)\big{\\}},$

for small values of $n$, where $\textup{Graphs}(n)$ denotes the class of all
finite simple graphs with $n$ non isolated vertices.

######  Example 2.15.

We determine the set $\textup{pdreg}(n)$ for $n=3,4,5$ and $6$.

  1. $({\bf n=3})$

We have $\textup{pdreg}(3)=\\{(1,2),(1,3)\\}$. In the following list we
display all the graphs $G$ with three non isolated vertices and below each of
them the pair
$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))$.

$(1,2)$$(1,3)$

  2. $({\bf n=4})$

We have $\textup{pdreg}(4)=\\{(2,2),(1,3),(2,3),(3,3),(2,4)\\}$. The following
is a list of graphs with four non isolated vertices that gives such pairs.

$(2,2)$$(1,3)$$(2,3)$$(3,3)$$(2,4)$

Note that the second, third and fourth graph are, respectively, $K_{2}\sqcup
K_{2}$, $(P_{2}\sqcup K_{1})*K_{1}$, $P_{2}*2K_{1}$. These graphs have
regularity $3$, by Theorem 2.9.

  3. $({\bf n=5})$

It is
$\textup{pdreg}(5)=\\{(3,2),(2,3),(3,3),(4,3),(5,3),(2,4),(3,4),(4,4),(3,5)\\}$.
Furthermore, a list of graphs giving such pairs is given below.

$(3,2)$$(2,3)$$(3,3)$$(4,3)$$(5,3)$

$(2,4)$$(3,4)$$(4,4)$$(3,5)$

Note that each graph $G$ displayed, with
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2=3$, is connected. The
graphs with regularity 3 are constructed as in Corollary 2.11. They are, in
the given order: $K_{2}\sqcup K_{3}$, $(K_{2}\sqcup K_{2})*K_{1}$,
$((P_{2}\sqcup K_{1})*K_{1})*K_{1}$, and $(P_{2}*2K_{1})*K_{1}$. Moreover,
since $n=5$, by Corollary 2.2, if $\operatorname{reg}(J_{G})=n-1=4$ then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-6=4$.

  4. $({\bf n=6})$

In the following, we list all pairs of the set $\textup{pdreg}(6)$, and for
each pair $(p,r)$ in the set a graph $G$ with
$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))=(p,r)$.

$(4,2)$$(3,3)$$(4,3)$$(5,3)$$(6,3)$$(7,3)$

$(2,4)$$(3,4)$$(4,4)$$(5,4)$$(6,4)$$(7,4)$

$(3,5)$$(4,5)$$(5,5)$$(4,6)$

Note that all graphs $G$ displayed, with
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2=4$, are connected.
Furthermore, the graphs with regularity 3 are constructed as in Corollary
2.11. Whereas, the graphs with regularity $n-2=4$ are constructed by using
Proposition 2.13. Finally, if $\operatorname{reg}(J_{G})=n-1$, then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-7=5$ by Corollary 2.2 and
Proposition 2.7.

##  3\. The size of the betti table of binomial edge ideals

Let $n\geq 1$ be an integer. Denote by $\textup{Graphs}(n)$ the class of all
finite simple graphs with $n$ non isolated vertices.

We define

$\textup{pdreg}(n)\ =\
\big{\\{}(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G})):G\in\textup{Graphs}(n)\big{\\}},$

which is the set of the sizes of the Betti tables of $J_{G}\subset
S=K[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]$, as $G$ ranges over all graphs with
$n$ non isolated vertices. Note that we are allowing $K$ to be any field.

Finally, we can state our main result in the article.

######  Theorem 3.1.

For all $n\geq 3$,

(25) $\displaystyle\textup{pdreg}(n)\ =\
\big{\\{}(n-2,2),(n-2,n)\big{\\}}\cup\bigcup_{r=3}^{\lfloor\frac{n}{2}\rfloor+1}\big{(}\bigcup_{p=n-r}^{2n-5}\\{(p,r)\\}\big{)}\
\cup$
$\displaystyle\cup\bigcup_{r=\lceil\frac{n}{2}\rceil+1}^{n-2}\big{(}\bigcup_{p=r-2}^{2n-5}\\{(p,r)\\}\big{)}\cup
A_{n},$

where $A_{n}=\\{(p,r)\in\textup{pdreg}(n):r=n-1\\}$.

For the proof of the theorem, we need the following lemma which is an
immediate consequence of [19, Theorems 3.4 and 3.9].

######  Lemma 3.2.

Let $\widetilde{G}$ be a graph with $n-1$ vertices, and set
$G=\widetilde{G}*K_{1}$. Then,

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\begin{cases}\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2,&\text{if}\
\widetilde{G}\ \text{is connected},\\\
\max\\{\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2,n-3\\},&\text{if}\
\widetilde{G}\ \text{is disconnected}.\end{cases}$

###### Proof.

If $\widetilde{G}$ is connected, by [19, Theorem 3.4],
$\operatorname{depth}_{S}(S/J_{G})=\operatorname{depth}_{\widetilde{S}}(\widetilde{S}/J_{\widetilde{G}})$,
where $\widetilde{S}=K[x_{v},y_{v}:v\in V(\widetilde{G})]$. Using the
Auslander–Buchsbaum formula, we obtain
$2n-\operatorname{proj\phantom{,}\\!dim}(J_{G})=2(n-1)-\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})$,
and consequently,

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2.$

Suppose now that $\widetilde{G}$ is disconnected. By [19, Theorem 3.9],

$\operatorname{depth}_{S}(S/J_{G})=\min\\{\operatorname{depth}_{\widetilde{S}}(\widetilde{S}/J_{\widetilde{G}}),n+2\\}.$

Using the Auslander–Buchsbaum formula we obtain

$2n-\operatorname{proj\phantom{,}\\!dim}(J_{G})-1=\min\\{2(n-1)-\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})-1,n+2\\}.$

Therefore,

$\displaystyle\operatorname{proj\phantom{,}\\!dim}(J_{G})\ $ $\displaystyle=\
2n-1-\min\\{2(n-1)-1-\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}}),n+2\\}$
$\displaystyle=\ \max\\{\operatorname{proj\phantom{,}\\!dim}(J_{G})+2,n-3\\},$

as desired.

The following picture describes the set $\textup{pdreg}(n)$ for $n\geq 3$. In
the $(p,r)$th position of the diagram we collocate the pair $(p,r)$ if there
exists $G\in\textup{Graphs}(n)$ such that
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=p$ and
$\operatorname{reg}(J_{G})=r$.

$2$$3$$n$$\ \ \ 2n-5$$2n-6\ \ $ $n$$\ n-1$$\ n-2\ \ $$\cdots$ $\cdots$
$\cdots$ $\cdots$ $\cdots$ $\cdots$ $\cdots$ $n-1\ \ \ \ \ \
$$\lceil\frac{n}{2}\rceil+1\ \ \ \ \ \ \ \ $$\lfloor\frac{n}{2}\rfloor+1\ \ \
\ \ \ \ \ $$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$

$\ddots$

$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$\vdots$

$\ddots$

$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $4$$\cdots$ $\cdots$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$

$\ddots$

$\ddots$

$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$\vdots$ $\vdots$ $\vdots$

$\ddots$

$\ddots$

$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $n-2\ \ \ \ \ \
$$\lceil\frac{n}{2}\rceil-1\ $$\ \ \ \ \cdots$ $\cdots$ $|$$|$$|$$|$$|$$|$

$|$

$|$

$|$

$|$

$|$

$|$

$|$

$|$

Note that the lattice points in the $(n-1)$th row are empty, because we do not
specify the set $A_{n}$ in Theorem 3.1.

Now, we are ready to prove our main result in the article.

###### Proof of Theorem 3.1..

By Propositions 1.4, 1.5 the set $\textup{pdreg}(n)$ is contained in the
second set written in (25). Therefore, we only need to prove the other
inclusion.

We proceed by induction on $n\geq 3$. By induction we also prove the following
Claim $(*)$ For all pairs $(p,r)\in\textup{pdreg}(n)\setminus A_{n}$ with
$p\geq n-2$, there exists a connected graph $G\in\textup{Graphs}(n)$ such that
$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))=(p,r)$.

Now, we start with our inductive proof. If $n=3,4,5,6$, by Example 2.15, the
theorem and the Claim $(*)$ hold true.

Suppose now $n\geq 7$. Let $(p,r)\in\textup{pdreg}(n)$. If $r=2$ or $r=n$,
then $p=n-2$ and the pairs $(n-2,2)$, $(n-2,n)$ belongs to
$\textup{pdreg}(n)$, by virtue of Theorem 1.2(i) and (ii). Hence, we can
consider $3\leq r\leq n-1$. If $p=2n-5,2n-6$, then $3\leq r\leq n-2$ and
$(p,r)\in\textup{pdreg}(n)$ for all such values of $p$ and $r$, by using
Corollaries 2.2 and 2.8 and Proposition 2.7. If $r=3$ or $r=n-2$, all possible
pairs $(p,3)$ and $(p,n-2)$ belong to $\textup{pdreg}(n)$, by Corollary 2.11
and Proposition 2.13.

It remains to construct $G\in\textup{Graphs}(n)$ such that
$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))=(p,r)$
for all $4\leq r\leq n-3$ and all admissible values that $p\leq 2n-7$ can
assume.

Suppose $n-2\leq p\leq 2n-7$ and $4\leq r\leq n-3$. Then
$(p-2,r)\in\textup{pdreg}(n-2)$. To prove this, note that $(n-1)-3\leq p-2\leq
2(n-1)-7$ and $4\leq r\leq(n-1)-2$. Therefore, by induction there exists
$\widetilde{G}\in\textup{Graphs}(n-1)$ such that

$(\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}}),\operatorname{reg}(J_{\widetilde{G}}))=(p-2,r).$

Set $G=\widetilde{G}*K_{1}$. If $p=n-2$, then $p-2=(n-1)-3<(n-1)-2$ and so
$\widetilde{G}$ is disconnected by Theorem 1.1. By Lemma 3.2,

$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\max\\{\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2,n-3\\}=\max\\{n-2,n-3\\}=n-2=p$

and by formula (4),
$\operatorname{reg}(J_{G})=\operatorname{reg}(J_{\widetilde{G}})=r$. Hence,
$G\in\textup{Graphs}(n)$ and

$(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))=(n-2,r),$

and so $(n-2,r)\in\textup{pdreg}(n)$. If $p>n-2$, then $p-2\geq(n-1)-2$ and by
induction and Claim $(*)$ we may assume that $\widetilde{G}$ is connected. By
Lemma 3.2
$\operatorname{proj\phantom{,}\\!dim}(J_{G})=\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+2=p$
and by formula (4),
$\operatorname{reg}(J_{G})=\operatorname{reg}(J_{\widetilde{G}})=r$. Once
again, $(p,r)\in\textup{pdreg}(n)$.

Now the inductive proof of the Claim $(*)$ is completed. Indeed, by Remarks
2.6, 2.10, 2.14 the claim holds for all pairs
$(p,r)\in\textup{pdreg}(n)\setminus A_{n}$, $p\geq n-2$, with $p=2n-6$ or
$p=2n-r$ or $r=3$ or $r=n-2$. For all other pairs
$(p,r)\in\textup{pdreg}(n)\setminus A_{n}$ with $p\geq n-2$, the claim also
holds because the various graphs $\widetilde{G}*K_{1}$ constructed are
connected.

Suppose now $4\leq r\leq\lfloor\frac{n}{2}\rfloor+1$ and $n-r\leq p\leq n-3$.
Then $(p-1,r-1)$ belongs to $\textup{pdreg}(n-2)$. To see why this is true,
note that $3\leq r-1\leq\lfloor\frac{n-2}{2}\rfloor+1$ and also
$(n-2)-(r-1)=n-1-r\leq p-1\leq(n-2)-2$. Therefore, by induction there exists
$\widetilde{G}\in\textup{Graphs}(n-2)$ such that

$(\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}}),\operatorname{reg}(J_{\widetilde{G}}))=(p-1,r-1).$

Set $G=\widetilde{G}\sqcup K_{2}$. Then $G\in\textup{Graphs}(n)$ and

$\displaystyle(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G}))$
$\displaystyle=(\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}})+\operatorname{proj\phantom{,}\\!dim}(J_{K_{2}})+1,\operatorname{reg}(J_{\widetilde{G}})+\operatorname{reg}(J_{K_{2}})-1)$
$\displaystyle=(p-1+0+1,r-1+2-1)=(p,r).$

Consequently, $(p,r)\in\textup{pdreg}(n)$.

Similarly, for the last case, suppose $\lceil\frac{n}{2}\rceil+1\leq r\leq
n-3$ and $r-2\leq p\leq n-3$. Then $(p-1,r-1)\in\textup{pdreg}(n-2)$. Indeed,
$\lceil\frac{n-2}{2}\rceil+1\leq r-1\leq(n-2)-2$ and so $(r-1)-2\leq
p-1\leq(n-2)-2$. Hence, by induction there exists
$\widetilde{G}\in\textup{Graphs}(n-2)$ such that

$(\operatorname{proj\phantom{,}\\!dim}(J_{\widetilde{G}}),\operatorname{reg}(J_{\widetilde{G}}))=(p-1,r-1).$

Let $G=\widetilde{G}\sqcup K_{2}$. Arguing as before, we obtain
$(p,r)\in\textup{pdreg}(n)$, as desired.

The inductive proof is complete, and the theorem is proved.

Denote by $\textup{CGraphs}(n)$ the set of all connected graphs with $n$ non
isolated vertices. We define the set

$\textup{pdreg}_{\textup{C}}(n)\ =\
\big{\\{}(\operatorname{proj\phantom{,}\\!dim}(J_{G}),\operatorname{reg}(J_{G})):G\in\textup{CGraphs}(n)\big{\\}}.$

######  Corollary 3.3.

For all $n\geq 3$,

$\textup{pdreg}_{\textup{C}}(n)\ =\
\big{\\{}(n-2,2),(n-2,n)\big{\\}}\cup\bigcup_{r=3}^{n-2}\big{(}\bigcup_{p=n-2}^{2n-5}\\{(p,r)\\}\big{)}\cup
A_{\textup{C},n},$

where $A_{\textup{C},n}=\\{(p,r)\in\textup{pdreg}_{\textup{C}}(n):r=n-1\\}$.

###### Proof.

For any $G\in\textup{CGraphs}(n)$ we have
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\geq n-2$ by Theorem 1.1. Thus,
our statement follows from Claim $(*)$ proved in the previous theorem.

At present, we do not know yet the sets $A_{n}$ and $A_{\textup{C},n}$, for
$n\geq 7$. Note that by Corollary 2.2 and Proposition 2.7, for all $n\geq 6$,
if $G$ is a graph with $n$ non isolated vertices and with
$\operatorname{reg}(J_{G})=n-1$, then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq 2n-7$. On the other hand, if
$n\geq 7$ and $\operatorname{reg}(J_{G})=n-1$, a much stronger bound for the
projective dimension of $J_{G}$ seems to hold. Indeed, our experiments using
[21] suggest the following

######  Conjecture 3.4.

Let $G$ be a graph with $n\geq 7$ non isolated vertices. Suppose that
$\operatorname{reg}(J_{G})=n-1$. Then
$\operatorname{proj\phantom{,}\\!dim}(J_{G})\leq n$.

Using [21] we could verify our conjecture for $n=7,8,9$.

## References

  * [1] A. Banerjee, L. Núñez-Betancourt, Graph connectivity and binomial edge ideals. Proc. Amer. Math. Soc. 145, 487–499 (2017).
  * [2] N. Boria, F. Della Croce and V. Th. Paschos, On the max min vertex cover problem, Disc. Appl. Math. 196 (2015), 62–71.
  * [3] N. Bourgeois, F. Della Croce, B. Escoffier and V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Appl. Math. 161 (2013), 4-5, 558–572.
  * [4] V. Costa, E. Haeusler, E.S. Lamer and L. Nogueira, A note on the size of minimal covers, Info. Proc. Lett. 102 (2007), 124–126.
  * [5] V. Ene, G. Rinaldo, N. Terai, Licci binomial edge ideals. J. Combin. Theory Ser. A, 175:105278, 23, 2020.
  * [6] N. Erey, T. Hibi, The size of Betti tables of edge ideals arising from bipartite graphs. 2020, arXiv preprint, available at https://arxiv.org/abs/2103.04766.
  * [7] D. R. Grayson, M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2.
  * [8] H.T. Hà, T. Hibi, MAX MIN vertex cover and the size of Betti tables. Ann. Combin. 25, 115–132 (2021).
  * [9] M.M. Halldórsson, Approximating the minimum maximal independence number, Inform. Process. Lett. 46 (1993) 169–172.
  * [10] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence statements. Adv. Appl. Math. 45, 317–333 (2010).
  * [11] J. Herzog, G. Rinaldo, On the extremal Betti numbers of binomial edge ideals of block graphs, Electron. J. Combin. 25(1) (2018).
  * [12] T. Hibi, H. Kanno, K. Kimura, K. Matsuda and A. Van Tuyl, Homological invariants of Cameron–Walker graphs, Trans. Amer. Math. Soc. 374 (2021), 6559–6582.
  * [13] T. Hibi, H. Kanno, K. Matsuda, Induced matching numbers of finite graphs and edge ideals, J. Algebra 532 (2019), 311–322.
  * [14] T. Hibi, K. Kimura, K. Matsuda, A. Tsuchiya, Regularity and a-invariant of Cameron–Walker graphs, J. Algebra 584 (2021) 215–242.
  * [15] T. Hibi, K. Kimura, K. Matsuda, A. Van Tuyl, The regularity and h-polynomial of Cameron–Walker graphs, 2020, arXiv preprint, available at https://arxiv.org/abs/2003.07416.
  * [16] T. Hibi, S. Saeedi Madani. Diameter and connectivity of finite simple graphs. 2021, arXiv preprint https://arxiv.org/abs/2103.14260.
  * [17] A. Higashitani, A. Kanno, R. Ueji, Behaviors of pairs of dimensions and depths of edge ideals, 2023, arXiv preprint, available at https://arxiv.org/abs/2301.04763.
  * [18] D. Kiani, S. Saeedi Madani, The Castelnuovo–Mumford regularity of binomial edge ideals. J. Combin. Theory Ser. A. 139, 80–86 (2016).
  * [19] A. Kumar, R. Sarkar. Depth and extremal Betti number of binomial edge ideals. Math. Nachr., 293(9):1746–1761, 2020.
  * [20] K. Matsuda, S. Murai, Regularity bounds for binomial edge ideals. J. Commutative Algebra. 5(1), 141–149 (2013).
  * [21] B. D. McKay, A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. The software package Nauty is available at http://cs.anu.edu.au/~bdm/nauty/
  * [22] F. Mohammadi, L. Sharifan, Hilbert function of binomial edge ideals, Comm. Algebra 42 (2014) 688–703.
  * [23] H. Mukherjee, P. Das, Homological properties of binomial edge ideal of a graphs, 2022, arXiv preprint, available at https://arxiv.org/abs/2209.01201.
  * [24] M. Ohtani, Graphs and ideals generated by some 2-minors. Comm. Algebra. 39, 905–917 (2011).
  * [25] A. Rauf, G. Rinaldo, Construction of Cohen-Macaulay binomial edge ideals, Comm. Algebra 42 (2014), 238–252.
  * [26] M. Rouzbahani Malayeri, S. Saeedi Madani, D. Kiani, Binomial edge ideals of small depth. J. Algebra. 572, 231–244 (2021).
  * [27] M. Rouzbahani Malayeri, S. Saeedi Madani, D. Kiani. On the depth of binomial edge ideals of graphs. J. Algebraic Combin., 55(3):827–846, 2022.
  * [28] S. Saeedi Madani, D. Kiani, Binomial edge ideals of graphs. Electron. J. Combin. 19(2), P44 (2012).
  * [29] S. Saeedi Madani, D. Kiani, Binomial edge ideals of regularity 3. J. Algebra. 515, 157–172 (2018).