11institutetext: Department of Computer Science, Durham University, Durham, UK
<EMAIL_ADDRESS>
22institutetext: School of Computing, Newcastle University, Newcastle upon
Tyne, UK<EMAIL_ADDRESS>

Authors’ Instructions

# An Exploration of Dropout with RNNs for Natural Language Inference

Amit Gajbhiye 11 Sardar Jaf 11 Noura Al Moubayed 11 A. Stephen McGough 22
Steven Bradley 11

###### Abstract

Dropout is a crucial regularization technique for the Recurrent Neural Network
(RNN) models of Natural Language Inference (NLI). However, dropout have not
been evaluated for the effectiveness at different layers and dropout rates in
NLI models. In this paper, we propose a RNN model for NLI and empirically
evaluate the effect of applying dropout at different layers in the model. We
also investigate the impact of varying dropout rates at these layers. Our
empirical evaluation on a large (Stanford Natural Language Inference (SNLI))
and a small (SciTail) dataset suggest that dropout at each feed-forward
connection severely affect the model accuracy at increasing dropout rates. We
also show that regularizing the embedding layer is efficient for SNLI whereas
regularizing the recurrent layer improves the accuracy for SciTail. Our model
achieved an accuracy $86.14\%$ on the SNLI dataset and $77.05\%$ on SciTail.

###### Keywords:

Neural Networks, Dropout, Natural Language Inference.

##  1 Introduction

Natural Language Understanding (NLU) is the process to enable computers to
understand the semantics of natural language text. The inherent complexities
and ambiguities in natural language text make NLU challenging for computers.
Natural Language Inference (NLI) is a fundamental step towards NLU [14]. NLI
involves logically inferring a hypothesis sentence from a given premise
sentence.

The recent release of a large public dataset the Stanford Natural Language
Inference (SNLI) [2] has made it feasible to train complex neural network
models for NLI. Recurrent Neural Networks (RNNs), particularly bidirectional
LSTMs (BiLSTMs) have shown state-of-the-art results on the SNLI dataset [9].
However, RNNs are susceptible to overfitting $-$ the case when a neural
network learns the exact patterns present in the training data but fails to
generalize to unseen data [21]. In NLI models, regularization techniques such
as early stopping [4], L2 regularization and dropout [20] are used to prevent
overfitting.

For RNNs, dropout is an effective regularization technique [21]. The idea of
dropout is to randomly omit computing units in a neural network during
training but to keep all of them for testing. Dropout consists of element-wise
multiplication of the neural network layer activations with a zero-one mask
$(r_{j})$ during training. Each element of the zero-one mask is drawn
independently from $r_{j}\sim\textrm{Bernoulli}(p)$, where $p$ is the
probability with which the units are retained in the network. During testing,
activations of the layer are multiplied by $p$ [19].

Dropout is a crucial regularization technique for NLI [9][20]. However, the
location of dropout varies considerably between NLI models and is based on
trail-and-error experiments with different locations in the network. To the
best of our knowledge no prior work has been performed to evaluate the
effectiveness of dropout location and rates in the RNN NLI models.

In this paper, we study the effect of applying dropout at different locations
in an RNN model for NLI. We also investigate the effect of varying the dropout
rate. Our results suggest that applying dropout for every feed forward
connection, especially at higher dropout rates degrades the performance of
RNN. Our best model achieves an accuracy of 86.14% on the SNLI dataset and an
accuracy of 77.05% on SciTail dataset.

To the best of our knowledge this research is the first exploratory analysis
of dropout for NLI. The main contributions of this paper are as follows: (1) A
RNN model based on BiLSTMs for NLI. (2) A comparative analysis of different
locations and dropout rates in the proposed RNN NLI model. (3) Recommendations
for the usage of dropout in the RNN models for NLI task.

The layout of the paper is as follows. In Section 2, we describe the related
work. In Section 3, we discuss the proposed RNN based NLI model. Experiments
and the results are presented in Section 4. Recommendations for the
application of dropouts are presented in Section 5. We conclude in Section 6.

##  2 Related Work

The RNN NLI models follow a general architecture. It consists of : (1) an
embedding layer that take as input the word embeddings of premise and
hypothesis (2) a sentence encoding layer which is generally an RNN that
generates representations of the input (3) an aggregation layer that combines
the representations and; (4) a classifier layer that classifies the
relationship (entailment, contradiction or neutral) between premise and
hypothesis.

Different NLI models apply dropout at different layers in general NLI
architecture. NLI models proposed by Ghaeini et al. [9] and Tay et al. [20]
apply dropout to each feed-forward layer in the network whereas others have
applied dropout only to the final classifier layer [13]. Bowman et al. [2]
apply dropout only to the input and output of sentence encoding layers.The
models proposed by Bowman et al. [3] and Choi et al. [7] applied dropout to
the output of embedding layer and to the input and output of classifier layer.
Chen et al. [4] and Cheng et al. [6] use dropout but they do not elaborate on
the location.

Dropout rates are also crucial for the NLI models [15]. Even the models which
apply dropout at the same locations vary dropout rates.

Previous research on dropout for RNNs on the applications such as neural
language models [16], handwriting recognition [18] and machine translation
[21] have established that recurrent connection dropout should not be applied
to RNNs as it affects the long term dependencies in sequential data.

Bluche et al. [1] studied dropout at different places with respect to the LSTM
units in the network proposed by [18] for handwriting recognition. The results
show that significant performance difference is observed when dropout is
applied to distinct places. They concluded that applying dropout only after
recurrent layers (as applied by Pham et al. [18]) or between every feed-
forward layer (as done by Zaremba et al. [21]) does not always yield good
results. Cheng et al. [5], investigated the effect of applying dropout in
LSTMs. They randomly switch off the outputs of various gates of LSTM,
achieving an optimal word error rate when dropout is applied to output, forget
and input gates of the LSTM.

Evaluations in previous research were conducted on datasets with fewer
samples. We evaluate the RNN model on a large, SNLI dataset (570,000 data
sample) as well as on a smaller SciTail dataset (27,000 data samples).
Furthermore, previous studies concentrate only on the location of dropout in
the network with fixed dropout rate.We further investigate the effect of
varying dropout rates. We focus on the application of widely used conventional
dropout [19] to non-recurrent connection in RNNs.

##  3 Recurrent Neural Network Model for NLI Task

The proposed RNN NLI model follows the general architecture of NLI models and
is depicted in Fig.1. The model combines the intra-attention model [13] with
soft-attention mechanism [11].

Figure 1: The Recurrent Neural Network Model with possible Dropout Locations

The embedding layer takes as input word embeddings in the sentence of length
$L$. The recurrent layer with BiLSTM units encodes the sentence. Next, the
intra-attention layer generates the attention weighted sentence representation
following the Equations $(\ref{eq:M})-(\ref{eq:R})$

$M=\tanh\left(W^{y}Y+W^{h}R_{avg}\otimes{e}_{L}\right)$ (1)
$\alpha=softmax\left(w^{T}M\right)$ (2) $R=Y\alpha^{T}$ (3)

where, $W^{y}$, $W^{h}$ are trained projection matrices, $w^{T}$ is the
transpose of trained parameter vector $w$, $Y$ is the matrix of hidden output
vectors of the BiLSTM layer, $R_{avg}$ is obtained from the average pooling of
$Y$, $e_{L}\in{\mathbb{R}}^{L}$ is a vector of 1s, $\alpha$ is a vector of
attention weights and $R$ is the attention weighted sequence representation.
The attention weighted sequence representation is generated for premise and
hypothesis and is denoted as $R_{p}$ and $R_{h}$. The attention weighted
representation gives more importance to the words which are important to the
semantics of the sequence and also captures its global context.

The interaction between $R_{p}$ and $R_{h}$ is performed by inter-attention
layer, following the Equations $(\ref{eq:Iv})-(\ref{eq:RhTilde})$.

$I_{v}=R_{p}^{T}R_{h}$ (4) $\tilde{R_{p}}=softmax(I_{v})R_{h}$ (5)
$\tilde{R_{h}}=softmax(I_{v})R_{p}$ (6)

where, $I_{v}$ is the interaction vector. $\tilde{R_{p}}$ contains the words
which are relevant based on the content of sequence $R_{h}$. Similarly,
$\tilde{R_{h}}$ contains words which are important with respect to the content
of sequence $R_{p}$. The final sequence encoding is obtained from the element-
wise multiplication of intra-attention weighted representation and inter-
attention weighted representation as follows:

$F_{p}=\tilde{R_{p}}\odot{R_{p}}$ (7) $F_{h}=\tilde{R_{h}}\odot{R_{h}}$ (8)

To classify the relationship between premise and hypothesis a relation vector
is formed from the encoding of premise and hypothesis generated in Equation
(7) and (8), as follows:

$\textrm{v}_{p,avg}=\textrm{averagepooling}(F_{p}),\textrm{v}_{p,max}=\textrm{maxpooling}(F_{p})$
(9)
$\textrm{v}_{h,avg}=\textrm{averagepooling}(F_{h}),\textrm{v}_{h,max}=\textrm{maxpooling}(F_{h})$
(10)
$F_{relation}=\left[\textrm{v}_{p,avg};\textrm{v}_{p,max};\textrm{v}_{h,avg};\textrm{v}_{h,max}\right]$
(11)

where v is a vector of length $L$. The relation vector
$\left(F_{relation}\right)$ is fed to the MLP layer. The three-way softmax
layer outputs the probability for each class of NLI.

##  4 Experiments and Results

###  4.1 Experimental Setup

The standard train, validation and test splits of SNLI[2] and SciTail [10] are
used in empirical evaluations. The validation set is used for hyper-parameter
tuning. The non-regularized model is our baseline model. The parameters for
the baseline model are selected separately for SNLI and SciTail dataset by a
grid search from the combination of L2 regularization $[1e-4,1e-5,1e-6]$,
batch size $[32,64,256,512]$ and learning rate $[0.001,0.0003,0.0004]$. The
Adam [12] optimizer with first momentum is set to $0.9$ and the second to
$0.999$ is used. The word embeddings are initialized with pre-trained 300-D
Glove 840B vectors [17]. Extensive experiments with dropout locations and
hidden units were conducted however we show only the best results for brevity
and space limits.

###  4.2 Dropout at Different Layers for NLI Model

Table 1 presents the models with different combinations of layers to the
output of which dropout are applied in our model depicted in Fig. 1.

Table 1: Models with corresponding layers to the outputs of which dropout is applied. Model | Layer
---|---
Model 1 | No Dropout (Baseline)
Model 2 | Embedding
Model 3 | Recurrent
Model 4 | Embedding and Recurrent
Model 5 | Recurrent and Intra-Attention
Model 6 | Inter-Attention and MLP
Model 7 | Recurrent, Inter-Attention and MLP
Model 8 | Embedding, Inter-Attention and MLP
Model 9 | Embedding, Recurrent, Inter-Attention and MLP
Model 10 | Recurrent, Intra-Attention, Inter-Attention and MLP
Model 11 | Embedding, Intra-Attention, Inter-Attention and MLP
Model 12 | Embedding, Recurrent, Intra-Attention, Inter-Attention and MLP
Model 13 | Embedding, Recurrent, Inter-Attention and MLP

Table 2. shows the results for the models in Table 1. Each model is evaluated
with dropout rates ranging from 0.1 to 0.5 with a granularity of 0.1.

Table 2: Model accuracy with varying dropout rates for SNLI and SciTail datasets. Bold numbers shows the highest accuracy for the model within the dropout range. Models | Dataset |  Dropout Rate (DR)
---|---|---
|  | 0.1 | 0.2 | 0.3 | 0.4 | 0.5
Model 1 | SNLI | 84.45
| SciTail | 74.18
Model 2 | SNLI | 84.56 | 84.59 | 84.42 | 86.14 | 84.85
| SciTail | 75.45 | 75.12 | 74.22 | 73.10 | 74.08
Model 3 | SNLI | 84.12 | 84.21 | 83.76 | 81.04 | 79.63
| SciTail | 76.15 | 75.78 | 73.50 | 73.19 | 75.26
Model 4 | SNLI | 83.83 | 85.22 | 84.34 | 80.82 | 79.92
| SciTail | 74.65 | 76.08 | 74.22 | 74.46 | 73.19
Model 5 | SNLI | 84.72 | 83.43 | 72.89 | 70.49 | 62.13
| SciTail | 75.87 | 75.13 | 75.26 | 73.71 | 72.25
Model 6 | SNLI | 84.17 | 84.32 | 83.71 | 82.79 | 81.68
| SciTail | 73.85 | 75.68 | 75.26 | 73.95 | 73.28
Model 7 | SNLI | 84.33 | 82.97 | 82.00 | 81.15 | 79.25
| SciTail | 73.75 | 75.02 | 74.37 | 73.37 | 73.42
Model 8 | SNLI | 84.67 | 85.82 | 84.60 | 84.14 | 83.94
| SciTail | 73.80 | 73.52 | 69.29 | 75.82 | 73.89
Model 9 | SNLI | 84.44 | 83.05 | 82.09 | 81.64 | 79.62
| SciTail | 75.68 | 76.11 | 75.96 | 70.84 | 74.55
Model 10 | SNLI | 84.45 | 80.95 | 75.31 | 70.81 | 69.34
| SciTail | 73.30 | 75.21 | 74.98 | 74.65 | 71.59
Model 11 | SNLI | 84.31 | 82.43 | 78.94 | 74.93 | 70.54
| SciTail | 75.63 | 73.47 | 74.93 | 74.93 | 70.32
Model 12 | SNLI | 84.32 | 82.60 | 73.36 | 71.53 | 66.67
| SciTail | 73.47 | 75.63 | 74.74 | 73.42 | 74.40

Dropout at Individual Layers We first apply dropout at each layer including
the embedding layer. Although the embedding layer is the largest layer it is
often not regularized for many language applications [8]. However, we observe
the benefit of regularizing it. For SNLI, the highest accuracy is achieved
when the embedding layer is regularized (Model 2, DR 0.4).

For SciTail, the highest accuracy is obtained when the recurrent layer is
regularized (Model 3, DR 0.1). The dropout injected noise at lower layers
prevents higher fully connected layers from overfitting. We further
experimented regularizing higher fully connected layers (Intra-Attention,
Inter-Attention, MLP) individually, however no significant performance gains
observed.

Dropout at Multiple Layers We next explore the effect of applying dropout at
multiple layers. For SNLI and SciTail, the models achieve higher performance
when dropout is applied to embedding and recurrent layer (Model 4, DR 0.2).
This supports the importance of regularizing embedding and recurrent layer as
shown for individual layers.

It is interesting to note that regularizing the recurrent layer helps SciTail
(Model 7, DR 0.2) whereas regularizing the embedding layer helps SNLI (Model
8, DR 0.2). A possible explanation to this is that for the smaller SciTail
dataset the model can not afford to lose information in the input, whereas for
the larger SNLI dataset the model has a chance to learn even with the loss of
information in input. Also, the results from models 7 and 8 suggests that
applying dropout at a single lower layer (Embedding or Recurrent; depending on
the amount of training data) and to the inputs and outputs of MLP layer
improves performance.

We can infer from models 9, 10, 11 and 12 that applying dropout to each feed
forward connection helps preventing the model overfit for SciTail (DR 0.1 and
0.2). However, for both the datasets with different dropout locations the
performance of the model decreases as the dropout rate increases (Section
4.4).

###  4.3 The Effectiveness of Dropout for Overfitting

We study the efficacy of dropout on overfitting. The main results are shown in
Fig. 2. For SNLI, Fig. 2 (a) - (b), shows the convergence curves for the
baseline model and the model achieving the highest accuracy (Model 2, DR 0.4).
The convergence curve show that dropout is very effective in preventing
overfitting. However, for the smaller SciTail dataset when regularizing
multiple layers we observe that the highest accuracy achieving model (Model 9,
DP 0.2), overfits significantly (Fig. 2(d)). This overfitting is due to the
large model size. With limited training data of SciTail, our model with higher
number of hidden units learns the relationship between the premise and the
hypothesis most accurately (Fig. 2(d)). However, these relationships are not
representative of the validation set data and thus the model does not
generalize well. When we reduced the model size (50, 100 and 200 hidden units)
we achieved the best accuracy for SciTail at 100 hidden units (Table 3). The
convergence curve (Fig. 2(c)) shows that dropout effectively prevents
overfitting in the model with 100 hidden units in comparison to 300 units.

Figure 2: Convergence Curves: (a) Baseline Model for SNLI, (b) Best Model for SNLI, (c) 100 Unit Model for SciTail, (d) 300 Unit Model for SciTail  Table 3: Accuracy of 100 unit model for SciTail dataset Models | Dataset |  Dropout Rate (DR)
---|---|---
|  | 0.1 | 0.2 | 0.3 | 0.4 | 0.5
Model 13 | SciTail | 76.72 | 76.25 | 72.58 | 77.05 | 74.22

Furthermore, for SciTail dataset, the model with 100 units achieved higher
accuracy for almost all the experiments when compared to models with 50, 200
and 300 hidden units.

The results of this experiment suggest that given the high learning capacity
of RNNs an appropriate model size selection according to the amount of
training data is essential. Dropout may independently be insufficient to
prevent overfitting in such scenarios.

###  4.4 Dropout Rate Effect on Accuracy and Dropout Location

We next investigate the effect of varying dropout rates on the accuracy of the
models and on various dropout locations. Fig 3. illustrates varying dropout
rates and the corresponding test accuracy for SNLI. We observe some distinct
trends from the plot. First, the dropout rate and location does not affect the
accuracy of the models 2 and 8 over the baseline. Second, in the dropout range
[0.2 - 0.5], the dropout locations affect the accuracy of the models
significantly. Increasing the dropout rate from 0.2 to 0.5 the accuracy of
models 5 and 12 decreases significantly by 21.3% and 15.9% respectively. For
most of the models (3, 4, 6, 7, 9 and 10) the dropout rate of 0.5 decreases
accuracy.

Figure 3: Plot showing the variation of test accuracy across the dropout range
for SNLI.

From the experiments on SciTail dataset (Fig. 4), we observed that the dropout
rate and its location do not have significant effect on most of the models,
with the exception of model 8 (which shows erratic performance).

Figure 4: Plot showing the variation of test accuracy across the dropout range
for SciTail.

Finally, for almost all the experiments a large dropout rate (0.5) decreases
the accuracy of the models. The dropout rate of 0.5 works for a wide rang of
neural networks and tasks [19]. However, our results show that this is not
desirable for RNN models of NLI. Based on our evaluations a dropout range of
$[0.2-0.4]$ is advised.

##  5 Recommendations for Dropout Application

Based on our empirical evaluations, the following is recommended for
regularizing a RNN model for NLI task: (1) Embedding layer should be
regularized for large datasets like SNLI. For smaller datasets such as SciTail
regularizing recurrent layer is an efficient option. The dropout injected
noise at these layers prevent the higher fully connected layers from
overfitting. (2) When regularizing multiple layers, regularizing a lower layer
(embedding or recurrent; depending on the amount of data) with the inputs and
outputs of MLP layer should be considered. The performance of our model
decreased when dropout is applied at each intermediate feed-forward
connection. (3) When dropout is applied at multiple feed forward connections,
it is almost always better to apply it at lower rate $-$ $[0.2-0.4]$. (4)
Given the high learning capacity of RNNs, an appropriate model size selection
according to the amount of training data is essential. Dropout may
independently be insufficient to prevent overfitting in the scenarios
otherwise.

##  6 Conclusions

In this paper, we reported the outcome of experiments conducted to investigate
the effect of applying dropout at different layers in an RNN model for the NLI
task. Based on our empirical evaluations we recommended the probable locations
of dropouts to gain high performance on NLI task. Through extensive
exploration, for the correct dropout location in our model, we achieved the
accuracies of 86.14% on SNLI and 77.05% on SciTail datasets. In future
research, we aim to investigate the effect of different dropout rates at
distinct layers.

## References

  * [1] Bluche, T., Kermorvant, C., Louradour, J.: Where to apply dropout in recurrent neural networks for handwriting recognition? In: Document Analysis and Recognition (ICDAR), 2015 13th International Conference on. pp. 681–685. IEEE (2015)
  * [2] Bowman, S.R., Angeli, G., Potts, C., Manning, C.D.: A large annotated corpus for learning natural language inference. In: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. pp. 632–642. Association for Computational Linguistics (2015)
  * [3] Bowman, S.R., Gauthier, J., Rastogi, A., Gupta, R., Manning, C.D., Potts, C.: A fast unified model for parsing and sentence understanding. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). vol. 1, pp. 1466–1477 (2016)
  * [4] Chen, Q., Zhu, X., Ling, Z.H., Inkpen, D.: Natural language inference with external knowledge. arXiv preprint arXiv:1711.04289 (2017)
  * [5] Cheng, G., Peddinti, V., Povey, D., Manohar, V., Khudanpur, S., Yan, Y.: An exploration of dropout with lstms. In: Proceedings of Interspeech (2017)
  * [6] Cheng, J., Dong, L., Lapata, M.: Long short-term memory-networks for machine reading. In: Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. pp. 551–561 (2016)
  * [7] Choi, J., Yoo, K.M., goo Lee, S.: Learning to compose task-specific tree structures. AAAI (2017)
  * [8] Gal, Y., Ghahramani, Z.: A theoretically grounded application of dropout in recurrent neural networks. In: Advances in neural information processing systems. pp. 1019–1027 (2016)
  * [9] Ghaeini, R., Hasan, S.A., Datla, V., Liu, J., Lee, K., Qadir, A., Ling, Y., Prakash, A., Fern, X.Z., Farri, O.: Dr-bilstm: Dependent reading bidirectional lstm for natural language inference. arXiv preprint arXiv:1802.05577 (2018)
  * [10] Khot, T., Sabharwal, A., Clark, P.: Scitail: A textual entailment dataset from science question answering. In: Proceedings of AAAI (2018)
  * [11] Kim, Y., Denton, C., Hoang, L., Rush, A.M.: Neural machine translation by jointly learning to align and translate. Proceedings of ICLR (2017)
  * [12] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [13] Liu, Y., Sun, C., Lin, L., Wang, X.: Learning natural language inference using bidirectional lstm model and inner-attention. CoRR abs/1605.09090 (2016)
  * [14] MacCartney, B.: Natural language inference. Stanford University (2009)
  * [15] Munkhdalai, T., Yu, H.: Neural tree indexers for text understanding. In: Proceedings of the conference. Association for Computational Linguistics. Meeting. vol. 1, p. 11. NIH Public Access (2017)
  * [16] Pachitariu, M., Sahani, M.: Regularization and nonlinearities for neural language models: when are they needed? arXiv preprint arXiv:1301.5650 (2013)
  * [17] Pennington, J., Socher, R., Manning, C.: Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532–1543 (2014)
  * [18] Pham, V., Bluche, T., Kermorvant, C., Louradour, J.: Dropout improves recurrent neural networks for handwriting recognition. In: Frontiers in Handwriting Recognition (ICFHR), 2014 14th International Conference on. pp. 285–290. IEEE (2014)
  * [19] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Dropout: A simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research 15(1), 1929–1958 (2014)
  * [20] Tay, Y., Tuan, L.A., Hui, S.C.: A compare-propagate architecture with alignment factorization for natural language inference. arXiv preprint arXiv:1801.00102 (2017)
  * [21] Zaremba, W., Sutskever, I., Vinyals, O.: Recurrent neural network regularization. arXiv preprint arXiv:1409.2329 (2014)


# Maximal signed bipartite graphs with totally disconnected graphs as star
complements 111This research is partially supported by NSFC of China No.
12171088.

Huiqun Jiang∗<EMAIL_ADDRESS>Yue Liu  School of Mathematics and
Statistics, Fuzhou University, Fuzhou, 350108, Fujian, China.

###### Abstract

Let $\dot{\mathscr{B}}\triangleq\dot{\mathscr{B}}_{\dot{H},\mu}$ denote an
arbitrary signed bipartite graph with $\dot{H}$ as a star complement for an
eigenvalue $\mu$, where $\dot{H}$ is a totally disconnected graph of order
$s$. In this paper, by using Hadamard and Conference matrices as tools, the
maximum order of $\dot{\mathscr{B}}$ and the extremal graphs are studied. It
is shown that $\dot{\mathscr{B}}$ exists if and only if $\mu^{2}$ is a
positive integer. A formula of the maximum order of $\dot{\mathscr{B}}$ is
given in the case of $\mu^{2}=p\times q$ such that $p$, $q$ are integers and
there exists a $p$-order Hadamard or $(p+1)$-order Conference matrix. In
particular, it is proved the maximum order of $\dot{\mathscr{B}}$ is $2s$ when
either $q=1$, $s=c\mu^{2}=cp$ or $q=1$, $s=c(\mu^{2}+1)=c(p+1)$,
$c=1,2,3,\cdots$. Futhermore, some extremal graphs are characterized.

###### keywords:

Star complement; Signed bipartite graph; Totally disconnected graph; Hadamard
matrix; Conference matrix

##  1 Introduction

A signed graph is a pair $(G,\sigma)$, where $G$ is a simple graph, called the
underlying graph, and $\sigma:E\to\\{-1,\,1\\}$ is a mapping, called the sign
function or signature. In certain circumstances, it will be more convenient to
deal with $(G,\sigma)$ in such a way that its set of negative edges is
emphasized, in which case we will write $(G,\,\Sigma^{-})$ instead, where
$\Sigma^{-}=\sigma^{-1}(-)$ denotes the set of negatives edges. A simple graph
$G$ can be regarded as a signed graph $(G,\emptyset)$.

The Reconstruction Theorem is well-known in the study of the spectrum of
simple or signed graphs, which is firstly proved by
Cvetkovi$\acute{\text{c}}$, Rowlison and Simi$\acute{\text{c}}$ in [1]. The
role of an individual eigenvalue in the structure of a simple or signed graph
is revealed by the theorem.

The star complement technique [3] is a procedure for constructing a simple or
signed graph with a prescribed star complement for an eigenvalue to illustrate
the use of the Reconstruction Theorem. In this procedure, there is a necessary
condition that the eigenvalue does not appear in the spectrum of the
prescribed star complement. In [8], by using this technique and the Kronecker
product, Ramezani constructs some families of the signed graphs with only two
opposite eigenvales.

The typical usages of this technique are to determine the maximum order of
simple or signed graphs, and construct maximal simple or signed graphs. In
[9], by using this technique, Ramezani, Rowlinson and Stani$\acute{\text{c}}$
prove that the maximum order $n$ of signed graphs is no more than
$\tbinom{n-k+2}{3}$, in which $k$ is the multiplicity of an eigenvalue
$\mu\notin\\{-1,0,1\\}$. In [13], Yuan, Mao and Liu characterize maximal
signed graphs with signed $C_{3}$ or $C_{5}$ as star complements for $-2$. In
[6], Mulas and Stani$\acute{\text{c}}$ characterize maximal signed graphs
$(G,\Sigma^{-})$ with any signed subgraphs whose spectrum lies in $(-2,2)$ as
star complements, where $(G,\Sigma^{-})$ has the eigenvalues $\pm 2$.

Let $\dot{H}\triangleq(sK_{1},\emptyset)$ be a totally disconnected signed
graph of order $s$. In [11], Stani$\acute{\text{c}}$ studies signed graphs
$(G,\,\Sigma^{-})$ with $\dot{H}$ as a star complement for an eigenvalue
$\mu$. It is shown that if $s=\mu^{2}$, then the star set induces
$\big{(}(n-\mu^{2})K_{1},\emptyset\big{)}$ or
$\big{(}K_{n-\mu^{2}},\,\emptyset\big{)}$, and the number of different
eigenvalues of $(G,\,\Sigma^{-})$ is two or three, where $n$ is the order of
$(G,\,\Sigma^{-})$.

It is easy to see $(G,\Sigma^{-})$ is bipartite in the case that the star set
induces $\big{(}(n-\mu^{2})K_{1},\emptyset\big{)}$. Therefore, we study the
following problem in this paper:

Problem $\mathcal{P}$: Let $\dot{H}$ be a totally disconnected graph of order
$s$, $\mu$ be a non-zero real number. What is the maximum order of the signed
bipartite graph $\dot{\mathscr{B}}$ such that $\dot{\mathscr{B}}$ has
$\dot{H}$ as a star complement for the eigenvalue $\mu$ ?

In Section 3, we show that $\dot{\mathscr{B}}$ exists if and only if $\mu^{2}$
is a positive integer and $s\geq\mu^{2}$ (see Proposition 3.1). Since the
adjacency matrix of $\dot{\mathscr{B}}$ can be orthogonal, then Hadamard and
Conference matrices can be tools to study the problem $\mathcal{P}$. We can
find some properties of Hadamard and Conference matrices in [5].

A formula of the maximum order of $\dot{\mathscr{B}}$ is given in the case of
$\mu^{2}=p\times q$ such that $p$, $q$ are integers and there exists a
$p$-order Hadamard or $(p+1)$-order Conference matrix. In particular, the
maximum order of $\dot{\mathscr{B}}$ is $2s$ in the case of $s=c\mu^{2}$ such
that $\mu^{2}$ is the order of a Hadamard matrix, or $s=c(\mu^{2}+1)$ such
that $\mu^{2}+1$ is the order of a Conference matrix (see Corollary 3.11).

The Section 2 contains terminologies and notations along with the
Reconstruction Theorem. In Section 4, some extremal graphs are characterized.

##  2 Preliminaries

Let $(G,\Sigma^{-})$ be a signed graph of order $n$. If the vertices $u$ and
$v$ of $(G,\Sigma^{-})$ are adjacent, then we write $u\sim v$. In particular,
if they are adjacent by a positive (or negative) edge, then we write
$u\stackrel{{\scriptstyle+}}{{\sim}}v$ (or
$u\stackrel{{\scriptstyle-}}{{\sim}}v$ ). If $u$ and $v$ are not adjacent,
then we write $u\nsim v$. The adjacency matrix of $(G,\Sigma^{-})$ is the
$n\times n$ matrix $A_{(G,\Sigma^{-})}=(a_{ij})$, where $a_{ij}=1$ if
$u\stackrel{{\scriptstyle+}}{{\sim}}v$, $a_{ij}=-1$ if
$u\stackrel{{\scriptstyle-}}{{\sim}}v$ and $a_{ij}=0$ if $u\nsim v$.

Let $\mu$ be an eigenvalue of $(G,\Sigma^{-})$ with the multiplicity $k$. If
$S$ is a subset of the set $V(G)$ such that $|S|=k$ and $\mu$ is not an
eigenvalue of the induced subgraph $(G,\Sigma^{-})-S$, then $S$ is called a
star set for $\mu$ in $(G,\Sigma^{-})$ and the graph $(G,\Sigma^{-})-S$ (of
order $n-k$) is called a star complement for $\mu$ in $(G,\Sigma^{-})$. The
properties of star sets and star complements for the corresponding eigenvalues
can be found in [1, 2, 3].

The following result, called the Reconstruction Theorem, is fundamental to the
theory of star complements.

######  Theorem 2.1.

[9, Theorem 2.1] Let $(G,\Sigma^{-})$ be a graph with adjacency matrix

$\left(\begin{array}[]{cc}A_{S}&B^{T}\\\ B&C\end{array}\right),$

where $A_{S}$ is the $k\times k$ adjacency matrix of the subgraph induced by a
vertex set $S$. Then $S$ is a star set for $\mu$ in $(G,\Sigma^{-})$ if and
only if $\mu$ is not an eigenvalue of $C$ and

$\mu I-A_{S}=B^{T}(\mu I-C)^{-1}B.$ (1)

This result is initially formulated in the context of simple graphs. Since
every simple graph can be interpreted as a signed graph, then it follows that
Theorem 2.1 is an extension of [2, Theorem 7.4.1]. In [2, 3],
Cvetkovi$\acute{\text{c}}$, Rowlinson and Simi$\acute{\text{c}}$ prove that
star sets and star complements exist for any eigenvalues in simple or signed
graphs.

In order to solve the problem $\mathcal{P}$, it is necessary to compute an
inverse of an inversable matrix forming as $\mu I-C$. In [3, Proposition
5.2.1], there is the way to compute the matrix $(\mu I-C)^{-1}$.

Let $S$ be a star set of order $k$ for $\mu$ in $(G,\Sigma^{-})$. A bilinear
form on $\mathbb{R}^{n-k}$ is defined as follows:

$\langle x,\,y\rangle=x^{T}(\mu I-C)^{-1}y\quad(x,\,y\in\mathbb{R}^{n-k}).$

Let $u$ be a vertex in $S$, $\mathbf{b}_{u}$ be a row of $B^{T}$ which
determines the neighbors of $u$ in the signed subgraph $(G,\Sigma^{-})-S$ and
the signatures of associate edges. By Equation (1), for every two vertices
$u,\,v\in S$, we have

$\langle\mathbf{b}_{u},\mathbf{b}_{v}\rangle=\left\\{\begin{aligned}
&\mu\quad&\text{if}\quad u=v,\\\ &-1\quad&\text{if}\quad
u\stackrel{{\scriptstyle+}}{{\sim}}v,\\\ &1\quad&\text{if}\quad
u\stackrel{{\scriptstyle-}}{{\sim}}v,\\\ &0\quad&\text{if}\quad u\nsim
v.\end{aligned}\right.$ (2)

If $\langle\mathbf{b}_{u},\mathbf{b}_{u}\rangle=\mu$, then $u$ is said to be
good for $\mu$. If both $u$, $v$ are good for $\mu$, and
$\langle\mathbf{b}_{u},\mathbf{b}_{v}\rangle\in\\{-1,0,1\\}$, then $u$, $v$
are said to be compatible for $\mu$.

Let $\dot{H}^{\prime}$ be a signed graph with the adjacency matrix $C$, $\mu$
be a real number such that $\mu$ does not appear in the spectrum of
$\dot{H}^{\prime}$. Then $\mu$ does appear in the graph obtained by adding
edges bewtween $\dot{H}^{\prime}$ and a single vertex $u$, where the edges are
allowed to have signatures by Equation (2). It follows that $u$ is good for
$\mu$ if and only if $\langle\mathbf{b}_{u},\mathbf{b}_{u}\rangle=\mu$; if
both $u$ and $v$ are good for $\mu$, then $u,v$ are compatible for $\mu$ if
and only if $\langle\mathbf{b}_{u},\mathbf{b}_{v}\rangle\in\\{-1,0,1\\}$.

Thus, in order to solve the problem $\mathcal{P}$, pairwise compatible
vertices for $\mu$ are required as many as possible.

##  3 The maximum order of $\dot{\mathscr{B}}$

Let $\dot{H}$ be totally disconnected, $V(\dot{H})=\\{1,2\cdots,s\\}$, $u$ be
a single vertex such that $u\notin V(\dot{H})$,
$\mathbf{b}_{u}=(b_{u1},\cdots,b_{us})^{T}$ be a $(0,\pm 1)$-vector such that
$\mathbf{b}_{u}$ determines the neighbors of $u$ in $\dot{H}$ and the
signatures of associate edges $u1,u2,\cdots,us$. By Equation (2), we get

$\sum_{i=1}^{s}b_{ui}b_{vi}=\left\\{\begin{aligned}
&\mu^{2}\quad&\text{if}\quad u=v,\\\ &-\mu\quad&\text{if}\quad
u\stackrel{{\scriptstyle+}}{{\sim}}v,\\\ &\mu\quad&\text{if}\quad
u\stackrel{{\scriptstyle-}}{{\sim}}v,\\\ &0\quad&\text{if}\quad u\nsim
v.\end{aligned}\right.$ (3)

######  Proposition 3.1.

Let $\dot{H}$ be a totally disconnected graph of order $s$, $\mu$ be a non-
zero real number, $\dot{\mathscr{B}}$ denote an arbitrary signed bipartite
graph with $\dot{H}$ as a star complement for $\mu$. Then $\dot{\mathscr{B}}$
exists if and only if $\mu^{2}$ is a positive integer and $s\geq\mu^{2}$.

If $s=\mu^{2}$, then the following theorem is obtained in [11], which shows an
inequality between $\mu^{2}$ and the order of $\dot{\mathscr{B}}$, and the
spectrum of $\dot{\mathscr{B}}$.

######  Theorem 3.2.

[11, Theorem 3.11.] If a signed graph $(G,\Sigma^{-})$ of order $n$ is
decomposed into the star complement $\big{(}\mu^{2}K_{1},\emptyset\big{)}$
$(\text{for $\mu$})$ and $\big{(}(n-\mu^{2})K_{1},\emptyset\big{)}$, then
$n\leq 2\mu^{2}$ and the spectrum of $(G,\Sigma^{-})$ is

$[\mu^{n-\mu^{2}},0^{2\mu^{2}-n},(-\mu)^{n-\mu^{2}}].$

This theorem reveals, if a signed graph $(G,\Sigma^{-})$ of order $n$ is
decomposed into the star complement $\big{(}sK_{1},\emptyset\big{)}$
$(\text{for $\mu$})$ and $\big{(}(n-s)K_{1},\emptyset\big{)}$, then $n\leq 2s$
and the spectrum of $(G,\Sigma^{-})$ is

$[\mu^{n-s},0^{2s-n},(-\mu)^{n-s}].$

It is easy to see the signed graph $(G,\Sigma^{-})$ is bipartite.

Since $\dot{\mathscr{B}}$ is bipartite and $\dot{H}$ is totally disconnected,
then for every two vertices $u,v\notin V(\dot{H})$, $u\nsim v$, otherwise
there is a induced signed graph $\big{(}K_{3},\emptyset\big{)}$ in
$\dot{\mathscr{B}}$. Thus the following theorem is obtained.

######  Theorem 3.3.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$. If the order of
$\dot{\mathscr{B}}$ is $n$, then $n\leq 2s$ and the spectrum of
$\dot{\mathscr{B}}$ is

$[\mu^{n-s},0^{2s-n},(-\mu)^{n-s}].$

Let

$A_{\dot{\mathscr{B}}}=\left(\begin{array}[]{cc}\mathbf{0}&B^{T}\\\
B&\mathbf{0}\end{array}\right).$ (4)

By Equations (3) and (4), we get $B^{T}B=\mu^{2}I$. It is essential for the
problem $\mathcal{P}$ to construct such $B$.

If $\mu^{2}=1$, then $B$ can be an identity matrix. Thus, the maximum order of
$\dot{\mathscr{B}}$ is $2s$, where $\dot{\mathscr{B}}$ is a signed bipartite
graph with $\dot{H}$ as a star complement for $\pm 1$.

######  Theorem 3.4.

Let $\dot{H}$ be a totally disconnected graph of order $s\,(s\geq 2)$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$. If $\mu^{2}=1$, then the maximum
order of $\dot{\mathscr{B}}$ is $2s$.

If $s=\mu^{2}$, then $B$ is a square $(-1,1)$-matrix. An $n\times n$
$(-1,1)$-matrix $\mathcal{H}(n)$ with $\mathcal{H}(n)^{T}\mathcal{H}(n)=nI$ is
called to be a Hadamard matrix.

A Hadamard matrix is defined by Sylvester in [12] and is studied further by
Hadamard in [4]. Hadamard conjectures that a Hadamard matrix of order $4n$
exists for every natural $n$ (Hadamard Conjecture). This condition is
necessary, and the sufficiency part is still an open problem. These Hadamard
matrices are systematically studied by Paley in [7].

It is shown the five following decompositions of a positive integer $n$ such
that $n$ is the order of a Hadamard matrix:

  1. (1)

$n=2^{p}$, $p\geq 1$;

  2. (2)

$n=2^{p}(q^{h}+1)$, $p\geq 2$, $h\geq 1$, $q$ is a prime;

  3. (3)

$n=2^{p}q(q+1)$, $p\geq 2$, $q\equiv 3$ (mod 4), $q$ is a prime;

  4. (4)

$n=q+1$, $q\equiv 3$ (mod 4), $q$ is a prime power;

  5. (5)

$n=2(q+1)$, $q\equiv 1$ (mod 4), $q$ is a prime power.

The cases of the first three decompositions are solved by Paley in [7], and
the rest cases are solved by Ionin and Shrikhande in [5, Corollary 4.3.26].

Let $\mathcal{N}(\mathcal{H})$ be a subset of natural numbers such that every
entry in $\mathcal{N}(\mathcal{H})$ is at least one of the five above
decompositions. Firstly, we consider $\mu^{2}\in\mathcal{N}(\mathcal{H})$ and
$s=\mu^{2}\geq 2$.

######  Lemma 3.5.

Let $\mu^{2}\,(\mu^{2}\geq 2)$ be a positive integer, $\mathbf{b}$ be a
$(-1,1)$-vector of rows $\mu^{2}$, $B$ be a matrix consisted of $\mathbf{b}$’s
such that $B^{T}B=\mu^{2}I$. If $\mu^{2}\in\mathcal{N}(\mathcal{H})$, then the
maximum number of colums of $B$ is $\mu^{2}$.

Secondly, we consider that $s=\mu^{2}$ and $\mu^{2}\in 2\mathbb{Z}^{+}-1$ or
$\mu^{2}\in 2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$. Let $\otimes$ be for
the Kronecker product .

######  Lemma 3.6.

Let $\mu^{2}\,(\mu^{2}\geq 2)$ be a positive integer, $\mathbf{b}$ be a
$(-1,1)$-vector of rows $\mu^{2}$, $B$ be a matrix consisted of $\mathbf{b}$’s
such that $B^{T}B=\mu^{2}I$. If $\mu^{2}\in 2\mathbb{Z}^{+}+1$ or $\mu^{2}\in
2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$, then the maximum number of colums
of $B$ is $1$ or $2$.

###### Proof.

Let $\mu^{2}=2^{p}(2q+1)$, where $p=0,1$ and $q=1,2,3,\cdots$. If $p=0$, then
$B$ is a vector. Otherwise, there is at least one $0$ in the second column of
$B$, which is a contradiction that $B$ is a $(-1,1)$-matrix. Thus the maximum
number of colums of $B$ is $1$.

Let

$\mathcal{H}(2)=\left(\begin{array}[]{cc}1&1\\\ 1&-1\end{array}\right),\quad
B=\mathcal{H}(2)\otimes\mathbf{j}_{2q+1},\quad\mathbf{y}=\mathbf{y}_{1}\otimes\mathbf{y}_{2}$

be a $(-1,1)$-vector such that $B^{T}\mathbf{y}=\mathbf{0}$, where the number
of rows of $\mathbf{y}_{1}$ (or $\mathbf{y}_{2}$) is $2$ (or $2q+1$). Then

$\left(\mathcal{H}(2)^{T}\mathbf{y}_{1}\right)\otimes\left(\mathbf{j}^{T}\mathbf{y}_{2}\right)=\mathbf{0},$

and $\mathcal{H}(2)^{T}\mathbf{y}_{1}=\mathbf{0}$ or
$\mathbf{j}^{T}\mathbf{y}_{2}=0$, which is a contradiction. Thus the maximum
number of colums of $B$ is $2$. ∎

By Lemma 3.5 and 3.6, the following theorem is obtained.

######  Theorem 3.7.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$, $n$ be the maximum order of
$\dot{\mathscr{B}}$. If $s=\mu^{2}\geq 2$, then

$n=\left\\{\begin{aligned} &s+1&\,&\text{$s\in 2\mathbb{Z}^{+}+1$},\\\
&s+2&\,&\text{$s\in 2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$},\\\
&2s&\,&s\in\mathcal{N}(\mathcal{H}).\\\ \end{aligned}\right.$

If $s=\mu^{2}+1$, then we consider whether there is a $(0,\pm 1)$-matrix $B$
such that $B^{T}B=(s-1)I$ or not. An $n\times n$ square matrix
$\mathcal{C}(n)$ with $\mathcal{C}(n)^{T}\mathcal{C}(n)=(n-1)I$, in which all
the diagonal entries are 0 and all off-diagonal entries are $\pm 1$, is said
to be a Conference matrix. In [5, Proposition 4.3.5.], it is shown that there
is a Conference matrix $\mathcal{C}(n)$ in the case that $n-1$ is an odd prime
power (the odd prime power can be 1).

Let $\mathcal{N}(\mathcal{C})$ be a set of odd prime powers. Thirdly, we
consider that $\mu^{2}\in\mathcal{N}(\mathcal{C})$ and $s=\mu^{2}+1$.

######  Lemma 3.8.

Let $\mu^{2}\in\mathcal{N}(\mathcal{C})$ with $\mu^{2}\geq 2$, $\mathbf{b}$ be
a $(0,\pm 1)$-vector of rows $\mu^{2}+1$, in which the number of zero is $1$.
If there is a matrix $B$ consisted of $\mathbf{b}$’s such that
$B^{T}B=\mu^{2}I$, then the maximum number of colums of $B$ is $\mu^{2}+1$.

######  Theorem 3.9.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$, $n$ be the maximum order of
$\dot{\mathscr{B}}$. If $s=\mu^{2}+1\geq 3$, then

$n=\left\\{\begin{aligned} &\mu^{2}+3&\,&\text{$\mu^{2}\in
2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$},\\\
&2\mu^{2}+1&\,&\mu^{2}\in\mathcal{N}(\mathcal{H}),\\\
&2\mu^{2}+2&\,&\text{$\mu^{2}\in\mathcal{N}(\mathcal{C})$}.\\\
\end{aligned}\right.$

###### Proof.

If $\mu^{2}\in 2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$, then
$n\geq\mu^{2}+3$ by Theorem 3.7. We suppose that there are two vertices $u$,
$v$ in $\dot{\mathscr{B}}$ such that the neighbors of $u$ are different from
ones of $v$. Then the number of the common neighbors between $u$ and $v$ is
$\mu^{2}-1$. Let $\mathbf{b}_{u}$ is a $(0,\pm 1)$-vector of order $s$ such
that $\mathbf{b}_{u}$ determines the neighbors of $u$ in $\dot{H}$ and the
signatures of associate edges. Since $\mu^{2}$ is even, then $\mu^{2}-1$ is
odd and $\mathbf{b}_{u}^{T}\mathbf{b}_{v}\neq\mathbf{0}$, which is a
contradiction. Thus $n=\mu^{2}+3$.

If $\mu^{2}\in\mathcal{N}(\mathcal{H})$, then $n=2\mu^{2}+1$ by Theorem 3.7.
If $s\in\mathcal{N}(\mathcal{C})$, then $n=2\mu^{2}+2$ by Lemma 3.8. ∎

Finally, we consider that $\mu^{2}=p\times q$ such that $p$, $q$ are integers
and there exists a $p$-order Hadamard or $(p+1)$-order Conference matrix.

######  Theorem 3.10.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$, $n$ be the maximum order of
$\dot{\mathscr{B}}$, where there are positive integers $p$ and $q$ such that
$\mu^{2}=pq\geq 2$.

  1. (1)

If $p,\,q\in\mathcal{N}(\mathcal{H})$ and $cpq\leq s<(c+1)pq$, then $n=s+cpq$,
where $c=1,2,3,\cdots$.

  2. (2)

If $q\in\mathcal{N}(\mathcal{C})$, then Table 1 holds.

Table 1: The maximum order $n$ of $\dot{\mathscr{B}}$, where $\mu^{2}=pq$,
$q\in\mathcal{N}(\mathcal{C})$ and $c=1,2,3,\cdots$.

cases | $p$ | $s$ | $n-s$
---|---|---|---
(2.1) | $2$ |  $2q$ or $2q+1$ | $2$
(2.2) | $p\in\mathcal{N}(\mathcal{H})$ | $cp(q+1)\leq s<(c+1)p(q+1)$ | $cp(q+1)$
(2.3) | $p\in\mathcal{N}(\mathcal{C})$ | $c(p+1)(q+1)\leq s<(c+1)(p+1)(q+1)$ | $c(p+1)(q+1)$

###### Proof.

Since $p,\,q\in\mathcal{N}(\mathcal{H})$, then there are Hadamard matrices
$\mathcal{H}(p)$ and $\mathcal{H}(q)$. If $s=pq$, then
$B=\mathcal{H}(p)\otimes\mathcal{H}(q)$. Let
$\mathbf{y}=\mathbf{y}_{1}\otimes\mathbf{y}_{2}$ be a $(-1,1)$-vector such
that $B^{T}\mathbf{y}=\mathbf{0}$, where the number of rows of
$\mathbf{y}_{1}$ (or $\mathbf{y}_{2}$) is $p$ (or $q$). Then

$\left(\mathcal{H}(p)^{T}\mathbf{y}_{1}\right)\otimes\left(\mathcal{H}(q)^{T}\mathbf{y}_{2}\right)=\mathbf{0},$

and there is a zero entry in $\mathcal{H}(p)^{T}\mathbf{y}_{1}$ or
$\mathcal{H}(q)^{T}\mathbf{y}_{2}$, which is a contradiction. Thus $n=s+pq$.
If $cpq\leq s<(c+1)pq$, then

$B^{T}=\left(I_{c}\otimes\mathcal{H}(p)^{T}\otimes\mathcal{H}(q)^{T}\quad\mathbf{0}\right),$

and $n=s+cpq$. Thus the result $(1)$ holds.

Since $q\in\mathcal{N}(\mathcal{C})$, then there is a Conference matrix
$\mathcal{C}(q+1)$. If $s=\mu^{2}=2q$, then $n=2q+3=s+2$ by Theorem 3.7. If
$s=\mu^{2}+1=2q+1$, then $n=s+2$ by Theorem 3.9. Thus the result $(2.1)$
holds.

Since $p\in\mathcal{N}(\mathcal{H})$, then there is a Hadamard matrix
$\mathcal{H}(p)$. If $s=p(q+1)$, then
$B=\mathcal{H}(p)\otimes\mathcal{C}(q+1)$. Let $\mathbf{x}_{1}$ be a $(0,\pm
1)$-vector of rows $p$, $\mathbf{x}_{2}$ be a $(0,\pm 1)$-vector of rows
$q+1$, $\mathbf{x}=\mathbf{x}_{1}\otimes\mathbf{x}_{2}$ be a vector such that
$B^{T}\mathbf{x}=\mathbf{0}$ and there is only one $0$ either in
$\mathbf{x}_{1}$ or in $\mathbf{x}_{2}$. Then

$\left(\mathcal{H}(p)^{T}\mathbf{x}_{1}\right)\otimes\left(\mathcal{C}(q+1)^{T}\mathbf{x}_{2}\right)=\mathbf{0}.$

If there is only one $0$ in $\mathbf{x}_{1}$, then there are no zero entries
in $\mathcal{H}(p)^{T}\mathbf{x}_{1}$ or $\mathcal{C}(q+1)^{T}\mathbf{x}_{2}$,
which is a contradiction. If there is only one $0$ in $\mathbf{x}_{2}$, then
there is a zero entry in $\mathcal{H}(p)^{T}\mathbf{x}_{1}$ or
$\mathcal{C}(q+1)^{T}\mathbf{x}_{2}$, which is a contradiction. Thus
$n=s+p(q+1)$. If $cp(q+1)\leq s<(c+1)p(q+1)$, then

$B^{T}=\left(I_{c}\otimes\mathcal{H}(p)^{T}\otimes\mathcal{C}(q+1)^{T}\quad\mathbf{0}\right),$

and $n=s+cp(q+1)$. Thus the result $(2.2)$ holds.

Since $p\in\mathcal{N}(\mathcal{C})$, then there is a Conference matrix
$\mathcal{C}(p+1)$. If $s=(p+1)(q+1)$, then
$B=\mathcal{C}(p+1)\otimes\mathcal{C}(q+1)$. Let $\mathbf{y}_{1}$ be a $(0,\pm
1)$-vector of rows $p+1$, $\mathbf{y}_{2}$ be a $(0,\pm 1)$-vector of rows
$q+1$, $\mathbf{y}=\mathbf{y}_{1}\otimes\mathbf{y}_{2}$ be a vector such that
$B^{T}\mathbf{y}=\mathbf{0}$ and there is either only one $0$ in both
$\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ or two $0$’s in $\mathbf{y}_{1}$. Then

$\left(\mathcal{C}(p+1)^{T}\mathbf{y}_{1}\right)\otimes\left(\mathcal{C}(q+1)^{T}\mathbf{y}_{2}\right)=\mathbf{0}.$

If there is only one $0$ in $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$, then there
is a zero entry in $\mathcal{C}(p+1)^{T}\mathbf{y}_{1}$ or
$\mathcal{C}(q+1)^{T}\mathbf{y}_{2}$, which is a contradiction. If there are
only two $0$’s in $\mathbf{y}_{1}$, then not all entries in
$\mathcal{C}(p+1)^{T}\mathbf{y}_{1}$ are $0$’s and there are no zero entries
in $\mathcal{C}(q+1)^{T}\mathbf{y}_{2}$, which is a contradiction. Thus
$n=s+(p+1)(q+1)$. If $c(p+1)(q+1)\leq s<(c+1)(p+1)(q+1)$, then

$B^{T}=(I_{c}\otimes\mathcal{C}(p+1)^{T}\otimes\mathcal{C}(q+1)^{T}\quad\mathbf{0}),$

and $n=s+c(p+1)(q+1)$. Thus the result $(2.3)$ holds. ∎

######  Corollary 3.11.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$ $(\mu^{2}\geq 2)$, $n$ be the
maximum order of $\dot{\mathscr{B}}$.

  1. (1)

If $\mu^{2}\in\mathcal{N}(\mathcal{H})$ and $c\mu^{2}\leq s<(c+1)\mu^{2}$,
then $n=s+c\mu^{2}$.

  2. (2)

If $\mu^{2}\in\mathcal{N}(\mathcal{C})$ and $c(\mu^{2}+1)\leq
s<(c+1)(\mu^{2}+1)$, then $n=s+c(\mu^{2}+1)$.

######  Theorem 3.12.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}$ denote an arbitrary signed bipartite graph with $\dot{H}$
as a star complement for an eigenvalue $\mu$, $n$ be the maximum order of
$\dot{\mathscr{B}}$, where there are positive integers $p$ and $q$ ($p>q$)
such that $\mu^{2}=pq\geq 2$.

  1. (1)

If $p\in\mathcal{N}(\mathcal{H})$, $q\in\mathcal{N}(\mathcal{C})$ and $pq\leq
s<p(q+1)$, then $s+p\leq n\leq 2s$.

  2. (2)

If $p,\,q\in\mathcal{N}(\mathcal{C})$ and $pq\leq s<(p+1)q$, then $s+1\leq
n\leq 2s$.

  3. (3)

If $p,\,q\in\mathcal{N}(\mathcal{C})$ and $(p+1)q\leq s<(p+1)(q+1)$, then
$s+p+1\leq n\leq 2s$.

###### Proof.

Since $p\in\mathcal{N}(\mathcal{H})$, $q\in\mathcal{N}(\mathcal{C})$, then
there is a Hadamard matrix $\mathcal{H}(p)$ and a Conference matrix
$\mathcal{C}(q+1)$. If $s=pq$, then $B=\mathcal{H}(p)\otimes\mathbf{j}_{q}$.
Let $\mathbf{x}=\mathbf{x}_{1}\otimes\mathbf{x}_{2}$ be a $(-1,1)$-vector such
that $B^{T}\mathbf{x}=\mathbf{0}$, where the number of rows of
$\mathbf{x}_{1}$ (or $\mathbf{x}_{2}$) is $p$ (or $q$). Then

$\left(\mathcal{H}(p)^{T}\mathbf{x}_{1}\right)\otimes\left(\mathbf{j}^{T}\mathbf{x}_{2}\right)=\mathbf{0},$

and there is a zero entry in $\mathcal{H}(p)^{T}\mathbf{x}_{1}$ or
$\mathbf{j}^{T}\mathbf{x}_{2}=0$, which is a contradiction. Thus $s+p\leq
n\leq 2s$.

If $s=\mu^{2}=pq$ and $p,\,q\in\mathcal{H}(\mathcal{C})$, then $n=s+1$ by
Lemma 3.7. If $pq\leq s<(p+1)q$, then $s+1\leq n\leq 2s$.

Since $p\in\mathcal{N}(\mathcal{C})$, then there is a Conference matrix
$\mathcal{C}(p+1)$. If $s=(p+1)q$, then
$B=\mathcal{C}(p+1)\otimes\mathbf{j}_{q}$. Let $\mathbf{y}_{1}$ be a $(0,\pm
1)$-vector of rows $p+1$, $\mathbf{y}_{1}$ be a $(0,\pm 1)$-vector of rows
$q$, $\mathbf{y}=\mathbf{y}_{1}\otimes\mathbf{y}_{2}$ be a vector such that
$B^{T}\mathbf{y}=\mathbf{0}$ and there is only one $0$ either in
$\mathbf{y}_{1}$ or in $\mathbf{y}_{2}$. Then

$\left(\mathcal{C}(p+1)^{T}\mathbf{y}_{1}\right)\otimes\left(\mathbf{j}^{T}\mathbf{y}_{2}\right)=\mathbf{0}.$

If there is only one $0$ in $\mathbf{y}_{1}$, then there is a zero entry in
$\mathcal{C}(p+1)^{T}\mathbf{y}_{1}$ and $\mathbf{j}^{T}\mathbf{y}_{2}\neq 0$,
which is a contradiction. If there is only one $0$ in $\mathbf{y}_{2}$, then
there are no zero entries in $\mathcal{C}(p+1)^{T}\mathbf{y}_{1}$ and
$\mathbf{j}^{T}\mathbf{y}_{2}\neq 0$, which is a contradiction. Thus
$s+p+1\leq n\leq 2s$. ∎

##  4 The maximal signed bipartite graph $\dot{\mathscr{B}}_{m}$

Let $(G_{1},\Sigma_{1}^{-})$ and $(G_{2},\Sigma^{-}_{2})$ be two signed
graphs. If there exists a permutation $(0,\,1)$-matrix $P$ such that
$A_{(G_{2},\Sigma^{-}_{2})}=P^{-1}A_{(G_{1},\Sigma^{-}_{1})}P$, then
$(G_{1},\Sigma^{-}_{1})$ and $(G_{2},\Sigma^{-}_{2})$ are said to be
isomorphic. Similarly, if there is a diagonal $(-1,1)$-matrix $D$ such that
$A_{(G_{2},\Sigma^{-}_{2})}=D^{-1}A_{(G_{1},\Sigma^{-}_{1})}D$, then
$(G_{1},\Sigma^{-}_{1})$ and $(G_{2},\Sigma^{-}_{2})$ are said to be switching
equivalent. Isomorphism and switching equivalence are equivalence relations
preserving the eigenvalues.

If $(G_{1},\Sigma^{-}_{1})$ is isomorphic to a switching equivalence of
$(G_{2},\Sigma^{-}_{2})$, then $(G_{1},\Sigma^{-}_{1})$ and
$(G_{2},\Sigma^{-}_{2})$ are said to be switching isomorphic, denoted by
$(G_{1},\Sigma^{-}_{1})\cong^{s}(G_{2},\Sigma^{-}_{2})$. Switching isomorphism
is also an equivalence relation preserving the eigenvalues.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ is a maximal signed bipartite graph with $\dot{H}$ as
a star complement for an eigenvalue $\mu$.

######  Theorem 4.1.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ denote the maximal signed bipartite graph with
$\dot{H}$ as a star complement for an eigenvalue $\mu$. If $\mu^{2}=1$, then
$\dot{\mathscr{B}}_{m}\cong^{s}(sK_{2},\emptyset)$.

###### Proof.

Let $S$ be a vertex subset of $\dot{\mathscr{B}}_{m}$ such that
$\dot{\mathscr{B}}_{m}-S=\dot{H}$. Since $\mu=\pm 1$, then by Equation (3), we
obtain that each vertex in $S$ is adjacent with only one vertex in $\dot{H}$,
and each vertex in $\dot{H}$ does not have common neighbors in $S$. Thus
$\dot{\mathscr{B}}_{m}\cong^{s}(sK_{2},\emptyset)$. ∎

Now we consider $s=\mu^{2}\geq 2$ or $s=\mu^{2}+1$.

######  Example 4.2.

Let $\dot{H}$ be a totally disconnected graph of order $\mu^{2}$. If
$\mu^{2}=2$, then $(K_{2,2},E(K_{2}))$ is the maximal signed bipartite graph
with $\dot{H}$ as a star complement for $\pm\sqrt{2}$. If $\mu^{2}=3$, then
$\big{(}K_{1,3},\emptyset\big{)}$ is the maximal signed bipartite graph with
$\dot{H}$ as a star complement for $\pm\sqrt{3}$. If $\mu^{2}=4$, then
$\big{(}K_{4,4},E(C_{6})\big{)}$ is the maximal signed bipartite graph with
$\dot{H}$ as a star complement for $\pm 2$.

A simple graph is said to be biregular if its vertex degrees assume exactly
two different values. Let $K_{n,n}\backslash nK_{2}$ be a simple graph
obtained by deleting $n$ edges without common vertices in $K_{n,n}$.

######  Example 4.3.

Let $\dot{H}$ be a totally disconnected graph of order $\mu^{2}+1$. If
$\mu^{2}=2$, then $(K_{1,3}\cup K_{1},\emptyset)$ is the maximal signed
bipartite graph with $\dot{H}$ as a star complement for $\pm\sqrt{2}$. If
$\mu^{2}=3$, then $\big{(}K_{4,4}\backslash{4K_{2}},E(P_{4}\cup K_{2})\big{)}$
is the maximal graph with $\dot{H}$ as a star complement for $\pm\sqrt{3}$,
where $P_{4}$ is a path of length $4$. If $\mu^{2}=5$, then
$\big{(}K_{6,6}\backslash{6K_{2}},E(BR)\big{)}$ is the maximal graph with
$\dot{H}$ as a star complement for $\pm\sqrt{5}$, where the simple graph $BR$
(see Figure 1) is biregular.

Figure 1: The biregular graph $BR$ is a induced subgraph in
$K_{6,6}\backslash{6K_{2}}$.

If $s=\mu^{2}\in\mathcal{N}(\mathcal{H})$, then the order of
$\dot{\mathscr{B}}_{m}$ is $2s$ by Theorem 3.7, and $\dot{\mathscr{B}}_{m}$
has only two opposite eigenvalue. If $s=\mu^{2}+1$, then the maximum order of
$\dot{\mathscr{B}}_{m}$ is $2s+2$ by Theorem 3.9, and $\dot{\mathscr{B}}_{m}$
also has only two opposite eigenvalue.

In [8], Ramezani proves that the signed graphs with just two distinct
eigenvalues are signed strongly regular graphs. In [10],
Stani$\acute{\text{c}}$ shows certain structural and spectral properties of
signed strongly regular graphs, which is also bipartite.

Let the signature of a walk be determined by the product of signatures of
edges, $u$ and $v$ be two vertices in a signed graph, $w_{2}(u,v)$ be the
difference between the numbers of positive and negative walks traversing along
$2$ edges between $u$ and $v$. A signed graph $(G,\Sigma^{-})$ is said to be
strongly regular (for short, $SRG^{s}(n,r,a,b,c)$) whenever it is regular and
satisfies the following four conditions:

  1. (1)

$(G,\Sigma^{-})$ is neither homogeneous complete nor totally disconnected;

  2. (2)

there exists $a\in\mathbb{Z}$ such that $w_{2}(u,v)=a$, for all
$u\stackrel{{\scriptstyle+}}{{\sim}}v$;

  3. (3)

there exists $b\in\mathbb{Z}$ such that $w_{2}(u,v)=b$, for all
$u\stackrel{{\scriptstyle-}}{{\sim}}v$;

  4. (4)

there exists $c\in\mathbb{Z}$ such that $w_{2}(u,v)=c$, for all $u\nsim v$.

Thus

$A_{(G,\Sigma^{-})}^{2}=\frac{a}{2}(A_{(G,\Sigma^{-})}+A_{G})-\frac{b}{2}(A_{(G,\Sigma^{-})}-A_{G})+cA_{\overline{G}}+rI,$
(5)

where $\overline{G}$ is for the complement of a simple graph $G$. We use the
notation $SRG^{s}(2n)$ to denote as $SRG^{s}(2n,n,0,0,0)$.

######  Theorem 4.4.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ denote the maximal signed bipartite graph with
$\dot{H}$ as a star complement for an eigenvalue $\mu$, where $s=\mu^{2}\geq
2$.

  1. (1)

If $s\in 2\mathbb{Z}^{+}+1$, then
$\dot{\mathscr{B}}_{m}\cong^{s}(K_{1,s},\,\emptyset)$.

  2. (2)

If $s\in 2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$, then
$\dot{\mathscr{B}}_{m}\cong^{s}\big{(}K_{2,s},\,E(K_{1,\frac{s}{2}})\big{)}$.

  3. (3)

If $s\in\mathcal{N}(\mathcal{H})$, then
$\dot{\mathscr{B}}_{m}\cong^{s}SRG^{s}(2s)$.

###### Proof.

Since $\dot{\mathscr{B}}_{m}$ is bipartite and $\dot{H}$ is totally
disconnected, then for every two vertices $u,v\notin V(\dot{H})$, $u\nsim v$,
otherwise there is a induced signed graph $(K_{3},\emptyset)$ in
$\dot{\mathscr{B}}_{m}$. By Equations (3) and (4), we get $B^{T}B=sI$.

If $s\in 2\mathbb{Z}^{+}-1$ or $s\in 2\mathbb{Z}^{+}\backslash
4\mathbb{Z}^{+}$, then the results (1) and (2) hold by Lemma 3.5. If
$s\in\mathcal{N}(\mathcal{H})$, then $A_{\dot{\mathscr{B}}_{m}}^{2}=sI$ and
$\dot{\mathscr{B}}_{m}$ is a signed strongly regular graph. Let $n$ be the
order of $\dot{\mathscr{B}}_{m}$, $r,\,a,\,b,\,c$ be integers satisfying
Equation (5). Then $n=2s$, $r=s$ and $a=b=c=0$. Thus the result $(3)$ holds. ∎

######  Theorem 4.5.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ denote the maximal signed bipartite graph with
$\dot{H}$ as a star complement for an eigenvaule $\mu$, where $s=\mu^{2}+1\geq
3$.

  1. (1)

If $\mu^{2}\in 2\mathbb{Z}^{+}\backslash 4\mathbb{Z}^{+}$, then
$\dot{\mathscr{B}}_{m}\cong^{s}\big{(}K_{2,\mu^{2}}\cup
K_{1},\,E(K_{1,\frac{\mu^{2}}{2}})\big{)}$.

  2. (2)

If $\mu^{2}\in\mathcal{N}(\mathcal{H})$, then
$\dot{\mathscr{B}}_{m}\cong^{s}SRG^{s}(2\mu^{2})\cup(K_{1},\,\emptyset)$.

  3. (3)

If $\mu^{2}\in\mathcal{N}(\mathcal{C})$, then
$\dot{\mathscr{B}}_{m}\cong^{s}SRG^{s}(2\mu^{2}+2)$.

###### Proof.

By Equation (4), we get $B^{T}B=\mu^{2}I$. If
$\mu^{2}\in(2\mathbb{Z}^{+}\backslash
4\mathbb{Z}^{+})\cup\mathcal{N}(\mathcal{H})$, then every two vertices in
$\dot{\mathscr{B}}_{m}$ have the same neighbors. Otherwise the inner product
between a $(-1,1)$-vector with odd rows and an all-one vector is zero, which
is a contradiction. The results $(1)$ and $(2)$ hold by Theorem 4.4. If
$\mu^{2}\in\mathcal{N}(\mathcal{C})$, then
$A_{\dot{\mathscr{B}}_{m}}^{2}=\mu^{2}I$, and $\dot{\mathscr{B}}_{m}$ is a
signed strongly regular graph. Let $n$ be the order of
$\dot{\mathscr{B}}_{m}$, $r,\,a,\,b,\,c$ be integers satisfying Equation (5),
then $n=2\mu^{2}+2$, $r=s+1$ and $a=b=c=0$ by Lemma 3.8. Thus the result $(3)$
holds. ∎

######  Remark 4.6.

Let $SRG^{s}(2s)$ is bipartite. If $s\in\mathcal{N}(\mathcal{H})$, then the
underlying graph of $SRG^{s}(2s)$ is $K_{s,s}$. If
$s\in\mathcal{N}(\mathcal{C})$, then the underlying graph of $SRG^{s}(2s)$ is
$K_{s,s}\backslash sK_{2}$.

Let $(G_{1},\Sigma^{-}_{1})$ and $(G_{2},\Sigma^{-}_{2})$ be two signed
bipartite graphs with the adjacency matrices

$\left(\begin{array}[]{cc}\mathbf{0}&B_{1}^{T}\\\
B_{1}&\mathbf{0}\end{array}\right)\quad\text{and}\quad\left(\begin{array}[]{cc}\mathbf{0}&B_{2}^{T}\\\
B_{2}&\mathbf{0}\end{array}\right),$

respectively. The signed graph
$(G_{1},\Sigma^{-}_{1})\dot{\otimes}(G_{2},\Sigma^{-}_{2})$ is defined as the
signed bipartite graph with the adjacency matrix

$A_{(G_{1},\Sigma^{-}_{1})}\dot{\otimes}A_{(G_{2},\Sigma^{-}_{2})}=\left(\begin{array}[]{cc}\mathbf{0}&B_{1}^{T}\otimes
B_{2}^{T}\\\ B_{1}\otimes B_{2}&\mathbf{0}\end{array}\right).$

Let $c(G_{1},\Sigma^{-}_{1})$ be for the disjoint union of $c$ copies of
$(G_{1},\Sigma^{-}_{1})$.

By Theorem 3.10, 4.4 and 4.5, the following result is obtained.

######  Theorem 4.7.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ denote the maximal signed bipartite graph with
$\dot{H}$ as a star complement for an eigenvalue $\mu$, where there are
positive integers $p$ and $q$ such that $\mu^{2}=pq\geq 2$.

  1. (1)

If $p,q\in\mathcal{N}(\mathcal{H})$ and $cpq\leq s<(c+1)pq\,(c=1,2,3,\cdots)$,
then

$\dot{\mathscr{B}}_{m}\cong^{s}\big{(}c\,SRG^{s}(2p)\dot{\otimes}SRG^{s}(2q)\big{)}\cup\big{(}(s-cpq)K_{1},\emptyset\big{)}.$

  2. (2)

If $q\in\mathcal{N}(\mathcal{C})$, then Table 2 holds.

Table 2: The maximal signed bipartite graph $\dot{\mathscr{B}}_{m}$, where
$\mu^{2}=pq$, $q\in\mathcal{N}(\mathcal{C})$ and $c=1,2,3,\cdots$.

$p$ | $s$ |  $\dot{\mathscr{B}}_{m}$ is switching isomorphic to
---|---|---
2 |  $2q$ or $2q+1$ | $\left(K_{2,2q}\cup(s-2q)K_{1},E(K_{1,q})\right)$
$p\in\mathcal{N}(\mathcal{H})$ | $cp(q+1)\leq s<(c+1)p(q+1)$ | $\big{(}c\,SRG^{s}(2p)\dot{\otimes}SRG^{s}(2q+2)\big{)}$
|  | $\cup\big{(}(s-cp(q+1))K_{1},\emptyset\big{)}$
$p\in\mathcal{N}(\mathcal{C})$ | $c(p+1)(q+1)\leq s<(c+1)(p+1)(q+1)$ | $\big{(}c\,SRG^{s}(2p+2)\dot{\otimes}SRG^{s}(2q+2)\big{)}$
|  | $\cup\big{(}(s-c(p+1)(q+1))K_{1},\emptyset\big{)}$

######  Remark 4.8.

Let $\dot{H}$ be a totally disconnected graph of order $s$,
$\dot{\mathscr{B}}_{m}$ denote the maximal signed bipartite graph with
$\dot{H}$ as a star complement for an eigenvalue $\mu$, where there are
positive integers $p$ and $q$ ($p>q$) such that $\mu^{2}=pq\geq 2$. Then by
Theorem 3.12, the three following results are obtained.

  1. (1)

If $p\in\mathcal{N}(\mathcal{H})$, $q\in\mathcal{N}(\mathcal{C})$ and $s=pq$,
then
$\dot{\mathscr{B}}_{m}\cong^{s}SRG^{s}(2p)\dot{\otimes}(K_{1,q},\emptyset)$.

  2. (2)

If $p,\,q\in\mathcal{N}(\mathcal{C})$ and $s=pq$, then
$\dot{\mathscr{B}}_{m}\cong^{s}\left(K_{1,pq},\emptyset\right)$.

  3. (3)

If $p,\,q\in\mathcal{N}(\mathcal{C})$ and $s=(p+1)q$, then
$\dot{\mathscr{B}}_{m}\cong^{s}SRG^{s}(2p+2)\dot{\otimes}(K_{1,q},\emptyset)$.

$\mathbf{References}$

## References

  * [1] D. Cvetkovi$\acute{\text{c}}$, P. Rowlinson, S. K. Simi$\acute{\text{c}}$, A study of eigenspaces of graphs, Linear Algebra and its Applications. 182 (1993) 45-66.
  * [2] D. Cvetkovi$\acute{\text{c}}$, P. Rowlinson, S. K. Simi$\acute{\text{c}}$, Eigenspaces of Graphs, Cambridge University Press, New York, 1997.
  * [3] D. Cvetkovi$\acute{\text{c}}$, P. Rowlinson, S. K. Simi$\acute{\text{c}}$, An Introduction to the Theory of Graph Spectra, Cambridge University Press, New York, 2010.
  * [4] J. Hadamard, Resolution d’une question relative aux determinants, Bulletin des Sciences Mathematiques. 17 (1893) 240-246.
  * [5] Y.J. Ionin, M.S. Shrikhande, Combinatorics of Symmetric Designs, Cambridge University Press, New York, 2006.
  * [6] R. Mulas, Z. Stani$\acute{\text{c}}$, Star complements for $\pm 2$ in signed graphs, Special Matrices. 10 (2022) 258-266.
  * [7] R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics. 12 (1933) 311-320.
  * [8] F. Ramezani, Constructing signed strongly regular graphs via star complement technique, Mathematical Sciences. 12 (2018) 157-161.
  * [9] F. Ramezani, P. Rowlinson, Z. Stani$\acute{\text{c}}$, On eigenvalue multiplicity in signed graphs, Discrete Mathematics. 343 (2020) 111982.
  * [10] Z. Stani$\acute{\text{c}}$, On strongly regular signed graphs, Discrete Applied Mathematics. 271 (2019) 184-190.
  * [11] Z. Stani$\acute{\text{c}}$, Signed graphs with totally disconnected star complements, Revista de la Uni$\acute{\text{o}}$n Matem$\acute{\text{a}}$tica Argentina. 62 (2021) 95-104.
  * [12] J. J. Sylvester, Thoughts on Orthogonal Matrices, Simultaneous Sign Successions, and Tessellated Pavements in Two or More Colors, with Applications to Newton’s Rule, Ornamental TileWork, and the Theory of Numbers, Philosophical Magazine. 34 (1867) 461-475.
  * [13] X. Yuan, Y. Mao, L. Liu, Maximal signed graphs with odd signed cycles as star complements, Applied Mathematics and Computation. 408 (2021) 126367.


# Relative Gromov–Witten and maximal contact conics

Giosuè Muratore  CMAFcIO, Faculdade de Ciências da ULisboa, Campo Grande
1749-016 Lisboa, Portugal<EMAIL_ADDRESS>https://sites.google.com/view/giosue-muratore

###### Abstract.

We discuss some properties of the relative Gromov–Witten invariants counting
rational curves with maximal contact order at one point. We compute the number
of Cayley’s sextactic conics to any smooth plane curve $Y$. In particular, we
compute the contribution, from double covers of inflectional lines, to a
certain degree $2$ relative Gromov–Witten invariant relative to $Y$.

###### Key words and phrases:

relative, Gromov–Witten, sextactic, osculating, tangent, rational

###### 2020 Mathematics Subject Classification:

Primary 14N35, 14N15, 14N10; Secondary 14H50

##  1\. Introduction

Let $Y$ be a complex general smooth plane curve of degree $d\geq 3$. By the
classical Bézout’s Theorem, a rational curve of degree $n$ meets $Y$ at $dn$
points. If we require that the contact order at some point is $3n$ (the
maximal possible), we expect that the number of such rational curves is
finite. For example, if $n=1$ these curves are the inflectional lines.

When $n=2$, they are called sextactic conics, and the relevant intersection
point is called sextactic point. The main result of this paper is the
following.

######  Theorem 1.1.

Let $Y$ be a general smooth plane curve of degree $d\geq 3$. The number of
conics of contact order $6$ with $Y$ is

$n_{d}=3d(4d-9).$

This result was first found by [Cay63], see also [TU02] for another proof and
historical background.

Our proof uses relative Gromov–Witten invariants, and closely follows the
approach of [Gat05] (where the number of conics five-fold tangent to $Y$ is
computed). We proceed as follow: In Section 3, we compute explicitly some
relative Gromov–Witten invariants relative to a smooth hypersurface of
$\mathbb{P}^{s}$. In particular, in Equation (3.4), we give a closed formula
for the number of lines with maximal contact with a degree $d$
hypersurface111The author could not find this formula in the literature..
Finally, in Section 4, we prove the theorem as a difference between virtual
numbers of stable maps tangent to the curve $Y$. The central point of the
proof is the computation of the contribution from double covers of lines to a
relative Gromov–Witten invariant. In the last subsection we conjecture an
analogous polynomial counting curves of degree $n=3$, using the multiple cover
contribution formula of Gross, Pandharipande, and Siebert.

When $Y$ is cubic, rational curves with high contact are well understood
[CC08]. Moreover, $Y$ meets a maximal contact curve at just one point. This
point corresponds to $3n$-torsion points of the elliptic curve $(Y,p)$, where
$p$ is inflectional [Tak96, Lemma 1.2]. Thus, sextactic points correspond to
$6$-torsion points that are not $3$-torsion. Moreover, the fact that the pair
$(\mathbb{P}^{2},Y)$ is log Calabi–Yau is used in [Tak01, BN22]. See [NR22,
Bou23, SS24] for related recent results. One of the purposes of this project
is to have a better comprehension of curves of maximal contact with $Y$ when
$d>3$.

In the future, we plan to further expand our result either by increasing the
value of $n$ (as in Conjecture 4.9), or by considering curves of maximal
contact to a surface $Y\subset\mathbb{P}^{3}$.

######  Acknowledgements.

I thank Ethan Cotterill for introducing me to the problem. I also thank Miguel
Moreira, Georg Oberdieck and Israel Vainsencher for useful discussions. The
author is supported by FCT - Fundação para a Ciência e a Tecnologia, under the
project: UIDP/04561/2020 (https://doi.org/10.54499/UIDP/04561/2020).

##  2\. Notation and background

Let $\overline{M}_{0,k}(\mathbb{P}^{s},n)$ be the moduli space of degree $n$
rational stable maps with $k$ marked point, see [FP97, 0.4]. We denote by
$\mathrm{ev}_{j}\colon\overline{M}_{0,k}(\mathbb{P}^{s},n)\rightarrow\mathbb{P}^{s}$
the $j^{\mathrm{th}}$ evaluation map, or simply by $\mathrm{ev}$ the unique
evaluation map when $k=1$. Let $Y\subset\mathbb{P}^{s}$ be a smooth
hypersurface of degree $d$, and $H\subset\mathbb{P}^{s}$ be a hyperplane. We
denote by $\overline{M}_{(m)}^{Y}(\mathbb{P}^{s},n)$ the moduli space of
$1$-pointed relative stable maps of degree $n$ to $\mathbb{P}^{s}$ relative to
$Y$ with multiplicity $m$ at the marked point, as in Definition 1.1 and 1.18
of [Gat02]. This space can be thought as the compactification of the moduli
space of maps whose contact order at the marked point is at least equal to
$m$. It has expected dimension

$\dim(\overline{M}_{0,1}(\mathbb{P}^{s},n))-m=s+n(s+1)-2-m.$

The virtual fundamental class, denoted by
$[\overline{M}_{(m)}^{Y}(\mathbb{P}^{s},n)]$, satisfies the following
recursive relation for every $m\geq 0$,

(2.1)
$(\mathrm{ev}^{*}(Y)+m\psi)\cdot[\overline{M}^{Y}_{(m)}(\mathbb{P}^{s},n)]=[\overline{M}^{Y}_{(m+1)}(\mathbb{P}^{s},n)]+[D_{(m)}(\mathbb{P}^{s},n)],$

where $D_{(m)}(\mathbb{P}^{s},n)$ is a space that parameterizes reducible
curves. We refer to [Gat03, Theorem 0.1] for all details of Equation (2.1).
When $n=1$ and $Y$ has no rational curves, there is no excess locus
$D_{(m)}(\mathbb{P}^{s},1)$. But when $n>1$, the situation is more
complicated.

######  Example 2.1.

Let $s=n=2$. If $\deg(Y)\geq 3$, then $Y$ has no rational curves. It follows
that

$(\mathrm{ev}^{*}(Y)+5\psi)\cdot[\overline{M}^{Y}_{(5)}(\mathbb{P}^{2},2)]=[\overline{M}^{Y}_{(6)}(\mathbb{P}^{2},2)]+[D_{(5)}(\mathbb{P}^{2},2)],$

where $[D_{(5)}(\mathbb{P}^{2},2)]=3[D(\mathbb{P}^{2},(1,1),(2,3))]$ and

$D(\mathbb{P}^{2},(1,1),(2,3))=\overline{M}_{0,3}(Y,0)\times_{Y}\overline{M}_{(2)}(\mathbb{P}^{2},1)\times_{Y}\overline{M}_{(3)}(\mathbb{P}^{2},1).$

Now, we define the virtual number of maximal contact curves. In the next
section we compute such a degree in some particular cases.

######  Definition 2.2.

Let $s,n$ be positive integers. We denote by
$T_{s,n}\colon\mathbb{N}\rightarrow\mathbb{Q}$ the virtual number of maximal
contact curves of degree $n$, that is the function

(2.2) $d\mapsto\deg([\overline{M}_{(s-2+n(s+1))}^{Y}(\mathbb{P}^{s},n)]),$

where $Y$ denotes a general hypersurface of degree $d$.

##  3\. Explicit computation of some relative GW invariants

###  3.1. The case of lines

For completeness, in this section we deduce a closed formula for the number of
lines of maximal contact with a hypersurface $Y$. We adopt the following
convention of the binomial coefficients:

$\binom{a}{i}=0\,\,\mathrm{if}\,\,a<i.$

Moreover, $\psi$ will always be the $\psi$-class with respect to the first
mark.

######  Lemma 3.1.

Let $a,i$ be two non negative integers. We have the following,

(3.1)
$\displaystyle\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}$
$\displaystyle=(-1)^{a-i}\binom{a}{i},$ (3.2)
$\displaystyle\int_{\overline{M}_{0,1}(\mathbb{P}^{s},1)}\psi^{a}\mathrm{ev}^{*}(H)^{2s-1-a}$
$\displaystyle=(-1)^{a-s-1}\binom{a+1}{s}.$

###### Proof.

We prove the first equation by induction on the sum $a+i=t$. If $t=0$, then
the only case we need to prove is $a=i=0$. That is, we need to prove that

$\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}\psi^{0}\mathrm{ev}_{1}^{*}(H)^{s}\mathrm{ev}_{2}^{*}(H)^{s}=1.$

But that is of course true since it is the number of lines passing through two
general points [FP97, Lemma 14]. Let us suppose that the equation holds true
whenever $a+i\leq t-1$. Let $a,i$ be such that $a+i=t$. Consider the invariant

(3.3)
$\int_{\overline{M}_{0,3}(\mathbb{P}^{s},1)}\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}\mathrm{ev}_{3}^{*}(H).$

Using the divisor equation [Pan98, 1.2.III], we see that

$\displaystyle\int_{\overline{M}_{0,3}(\mathbb{P}^{s},1)}$
$\displaystyle\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}\mathrm{ev}_{3}^{*}(H)$
$\displaystyle=\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}$
$\displaystyle\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}+\psi^{a-1}\mathrm{ev}_{1}^{*}(H)^{s-(a-1)+i}\mathrm{ev}_{2}^{*}(H)^{s-i}$
$\displaystyle=\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}$
$\displaystyle\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}+(-1)^{a-1-i}\binom{a-1}{i}.$

Note that we used the inductive hypothesis. On the other hand, using the
topological recursion relation [Pan98, Equation (6)], we see that (3.3) is
equal to

$\displaystyle\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}$
$\displaystyle\psi^{a-1}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-(i-1)}=(-1)^{a-i}\binom{a-1}{i-1}.$

We deduce immediately

$\displaystyle\int_{\overline{M}_{0,2}(\mathbb{P}^{s},1)}\psi^{a}\mathrm{ev}_{1}^{*}(H)^{s-a+i}\mathrm{ev}_{2}^{*}(H)^{s-i}$
$\displaystyle=(-1)^{a-i}\binom{a-1}{i}+(-1)^{a-i}\binom{a-1}{i-1}$
$\displaystyle=(-1)^{a-i}\binom{a}{i}.$

So, (3.1) is proved. In order to prove (3.2), it is enough to take $i=s$ in
(3.1) and apply the string equation [Pan98, 1.2.I]. ∎

Let $\mathcal{S}(n,k)$ denote the signed Stirling numbers of the first kind.
More precisely, $\mathcal{S}(n,k)$ are the integers numbers such that

$x(x+1)(x+2)\cdots(x+n-1)=\sum_{k=0}^{n}(-1)^{n-k}\mathcal{S}(n,k)x^{k}.$

Using Equations (2.1) and (3.2), we have

$\displaystyle\deg([\overline{M}^{Y}_{(2s-1)}(\mathbb{P}^{s},1)])$
$\displaystyle=\sum_{k=0}^{2s-1}(-1)^{2s-1-k}\mathcal{S}(2s-1,k)\int_{\overline{M}_{0,1}(\mathbb{P}^{s},1)}\psi^{2s-1-k}\mathrm{ev}^{*}(H)^{k}d^{k}$
$\displaystyle=\sum_{k=1}^{s}(-1)^{k+1}\mathcal{S}(2s-1,k)\int_{\overline{M}_{0,1}(\mathbb{P}^{s},1)}\psi^{2s-1-k}\mathrm{ev}^{*}(H)^{k}d^{k}$
$\displaystyle=\sum_{k=1}^{s}(-1)^{k+1+2s-1-k-s-1}\mathcal{S}(2s-1,k)\binom{2s-k}{s}d^{k}.$

Finally,

(3.4)
$\deg([\overline{M}^{Y}_{(2s-1)}(\mathbb{P}^{s},1)])=(-1)^{s+1}\sum_{k=1}^{s}\mathcal{S}(2s-1,k)\binom{2s-k}{s}d^{k}.$

######  Example 3.2.

Take $s=2$ and $s=3$. We easily get

$\displaystyle\mathcal{S}(3,1)$ $\displaystyle=2,$
$\displaystyle\mathcal{S}(3,2)$ $\displaystyle=-3,$
$\displaystyle\mathcal{S}(5,1)$ $\displaystyle=24,$
$\displaystyle\mathcal{S}(5,2)$ $\displaystyle=-50,$
$\displaystyle\mathcal{S}(5,3)$ $\displaystyle=35.$

So we have

$\displaystyle\deg([\overline{M}^{Y}_{(3)}(\mathbb{P}^{2},1)])$
$\displaystyle=3d(d-2),$
$\displaystyle\deg([\overline{M}^{Y}_{(5)}(\mathbb{P}^{3},1)])$
$\displaystyle=35d^{3}-200d^{2}+240d.$

Both cases are classically known, see [Har77, Exercise IV.2.3(e)] and [EH16,
11.1.3].

###  3.2. The case of any degree

When the degree of the curve is greater than $1$, a closed formula like
Equation (3.4) is not known. But the following proposition is very useful,
because it allows to completely determine relative invariants after knowing a
finite number of them. We denote by $p_{t}(d)\in\mathbb{Q}[d]$ a polynomial of
degree at most $t$.

######  Proposition 3.3.

Let $Y\subset\mathbb{P}^{s}$ be a smooth hypersurface of degree $d$, which
does not contain rational curves. For any $m\geq 0$ and $n\geq 1$,

(3.5)
$\int_{\overline{M}_{(m+1)}^{Y}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k}\psi^{j}=\begin{cases}0,&\text{if
}j\neq s+n(s+1)-m-k-3\\\ 0,&\text{if }k\geq s\\\ d^{k+1}p_{s-1-k}(d),&\text{if
}0\leq k\leq s-1.\end{cases}$

In particular, the integral in the equation is either zero or a polynomial in
$d$ of degree at most $s$ where $0$ is a root of multiplicity $k+1$.

###### Proof.

We prove the proposition by induction on $m$. By Equation (2.1),

$\int_{\overline{M}_{(1)}^{Y}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k}\psi^{j}=d^{k+1}\int_{\overline{M}_{0,1}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(H)^{k+1}\psi^{j}.$

Thus Equation (3.5) holds, independently of $n$, for $m=0$. Suppose that
$m>0$, hence

$\int_{\overline{M}_{(m+1)}^{Y}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k}\psi^{j}=\int_{\overline{M}_{(m)}^{Y}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k+1}\psi^{j}\\\
+m\int_{\overline{M}_{(m)}^{Y}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k}\psi^{j+1}-\int_{D_{(m)}(\mathbb{P}^{s},n)}\mathrm{ev}^{*}(Y)^{k}\psi^{j}.$

By induction, we need to compute only the integral on the right. By the
explicit formula in [Gat03, Remark 1.4], using that $Y$ has no rational
curves, it is

(3.6) $\sum_{r\geq
2}\int_{\overline{M}_{0,1+r}}\psi^{j}\sum_{\gamma_{1},\ldots,\gamma_{r}}\left((Y_{|Y}^{k}\cup\gamma_{1}\cup\cdots\cup\gamma_{r})\frac{1}{r!}\prod_{i=1}^{r}m_{i}\int_{\overline{M}_{(m_{i})}^{Y}(\mathbb{P}^{s},n_{i})}\mathrm{ev}^{*}(\gamma_{i}^{\vee})\right),$

where $m_{1}+\ldots+m_{r}=m$, $n_{1}+\ldots+n_{r}=n$, the $\gamma_{i}$ run
over a basis of the part of $H^{*}(Y)\otimes\mathbb{Q}$ induced by
$\mathbb{P}^{s}$, and $\gamma_{i}^{\vee}$ is the dual of $\gamma_{i}$ immersed
in $H^{*}(\mathbb{P}^{s})\otimes\mathbb{Q}$.

In order to compute (3.6), we may suppose that each $\gamma_{i}$ has
codimension $t_{i}$, that is $\gamma_{i}=H_{|Y}^{t_{i}}$. Thus the cap product
is

$Y_{|Y}^{k}\cup\gamma_{1}\cup\cdots\cup\gamma_{r}=d^{k}H_{|Y}^{k}\cup\gamma_{1}\cup\cdots\cup\gamma_{r}=d^{k+1}$

if and only if $\sum_{i=1}^{r}t_{i}=s-1-k$, otherwise it is zero. Since
$m_{i}<m$ for any $i$, by induction we have

$\displaystyle\prod_{i=1}^{r}m_{i}\int_{\overline{M}_{(m_{i})}^{Y}(\mathbb{P}^{s},n_{i})}\mathrm{ev}^{*}(\gamma_{i}^{\vee})$
$\displaystyle=\prod_{i=1}^{r}m_{i}\int_{\overline{M}_{(m_{i})}^{Y}(\mathbb{P}^{s},n_{i})}\mathrm{ev}^{*}(\frac{1}{d}H^{s-t_{i}-1})$
$\displaystyle=\prod_{i=1}^{r}\frac{m_{i}}{d^{s-t_{i}}}\int_{\overline{M}_{(m_{i})}^{Y}(\mathbb{P}^{s},n_{i})}\mathrm{ev}^{*}(Y^{s-t_{i}-1})$
$\displaystyle=\prod_{i=1}^{r}\frac{m_{i}}{d^{s-t_{i}}}d^{s-t_{i}}p_{t_{i}}(d)$
$\displaystyle=p_{s-1-k}(d).$

Thus (3.6) is either zero or $d^{k+1}p_{s-1-k}(d)$, as expected. ∎

We may apply Equation (3.5) to Definition 2.2.

######  Proposition 3.4.

There exists a polynomial $p(d)$ of degree $s-1$ such that, for every $d\geq
2s-1$, $T_{s,n}(d)=dp(d)$.

###### Proof.

If $d\geq 2s-1$, a general $Y$ is smooth and does not contain rational curves
by [Cle86]. The result follows by Proposition 3.3. ∎

Thus, in order to completely determinate the polynomial $T_{s,n}$, it is
enough to compute it for $s$ values of $d$ greater or equal than $2s-1$. Using
the packages [MS22, Mur23], we computed the following values by hand,

$\displaystyle T_{2,2}(3)$ $\displaystyle=\frac{135}{4},$ $\displaystyle
T_{2,2}(4)$ $\displaystyle=102,$ $\displaystyle T_{2,3}(3)$
$\displaystyle=244,$ $\displaystyle T_{2,3}(4)$
$\displaystyle=\frac{2384}{3}.$

Using polynomial interpolation, these values imply that for $d\geq 3$,

(3.7) $\displaystyle T_{2,2}(d)$
$\displaystyle=\frac{57}{4}d^{2}-\frac{63}{2}d,$ (3.8) $\displaystyle
T_{2,3}(d)$ $\displaystyle=\frac{352}{3}d^{2}-\frac{812}{3}d.$

We checked that (3.7) and (3.8) match (2.2) for many values of $d$, using
[Gat]. Using again interpolation, we see that

$T_{3,2}(d)=\frac{20331}{4}d^{3}-30294d^{2}+39852d.$

In Introduction, we said that we plan to compute the number of maximal contact
conics to any surface $Y\subset\mathbb{P}^{3}$ of degree $d$. This problem is
equivalent to removing from $T_{3,2}(d)$ the contribution from non enumerative
stable maps (e.g., double covers).

##  4\. Sextactic conics

In this section we focus on the case of smooth conics. Our goal is to compute
the contribution to $T_{2,2}$ from double covers. We denote by $Y$ a general
smooth plane curve of degree $d$.

######  Lemma 4.1.

Let $m$ be a non negative integer such that $m\leq 6$, and let $(C,f,x)$ be an
irreducible stable map that is not a double cover of a line. Then the moduli
space $\overline{M}_{(m)}^{Y}(\mathbb{P}^{2},2)$ is smooth of dimension $6-m$
at $(C,f,x)$ (which is the expected dimension).

###### Proof.

It follows from [Gat05, Lemma 2.1].∎

An immediate consequence of this lemma is the following.

######  Corollary 4.2.

Every irreducible stable map in $\overline{M}_{(m)}^{Y}(\mathbb{P}^{2},2)$
whose image in $\mathbb{P}^{2}$ is a smooth conic lies in a unique irreducible
component of $\overline{M}_{(m)}^{Y}(\mathbb{P}^{2},2)$ of the expected
dimension. The virtual fundamental class of this component is equal to the
usual one. Moreover, the number of smooth plane conics of maximal contact with
$Y$ is finite.

###### Proof.

The fact that the stable map $(C,f,x)$ lies in a unique irreducible component
of the expected dimension follows directly from the lemma. The virtual
fundamental class is equal to the usual one because it is smooth of the right
dimension.

Finally, the smooth plane conics of maximal contact with $Y$ are supported at
the isolated points of $\overline{M}_{(6)}^{Y}(\mathbb{P}^{2},2)$. Hence there
are only a finite number of them. ∎

######  Proposition 4.3.

The moduli space $\overline{M}^{Y}_{({5})}(\mathbb{P}^{2},2)$ is a connected
space with the following irreducible components.

  1. (A)

An irreducible component parameterizing smooth conics, denoted by $M^{*}$.

  2. (B)

One smooth rational curve for each line $l$ that is inflectional to $Y$ at
$p$. This space parameterizes $1$-marked double convers of $l$ such that the
mark is mapped to $p$.

###### Proof.

If the image of the stable map is a smooth conic, point $(A)$ follows from
Corollary 4.2. If the image is instead the union of two distinct lines, then
the conditions of [Gat05, Remark 1.5] cannot be satisfied.

Now, suppose that the stable map is a double cover of a line. If a
ramification point is mapped to a point of $Y$, it doubles the contact order
of the line with $Y$ at that point. It is clear that the only possibility for
getting a contact strictly greater than $4$ is when the ramification point is
mapped to an inflectional point. The choice of the other branch point gives a
unidimensional family.

Note that, for each point of $Y$, there is only one conic with contact order
$5$. Because if we had two, any conic in the pencil generated by them would
have contact order $5$. This is impossible. More formally, we may say that the
map of curves $\mathrm{ev}\colon M^{*}\rightarrow Y$ has degree $1$ by [Mur21,
Proposition 4.1].

Since $Y$ is smooth, we have $M^{*}\cong Y$. In particular $M^{*}$ is
connected.

Finally, $\overline{M}^{Y}_{({5})}(\mathbb{P}^{2},2)$ is connected because at
any inflectional point $p\in Y$, the only conic with contact order $5$ at $p$
is the double inflectional line. Thus $M^{*}$ meets any component in $(B)$. ∎

The components described in point $(B)$ are particularly interesting. We
denote them by $M_{l}$ as in the following.

######  Definition 4.4.

Let $l$ be a line inflectional to $Y$ at $p$. We denote by $M_{l}$ the closure
of the space of stable maps $(\mathbb{P}^{1},f,x)$ such that $f$ is a double
cover of $l$ ramified at $x$ and $f(x)=p$.

$\mathbb{P}^{1}$inflectional$f$$x$${\scriptstyle\bullet}$$p$ Figure 4.1. The
space $M_{l}$.

Figure 4.1 gives us an idea of a curve in $M_{l}$. Before we move on, we need
to understand better the virtual fundamental class of
$\overline{M}^{Y}_{({5})}(\mathbb{P}^{2},2)$. Note that there exists a section
$\sigma$ of a line bundle on $M^{*}$, whose vanishing describes the condition
of increasing by $1$ the contact order at the marked point, see [Gat05, Remark
1.12].

######  Proposition 4.5.

We have the following.

  1. (1)

The virtual fundamental class of $\overline{M}^{Y}_{({5})}(\mathbb{P}^{2},2)$
on $M_{l}$ is the usual one.

  2. (2)

Let $\mathcal{C}$ be the intersection between $M^{*}$ and $M_{l}$. The section
$\sigma$ on $M^{*}$ vanishes at $\mathcal{C}$ with multiplicity $1$.

###### Proof.

This proof involves some local computations. Let $[z_{0}:z_{1}:z_{2}]$ be
homogeneous coordinates for $\mathbb{P}^{2}$. We may assume, using an
automorphism of $\mathbb{P}^{1}$, that a general point of $M_{l}$ is a double
cover ramified at the points $[1:0]$ and $[0:1]$. Moreover, we fix a line
$l:z_{2}=0$ that is inflectional to $Y$ at $[1:0:0]$. Let us consider
coordinates of $\overline{M}_{0,0}(\mathbb{P}^{2},2)$ centered at a double
cover of $l$:

$[s:t]\mapsto[s^{2}+\epsilon_{1}t^{2}:t^{2}+\epsilon_{2}s^{2}:\epsilon_{3}s^{2}+\epsilon_{4}st+\epsilon_{5}t^{2}].$

In order to get the space of all double covers that map $[1:0]$ to $[1:0:0]$,
it is enough to impose

$\epsilon_{2}=\epsilon_{3}=\epsilon_{4}=\epsilon_{5}=0.$

So, we get the one dimensional space of double covers
$f\colon\mathbb{P}^{1}\rightarrow l$ whose image of a ramification point is
fixed. Locally around $[1:0]$, the maps can be represented as

$f(t)=\frac{t^{2}}{1+\epsilon_{1}t^{2}}.$

Let us add a marked point whose coordinate is $t=\epsilon$. The tangency
condition at the marked point is obtained by imposing that

$f(t+\epsilon)=\frac{(t+\epsilon)^{2}}{1+\epsilon_{1}(t+\epsilon)^{2}}=t^{2}+2t\epsilon+\epsilon^{2}-\epsilon_{1}o((t+\epsilon)^{4})$

has no linear $t$ terms locally around zero. This is obtained by imposing
$\epsilon=0$. Thus $M_{l}$ is locally the vanishing of linear coordinates. So
it is smooth, in particular it has a reduced structure in
$\overline{M}^{Y}_{({5})}(\mathbb{P}^{2},2)$.

Let us prove the second point. Let us consider the family of stable maps whose
image is a conic and centered at the double line $l$. In affine coordinates we
may represent it as

$f(t)=(t^{2}+\eta_{1}t+\eta_{2},\eta_{3}t^{2}+\eta_{4}t+\eta_{5}).$

Around the inflectional line $l$, the equation of $Y$ is, modulo a change of
coordinates, $z_{2}=z_{1}^{3}+o(z_{1}^{4})$. If we want that the family $f(t)$
meets $Y$ with contact order $5$, we need that all coefficients of $t^{i}$ are
zero for $i\leq 4$ in the following expression:

$\eta_{3}t^{2}+\eta_{4}t+\eta_{5}=(t^{2}+\eta_{1}t+\eta_{2})^{3}.$

In order to increase the multiplicity, we need that also the coefficient of
$t^{5}$ is zero. That is, $\eta_{1}=0$. This is true also if we consider
conics with one marked point (same as before). Thus, $\sigma$ vanishes around
$\mathcal{C}$ with a linear equation. ∎

We want to study the moduli space
$\overline{M}^{Y}_{({6})}(\mathbb{P}^{2},2)$. As we saw in the proof of
Proposition 4.3, the spaces $M_{l}$ have contact order $6$. So the following
corollary is easily proved.

######  Corollary 4.6.

The moduli space $\overline{M}^{Y}_{({6})}(\mathbb{P}^{2},2)$ has the
following connected components.

  1. (A)

One reduced point for every sextactic of $Y$.

  2. (B)

One smooth rational curve $M_{l}$ for each inflectional line $l$.

In order to compute the number of sextactic conics, we take the degree of the
virtual fundamental class of $\overline{M}^{Y}_{({6})}(\mathbb{P}^{2},2)$,
minus the contribution of components of type $M_{l}$. Let $b_{d}$ denote the
contribution of each of component. The rest of the section is dedicated to the
computation of $b_{d}$.

Let us note that this $M_{l}$ has a natural virtual fundamental class. Indeed,
as the line $l$ is fixed, $M_{l}$ is isomorphic to the subscheme of
$\overline{M}_{0,1}(\mathbb{P}^{1},2)$ whose contact order at the marked point
is $2$. That is,

(4.1) $M_{l}\cong\overline{M}^{H}_{(2)}(\mathbb{P}^{1},2).$

We use this equation in the proof of the following lemma.

######  Lemma 4.7.

We have $b_{d}=\frac{3}{4}$ for all $d\geq 3$.

###### Proof.

Let us fix an inflectional line $l$. By definition, $b_{d}$ is the degree of
the part of the virtual fundamental class of
$\overline{M}_{(6)}^{Y}(\mathbb{P}^{2},2)$ supported on $M_{l}$. By Example
2.1, if we restrict Equation (2.1) to $M_{l}$, we get

$((\mathrm{ev}^{*}(Y)+5\psi)\cdot[\overline{M}^{Y}_{(5)}(\mathbb{P}^{2},2)])_{|M_{l}}=b_{d}+3[D(\mathbb{P}^{2},(1,1),(2,3))]_{|M_{l}}.$

where

$D(\mathbb{P}^{2},(1,1),(2,3))=\overline{M}_{0,3}(Y,0)\times_{Y}\overline{M}_{(2)}(\mathbb{P}^{2},1)\times_{Y}\overline{M}_{(3)}(\mathbb{P}^{2},1).$

Note that $\overline{M}_{(3)}(\mathbb{P}^{2},1)$ is zero dimensional, each
point is the class of an inflectional line. When restricting to $M_{l}$, only
the component relative to $l$ is not annihilated. Inside $M_{l}$,
$D(\mathbb{P}^{2},(1,1),(2,3))$ is characterized by the fact that
parameterizes the only map with contact order strictly greater than $2$. Using
Equation (4.1), we get

$\displaystyle[D(\mathbb{P}^{2},(1,1),(2,3))]_{|M_{l}}$
$\displaystyle=(\mathrm{ev}^{*}(Y)+2\psi)_{|M_{l}}$
$\displaystyle=\int_{\overline{M}_{0,1}(\mathbb{P}^{2},2)}\prod_{k=0}^{2}(\mathrm{ev}^{*}(Y)+k\psi)$
$\displaystyle=\frac{1}{2}.$

Let $M^{*}$ denote the component of $\overline{M}_{(5)}^{Y}(\mathbb{P}^{2},2)$
parameterizing birational maps. It is the only component of
$\overline{M}_{(5)}^{Y}(\mathbb{P}^{2},2)$, meeting $M_{l}$, that is not
$M_{l}$ itself.

By Proposition 4.5, we have

$((\mathrm{ev}^{*}(Y)+5\psi)\cdot[M^{*}])_{|M_{l}}=1,$

and, using again Equation (4.1),

$\displaystyle(\mathrm{ev}^{*}(Y)+5\psi)_{|M_{l}}$
$\displaystyle=\int_{\overline{M}_{0,1}(\mathbb{P}^{2},2)}(d\mathrm{ev}^{*}(H)+5\psi)\cdot\prod_{k=0}^{1}(\mathrm{ev}^{*}(Y)+k\psi)$
$\displaystyle=\int_{\overline{M}_{0,1}(\mathbb{P}^{2},2)}5\mathrm{ev}^{*}(H)\cdot\psi^{2}$
$\displaystyle=\frac{5}{4}.$

This implies that $b_{d}=1+\frac{5}{4}-\frac{3}{2}=\frac{3}{4}$. ∎

We are ready to prove the main theorem.

###### Proof of Theorem 1.1.

The degree of the virtual fundamental class of
$\overline{M}_{(6)}^{Y}(\mathbb{P}^{2},2)$ is given by the number of sextactic
conics $n_{d}$ plus the contribution from double covers of inflectional lines.
By generality, the number of these lines is given by Example 3.2. Thus

$\deg([\overline{M}_{(6)}^{Y}(\mathbb{P}^{2},2)])=n_{d}+3d(d-2)b_{d}.$

Combined with Equation (3.7) and Lemma 4.7, we have $n_{d}=3d(4d-9)$, as
expected. ∎

######  Remark 4.8.

When $Y$ is not general, Theorem 1.1 is not true even if $Y$ is smooth.
Indeed, Lemma 4.1 is false in general, so is Corollary 4.6. Moreover, in
Proposition 4.5 we used that, locally around an inflectional point, the
equation of $Y$ is $z_{2}=z_{1}^{3}$. This is true because $Y$ is general,
otherwise the inflectional point may have greater multiplicity. The case when
$Y$ is not general, or even singular, is discussed in [TU02, MM19].

###  4.1. Curves of higher degree

Assuming $\deg(Y)=3$, the multiple cover contribution formula [GPS10,
Proposition 6.1] computes the contribution from $k$-cover of curves meeting
$Y$ with multiplicity $w$,

(4.2) $\frac{1}{k^{2}}\binom{k(w-1)-1}{k-1}.$

Lemma 4.7 coincides with this formula, even without assuming $\deg(Y)=3$. It
seems that such a assumption in unnecessary, so we expect that Formula (4.2)
is still valid if we consider, for example, maximal contact cubics. In this
case we have contribution from triple covers of inflectional lines. By
Equation (3.8), the expected number of such cubics would be

$\frac{352}{3}d^{2}-\frac{812}{3}d-\frac{10}{9}3d(d-2),$

so we have the following.

######  Conjecture 4.9.

The number of rational cubics with maximal contact with a general smooth curve
of degree $d\geq 3$ is

(4.3) $N_{d}=6d(19d-44).$

Note that $N_{3}=234$ as claimed in [BN22, 5.6]. For higher degrees, we expect
contribution from covers of irreducible curves, but also from reducible curves
obtained by combining maximal contact curves of lower degrees.

## References

  * [BN22] Lawrence Jack Barrott and Navid Nabijou, _Tangent curves to degenerating hypersurfaces_ , J. Reine Angew. Math. 793 (2022), 185–224. MR 4513164
  * [Bou23] Pierrick Bousseau, _A proof of N. Takahashi’s conjecture for (P2,E) and a refined sheaves/Gromov–Witten correspondence_ , Duke Math. J. 172 (2023), no. 15, 2895–2955. MR 4675044
  * [Cay63] A Cayley, _On the sextactic points of a plane curve_ , Proceedings of the Royal Society of London (1863), 553–555.
  * [CC08] Charles Cadman and Linda Chen, _Enumeration of rational plane curves tangent to a smooth cubic_ , Adv. Math. 219 (2008), no. 1, 316–343. MR 2435425
  * [Cle86] Herbert Clemens, _Curves on generic hypersurfaces_ , Ann. Sci. École Norm. Sup. (4) 19 (1986), no. 4, 629–636. MR 875091
  * [EH16] David Eisenbud and Joe Harris, _3264 and all that—a second course in algebraic geometry_ , Cambridge University Press, Cambridge, 2016. MR 3617981
  * [FP97] W. Fulton and R. Pandharipande, _Notes on stable maps and quantum cohomology_ , Algebraic geometry—Santa Cruz 1995, Proc. Sympos. Pure Math., vol. 62, Amer. Math. Soc., Providence, RI, 1997, pp. 45–96. MR 1492534
  * [Gat] Andreas Gathmann, _GROWI: A C++ program for the computation of Gromov-Witten invariants_ , https://www.mathematik.uni-kl.de/~gathmann/en/growi.php.
  * [Gat02] by same author, _Absolute and relative Gromov-Witten invariants of very ample hypersurfaces_ , Duke Math. J. 115 (2002), no. 2, 171–203. MR 1944571
  * [Gat03] by same author, _Relative Gromov-Witten invariants and the mirror formula_ , Math. Ann. 325 (2003), no. 2, 393–412. MR 1962055
  * [Gat05] by same author, _The number of plane conics that are five-fold tangent to a given curve_ , Compos. Math. 141 (2005), no. 2, 487–501. MR 2134277
  * [GPS10] Mark Gross, Rahul Pandharipande, and Bernd Siebert, _The tropical vertex_ , Duke Math. J. 153 (2010), no. 2, 297–362. MR 2667135
  * [Har77] Robin Hartshorne, _Algebraic Geometry_ , Springer-Verlag, New York-Heidelberg, 1977, Graduate Texts in Mathematics, No. 52. MR 0463157
  * [MM19] Paul Aleksander Maugesten and Torgunn Karoline Moe, _The 2-Hessian and sextactic points on plane algebraic curves_ , Math. Scand. 125 (2019), no. 1, 13–38. MR 4009323
  * [MS22] Giosuè Muratore and Csaba Schneider, _Effective computations of the Atiyah-Bott formula_ , J. Symbolic Comput. 112 (2022), 164–181. MR 4383164
  * [Mur21] Giosuè Muratore, _A recursive formula for osculating curves_ , Ark. Mat. 59 (2021), no. 1, 195–211. MR 4256011
  * [Mur23] by same author, _Computations of Gromov–Witten invariants of toric varieties_ , 2023.
  * [NR22] Navid Nabijou and Dhruv Ranganathan, _Gromov-Witten theory with maximal contacts_ , Forum Math. Sigma 10 (2022), Paper No. e5, 34. MR 4371043
  * [Pan98] Rahul Pandharipande, _Rational curves on hypersurfaces (after A. Givental)_ , Séminaire Bourbaki. Vol. 1997/98, no. 252, Paris: Société Mathématique de France, 1998, pp. Exp. No. 848, 5, 307–340. MR 1685628
  * [SS24] Tomasz Szemberg and Justyna Szpond, _Sextactic points on the Fermat cubic curve and arrangements of conics_ , J. Symbolic Comput. 120 (2024), Paper No. 102228, 8. MR 4586769
  * [Tak96] Nobuyoshi Takahashi, _Curves in the complement of a smooth plane cubic whose normalizations are $\mathbb{A}^{1}$_, 1996.
  * [Tak01] Nobuyoshi Takahashi, _Log mirror symmetry and local mirror symmetry_ , Comm. Math. Phys. 220 (2001), no. 2, 293–299. MR 1844627
  * [TU02] Gudlaugur Thorbergsson and Masaaki Umehara, _Sextactic points on a simple closed curve_ , Nagoya Math. J. 167 (2002), 55–94. MR 1924719