# Changing CO Bands in Near-IR Spectra of CP Cephei

Scott G. Call,1 Eric G. Hintz,1 Steve Ardern,2 Victoria Scowcroft,2 and
Timothy D. Morrell1
1Department of Physics and Astronomy, Brigham Young University, Provo, Utah,
84602, USA
2Department of Physics, University of Bath, Claverton Down, Bath, BA2 7AY, UK

(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

We present time-series near-infrared (NIR) spectra for the classical Cepheid,
CP Cephei, from the Astrophysical Research Consortium 3.5-m telescope and NIR
spectrograph, TripleSpec, at Apache Point Observatory, NM, USA. Spectral
observations were made at three points on the ascending portion of the visible
phase diagram for the star. Carbon monoxide (CO) was detected in absorption in
the 2.3-micron band head for each observation. We observed that the equivalent
width of the 3-1 transition of the CO band head decreased by half from our
first observation to the second, or slightly over one day out of the
17.867-day period. Our third observation occurred 54 days after the first
(slightly over three periods for the star) and showed similar CO levels to the
first observation, suggesting that the CO is in the stellar atmosphere and
varies with pulsation.

###### keywords:

stars: variables: Cepheids – infrared: stars – stars: abundances

††pubyear: 2023††pagerange: Changing CO Bands in Near-IR Spectra of CP
Cephei–Changing CO Bands in Near-IR Spectra of CP Cephei

##  1 Introduction

The period-luminosity relation of classical Cepheid variables, the Leavitt
law, has been shown to have less scatter at longer wavelengths (Madore &
Freedman, 1991). As we move beyond the optical region, temperature variation
of the stars and extinction due to the interstellar medium become smaller
obstacles to obtaining accurate measurements. The near and mid-infrared (NIR
and MIR) have become the priority regions for distance measurements using the
Leavitt law.

The conditions present in supergiant stars allow carbon monoxide (CO) to form
in the atmospheres (see Lancon & Rocca-Volmerange, 1992). Marengo et al.
(2010) found that variable CO was the cause of color variations in the
$4.5\,\mathrm{\mu m}$ passband for a selection of Cepheids, and modeled the CO
variation at different phases for one star. The dissociation and recombination
of CO in Cepheid atmospheres is the result of changes in temperature and thus,
correlated with pulsation phase (discussions of this are given in Scowcroft et
al., 2011; Monson et al., 2012; Scowcroft et al., 2016). As temperature
decreases and CO forms, the flux in the associated passband will be suppressed
due to greater absorption (see Figure 2 of Scowcroft et al., 2016).

In addition to the photometric detections in the MIR, Hamer et al. (2023)
observed CO in four classical Cepheids at sub-mm wavelengths. This represents
the first direct evidence of CO in Cepheid atmospheres. We present NIR
spectroscopic data for CP Cephei (hereafter CP Cep), one of the targets
observed by Hamer et al. (2023), confirming CO presence in the form of the
2.3-$\mathrm{\mu m}$ band head. We observed CP Cep three times all at similar
phases, and the CO strength in these observations confirm the variation is
correlated with pulsation of the star.

This work contains the initial spectroscopic observations of temperature
dependent CO in CP Cep. In Section 2 we discuss the instrumentation and data
reduction and provide context for the observations. Our brief analysis of
changes in CO strength and the results from the three observations are given
in Section 3. We conclude with a summary of our findings.

##  2 Observations

Near-infrared observations of CP Cephei (CP Cep) were obtained using the
Astrophysical Research Consortium 3.5-m telescope at Apache Point Observatory
on July 4th, July 5th, and August 27th, 2023 (UTC). The near-infrared
spectrograph, _TripleSpec_ , covers a range of
$0.95{\text{-}}2.46\,\mathrm{\mu m}$ with spectral resolution
$\mathrm{R}=3500$ (Wilson et al., 2004). Observations were “nodded”, or
dithered, between two points on the slit allowing for subtraction of
atmospheric emission lines and background. Standard stars were observed close
in time and airmass to CP Cep for flux calibration and correction of telluric
absorption.

Figure 1: Calibrated spectra for CP Cep for the three nights of observation.
Low signal-to-noise segments due to atmospheric absorption were removed. To
better show the differences in continuum levels, the July 4th and August 27th
spectra are both offset by $+10^{-13}\,\mathrm{erg\,s^{-1}\,cm^{-2}}$ Å-1. The
phase increases from top to bottom.

Table 1 details the observations and sky conditions. Spectral extraction and
telluric correction were performed using a modified version of _SpexTool_
(Cushing et al., 2004; Vacca et al., 2003). We had a small window to observe
CP Cep at an acceptable airmass ($<1.5$) on July 4th. The target was higher in
the sky during our observing run the following night, with almost 26 hours
between observations. The sky conditions on both July nights were mostly clear
with the possibility of thin clouds affecting the strength of signal. For the
August observation, clouds were intermittent at the beginning of the session
which led to a larger difference in airmass between our standard and CP Cep.
Flux values should not be considered absolute due to uncertainties stemming
from sky conditions.

Near-infrared spectra for CP Cep from the three nights are shown in Figure 1,
with the fluxes of two of the observations shifted for the sake of comparison.
The shape of each continuum is indicative of temperature, with the spectra
from July 4th as the coolest of the set with more of a curved continuum and
the July 5th as the hottest. At 2.3-$\mathrm{\mu m}$ three transitions of the
CO absorption feature are visible in the July 4th and August 27th
observations. In the July 5th spectra the CO feature is more difficult to
distinguish from the continuum.

Table 1: Table of observations. $T$ is the total exposure time, $\phi$ is the phase, $X$ is the average airmass, and $\Delta X$ is the difference in airmass between CP Cep and the standard. Obs Date | $T$ | $\phi$ | $X$ | $\Delta X$
---|---|---|---|---
UTC | s |  |  | std-obj
2023-07-04 | 120 | 0.832 | 1.371 | -0.0708
2023-07-05 | 450 | 0.893 | 1.137 | -0.0342
2023-08-27 | 450 | 0.853 | 1.243 | -0.1112

The phase diagram in Figure 2 was constructed using $K$-band magnitudes from
Monson & Pierce (2011) with the corresponding gloess fitted light curve
(Persson et al., 2004) and shifted magnitudes from TESS in 2022. We adopted
the period of 17.867373 days from _Gaia_ (Gaia Collaboration et al., 2016,
2023) and used maximum light from the TESS data as the epoch. Vertical lines
are overlaid showing the phase locality of our observations. Our three
observations of CP Cep happen after the bump on the ascending portion of the
visible light curve, with the first observation on the relatively flat section
and second on the steep rise. The phase of our third observation similar to
the first observation, but slightly farther along. These observations are near
minimum light in the $K$-band.

Figure 2: Phase diagram for CP Cep comprised of $K$-band photometry from
Monson & Pierce (2011) and 2022 TESS photometry shifted 1.5 magnitudes
brighter for the purpose of comparison. Vertical lines are our observations
relative to the phase, with solid orange, purple dotted-dash, and dotted green
representing July 4th, July 5th and August 27th respectively.

##  3 Results

Figure 3: The normalized spectra from each night for a segment of the $K$
region. Vertical lines represent the central wavelengths for CO transitions in
vacuum, and are labeled in the top plot. The bottom has July 5th plotted with
July 4th to show differences in depth and width.

The $2.3{\text{-}}\mathrm{\mu m}$ CO band head is strong enough on the first
and third nights of observations that it can be seen even in the full spectra
given in Figure 1. While the CO band head is there on July 5th, it is not as
deep. To visualize the decrease in strength, the normalized spectra for the
range covering four of the ro-vibrational transitions (2-0, 3-1, 4-2 and 5-3)
in the band head are shown in Figure 3, and the bottom plot has the normalized
spectra of the second night overlaid on the first night. While the CO features
decreased in strength between observations on July 4th and July 5th, other
features remained relatively constant such as the metal lines near
$2.28\,\mathrm{and}\,2.34\,\mathrm{\mu m}$.

Out of the four transitions, the 3-1 transition appears to be the best
indicator of the change in CO strength in our set of spectra. The 4-2
transition seems to have more contamination from metal lines in the stellar
atmosphere, and many telluric absorption lines exist in the area of the 5-3
transition. Also, the even-to-even transitions, 2-0 and 4-2, appear to be
greatly broadened on the second night while the 3-1 and 5-3 transitions are
not. There is some indication of this broadening on the August 27th
observation, with slight depressions to the right of the central wavelengths
for the 2-0 and 4-2 transitions.

Historically, the most common transition to measure in this CO feature is the
2-0. Indices for CO from Origlia et al. (1993) and Frogel et al. (2001) are
often used in extragalactic research, and the index from Kleinmann & Hall
(1986) is often used for late-type stars. We would intend to use the same
wavelength ranges for comparison, but the 2-0 broadening seen in the July 5th
data requires us to use the 3-1 transition.

To quantify the change in CO strength, equivalent widths of the 3-1 transition
were carefully measured using the _Specutils_ package of astropy (Astropy
Collaboration et al., 2022; Earl et al., 2023). We defined the 3-1 feature as
the range from 2.32061 to 2.33016 $\mathrm{\mu m}$. The results are shown in
Table 2 with the average signal-to-noise for the wavelength range and
calculated errors. For the 3-1 transition, the equivalent width decreased by a
factor of 2 from the first observation on the relatively flat portion of the
bump to the second observation about halfway up the ascending section (a phase
difference of $0.061$). From the first observation to the third (phase
difference of $0.012$), the equivalent width decreased by less than $0.1$ Å
and the errors overlap.

Table 2: Equivalent width (W) measurements for the 3-1 transition and mean signal-to-noise (SNR) for the wavelengths used in determining W. Associated errors were calculated using Cayrel (1988). Obs Date | W (Å) | SNR
---|---|---
2023-07-04 | $3.111\pm 0.0463$ | 391.3
2023-07-05 | $1.509\pm 0.1183$ | 153.3
2023-08-27 | $3.024\pm 0.0876$ | 202.8

##  4 Conclusions

Figure 4: Normalized spectra from July 4 with the $K$ and $K_{s}$ filter
profiles overlaid. The four CO band head transitions are labeled as is the
nearby hydrogen absorption line, Brackett 7-4.

We obtained NIR spectra for the classical Cepheid, CP Cep, at three different
phases. The transitions of the CO band head are present in each observation
but with differing depths and equivalent widths. The strengths of these
transitions appear to change with the pulsation of the star, which agrees with
previous work in the MIR (Scowcroft et al., 2016). The August observation was
at a similar phase to the July 4th observation and features similar depths and
equivalent widths, but these data were obtained three pulsation cycles later;
further suggesting that the CO absorption is in the star and not the
interstellar medium.

The effect the changing CO absorption levels has on the photometry is beyond
the scope of this paper, but we have included the Mauna Kea filter profiles in
the area of interest in Figure 4 (Tokunaga et al., 2002). The $K_{s}$ filter
was developed to minimize the effect of the atmosphere’s thermal background
for ground-based telescopes, and Persson et al. (1998) showed that the CO band
head was responsible for the scatter seen in $K-K_{s}$ for red stars. With
these filter profiles, we can see the $K_{s}$ filter captures the 2-0
transition at around $60\%$ transmission and the 3-1 transition close to
$0\%$. The $K$ filter however, captures the first three transitions in the
band head at almost full transmission. To determine whether this changing
opacity has a non-negligible effect on NIR photometric measurements, NIR
spectral observations should be taken at maximum and minimum CO strength.

We have confirmed that CO varies with pulsation with three observations of
classical Cepheid, CP Cep. One of those observations occurred several cycles
later and had a similar CO strength to the first observation confirming that
the CO is in the stellar atmosphere. To better understand this CO variation in
Cepheid atmospheres, more observations must be made at different phases for
this and other Cepheids.

## Acknowledgements

This paper includes data collected by the TESS mission, which are publicly
available from the Mikulski Archive for Space Telescopes (MAST). Based on
observations obtained with the Apache Point Observatory 3.5-meter telescope,
which is owned and operated by the Astrophysical Research Consortium.

## Data Availability

The data discussed in this paper will be made available upon reasonable
request.

## References

  * Astropy Collaboration et al. (2022) Astropy Collaboration et al., 2022, ApJ, 935, 167
  * Cayrel (1988) Cayrel R., 1988, in Cayrel de Strobel G., Spite M., eds, Vol. 132, The Impact of Very High S/N Spectroscopy on Stellar Physics. p. 345
  * Cushing et al. (2004) Cushing M. C., Vacca W. D., Rayner J. T., 2004, PASP, 116, 362
  * Earl et al. (2023) Earl N., et al., 2023, astropy/specutils: v1.11.0, Zenodo, doi:10.5281/zenodo.8049033
  * Frogel et al. (2001) Frogel J. A., Stephens A., Ramírez S., DePoy D. L., 2001, AJ, 122, 1896
  * Gaia Collaboration et al. (2016) Gaia Collaboration et al., 2016, A&A, 595, A1
  * Gaia Collaboration et al. (2023) Gaia Collaboration et al., 2023, A&A, 674, A1
  * Hamer et al. (2023) Hamer S. L., Ardern S., Scowcroft V., 2023, arXiv e-prints, p. arXiv:2302.14075
  * Kleinmann & Hall (1986) Kleinmann S. G., Hall D. N. B., 1986, ApJS, 62, 501
  * Lancon & Rocca-Volmerange (1992) Lancon A., Rocca-Volmerange B., 1992, A&AS, 96, 593
  * Madore & Freedman (1991) Madore B. F., Freedman W. L., 1991, PASP, 103, 933
  * Marengo et al. (2010) Marengo M., Evans N. R., Barmby P., Bono G., Welch D. L., Romaniello M., 2010, ApJ, 709, 120
  * Monson & Pierce (2011) Monson A. J., Pierce M. J., 2011, The Astrophysical Journal Supplement Series, 193, 12
  * Monson et al. (2012) Monson A. J., Freedman W. L., Madore B. F., Persson S. E., Scowcroft V., Seibert M., Rigby J. R., 2012, ApJ, 759, 146
  * Origlia et al. (1993) Origlia L., Moorwood A. F. M., Oliva E., 1993, A&A, 280, 536
  * Persson et al. (1998) Persson S. E., Murphy D. C., Krzeminski W., Roth M., Rieke M. J., 1998, AJ, 116, 2475
  * Persson et al. (2004) Persson S. E., Madore B. F., Krzemiński W., Freedman W. L., Roth M., Murphy D. C., 2004, AJ, 128, 2239
  * Scowcroft et al. (2011) Scowcroft V., Freedman W. L., Madore B. F., Monson A. J., Persson S. E., Seibert M., Rigby J. R., Sturch L., 2011, ApJ, 743, 76
  * Scowcroft et al. (2016) Scowcroft V., Seibert M., Freedman W. L., Beaton R. L., Madore B. F., Monson A. J., Rich J. A., Rigby J. R., 2016, MNRAS, 459, 1170
  * Tokunaga et al. (2002) Tokunaga A. T., Simons D. A., Vacca W. D., 2002, PASP, 114, 180
  * Vacca et al. (2003) Vacca W. D., Cushing M. C., Rayner J. T., 2003, PASP, 115, 389
  * Wilson et al. (2004) Wilson J. C., et al., 2004, in Moorwood A. F. M., Iye M., eds, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series Vol. 5492, Ground-based Instrumentation for Astronomy. pp 1295–1305, doi:10.1117/12.550925


11institutetext:  Yunnan Observatories, Chinese Academy of Sciences,Kunming
650216, China<EMAIL_ADDRESS>
22institutetext: University of Chinese Academy of Sciences, Beijing 100049,
China;
33institutetext: Key Laboratory for the Structure and Evolution of Celestial
Objects, Chinese Academy of Sciences, Kunming 650216, China
44institutetext: International Centre of Supernovae, Yunnan Key Laboratory,
Kunming 650216, China
55institutetext: South-Western Institute for Astronomy Research, Yunnan
University, Kunming 650500, China;
Received 20xx month day; accepted 20xx month day

# Prospects of the multi-channel photometric survey telescope in the
cosmological application of Type Ia supernovae

Zhenyu Wang 11223344 Jujia Zhang 113344 Xinzhong Er 55 Jinming Bai 113344

###### Abstract

The Multi-channel Photometric Survey Telescope (Mephisto) is a real-time,
three-color photometric system designed to capture the color evolution of
stars and transients accurately. This telescope system can be crucial in
cosmological distance measurements of low-redshift (low-$z$, $z$ $\lesssim
0.1$) Type Ia supernovae (SNe Ia). To optimize the capabilities of this
instrument, we perform a comprehensive simulation study before its official
operation is scheduled to start. By considering the impact of atmospheric
extinction, weather conditions, and the lunar phase at the observing site
involving the instrumental features, we simulate the light curves of SNe Ia
obtained by the Mephisto. The best strategy in the case of SN Ia cosmology is
to take the image at an exposure time of 130 s with a cadence of 3 days. In
this condition, Mephisto can obtain hundreds of high-quality SNe Ia to achieve
a distance measurement better than $4.5\%$. Given the on-time spectral
classification and monitoring of the Lijiang 2.4 m Telescope at the same
observatory, Mephisto, in the whole operation, can significantly enrich the
well-calibrated sample of supernovae at low-$z$ and improve the calibration
accuracy of high-$z$ SNe Ia.

###### keywords:

transients: supernovae; cosmology: cosmological parameters

##  1 Introduction

As the most reliable indicators of cosmological distance so far, Type Ia
supernovae (SNe Ia) play a crucial role in unveiling the accelerated expansion
of the universe (Riess et al. 1998; Perlmutter et al. 1999). Additionally, SNe
Ia have greatly contributed to the discovery of the Hubble tension (Dainotti
et al. 2021). Despite the proposal of dark energy as an explanation for the
accelerated expansion of the universe, our understanding of its fundamental
properties remains limited. As the most straightforward observational tool for
constraining the parameters associated with dark energy, SNe Ia achieve a high
level of accuracy when employed for distance measurements (Weinberg et al.
2013). However, the recent accuracy of SNe Ia (e.g., $\lesssim 7\%$, Abbott et
al. 2019) falls short in constraining cosmological parameters and determining
the nature of dark energy.

The crucial factor in constraining the range of cosmological parameter values
lies in accurately ascertaining the distances of SNe Ia at high-$z$ ( $z>$
0.5). The application of SNe Ia in cosmological distance measurement depends
on some empirical relations between the absolute peak brightness and shape of
light curves, for example, the width-luminosity relation (WLR, usually known
as the Phillips relation; Phillips 1993). The original form of the Phillips
relation is

$M(\lambda)_{max}=a+b\Delta m_{15}(\lambda),$ (1)

where $M(\lambda)_{max}$ represents the maximum absolute magnitude at a
particular band (usually using the $B$-band), and $\Delta m_{15}$ is the
decline rate from the peak luminosity to 15 days later. The coefficients $a$
and $b$ are measured by dozens of well-observed low-$z$ SNe Ia. Comparing with
the low-$z$ sample, one can derive the intrinsic brightness of SNe Ia at a
corresponding band for a given redshift and thus measure its luminosity
distance. For example, at $z$ = 0.01, the rest-frame 4310Å flux is observed in
the $B$-band, while at $z$ = 1.01 this same flux is roughly observed in the
$I$-band. To accurately determine the distances of SNe Ia at various
redshifts, it is imperative to possess knowledge regarding the wavelength-
dependent evolution of WLR. This calibration predicament in SN Ia cosmology is
the primary source of systematic error in constructing the SNe Ia Hubble
diagram. Consequently, enhancing calibration precision at low-$z$ becomes
indispensable for refining measurements of cosmological parameters using SNe
Ia. Moreover, low-$z$ supernova samples not only help to reduce the
uncertainties associated with high-$z$ SN Ia measurements but also provide
constraints to the Hubble constant (Riess et al. 2009, 2011, 2016, 2022),
which can alleviate the Hubble tension.

For low-$z$ samples, the current largest source of systematic error is the
calibration. The existing low-$z$ SNe Ia come from different telescopes, with
some using Bessel-like $UBVRI$ filters and some utilizing SDSS-like $ugriz$
filters. Differing filter systems present a significant challenge for
calibration at the level of a few percent. Even with the same filter system,
subtle differences can exist in the transmissions. The most direct approach to
reducing this error is to obtain additional samples using a consistent
telescope system. Extinction is another factor of systematic uncertainty. For
the purpose of calculating extinction, accurate color measurement is
essential. Additionally, variations in ignition positions (central versus off-
center) and explosion mechanisms (deflagration versus detonation) contribute
to the diversity of SN Ia observations.

Furthermore, WLR is not only a function of wavelength but also depends on the
spectral parameters of SNe Ia. Besides the outliers that cannot be
standardized by any kind of WLR, the normal SNe Ia can be further divided into
some subclasses depending on the spectral features around the peak brightness,
e.g., the equivalent width (EW, Branch et al. 2006), velocity (Wang et al.
2009), and temporal velocity gradient (Benetti et al. 2005) of Si II
$\lambda$6355\. The fine classification is an efficient way to improve the
accuracy of SNe Ia in distance measurement. For example, Wang et al. (2009)
divided the normal SNe Ia into two subclasses depending on the velocity of Si
II 6355 around the maximum brightness and improved the accuracy of the Hubble
diagram from 0.178 mag to 0.125 mag. Blondin et al. (2012) use different
coefficients to fit each subclasses of various SNe Ia depending on the EW of
Si II lines. Thus, to create a consistent sample, it is crucial to have three
spectra for every well-observed SN Ia that covers the spectral evolution from
a few days before to a few days after the $B$-band maximum.

In this paper, we investigate the possibility of the Multi-channel Photometric
Survey Telescope (Mephisto, Yuan et al. 2020) for low-$z$ calibration of SNe
Ia. Mephisto is a 1.6-meter wide-field high-precision telescope with a 2 deg2
field of view. It is led by Yunnan University and co-built by Yunnan
Observatories and Nanjing Institute of Astronomical Optics & Technology. This
telescope can simultaneously image the sky in three bands ($ugi$ or $vrz$) and
obtain real-time color information. It boasts high color calibration accuracy,
which can effectively reduce errors introduced by extinction and reddening.
Moreover, the available samples around $z=0.1$ so far are low (Abbott et al.
2019). As a 1.6 m-aperture wide-field survey telescope, it has the ability to
obtain a great number of high-quality samples. Based on multi-color
photometry, it can trigger the Lijiang 2.4 m Telescope (LJT, Fan et al. 2015)
to perform follow-up spectral observation. We can get the spectral evolution
to help us identify the subclass. Hence, we can remove SNe Ia with larger
deviations in the analysis, and thus reduce the uncertainty in the Hubble
diagram.

To improve the observation efficiency of Mephisto, we conduct observation
simulation and cosmological fitting to produce an appropriate observation
strategy. We use SNCosmo (Barbary et al. 2022) in this study to simulate the
light curves of SNe Ia for Mephisto. Section 2 provides a concise introduction
to the fundamental information of Mephitso and the Lijiang Observatory.
Section 3 delves into the simulation of SN Ia light curves and the photometric
accuracy under different exposure durations. The cosmological parameter
estimation method is detailed in Section 4. Section 5 is the presentation of
the results, and there we have provided appropriate observation strategies.
Section 6 presents the results of the estimation and provides suggestions for
future observations.

##  2 Mephisto and Lijiang Observatory

Mephisto innovatively uses a Ritchey-Chrétien (RC) system with correctors and
film-coated cubic prisms, so that the focal plane of the telescope is under
the main mirror and there is a large distance between the focal plane and the
main mirror. Therefore, the color separation system and multiple cameras can
be placed in the rear optical path while ensuring a high-quality image in the
entire field of view. The telescope is equipped with three high-quality CCD
cameras, which can capture real-time color images of the same patch of sky in
three different bands ($ugi$ or $vrz$), providing valuable color information.

The current total efficiency of Mephisto is depicted in Figure 1. The filters
used by Mephisto are not the most popular system among observers, e.g.,
$UBVRI$ of Johnson-Cousins or $ugriz$ of SDSS. The specific choice of these
filters depends largely on their scientific objectives. Mephisto’s survey mode
includes both W-survey and D/H/M-survey modes. The W mode focuses on 2*20
second exposures of observable areas in the northern hemisphere ($\delta>$15°,
26,000 square degrees). The D/H/M models, on the other hand, sample at daily,
hourly, and minute cadence, respectively, for time-domain astronomy
observations. The observation strategy adopted in this paper is based on D
mode.

Mephisto is situated at the Lijiang Observatory administered by Yunnan
Observatories, located in Gaomeigu, Lijiang City, in Yunnan Province, China,
at an altitude of 3200 meters. The site benefits from an effective observation
time of more than 2000 hours per year. The average seeing is about 1.17, with
25$\%$ of the time experiencing seeing below 0.91 and 75$\%$ of the time
experiencing seeing below 1.33 (Xin et al. 2020). Overall, the Lijiang
Observatory is an outstanding site for optical surveys.

Figure 1: The current total efficiency of Mephisto in $u,v,g,r,i$ and $z$
bands.

##  3 The simulation of SNe Ia

The simulation of SN Ia light curves is discussed in Section 3.1. We take
atmospheric extinction, seeing, telescope efficiency, weather, and lunar phase
into consideration. We explore the impact of exposure time on the accuracy of
light measurement and distance measurement in Section 3.2. In Section 3.3, we
list some well-observed spectra captured by LJT.

###  3.1 SN Ia light curve

The modified spectral adaptive light curve template (SALT2, Guy et al. 2007)
model produces a spectral energy distribution (SED) for the following
simulation. The flux is defined as follows

$F(t,\lambda)=x_{0}\times[M_{0}(t,\lambda)+x_{1}M_{1}(t,\lambda)]\times
exp[c\times CL(\lambda)],$ (2)

where $\lambda$ and t represent the rest-frame wavelength and time
respectively, $M_{0}$($t$, $\lambda$) and $M_{1}$(t, $\lambda$) describe the
temporal variation of SED, CL($\lambda$) is the average color correction law,
$x_{0}$, $x_{1}$ and $c$ are the fitting parameters of the light curves for
SNe Ia, $x_{0}$ is the flux normalization parameter, $x_{1}$ is the stretch
parameter, and $c$ is color. In addition to atmospheric extinction, seeing,
and telescope efficiency, we consider several other factors, including:

Figure 2: This figure simulates an SN Ia with $z$ = 0.1, taking atmospheric
extinction, seeing, weather, and lunar phase into account. The exposure time
is 130 s. The absolute magnitude in the $B$-band is -19.3 mag. The top panel
shows the observation data without the influence of the lunar phase, while the
bottom panel includes the lunar phase.

Weather: Lijiang experiences a notable rainy season from June to September.
The number of nights suitable for observation during this period is relatively
limited. This paper primarily focuses on analyzing the weather patterns during
the dry season. Based on the statistics of the weather conditions (Xin et al.
2020), usually there are about 200 nights in one year which are suitable for
observations. In this study, we adopt 200 observational nights per year in the
simulation. The occurrence of supernovae is uniformly and randomly distributed
among these 200 days. Furthermore, weather conditions are also taken into
account. Even during the dry season, there may be occasional instances where
observation is hindered due to factors such as precipitation or high humidity.
Therefore, a few data points are randomly omitted from the observed dataset to
account for these circumstances.

Lunar phase: The influence of the lunar phase on observation is predominantly
concentrated in the $u$ and $g$ bands, which correspond to the $u$, $v$, and
$g$ bands of Mephisto. We incorporated the effect of lunar phase into these
three bands, based on data from ref. Xin et al. (2020), as per the
corresponding lunar calendar during the time of observation. The observation
data with and without the influence of the lunar phase are presented in Figure
2. As we can see, the influence of the lunar phase decreases the number of
observable days in the $u$ and $v$ bands.

data: We generate a batch of SNe Ia with the following conditions. In our
simulation, the redshifts are less than 0.5. The volumetric rate of SNe Ia we
adopt in this simulation is $1.0\times 10^{-4}$ yr-1 Mpc-3 according to ref.
Rodney_2014. The redshift distribution of 4957 SNe Ia with 200 days of
observation time and a 180 $deg^{2}$ sky area is shown in the upper panel of
figure 5. The absolute magnitude follows a normal distribution with a mean of
-19.26 and a standard deviation of 0.2 (Richardson et al. 2014). The
distributions of the parameters $x_{1}$ and $c$ obey the following functions
(Scolnic & Kessler 2016):

$P(x)=\left\\{\begin{aligned}
Ae^{(-(x-\overline{x})^{2})/2\sigma_{1}^{2}},x<\overline{x};\\\
Ae^{(-(x-\overline{x})^{2})/2\sigma_{2}^{2}},x\geq\overline{x}.\\\
\end{aligned}\right.$ (3)

where $A=\sqrt{2/\pi}(\sigma_{1}+\sigma_{2})^{-1}$, and $\overline{x}$ =
1.142, $\sigma_{1}$ = 1.652, and $\sigma_{2}$ = 0.104 for $x_{1}$, and
$\overline{x}$ = -0.061, $\sigma_{1}$ = 0.023, $\sigma_{2}$=0.083 for c (Li et
al. 2023). With these distributions, we have compiled a comprehensive library
of SN Ia light curves, which serves as a valuable resource for further
analysis.

###  3.2 exposure time

Table 1: The fitting results under different exposure times, and $\mu$ represents the distance modulus.  exposure time |  $\mu$
---|---
20 s |  $39.02\pm{0.21}$
60 s |  $38.84\pm{0.11}$
80 s |  $38.83\pm{0.10}$
130 s |  $38.82\pm{0.09}$

We test the photometric accuracy at different exposure times. The results are
plotted in Figure 3. Due to the sensitivity of the SALT2 fitting to
observation points near the maximum brightness, we select a total of 10 data
points before and after the maximum and evaluate the quality of photometric
measurements based on their errors. Additionally, for bands with fewer than 10
data points, we include all available data in our analysis.

Figure 3:  The horizontal axis is exposure time, and the vertical axis is the
average mag error over the 10 days before and after the $B$-band maximum. The
exposure time is from 10 to 200 s, with two decimal places retained for the
result. We select an SN Ia with a redshift of 0.1.

As expected, the photometric error generally decreases exponentially with
increasing exposure time. However, lower apparent magnitudes become visible in
the u-band with increasing exposure time, which leads to an overall increase
in the average photometric error in the $u$-band. Only data from the $g$ and
$r$ bands can be captured when the exposure time is limited to 10 s. Data of
$v,g,r$, and $i$ bands are available in all four bands when the exposure time
is longer than 20 s. Data from the $u$ band also becomes observable when the
exposure time is further increased to 60 s. Data from all six bands can be
detected when the exposure time exceeds 70 seconds. An increase of 10 s in
exposure time does not bring significant improvements in accuracy at 80 and
130 s. We take into account the SALT2 fitting accuracy under various exposure
times for further analysis. Table 1 displays the results of the fitting.
Fitting results show very small and close errors when the exposure time
exceeds 60 s. This indicates that the telescope can achieve good observation
accuracy for SNe Ia with redshifts near 0.1. The error in the distance modulus
decreases to $~{}0.1$ mag when the exposure time exceeds 80 s. This means the
distance uncertainty is $\lesssim 4.5\%$ according to the law of propagation
of uncertainties. We take 80 and 130 s into consideration for further
exploration.

###  3.3 Spectral diversity of well-observed SNe Ia

Spectral follow-up of LJT is crucial for achieving a homogeneous SN Ia sample
from Mephisto. For example, including three spectra at $t\sim-7,0,+7$ days
post-maximum is vital in obtaining essential information for diversity
studies, encompassing the examination of EW, velocity, and velocity
graduation. Consequently, we can effectively exclude subclass samples
exhibiting more significant dispersion, thereby reducing distance measurement
errors arising from scatter and enhancing the fitting accuracy of cosmological
parameters.

Table 2: The observation results of SNe Ia with a redshift of 0.1 under different cadences. SN Ia | $\Delta m_{15}(B)$ | $M_{B}$ | type(wang) | type(branch) | ref.
---|---|---|---|---|---
13dy | 0.90 | -19.65 | NV | CN | Zhai et al.2016
09ig | 0.90 | -19.46 | HV | $\cdots$ | Marion et al.2013
12fr | 0.85 | -19.49 | HV | SS | Zhang et al.2014
15bq | 0.82 | -19.68 | $\cdots$ | SS | Li et al.2022
19ein | 1.35 | -18.71 | HV | BL | Xi et al.2022
11fe | 1.18 | -19.40 | NV | CN | Zhang et al.2016

We present the photometric data of SNe Ia in Table 2, while Figure 4 shows
spectra of selected well-observed SNe Ia. Notably, supernovae with similar
$\Delta m_{15}$ values may exhibit varying absolute magnitudes, e.g., SN
2013dy and SN 2009ig. Through the measurement of the velocity of SiII
$\lambda$6355 SN 2013dy is classified into the normal-velocity (NV) type,
while SN 2009ig is classified into the high-velocity (HV) type in the Wang
diagram (Wang et al. 2009). The $\Delta m_{15}$ and $M_{B}$ of SNe 2012fr and
2015bq are similar. They are both divided into shallow silicon (SS) due to the
small EWs ($\leq 60\AA$) of Si II $\lambda$6355 (Branch et al. 2006). However,
SN 2012fr shows narrower Si II $\lambda$6355 and Ca II IRT profiles, with
generally deeper absorption lines than the 91T-like events. In the early
spectra, there are strong high-velocity features of Si II $\lambda$6355 that
are not seen in other 91T-like events (Zhang et al. 2014). SN 2019ein is a
91bg-like supernova. Its peak brightness is significantly lower than normal
SNe Ia. During maximum, the 91bg-like events show weak or absent Fe II lines
and strong absorption lines of intermediate elements. These supernovae do not
follow the WLR. SN 2011fe is a typical normal SN Ia. We also list some SNe Ia
with $z>0.05$, e.g., SN 2022zsy ($z\sim 0.06$), SN 2022aadh ($z\sim 0.076$),
and SN 2022adfs ($z\sim 0.088$).

The collaboration between LJT and Mephisto enables us to acquire a substantial
quantity of samples featuring spectra at $z\sim 0.1$ for subsequent
classification based on multidimensional spectral information. This
information facilitates the elimination of subclasses that significantly
deviate from the WLR, resulting in a more homogeneous sample set.
Additionally, distinct subclasses of supernovae exhibit varying Phillip
relationship coefficients, effectively mitigating the dispersion observed in
the SNe Ia Hubble diagram.

Figure 4: Temporal spectra of different subclasses of SNe Ia at a few days
before and after the $B$-band maximum. The spectrum of 13dy-7 is from ref
Zheng et al. (2013), and the others are from LJT.

##  4 Calibration and Constraints on Cosmological Parameters

To achieve higher accuracy, we conduct a preliminary screening on the data
before performing the light curve fitting. We remove some supernovae with a
limited number of observed data points. The filtering criteria are as follows:

  1. 1)

signal-to-noise ratio (S/N) greater than 5;

  2. 2)

The sum of all the bands is at least 15 data points;

  3. 3)

Data are available in at least three different bands;

  4. 4)

After applying the aforementioned selection criteria, we retained only the
supernovae with successful convergence in the SALT2 fitting.

We refer to SNe Ia that have passed the screening as good-samples. Table 3
presents the number of supernovae obtained under the observation conditions of
a 200 day time span and a 180 deg2 sky area. Mephisto has many scientific
goals, such as the search for extremely metal-poor stars and transient
sources. In our simulation, we focus on a 180 $deg^{2}$ sky area for our SNe
Ia survey, which accounts for about 20% of the observing time. Our analysis
primarily focuses on the cases with cadence of 2 days, 3 days, or 5 days,
considering exposure times of 80 s and 130 s respectively.

Table 3: The number of SNe Ia that can be observed after screening at different cadence and exposure times. The observation time is one year.  Cadence |  exposure time |  Number
---|---|---
2 d |  130 s |  1094
2 d |  80 s |  762
3 d |  130 s |  979
3 d |  80 s |  616
5 d |  130 s |  566
5 d |  80 s |  312

Various factors can influence the details of an SN Ia explosion, including the
precise location of ignition, whether it is at the center or off-center, and
the dynamical burning mechanism (e.g., subsonic deflagration or supersonic
detonation). Additionally, the circumstellar environment in which the
explosion occurs plays a significant role. These factors collectively
contribute to the observational diversities and result in distinct light curve
parameters. The dispersion caused by these influential factors can
substantially impact accurately fitting cosmological parameters. Therefore,
prior data calibration becomes imperative before undertaking cosmological
parameter fitting procedures. Our study employed the minimizing $\chi^{2}$
methodology (Marriner et al. 2011) to produce the best fitting result.

$\chi^{2}(\alpha,\beta)=\sum\limits_{i=1}[m_{xi}-{\mu}(z_{i})+{\alpha}x_{1i}-{\beta}c_{i}-M_{bin}(z)]^{2}/({\sigma}_{i}^{2}+{\sigma}_{int}^{2}),$
(4)

where $m_{xi}$, $x_{1i}$, and $c_{i}$ are the best-fit parameters of the SALT2
model for the $i-th$ SN Ia. $M_{bin}$ is a constant in each redshift bin. The
number of bins exceeds 30, with each redshift bin having a width of 0.01. The
definition of $M_{bin}$ is as follows

$M_{bin}(z_{b})=m_{x}-{\mu}(z)+{\alpha}x_{1}-{\beta}c,$ (5)

where $m_{x}=-2.5logx_{0}$, $\mu(z)$ is the distance modulus, and the redshift
$z_{b}$ represents the central point of each bin. One of the key benefits of
this approach is its robustness against variations in wavelength bands. The
difference between $m_{x}$ and $m_{0}$ is about 10 mag. While a cosmological
model is employed to calculate $\mu(z)$ in this process, it has been shown in
ref. Marriner et al. (2011) that the values of $\alpha$ and $\beta$ are not
affected by the choice of cosmological parameters when a large number of bins
are used. The definition of $\sigma_{int}$ is as follows

${\sigma}_{int}^{2}=V_{m_{x}}+\alpha^{2}V_{x_{1}}+\beta^{2}V_{c}+2\alpha
V_{m_{x},x_{1}}-2\beta V_{m_{x},c}-2\alpha\beta V_{x_{1},c},$ (6)

where $V$ represents the intrinsic covariance matrix of parameters,
$V_{m_{x}}$, $V_{x_{1}}$, and $V_{c}$ are the diagonal elements of the
covariance matrix, $V_{m_{x},x_{1}}$, $V_{m_{x},c}$, and $V_{x_{1},c}$ are the
corresponding off-diagonal elements. $\sigma_{i}^{2}$ is defined as follows

${\sigma}_{i}^{2}=V_{m_{xi}}+\alpha^{2}V_{x_{1i}}+\beta^{2}V_{c_{i}}+2\alpha
V_{m_{xi},x_{1i}}-2\beta V_{m_{xi},c_{i}}-2\alpha\beta V_{x_{1i},c_{i}},$ (7)

Similar to the definition of $\sigma_{int}^{2}$, the covariance matrix
consists of $m_{x}$, $x_{1}$, and $x_{0}$ for the $i-th$ SN Ia. Restrictions
on cosmological parameters can be made based on the observed distance moduli
$\mu$ and the theoretically calculated values of $\mu_{th}$. We consider the
flat $\Lambda CDM$ model here. We used the MCMC (Foreman-Mackey et al. 2013)
method for parameter fitting, with particular focus on the values of $H_{0}$
and $\Omega_{M}$. The likelihood function is defined as follows

$lnP=-\frac{1}{2}\sum_{i=0}^{n}\frac{(\mu_{i}-\mu_{th}(z_{i},H_{0},\Omega_{M}))^{2}}{\sigma_{\mu_{i}}^{2}}$
(8)

where $\mu_{i}=m_{x}-M_{0}(z_{b})+\alpha x_{1_{i}}-\beta c{{}_{i}}$, and
$\mu_{th}$ is defined as follows

$\mu_{th}(z_{i},H_{0},\Omega_{M})=5log(d_{L}/Mpc)+25$ (9)

Considering a flat universe and discarding the radiation term, the luminosity
distance $d_{L}$ is defined by

$d_{L}=\frac{c(1+z)}{H_{0}}\int_{0}^{z}{\frac{dz^{\prime}}{\sqrt{\Omega_{M}(1+z^{\prime})^{3}+(1-\Omega_{M})}}}$
(10)

The absolute peak magnitude of SNe Ia in our simulation follows a normal
distribution with a mean of -19.26 and a deviation of 0.2 (Richardson et al.
2014). This can lead to the production of supernovae that are very bright or
very dim. We removed data that significantly deviated from the Hubble flow.

##  5 Result

Figure 5: The top panel shows the original number-redshift distribution of
simulated SNe Ia (initial data, blue histogram) and selected SNe Ia (selected
data, red step line). The bottom panel displays the moduli-redshift
distribution of selected SNe Ia (red points). The solid line in the bottom
panel represents the theoretical prediction. The figure illustrates a scenario
where the cadence is 3 days and the exposure time is 130 s for red points. The
observation time is one year for both initial data and selected data.

Figure 5 displays the redshift distribution of the screened data. The
observation strategy utilized a cadence of 2 days and an exposure time of 130
s. The top panel displays the distribution of the number of SNe Ia with
redshifts. The blue histogram represents the original redshift distribution of
simulated SNe Ia, while the red step line depicts the number distribution of
SNe Ia after the selection process. The bottom panel displays the distribution
of distance moduli with redshift. The solid line represents a flat $\Lambda
CDM$ model with $\Omega_{M_{0}}$=0.3, $\Omega_{\Lambda_{0}}$=0.7, and
$H_{0}$=70 km s-1Mpc-1, which are used to generate the SNe Ia data. The red
points in the chart represent the distribution of SNe Ia after the selection
process. Under this observational strategy, the telescope’s observational
limit extends slightly beyond a redshift of 0.3. For supernovae with a
redshift around 0.1, there is not only good observational accuracy but also no
significant selection bias. However, selection bias is apparent when the
redshift exceeds 0.26.

Table 4: The observation results of an SN Ia with a redshift of 0.1 under different cadences. Observation Strategy |  $H_{0}$ |  $\Omega_{M}$
---|---|---
cadence=2 days, t=130 s |  $68.76^{+0.70}_{-0.72}$ |  $0.44^{+0.07}_{-0.07}$
cadence=2 days, t=80 s |  $68.83^{+0.91}_{-0.95}$ |  $0.45^{+0.12}_{-0.10}$
cadence=3 days, t=130 s |  $69.73^{+0.76}_{-0.77}$ |  $0.36^{+0.08}_{-0.08}$
cadence=3 days, t=80 s |  $69.70^{+1.01}_{-1.05}$ |  $0.37^{+0.13}_{-0.12}$
cadence=5 days, t=130 s |  $70.17^{+1.00}_{-1.03}$ |  $0.31^{+0.11}_{-0.11}$
cadence=5 days, t=80 s |  $70.58^{+1.36}_{-1.40}$ |  $0.26^{+0.19}_{-0.17}$

Figure 6: The MCMC fitting results include high-redshift SNe Ia. The left
panel is cadence = 2 days, and the right panel is cadence = 3 days. The
exposure times are both 130 s with a year of observation time.

The fitting results are shown in Table 4. The obtained fit results do not
align with the parameters used to generate the SNe data, which will be
discussed in the next section. Here we focus on the errors rather than the fit
values. From the results, it can be seen that the fit values have the smallest
errors for a cadence of 2 days and an exposure time of 130 s. However,
compared to the strategy with a cadence of 3 days and the same exposure time,
it increases the observation time by 33$\%$, resulting in only a 12.5$\%$
decrease in the error of $\Omega_{M}$ and almost no change in the error of
$H_{0}$. We include 88 high-$z$ samples at redshifts higher than 0.5 (Riess et
al. 2007; Brout et al. 2019). The improvement in precision at this level will
be washed out when incorporating existing data that includes high-$z$ samples
(see Figure 6). Therefore, taking everything into consideration, we recommend
adopting the strategy of a cadence of 3 days and an exposure time of 130
seconds for the observations.

##  6 Discussion and conclusion

The results obtained by different strategies indicate a deviation from the
cosmological parameters in generating the supernovae. The discrepancy is
attributed to multiple factors. Firstly, a sample collected at low-$z$
provides limited constraints on cosmological parameters. Figure 7 illustrates
the Hubble diagram at lower redshifts for different values of $\Omega_{M}$ and
$\Omega_{\Lambda}$. It can be seen that at low redshifts, the curves predicted
with different $\Omega_{M}$ and $\Omega_{\Lambda}$ almost overlap, indicating
that the constraints on $\Omega_{M}$ and $\Omega_{\Lambda}$ are weak by the
low-$z$ samples. Even a slight deviation can result in significant
discrepancies in the fitting values, highlighting the sensitivity of the
process. Another factor to consider is the diversity exhibited by SNe Ia,
which stems from variations in ignition locations, explosion mechanisms, and
environments. This study does not incorporate spectral simulations, thus
making it difficult to ascertain the abnormal supernovae within the simulated
data. This lack of comprehensive classification of SNe Ia may introduce biases
into the fitting of cosmological parameters. Moreover, it is essential to
acknowledge that Mephisto filters are non-standard and may introduce certain
biases during fitting procedures. Lastly, while the light curves of SNe Ia
align with actual observations, any deviations between fitted and actual
values can be attributed to potential limitations or inaccuracies within the
utilized cosmological model for generating SNe Ia at varying distances;
however, these deviations do not significantly impact overall error
estimation.

Figure 7:  Hubble diagram for different values of cosmological parameters. Red
points represent simulated SN Ia data, similar to the data in Figure 5.

This study serves as a preliminary investigation of the Mephisto survey. Once
Mephisto is fully operational, we can combine it with the LJT to obtain about
three spectra during the peak phase of well-observed SNe Ia. Currently, LJT
can identify 30–50 SNe Ia every year. With the addition of Mephisto, the
sample size of SNe Ia will be significantly increased. The fundamental
astrophysics of SNe Ia, including their progenitor scenarios and explosion
mechanisms, remains elusive (Liu et al. 2023). A larger sample size of SNe Ia
can significantly improve our ability to constrain the complex interplay
between the progenitor channels, explosion models, and observations.

Although Mephisto may not exhibit a numerical advantage in the quantity of SN
Ia discoveries compared to other large-scale survey telescopes, its
observational capabilities are formidable when detecting SNe Ia at lower
redshifts. Furthermore, the Mephisto project prides itself on its exceptional
color calibration precision and unique ability to conduct simultaneous
observations across three spectral bands. As a result, these features play a
significant role in partially mitigating systematic errors arising from
variations in site weather conditions.

We conducted a simulation for Mephisto to investigate the accuracy of
cosmological parameter estimation under various observation strategies, with a
fixed observation duration of 180 deg2 and 200 days. The optimal observation
strategy we have determined is an exposure duration of 130 seconds and a
frequency of three days. In our simulation, more than 900 SNe can be detected
in one year of observation. Implementing this strategy ensures commendable
photometric precision and enables us to detect numerous SNe Ia. Our simulation
has considered the influence of the lunar phase in the light curve and
assessed the photometric precision of SNe Ia at $z\sim$ 0.1 for various
exposure durations. The $\sigma_{\mu}$ of sources near redshift 0.1 are about
0.1 mag, with distance uncertainty 4.5%. Compared to the existing sample, the
distance measurement accuracy has improved from 7% to 4.5%. By incorporating
spectroscopic analysis to exclude abnormal SNe Ia, it is possible to achieve a
better fit of the Phillips relation coefficients and further enhance distance
measurement precision. We found that beyond an exposure time of 60 s, there is
a diminishing improvement in photometric accuracy with increasing duration.
Once Mephisto runs officially for survey purposes, the collaborative
observations with LJT will substantially increase the sample size of SNe Ia
and facilitate more comprehensive spectroscopic classification, thereby
mitigating the scatter induced by the diversities.

Mephisto and LJT can build an extensive SN Ia database, a valuable resource
for further analysis. This database will encompass light curves exhibiting
diverse shapes and brightness levels, along with spectra captured near the
peak of the light curve. This comprehensive dataset will offer a valuable tool
for investigating the heterogeneity of SN Ia events and comprehending their
utility as cosmological probes. Through meticulous examination of these data,
we can derive precise distance measurements, delve into the nature of dark
energy, and unveil fresh insights into the origin and evolution of our
universe.

###### Acknowledgements.

We thank the anonymous referee for constructive comments and suggestions. This
work was supported by the National Key R&D Program of China (2021YFA1600404),
the National Natural Science Foundation of China (12173082), and science
research grants from the China Manned Space Project (CMS-CSST-2021-A12), the
Yunnan Province Foundation (202201AT070069), the Top-notch Young Talents
Program of Yunnan Province, the Light of West China Program provided by the
Chinese Academy of Sciences, and the International Centre of Supernovae,
Yunnan Key Laboratory (202302AN360001). We acknowledge the support of the
staff of the LJT and Mephisto. Funding for the LJT has been provided by the
CAS and the People’s Government of Yunnan Province. The LJT is jointly
operated and administrated by YNAO and the Center for Astronomical Mega-
Science, CAS. Mephisto is mainly funded by the “Yunnan University Development
Plan for World-Class University” and “Yunnan University Development Plan for
World-Class Astronomy Discipline”, and obtained supports from the “Science &
Technology Champion Project” (202005AB160002) and from two “Team Projects” –
the “Innovation Team” (202105AE160021) and the “Top Team” (202305AT350002),
all funded by the “Yunnan Revitalization Talent Support Program”.

## References

  * Abbott et al. (2019) Abbott, T. M. C., Allam, S., Andersen, P., et al. 2019, ApJ, 872, L30
  * Barbary et al. (2022) Barbary, K., Bailey, S., Barentsen, G., et al. 2022, SNCosmo
  * Benetti et al. (2005) Benetti, S., Cappellaro, E., Mazzali, P. A., et al. 2005, ApJ, 623, 1011
  * Blondin et al. (2012) Blondin, S., Matheson, T., Kirshner, R. P., et al. 2012, AJ, 143, 126
  * Branch et al. (2006) Branch, D., Dang, L. C., Hall, N., et al. 2006, PASP, 118, 560
  * Brout et al. (2019) Brout, D., Scolnic, D., Kessler, R., et al. 2019, ApJ, 874, 150
  * Dainotti et al. (2021) Dainotti, M. G., De Simone, B., Schiavone, T., et al. 2021, ApJ, 912, 150
  * Fan et al. (2015) Fan, Y.-F., Bai, J.-M., Zhang, J.-J., et al. 2015, Research in Astronomy and Astrophysics, 15, 918
  * Foreman-Mackey et al. (2013) Foreman-Mackey, D., Hogg, D. W., Lang, D., & Goodman, J. 2013, PASP, 125, 306
  * Guy et al. (2007) Guy, J., Astier, P., Baumont, S., et al. 2007, A&A, 466, 11
  * Li et al. (2022) Li, L., Zhang, J., Dai, B., et al. 2022, ApJ, 924, 35
  * Li et al. (2023) Li, S.-Y., Li, Y.-L., Zhang, T., et al. 2023, Science China Physics, Mechanics, and Astronomy, 66, 229511
  * Liu et al. (2023) Liu, Z.-W., Röpke, F. K., & Han, Z. 2023, Research in Astronomy and Astrophysics, 23, 082001
  * Marion et al. (2013) Marion, G. H., Vinko, J., Wheeler, J. C., et al. 2013, ApJ, 777, 40
  * Marriner et al. (2011) Marriner, J., Bernstein, J. P., Kessler, R., et al. 2011, ApJ, 740, 72
  * Perlmutter et al. (1999) Perlmutter, S., Aldering, G., Goldhaber, G., et al. 1999, ApJ, 517, 565
  * Phillips (1993) Phillips, M. M. 1993, ApJ, 413, L105
  * Richardson et al. (2014) Richardson, D., Jenkins, Robert L., I., Wright, J., & Maddox, L. 2014, AJ, 147, 118
  * Riess et al. (1998) Riess, A. G., Filippenko, A. V., Challis, P., et al. 1998, AJ, 116, 1009
  * Riess et al. (2007) Riess, A. G., Strolger, L.-G., Casertano, S., et al. 2007, ApJ, 659, 98
  * Riess et al. (2009) Riess, A. G., Macri, L., Casertano, S., et al. 2009, ApJ, 699, 539
  * Riess et al. (2011) Riess, A. G., Macri, L., Casertano, S., et al. 2011, ApJ, 730, 119
  * Riess et al. (2016) Riess, A. G., Macri, L. M., Hoffmann, S. L., et al. 2016, ApJ, 826, 56
  * Riess et al. (2022) Riess, A. G., Yuan, W., Macri, L. M., et al. 2022, ApJ, 934, L7
  * Scolnic & Kessler (2016) Scolnic, D., & Kessler, R. 2016, ApJ, 822, L35
  * Wang et al. (2009) Wang, X., Filippenko, A. V., Ganeshalingam, M., et al. 2009, ApJ, 699, L139
  * Weinberg et al. (2013) Weinberg, D. H., Mortonson, M. J., Eisenstein, D. J., et al. 2013, Phys. Rep., 530, 87
  * Xi et al. (2022) Xi, G., Wang, X., Li, W., et al. 2022, MNRAS, 517, 4098
  * Xin et al. (2020) Xin, Y.-X., Bai, J.-M., Lun, B.-L., et al. 2020, Research in Astronomy and Astrophysics, 20, 149
  * Yuan et al. (2020) Yuan, X., Li, Z., Liu, X., et al. 2020, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 11445, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 114457M
  * Zhai et al. (2016) Zhai, Q., Zhang, J.-J., Wang, X.-F., et al. 2016, AJ, 151, 125
  * Zhang et al. (2014) Zhang, J.-J., Wang, X.-F., Bai, J.-M., et al. 2014, AJ, 148, 1
  * Zhang et al. (2016) Zhang, K., Wang, X., Zhang, J., et al. 2016, ApJ, 820, 67
  * Zheng et al. (2013) Zheng, W., Silverman, J. M., Filippenko, A. V., et al. 2013, ApJ, 778, L15


# Hamilton cycles in a semi-random graph model

Alan Frieze† Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh PA 15213<EMAIL_ADDRESS>and  Gregory B. Sorkin
Department of Mathematics, The London School of Economics and Political
Science, Houghton Street, London WC2A 2AE, England<EMAIL_ADDRESS>
(Date: 5 August 2022)

###### Abstract.

We show that whp we can build a Hamilton cycle after at most $1.85n$ rounds in
a particular semi-random model. In this model, in one round, we are given a
uniform random $v\in[n]$ and then we can add an _arbitrary_ edge
$\left\\{v,w\right\\}$. Our result improves on $2.016n$ in [5].

${\dagger}$ Research supported in part by NSF grant DMS1952285

##  1\. Introduction

We consider the following semi-random graph model. We start with $G_{0}$ equal
to the empty graph on vertex set $[n]$. We then obtain $G_{i+1}$ from
$G_{i},i\geq 0$ as follows: we are presented with a uniform random $v\in[n]$
and then we can choose to add an arbitrary edge $\left\\{v,w\right\\}$ to
$G_{i}$. This model was suggested by Peleg Michaeli and first explored in Ben-
Eliezer, Hefetz, Kronenberg, Parczyk, Shikhelman and Stojaković [1]. Further
research on the model can be found in Ben-Eliezer, Gishboliner, Hefetz and
Krivelevich [2]; Gao, Kamiński, MacRury and Prałat[3]; and Gao, Macrury and
Prałat[4, 5]. In particular [5] shows that whp one can construct a Hamilton
cycle in this model in at most $2.016n$ rounds.

In this short note we modify the algorithm of [5] and prove:

######  Theorem 1.1.

In the semi-random model, there is a strategy for constructing a Hamilton
cycle in at most $1.85n$ rounds.

##  2\. Outline and Algorithm

Our algorithm and analysis are largely similar to those of [5], so let us
recapitulate the broad strokes. They maintain a large and growing path, and a
set of isolated nodes. When an isolated node is presented they join it to the
tail of the path. When a path node $v$ is presented, they generate a
“stubedge” (our name, not theirs) to a random isolated node $w$; later, if a
path node $v^{\prime}$ adjacent to $v$ is presented, they generate edge
$\left\\{v^{\prime},w\right\\}$ and use it to insert the vertex $w$ into the
path between $v$ and $v^{\prime}$. These stubs are vital when the path is long
and there are few isolated vertices: at that point, isolated vertices are
rarely presented, while many stubs are generated. Note that by “birthday
paradox” reasoning, only $\Theta(\sqrt{n})$ stubs are needed before there is a
good chance of a neighboring vertex being presented.

As observed in [5], stubs can also be used to turn a Hamilton path into a
Hamilton cycle in $o(n)$ rounds. Assume w.l.o.g. that the path vertices are in
sequence $1,\ldots,n$. From each vertex $v$ presented, we generate a stubedge
randomly to vertex $1$ or $n$. If $v$ had a stubedge to $n$ and later $v+1$ is
presented, joining $v+1$ to $1$ creates a Hamilton cycle, using $1,\ldots,v$;
$v+1,\ldots,n$; the stubedge $\left\\{v,n\right\\}$; and the new edge
$\left\\{v+1,1\right\\}$. This takes expected time $O(1/\sqrt{n})$.

As in [5], we maintain a large and growing path and isolated nodes, but a key
difference is that we also maintain a set of _pairs_. When an isolated node
$v$ is presented, rather than joining it to the tail of the path, we join it
to another isolated node $v^{\prime}$ to make a pair. When a vertex $v$ in a
pair is presented, we join the pair to the tail of the path. Stubs are used to
incorporate into the path either an isolated node, just as in [5], or a pair:
If a stubedge goes from $v$ to a paired vertex $w$, and a path neighbor
$v^{\prime}$ of $v$ is presented, joining $v^{\prime}$ to the partner
$w^{\prime}$ of $w$ allows replacement of the edge
$\left\\{v,v^{\prime}\right\\}$ with the path $v,w,w^{\prime},v^{\prime}$.

The motivation for this is simple. If an isolated vertex $v$ is presented, the
number of components decreases by 1 whether $v$ is added to the path or paired
with another vertex $v^{\prime}$: in this sense, equal progress is made either
way. Ignoring the use of stubs, in the [5] algorithm, after $v$ is presented
and joined to the path, to join $v^{\prime}$ to the path we would have to wait
for $v^{\prime}$ to be presented. In the paired version, after $v$ is
presented and paired with $v^{\prime}$, to join the pair of them to the path
we wait until _either_ $v$ or $v^{\prime}$ is presented; this takes half as
long in expectation.

With regard to the stubs, the two versions are similar. As just noted, the
number of components (isolated vertices or pairs) needing to be incorporated
into the path (including by use of stubs) is the same either way. The only
drawback of the paired version is that the path’s growth is somewhat delayed,
so there are fewer early opportunities to create and use stubs.

##  3\. Algorithm and Differential Equations

Our algorithm is largely the same as the main “fully randomized algorithm” of
[5]. We do not employ any equivalent of their initial “degree-greedy” phase,
although doing so would probably improve our results slightly. Like them, we
run the main algorithm until the path is nearly but not quite complete, so
that it can be analysed by the differential equation method. We finish up by
appealing to the “clean-up” algorithm of [5, Lemma 2.5].

We now describe our algorithm in detail but briefly, then present the
corresponding differential equations. As said, we maintain a _path_ $P$, and
_non-path_ vertices $V$ consisting of _isolated_ vertices $V_{1}$ and _paired_
vertices $V_{2}$.

A _stubedge_ goes from a path vertex we call the _stubroot_ or simply _stub_
to a non-path vertex we call a _stubend_. We say a stubroot with $i$ stubedges
has _stub-degree_ $i$; we will also call it an _$i$ -stubroot_, and let
$S_{i}$ be the set of such vertices. We limit the stub-degree to at most 3, so
$S=S_{1}\cup S_{2}\cup S_{3}$ is the set of all stubroots. (There are never
more than about $0.001n$ 3-stubs, and restricting the degree to at most 2 as
in [5] only increases our completion time by about $0.002n$, from about
$1.8465n$ to $1.8482n$.)

Each path vertex is one of four types, and when focussing on type we will use
this font: a stub; a path-neighbor of a stub, called a stubneighbor; a clear
vertex, which if presented will become a stub; or a blocked vertex, which is
essentially useless.

In an abuse of notation, reusing the letters for the sets to denote their
cardinality, let $P=P(t)$ denote the number of vertices on the path at time
$t$, $V_{1}=V_{1}(t)$ the number of isolated vertices, $V_{2}=V_{2}(t)$ the
number of vertices in pairs, $S_{i}=S_{i}(t)$ the number of $i$-stubs (for
$i\in\left\\{1,2,3\right\\}$), $V(t)=V_{1}(t)+V_{2}(t)$, and
$S(t)=S_{1}(t)+S_{2}(t)+S_{3}(t)$. We explore the expected changes in these
quantities in one round.

Our algorithm will preserve the following property.

######  Property 3.1.

Within path-distance 2 of any stub there is no other stub nor any clear
vertex, and the total number of clear vertices is exactly $P-5S$.

We discuss this in case (C1) below.

###  3.1. Description of the Algorithm

We list the actions taken after a (random) vertex is presented. The
description below is valid as long as there remain at least 2 isolated
vertices, and we will stop the algorithm long before that is an issue.

  1. (C1)

_The presented vertex $v$ is clear._ Choose a random non-path vertex $w$ and
create a stubedge from $v$ to $w$, making $v$ a 1-stubroot. Change the type of
$v$ from clear to stub, and if $v$ has path-distance 5 or more from other
stubs, change the types of its path neighbors and second-neighbors,
respectively, to stubneighbor and blocked, i.e., BNSNB. If $v$ is at distance
4 from the next stub to the right, make the types from $v$ to the next stub be
SNBNS, and if distance 3, then SNNS.

This changes 5 or fewer vertices from clear to another type. If fewer, then
artificially change the type of additional clear vertices to blocked to make
it exactly 5. This, and the fact that there is no clear nor stub vertex within
path-distance 2 of $v$, preserve Property 3.1. There is no constraint on where
the artificially blocked vertices should be, and they need not even stay fixed
from round to round.

  2. (C2)

_The presented vertex $v$ is a stub with $i$ stubneighbors, $i=1,2$._ Choose a
random non-path vertex $w$ and create a stubedge from $v$ to $w$, making $v$
an $(i+1)$-stubroot.

  3. (C3)

_The presented vertex $v$ is a stubneighbor of a stub vertex $u$._ By Property
3.1, $u$ is uniquely determined. Randomly choose one of $u$’s stubneighbors,
$w$. Lengthen the path by removing the edge $\left\\{v,u\right\\}$, then
adding the path $u,w,v$ (if $w\in V_{1}$, making the new edge
$\left\\{v,w\right\\}$) or $u,w,w^{\prime},v$ (if $w\in V_{2}$ and
$w,w^{\prime}$ is a pair, making the new edge
$\left\\{v,w^{\prime}\right\\}$). If $u$’s degree was 2 or 3, $u$ becomes an
$(i-1)$-stub.

If $u$’s degree was 1, the stub disappears: $u$ and its two associated
stubneighbor vertices become clear, as do its two associated blocked vertices
unless they must remain blocked by proximity to some other stub. If necessary,
change one or two other blocked vertices to clear to preserve Property 3.1.

The stubedge $\left\\{v,w\right\\}$ becomes a path edge, and all other
stubedges into $w$ (and $w^{\prime}$, if relevant) are deleted. This results
in reducing the stub-degrees of other stubroots, and possibly their deletion.

  4. (C4)

_The presented vertex $v$ is on the path, but blocked or a stub of degree 3._
Do nothing.

  5. (C5)

_The presented vertex $v$ is isolated._ Choose another isolated vertex
$v^{\prime}$ at random and make a pair $v,v^{\prime}$.

  6. (C6)

_The presented vertex $v$ is one of a pair, with some $v^{\prime}$._ Add
$v,v^{\prime}$ to the tail of the path. As in (C3), delete all stubs to $v$
and $v^{\prime}$.

######  Lemma 3.2.

In (C6), each stubedge has probability $2/V(t)$ that its stubend is either $v$
or $v^{\prime}$, and these events are independent. In (C3) where $w$ was
isolated, each stubedge except $\left\\{v,w\right\\}$ has probability $1/V(t)$
that its stubend is $w$, and these events are independent. In (C3) where $w$
was paired with $w^{\prime}$, each stubedge except $\left\\{v,w\right\\}$ has
probability $2/V(t)$ that its stubend is either $w$ or $w^{\prime}$, and these
events are independent.

This is analogous to a claim within [5, Lemma 2.2]. For (C6) the Lemma is
immediate as the stubs to $v$ and $v^{\prime}$ are independent of their
getting paired or joining the path. In the (C3) cases, though, there is a
potential issue of size-biased sampling that is not explicitly addressed in
the proof in [5], and so we give a proof sketch. The issue is that $w$ being
the stubend of the chosen stubedge biases $w$ to have higher stub-degree
(e.g., $w$ could not have been selected if it had no stub edges), suggesting
that other stubedges are also more likely to have $w$ as stubend.

###### Proof.

Imagine that, when created, the stubedges are not revealed. They remain, then,
uniformly random between the stubroots (whose stub-degrees are “known”) and
non-path vertices. Only when the stubroot $v$ is determined and one of its
stubedges is chosen, reveal (or, indeed, generate) the stubedge: this
determines $w$. Only then, reveal (or generate) the other stubedges: each is
equally likely to lead to $w$ or any other non-path vertex (including
$w^{\prime}$, if relevant). So that we can apply the argument again in later
rounds, we can reveal just the stubedges incident to $w$ (and $w^{\prime}$ if
relevant): after deleting them, the other stubedges remain unrevealed and
uniformly random. ∎

Alternatively, one may argue from the perspective that if one sample is taken
from a population of i.i.d. Poisson $\lambda$ random variables, in proportion
to the variables’ values, the sampled value $X$ is not Poisson $\lambda$ (for
example, it cannot be 0), but $X-1$ is Poisson $\lambda$.

###  3.2. Derivation of the Equations

The following equations are valid as long as $P(t)\leq(1-\epsilon)n$ where
$\epsilon>0$ is arbitrarily small; anyway the differential equation method can
only be applied through such time. The error terms below are sometimes
naturally $O(1/n)$ and sometimes $O(1/V(t))$, but with this assumption we
always write them as $O(1/n)$.

####  3.2.1. ${\bf P(t)}$

$\displaystyle\mathbb{E}(P(t+1)\mid
G_{t})=P(t)+\frac{2V_{2}(t)}{n}+\frac{2S(t)}{n}\cdot\frac{V_{1}(t)+2V_{2}(t)}{V(t)}+O(1/n).$
(1)

(C6):

$V_{2}(t)/n$ is the probability that a paired vertex is presented. The path
length increases by 2.

(C3):

$2S(t)/n$ is the probability that a stubneighbor is presented.111Actually, a
stubneighbor is presented with probability $2S(t)/n+O(1/n)$, because a stub at
either end of $P$ would have only one neighbor rather than the two we are
assuming. The $O(1/n)$ correction term in (1) covers this case. Similar
correction terms apply in subsequent cases and we will not explain the rest.
By Property 3.1 the stubroot $v$ is uniquely determined, and one of its
stubedges $\left\\{v,w\right\\}$ is chosen randomly. With probability
$V_{1}(t)/V(t)$, $w$ is isolated and the path length increases by 1; with
probability $V_{2}(t)/V(t)$, $w$ is paired and the path length increases by 2.

####  3.2.2. ${\bf V_{1}(t)}$

$\displaystyle\mathbb{E}(V_{1}(t+1)\mid
G_{t})=V_{1}(t)-\frac{2V_{1}(t)}{n}-\frac{2S(t)}{n}\cdot\frac{V_{1}(t)}{V(t)}+O(1/n).$
(2)

(C5):

$V_{1}(t)/n$ is the probability that an isolated vertex is presented. The
vertex is paired with another isolated vertex and the number of isolated
vertices decreases by 2.

(C3):

$2S(t)/n$ is the probability that a stubneighbor is presented. As in section
3.2.1’s (C3), the chosen stubend of the stub is isolated with probability
$V_{1}(t)/V(t)$ and the number of isolated vertices decreases by 1.

####  3.2.3. ${\bf V_{2}(t)}$

$\displaystyle\mathbb{E}(V_{2}(t+1)\mid
G_{t})=V_{2}(t)-\frac{2V_{2}(t)}{n}+\frac{2V_{1}(t)}{n}-\frac{2S(t)}{n}\cdot\frac{2V_{2}(t)}{V(t)}+O(1/n).$
(3)

(C6):

$V_{2}(t)/n$ is the probability that a paired vertex is presented. The path is
extended using this pair, and the number of paired vertices decreases by 2.

(C5):

$V_{1}(t)/n$ is the probability that an isolated vertex is presented. The
vertex is paired with another isolated vertex and the number of paired
vertices increases by 2.

(C3):

$2S(t)/n$ is the probability that a stubneighbor is presented. The chosen
stubend of the stub is paired with probability $V_{2}(t)/V(t)$, and the number
of paired vertices decreases by 2.

At this point the reader will observe that the expected change in
$n=P(t)+V_{1}(t)+V_{2}(t)$ is zero, as it should be.

####  3.2.4. ${\bf S_{1}(t)}$

$\displaystyle\mathbb{E}(S_{1}(t+1)\mid G_{t})$
$\displaystyle=S_{1}(t)+\frac{P(t)-5S(t)}{n}-\frac{S_{1}(t)}{n}-\frac{2S_{1}(t)}{n}+\frac{2S_{2}(t)}{n}$
$\displaystyle\hskip
10.00002pt+\frac{2S(t)}{n}\cdot\frac{V_{1}(t)+2V_{2}(t)}{V(t)^{2}}\cdot(2S_{2}(t)-S_{1}(t))$
$\displaystyle\hskip
10.00002pt+\frac{V_{2}(t)}{n}\cdot\frac{2}{V(t)}\cdot(2S_{2}(t)-S_{1}(t))+O(1/n).$
(4)

(C1):

$(P(t)-5S(t))/n$ is the probability that a clear vertex is presented. It
becomes a 1-stub and $S_{1}(t)$ increases by 1.

(C2, $i=1$):

$S_{1}(t)/n$ is the probability that a 1-stub of the path is presented. It
becomes a 2-stub, and $S_{1}(t)$ decreases by 1.

(C3, $i=1$):

$2S_{1}(t)/n$ is the probability that a neighbor of a 1-stub is presented. The
stub is used and $S_{1}(t)$ decreases by 1.

(C3, $i=2$):

$2S_{2}(t)/n$ is the probability that a neighbor of a 2-stub is presented. The
stub is used and $S_{1}(t)$ increases by 1.

(C3):

$2S(t)/n$ is the probability that a stubneighbor is presented. As in previous
cases, the stub $v$ is determined and one of its stubedges
$\left\\{v,w\right\\}$ is chosen randomly. Edge $\left\\{v,w\right\\}$ becomes
a path edge, and is no longer a stubedge; this is captured by the previous two
cases.

All other stubedges into $w$, and its pair-partner $w^{\prime}$ if any, are
deleted. With probability $V_{1}(t)/V(t)$, $w$ was isolated, in which case by
Lemma 3.2 each stubedge has probability $1/V(t)$ of having $w$ as stubend.
With probability $V_{2}(t)/V(t)$, $w$ was paired with some $w^{\prime}$, in
which case by Lemma 3.2 each stubend has probability $2/V(t)$ of having $w$ or
$w^{\prime}$ as stubend. This gives the probability in the next term.

The effect in that term is that each $S_{2}$ vertex has 2 stubedges whose
potential deletion turns it into an $S_{1}$ vertex, increasing $S_{1}$ by 1,
while each $S_{1}$ vertex has 1 stubedge whose potential deletion turns it
into a clear vertex, decreasing $S_{1}$ by 1.

(C6):

$V_{2}(t)/n$ is the probability that a paired vertex is presented. As in the
preceding case, by Lemma 3.2 each stubedge has probability $2/V(t)$ of having
either element of the pair as stubend and thus being deleted. The effect is
that of the previous case.

####  3.2.5. $\bf S_{2}(t)$

$\displaystyle\mathbb{E}(S_{2}(t+1)\mid G_{t})$
$\displaystyle=S_{2}(t)+\frac{S_{1}(t)}{n}-\frac{S_{2}(t)}{n}-\frac{2S_{2}(t)}{n}+\frac{2S_{3}(t)}{n}$
$\displaystyle\hskip
10.00002pt+\left[\frac{2S(t)}{n}\cdot\frac{V_{1}(t)+2V_{2}(t)}{V(t)^{2}}+\frac{V_{2}(t)}{n}\cdot\frac{2}{V(t)}\right]\cdot(3S_{3}(t)-2S_{2}(t))+O(1/n).$
(5)

(C2, $i=1$):

$S_{1}(t)/n$ is the probability that a 1-stubroot of the path is presented. It
becomes a 2-stubroot, and $S_{2}(t)$ increases by 1.

(C2, $i=2$):

$S_{2}(t)/n$ is the probability that a 2-stubroot of the path is presented. It
becomes a 3-stubroot, and $S_{2}(t)$ decreases by 1.

(C3, $i=2$):

$2S_{2}(t)/n$ is the probability that a neighbor of a 2-stubroot is presented.
The stub is used and $S_{2}(t)$ decreases by 1.

(C3, $i=3$):

$2S_{3}(t)/n$ is the probability that a neighbor of a 3-stubroot is presented.
The stub is used and $S_{2}(t)$ increases by 1.

(C3),(C6):

Analogous to (C3) and (C6) of section 3.2.4, here combined.

####  3.2.6. $\bf S_{3}(t)$

$\displaystyle\mathbb{E}(S_{3}(t+1)\mid G_{t})$
$\displaystyle=S_{3}(t)+\frac{S_{2}(t)}{n}-\frac{2S_{3}(t)}{n}$
$\displaystyle\hskip
10.00002pt-\left[\frac{2S(t)}{n}\cdot\frac{V_{1}(t)+2V_{2}(t)}{V(t)^{2}}+\frac{V_{2}(t)}{n}\cdot\frac{2}{V(t)}\right]\cdot
3S_{3}(t)+O(1/n).$ (6)

(C2, $i=2$):

$S_{2}(t)/n$ is the probability that a 2-stub vertex of the path is presented.
It becomes a 2-stub, and $S_{3}(t)$ increases by 1.

(C3, $i=3$):

$2S_{3}(t)/n$ is the probability that a neighbor of a 3-stub is presented. The
stub is used and $S_{3}(t)$ decreases by 1.

(C3),(C6):

Analogous to the corresponding case of section 3.2.5.

The equations (1) – (3.2.6) lead to the following differential equations in
the usual way: we let $\tau=t/n$ and $p(\tau)=P(t)/n,v_{1}(\tau)=V_{1}(t)/n$
etc. The initial conditions are $v_{1}(0)=1,p(0)=v_{2}(0)=\cdots=s_{3}(0)=0$.

$\displaystyle\begin{split}p^{\prime}&=2v_{2}+\frac{2s(v_{1}+2v_{2})}{v}.\\\
v_{1}^{\prime}&=-2v_{1}-\frac{2sv_{1}}{v}.\\\
v_{2}^{\prime}&=-2v_{2}+2v_{1}-\frac{4sv_{2}}{v}.\\\
s_{1}^{\prime}&=p-5s-3s_{1}+2s_{2}+\left[\frac{2s(v_{1}+2v_{2})}{v^{2}}+\frac{2v_{2}(t)}{v}\right](2s_{2}-s_{1}).\\\
s_{2}^{\prime}&=s_{1}-3s_{2}+2s_{3}+\left[\frac{2s(v_{1}+2v_{2})}{v^{2}}+\frac{2v_{2}}{v}\right](3s_{3}-2s_{2}).\\\
s_{3}^{\prime}&=s_{2}-2s_{3}-\left[\frac{2s(v_{1}+2v_{2})}{v^{2}}+\frac{2v_{2}}{v}\right](3s_{3}).\\\
\end{split}$ (7)

A numerical simulation of the differential equations is shown in Figure 1. It
shows that $v_{1}(\tau^{*})+v_{2}(\tau^{*})\approx 0$ and $p(\tau^{*})\approx
1$ for $\tau^{*}\approx 1.85$. Justification of the use of the differential
equation method follows as in [5]. As in [5], we use the differential equation
method to analyse the algorithm until the path has length $(1-\epsilon)n$, for
some suitably small $\epsilon$. After this we apply the _clean-up_ algorithm
of [5, Lemma 2.5] to construct a Hamilton cycle in a further
$O(\sqrt{\epsilon}n+n^{3/4}\log^{2}n)$ rounds.

##  4\. Concluding Remarks

Our combining of isolated vertices into pairs leads to a substantial speedup
of the algorithm compared with [5], despite our skipping their first, “degree
greedy” phase. We allowed for stub degrees up to 3 where [5] goes up only to
2, but, observing that the number of degree-3 stubs is never more than about
$0.001n$, this seems to have been unimportant. Further improvements could
probably be made.

First, since pairs gave a big gain, it is natural to consider paths of 3
vertices (“triplets”) or more. We have not tried it, but it appears that this
cannot help. Specifically, if an isolated vertex $v$ is presented, there would
appear to be no advantage in using $v$ to extend a “pair” $Q$ to a 3-vertex
path, over concatenating $v$ to the main path. Either way, the number of
components is the same. Either way, $Q$ must eventually be brought into $P$,
either when one of its endpoints is presented (no difference in whether $p$ is
added to $Q$ or not, as either way $Q$ has two endpoints), or when a stubedge
to one of $Q$’s endpoints is used (again, with no advantage to $v$ over $Q$’s
earlier endpoint).

Other improvements, possibly challenging to analyse, would come from choices
intuitively more sensible than the uniformly random choices made by our
algorithm.

One such is to restore the “degree greedy” approach from [5] that we
discarded: when generating stubedges, let each go to a (random) non-path
vertex _of lowest stub-degree_.

Another, when generating stubedges, is to favour paired vertices over isolated
ones. We have some weak evidence that generating stubedges only to non-paired
vertices up to some time, then uniformly to all non-paired vertices, is better
than generating them uniformly throughout.

Another strategy is, in the case where a 2- or 3-stub is used, to select a
stubedge to a non-path vertex of low stub degree, and/or to favor an isolated
vertex over a paired one (or vice versa).

Returning to the idea of using “triples” as well as pairs, potentially, small
advantages could be found if, for example, we linked $v$ with $Q$ only if $v$
were the stubend of more stubedges than the $Q$-endpoint it extends.

It would be very satisfying in its own right to better understand the natural
stub process, where a presented vertex becomes a new stubroot unless it is
already a stubroot or stubneighbor, i.e., if it is at path distance at least 2
from every existing stub. This in contradistinction to the easier-to-analyse
process taken from [5] and described in (C1), where a presented vertex becomes
a stub only if it is at path distance at least 3 from every existing stub, and
not blocked. In the natural process, the number of stubneighbors will be
between 1 and 2 times the number of stubroots (not 2 times, as used in (C3))
but it is not clear how to find the typical number, nor give a good lower
bound. Presumably more stubroots will be produced, but it is not clear how to
control the likelihood that a presented vertex will become a stub; indeed,
nothing about the process is clear.

Figure 1. The differential equations simulated, as a function of time (rounds
divided by $n$). Path length $P$ (as a multiple of $n$) is shown in red,
isolated vertices $V_{1}$ in green, paired vertices $V_{2}$ in blue, and
degree 1-, 2-, and 3-stubs $S_{i}$ in yellow, turquoise, and magenta. (The
figure is clearer in some PDF viewers than others.)

## Acknowledgement

We thank Zachary Hunter for a spotting two oversights in the paper’s first
version.

## References

  * [1] O. Ben-Eliezer, D. Hefetz, G. Kronenberg, O. Parczyk, C. Shikhelman, M. Stojaković (2020). Semi‐random graph process. Random Structures & Algorithms, 56, 648–675.
  * [2] O. Ben-Eliezer, L. Gishboliner, D. Hefetz, M. Krivelevich. Very fast construction of bounded-degree spanning graphs via the semi-random graph process. Random Structures & Algorithms, 57(4), 892–919.
  * [3] P. Gao, B. Kamiński, C. MacRury, and P. Prałat. 2022. Hamilton cycles in the semi-random graph process. Eur. J. Comb. 99, C (Jan 2022).
  * [4] P. Gao, C. MacRury, and P. Prałat. Perfect Matchings in the Semirandom Graph Process. SIAM J. Discrete Mathematics 36(2) (2022).
  * [5] P. Gao, C. MacRury, and P. Prałat. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. 2022\. arXiv, https://arxiv.org/abs/2205.02350.