# Aspects of Rotating Anisotropic Dark Energy Stars

O. P. Jyothilakshmi<EMAIL_ADDRESS>Lakshmi J. Naik
<EMAIL_ADDRESS>V. Sreekanth<EMAIL_ADDRESS>Department of Physics, Amrita School of Physical Sciences Coimbatore, Amrita
Vishwa Vidyapeetham, India.

###### Abstract

By employing modified Chaplygin fluid prescription for the dark energy, we
construct slowly rotating isotropic and anisotropic dark energy stars. The
slow rotation is incorporated via general relativistic Hartle-Thorne
formalism; whereas the anisotropy is introduced through Bowers-Liang
prescription. We consider both the monopole and quadrupole deformations and
present a complete analysis of rotating dark energy stars. By numerically
solving the rotating stellar structure equations in presence of anisotropy, we
analyse and quantify various properties of dark energy stars such as mass
($M$), radius, mass deformation, angular momentum ($J$), moment of inertia,
and quadrupole moment ($Q$), for three different equation of state parameters.
We find that anisotropic slow rotation results in significant deformation of
stellar mass and thereby affects other global properties studied. For the
values of angular frequencies considered, the effect of anisotropy on the
stellar structure is found to be more prominent than that due to rotation. The
dimensionless quadrupole moment $QM/J^{2}$ measuring deviation from a Kerr
metric black hole was obtained for anisotropic dark energy stars. We observe
that dark energy stars with higher anisotropic strength tend to approach the
Kerr solution more closely. We report that our results have considerable
agreement with various astrophysical observational measurements.

††preprint:

##  I Introduction

Compact stars are extremely dense stellar bodies, whose internal composition
is not well understood at present. In this regard, there have been many
studies assuming various internal matter such as normal nuclear matter,
hyperons, quarks, Bose-Einstein condensates, dark matter, dark energy and so
on. Among these, compact objects made of elusive dark energy have recently
attracted interest Chapline (2004); Lobo (2006); Chan  _et al._ (2009); Ghezzi
(2011); Yazadjiev (2011); Rahaman  _et al._ (2012); Beltracchi and Gondolo
(2019); Sakti and Sulaksono (2021); Abellán  _et al._ (2023); Panotopoulos
_et al._ (2020, 2021); Pretel (2023); Pretel  _et al._ (2024); Jyothilakshmi
_et al._ (2024). Various observations suggest the presence of a hidden
component called dark energy, that leads to the accelerated expansion of
Universe. Some of the models of dark energy are quintessence, K-essence,
tachyon field, cosmological constant, phantom field, dilatonic field,
Chaplygin gas etc. Detailed reviews on various such models of dark energy can
be seen in Refs. Copeland  _et al._ (2006); Bamba  _et al._ (2012). In 2004,
Chapline Chapline (2004) was the first to propose the idea of a dark energy
star, which was considered as an alternative to astrophysically observed black
holes. Later, various models of dark energy stars were introduced that include
anisotropy effects Chan  _et al._ (2009), neutron gas Ghezzi (2011), and a
mixture of baryonic matter and phantom scalar field Yazadjiev (2011). Further,
a spherical system that collapses from a state of positive pressure to a state
with a dark energy core Beltracchi and Gondolo (2019) and the stability of a
dark energy star with a phantom field Sakti and Sulaksono (2021) were studied.
Analyses of radial pulsations in dark energy stars Panotopoulos  _et al._
(2020) and neutron stars with dark energy core Pretel  _et al._ (2024) also
exist. Recently, the non-radial oscillations in dark energy stars were also
considered Jyothilakshmi  _et al._ (2024).

In general, the stellar fluid is assumed to be isotropic, while the fact that
compact stars have high densities and strong gravity suggests the possibility
of pressure anisotropy within them. The origin of this anisotropy might be due
to the presence of rotation, strong electric and magnetic fields, superfluid
cores, phase transition, etc. Anisotropy in compact stars was first proposed
by Ruderman in 1972 Ruderman (1972) and two years later, Bowers and Liang
Bowers and Liang (1974) constructed a model for anisotropy and obtained the
stellar structure equations. Later, various other models of anisotropy such as
Quasi-local Horvat  _et al._ (2011), Herrera-Barreto Herrera and Barreto
(2013), and covariant Raposo  _et al._ (2019) were used to obtain different
aspects of compact stars. A review on various relativistic models of
anisotropic compact stars can be seen in Ref. Kumar and Bharti (2022).

Lately, the effect of anisotropy on various astrophysical scenarios has drawn
great interest Silva  _et al._ (2015); Folomeev and Dzhunushaliev (2015); Deb
_et al._ (2017); Maurya  _et al._ (2017); Pretel (2020); Becerra  _et al._
(2024). The tidal deformability of an anisotropic compact star was studied in
Ref. Biswas and Bose (2019). Further, the effect of anisotropy on radial
Horvat  _et al._ (2011) and non-radial Doneva and Yazadjiev (2012); Curi  _et
al._ (2022) oscillations were also analysed. In dark energy stars, the effect
of anisotropy was considered within Newtonian approximation by using the
generalised Chaplygin model in Ref. Abellán  _et al._ (2023). Recently, the
radial stability, moment of inertia and tidal deformability of anisotropic
dark energy stars were analysed using proper general relativistic treatment
Pretel (2023). Further, in our previous work, it was found that the distinct
behaviour of non-radial $f$-mode spectra of anisotropic dark energy stars may
help in easy detection by future detectors Jyothilakshmi  _et al._ (2024). In
the present work, we intend to study the effect of rotation on properties of
anisotropic dark energy stars.

The effect of rotation on stellar structure of compact stars has been studied
using different general relativistic methods such as Hartle-Thorne Hartle
(1967); Hartle and Thorne (1968), Butterworth-Ipser Butterworth and Ipser
(1976) and Komatsu-Eriguchi-Hachisu Komatsu  _et al._ (1989a, b) by various
physicists in last few decades Kojima (1992); Glendenning and Weber (1992);
Yoshida and Kojima (1997); Friedman and Morsink (1998); Gupta  _et al._
(1998); Rezzolla  _et al._ (2001); Stergioulas (2003); Berti  _et al._ (2005);
Jha  _et al._ (2008); Sotani (2010); Laskos-Patkos and Moustakidis (2023).
Among these, the Hartle-Thorne slow rotation mechanism is widely used in
several studies of different types of compact objects. This formalism gives
various attributes such as the mass, angular momentum and quadrupole moment of
the rotating stars upto second order in angular velocity $\Omega$. Many
investigations have used this formalism in the study of gravitational wave
sensitive $r$-modes Nayyar and Owen (2006); Jha  _et al._ (2010);
Jyothilakshmi  _et al._ (2022); Gittins and Andersson (2023). In Ref. Urbanec
_et al._ (2013), this method was used to analyse the quadrupole moments of
neutron stars and strange stars. The stellar structure of slowly rotating
neutron stars within the scalar tensor Sotani (2010) and $f(R,T)$ Murshid and
Kalam (2023) theories of gravity were also looked in. Recently, the properties
of slowly rotating isotropic exotic compact objects like Bose-Einstein
condensate stars at finite temperature Aswathi  _et al._ (2023), dark matter
admixture neutron stars Cronin  _et al._ (2023) and dark energy stars
Panotopoulos  _et al._ (2021) were also studied using the Hartle-Thorne
formalism. Now, coming to anisotropic compact objects, different aspects of
the structure of slowly rotating neutron stars were studied in Ref. Pattersons
and Sulaksono (2021). Further, tidal deformability and moment of inertia
relation for an anisotropic neutron star was investigated in Ref. Das (2022).
The quadrupole moments of neutron stars and strange stars were also studied
using the Hartle-Thorne formalism and it was found that both neutron and
strange stars show entirely different behaviour Urbanec  _et al._ (2013).
Inclusion of the effect of rotation in anisotropic dark energy star models
will be of interest and we aim to take up this study in the present paper.

Using the modified Chaplygin prescription for dark energy, we study the
stellar structure of slowly rotating isotropic and anisotropic dark energy
stars and obtain various parameters such as mass, angular momentum, moment of
inertia, quadrupole moment, and tidal deformability. The anisotropy is
included through the Bowers-Liang model and slow rotation via Hartle-Thorne
formalism.

The manuscript is organised as follows: In Sec. II, we discuss the modified
Chaplygin EoS for dark energy stars used in our analysis. Next, we present the
modified Hartle-Thorne formalism for anisotropic compact stars in Sec. III.
Finally, we discuss the results in Sec. IV and present the conclusions drawn
in Sec. V.
Notations and conventions: Through out this paper, we take Newton’s universal
gravitational constant $G$ and velocity of light in vaccum $c$ to be $G=c=1$
and follow the metric convention $g_{\mu\nu}=\textrm{diag}(-1,1,1,1)$. M⊙
denotes mass of the Sun.

##  II Chaplygin model of Dark Energy

In this section, we present the equation of state used to describe dark energy
in our analysis. The Chaplygin gas is one of the well known fluid prescription
for dark energy, which could explain the unification of dark matter and dark
energy Kamenshchik  _et al._ (2001); Bilic  _et al._ (2002); Bento  _et al._
(2002); Gorini  _et al._ (2003); Zhang  _et al._ (2006); Xu  _et al._ (2012).
This model assumes universe is filled with the particular fluid form of the
dark energy. For our analysis we use a modified version of the Chaplygin
prescription Pourhassan (2013); Saadat and Pourhassan (2013), that takes the
following form Kahya and Pourhassan (2015)

$\displaystyle p=A^{2}\rho-\frac{B^{2}}{\rho}.$ (1)

Here, $p$ is the pressure of the fluid, $\rho$ is the energy density and $A$
(no unit) and $B$ (units of energy density) are positive constants. It must be
noted that as the pressure vanishes at the surface of the star, the energy
density there takes becomes $\rho_{s}=B/A$. This along with the causality
condition ($v_{s}^{2}=dp_{r}/d\rho<1$) puts constraints on the values of the
constant ($A^{2}<0.5$) Pretel (2023). In the present analysis, following
previous studies Panotopoulos  _et al._ (2021, 2020); Pretel (2023), we
consider the three sets of values for the constants as given in Table 1.

| Set I | Set II | Set III
---|---|---|---
A | $\sqrt{0.4}$ | $\sqrt{0.425}$ | $\sqrt{0.45}$
B ($km^{-2}$) | $0.23\times 10^{-3}$ | $0.215\times 10^{-3}$ | $0.2\times 10^{-3}$
Table 1: The values of constants $A$ and $B$ of modified Chaplygin equation of
state under consideration. Figure 1: Equation of state of dark energy star
that follows the modified Chaplygin prescription, for three parameter sets
(See Table 1).

In Fig. 1, we plot the dark energy equation of state (EoS) for the three sets.
We can see that as we increase (decrease) the value of $A$ ($B$), i.e., moving
from Set I to Set III, the resulting EoS becomes more and more stiffer.

##  III Slowly rotating anisotropic stars

In this section, we present the slowly rotating stellar structure solutions
with pressure anisotropy Pattersons and Sulaksono (2021) obtained by modifying
the Hartle-Thorne formalism Hartle (1967); Hartle and Thorne (1968).
Anisotropy in pressure means the pressure in radial and transverse directions
are different. The stress-energy tensor $T_{\mu\nu}$ for an anisotropic fluid
can be given as

$\displaystyle T^{\mu}_{\nu}$ $\displaystyle=\rho
u^{\mu}u_{\nu}+q\delta^{\mu}_{\nu}+\sigma k^{\mu}k_{\nu};$ (2)

where, $\sigma=p-q$ is the anisotropy pressure, $p$ is the radial pressure,
$q$ is the tangential pressure, $u^{\mu}$ is the four velocity of the fluid,
and $k_{\nu}$ denoting the radial vector. The four-vectors obeys the relations
$u_{\mu}u^{\mu}=-1$, $k_{\mu}k^{\mu}=1$, and $u^{\mu}k_{\mu}=0$. For modelling
anisotropy we use the Bowers-Liang model given by Bowers and Liang (1974),

$\displaystyle\sigma=-\lambda_{BL}\frac{r^{3}}{3}\left(\rho+3p\right)\left(\frac{\rho+p}{r-2m}\right),$
(3)

with $\lambda_{BL}$ describing the strength of anisotropy. The metric for a
spherically symmetric static star in Schwarzschild coordinates,
($t,\,r,\,\theta,\,\phi$) can be written as

$\displaystyle ds^{2}$
$\displaystyle=-e^{2\nu}dt^{2}+e^{\Lambda}dr^{2}+r^{2}\left(d\theta^{2}+\sin^{2}\theta
d\phi^{2}\right).$ (4)

Here, $\nu(r)$ and $\Lambda(r)$ are the metric functions. Solving the Einstein
field equations for the above metric for an anisotropic fluid results in the
modified Tolman-Oppenheimer-Volkoff (TOV) equations describing the stellar
structure of the static system, which are given as Tolman (1939); Oppenheimer
and Volkoff (1939); Bowers and Liang (1974)

$\displaystyle\frac{dp}{dr}$ $\displaystyle=-\frac{(\rho+p)(m+4\pi
r^{3}p)}{r^{2}(1-2m/r)}-\frac{2\sigma}{r},$ (5a) $\displaystyle\frac{dm}{dr}$
$\displaystyle=4\pi r^{2}\rho.$ (5b)

These coupled differential equations reduce to the well known isotropic case
(TOV equations), if the anisotropic parameter $\sigma$ is set to zero. For a
given EoS, the Eqs. (5a) and (5b) are integrated from the center to the
surface of star where the pressure and mass towards the center are:
$p(r=0)=p(\rho_{c})$ and $m(r=0)=0$. Also, towards the surface of the star,
pressure approaches to zero and mass of the star is obtained as $M=m(r=R)$.
Further, we can obtain different masses and radii for all possible values of
central densities $\rho_{c}$.

The pressure $p(r)$ and mass $m(r)$ profiles obtained thus for the static case
are used to obtain the solution for a slowly rotating anisotropic star. Here,
we make use of the Hartle-Thorne metric Hartle (1967); Hartle and Thorne
(1968), which is a small perturbation on the metric of a static star:

$\displaystyle ds^{2}=$ $\displaystyle-e^{2\nu}[1+2(h_{0}+h_{2}P_{2})]dt^{2}$
$\displaystyle+r\left[1+2(m_{0}+m_{2}P_{2})(r-2m)^{-1}\right]/\left(r-2m\right)dr^{2}$
$\displaystyle+r^{2}\left[1+2(v_{2}-h_{2})P_{2}\right]\left[d\theta^{2}+\sin^{2}\theta(d\phi-\omega
dt)^{2}\right]$ $\displaystyle+O(\Omega^{3}).$ (6)

Here, $P_{2}=P_{2}(\cos\theta)$ is the second order Legendre polynomial and
the perturbative terms $h_{0},\,m_{0},\,h_{2},\,m_{2},\,p_{2},$ and $v_{2}$
are functions of $r$ and are proportional to the square of angular velocity of
the star $\Omega^{2}(r)$. The quantity $\omega$ is the angular velocity of the
local inertial frame, given by $\omega=\Omega-\bar{\omega}$. For an
anisotropic star, the angular velocity relative to the local inertial frame
$\bar{\omega}$ is obtained by solving the following second order differential
equation Pattersons and Sulaksono (2021)

$\frac{1}{r^{4}}\frac{d}{dr}\left(r^{4}j\frac{d\bar{\omega}}{dr}\right)+\frac{4}{r}\frac{dj}{dr}\bar{\omega}(1-\frac{\sigma}{\rho+p})=0;$
(7)

where, $j=e^{-\nu}{\left(1-2m/r\right)}^{1/2}$. The above differential
equation is integrated from the center $(r=0)$ to the surface $(r=R)$ of the
star using the boundary conditions: $\bar{\omega}(r=0)=\omega_{c}$ and
$(d\bar{\omega}/dr)_{r=0}=0$, where the value of $\omega_{c}$ is chosen
arbitrarily. The angular momentum $J$ and the angular velocity $\Omega$
corresponding to $\omega_{c}$ are

$J=\frac{1}{6}R^{4}\left(\frac{d\bar{\omega}}{dr}\right)_{r=R},\qquad\Omega=\bar{\omega}(R)+\frac{2J}{R^{3}};$
(8)

and the moment of inertia $I=J/\Omega$ of a slow rotating anisotropic star is
given as

$\displaystyle
I=\frac{8\pi}{3}\int_{0}^{R}\left(\rho+p+\sigma\right)e^{\lambda-\nu}r^{4}\left(\frac{\bar{\omega}}{\Omega}\right)dr.$
(9)

The function $\bar{\omega}(r)$ can be re-scaled to obtain a different value of
angular velocity as:
${\bar{\omega}(r)}_{new}={\bar{\omega}(r)}_{old}\left(\Omega_{new}/\Omega_{old}\right)$.

Now, we proceed to obtain the first ($l=0$) and second ($l=2$) order
perturbation functions. The first order (spherical) deformation is obtained by
solving the mass perturbation factor ($m_{0}$) and the pressure perturbation
factor ($p_{0}^{*}$) equations given by Pattersons and Sulaksono (2021)

$\displaystyle\frac{dm_{0}}{dr}$ $\displaystyle=$ $\displaystyle 4\pi
r^{2}\frac{d\rho}{dp}\left(\rho+p\right)\left(1-\frac{\sigma}{\rho+p}\right)\left(1-\frac{d\sigma}{dp}\right)^{-1}p_{0}^{*}$
(10a) $\displaystyle+$
$\displaystyle\frac{j^{2}r^{4}}{12}\left(\frac{d\bar{\omega}}{dr}\right)^{2}-\frac{r^{3}}{3}\frac{dj^{2}}{dr}\left(1-\frac{\sigma}{\rho+p}\right)\bar{\omega}^{2},$
$\displaystyle\frac{dp_{0}^{*}}{dr}$ $\displaystyle=$
$\displaystyle-\frac{m_{0}(1+8\pi r^{2}p)}{r{(r-2m)}^{2}}-\frac{4\pi
r^{2}\left(\rho+p-\sigma\right)}{(r-2m)(1-d\sigma/dp)}p_{0}^{*}$ (10b)
$\displaystyle+$
$\displaystyle\frac{1}{12}\frac{r^{4}j^{2}}{(r-2m)}{\left(\frac{d\bar{\omega}}{dr}\right)}^{2}+\frac{1}{3}\frac{d}{dr}\left(\frac{r^{3}j^{2}{\bar{\omega}^{2}}}{r-2m}\right).$

The above differential equations are solved from the center to the surface of
the star and obey the conditions that at the center of the star
$m_{0}=p_{0}^{*}=0$. The spherical deformation $\xi_{0}$ is expressed in terms
of the perturbation factor $p_{0}*$:

$\displaystyle\xi_{0}(r)$ $\displaystyle=$ $\displaystyle-
p_{0}^{*}\left(\rho+p\right)\left(1-\frac{\sigma}{\rho+p}\right)\left(\frac{dp}{dr}-\frac{d\sigma}{dr}\right)^{-1}.$
(11)

Further, the change in gravitational mass $\delta M$ is given by

$\delta M=m_{0}(R)+\frac{J^{2}}{R^{3}}.$ (12)

Now, in order to obtain the metric functions $v_{2}$ and $h_{2}$ describing
the second order (quadrupole) deformations, we solve the following
differential equations Hartle and Thorne (1968); Pattersons and Sulaksono
(2021):

$\displaystyle\frac{dv_{2}}{dr}$ $\displaystyle=$
$\displaystyle-2\frac{d\nu}{dr}h_{2}+\left(\frac{1}{r}+\frac{d\nu}{dr}\right)\left[r^{3}\frac{dj^{2}}{dr}\bar{\omega}^{2}\left(\frac{2\sigma}{\rho+p}-\frac{1}{3}\right)\right]$
(13a) $\displaystyle+$
$\displaystyle\left(\frac{1}{r}+\frac{d\nu}{dr}\right)\left[\frac{1}{6}j^{2}r^{4}\left(\frac{d\bar{\omega}}{dr}\right)^{2}\right],$
$\displaystyle\frac{dh_{2}}{dr}$ $\displaystyle=$
$\displaystyle-2\frac{d\nu}{dr}h_{2}+\frac{8\pi
r(\rho+p)}{r-2m}\left(2\frac{d\nu}{dr}\right)^{-1}h_{2}\left(1-\frac{\sigma}{\rho+p}\right)$
(13b) $\displaystyle\times$
$\displaystyle\left(1-\frac{d\sigma}{dp}\right)^{-1}-\frac{r}{r-2m}\left(2\frac{d\nu}{dr}\right)^{-1}\frac{4m}{r^{3}}h_{2}$
$\displaystyle+$
$\displaystyle\frac{r^{3}j^{2}}{6}\left(\frac{d\bar{\omega}}{dr}\right)^{2}\Bigg{[}\frac{d\nu}{dr}r-\frac{1}{r-2m}\left(2\frac{d\nu}{dr}\right)^{-1}\Bigg{]}$
$\displaystyle-$
$\displaystyle\frac{4v_{2}}{r(r-2m)}\left(2\frac{d\nu}{dr}\right)^{-1}-\frac{r^{3}\bar{\omega}^{2}}{3}\frac{d\nu}{dr}\frac{dj^{2}}{dr}\bar{\omega}^{2}\left(1-\frac{6\sigma}{\rho+p}\right)$
$\displaystyle-$
$\displaystyle\frac{r^{2}\bar{\omega^{2}}}{6(r-2m)}\left(\frac{dj^{2}/dr}{d\nu/dr}\right)\left(1-\frac{\sigma}{\rho+p}\right)\left(1-\frac{d\sigma}{dp}\right)^{-1}.$

The solutions of the coupled differential equations given above must be
regular near the center of the star ($r=0$) and can be expressed as

$\displaystyle h_{2}^{P}$ $\displaystyle\to$
$\displaystyle\mathcal{A}r^{2},\qquad v_{2}^{P}\to\mathcal{B}r^{4};$ (14)

where constants $\mathcal{A}$ and $\mathcal{B}$ are related by

$\mathcal{B}+\frac{2\pi}{3}(\rho_{c}+3P_{c})\mathcal{A}=-\frac{4\pi}{3}(\rho_{c}+P_{c})(j_{c}\bar{\omega}_{c})^{2}.$
(15)

Here, subscript ’$c$’ is used to denote the center of the star. The particular
solutions $h_{2}^{P}$ and $v_{2}^{P}$ are obtained by integrating Eqs. (13a)
and (13b) from the center to the surface of the star using the conditions
given by Eq. (14). Then, we solve the homogeneous differential equations
Hartle and Thorne (1968)

$\displaystyle\frac{dv_{2}^{H}}{dr}$ $\displaystyle=$
$\displaystyle-2\frac{d\nu}{dr}h_{2}^{H},$ (16a)
$\displaystyle\frac{dh_{2}^{H}}{dr}$ $\displaystyle=$
$\displaystyle-2\frac{d\nu}{dr}h_{2}^{H}-\frac{r}{r-2m}\left(2\frac{d\nu}{dr}\right)^{-1}\frac{4m}{r^{3}}h_{2}^{H}$
(16b) $\displaystyle+$ $\displaystyle\frac{4\pi
r(\rho+p)h_{2}^{H}}{(r-2m)(d\nu/dr)}\left(1-\frac{\sigma}{\rho+p}\right)\left(1-\frac{d\sigma}{dp}\right)^{-1}$
$\displaystyle-$
$\displaystyle\frac{4v_{2}^{H}}{r(r-2m)}\left(2\frac{d\nu}{dr}\right)^{-1}.$

Near the center ($r=0$) of the star these equations obey the following
conditions:

$\displaystyle h_{2}^{H}$ $\displaystyle\to$
$\displaystyle\mathcal{B}^{H}r^{2},\qquad
v_{2}^{H}\to-\frac{2\pi}{3}(\rho_{c}+3P_{c})\mathcal{B}^{H}r^{4}.$ (17)

Here, we take $\mathcal{B}^{H}$ to be unity and then integrate Eqs. (16a) and
(16b) from the center to the surface of the star. The internal solutions of
Eqs. (13a) and (13b) are expressed as a linear combination of both particular
($v_{2}^{P}$ and $h_{2}^{P}$) and homogeneous solutions ($v_{2}^{H}$ and
$h_{2}^{H}$) as

$\displaystyle h_{2}$ $\displaystyle=$ $\displaystyle
h_{2}^{P}+\mathcal{K}_{1}h_{2}^{H},$ (18) $\displaystyle v_{2}$
$\displaystyle=$ $\displaystyle v_{2}^{P}+\mathcal{K}_{1}v_{2}^{H};$ (19)

where $\mathcal{K}_{1}$ is a constant. Outside the star, $h_{2}$ and $v_{2}$
take the form

$\displaystyle h_{2}$ $\displaystyle=$ $\displaystyle
J^{2}\left(\frac{1}{mr^{3}}+\frac{1}{r^{4}}\right)+\mathcal{K}_{2}\mathcal{Q}_{2}^{2}\left(\frac{r}{m}-1\right),$
(20) $\displaystyle v_{2}$ $\displaystyle=$
$\displaystyle-\frac{J^{2}}{r^{4}}+\mathcal{K}_{2}\frac{2m}{[r(r-2m)]^{1/2}}\mathcal{Q}_{2}^{1}\left(\frac{r}{m}-1\right);$
(21)

where $\mathcal{K}_{2}$ is a constant and the $\mathcal{Q}_{a}^{b}$ are
associated Legendre functions of the second kind. The constants
$\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ can then be obtained by matching the
internal values for $v_{2}$ and $h_{2}$ to the external values at the surface.
Finally, we obtain the mass quadrupole moment $Q$ of a rotating star given by

$Q=\frac{8}{5}\mathcal{K}_{2}M^{3}+\frac{J^{2}}{M}.$ (22)

The quadrupole moment $Q$ can be written with respect to the Kerr solution as
a dimensionless quantity, $\bar{q}=QM/J^{2}$ and can be used to describe the
deviation of the Hartle-Thorne metric from the Kerr black hole metric, for
which the Kerr factor tends to unity.

Further, we proceed to calculate the mass and radius of the star under
rotation by obtaining the quadrupole deformation $\xi_{2}$, which is expressed
as

$\displaystyle\xi_{2}(r)$ $\displaystyle=$ $\displaystyle-
p_{2}\left(\rho+p-\sigma\right)\left(\frac{dp}{dr}-\frac{d\sigma}{dr}\right)^{-1};$
(23)

where, $p_{2}=-(h_{2}+\frac{1}{3}e^{-2\nu}r^{2}\bar{\omega}^{2})$ is the
quadrupole pressure perturbation factor. Now, the mass ($M_{rot}$) and radius
($R_{rot}$) of a slowly rotating star in the Hartle-Thorne formalism are given
by

$\displaystyle M_{rot}$ $\displaystyle=$ $\displaystyle
M+m_{0}(R)+\frac{J^{2}}{R^{3}},$ (24a) $\displaystyle R_{rot}$
$\displaystyle=$ $\displaystyle R+\xi(r,\theta)=R+\xi_{0}(R)+\xi_{2}(R)P_{2}.$
(24b)

Here, $M$ and $R$ are the mass and radius of a static star obtained from TOV
equations for a given central density. We note that, towards the pole and
equator of the star, the values of $\theta$ are $0$ and $\pi$ respectively.
Therefore, the polar and equatorial radii are defined respectively as

$\displaystyle R_{p}$ $\displaystyle=$ $\displaystyle
R+\xi_{0}(R)+\xi_{2}(R),$ (25) $\displaystyle R_{e}$ $\displaystyle=$
$\displaystyle R+\xi_{0}(R)-\xi_{2}(R)/2.$ (26)

The expressions for various stellar profiles, such as energy density
($\rho_{r}$) and radial ($p_{r}$), tangential ($q_{r}$) and anisotropic
($\sigma_{r}$) pressures of slowly rotating anisotropic stars are given
respectively as

$\displaystyle\rho_{r}$ $\displaystyle=$
$\displaystyle\rho-\xi(r,\theta)(d\rho/dr),$ (27a) $\displaystyle p_{r}$
$\displaystyle=$ $\displaystyle p-\xi(r,\theta)(dp/dr),$ (27b) $\displaystyle
q_{r}$ $\displaystyle=$ $\displaystyle q-\xi(r,\theta)(dq/dr),$ (27c)
$\displaystyle\sigma_{r}$ $\displaystyle=$
$\displaystyle\sigma-\xi(r,\theta)(d\sigma/dr).$ (27d)

We make use of this formalism to obtain the stellar configurations of slowly
rotating dark energy stars that obey the modified Chaplygin EoS.

Figure 2: (a) Stellar mass $M$ as a function of equatorial radius $R_{eq}$
with angular velocity $\Omega=0,\,1500$ and $2500$ s-1 and (b) the mass
correction $\delta M$ as a function of central density $\rho_{c}$ with
$\Omega=1500$ s-1 for dark energy stars by varying the anisotropic parameter
$\lambda_{BL}$ from $-2$ to $2$ for EoS Set I (see Table 1).

Figure 3: (a) Angular momentum $J$ as a function of central density $\rho_{c}$
and (b) Moment of inertia $I$ as a function of stellar mass $M$ for an angular
velocity $\Omega=1500\,s^{-1}$ with $\lambda_{BL}$ values ranging from $-2$ to
$2$ for EoS Set I.

Figure 4: (a) The Kerr factor $\bar{q}=QM/J^{2}$ and (b) tidal deformability
$\Lambda$ as a function of stellar mass $M$ of anisotropic dark energy stars
obeying EoS Set I. Figure 5: Mass-radius curves of slowly rotating anisotropic
dark energy stars for angular velocity $\Omega=1500\,s^{-1}$ for the three
different parameter sets discussed in Sec. II (see Table 1) with
$\lambda_{BL}=-2,\,0,$ and $2$. The horizontal bands are observational
measurements from GW190814 events Abbott  _et al._ (2020) and pulsars, PSR
J2215+5135 ($M=2.27_{-0.15}^{+0.17}M_{\odot}$) Linares  _et al._ (2018) and
PSR J0740+6620 ($2.14_{-0.09}^{+0.10}M_{\odot}$ ($68.3\%$ credible)) Cromartie
_et al._ (2019). The observational constraints from GW 170817 event Abbott
_et al._ (2018) are also shown.

Figure 6: (a) Angular momentum $J$ as a function of central density $\rho_{c}$
and (b) Moment of inertia $I$ as a function of stellar mass $M$ for an angular
velocity $\Omega=1500\,s^{-1}$ for the three different parameter sets
discussed in Sec. II by varying $\lambda_{BL}$ from $-2$ to $2$.

Figure 7: (a) Kerr factor ($\bar{q}_{max}$) and (b) tidal deformability
($\Lambda_{max}$) as a function of maximum mass $M_{max}$ for the three
different parameter sets discussed in Sec. II with
$\lambda_{BL}=-2,\,-1,\,0,\,1,\,2$.

##  IV Results and discussions

Here, we present the stellar properties of slowly rotating anisotropic dark
energy stars that obey the modified Chaplygin EoS given by Eq. (1), for three
different parameter sets given in Table 1. In our analysis, the effect of
anisotropy is incorporated using the Bowers-Liang model. We follow the
modified Hartle-Thorne formalism discussed in Sec. III to obtain the mass and
radius of rotating anisotropic dark energy stars. First, we numerically obtain
the solutions for static case by solving the coupled differential equations,
Eqs. (5a) and (5b). These solutions are then used to obtain the stellar
properties of slowly rotating dark energy stars by numerically integrating the
differential equations corresponding to first (Eqs. (10a) and (10b)) and
second (Eqs. (13a) and (13b)) order perturbations. In all the plots, we mark
the maximum mass points using dots.

In Fig. 2, we plot the mass of anisotropic dark energy stars as a function of
stellar radius for different angular velocities $\Omega=(1500,\,2500)$ s-1. We
vary the strength of anisotropy, $\lambda_{BL}$ from $-2$ to $2$ for equation
of state (EoS) Set I parameters discussed in Sec. II. The stellar structure of
a static dark energy star shows an overall increment (decrement) if we
increase (decrease) the value of $\lambda_{BL}$ from zero. This is inline with
the previous studies Pretel (2023); Jyothilakshmi  _et al._ (2024). With
rotation, the stellar structure shows an overall increment in masses and
radii; while only a minimal increment is found in the maximum masses and
corresponding radii. The equatorial radii corresponding to a $1.5\,M_{\odot}$
dark energy star rotating with angular velocties $\Omega=1500\,(2500)$ s-1 are
$10.85\,(10.94)$, $11.06\,(11.17)$, and $11.25\,(11.44)$ km for
$\lambda_{BL}=-2,\,0,$ and $2$ respectively. The corresponding values of
central density are $7.6,\,6.4$ and $5.7$ $\times 10^{14}$ g cm-3
respectively. The maximum masses (corresponding radii) of rotating dark energy
stars show only a minimal deviation from the static case ($\Omega=0$) and
their values are approximately $2.07$ M⊙ ($11.08$ km), $2.48$ M⊙ ($11.86$ km)
and $3.09$ M⊙ ($12.91$ km) respectively for $\lambda_{BL}=-2,\,0$ and $2$. We
find that the maximum masses and corresponding radii increase (decrease) for a
positive (negative) deviation of $\lambda_{BL}$ from zero (isotropic case), as
observed for the static case Jyothilakshmi  _et al._ (2024).

Next, we plot the mass correction $\delta M$ due to rotation as a function of
central density $\rho_{c}$ for an anisotropic dark energy star by varying
$\lambda_{BL}$ from $-2$ to $2$ in Fig. 2. For a fixed value of
$\lambda_{BL}$, the $\delta M$ value shows a gradual increase with an increase
in $\rho_{c}$ until it attains a certain value and when $\rho_{c}$ is
increased further, $\delta M$ remains almost constant for profiles with
$\lambda_{BL}\leq 0$ and decreases gradually for profiles with
$\lambda_{BL}>0$. A significant increase of mass is found for a dark energy
star rotating with an angular velocity ($\Omega=1500$ s-1). For a central
density $\rho_{c}=8\times 10^{14}$ gcm-3, the values of mass deformation
$\delta M$ with $\lambda_{BL}=-2,\,-1,\,0,\,1,\,$ and $2$ are
($3.07,\,3.84,\,4.90,\,6.37,$ and $8.45$) $\times 10^{-3}$ M⊙ respectively. We
find that the effect of rotation causes high (low) deformation for a positive
(negative) increment of $\lambda_{BL}$. The values of mass correction $\delta
M$ corresponding to the maximum mass configuration of dark energy stars are
($3.93,\,4.60,\,5.41,\,6.65,\,8.11$) $\times 10^{-3}$ M⊙ for
$\lambda_{BL}=(-2,\,-1,\,0,\,1,\,2)$ respectively. The corresponding central
density $\rho_{c}$ values are ($2.18,\,1.91,\,1.73,\,1.42,\,1.25$) $\times
10^{15}$ g cm-3 respectively. We note that the stellar configurations with
higher anisotropy values attain the maximum mass for a smaller value of
$\rho_{c}$, which reduces the possible range of $\rho_{c}$ values that gives
stable dark energy profiles. We find that the inclusion of anisotropy results
in a substantial change in the mass of a slowly rotating anisotropic dark
energy star.

In Fig. 3, we plot the angular momentum $J$ as a function of central density
$\rho_{c}$ for rotating anisotropic dark energy stars with an angular velocity
$\Omega=1500$ s-1. The values of angular momentum corresponding to the maximum
mass ($J_{max}$) for $\lambda_{BL}=-2,\,-1,\,0,\,1,\,$ and $2$ are
($3.61,\,4.42,\,5.47,\,7.06$, and $9.26$) $\times 10^{41}$ kg m2 s-1
respectively. We find that the values of angular momentum increase (decrease)
when the $\lambda_{BL}$ value is increased (decreased) from zero. In Fig. 3,
we plot the moment of inertia $I$ as a function of stellar mass for a rotating
anisotropic dark energy star with an angular velocity $\Omega=1500$ s-1. We
find that the deviation of $I$ due to anisotropy is more prominent in the high
mass region, while it shows only a minimal change in the low mass region. The
values of moment of inertia corresponding to the maximum mass ($I_{max}$) for
dark energy stars are ($2.40,\,2.94,\,3.64,\,4.69,$ and $6.16$) $\times
10^{38}$ kg m2 with $\lambda_{BL}=-2,\,-1,\,0,\,1,\,$ and $2$ respectively.

We numerically obtain the quadrupole moment $Q$ using Eq. (22). In Fig. 4, we
plot the dimensionless Kerr factor $\bar{q}=QM/J^{2}$ as a function of the
stellar mass $M$ for Set I EoS by varying $\lambda_{BL}$ from $-2$ to $2$. We
find that the Kerr factor $\bar{q}$ has a high value in the low mass region
and as the mass increases, the $\bar{q}$ value decreases and approaches unity.
The values of quadrupole moment corresponding to the maximum stellar mass
($\bar{q}_{max}$) are $2.01,\,1.88,\,1.74,\,1.65,$ and $1.53$ respectively for
$\lambda_{BL}=-2,\,-1,\,0,\,1,$ and $2$. We find that the $\bar{q}_{max}$
corresponding to the positive (negative) values of $\lambda_{BL}$ tends more
(less) towards the Kerr solution. The $\bar{q}_{max}$ values lie between
$2-1.5$ for $\lambda_{BL}$ values ranging from $-2$ to $2$, which is almost
similar to the range obtained for isotropic neutron and strange stars in Ref.
Urbanec  _et al._ (2013).

Next, we plot the tidal deformability $\Lambda$ as a function of stellar mass
$M$ for anisotropic dark energy stars by varying $\lambda_{BL}$ from $-2$ to
$2$ in Fig. 4. The dimensionless tidal deformability is given by
$\Lambda=2k_{2}C^{-5}/3$, where $C=M/R$ is the compactness of the star and
$k_{2}$ is the tidal Love number. We obtain the Love number $k_{2}$ by
following the prescription given in Refs. Hinderer (2008); Hinderer  _et al._
(2010). The $\Lambda$ values show only a minimal variation from the isotropic
case in the low mass region and the deviation is prominent in the higher mass
region. We also note that the $\Lambda$ values are high (low) for positive
(negative) values of $\lambda_{BL}$. The values of $\Lambda$ corresponding to
$1.40$ M⊙ are $49,\,53,\,59,\,60,$ and $76$ for
$\lambda_{BL}=-2,\,-1,\,0,\,1,$ and $2$ respectively. These values are in
agreement with the limit provided by GW 170817 ($\Lambda_{1.4}\leq 800$)
Abbott  _et al._ (2017).

We now proceed to study the impact of EoS parameters on rotation and
anisotropy in the system by varying the positive constants $A$ and $B$ (see
Table. 1) of the modified Chaplygin EoS. We plot the mass-radius relation of a
dark energy star rotating with an angular velocity $\Omega=1500\;s^{-1}$ for
three different sets of $A$ and $B$ values by varying the anisotropy parameter
$\lambda_{BL}$ from $-2$ to $+2$ in Fig. 5. The maximum mass of dark energy
stars with $\lambda_{BL}=(-2,0,2)$ are ($2.065,\,2.480,\,3.077$),
($2.246,\,2.694,\,3.337$) and ($2.418,\,2.895,\,3.572$) M⊙ for Sets I, II, and
III respectively. The equatorial radii corresponding to them are
($11.02,\,11.78,\,12.89$), ($11.76,\,12.64,\,13.76$) and
($12.44,\,13.34,\,14.53$) km respectively. We note that for different values
of $\lambda_{BL}$, Set III gives the highest maximum mass, since a stiffer EoS
results in higher maximum mass.

In Fig. 5, we also compare our results with some of the recent observational
limits obtained from gravitational wave events (GW190814 Abbott  _et al._
(2020), GW170817 Abbott  _et al._ (2018)) and milli-second pulsars (PSR
J2215+5135 ($M=2.27_{-0.15}^{+0.17}M_{\odot}$) Linares  _et al._ (2018) and
PSR J0740+6620 ($2.14_{-0.09}^{+0.10}M_{\odot}$ ) Cromartie  _et al._ (2019)).
We find that our results for rotating anisotropic dark energy stars for all
the three sets of EoS parameters lie well within the bound given by the
GW170817. The maximum masses of $\lambda_{BL}=-2$ are also consistent with the
PSR J2215+5135 and PSR J0740+6620. Further, the masses of dark energy stars
with $\lambda_{BL}=2$ obey the limit imposed by the GW190814 for all three
parameter sets considered, while for stars with $\lambda_{BL}=0$, only set II
and III obey this limit.

In Fig. 6, we plot the angular momentum corresponding to the maximum mass
($J_{max}$) and analogous central density $\rho_{c}$ of a slowly rotating dark
energy star with angular velocity $\Omega=1500\,s^{-1}$ by varying the
$\lambda_{BL}$ for three different parameter sets. We find that the $J_{max}$
value increases when we increase the $\lambda_{BL}$ value from $-2$ to $2$.
The central density corresponding to the maximum mass is highest for
$\lambda_{BL}=-2$ and lowest for $\lambda_{BL}=2$. Therefore, for positive
increament of $\lambda_{BL}$ value the star attains the maximum mass
configuration with comparitively smaller value of central density. The values
of $J_{max}$ for Sets I, II, and III are ($3.61$, $4.42$, $5.48$, $7.06$,
$9.26$), ($4.50$, $5.54$, $6.92$, $8.77$, $11.60$) and ($5.49$, $6.78$,
$8.38$, $10.65$, $14.01$) $\times 10^{41}$ kg m2 s-1 respectively with
$\lambda_{BL}=(-2,\,-1,\,0,\,1,\,2)$. The central densities corresponding to
the maximum masses are ($2.18$, $1.91$, $1.73$, $1.42$, $1.22$), ($2.01$,
$1.69$, $1.45$, $1.31$, $1.07$) and ($1.79$, $1.47$, $1.34$, $1.18$, $0.97$)
$\times 10^{15}$ g cm-3 respectively.

We plot the moment of inertia $I_{max}$ as a function of maximum mass by
varying $\lambda_{BL}$ of dark energy stars rotating with an angular velocity
$\Omega=1500\;s^{-1}$ for different EoS parameter sets in Fig. 6. The values
of $I_{max}$ for Sets I, II, and III are ($2.40,\,2.94,\,3.64,\,4.70,\,6.16$),
($2.99,\,3.68,\,4.60,\,5.83,\,7.71$) and ($3.65,\,4.51,\,5.58,\,7.08,\,9.32$)
$\times 10^{38}$ kg m2 respectively with $\lambda_{BL}=(-2,\,-1,\,0,\,1,\,2)$.
We find that the values of moment of inertia for anisotropic dark energy stars
with $1.5\,M_{\odot}$ lie in the range of $(1.7-2.1)\times 10^{38}$ kg m2. We
also note that, EoS Set III gives the highest value for $J_{max}$ and
$I_{max}$. We note that the order of magnitude of values of $J$ and $I$ for
dark energy stars are in agreement with the results given in Refs.
Panotopoulos  _et al._ (2021); Pretel (2023).

Further, in Fig. 7, we plot the Kerr factor corresponding to the maximum mass
($\bar{q}_{max}$) for different parameter sets by varying $\lambda_{BL}$. The
values of $\bar{q}_{max}$ for Sets I, II, and III are ($2.01$, $1.88$, $1.74$,
$1.65$, $1.53$), ($1.9$, $1.81$, $1.70$, $1.58$, $1.50$) and ($1.84$, $1.75$,
$1.64$, $1.53$, $1.47$) respectively with
$\lambda_{BL}=(-2,\,-1,\,0,\,1,\,2)$. The value of $\bar{q}_{max}$ is lowest
for $\lambda_{BL}=2$ for all three sets of parameters discussed here. We also
plot the tidal deformability corresponding to the maximum mass
($\Lambda_{max}$) by varying $\lambda_{BL}$ for different parameter sets in
Fig. 7. The values of $\Lambda_{max}$ for Sets I, II, and III are ($5.95$,
$4.11$, $2.71$, $1.63$, $0.96$), ($5.43$, $3.61$, $2.38$, $1.45$, $0.82$) and
($4.84$, $3.26$, $2.15$, $1.33$, $0.73$) respectively with
$\lambda_{BL}=(-2,\,-1,\,0,\,1,\,2)$.

##  V Summary and Conclusions

We have studied the global properties of slowly rotating isotropic and
anisotropic dark energy stars obeying modified Chaplygin EoS. We have used the
general relativistic Hartle-Thorne slow rotation approximation method for
incorporating the effects of rotation. By including both the monopole and
quadrupole deformations, we carried out a complete analysis of slowly rotating
dark energy stars. We investigated and quantified the mass-radius relation,
mass correction, angular momentum, moment of inertia, quadrupole moment and
tidal deformability of rotating anisotropic dark energy stars. For our
analysis, we made use of three different EoS parameter sets and varied
anisotropy parameter $\lambda_{BL}$ from $-2$ to $+2$.

Firstly, we studied the stellar configurations for different angular
velocities by varying the strength of anisotropy $\lambda_{BL}$ for a single
set of EoS parameters, $A$ and $B$. We found that for a fixed value of
$\lambda_{BL}$, the effect of rotation on maximum mass and corresponding
radius is minimal. However, the overall structure of a rotating dark energy
star shows significant deviation from the static case. We also obtained the
mass correction as a function of central density by varying the values of
$\lambda_{BL}$. It was found that the mass correction increases (decreases)
for a positive (negative) deviation from the isotropic case
($\lambda_{BL}=0$). We report that the mass correction due to anisotropy is
high compared to the correction obtained by rotation. Also, the maximum mass
occurs at smaller central densities for more positive values of
$\lambda_{BL}$. Further, we have analysed the angular momentum and moment of
inertia for the system. The angular momentum of the star shows an overall
increment (decrement) for positive (negative) values of $\lambda_{BL}$. It was
observed that the effect of anisotropy on moment of inertia is more visible in
high mass regions. We also studied the quadrupole deformation and obtained the
quadrupole moments with respect to Kerr solution. It was found that the dark
energy stars with higher anisotropy value approach more towards the Kerr
solution. Further, the tidal deformability of the dark energy star was studied
by varying $\lambda_{BL}$ and our analysis shows that effect of anisotropy is
prominent in the high mass region. The obtained tidal deformability values are
consistent with the constraints set by the GW170817 event.

Next, we have studied the stellar properties by varying the EoS parameters.
With a stiffer EoS, we obtained stellar configurations with higher maximum
masses and corresponding equatorial radii, for any fixed $\lambda_{BL}$ value.
We have also compared our results with various astrophysical observations of
milli-second pulsars (PSR J2215+5135 and PSR J0740+6620) and GW events
(GW190814, GW170817) and considerable agreement was found. The effect of EoS
parameters was studied on the angular momentum, moment of inertia, quadrupole
moment and tidal deformability. It was found that the values of Kerr factor
for maximum mass profiles decrease with the stiffness of EoS and lie in the
range of $1.47-2.01$, which could be well approximated by the Kerr metric.

## Acknowledgements

L. J. N. acknowledges the Department of Science and Technology, Govt. of India
for the INSPIRE Fellowship.

## References

  * Chapline (2004) G. Chapline, eConf C041213, 0205 (2004), arXiv:astro-ph/0503200 .
  * Lobo (2006) F. S. N. Lobo, Class. Quant. Grav. 23, 1525 (2006), arXiv:gr-qc/0508115 .
  * Chan  _et al._ (2009) R. Chan, M. F. A. da Silva, and J. F. Villas da Rocha, Mod. Phys. Lett. A 24, 1137 (2009), arXiv:0803.2508 [gr-qc] .
  * Ghezzi (2011) C. R. Ghezzi, Astrophys. Space Sci. 333, 437 (2011), arXiv:0908.0779 [gr-qc] .
  * Yazadjiev (2011) S. S. Yazadjiev, Phys. Rev. D 83, 127501 (2011), arXiv:1104.1865 [gr-qc] .
  * Rahaman  _et al._ (2012) F. Rahaman, R. Maulick, A. K. Yadav, S. Ray, and R. Sharma, Gen. Rel. Grav. 44, 107 (2012), arXiv:1102.1382 [gr-qc] .
  * Beltracchi and Gondolo (2019) P. Beltracchi and P. Gondolo, Phys. Rev. D 99, 044037 (2019), arXiv:1810.12400 [gr-qc] .
  * Sakti and Sulaksono (2021) M. F. A. R. Sakti and A. Sulaksono, Phys. Rev. D 103, 084042 (2021), arXiv:2103.15393 [gr-qc] .
  * Abellán  _et al._ (2023) G. Abellán, A. Rincon, and E. Sanchez, Universe 9, 352 (2023), arXiv:2308.12236 [gr-qc] .
  * Panotopoulos  _et al._ (2020) G. Panotopoulos, A. Rincón, and I. Lopes, Eur. Phys. J. Plus 135, 856 (2020), arXiv:2010.09373 [gr-qc] .
  * Panotopoulos  _et al._ (2021) G. Panotopoulos, A. Rincón, and I. Lopes, Phys. Dark Univ. 34, 100885 (2021), arXiv:2109.05619 [gr-qc] .
  * Pretel (2023) J. M. Z. Pretel, Eur. Phys. J. C 83, 26 (2023), arXiv:2301.03504 [gr-qc] .
  * Pretel  _et al._ (2024) J. M. Z. Pretel, M. Dutra, and S. B. Duarte, Phys. Rev. D 109, 023524 (2024), arXiv:2401.01961 [astro-ph.HE] .
  * Jyothilakshmi  _et al._ (2024) O. P. Jyothilakshmi, L. J. Naik, and V. Sreekanth, Eur. Phys. J. C 84, 427 (2024), arXiv:2403.00711 [gr-qc] .
  * Copeland  _et al._ (2006) E. J. Copeland, M. Sami, and S. Tsujikawa, Int. J. Mod. Phys. D 15, 1753 (2006), arXiv:hep-th/0603057 .
  * Bamba  _et al._ (2012) K. Bamba, S. Capozziello, S. Nojiri, and S. D. Odintsov, Astrophys. Space Sci. 342, 155 (2012), arXiv:1205.3421 [gr-qc] .
  * Ruderman (1972) M. Ruderman, Ann. Rev. Astron. Astrophys. 10, 427 (1972).
  * Bowers and Liang (1974) R. L. Bowers and E. P. T. Liang, Astrophys. J. 188, 657 (1974).
  * Horvat  _et al._ (2011) D. Horvat, S. Ilijic, and A. Marunovic, Class. Quant. Grav. 28, 025009 (2011), arXiv:1010.0878 [gr-qc] .
  * Herrera and Barreto (2013) L. Herrera and W. Barreto, Phys. Rev. D 88, 084022 (2013), arXiv:1310.1114 [gr-qc] .
  * Raposo  _et al._ (2019) G. Raposo, P. Pani, M. Bezares, C. Palenzuela, and V. Cardoso, Phys. Rev. D 99, 104072 (2019), arXiv:1811.07917 [gr-qc] .
  * Kumar and Bharti (2022) J. Kumar and P. Bharti, New Astronomy Reviews 95, 101662 (2022).
  * Silva  _et al._ (2015) H. O. Silva, C. F. B. Macedo, E. Berti, and L. C. B. Crispino, Class. Quant. Grav. 32, 145008 (2015), arXiv:1411.6286 [gr-qc] .
  * Folomeev and Dzhunushaliev (2015) V. Folomeev and V. Dzhunushaliev, Phys. Rev. D 91, 044040 (2015), arXiv:1501.06275 [gr-qc] .
  * Deb  _et al._ (2017) D. Deb, S. R. Chowdhury, S. Ray, F. Rahaman, and B. K. Guha, Annals Phys. 387, 239 (2017), arXiv:1606.00713 [gr-qc] .
  * Maurya  _et al._ (2017) S. K. Maurya, Y. K. Gupta, and S. Ray, Eur. Phys. J. C 77, 360 (2017), arXiv:1502.01915 [gr-qc] .
  * Pretel (2020) J. M. Z. Pretel, Eur. Phys. J. C 80, 726 (2020), arXiv:2008.05331 [gr-qc] .
  * Becerra  _et al._ (2024) L. M. Becerra, E. A. Becerra-Vergara, and F. D. Lora-Clavijo, Phys. Rev. D 109, 043025 (2024), arXiv:2401.10311 [astro-ph.HE] .
  * Biswas and Bose (2019) B. Biswas and S. Bose, Phys. Rev. D 99, 104002 (2019), arXiv:1903.04956 [gr-qc] .
  * Doneva and Yazadjiev (2012) D. D. Doneva and S. S. Yazadjiev, Phys. Rev. D 85, 124023 (2012), arXiv:1203.3963 [gr-qc] .
  * Curi  _et al._ (2022) E. J. A. Curi, L. B. Castro, C. V. Flores, and C. H. Lenzi, Eur. Phys. J. C 82, 527 (2022), arXiv:2206.09260 [gr-qc] .
  * Hartle (1967) J. B. Hartle, Astrophys. J. 150, 1005 (1967).
  * Hartle and Thorne (1968) J. B. Hartle and K. S. Thorne, Astrophys. J. 153, 807 (1968).
  * Butterworth and Ipser (1976) E. M. Butterworth and J. R. Ipser, Astrophys. J. 204, 200 (1976).
  * Komatsu  _et al._ (1989a) H. Komatsu, Y. Eriguchi, and I. Hachisu, Mon. Not. Roy. Astron. Soc. 237, 355 (1989a).
  * Komatsu  _et al._ (1989b) H. Komatsu, Y. Eriguchi, and I. Hachisu, Monthly Notices of the Royal Astronomical Society 239, 153 (1989b), https://academic.oup.com/mnras/article-pdf/239/1/153/3769884/mnras239-0153.pdf .
  * Kojima (1992) Y. Kojima, Phys. Rev. D 46, 4289 (1992).
  * Glendenning and Weber (1992) N. K. Glendenning and F. Weber, Astrophys. J. 400, 647 (1992).
  * Yoshida and Kojima (1997) S. Yoshida and Y. Kojima, Mon. Not. Roy. Astron. Soc. 289, 117 (1997), arXiv:gr-qc/9705081 .
  * Friedman and Morsink (1998) J. L. Friedman and S. M. Morsink, Astrophys. J. 502, 714 (1998), arXiv:gr-qc/9706073 .
  * Gupta  _et al._ (1998) A. Gupta, A. Mishra, H. Mishra, and A. R. Prasanna, Class. Quant. Grav. 15, 3131 (1998), arXiv:astro-ph/9805146 .
  * Rezzolla  _et al._ (2001) L. Rezzolla, B. J. Ahmedov, and J. C. Miller, Mon. Not. Roy. Astron. Soc. 322, 723 (2001), arXiv:astro-ph/0011316 .
  * Stergioulas (2003) N. Stergioulas, Living Rev. Rel. 6, 3 (2003), arXiv:gr-qc/0302034 .
  * Berti  _et al._ (2005) E. Berti, F. White, A. Maniopoulou, and M. Bruni, Mon. Not. Roy. Astron. Soc. 358, 923 (2005), arXiv:gr-qc/0405146 .
  * Jha  _et al._ (2008) T. K. Jha, H. Mishra, and V. Sreekanth, Phys. Rev. C77, 045801 (2008), arXiv:0710.5392 [nucl-th] .
  * Sotani (2010) H. Sotani, Phys. Rev. D 81, 084006 (2010), arXiv:1003.2575 [astro-ph.HE] .
  * Laskos-Patkos and Moustakidis (2023) P. Laskos-Patkos and C. C. Moustakidis, Phys. Rev. D 107, 123023 (2023), arXiv:2302.14537 [nucl-th] .
  * Nayyar and Owen (2006) M. Nayyar and B. J. Owen, Phys. Rev. D 73, 084001 (2006), arXiv:astro-ph/0512041 .
  * Jha  _et al._ (2010) T. K. Jha, H. Mishra, and V. Sreekanth, Phys. Rev. C 82, 025803 (2010).
  * Jyothilakshmi  _et al._ (2022) O. P. Jyothilakshmi, P. E. S. Krishnan, P. Thakur, V. Sreekanth, and T. K. Jha, Mon. Not. Roy. Astron. Soc. 516, 3381 (2022), arXiv:2208.14436 [astro-ph.HE] .
  * Gittins and Andersson (2023) F. Gittins and N. Andersson, Mon. Not. Roy. Astron. Soc. 521, 3043 (2023), arXiv:2212.04892 [gr-qc] .
  * Urbanec  _et al._ (2013) M. Urbanec, J. C. Miller, and Z. Stuchlik, Mon. Not. Roy. Astron. Soc. 433, 1903 (2013), arXiv:1301.5925 [astro-ph.SR] .
  * Murshid and Kalam (2023) M. Murshid and M. Kalam, (2023), arXiv:2306.13758 [gr-qc] .
  * Aswathi  _et al._ (2023) P. S. Aswathi, P. S. Keerthi, O. P. Jyothilakshmi, L. J. Naik, and V. Sreekanth, Phys. Rev. D 108, 123001 (2023), arXiv:2311.01278 [gr-qc] .
  * Cronin  _et al._ (2023) J. Cronin, X. Zhang, and B. Kain, Phys. Rev. D 108, 103016 (2023), arXiv:2311.07714 [gr-qc] .
  * Pattersons and Sulaksono (2021) M. L. Pattersons and A. Sulaksono, Eur. Phys. J. C 81, 698 (2021).
  * Das (2022) H. C. Das, Phys. Rev. D 106, 103518 (2022), arXiv:2208.12566 [gr-qc] .
  * Kamenshchik  _et al._ (2001) A. Y. Kamenshchik, U. Moschella, and V. Pasquier, Phys. Lett. B 511, 265 (2001), arXiv:gr-qc/0103004 .
  * Bilic  _et al._ (2002) N. Bilic, G. B. Tupper, and R. D. Viollier, Phys. Lett. B 535, 17 (2002), arXiv:astro-ph/0111325 .
  * Bento  _et al._ (2002) M. C. Bento, O. Bertolami, and A. A. Sen, Phys. Rev. D 66, 043507 (2002), arXiv:gr-qc/0202064 .
  * Gorini  _et al._ (2003) V. Gorini, A. Kamenshchik, and U. Moschella, Phys. Rev. D 67, 063509 (2003), arXiv:astro-ph/0209395 .
  * Zhang  _et al._ (2006) X. Zhang, F.-Q. Wu, and J. Zhang, JCAP 01, 003 (2006), arXiv:astro-ph/0411221 .
  * Xu  _et al._ (2012) L. Xu, J. Lu, and Y. Wang, The European Physical Journal C 72 (2012), 10.1140/epjc/s10052-012-1883-7.
  * Pourhassan (2013) B. Pourhassan, Int. J. Mod. Phys. D 22, 1350061 (2013), arXiv:1301.2788 [gr-qc] .
  * Saadat and Pourhassan (2013) H. Saadat and B. Pourhassan, Astrophys. Space Sci. 344, 237 (2013).
  * Kahya and Pourhassan (2015) E. O. Kahya and B. Pourhassan, Mod. Phys. Lett. A 30, 1550070 (2015), arXiv:1502.01189 [gr-qc] .
  * Tolman (1939) R. C. Tolman, Phys. Rev. 55, 364 (1939).
  * Oppenheimer and Volkoff (1939) J. R. Oppenheimer and G. M. Volkoff, Phys. Rev. 55, 374 (1939).
  * Abbott  _et al._ (2020) R. Abbott _et al._ (LIGO Scientific, Virgo), Astrophys. J. 896, L44 (2020), arXiv:2006.12611 [astro-ph.HE] .
  * Linares  _et al._ (2018) M. Linares, T. Shahbaz, and J. Casares, Astrophys. J. 859, 54 (2018), arXiv:1805.08799 [astro-ph.HE] .
  * Cromartie  _et al._ (2019) H. T. Cromartie _et al._ (NANOGrav), Nature Astron. 4, 72 (2019), arXiv:1904.06759 [astro-ph.HE] .
  * Abbott  _et al._ (2018) B. P. Abbott _et al._ (LIGO Scientific, Virgo), Phys. Rev. Lett. 121, 161101 (2018), arXiv:1805.11581 [gr-qc] .
  * Hinderer (2008) T. Hinderer, The Astrophysical Journal 677, 1216 (2008).
  * Hinderer  _et al._ (2010) T. Hinderer, B. D. Lackey, R. N. Lang, and J. S. Read, Phys. Rev. D 81, 123016 (2010).
  * Abbott  _et al._ (2017) B. P. Abbott _et al._ (LIGO Scientific, Virgo), Phys. Rev. Lett. 119, 161101 (2017), arXiv:1710.05832 [gr-qc] .


# Optimal Adjacency Labels for Subgraphs of Cartesian Products

Louis Esperet
Laboratoire G-SCOP, CNRS, France
<EMAIL_ADDRESS>Partially supported by the French ANR Projects
GATO (ANR-16-CE40-0009-01), GrR (ANR-18-CE40-0032), TWIN-WIDTH
(ANR-21-CE48-0014-01) and by LabEx PERSYVAL-lab (ANR-11-LABX-0025). Nathaniel
Harms
University of Waterloo, Canada
<EMAIL_ADDRESS>This work was partly funded by NSERC, and was done while
the author was visiting Laboratoire G-SCOP and the University of Liverpool.
Viktor Zamaraev
University of Liverpool, UK
<EMAIL_ADDRESS>
###### Abstract

For any hereditary graph class $\mathcal{F}$, we construct optimal adjacency
labeling schemes for the classes of subgraphs and induced subgraphs of
Cartesian products of graphs in $\mathcal{F}$. As a consequence, we show that,
if $\mathcal{F}$ admits efficient adjacency labels (or, equivalently, small
induced-universal graphs) meeting the information-theoretic minimum, then the
classes of subgraphs and induced subgraphs of Cartesian products of graphs in
$\mathcal{F}$ do too.

##  1 Introduction

#### Adjacency labeling.

A class of graphs is a set $\mathcal{F}$ of graphs closed under isomorphism,
where the set $\mathcal{F}_{n}\subseteq\mathcal{F}$ of graphs on $n$ vertices
has vertex set $[n]$. It is _hereditary_ if it is also closed under taking
induced subgraphs, and _monotone_ if it is also closed under taking subgraphs.
An _adjacency labeling scheme_ for a class $\mathcal{F}$ consists of a
_decoder_ $D:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\to\\{0,1\\}$ such that for every
$G\in\mathcal{F}$ there exists a _labeling_ $\ell:V(G)\to\\{0,1\\}^{*}$
satisfying

$\forall x,y\in V(G)\,:\qquad D(\ell(x),\ell(y))=1\iff xy\in E(G)\,.$

The _size_ of the adjacency labeling scheme (or _labeling scheme_ for short)
is the function $n\mapsto\max_{G\in\mathcal{F}_{n}}\max_{x\in V(G)}|\ell(x)|$,
where $|\ell(x)|$ is the number of bits of $\ell(x)$. Labeling schemes have
been studied extensively since their introduction by Kannan, Naor, & Rudich
[KNR92] and Muller [Mul89]. If $\mathcal{F}$ admits a labeling scheme of size
$s(n)$, then a graph $G\in\mathcal{F}_{n}$ can be recovered from the $n\cdot
s(n)$ total bits in the adjacency labels of its vertices, so a labeling scheme
is an encoding of the graph, distributed among its vertices. The information-
theoretic lower bound on any encoding is $\log|\mathcal{F}_{n}|$, so the
question is, when can the distributed adjacency labeling scheme approach this
bound? In other words, which classes of graphs admit labeling schemes of size
$O(\tfrac{1}{n}\log|\mathcal{F}_{n}|)$?

#### Cartesian products.

Write $G\square H$ for the Cartesian product of $G$ and $H$, write $G^{d}$ for
the $d$-wise Cartesian product of $G$, and for any class $\mathcal{F}$ write
$\mathcal{F}^{\square}=\\{G_{1}\square G_{2}\square\dotsm\square
G_{d}:d\in\mathbb{N},G_{i}\in\mathcal{F}\\}$ for the class of Cartesian
products of graphs in $\mathcal{F}$. Write
$\mathsf{mon}(\mathcal{F}^{\square})$ and
$\mathsf{her}(\mathcal{F}^{\square})$, respectively, for the monotone and
hereditary closures of this class, which are the sets of all graphs $G$ that
are a subgraph (respectively, induced subgraph) of some
$H\in\mathcal{F}^{\square}$.

Cartesian products have appeared several times independently in the recent
literature on labeling schemes [CLR20, Har20, AAL21] (and later in [HWZ22,
AAA+22, EHK22]), and are extremely natural for the problem of adjacency
labeling. For example, taking $\mathcal{F}$ to be the class of complete
graphs, a labeling scheme for $\mathsf{her}(\mathcal{F}^{\square})$ is
equivalent to an encoding $\ell:T\to\\{0,1\\}^{*}$ of a set of strings
$T\subseteq\Sigma^{*}$, with $\Sigma$ being an arbitrarily large finite
alphabet, such that a decoder who doesn’t know $T$ can decide whether $x,y\in
T$ have Hamming distance 1, using only the encodings $\ell(x)$ and $\ell(y)$.
Replacing complete graphs with, say, paths, one obtains induced subgraphs of
grids in arbitrary dimension. Switching to
$\mathsf{mon}(\mathcal{F}^{\square})$ allows arbitrary edges of these products
to be deleted.

Motivated by the problem of designing labeling schemes, Chepoi, Labourel, &
Ratel [CLR20] studied the structure of general Cartesian products. For the
subgraphs and induced subgraphs of hypercubes (i.e.
$\mathsf{her}(\\{K_{2}\\}^{\square})$ and
$\mathsf{mon}(\\{K_{2}\\}^{\square})$), there is a labeling scheme of size
$O(\log^{2}n)$ that follows from a folklore bound of $\log(n)$ on their
degeneracy (see [Gra70]) and a general $O(k\log n)$ labeling scheme for
classes of degeneracy $k$ [KNR92]. [CLR20] give upper bounds on the label size
for a number of special cases but do not improve in general upon the
$O(\log^{2}n)$ bound for subgraphs of hypercubes. Designing a labeling scheme
for _induced_ subgraphs of hypercubes (rather, the weaker question of proving
bounds on $|\mathcal{F}_{n}|$) was an open problem of Alecu, Atminas, & Lozin
[AAL21], answered concurrently in independent work [Har20] (see the clearer
exposition [Har22]) using a probabilistic argument, which also answered a
question of [AAL21] about _graph functionality_. Finding an efficient
_deterministic_ labeling scheme is an open problem of [AAA+22].

Meanwhile, the subgraphs of hypercubes are a counterexample [EHK22] to a
conjecture in [HWZ22] about adjacency _sketches_ (a randomized variant of
labeling schemes). Cartesian products are important for understanding the
relationship between sketches and labels: a constant-size sketch and an
$O(\log n)$ labeling scheme exist for _induced_ subgraphs of the hypercube,
but constant-size sketches for _subgraphs_ do not exist [EHK22]. This prompted
[EHK22] to ask if an $O(\log n)$ labeling scheme for subgraphs _also_ does not
exist, since the earlier work considering hypercubes [CLR20, Har20, HWZ22,
AAL21, AAA+22] had not improved on the trivial $O(\log^{2}n)$ bound. This
would be the first natural and explicit counterexample to the Implicit Graph
Conjecture of [KNR92, Spi03], which was recently refuted by a non-constructive
proof [HH21]. That possibility was one motivation for this work; alas, it is
not so.

An equivalent problem to designing labeling schemes is constructing _induced-
universal graphs_ (or simply _universal graphs_) for a hereditary class
$\mathcal{F}$. A sequence of graphs $(U_{n})_{n\in\mathbb{N}}$ are universal
graphs of size $n\mapsto|V(U_{n})|$ if every $G\in\mathcal{F}_{n}$ is an
induced subgraph of $U_{n}$. [KNR92] observed that a labeling scheme of size
$s(n)$ is equivalent to a universal graph of size $2^{s(n)}$. In this
terminology, the goal is to find universal graphs of size
$\operatorname{poly}(|\mathcal{F}_{n}|^{1/n})$; the case where this is
$\operatorname{poly}(n)$ is of special interest, which corresponds to labels
of size $O(\log n)$ [KNR92, Spi03, HH21]. If $U_{n}$ is a universal graph for
$\mathcal{F}$ then for large enough $d$, $U_{n}^{d}$ is a universal graph for
$\mathsf{her}(\mathcal{F}^{\square})$, but in general it has at least
exponential size: a star with $n-1$ leaves is a member of
$\mathsf{her}(\\{K_{2}\\}^{\square})$ but the smallest product it can be
embedded into is $K_{2}^{n-1}$. It is not clear _a priori_ how to get a
universal graph for $\mathsf{mon}(\mathcal{F}^{\square})$ in a similar way
from $U_{n}$ even when $\mathcal{F}$ is monotone, since $U_{n}^{d}$ is not
universal for $\mathsf{mon}(\mathcal{F}^{\square})$ (we emphasize that
$\mathsf{mon}(\mathcal{F}^{\square})$ is not the same as
$\mathsf{her}(\mathsf{mon}(\mathcal{F})^{\square})$). Our proof shows that one
can derive small universal graphs for $\mathsf{her}(\mathcal{F}^{\square})$
and $\mathsf{mon}(\mathcal{F}^{\square})$ from $U_{n}$, although the
transformation is not clearly interpretable from a graph theory perspective.

#### Results.

We improve the best-known $O(\log^{2}n)$ bound for subgraphs of hypercubes to
the optimal $O(\log n)$, and in general show how to construct optimal labels
for all subgraphs and induced subgraphs of Cartesian products.

######  Theorem 1.1.

Let $\mathcal{F}$ be a hereditary class with an adjacency labeling scheme of
size $s(n)$. Then:

  1. 1.

$\mathsf{her}(\mathcal{F}^{\square})$ has a labeling scheme of size at most
$4s(n)+O(\log n)$.

  2. 2.

$\mathsf{mon}(\mathcal{F}^{\square})$ has a labeling scheme where each
$G\in\mathsf{mon}(\mathcal{F}^{\square})$ on $n$ vertices is given labels of
size at most $4s(n)+O(k(G)+\log n)$, where $k(G)$ is the degeneracy of $G$.

All of the labeling schemes of Chepoi, Labourel, & Ratel [CLR20] are obtained
by bounding $k(G)$ and applying the black-box $O(k(G)\cdot\log n)$ bound of
[KNR92]. For example, they get labels of size $O(d\log^{2}n)$ when the base
class $\mathcal{F}$ has degeneracy $d$, by showing that
$\mathsf{mon}(\mathcal{F}^{\square})$ has degeneracy $O(d\log n)$. Our result
can substituted for that black-box, replacing the multiplicative $O(\log n)$
with an _additive_ $O(\log n)$, thereby improving all of the results of
[CLR20]; for example, achieving $O(d\log n)$ when $\mathcal{F}$ has degeneracy
$d$.

For subgraphs of hypercubes, [CLR20] observed that a bound of
$O(\mathsf{vc}(G)\log n)$ follows from the inequality $k(G)\leq\mathsf{vc}(G)$
due to Haussler [Hau95], where $\mathsf{vc}(G)$ is the VC dimension111See
[CLR20] for the definition of VC dimension, which can be as large as $\log n$
but is often much smaller; they generalize this inequality in various ways to
other Cartesian products. Our result supercedes the VC dimension result for
hypercubes.

Theorem 1.1 is optimal up to constant factors (which we have not tried to
optimize), and we get the following corollary (see Section 3 for proofs). Say
that a hereditary class $\mathcal{F}$ admits an _efficient_ labeling scheme if
it either admits a _constant-size_ labeling scheme (i.e. it satisfies
$\log|\mathcal{F}_{n}|=o(n\log n)$ [Sch99], including the case where
$\mathcal{F}$ is finite), or it admits a labeling scheme of size
$O(\tfrac{1}{n}\log|\mathcal{F}_{n}|)$. Equivalently, if it admits a universal
graph of size $\operatorname{poly}(|\mathcal{F}_{n}|^{1/n})$. Then:

######  Corollary 1.2.

If a hereditary class $\mathcal{F}$ has an efficient labeling scheme, then so
do $\mathsf{her}(\mathcal{F}^{\square})$ and
$\mathsf{mon}(\mathcal{F}^{\square})$.

##  2 Adjacency Labeling Scheme

#### Notation.

For two binary strings $x,y$, we write $x\oplus y$ for the bitwise XOR. For
two graphs $G$ and $H$, we will write $G\subset H$ if $G$ is a subgraph of
$H$, and $G\subset_{I}H$ if $G$ is an _induced_ subgraph of $H$. We will write
$V(G)$ and $E(G)$ as the vertex and edge set of a graph $G$, respectively. All
graphs in this paper are simple and undirected. A graph $G$ has _degeneracy_
$k$ if all subgraphs of $G$ have a vertex of degree at most $k$.

For graphs $G_{1},\dotsc,G_{d}$, the Cartesian product graph
$G=G_{1}\square\dotsm\square G_{d}$ is the graph with vertices
$V(G)=V(G_{1})\times\dotsm\times V(G_{d})$, where each $x\in V(G)$ can be
written as $x=(x_{1},\dotsc,x_{d})$ for $x_{i}\in V(G_{i})$; there is an edge
between $x$ and $y$ if and only if there is a unique $i\in[d]$ where
$x_{i}\neq y_{i}$, and, for this coordinate, $x_{i}y_{i}\in E(G_{i})$.

#### Strategy.

Suppose $G\subset G_{1}\square\dotsm\square G_{d}$ is a subgraph of a
Cartesian product. Then $V(G)\subseteq V(G_{1})\times\dotsm\times V(G_{d})$.
Let $H\subset_{I}G_{1}\square\dotsm\square G_{d}$ be the subgraph induced by
$V(G)$, so that $E(G)\subseteq E(H)$. One may think of $G$ as being obtained
from the induced subgraph $H$ by deleting some edges. Then two vertices
$x,y\in V(G)$ are adjacent if and only if:

  1. 1.

There exists exactly one coordinate $i\in[d]$ where $x_{i}\neq y_{i}$;

  2. 2.

On this coordinate, $x_{i}y_{i}\in E(G_{i})$; and,

  3. 3.

The edge $xy\in E(H)$ has not been deleted in $E(G)$.

We construct the labels for vertices in $G$ in three phases, which check these
conditions in sequence.

###  2.1 Phase 1: Exactly One Difference

This phase is an easy extension of the simple proof in [Har22] of the labeling
scheme for induced subgraphs of hypercubes, derived from [Har20, HWZ22]. The
labels are obtained by a simple probabilistic method (and are efficiently
computable by a randomized algorithm).

For any alphabet $\Sigma$ and any two strings $x,y\in\Sigma^{d}$ where
$d\in\mathbb{N}$, write $\mathsf{dist}(x,y)$ for the Hamming distance between
$x$ and $y$, i.e. $\mathsf{dist}(x,y)=|\\{i\in[d]:x_{i}\neq y_{i}\\}|$.

######  Proposition 2.1.

For any set $S\subseteq\\{0,1\\}^{d}$, there exists a random function
$\ell:S\to\\{0,1\\}^{4}$ such that, for all $x,y\in S$,

  1. 1.

If $\mathsf{dist}(x,y)\leq 1$ then
$\underset{\ell}{\mathbb{P}}\left[\mathsf{dist}(\ell(x),\ell(y))\leq
1\right]=1$, and

  2. 2.

If $\mathsf{dist}(x,y)>1$ then
$\underset{\ell}{\mathbb{P}}\left[\mathsf{dist}(\ell(x),\ell(y))\leq
1\right]\leq 3/4$.

###### Proof.

Choose a uniformly random map $p:[d]\to[4]$ and partition $[d]$ into four sets
$P_{j}=p^{-1}(j)$. For each $i\in[4]$, define $\ell(x)_{i}:=\bigoplus_{j\in
P_{i}}x_{j}$.

Let $x,y\in S$ and write $w=\ell(x)\oplus\ell(y)$. Note that
$\mathsf{dist}(\ell(x),\ell(y))=|w|$, which is the number of 1s in $w$. If
$\mathsf{dist}(x,y)=0$ then $\mathsf{dist}(\ell(x),\ell(y))=0\leq 1$. Now
suppose $\mathsf{dist}(x,y)=1$. For any choice of $p:[d]\to[4]$, one of the
sets $P_{i}$ contains the differing coordinate and will have $w_{i}=1$, while
the other three sets $P_{j}$ will have $w_{j}=0$, so
$\underset{\ell}{\mathbb{P}}\left[\mathsf{dist}(\ell(x),\ell(y))\leq
1\right]=1$.

Now suppose $\mathsf{dist}(x,y)=t\geq 2$. We will show that $|w|\leq 1$ with
probability at most $3/4$. Note that $w$ is obtained by the random process
where $\vec{0}=w^{(0)},w=w^{(t)}$, and $w^{(i)}$ is obtained from $w^{(i-1)}$
by flipping a uniformly random coordinate.

Observe that, for $i\geq 1$, $\mathbb{P}\left[w^{(i)}=\vec{0}\right]\leq 1/4$.
This is because $w^{(i)}=\vec{0}$ can occur only if $|w^{(i-1)}|=1$, so the
probability of flipping the 1-valued coordinate is $1/4$. If $|w^{(i-1)}|\geq
1$ then $\underset{}{\mathbb{P}}\left[|w^{(i)}|\leq
1\;\;\mid\;\;|w^{(i-1)}|\geq 1\right]\leq 1/2$ since either $|w^{(i-1)}|=1$
and then $|w^{(i)}|=0\leq 1$ with probability $1/4$, or $|w^{(i-1)}|\geq 2$
and $|w^{(i)}|=1$ with probability at most $1/2$. Then, for $t\geq 2$,

$\displaystyle\mathbb{P}\left[|w^{(t)}|\leq 1\right]$
$\displaystyle=\mathbb{P}\left[w^{(t-1)}=\vec{0}\right]+\mathbb{P}\left[|w^{(t-1)}|\geq
1\right]\cdot\underset{}{\mathbb{P}}\left[|w^{(t)}|=1\;\;\mid\;\;|w^{(t-1)}|\geq
1\right]\leq\frac{1}{4}+\frac{1}{2}=\frac{3}{4}\,.\qed$

######  Proposition 2.2.

There exists a function $D:\\{0,1\\}^{4}\times\\{0,1\\}^{4}\to\\{0,1\\}$ such
that, for any countable alphabet $\Sigma$, any $d\in\mathbb{N}$, and any
$S\subseteq\Sigma^{d}$ of size $n=|S|$, there exists a random function
$\ell:S\to\\{0,1\\}^{4}$ such that, for all $x,y\in S$,

  1. 1.

If $\mathsf{dist}(x,y)\leq 1$, then
$\underset{\ell}{\mathbb{P}}\left[D(\ell(x),\ell(y))=1\right]=1$, and

  2. 2.

If $\mathsf{dist}(x,y)>1$, then
$\underset{\ell}{\mathbb{P}}\left[D(\ell(x),\ell(y))=1\right]\leq 15/16$.

###### Proof.

For each $\sigma\in\Sigma$ and $i\in[d]$, generate an independently and
uniformly random bit $q_{i}(\sigma)\sim\\{0,1\\}$. Then for each $x\in S$
define $p(x)=(q_{1}(x_{1}),\dotsc,q_{d}(x_{d}))\in\\{0,1\\}^{d}$ and
$S^{\prime}=\\{p(x):x\in S\\}$, and let $\ell^{\prime}$ be the random function
$S^{\prime}\to\\{0,1\\}^{4}$ guaranteed to exist by Proposition 2.1. We define
the random function $\ell:S\to\\{0,1\\}^{4}$ as $\ell(x)=\ell^{\prime}(p(x))$.
We define $D(\ell(x),\ell(y))=1$ if and only if
$\mathsf{dist}(\ell^{\prime}(p(x)),\ell^{\prime}(p(y)))\leq 1$.

Let $x,y\in S$. If $\mathsf{dist}(x,y)\leq 1$, so there is a unique $i\in[d]$
with $x_{i}\neq y_{i}$, then

$\mathbb{P}\left[\mathsf{dist}(p(x),p(y))=1\right]=\mathbb{P}\left[q_{i}(x_{i})\neq
q_{i}(y_{i})\right]=\mathbb{P}\left[\mathsf{dist}(p(x),p(y))=0\right]=1/2\,,$

so $\mathbb{P}\left[\mathsf{dist}(p(x),p(y))\leq 1\right]=1$. Then by
Proposition 2.1,

$\mathbb{P}\left[D(\ell(x),\ell(y))=1\right]=\mathbb{P}\left[\mathsf{dist}(\ell^{\prime}(p(x)),\ell^{\prime}(p(y)))\leq
1\right]=1\,.$

If $\mathsf{dist}(x,y)>1$ so that there are distinct $i,i^{\prime}\in[d]$ such
that $x_{i}\neq y_{i}$ and $x_{i^{\prime}}\neq y_{i^{\prime}}$, then

$\mathbb{P}\left[\mathsf{dist}(p(x),p(y))\geq
2\right]\geq\mathbb{P}\left[q_{i}(x_{i})\neq q_{i}(y_{i})\wedge
q_{i^{\prime}}(x_{i^{\prime}})\neq
q_{i^{\prime}}(y_{i^{\prime}})\right]=1/4\,.$

Then by Proposition 2.1,

$\displaystyle\mathbb{P}\left[D(\ell(x),\ell(y))=1\right]$
$\displaystyle=\mathbb{P}\left[\mathsf{dist}(\ell^{\prime}(p(x)),\ell^{\prime}(p(y)))\leq
1\right]$ $\displaystyle=\mathbb{P}\left[\mathsf{dist}(p(x),p(y))\leq
1\vee\mathsf{dist}(\ell^{\prime}(p(x)),\ell^{\prime}(p(y)))\leq 1\right]$
$\displaystyle\leq 3/4+(1-3/4)(3/4)=15/16\,.\qed$

######  Lemma 2.3.

There exists a function $D:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\to\\{0,1\\}$ and a
constant $c>0$ such that, for any countable alphabet $\Sigma$ any
$d\in\mathbb{N}$, and any set $S\subseteq\Sigma^{d}$ of size $|S|=n$, there
exists a function $\ell:S\to\\{0,1\\}^{k}$ for $k\leq c\log n$, where
$D(\ell(x),\ell(y))=1$ if and only if $\mathsf{dist}(x,y)=1$.

###### Proof.

Since $\lceil\log n\rceil$ bits can be added to any $\ell(x)$ to ensure that
each $\ell(x)$ is unique, it suffices to construct functions $D,\ell$ where
$D(\ell(x),\ell(y))=1$ if and only if $\mathsf{dist}(x,y)\leq 1$, instead of
$\mathsf{dist}(x,y)=1$.

Let $q$ be a parameter to be fixed later. Let
$D^{\prime}:\\{0,1\\}^{4}\times\\{0,1\\}^{4}\to\\{0,1\\}$ be the function from
Proposition 2.2. Choose a random function $\ell:S\to\\{0,1\\}^{k}$ with $k=4q$
as follows. For each $x\in S$, let $\ell(x)=(\ell_{1}(x),\dotsc,\ell_{q}(x))$
where each $\ell_{i}:S\to\\{0,1\\}^{4}$ is an independent copy of the random
function from Proposition 2.2. Define

$D(\ell(x),\ell(y))=\bigwedge_{i=1}^{q}D^{\prime}(\ell_{i}(x),\ell_{i}(y))\,.$

Fix any pair $x,y\in S$. If $\mathsf{dist}(x,y)\leq 1$ then
$\underset{\ell}{\mathbb{P}}\left[D(\ell(x),\ell(y))=1\right]=1$ since
$D^{\prime}(\ell_{j}(x),\ell_{j}(y))=1$ with probability 1. If
$\mathsf{dist}(x,y)>1$ then
$\mathbb{P}\left[D^{\prime}(\ell_{j}(x),\ell_{j}(y))=1\right]\leq 15/16$. Then

$\mathbb{P}\left[D(\ell(x),\ell(y))=1\right]\leq(15/16)^{q}\leq 1/n^{2}\,,$

when we set $q=\frac{2}{\log(16/15)}\log(n)$. Therefore, by the union bound,
the probability that there exist two $x,y\in S$ such that $D(\ell(x),\ell(y))$
is incorrect is less than 1. So there exists a fixed function $\ell$ with the
desired properties. ∎

###  2.2 Phase 2: Induced Subgraphs

After the first phase, we are guaranteed that there is a unique coordinate
$i\in[d]$ where $x_{i}\neq y_{i}$. In the second phase we wish to determine
whether $x_{i}y_{i}\in E(G_{i})$. It is convenient to have labeling schemes
for the factors $G_{1},\dotsc,G_{d}$ where we can XOR the labels together
while retaining the ability to compute adjacency. Define an _XOR-labeling
scheme_ the same as an adjacency labeling scheme, with the restriction that
for each $s\in\mathbb{N}$ there is some function
$g_{s}:\\{0,1\\}^{s}\to\\{0,1\\}$ such that on any two labels
$\ell(x),\ell(y)$ of size $s$, the decoder outputs
$D(\ell(x),\ell(y))=g_{s}(\ell(x)\oplus\ell(y))$. Any labeling scheme can be
transformed into an XOR-labeling scheme with at most a constant-factor loss:

######  Lemma 2.4.

Let $\mathcal{F}$ be any hereditary class of graphs with an adjacency labeling
scheme of size $s(n)$. Then $\mathcal{F}$ admits an XOR-labeling scheme of
size at most $4s(n)$.

###### Proof.

Let $D:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\to\\{0,1\\}$ be the decoder of the
adjacency labeling scheme for $\mathcal{F}$, fix any $n\in\mathbb{N}$, and
write $s=s(n)$. Note that $D$ must be symmetric, so $D(a,b)=D(b,a)$ for any
$a,b\in\\{0,1\\}^{s}$. Let $\phi:\\{0,1\\}^{s}\to\\{0,1\\}^{4s}$ be uniformly
randomly chosen, so that for every $z\in\\{0,1\\}^{s}$,
$\phi(z)\sim\\{0,1\\}^{4s}$ is a uniform and independently random variable.
For any two distinct pairs
$\\{z_{1},z_{2}\\},\\{z_{1}^{\prime},z_{2}^{\prime}\\}\in{\\{0,1\\}^{s}\choose
2}$ where $z_{1}\neq z_{2}$, $z_{1}^{\prime}\neq z_{2}^{\prime}$, and
$\\{z_{1},z_{2}\\}\neq\\{z_{1}^{\prime},z_{2}^{\prime}\\}$, the probability
that
$\phi(z_{1})\oplus\phi(z_{2})=\phi(z_{1}^{\prime})\oplus\phi(z_{2}^{\prime})$
is at most $2^{-4s}$, since at least one of the variables
$\phi(z_{1}),\phi(z_{2}),\phi(z_{1}^{\prime}),\phi(z_{2}^{\prime})$ is
independent of the other ones. Therefore, by the union bound,

$\mathbb{P}\left[\exists\\{z_{1},z_{2}\\},\\{z_{1}^{\prime},z_{2}^{\prime}\\}:\phi(z_{1})\oplus\phi(z_{2})=\phi(z_{1}^{\prime})\oplus\phi(z_{2}^{\prime})\right]\leq{2^{s}\choose
2}^{2}2^{-4s}\leq\frac{1}{4}\,.$

Then there is $\phi:\\{0,1\\}^{s}\to\\{0,1\\}^{4s}$ such that each distinct
pair $\\{z_{1},z_{2}\\}\in{\\{0,1\\}^{s}\choose 2}$ is assigned has a distinct
unique value $\phi(z_{1})\oplus\phi(z_{2})$. So the function
$\Phi(\\{z_{1},z_{2}\\})=\phi(z_{1})\oplus\phi(z_{2})$ is a one-to-one map
${\\{0,1\\}^{s}\choose 2}\to\\{0,1\\}^{4s}$. Then for any graph
$G\in\mathcal{F}$ on $n$ vertices, with labeling $\ell:V(G)\to\\{0,1\\}^{s}$,
we may assign the new label $\ell^{\prime}(x)=\phi(\ell(x))$. On labels
$\phi(\ell(x)),\phi(\ell(y))\in\\{0,1\\}^{s}$, the decoder for the XOR-
labeling scheme simply computes
$D\left(\Phi^{-1}(\phi(\ell(x))\oplus\phi(\ell(y)))\right)=D(\ell(x),\ell(y))$.
∎

We can now prove the first part of Theorem 1.1.

######  Lemma 2.5.

Let $\mathcal{F}$ be a hereditary class of graphs that admits an adjacency
labeling scheme of size $s(n)$. Then $\mathsf{her}(\mathcal{F}^{\square})$
admits an adjacency labeling scheme of size $4s(n)+O(\log n)$.

###### Proof.

By Lemma 2.4, there is an XOR-labeling scheme for $\mathcal{F}$ with labels of
size $4s(n)$. Let $D:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\to\\{0,1\\}$ be the
decoder for this scheme, with $D(a,b)=g(a\oplus b)$ for some function $g$.
Design the labels for $\mathsf{her}(\mathcal{F}^{\square})$ as follows.
Consider a graph $G\in\mathsf{her}(\mathcal{F}^{\square})$, so that
$G\subset_{I}G_{1}\square G_{2}\square\dotsm\square G_{d}$ for some
$d\in\mathbb{N}$ and $G_{i}\in\mathcal{F}$ for each $i\in[d]$. Since
$\mathcal{F}$ is hereditary, we may assume that each $G_{i}$ has at most $n$
vertices; otherwise we could simply replace it with the subgraph of $G_{i}$
induced by the vertices $\\{x_{i}:x\in V(G)\\}$. For each
$x=(x_{1},\dotsc,x_{d})\in V(G)$, construct the label as follows:

  1. 1.

Treating the vertices in each $G_{i}$ as characters of the alphabet $[n]$, use
$O(\log n)$ bits to assign the label given to
$x=(x_{1},\dotsc,x_{d})\in[n]^{d}$ by Lemma 2.3.

  2. 2.

Using $4s(n)$ bits, append the vector $\bigoplus_{i\in[d]}\ell_{i}(x_{i})$,
where $\ell_{i}(x_{i})$ is the label of $x_{i}\in V(G_{i})$ in graph $G_{i}$,
according to the XOR-labeling scheme for $\mathcal{F}$.

The decoder operates as follows. Given the labels for $x,y\in V(G)$:

  1. 1.

If $x$ and $y$ differ on exactly one coordinate, as determined by the first
part of the label, continue to the next step. Otherwise output “not
adjacent”.

  2. 2.

Now guaranteed that there is a unique $i\in[d]$ such that $x_{i}\neq y_{i}$,
output “adjacent” if and only if the following is 1:

$\displaystyle
D\left(\bigoplus_{j\in[d]}\ell_{j}(x_{j})\,,\bigoplus_{j\in[d]}\ell_{j}(y_{j})\right)$
$\displaystyle=g\left(\bigoplus_{j\in[d]}\ell_{j}(x_{j})\oplus\bigoplus\ell_{j}(y_{j})\right)$
$\displaystyle=g\left(\ell_{i}(x_{i})\oplus\ell_{i}(y_{i})\oplus\bigoplus_{j\neq
i}\ell_{j}(x_{j})\oplus\ell_{j}(y_{j})\right)=g(\ell_{i}(x_{i})\oplus\ell_{i}(y_{i}))\,,$

where the final equality holds because $x_{j}=y_{j}$ for all $j\neq i$, so
$\ell_{j}(x_{j})=\ell_{j}(y_{j})$. Then the output value is 1 if and only
$x_{i}y_{i}$ is an edge of $G_{i}$; equivalently, $xy$ is an edge of $G$.

This concludes the proof. ∎

The XOR-labeling trick can also be used to simplify the proof of [HWZ22] for
adjacency _sketches_ of Cartesian products. That proof uses a two-level
hashing scheme to avoid destroying the labels of $x_{i}$ and $y_{i}$ with the
XOR, with a high constant probability of success. That strategy does not work
for us here, because we need to succeed with certainty.

###  2.3 Phase 3: Subgraphs

Finally, we must check whether the edge $xy\in E(H)$ in the _induced_ subgraph
$H\subset_{I}G_{1}\square\dotsm\square G_{d}$ has been deleted in $E(G)$.
There is a minimal and perfect tool for this task:

######  Theorem 2.6 (Minimal Perfect Hashing).

For every $m,k\in\mathbb{N}$, there is a family $\mathcal{P}_{m,k}$ of hash
functions $[m]\to[k]$ such that, for any $S\subseteq[m]$ of size $k$, there
exists $h\in\mathcal{P}_{m,k}$ where the image of $S$ under $h$ is $[k]$ and
for every distinct $i,j\in S$ we have $h(i)\neq h(j)$. The function $h$ can be
stored in $k\ln e+\log\log m+o(k+\log\log m)$ bits of space and it can be
computed by a randomized algorithm in expected time $O(k+\log\log m)$.

Minimal perfect hashing has been well-studied. A proof of the space bound
appears in [Meh84] and significant effort has been applied to improving the
construction and evaluation time. We take the above statement from [HT01]. We
now conclude the proof of Theorem 1.1 by applying the next lemma to the class
$\mathcal{G}=\mathsf{her}(\mathcal{F}^{\square})$, using the labeling scheme
for $\mathsf{her}(\mathcal{F}^{\square})$ obtained in Lemma 2.5 (note that
$\mathsf{mon}(\mathsf{her}(\mathcal{F}^{\square}))=\mathsf{mon}(\mathcal{F}^{\square})$).

######  Lemma 2.7.

Let $\mathcal{G}$ be any graph class which admits an adjacency labeling scheme
of size $s(n)$. Then $\mathsf{mon}(\mathcal{G})$ admits an adjacency labeling
scheme where each $G\in\mathsf{mon}(\mathcal{G})$ on $n$ vertices has labels
of size $s(n)+O(k(G)+\log n)$, where $k(G)$ is the degeneracy of $G$.

###### Proof.

Let $G\in\mathsf{mon}(\mathcal{G})$ have $n$ vertices, so that it is a
subgraph of $H\in\mathcal{G}$ on $n$ vertices. The labeling scheme is as
follows.

  1. 1.

Fix a total order $\prec$ on $V(H)$ such that each vertex $x$ has at most
$k=k(G)$ neighbors $y$ in $H$ such that $x\prec y$; this exists by definition.
We will identify each vertex $x$ with its position in the order.

  2. 2.

For each vertex $x$, assign the label as follows:

    1. (a)

Use $s(n)$ bits for the adjacency label of $x$ in $H$.

    2. (b)

Use $\log n$ bits to indicate $x$ (the position in the order).

    3. (c)

Let $N^{+}(x)$ be the set of neighbors $x\prec y$. Construct a perfect hash
function $h_{x}:N^{+}(x)\to[k]$ and store it, using $O(k+\log\log n)$ bits.

    4. (d)

Use $k$ bits to write the function $\mathsf{edge}_{x}:[k]\to\\{0,1\\}$ which
takes value 1 on $i\in[k]$ if and only if $xy$ is an edge of $G$, where $y$ is
the unique vertex in $N^{+}(x)$ satisfying $h_{x}(y)=i$.

Given the labels for $x$ and $y$, the decoder performs the following:

  1. 1.

If $xy$ are not adjacent in $H$, output “not adjacent”.

  2. 2.

Otherwise $xy$ are adjacent. If $x\prec y$, we are guaranteed that $y$ is in
the domain of $h_{x}$, so output “adjacent” if and only if
$\mathsf{edge}_{x}(h_{x}(y))=1$. If $y\prec x$, output “adjacent” if and only
if $\mathsf{edge}_{y}(h_{y}(x))=1$.

This concludes the proof. ∎

##  3 Optimality

We now prove the optimality of our labeling schemes, and Corollary 1.2. We
require:

######  Proposition 3.1.

For any hereditary class $\mathcal{F}$, let $k(n)$ be the maximum degeneracy
of an $n$-vertex graph $G\in\mathsf{her}(\mathcal{F}^{\square})$. Then
$\mathsf{her}(\mathcal{F}^{\square})$ contains a graph $H$ on $n$ vertices
with at least $n\cdot k(n)/4$ edges, so $\mathsf{mon}(\mathcal{F}^{\square})$
contains all $2^{n\cdot k(n)/4}$ spanning subgraphs of $H$.

###### Proof.

Since $G$ has degeneracy $k=k(n)$, it contains an induced subgraph
$G^{\prime}\subset_{I}G$ with minimum degree $k$ and $n_{1}\leq n$ vertices.
If $n_{1}\geq n/2$ then $G$ itself has at least $kn_{1}/2\geq kn/4$ edges, and
we are done. Now assume $n_{1}<n/2$. Since
$G\in\mathsf{her}(\mathcal{F}^{\square})$,
$G\subset_{I}H_{1}\square\dotsm\square H_{t}$ for some $t\in\mathbb{N}$ and
$H_{i}\in\mathcal{F}$. So for any $d\in\mathbb{N}$, the graph
$(G^{\prime})^{d}\subset_{I}(H_{1}\square\dotsm\square H_{t})^{d}$ belongs to
$\mathsf{her}(\mathcal{F}^{\square})$. Consider the graph
$H\subset_{I}(G^{\prime})^{d}$ defined as follows. Choose any $w\in
V(G^{\prime})$, and for each $i\in[d]$ let

$V_{i}=\\{(v_{1},v_{2},\dotsc,v_{d}):v_{i}\in V(G^{\prime})\text{ and }\forall
j\neq i,v_{j}=w\\}\,,$

and let $H$ be the graph induced by vertices $V_{1}\cup\dotsm\cup V_{d}$. Then
$H$ has $dn_{1}$ vertices, each of degree at least $k$, since each $v\in
V_{i}$ is adjacent to $k$ other vertices in $V_{i}$. Set $d=\lceil
n/n_{1}\rceil$, so that $H$ has at least $n$ vertices, and let $m=dn_{1}-n$,
which satisfies $m<n_{1}$. Remove any $m$ vertices of $V_{1}$. The remaining
graph $H^{\prime}$ has $n$ vertices, and at least $(d-1)n_{1}\geq n-n_{1}>n/2$
vertices of degree $k$. Then $H^{\prime}$ has at least $kn/4$ edges. ∎

The next proposition shows that Theorem 1.1 is optimal up to constant factors.
It is straightforward to check that this proposition implies Corollary 1.2.

######  Proposition 3.2.

Let $\mathcal{F}$ be a hereditary class whose optimal adjacency labeling
scheme has size $s(n)$ and which contains a graph with at least one edge. Then
any adjacency labeling scheme for $\mathsf{her}(\mathcal{F}^{\square})$ has
size at least $\Omega(s(n)+\log n)$, and any adjacency labeling scheme for
$\mathsf{mon}(\mathcal{F}^{\square})$ has size at least $\Omega(s(n)+k(n)+\log
n)$, where $k(n)$ is the maximum degeneracy of any $n$-vertex graph in
$\mathsf{mon}(\mathcal{F}^{\square})$.

###### Proof.

Since $\mathcal{F}\subseteq\mathsf{her}(\mathcal{F}^{\square})$ and
$\mathcal{F}\subseteq\mathsf{mon}(\mathcal{F}^{\square})$, we have a lower
bound of $s(n)$ for the labeling schemes for both of these classes. Since
$\mathcal{F}$ contains a graph $G$ with at least one edge, the Cartesian
products contain the class of hypercubes:
$\mathsf{her}(\\{K_{2}\\}^{\square})\subseteq\mathsf{her}(\mathcal{F}^{\square})\subseteq\mathsf{mon}(\mathcal{F}^{\square})$.
A labeling scheme for $\mathsf{her}(\\{K_{2}\\}^{\square})$ must have size
$\Omega(\log n)$ (which can be seen since each vertex of $K_{2}^{d}$ has a
unique neighborhood and thus requires a unique label). This establishes the
lower bound for $\mathsf{her}(\mathcal{F}^{\square})$, since the labels must
have size $\max\\{s(n),\Omega(\log n)\\}=\Omega(s(n)+\log n)$. Finally, by
Proposition 3.1, the number of $n$-vertex graphs in
$\mathsf{mon}(\mathcal{F}^{\square})$ is at least $2^{\Omega(nk(n))}$, so
there is a lower bound on the label size of $\Omega(k(n))$, which implies a
lower bound of $\max\\{s(n),\Omega(\log
n),\Omega(k(n))\\}=\Omega(s(n)+k(n)+\log n)$ for
$\mathsf{mon}(\mathcal{F}^{\square})$. ∎

Acknowledgments.

We are very grateful to Sebastian Wild, who prevented us trying to reinvent
perfect hashing.

## References

  * [AAA+22] Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin, and Viktor Zamaraev.  Graph parameters, implicit representations and factorial properties.  In submission, 2022.
  * [AAL21] Bogdan Alecu, Aistis Atminas, and Vadim Lozin.  Graph functionality.  Journal of Combinatorial Theory, Series B, 147:139–158, 2021.
  * [CLR20] Victor Chepoi, Arnaud Labourel, and Sébastien Ratel.  On density of subgraphs of Cartesian products.  Journal of Graph Theory, 93(1):64–87, 2020.
  * [EHK22] Louis Esperet, Nathaniel Harms, and Andrey Kupavskii.  Sketching distances in monotone graph classes.  https://arxiv.org/abs/2202.09253, 2022.
  * [Gra70] Ron L Graham.  On primitive graphs and optimal vertex assignments.  Annals of the New York academy of sciences, 175(1):170–186, 1970\.
  * [Har20] Nathaniel Harms.  Universal communication, universal graphs, and graph labeling.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, page 33. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.
  * [Har22] Nathaniel Harms.  Adjacency labeling and sketching for induced subgraphs of the hypercube.  https://cs.uwaterloo.ca/~nharms/downloads/hypercube_sketch.pdf, 2022\.
  * [Hau95] David Haussler.  Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension.  Journal of Combinatorial Theory, Series A, 69(2):217–232, 1995\.
  * [HH21] Hamed Hatami and Pooya Hatami.  The implicit graph conjecture is false.  arXiv preprint arXiv:2111.13198, 2021.
  * [HT01] Torben Hagerup and Torsten Tholey.  Efficient minimal perfect hashing in nearly minimal space.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 317–326. Springer, 2001.
  * [HWZ22] Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev.  Randomized communication and implicit graph representations.  https://arxiv.org/abs/2111.03639, 2022.  Proceedings of the 54th Annual Symposium on Theory of Computing (STOC 2022), to appear.
  * [KNR92] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.
  * [Meh84] Kurt Mehlhorn.  Data Structures and Algorithms 1 Sorting and Searching.  Monographs in Theoretical Computer Science. An EATCS Series, 1. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 1984. edition, 1984.
  * [Mul89] John H Muller.  Local structure in graph classes.  1989\.
  * [Sch99] Edward R Scheinerman.  Local representations using very short labels.  Discrete mathematics, 203(1-3):287–290, 1999.
  * [Spi03] Jeremy P Spinrad.  Efficient graph representations.  American Mathematical Society, 2003.