# Metallicities, dust and molecular content of a QSO-Damped Lyman-$\alpha$
system reaching $\log N$(H i) = 22:
An analog to GRB-DLAs

R. Guimarães  Programa de Modelagem Computacional - SENAI - Cimatec, 41650-010
Salvador, Bahia, Brasil<EMAIL_ADDRESS>P. Noterdaeme and P. Petitjean
UPMC-CNRS, UMR7095, Institut d’Astrophysique de Paris, 98bis bd Arago, F-75014
Paris, France  C. Ledoux  European Southern Observatory, Alonso de Córdova
3107, Casilla 19001, Vitacura, Santiago 19, Chile  R. Srianand  Inter-
University Centre for Astronomy and Astrophysics, Post Bag 4, Ganeshkhind,
Pune 411 007, India  S. López  Departamento de Astronomía, Universidad de
Chile, Casilla 36-D, Santiago, Chile  H. Rahmani  Inter-University Centre for
Astronomy and Astrophysics, Post Bag 4, Ganeshkhind, Pune 411 007, India

###### Abstract

We present the elemental abundance and H2 content measurements of a Damped
Lyman-$\alpha$ (DLA) system with an extremely large H i column density, $\log
N$(H i) (cm-2) = 22.0$\pm$0.10, at $z_{\rm abs}=3.287$ towards the QSO SDSS J
081634$+$144612\. We measure column densities of H2, C i, C i⋆, Zn ii, Fe ii,
Cr ii, Ni ii and Si ii from a high signal-to-noise and high spectral
resolution VLT-UVES spectrum. The overall metallicity of the system is [Zn/H]
= $-1.10\pm 0.10$ relative to solar. Two molecular hydrogen absorption
components are seen at $z=3.28667$ and 3.28742 (a velocity separation of
$\approx 52$ km s-1) in rotational levels up to $J=3$. We derive a total H2
column density of log $N$(H2) (cm-2) = 18.66 and a mean molecular fraction of
$f$ = $2N($H${}_{2})/[2N$(H${}_{2})+N($H i$)]=10^{-3.04\pm 0.37}$, typical of
known H2-bearing DLA systems. From the observed abundance ratios we conclude
that dust is present in the Interstellar Medium (ISM) of this galaxy, with a
enhanced abundance in the H2-bearing clouds. However, the total amount of dust
along the line of sight is not large and does not produce any significant
reddening of the background QSO. The physical conditions in the H2-bearing
clouds are constrained directly from the column densities of H2 in different
rotational levels, C i and C i⋆. The kinetic temperature is found to be
$T\approx 75$ K and the particle density lies in the range $n_{\rm H}$ =
50$-$80 cm-3. The neutral hydrogen column density of this DLA is similar to
the mean H i column density of DLAs observed at the redshift of $\gamma$-ray
bursts (GRBs). We explore the relationship between GRB-DLAs and high column
density end of QSO-DLAs finding that the properties (metallicity and
depletion) of DLAs with $\log N$(H i) $>$ 21.5 in the two populations do not
appear to be significantly different.

quasars: general — quasars: absorption lines — ISM: molecules

##  1 Introduction

Despite accounting for only a small fraction of all the baryons in the
Universe (see, e.g., Petitjean et al. 1993), the physical state of the neutral
and molecular phases of the interstellar medium is a crucial ingredient of
galaxy formation. These gaseous phases are at any redshift the reservoir of
gas available for star formation. At high redshift, most of the neutral
hydrogen mass is revealed by the damped Lyman-$\alpha$ absorption system
(DLAs) detected in the spectra of background quasars (see e.g. Wolfe et al.
2005 for a review). Since DLAs are easy to identify in QSO spectra and the H i
column densities can be measured accurately, it is possible to derive the
cosmological mass density of the neutral gas at different redshifts,
independent of the exact nature of the absorbers, provided a sufficiently
large number of background quasars are observed (see Prochaska & Wolfe 2009,
Guimarães et al. 2009, Noterdaeme et al. 2009b).

Key results of DLA surveys include the indication that the $N$(H i) frequency
distribution deviates significantly from a single power-law with $f$($N$(H i))
sharply steepening at $\log N$(H i) $>$ 21.5. However, Zwaan & Prochaska
(2006) used CO emission maps in the nearby Universe to show that the H2 column
density distribution function is a continuous extension of the H i
distribution for high column densities. The transition happens at log $N$(H i)
$\sim$ 22 which is the approximate column density associated with the
conversion from H i into H2 (e.g., Schaye 2001).

The slope of the column density distribution at large $N$(H i),
$\alpha\sim−3.5$, implies that systems with very large column density are very
rare. Indeed, until very recently111In the last stages of this work, the
discovery of another DLA with log $N$(H i) $\geq$ 22 was reported by
Noterdaeme et al. (2012) and Kulkarni et al. (2012)., only one DLA system with
$\log N$(H i) $\sim$ 22 was reported in the literature: the system at $z_{\rm
abs}=3.287$ towards SDSS J 081634$+$144612 (from the SDSS-II DLA catalog,
Noterdaeme et al. 2009b). However, DLAs with such high column densities are
frequently detected at the redshift of $\gamma$-ray bursts (e.g. Savaglio et
al. 2003; Vreeswijk et al. 2004; Fynbo et al. 2006; Jakobsson et al. 2006;
Prochaska et al. 2007; Fynbo et al. 2009; Ledoux et al. 2009; Savaglio 2010).
Therefore, comparing the chemical and physical properties of the strongest
QSO-DLAs to that of GRB-DLAs may provide clues to understand the nature of
these absorbers.

We present here a detailed study of the gas-phase abundances of metals, dust
and molecules in the QSO-DLA towards SDSS J 081634$+$144612, based on high
spectral resolution data. The paper is organized as follows. In Sect. 2 we
provide details of observations and data reduction. The hydrogen column
density of the DLA, the metal, dust and molecular content are discussed in
Sect. 3. The physical state of the H2 bearing gas component is discussed in
Sect. 4. In Sect. 5, we finally investigate the connection between QSO-DLAs
and GRB-DLAs.

##  2 Observations

We observed quasar SDSS J 081634$+$144612 twice, in September 2008 and April
2009, with the high-resolution Ultraviolet and Visual Echelle spectrograph
(UVES, Ballester et al. 2000) mounted on the ESO Kueyen VLT-UT2 8.2 m
telescope at Cerro Paranal, Chile. Observations have been performed under
programs 081.A-0334(A), PI. S. López in visitor mode, and 282.A-5030(A), PI.
P. Noterdaeme in service mode. Ten exposures were taken for a total of 12.4
hours exposure time: nine exposures using Dichroic 2 with a setting 437+760 nm
plus one 5400 s exposure with the red arm centered at 550 nm that covers the
Lyman-$\alpha$ absorption. A slit width of 1 arcsec and 2x2 pixel binning were
used, resulting in a spectral resolution of 50,000.

The quasar spectrum was reduced using the UVES pipeline (see e.g. Ledoux et
al. 2003 for details). The main characteristics of the pipeline are to perform
a precise inter-order background subtraction, especially for master flat-
fields, and to allow for an optimal extraction of the object signal rejecting
cosmic rays and performing sky subtraction at the same time. The pipeline
products were checked step by step. The wavelength scale of each reduced
spectrum was then converted to vacuum-heliocentric values and the spectra
rebinned to a constant wavelength step. No further rebinning was performed
during the analysis of the whole spectrum. Individual 1-D exposures were
scaled, weighted and combined together.

In order to derive the physical parameters of the absorption features, we fit
the metal absorption profiles with multiple Voigt profiles using VPFIT
(Carswell et al. 1987). The continuum level was obtained locally in the
vicinity of each metal absorption feature. Molecular hydrogen features were
fitted altogether using fit/lyman and after normalizing the corresponding
region of the Lyman-$\alpha$ forest. Atomic data for metal species and H2 are,
respectively, from Morton (2003) and Bailly et al. (2010). In the following,
solar abundances are taken from Lodders (2003). The origin of the velocity
scale ($v$ = 0 km s-1) is set at the redshift of the single C i component,
$z=3.28746$.

##  3 Abundances

###  3.1 H i and metal content

The neutral hydrogen column density was measured from the fit of the damping
wings of the Lyman-$\alpha$ absorption at $z=3.287$. We find $\log N$(H i)
(cm-2) = 22.0$\pm$0.10. The observed Damped Lyman-$\alpha$ absorption together
with the best fitted Voigt profile is shown in Figure 1. The dashed lines
indicate the profiles corresponding to $\log N$(H i) = 21.9 and 22.1.

We detect absorption lines of C i, C i⋆, Zn ii, Fe ii, Cr ii, Ni ii and Si ii,
spread over about 150 km s-1. As can be seen in Fig. 2, the absorption
profiles are not strongly saturated except may be for Si ii$\lambda$1808\. We
are therefore confident that our column density determinations are robust. The
fit to the absorption lines are overplotted on the Figure as red solid lines.
The singly ionized species are expected to be the dominant contributors to the
abundances of the corresponding elements in H i clouds with such high column
densities.

Voigt profile fitting is performed simultaneously for all the absorption lines
keeping the same number of components having same redshifts and Doppler
parameters for all singly ionized species. Note that Zn ii$\lambda$2026 is
blended with Mg i$\lambda$2026\. The contributions of the latter is taken into
account in the fits and found to have negligible influence on the derived N(Zn
ii).

Eight velocity components are necessary to model the profiles (see Fig. 2). We
report in Table 1 the results of the fits, column density and Doppler
parameter, for each of the components. Because of saturation effects, the Si
ii column density should be considered a lower limit. However, given the shape
of the absorption, we are confident that the true value cannot be much larger.
The column density of singly ionized iron, despite their blending, could be
reliably measured.

Although the profile decomposition may not be unique, three distinct clumps
can be identified (#1, 2 and 3 from blue to red) at mean redshifts of 3.28661,
3.28735 and 3.28814, and made of respectively, 3, 2 and 3 components. H2
absorption is detected in #1, which is the strongest clump in metal species,
but most of the H2 is found associated to the C i component in clump #2.
Unfortunately, we cannot determine $N$(H i) in each clump. The mean
metallicity222Metallicities are given relative to solar: ${\rm[X/H]}={\rm
log}(N_{\rm X}/N_{\rm HI})_{\rm DLA}-{\rm log}({\rm X/H})_{\odot}$ in the
cloud, derived by adding the column densities of the eight components are:
[Zn/H] = $-1.10\pm 0.10$, [Si/H] $\geq$ $-1.23\pm 0.10$, [Cr/H] = $-1.58\pm
0.10$, [Ni/H] = $-1.68\pm 0.10$ and [Fe/H] = $-1.58\pm 0.10$.

###  3.2 Dust

In the ISM of the Galaxy, zinc is virtually undepleted onto dust grains when
Si, Cr and Ni are. We find in the present DLA mean relative abundances:
[Si/Zn] = $-0.13\pm 0.03$, [Cr/Zn] = $-0.48\pm 0.02$, [Ni/Zn] = $-0.58\pm
0.02$ and [Fe/Zn] = $-0.48\pm 0.02$ indicating that the overall depletion of
Si, Cr, Ni and Fe is similar to what is seen in the gas from the halo of our
Galaxy (Welty et al. 1999). This is also typical of DLAs where H2 is detected
(Noterdaeme et al. 2008). From Fig. 3, which presents the depletion patterns
relative to zinc observed component by component, it is clear however that the
depletion is enhanced in the main H2-bearing component. This situation is
similar to that of the H2-bearing component towards Q 0013$-$004 (Petitjean et
al. 2002), where higher depletion factors are seen in the H2 components.

From the flux-calibrated SDSS spectrum, it is also possible to estimate the
reddening induced by the presence of dust in the DLA to the background QSO
light, following the method described in Noterdaeme et al. (2009b). In Fig. 4,
we show that the SDSS spectrum of J 081634$+$144612 is well matched with the
SDSS composite spectrum from Vanden Berk et al. (2001), shifted to the same
emission redshift and reddened using a SMC extinction law (Gordon et al. 2003)
at $z=3.286$ with E(B-V) = 0.05$\pm$0.06. The associated uncertainty is
obtained from the dispersion measured for a control sample of 163 SDSS QSOs
from Schneider et al. (2010) with emission redshift within $\pm 0.02$ to that
of J 081634$+$144612\. This means that there is no significant reddening of
the quasar J 081634$+$144612\. Overall, the measured extinction-to-dust ratio,
A${}_{\rm v}/N$(H i) $<5\times 10^{-23}$ mag cm2 (2 $\sigma$) is typical of
that of the general DLA population (Vladilo et al. 2008). This, together with
the presence of H2 in a component with higher depletion factor suggests that
appreciable fraction of H i may be associated with components that do not have
H2.

###  3.3 H2 content

Molecular hydrogen is detected in two distinct sub-systems at $z_{\rm abs}$ =
3.28667 and 3.28742, separated by $\sim$52 km s-1 with absorption lines from
rotational levels up to J = 3 (see Figure 5). The results of the fits to the
numerous absorption lines are given in Table 2. The $z_{\rm abs}$ = 3.28742
component alone contains about 90% of the total H2 column density in the
absorber, log $N$(H2) = 18.62, and coincides with the C i component. This is
expected because the energy of the photons that ionize C i is close to that of
photons that dissociate H2. The total H2 column density integrated over the
two components and all rotational levels is log $N$(H2) = 18.66 $\pm$ 0.27
(cm-2) corresponding to a molecular fraction of log $f$ = log 2$\times$
$N$(H2)/(2$\times$ $N$(H2) + $N$(H i)) = $-3.04\pm 0.37$ if we assume that the
totality of neutral hydrogen is associated with the H2 components. This value
is amongst the lowest observed in H2 bearing DLAs with metallicities [Zn/H]
$>$ $-1.3$ (Petitjean et al. 2006, Noterdaeme et al. 2008). This again may
indicate that appreciable fraction of H i may be associated with components
that do not have H2 (see also Noterdaeme et al. 2010, Srianand et al. 2010,
2012).

##  4 Physical state of the gas

###  4.1 Excitation of H2

From the detection of H2 in different rotational levels (J=0 to J=3, see Table
2), it is possible to put constraints on the physical state of the gas. The
excitation temperature $T_{0J}$ between rotational levels 0 and J is defined
as

$\frac{N(\rm J)}{N(0)}=\frac{g(\rm J)}{g(0)}e^{-E(\rm 0J)/kT_{0J}}\noindent$
(1)

where $g(\rm J)$ is the statistical weight of the rotational level J: $g(\rm
J)=(2J+1)(2I+1)$ with nuclear spin I = 0 for even J (para-H2) and I = 1 for
odd J (ortho-H2), $k$ is the Boltzmann constant, and $E(\rm 0J)$ is the energy
difference between level J and the ground state (J=0). If the excitation
processes are dominated by collisions, then the populations of the rotational
levels follow a Boltzmann distribution described by a unique excitation
temperature for all rotational levels. This is generally the case for low
rotational levels which have a de-excitation time scale larger than the
collision time-scale. Indeed, $T_{01}$ is a good indicator of the kinetic
temperature (Roy et al. 2006; Le Petit et al. 2006) especially in clouds
similar to the one we study here (log $N$(H2) $>$ 18). However, because of the
small energy difference between the J=0 and J=1 levels, the value of $T_{01}$
is very sensitive to uncertainties on $N$(H2,J=0) and $N$(H2,J=1) and the use
of higher rotational levels may help derive a better constraint on $T_{\rm
K}$. From Fig. 6, it can be seen that the population of J=0 to J=2 levels can
be described by a unique excitation temperature $T_{\rm ex}=69_{-8}^{+10}$ K
and $T_{\rm ex}=79_{-10}^{+14}$ K for the first and second component,
respectively.

These temperatures are slightly smaller than what was found in previous
studies of H2-bearing DLAs (e.g. Ledoux et al. 2003, $T\sim$ 90 to 180 K;
Srianand et al. 2005, $T\sim$ 153$\pm$78 K), but similar to what is measured
in the ISM of our Galaxy (77$\pm$17 K; Rachford et al. 2002) and in the
Magellanic Clouds (82$\pm$21 K; Tumlinson et al. 2002), where H i column
densities are also large. Note that, temperatures observed through high
latitude Galactic sight lines are also larger (124$\pm$8 K; Gillmon et al.
2006, or ranging from 81 K at log $N$(H2) = 20 to 219 K at log $N$(H2) = 14;
Wakker 2006).

The population of J=3 rotational level is in turn enhanced compared to the
Boltzmann distribution, which indicates the presence of additional excitation
processes such as UV pumping (e.g. Noterdaeme et al. 2007a) and/or turbulent
dissipation (as possibly indicated by the larger $b$-parameters for higher-J
levels seen by Noterdaeme et al. 2007b).

###  4.2 Density

Absorption lines produced by neutral carbon are seen only in one component at
$z_{\rm abs}$ = 3.28746 (see Figure 2) and are associated with the strongest
H2 component.

We used the relative populations of the two first sub-levels of the C i ground
state to derive the excitation temperature of the C i fine-structure level,
according to the Boltzmann equation (see Eq. 1). We have adopted the energy
difference between the C i excited (C i⋆: 2s22p2 3P1) and true ground-state
(2s22p2 3P0) levels, $\Delta E_{\rm eg}$ = 23.6 K. The population ratio
$N$(J=1)/$N$(J=0) of the C i fine-structure level corresponds to an excitation
temperature of $T_{\rm ex}$ = 15.4$\pm$0.1 K. This is higher than the
temperature expected in the case the excitation is dominated by the cosmic
microwave background radiation ($T_{\rm CMBR}$ = 11.7 K at $z=3.287$)
indicating that excitation by collisions is important. Using the results shown
in fig. 12 of Srianand et al. (2005), we derive that the particle density,
$n_{\rm H}$, is in the range 50-80 cm-3.

##  5 Discussion

We have presented a detailed analysis of a QSO-DLA system with an extremely
large column density, $\log N($H i$)=22.0\pm 0.10$, at $z_{\rm abs}=3.287$
towards the quasar SDSS J 081634$+$144612\. The velocity structure of
associated metal absorption lines indicates the presence of 8 components
grouped into three sub-systems centered at $z=3.28661$, 3.28735 and 3.28814
respectively, spanning $\sim 115$ km s-1. C i is detected in the $z=3.28735$
sub-system whilst H2 is detected in both the $z=3.28661$ and 3.28735 sub-
systems. From the H2 excitation, we derive a kinetic temperature of $T_{\rm
K}\sim 75$ K and the observed column density ratio $N($C i$)^{\star}/N($C i$)$
yields a particle density in the range $n_{\rm H}\sim 50-80$ cm-3. The
depletion of metals onto dust grains measured in the strongest H2 component
located at $z_{\rm abs}=3.28735$ is similar to what is observed in the disc of
the Galaxy. All this shows that this system, apart from having unusually large
N(H i), has properties consistent with that of a typical H2-bearing DLA (see
Ledoux et al. 2003; Noterdaeme et al. 2008).

While log $N($H i$)\geq 22$ DLAs are very rarely seen in front of QSOs,
several have already been detected in the optical afterglow spectrum and at
the redshift of long-duration $\gamma$-ray bursts. Two of them (towards GRB
050401, GRB 080607 and GRB 060926) even have log $N($H i$)>22.5$ (Watson et
al. 2006; Prochaska et al. 2009; Jakobsson et al. 2006). It is not surprising
to observe a strong DLA at the redshift of GRBs since these objects are
expected to be associated with star-forming regions where the gas is likely to
be found in large quantities. Although QSO-DLAs are located close to regions
where stars form as indicated by the presence of metals, the detection of C
ii⋆ absorption and galaxy-like kinematics (Wolfe et al. 2003), their exact
nature is not completely elucidated. Some should be associated with the ISM of
galaxies especially when molecules are detected (Noterdaeme et al. 2008),
others are probably located in the outskirts of galactic haloes (Møller et al.
2002; Møller et al. 2004; Fox et al. 2007; Pontzen et al. 2008, Rauch et al.
2008; Rahmani et al. 2010; Fynbo et al. 2010, 2011).

The difference between the populations of GRB-DLAs and QSO-DLAs is apparent
because (i) the mean H i column density is higher in GRBs than in DLAs
reaching easily well beyond $10^{21.5}$ cm-2 in the former case (see, e.g.,
Jakobsson et al. 2006; Fynbo et al. 2009) whilst QSO-DLA with log $N($H
i$)\geq 22$ are very rare (Noterdaeme et al. 2009b), and (ii) the mean
metallicity is larger for GRB-DLAs (Savaglio et al. 2006; Fynbo et al. 2006;
Prochaska et al. 2007; Fynbo et al. 2008), about 0.1 solar at $z>2$ (to be
compared to $\sim 0.03$ solar for intervening DLAs). Note that molecules (H2,
CO) have been detected in a number of QSO-DLAs (Noterdaeme et al. 2008, 2011,
Srianand et al. 2008), whereas they are rarely seen in GRB-DLAs (Ledoux et al.
2009). This may be a consequence of small number statistics however (see Fynbo
et al. 2006 and Prochaska et al. 2009) and possibly of inadequate data as high
spectral resolution in the blue is usually needed (see Ledoux et al. 2009).

If these differences exist when comparing the overall populations, they may
not be that apparent if we restrict ourselves to high H i column density
systems. This is why it is interesting to compare the properties of SDSS J
081634$+$144612 with those of GRB-DLAs. In Fig. 7, we plot the logarithm of
the H i column density versus metallicity for QSO-DLAs where H2 is not
detected (open circles), QSO-DLAs where H2 is detected (filled circles), the
same for GRB-DLAs (squares) and SDSS J 081634$+$144612 (filled diamond). It
can be seen that there is a lack of systems with both a high metallicity and a
high column density. This is well known for QSO-DLAs and could be a
consequence of these DLAs being missed because of the high induced attenuation
which makes the QSO drop out of the sample (e.g. Boissé et al. 1998). Altough
GRB afterglows are for a little while much brighter than quasars, the presence
of a dust-bias could also affect their statistics (see e.g. Fynbo et al. 2009;
Ledoux et al. 2009; and Greiner et al. 2011). A possibility is that GRB-DLA
metallicities could be higher than measured as often only lower limits are
derived from intermediate resolution observations (see Prochaska 2006,
Petitjean & Vergani, 2011). This can however probably not explain this lack of
systems completely. SDSS J 081634$+$144612 is located at the limit of the
region where systems are missing and within the region where GRB-DLAs are
located. In Fig. 8, the logarithm of the H i column density is plotted for the
same systems versus the depletion of iron onto dust grains. We have scaled the
depletion of chromium in SDSS J 081634$+$144612\. It can be seen here again
that the DLA towards SDSS J 081634$+$144612 is well within the region where
GRB-DLAs are located. Therefore, our study indicates that extremely large H i
column density DLAs found toward QSOs have properties similar to those of GRB-
DLAs.

Following Schaye (2001), Krumholz et al (2009) proposed a radiation-
insensitive model –hence applying to both QSO and GRB-DLAs– where the lack of
high-$N$(H i), high-metallicity is explained by the conversion from atomic to
molecular gas. Here, the physical conditions in the $H_{2}$-bearing cloud
indicate that we are still observing diffuse gas. This is not in tension with
the above model since dense, cold and molecular gas is expected to have a
small cross section and is not easily intercepted by the line-of-sight.
Interestingly, a fully molecular cloud has been observed in the case of the
$\log N$(H i) = 22.7 DLA associated to GRB080607 (Prochaska et al. 2009),
which could be observed very quickly ($<$1 h) after the burst. Therefore,
while the absorption properties of high-$N$(H i) GRB and QSO-DLAs appear to be
similar, detecting fully molecular clouds will remain challenging in the case
of QSOs, because of the random distribution of the lines-of-sight and the high
induced extinction.

Very little is known about GRB host galaxies at high redshift ($z>2$, Savaglio
et al. 2009). Cosmological simulations show that GRB-DLAs are predominantly
associated with haloes of mass 10${}^{10}<M_{\rm vir}$/$M_{\odot}<10^{12}$, an
order of magnitude larger than the galaxies responsible for the bulk of QSO-
DLAs (Pontzen et al. 2010; see however Barnes & Haehnelt 2010). But what is
true for the overall QSO-DLA population does not hold for its high column
density end. We have shown here that DLAs with the highest H i column
densities, seem to have absorption properties similar to that of GRB-DLAs. It
would be most interesting to search for emission lines associated to these
DLAs which have probably small impact parameters (see e.g. Noterdaeme et al.
2012)333The galaxy responsible for the recently found $\log N($H i$)\sim 22$
DLA towards J 1135$-$0010 was detected at $b\approx 0.1$ arcsec from the
background QSO (Noterdaeme et al. 2012). In this particular case, Kukarni et
al. (2012) demonstrated that detecting the Lyman-$\alpha$ emission is even
possible from UVES data. Here, the DLA is covered at the edge of two UVES
echelle orders and possibly contaminated by scattered light in the red arm,
preventing us from putting any meaningful limit on the Ly-$\alpha$ flux
–within the slit. Follow-up observations specifically tuned to the search of
emission lines is thus desirable (see e.g. Fynbo et al. 2010, 2011, Péroux et
al. 2012).

Note that the above conclusion is probably not very surprising as high H i
column densities likely arise in gas located in the inner regions of star
forming galaxies of moderate attenuation. This idea should be investigated
with larger samples of both QSO and GRB-DLAs with high column densities. The
BOSS survey (Eisenstein et al. 2011) will soon increase the number of such
QSO-DLAs by an order of magnitude.

We thank the anonymous referee for helpful comments and suggestions which
improved this paper. PPJ and RS acknowledge the support of the Indo-French
Centre for the Promotion of Advanced Research (Centre Franco-Indien pour la
Promotion de la Recherche Avancée) under contract no. 4304-2. S. L. is
supported by FONDECYT grant No. 1100214.

## References

  * Ballester et al. (2000) Ballester, P., Modigliani, A., Boitquin, O., Cristiani, S., Hanuschik, R., Kaufer, A., & Wolf, S. 2000, The Messenger, 101, 31
  * Barnes & Haehnelt (2010) Barnes, L. A. & Haehnelt, M. G., 2010, MNRAS 403, 870
  * (3) Bailly, D., Salumbides, E.J., Vervloet, M., Ubachs, W. Mol. Phys. (2010) 108, 827
  * Boisse et al. (1998) Boisse, P., Le Brun, V., Bergeron, J., & Deharveng, J.-M. 1998, A&A, 333, 841
  * Carswell et al. (1987) Carswell, R. F., Webb, J. K., Baldwin, J. A., & Atwood, B. 1987, ApJ, 319, 709
  * (6) Eisenstein, D. J., et al., 2011, AJ, 142, 72
  * (7) Fox, A. J., Petitjean, P., Ledoux, C., & Srianand, R. 2007, A&A, 465, 171
  * Fynbo et al. (2006) Fynbo, J. P. U., Starling, R. L. C., Ledoux, C., et al. 2006, A&A, 451, L47
  * Fynbo et al. (2008) Fynbo, J. P. U., Prochaska, J. X., Sommer-Larsen, J., Dessauges-Zavadsky, M., & Møller, P. 2008, ApJ, 683, 321
  * Fynbo et al. (2009) Fynbo, J. P. U., Jakobsson, P., Prochaska, J. X., et al. 2009, ApJS, 185, 526
  * Fynbo et al. (2010) Fynbo, J. P. U., Laursen, P., Ledoux, C., et al. 2010, MNRAS, 408, 2128
  * Fynbo et al. (2011) Fynbo, J. P. U., Ledoux, C., Noterdaeme, P., et al. 2011, MNRAS, 413, 2481
  * Gillmon et al. (2006) Gillmon, K., Shull, J. M., Tumlinson, J., & Danforth, C. 2006, ApJ, 636, 891
  * Gordon et al. (2003) Gordon, K. D., Clayton, G. C., Misselt, K. A., Landolt, A. U., & Wolff, M. J. 2003, ApJ, 594, 279
  * Greiner et al. (2011) Greiner, J., Krühler, T., Klose, S., et al. 2011, A&A, 526, A30
  * Guimarães et al. (2009) Guimarães, R., Petitjean, P., de Carvalho, R. R., et al. 2009, A&A, 508, 133
  * Jakobsson et al. (2006) Jakobsson, P., Fynbo, J. P. U., Ledoux, C., et al. 2006, A&A, 460, L13
  * (18) Krumholz, M. R., Ellison, S. L., Prochaska, J. X., Tumlinson, J., 2009, ApJ, 701, L12
  * (19) Kulkarni, V. P., Meiring, J., Debopam, S., Péroux, C., York, D. G., Khare, P., & Lauroesch, J. T. 2012, ArXiv:1202.0882
  * Ledoux et al. (2003) Ledoux, C., Petitjean, P., & Srianand, R. 2003, MNRAS, 346, 209
  * (21) Ledoux, C., Petitjean, P., & Srianand, R. 2006, ApJ, 640, L25
  * Ledoux et al. (2009) Ledoux, C., Vreeswijk, P. M., Smette, A., et al. 2009, A&A, 506, 661
  * (23) Le Petit, F., Nehmé, C., Le Bourlot, J., & Roueff, E. 2006, ApJS, 164, 506
  * (24) Lodders, K. 2003, ApJ, 591, 1220
  * Möller et al. (2002) Møller, P., Warren, S. J., Fall, S. M., Fynbo, J. U., & Jakobsen, P. 2002, ApJ, 574, 51
  * Möller et al. (2004) Möller, P., Fynbo, J. P. U., & Fall, S. M. 2004, A&A, 422, L33
  * Morton (2003) Morton, D. C. 2003, ApJS, 149, 205.
  * Noterdaeme et al. (2007) Noterdaeme, P., Petitjean, P., Srianand, R., Ledoux, C., & Le Petit, F. 2007, A&A, 469, 425
  * Noterdaeme et al. (2007) Noterdaeme, P., Ledoux, C., Petitjean, P., et al. 2007, A&A, 474, 393
  * Noterdaeme et al. (2008) Noterdaeme, P., Ledoux, C., Petitjean, P., & Srianand, R. 2008, A&A, 481, 327
  * Noterdaeme et al. (2009) Noterdaeme, P., Ledoux, C., Srianand, R., Petitjean, P., & Lopez, S. 2009, A&A, 503, 765
  * Noterdaeme et al. (2009b) Noterdaeme, P., Petitjean, P., Ledoux, C., & Srianand, R. 2009b, A&A, 505, 1087
  * Noterdaeme et al. (2010) Noterdaeme, P., Petitjean, P., Ledoux, C., et al. 2010, A&A, 523, A80
  * Noterdaeme et al. (2011) Noterdaeme, P., Petitjean, P., Srianand, R., Ledoux, C., & López, S. 2011, A&A, 526, L7
  * Noterdaeme et al. (2012) Noterdaeme, P. , Laursen, P. , Petitjean, P., Vergani, S. D., Maureira, M.-J., Ledoux, C., Fynbo, J. P. U., López, S., & Srianand, R. 2012, ArXiv:1202.0280
  * Péroux et al. (2012) Péroux, C., Bouché, N., Kulkarni, V. P., York, D. G. & Vladilo, G. 2012, MNRAS, 419, 3060
  * Petitjean et al. (1993) Petitjean, P., Webb, J. K., Rauch, M., Carswell, R. F., & Lanzetta, K. 1993, MNRAS, 262, 499
  * Petitjean et al. (2002) Petitjean, P., Srianand, R., & Ledoux, C. 2002, MNRAS, 332, 383
  * Petitjean (2006) Petitjean, P., Ledoux, C., Noterdaeme, P., & Srianand, R. 2006, A&A, 456, L9
  * (40) Petitjean, P., & Vergani, S. D. 2011, CR Phys. 12, 288
  * Pontzen et al. (2008) Pontzen, A., Governato, F., Pettini, M., et al. 2008, MNRAS, 390, 1349
  * Pontzen et al. (2010) Pontzen, A., Deason, A., Governato, F., et al. 2010, MNRAS, 402, 1523
  * Prochaska (2006) Prochaska, J. X. 2006, ApJ, 650, 272
  * Prochaska et al. (2007) Prochaska, J. X., Chen, H.-W., Dessauges-Zavadsky, M., & Bloom, J. S. 2007, ApJ, 666, 267
  * Prochaska et al. (2008) Prochaska, J. X., Chen, H.-W., Wolfe, A. M., Dessauges-Zavadsky, M., & Bloom, J. S. 2008, ApJ, 672, 59
  * Prochaska & Wolfe (2009) Prochaska, J. X., & Wolfe, A. M. 2009, ApJ, 696, 1543
  * Prochaska et al. (2009) Prochaska, J. X., Sheffer, Y., Perley, D. A., et al. 2009, ApJ, 691, L27
  * Rachford et al. (2002) Rachford, B. L., Snow, T. P., Tumlinson, J., et al. 2002, ApJ, 577, 221
  * Rahmani et al. (2010) Rahmani, H., Srianand, R., Noterdaeme, P., & Petitjean, P. 2010, MNRAS, 409, L59
  * (50) Rauch, M., Haehnelt, M., Bunker, A., et al., 2008, ApJ, 681, 856
  * (51) Roy, N., Chengalur, J. N., & Srianand, R. 2006, MNRAS, 365, L1
  * Savaglio et al. (2003) Savaglio, S., Fall, S. M., & Fiore, F. 2003, ApJ, 585, 638
  * Savaglio (2006) Savaglio, S. 2006, New Journal of Physics, 8, 195
  * Savaglio (2010) Savaglio, S. 2010, IAU Symposium, 265, 139
  * (55) Savaglio, S., Glazebrook, K., & Le Borgne, D. 2009, ApJ, 691, 182
  * Schneider et al. (2010) Schneider, D. P., Richards, G. T., Hall, P. B., et al. 2010, AJ, 139, 2360
  * Schaye (2001) Schaye, J. 2001, ApJ, 562, L95
  * (58) Srianand, R., Petitjean, P., Ledoux, C., Ferland, G., & Shaw, G. 2005, MNRAS, 362, 549
  * (59) Srianand, R., Noterdaeme, P., Ledoux, C., & Petitjean, P. 2008, A&A, 482, 39
  * Srianand et al. (2010) Srianand, R., Gupta, N., Petitjean, P., Noterdaeme, P., & Ledoux, C. 2010, MNRAS, 405, 1888
  * Srianand et al. (2012) Srianand, R., Gupta, N., Petitjean, P., et al. 2012, MNRAS, 421, 65
  * (62) Tumlinson, J., Shull, J. M., Rachford, B. L., et al. 2002, ApJ, 566, 857
  * Vanden Berk et al. (2001) Vanden Berk, D. E., Richards, G. T., Bauer, A., et al. 2001, AJ, 122, 549
  * Vladilo et al. (2008) Vladilo, G., Prochaska, J. X., & Wolfe, A. M. 2008, A&A, 478, 701
  * Vreeswijk et al. (2004) Vreeswijk, P. M., Ellison, S. L., Ledoux, C., et al. 2004, A&A, 419, 927
  * (66) Wakker, B. P. 2006, ApJS, 163, 282
  * Watson et al. (2006) Watson, D., Fynbo, J. P. U., Ledoux, C., et al. 2006, ApJ, 652, 1011
  * Welty et al. (1999) Welty, D. E., Frisch, P. C., Sonneborn, G., & York, D. G. 1999, ApJ, 512, 636
  * (69) Wolfe, A. M., Prochaska, J. X., & Gawiser, E. 2003, ApJ, 593, 215
  * Zwaan & Prochaska (2006) Zwaan, M. A., & Prochaska, J. X. 2006, ApJ, 643, 675

Figure 1: H i Lyman-$\alpha$ profile of the DLA at $z=3.286$ toward QSO SDSS J 081634$+$144612\. The overplotted solid line and accompanying dashed lines correspond to the best fit solution log $N$(H i) = 22.0$\pm$0.10. The origin of the velocity scale is taken at $z=3.287$. Figure 2: Observed absorption profiles of C i, C i*, Zn ii, Fe ii, Cr ii, Ni ii, Si ii together with fitted profiles. The dashed vertical lines indicate the positions of the velocity components. The origin of the velocity scale is taken at $z=3.287456$, the redshift of the C i component. Regions affected by blends (see Fe ii lines as well as the reddest clump of Cr ii$\lambda$2066) are not considered in the fitting process. Additional absorption seen at +150 km s-1 the C i⋆ $\lambda$1560.6 panel and in the red wing of C i$\lambda$1656 and C i⋆ $\lambda$1657.9 are due to C i⋆⋆. Figure 3: Depletion pattern of elements relative to zinc measured in individual components in the DLA toward SDSS J 081634$+$144612\. The points are slightly shifted along the x-axis according to their position in the system (for clarity purpose only). The filled circle indicates the component associated with the strongest H2 absorption. The dotted, dashed and continuous lines represent the typical relative abundances observed in, respectively, cold or warm gas in the Galactic disk and diffuse gas in the Galactic Halo, from Welty et al. (1999).  Figure 4:  Left: The SDSS spectrum of J 081634$+$144612 (black) is shown together with the unreddened SDSS composite (grey) and the same reddened using a SMC extinction law and E(B-V) = 0.05 (red). Right: Distribution of E(B-V) measured for a control sample of 163 QSOs within $\Delta z=\pm 0.02$ from SDSS J 081634$+$144612\. The arrow indicate the position of the latter. Figure 5: Portions of the SDSS J 081634$+$144612 normalized spectrum. The best fit to the H2 absorption lines in several Lyman bands (0-0 to 4-0) is superimposed onto the spectrum, with the corresponding uncertainty represented by the shaded area. The fit parameters are given in Table 2. The blue and green labels indicate the branch and the rotational level for the bluest and reddest component of H2, respectively. Figure 6: H2 excitation diagram for the 2 components observed toward SDSS J 081634$+$144612\. Triangles correspond to $z_{\rm abs}$ = 3.28667 and squares to $z_{\rm abs}$ = 3.28742. The column density $N_{\rm J}$ divided by the statistical weight, $g_{\rm J}$, is plotted for the J = 0 up to J = 3 H2 rotational levels on a logarithmic scale against the excitation energy, $E_{\rm J}$, in K. The J=0 to J=2 points have been fitted with straight lines using Eq. 1 giving the excitation temperatures $T_{\rm ex}^{012}$ indicated in Table 2. Figure 7: Logarithm of the total neutral hydrogen column density versus metallicity. Circles correspond to QSO-DLAs (Noterdaeme et al. 2008), squares to GRB-DLAs (Prochaska et al. 2009), triangles to GRB-DLAs(Ledoux et al. 2009), inverted triangle to the QSO-DLA towards SDSS J 113520$+$001053 (Noterdame et al. 2012) and the diamond indicates our measurement for the QSO-DLA towards SDSS J 081634$+$144612\. Filled symbols indicate systems in which H2 is detected, the filled square corresponds to the GRB080607 (Prochaska et al. 2009). Figure 8: Logarithm of the total neutral hydrogen column density versus depletion. Circles correspond to QSO-DLAs (Noterdaeme et al. 2008), squares to GRB-DLAs (Prochaska et al. 2009), triangles to GRB-DLAs (Ledoux et al. 2009), inverted triangle to the QSO-DLA towards SDSS J 113520$+$001053 (Noterdame et al. 2012) and the diamond indicates our measurement for the QSO-DLA towards SDSS J 081634$+$144612\. Filled symbols indicate systems in which H2 is detected, the filled square corresponds to the GRB080607 (Prochaska et al. 2009) . Table 1: Results of Voigt profile fitting analysis. $z$ | $v$ | $b$ |  $\log N$ (cm-2)
---|---|---|---
|  (km s-1) |  (km s-1) |  C i |  C i⋆ |  C i⋆⋆ |  Si ii |  Cr ii |  Ni ii |  Zn ii |  Fe ii
3.286481 | -68 |  8.1$\pm$0.2 |  |  |  |  15.73$\pm$0.03 |  13.43$\pm$0.02 |  13.87$\pm$0.01 |  13.04$\pm$0.02 |  15.09$\pm$0.04
3.286746 | -50 |  8.2$\pm$0.3 |  |  |  |  15.99$\pm$0.04 |  13.71$\pm$0.02 |  14.15$\pm$0.01 |  13.12$\pm$0.02 |  15.48$\pm$0.03
3.286998 | -32 |  7.4$\pm$1.7 |  |  |  |  14.90$\pm$0.10 |  12.68$\pm$0.11 |  13.18$\pm$0.10 |  12.19$\pm$0.10 |  14.79$\pm$0.04
3.287260 | -14 |  8.7$\pm$1.0 |  |  |  |  14.99$\pm$0.05 |  12.83$\pm$0.06 |  13.44$\pm$0.04 |  12.40$\pm$0.05 |  14.85$\pm$0.04
3.287456 | 0 |  7.2$\pm$0.2 |  13.43$\pm$0.01 |  13.24$\pm$0.02 |  12.47$\pm$0.07 |  14.90$\pm$0.04 |  12.63$\pm$0.08 |  13.33$\pm$0.03 |  12.40$\pm$0.07 |  14.57$\pm$0.06
3.288098 | +45 |  20.6$\pm$0.8 |  |  |  |  15.29$\pm$0.04 |  13.23$\pm$0.05 |  13.73$\pm$0.03 |  12.45$\pm$0.06 |  14.91$\pm$0.07
3.288169 | +50 |  4.4$\pm$0.6 |  |  |  |  14.89$\pm$0.07 |  12.69$\pm$0.09 |  13.23$\pm$0.05 |  11.73$\pm$0.16 |  14.41$\pm$0.13
3.288345 | +62 |  6.1$\pm$3.7 |  |  |  |  14.30$\pm$0.25 |  |  12.30$\pm$0.48 |  11.34$\pm$0.38 |  14.82$\pm$0.05
Total |  13.43$\pm$0.01 |  13.24$\pm$0.02 |  12.47$\pm$0.07 |  16.31$\pm$0.01 |  14.07$\pm$0.02 |  14.54$\pm$0.01 |  13.53$\pm$0.01 |  15.89$\pm$0.02
Table 2: Molecular hydrogen column densities and excitation temperatures

$z_{\rm abs}$ |  $v$ 1 | J | log $N($H2,J) 2 | $b$ | $T_{\rm ex}$
---|---|---|---|---|---
| (km s-1) |  | (cm-2) | (km s-1) | (K)
3.28667 3 | 55.0 | 0.0 | 16.59$\pm$0.50 | $2_{-1}^{+2}$ | $T_{\rm ex}^{012}=69_{-8}^{+10}$
|  | 1 | 17.55 $\pm$0.30 | $2_{-1}^{+2}$
|  | 2 | 14.71 $\pm$0.20 | $8.3_{-0.4}^{+0.4}$
|  | 3 | 15.13 $\pm$0.10 | $6.5_{-0.4}^{+0.4}$ | $T_{\rm ex}^{03}=158_{-28}^{+44}$
3.28742 4 | 2.5 | 0 | 18.19 $\pm$0.35 | $2_{-1}^{+2}$ | $T_{\rm ex}^{012}=79_{-10}^{+14}$
|  | 1 | 18.41 $\pm$0.20 | $2_{-1}^{+2}$
|  | 2 | 16.21 $\pm$0.25 | $8.3_{-0.4}^{+0.4}$
|  | 3 | 15.75 $\pm$0.10 | $6.5_{-0.4}^{+0.4}$ | $T_{\rm ex}^{03}=117_{-12}^{+16}$

1 With respect to C i.
2 The errors on the H2 column densities correspond to the best fits using the
range of $b$-values.
3 Total log $N$(H2)= 17.60.
4 Total log $N$(H2)= 18.62.


# Outerplanar graphs with positive Lin-Lu-Yau curvature

George Brooks Fadekemi Osaye Anna Schenfisch Zhiyu Wang Jing Yu University of
South Carolina, Columbia, SC, USA. (ghbrooks@email.sc.edu).Alabama State
University, Montgomery, AL, USA. (fosaye@alasu.edu). Eindhoven University of
Technology, Eindhoven, Netherlands. (a.k.schenfisch@tue.nl). Louisiana State
University, Baton Rouge, LA, USA. (zhiyuw@lsu.edu). School of Mathematics,
Georgia Institute of Technology, Atlanta, GA, USA. (jingyu@gatech.edu).

###### Abstract

In this paper, we show that all simple outerplanar graphs $G$ with minimum
degree at least $2$ and positive Lin-Lu-Yau Ricci curvature on every edge have
maximum degree at most $9$. Furthermore, if $G$ is maximally outerplanar, then
$G$ has at most $10$ vertices. Both upper bounds are sharp.

##  1 Introduction

Ricci curvature plays a crucial role in the geometric analysis of Riemannian
manifolds. Roughly speaking, it measures the degree to which the geometry of a
metric tensor differs locally from that of an Euclidean space. Curvature in
the continuous setting has been studied in depth throughout the past 200
years, and more recent interest has arisen in establishing analogous results
in metric spaces. The definition of the (non-combinatorial) Ricci curvature on
metric spaces first came from the Bakry and Emery notation [1] who defined the
“lower Ricci curvature bound” through the heat semigroup $(P_{t})_{t\geq 0}$
on a metric measure space. Ollivier [21] defined the coarse Ricci curvature of
metric spaces in terms of how much small balls are closer (in Wasserstein
transportation distance) then their centers are. This notion of coarse Ricci
curvature on discrete spaces was also made explicit in the Ph.D. thesis of
Sammer [23]. The first definition of Ricci curvature on graphs was introduced
by Chung and Yau in [5]. To obtain a good log-Sobolev inequality, they defined
Ricci-flatness in graphs. Later, Lin and Yau [16] gave a generalization of the
lower Ricci curvature bound in the framework of graphs. In [15], Lin, Lu, and
Yau modified Ollivier’s Ricci curvature [21] and defined a new variant of
Ricci curvature on graphs, which does not depend on the idleness of the random
walk. For other variants of curvature on discrete spaces, see e.g., see [7, 8]
and the references therein.

In this paper, we are interested in studying planar and outerplanar graphs
with positive curvature. A planar graph is a graph that can be embedded in the
plane, i.e., it can be drawn on the plane in such a way that its edges
intersect only at their endpoints. Infinite planar graphs are often treated as
the discrete version of noncompact simply connected $2$-dimensional manifolds.
Thus it’s natural to consider the ‘curvature’ of planar graphs. A notion of
curvature, previously more extensively studied in graph theory, is the
combinatorial curvature, which is defined on the vertices of a graph. Given a
graph $G$ that is $2$-cell embedded in a surface without loops or multiple
edges, the combinatorial curvature of $v\in V(G)$ is defined as
$K(v):=1-\frac{d_{v}}{2}+\displaystyle\sum_{\sigma\in
F(v)}\frac{1}{|\sigma|}$, where $d_{v}$ denotes the degree of $v$, $F(v)$ is
the multiset of faces touching $x$ and $|\sigma|$ is the size of the face
$\sigma$. A graph $G$ is said to have positive combinatorial curvature
everywhere if $\phi(v)>0$ for all $v\in V(G)$. Higuchi [11] conjectured that
that if $G$ is a simple connected graph embedded into a $2$-sphere with
positive combinatorial curvature everywhere and minimum degree $\delta(G)\geq
3$, then $G$ is finite. Higuchi’s conjecture was verified by Sun and Yu [25]
for cubic planar graphs and resolved by DeVos and Mohar [6]. In particular,
DeVos and Mohar showed the following theorem.

######  Theorem 1.

[6] Suppose $G$ is a connected simple graph embedded into a $2$-dimensional
topological manifold $\Omega$ without boundary and $G$ has minimum degree at
least $3$. If $G$ has positive combinatorial curvature, then it is finite and
$\Omega$ is homeomorphic to either a $2$-sphere or a projective plane.
Moreover, if $G$ is not a prism, an antiprism, or one of their projective
plane analogues, then $|V(G)|\leq 3444$.

The minimum possible constants for $|V(G)|$ in Theorem 1 for $G$ embedded in a
$2$-sphere and projective plane respectively was studied in [22, 19, 4, 26,
20]. In particular, Nicholson and Sneddon [19] gave examples of positively
(combinatorially) curved graphs with $208$ vertices embedded into a
$2$-sphere. The upper bound on $|V(G)|$ was recently settled by Ghidelli [10].
Planar graphs with nonnegative combinatorial curvature have also be
extensively studied (see [12] and the references within). Tight upper bounds
on certain graph classes with positive Lin-Lu-Yau curvature everywhere are
also obtained in [9].

Recently, Lu and Wang [17] initiated the study of the order of planar graphs
with positive Lin-Lu-Yau curvature (LLY curvature for short), which is defined
on the vertex pairs of a graph. A graph $G$ is called positively LLY-curved if
it has positive Lin-Lu-Yau curvature on every vertex pair of $G$. For brevity
of the introduction, we give the definition of the Lin-Lu-Yau curvature in
Section 2. In [17], Lu and Wang established an analogue of DeVos and Mohar’s
result in the context of Lin-Lu-Yau curvature. In particular, they showed the
following two theorems.

######  Theorem 2.

[17] Let $G$ be a simple positively LLY-curved planar graph $G$ with
$\delta(G)\geq 3$. Then the maximum degree $\Delta(G)\leq 17$.

######  Theorem 3.

[17] If $G$ is a simple positively LLY-curved planar graph with minimum degree
at least $3$, then $G$ is finite. In particular, $|V(G)|\leq 17^{544}$.

The question of determining a sharp upper bound on the order of a positively
LLY-curved planar graphs is still open and seems hard. In this paper, we
obtain sharp upper bounds on the maximum degree and order of a positively LLY-
curved (maximal) outerplanar graph. A graph is outerplanar if it admits a
planar embedding such that all vertices lie on the outer face. A _maximal
outerplanar_ graph is an edge maximal outerplanar graph. We first show a sharp
upper bound on the maximum degree of a positively LLY-curved outerplanar
graph.

######  Theorem 4.

Let $G$ be a simple positively LLY-curved outerplanar graph with
$\delta(G)\geq 2$. Then $\Delta(G)\leq 9$ and the upper bound is sharp.

Using Theorem 4 and additional degree constraints shown in Section 4, we
obtain a sharp upper bound on the order of positively LLY-curved maximal
outerplanar graph.

######  Theorem 5.

Let $G$ be a positively LLY-curved maximal outerplanar graph. Then $|V(G)|\leq
10$ and the upper bound is sharp.

The upper bounds in Theorem 4 and Theorem 5 are both achieved by the fan graph
on $10$ vertices (see Figure 1).

Figure 1: Fan graph on 10 vertices with curvature of each edge computed by
SageMath.

For convenience, in the rest of the paper, we simply say a graph $G$ is
positively curved if it is positive LLY-curved, and we simply denote
$\kappa_{LLY}(x,y)$ by $\kappa(x,y)$.

Notation and Terminology. Given a graph $G$ and $x\in V(G)$, we use $N(x)$ to
denote the neighborhood of $x$, i.e., $N(x)=\\{y\in V(G):xy\in E(G)\\}$. Let
$d_{x}$ denote the degree of $x$, i.e., $d_{x}=|N(x)|$. Let
$N[x]:=N(x)\cup\\{x\\}$. Given $x,y\in V(G)$, let $N(x,y)$ denote the common
neighborhood of $x$ and $y$, i.e., $N(x,y):=N(x)\cap N(y)$. Moreover, given
$S\subseteq V(G)$, define $N(S):=\\{x\in V(G):xs\in E(G)\text{ for some }s\in
S\\}$ and $E(x,S):=\\{xs\in E(G):s\in S\\}$. Throughout the paper, for $xy\in
E(G)$, we will consider the _local configuration_ $H_{xy}\subseteq G$, the
induced subgraph of $G$ defined by $H_{xy}=G[N[x]\cup N[y]].$ For $x,y\in
V(G)$, we use $d(x,y)$ to denote the number of edges in a shortest path
between $x$ and $y$. Given an outerplanar graph $G$ and an edge $e$, we call
$e$ an _exterior edge_ if it lies on the boundary of the outer face of $G$,
and we call $e$ an _interior edge_ otherwise.

##  2 Lin-Lu-Yau Ricci curvature

In this section, we define the Lin-Lu-Yau Ricci curvature. We closely follow
the notation of [17, 21]. Let $m_{1}$ and $m_{2}$ be two probability
distributions on $V(G)$. That is, for $i=1,2$, we have $m_{i}:V(G)\to[0,1]$
such that $\sum_{x\in V(G)}m_{i}(x)=1$. A _coupling_ between $m_{1}$ and
$m_{2}$, is a map $A:V(G)\times V(G)\to[0,1]$ with finite support such that
$\sum_{y\in V(G)}A(x,y)=m_{1}(x)$ and $\sum_{x\in V(G)}A(x,y)=m_{2}(y)$. The
_transportation distance_ between $m_{1}$ and $m_{2}$ is defined as

$W(m_{1},m_{2})=\inf_{A}\sum_{x,y\in V(G)}A(x,y)\,d(x,y),$ (1)

where the infimum is taken over all couplings $A$ between $m_{1}$ and $m_{2}$.
By the duality theorem of a linear optimization problem, the transportation
distance can also be written as

$W(m_{1},m_{2})=\sup_{f\in Lip(1)}\displaystyle\sum_{x\in
V(G)}f(x)\left(m_{1}(x)-m_{2}(x)\right),$ (2)

where the supremum is taken over all $1$-Lipschitz functions $f$. A random
walk $m$ on a graph $G=(V,E)$ is defined as a family of probability measures
$\\{m_{v}(\cdot)\\}_{v\in V(G)}$ such that $m_{v}(u)=0$ for all $uv\notin
E(G)$. It follows that $m_{v}(u)\geq 0$ for all $v,u\in V(G)$ and $\sum_{u\in
N[v]}m_{v}(u)=1$. For $v\in V(G)$, consider the $\alpha$-lazy random walk
$\\{m_{v}^{\alpha}\\}_{v\in V(G)}$ defined as

$\displaystyle m^{\alpha}_{v}(u)=\begin{cases}\alpha&\text{\qquad if }u=v,\\\
\frac{1-\alpha}{d_{v}}&\text{\qquad if }u\in N(v),\\\ 0&\text{\qquad
otherwise}.\end{cases}$

In [15], Lin, Lu and Yau defined the Ricci curvature of graphs based on the
$\alpha$-lazy random walk as $\alpha$ goes to $1$. More precisely, for any
$x\neq y\in V$, they defined the $\alpha$-Ricci-curvature
$\kappa_{\alpha}(x,y)$ to be

$\kappa_{\alpha}(x,y)=1-\frac{W(m_{x}^{\alpha},m_{y}^{\alpha})}{d(x,y)}$ (3)

and the Lin-Lu-Yau Ricci curvature $\kappa_{\textrm{LLY}}$ of the vertex pair
$(x,y)$ in $G$ to be

$\kappa_{\textrm{LLY}}(x,y)=\displaystyle\lim_{\alpha\to
1}\frac{\kappa_{\alpha}(x,y)}{(1-\alpha)}.$ (4)

A graph $G$ is called positively LLY-curved if it has positive Lin-Lu-Yau
curvature on every vertex pair of $G$. It was shown [15] that if
$\kappa_{\textrm{LLY}}(x,y)\geq\kappa_{0}$ for every edge $xy\in E(G)$, then
$\kappa_{\textrm{LLY}}(x,y)\geq\kappa_{0}$ for any pair of vertices $(x,y)$.

Recently, Münch and Wojciechowski [18] gave a limit-free formulation of the
Lin-Lu-Yau Ricci curvature using graph Laplacian. Given a graph $G=(V,E)$, the
graph Laplacian $\Delta$ is defined as

$\Delta f(x)=\frac{1}{d_{x}}\sum\limits_{y\in N(x)}(f(y)-f(x)).$ (5)

The Lin-Lu-Yau curvature can be alternatively expressed [18] as

$\kappa_{LLY}(x,y)=\inf_{\begin{subarray}{c}f\in Lip(1),\\\
\nabla_{yx}f=1\end{subarray}}\nabla_{xy}\Delta f,$ (6)

where $\nabla_{xy}f=\frac{f(x)-f(y)}{d(x,y)}$ is the _gradient_ function.
Following Lemma 2.2 of [2], it suffices to optimize over all integer-valued
$1$-Lipschitz functions $f$. An integer-valued $1$-Lipschitz function
$f:V(G)\to\mathbb{Z}$ that attains the infimum in Equation (6) is called
_optimal for $(x,y)$_.

##  3 Proof of Theorem 4.

In this section, we show a sharp upper bound on the maximum degree of a
positively curved outerplanar graph. We first recall the following lemma of Lu
and Wang [17].

######  Lemma 1.

[17] Let $G$ be a simple positively curved planar graph and $xy\in E(G)$ be an
arbitrary edge with $d_{x}\leq d_{y}$. Suppose $S\subseteq
N(x)\setminus\\{y\\}$, $|S|=s$, and $|S\cap N(y)|=k$. Then

$\displaystyle|N(S)\cap N(y)|>\frac{s}{d_{x}}d_{y}-(k+1+|N(x,y)|)+|N(S)\cap
N(x,y)|.$

When $S=N(x)\setminus\\{y\\}$ in the equation above, we have $s=d_{x}-1$ and
$k=|N(x,y)|$. We then obtain the following immediate corollary of Lemma 1.

######  Corollary 1.

Let $G$ be a simple positively curved planar graph and $xy\in E(G)$ be an
arbitrary edge with $d_{x}\leq d_{y}$. Let $S=N(x)\setminus\\{y\\}$. Then

$\left|N(S)\cap
N(y)\right|>\left(1-\frac{1}{d_{x}}\right)d_{y}-(2\left|N(x,y)\right|+1)+\left|N(S)\cap
N(x,y)\right|.$

###### Proof of Theorem 4.

Suppose, towards a contradiction, that $\Delta(G)\geq 10$. Let $x,y\in V(G)$
such that $d_{y}=\Delta(G)$ and $xy\in E(G)$ is an exterior edge. Then
$d_{x}\geq\delta(G)\geq 2$. Let $S=N(x)\setminus\\{y\\}$ and let
$T\vcentcolon=N(S)\cap N(y)$. Since $xy$ is an exterior edge, the common
neighborhood $N(x,y)$ may either be empty, or contain one vertex. We consider
these cases separately.
Case $1$: Suppose $\left|N(x,y)\right|=0$. Using Corollary 1,

$\displaystyle\left|T\right|$
$\displaystyle>\left(1-\frac{1}{d_{x}}\right)d_{y}-1+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq\frac{1}{2}\cdot 10-1+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq 4.$

Hence $\left|T\right|\geq 5$. However, note that contracting all edges in
$E(x,S)$ yields a $K_{2,3}$ minor in $G$, contradicting the outerplanarity of
$G$.
Case $2$: Suppose $\left|N(x,y)\right|=1$ and let $z$ be the only common
neighbor in $N(x,y)$. If $d_{x}=2$, then $|S|=|N(x)\setminus\\{y\\}|=1$ and

$\displaystyle\left|T\right|$
$\displaystyle>\left(1-\frac{1}{d_{x}}\right)d_{y}-3+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq\frac{1}{2}\cdot 10-3+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq 2.$

Hence, $\left|T\right|\geq 3$. Therefore, the only vertex in $S$ (which is
$z$) is adjacent to at least $3$ neighbors of $y$, yielding a $K_{2,3}$ minor
and contradicting the outerplanarity of $G$. If $d_{x}\geq 3$, then

$\displaystyle\left|T\right|$
$\displaystyle>\left(1-\frac{1}{d_{x}}\right)d_{y}-3+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq\frac{2}{3}\cdot 10-3+\left|N(S)\cap
N(x,y)\right|$ $\displaystyle\geq\frac{11}{3}.$

Hence, $\left|T\right|\geq 4$. Since $d_{y}=\Delta(G)\geq 10$ and $d_{x}\geq
3$, the sets $N(y)\setminus S$ and $S\setminus\\{z\\}$ must be nonempty. For
any $v\in N(y)\setminus S$ and $w\in S\setminus\\{z\\}$, if $vw\in E(G)$, then
either $z$ lies in the interior of the cycle $wxyv$ which contradicts that $G$
is outerplanar, or $xy$ lies in the interior of the cycle $wxyv$ which
contradicts that $xy$ is an exterior edge. Therefore, we have that for any
$v\in N(y)\setminus S$ and $w\in S\setminus\\{z\\}$, $vw\notin E(G)$.

Since $|T|\geq 4$ and $N(x,y)=\\{z\\}$, we then obtain that $z$ is adjacent to
at least three vertices in $N(y)$, yielding a $K_{2,3}$ minor together with
$y$ and $N(z,y)$, contradicting the outerplanarity of $G$. ∎

##  4 Exact Curvature via Local Configuration

In this section, we characterize the possible degree pairs of an edge with
positive Lin-Lu-Yau curvature in a maximal outerplanar graph by determining
the optimal $1$-Lipschitz functions for every edge $xy\in E(G)$. Recall that

$\kappa(x,y)=\inf_{\begin{subarray}{c}f\in Lip(1),\\\
\nabla_{yx}f=1\end{subarray}}\nabla_{xy}\Delta f,\;\;\;\textrm{where
$\nabla_{xy}f=\frac{f(x)-f(y)}{d(x,y)}$.}$ (7)

Moreover, recall that by Lemma 2.2 of [2], it suffices to consider integer-
valued optimal functions $f_{0}$. Thus, since $\nabla_{yx}f_{0}=1$, we may
assume without loss of generality that $f_{0}(x)=0$ and $f_{0}(y)=1$. Then,
due to the $1$-Lipschitz condition,
$\text{Im}(f_{0}|_{N(x)})\subseteq\\{-1,0,1\\}$ and
$\text{Im}(f_{0}|_{N(y)})\subseteq\\{0,1,2\\}$ where Im denotes the image of a
function.

######  Lemma 2.

Let $G$ be a maximal outerplanar graph, and suppose $xy\in E(G)$ is an
exterior edge such that $d_{x}\leq d_{y}$. Then, $\kappa_{LLY}(x,y)>0$ if and
only if

$(d_{x},d_{y})\in\left\\{(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,3),(3,4)\right\\}.$

$H_{xy}$ $\delta_{xz}$ $d_{x}$ $\delta_{yz}$ $d_{y}$ $\kappa(x,y)$ Positive
degree pairs $(d_{x},d_{y})$ 0 2 0 2 $3/d_{x}+4/d_{y}-2$ $\\{(2,2)\\}$ 0 2 1
$\geq 3$ $\begin{cases}4/d_{x}+3/d_{y}-2&\text{if }d_{y}<2d_{x}\\\
3/d_{x}+5/d_{y}-2&\text{if }2d_{x}\leq d_{y}\end{cases}$
$\\{(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9)\\}$ 1 $\geq 3$ 1 $\geq d_{x}$
$3/d_{x}+5/d_{y}-2$ $\\{(3,3),(3,4)\\}$

Table 1: Degree pairs for positively curved exterior edges $xy$ and local
configuration $H_{xy}$.

###### Proof of Lemma 2.

Let $xy$ be an exterior edge of $G$. We will deduce optimal functions $f_{0}$
for the edge $xy$ in all possible local configurations around $xy$, that is,
$f_{0}$ such that

$\kappa(x,y)=\inf_{\begin{subarray}{c}f\in\text{Lip}(1),\\\
\nabla_{yx}f=1\end{subarray}}\nabla_{xy}\Delta f=\nabla_{xy}\Delta f_{0}.$

Without loss of generality, we assign $f_{0}(x)=0$ and $f_{0}(y)=1$. Since
$xy$ is an exterior edge and $G$ is edge maximal, $N(x)\cap N(y)=\\{z\\}$ for
some $z\in V(G)$. Then, since $f_{0}\in\text{Lip}(1)$, we must have
$f_{0}(z)\in\\{0,1\\}$. Let $\delta_{xz}=|N(x,z)\setminus\\{y\\}|$ and
$\delta_{yz}=|N(y,z)\setminus\\{x\\}|$. Note that, since $G$ is outerplanar,
$\delta_{xz},\delta_{yz}\in\\{0,1\\}$. If $\delta_{xz}=1$, let
$N(x,z)\setminus\\{y\\}=\\{v_{xz}\\}$. Similarly, if $\delta_{yz}=1$, let
$N(y,z)\setminus\\{x\\}=\\{v_{yz}\\}$. Since $f_{0}(x)=0$ and $f_{0}(y)=1$, we
then obtain that

$\displaystyle\nabla_{xy}\Delta f_{0}$
$\displaystyle=\frac{1}{d_{x}}\sum_{v\in
N(x)}(f_{0}(v)-f_{0}(x))-\frac{1}{d_{y}}\sum_{v\in N(y)}(f_{0}(v)-f_{0}(y))$
$\displaystyle=\frac{1}{d_{x}}\sum_{v\in
N(x)}f_{0}(v)+\frac{1}{d_{y}}\sum_{v\in N(y)}(1-f_{0}(v)).$ (8)

Observe that since $G$ is outerplanar, $xy$ is an exterior edge and
$\\{z\\}=N(x,y)$, we have that the distance from any vertex in
$N(x)\setminus\\{v_{xz},y,z\\}$ to any vertex in
$N(y)\setminus\\{v_{yz},x,z\\}$ is $3$. Since $f_{0}$ is an optimal function
for $xy$, we then obtain that $f_{0}(v)=-1$ for all $v\in
N(x)\setminus\\{v_{xz},y,z\\}$ and $f_{0}(v)=2$ for all $v\in
N(y)\setminus\\{v_{yz},x,z\\}$. Equation (8) can then be re-written as

$\displaystyle\nabla_{xy}\Delta f_{0}$
$\displaystyle=\frac{1}{d_{x}}\left[\delta_{xz}(f_{0}(z)-1)+f_{0}(z)+1-(d_{x}-2-\delta_{xz})\right]$
$\displaystyle\quad\quad\quad+\frac{1}{d_{y}}\left[-\delta_{yz}f_{0}(z)+(1-f_{0}(z))+1-(d_{y}-2-\delta_{yz})\right]$
$\displaystyle=\left(\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}\right)f_{0}(z)+\frac{3}{d_{x}}+\frac{4+\delta_{yz}}{d_{y}}-2.$
(9)

Note that $\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}<0$ if and
only if $\delta_{xz}=0,\delta_{yz}=1$ and $d_{y}<2d_{x}$.

Case 1: $\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}<0$. Then it
is clear that $\nabla_{xy}\Delta f_{0}$ is minimized when $f_{0}(z)=1$.
Moreover, since in this case $\delta_{xz}=0$, $f_{0}$ still satisfies the
$1$-Lipschitz condition.

Case 2: $\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}\geq 0$. Then
it is clear that $\nabla_{xy}\Delta f_{0}$ is minimized when $f_{0}(z)=0$.
Note that in this case it’s impossible that $\delta_{xz}=1$ and
$\delta_{yz}=0$, otherwise it will contradict that
$\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}\geq 0$. Hence it
follows that $(\delta_{xz},\delta_{yz})\in\\{(0,0),(0,1),(1,1)\\}$. We list
each local configuration based on $\delta_{xz}$ and $\delta_{yz}$ in Table 1
and characterize the possible degree pairs when $\kappa(x,y)>0$. It is not
hard to check that $f_{0}$ can be made $1$-Lipschitz in each case. ∎

######  Lemma 3.

Let $G$ be a maximal outerplanar graph, and suppose $xy\in E(G)$ is an
interior edge such that $d_{x}\leq d_{y}$. A complete characterization of
degree pairs $(d_{x},d_{y})$, depending upon the local configuration, such
that $\kappa_{LLY}(x,y)>0$ is given by Table 2.

$H_{xy}$ $\delta_{xw}$ $\delta_{xz}$ $d_{x}$ $\delta_{yw}$ $\delta_{yz}$
$d_{y}$ $\kappa(x,y)$ Positive degree pairs $(d_{x},d_{y})$ 0 0 3 0 0 3
$4/d_{x}+6/d_{y}-2$ $\\{(3,3)\\}$ 0 0 3 0 1 $\geq 4$
$\begin{cases}5/d_{x}+5/d_{y}-2&\text{if }d_{y}<2d_{x}\\\
4/d_{x}+7/d_{y}-2&\text{if }2d_{x}\leq d_{y}\end{cases}$
$\\{(3,4),(3,5),(3,6),(3,7),(3,8),(3,9)\\}$ 0 0 3 1 1 $\geq 5$
$\begin{cases}6/d_{x}+4/d_{y}-2&\text{if }d_{y}<2d_{x}\\\
4/d_{x}+8/d_{y}-2&\text{if }2d_{x}\leq d_{y}\end{cases}$
$\\{(3,5),(3,6),(3,7),(3,8),(3,9)\\}$ 0 1 $\geq 4$ 0 1 $\geq d_{x}$
$4/d_{x}+7/d_{y}-2$ $\\{(4,4),(4,5),(4,6),(5,5)\\}$ 0 1 $\geq 4$ 1 0 $\geq
d_{x}$ $\begin{cases}5/d_{x}+5/d_{y}-2&\text{if }d_{y}<2d_{x}\\\
4/d_{x}+7/d_{y}-2&\text{if }2d_{x}\leq d_{y}\end{cases}$
$\\{(4,4),(4,5),(4,6)\\}$ 0 1 $\geq$ 4 1 1 $\geq\max\\{5,d_{x}\\}$
$\begin{cases}5/d_{x}+6/d_{y}-2&\text{if }d_{y}<2d_{x}\\\
4/d_{x}+8/d_{y}-2&\text{if }2d_{x}\leq d_{y}\end{cases}$
$\\{(4,5),(4,6),(4,7),(5,5)\\}$ 1 1 $\geq$ 5 0 1 $\geq d_{x}$
$4/d_{x}+7/d_{y}-2$ $\\{(5,5)\\}$ 1 1 $\geq$ 5 1 1 $\geq d_{x}$
$4/d_{x}+8/d_{y}-2$ $\\{(5,5),(5,6)\\}$

Table 2: Positive degree pairs for interior edges $xy$ based on the local
configuration $H_{xy}$.

###### Proof of Lemma 3.

Let $xy$ be an interior edge of $G$. We will deduce optimal functions $f_{0}$
for the edge $xy$ in all possible local configurations around $xy$. Similar to
before, without loss of generality, we assume that $f_{0}(x)=0$ and
$f_{0}(y)=1$.

Since $xy$ is an interior edge and $G$ is edge maximal, $N(x)\cap
N(y)=\\{w,z\\}$ for some $w,z\in V(G)$ and by the $1$-Lipschitz condition we
have $f_{0}(w),f_{0}(z)\in\\{0,1\\}$. Similar to before, Equation (8) still
holds, i.e.,

$\displaystyle\nabla_{xy}\Delta f_{0}$
$\displaystyle=\frac{1}{d_{x}}\sum_{v\in
N(x)}(f_{0}(v)-f_{0}(x))-\frac{1}{d_{y}}\sum_{v\in N(y)}(f_{0}(v)-f_{0}(y))$
$\displaystyle=\frac{1}{d_{x}}\sum_{v\in
N(x)}f_{0}(v)+\frac{1}{d_{y}}\sum_{v\in N(y)}(1-f_{0}(v)).$ (10)

Define $\delta_{xw}=|N(x,w)\setminus\\{y\\}|$,
$\delta_{xz}=|N(x,z)\setminus\\{y\\}|$, $\delta_{yw}=|N(y,w)\setminus\\{x\\}|$
and $\delta_{yz}=|N(y,z)\setminus\\{x\\}|$. Since $G$ is outerplanar,
$\delta_{xw},\delta_{xz},\delta_{yw},\delta_{yz}\in\\{0,1\\}$. For
$a\in\\{x,y\\}$ and $b\in\\{w,z\\}$, if $\delta_{ab}=1$, then let
$N(a,b)\backslash\\{x,y\\}=\\{v_{ab}\\}$.

Observe that in (10), $\nabla_{xy}\Delta f_{0}$ is minimized when $f_{0}(v)$
is as small as possible for $v\in N(x)$ and as big as possible for $v\in N(y)$
while keeping $f_{0}$ $1$-Lipschitz. Note that since $G$ is outerplanar,
$\\{w,x\\}$ separates $v_{xw}$ (if it exists) with vertices in
$N(y)\backslash\\{x,w\\}$. Thus if $\delta_{xw}=1$, then
$f_{0}(v_{xw})=f_{0}(w)-1$ due to the optimality of $f_{0}$. Similarly,
$f_{0}(v_{xz})=f_{0}(z)-1$, $f_{0}(v_{yw})=f_{0}(w)+1$,
$f_{0}(v_{yz})=f_{0}(z)+1$ if $v_{xz},v_{yw},v_{yz}$ exist respectively.

Moreover, observe that the distance from any vertex in
$N(x)\setminus\\{v_{xw},w,y,z,v_{xz}\\}$ to any vertex
$N(y)\setminus\\{v_{yw},w,x,z,v_{yz}\\}$ is $3$. Therefore, since $f_{0}$ is
optimal, we obtain that $f_{0}(v)=-1$ for all $v\in
N(x)\setminus\\{v_{xw},w,y,z,v_{xz}\\}$ and $f_{0}(v)=2$ for all $v\in
N(y)\setminus\\{v_{yw},w,x,z,v_{yz}\\}$. Then Equation (10) becomes

$\displaystyle\nabla_{xy}\Delta f_{0}$
$\displaystyle=\frac{1}{d_{x}}\left[\delta_{xw}(f_{0}(w)-1)+f_{0}(w)+1+f_{0}(z)+\delta_{xz}(f_{0}(z)-1)-(d_{x}-3-\delta_{xw}-\delta_{xz})\right]$
$\displaystyle\quad\quad\quad+\frac{1}{d_{y}}\left[-\delta_{yw}f_{0}(w)+(1-f_{0}(w))+1+(1-f_{0}(z))-\delta_{yz}f_{0}(z)-(d_{y}-3-\delta_{yw}-\delta_{yz})\right]$
$\displaystyle=\left(\frac{1+\delta_{xw}}{d_{x}}-\frac{1+\delta_{yw}}{d_{y}}\right)f_{0}(w)+\left(\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}\right)f_{0}(z)+\frac{4}{d_{x}}+\frac{6+\delta_{yw}+\delta_{yz}}{d_{y}}-2.$

Note that $\frac{1+\delta_{xw}}{d_{x}}-\frac{1+\delta_{yw}}{d_{y}}<0$ if and
only if $\delta_{xw}=0,\delta_{yw}=1$ and $d_{y}<2d_{x}$. In that case, since
$f_{0}$ is optimal, it must be the case that $f_{0}(w)=1$. On the other hand,
if $\frac{1+\delta_{xw}}{d_{x}}-\frac{1+\delta_{yw}}{d_{y}}$ is nonnegative,
$\nabla_{xy}\Delta f_{0}$ is minimized when $f_{0}(w)=0$.

Similarly, note that
$\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}<0$ if and only if
$\delta_{xz}=0,\delta_{yz}=1$ and $d_{y}<2d_{x}$. In that case, it must happen
that $f_{0}(z)=1$ as before. On the other hand, if
$\frac{1+\delta_{xz}}{d_{x}}-\frac{1+\delta_{yz}}{d_{y}}\geq 0$, we may assume
$f_{0}(z)=0$. Note that the case when $\delta_{xw}+\delta_{xz}\geq 1$ and
$\delta_{yw}=\delta_{yz}=0$ is impossible since $d_{x}\leq d_{y}$. We list
each local configuration (up to symmetry) for
$\delta_{xw},\delta_{xz},\delta_{yw}$ and $\delta_{yz}$ in Table 2 and compute
the possible degree pairs when $\kappa(x,y)>0$. ∎

##  5 Bounding the Order

In this section, we bound the order of a positively curved maximal outerplanar
graph $G$. Note that since $G$ is maximally outerplanar, if $|V(G)|\geq 3$,
then $G$ is connected and $\delta(G)\geq 2$. Given two graphs $A$ and $B$, let
the join of $A$ and $B$, denoted by $A\vee B$, be the graph obtained from
$A\cup B$ by connecting each vertex in $A$ with each vertex in $B$. We begin
with the following structural lemma.

######  Lemma 4.

Let $G$ be a maximal outerplanar graph and suppose $x\in V(G)$. Then,
$G[N[x]]\cong K_{1}\vee P_{d_{x}}$.

###### Proof.

Since $G$ is outerplanar, $G[N(x)]$ must be a disjoint union of paths.
Moreover, since $G$ is edge-maximal, $G[N(x)]$ must be a single path
(otherwise we could add an edge to merge two paths into one without violating
the outerplanarity condition). Thus $G[N[x]]\cong K_{1}\vee P_{d_{x}}$. ∎

###### Proof of Theorem 5.

We will show Theorem 5 by induction on $|V(G)|$. For the base case, we
consider $|V(G)|=11$. Using SageMath, we verify that all $228$ maximal
outerplanar graphs on $11$ vertices are non-positively curved.111The SageMath
code used to verify is available at:
https://github.com/ghbrooks28/outerplanar-LLY/.

Now consider $G$, a maximal outerplanar graph on $n\geq 12$ vertices. Assume,
towards a contradiction, that $G$ is positively curved. Let $w\in V(G)$ such
that $d_{w}=2$ (such $w$ exists since every outerplanar graph contains a
vertex of degree $2$). Note that $G-w$ is maximally outerplanar. It follows
from the induction hypothesis that $G-w$ is not positively curved, thus there
exists some $xy\in E(G)$ with $\kappa(x,y)\leq 0$. Without loss of generality,
assume that $d_{x}\leq d_{y}$. We write $d_{v}$ for the degree of $v$ in $G$,
and we write $\tilde{d}_{v}$ for the degree of $v$ in $G-w$. Since $xy$ is
non-positively curved in $G-w$, Lemmas 2 and 3 exactly characterize the
possible values of $(\tilde{d}_{x},\tilde{d}_{y})$; we call degree pairs
corresponding to non-positively curved edges _bad_ degree pairs and degree
pairs corresponding to positively curved edges _good_ degree pairs.

First, suppose $w\not\in N(x)\cup N(y)$, so that
$(d_{x},d_{y})=(\tilde{d}_{x},\tilde{d}_{y})$. Since
$(\tilde{d}_{x},\tilde{d}_{y})$ is a bad degree pair and the degrees of $x$
and $y$ are the same in $G$ and $G-w$, we have that $(d_{x},d_{y})$ is a bad
degree pair, a contradiction. Next, suppose $w\in N(x)\setminus N(y)$ so that
$(d_{x},d_{y})=(\tilde{d}_{x}+1,\tilde{d}_{y})$. Notice that since $w\in
N(x)\setminus N(y)$, $xy$ is an exterior (or interior) edge in $G$ if and only
if it is an exterior (respectively, interior) edge in $G-w$. Examining Table 1
and Table 2, we see that, given a degree pair $(a,b)$ that is bad for exterior
(or interior) edges, the degree pair $(a+1,b)$ is also bad for exterior
(respectively, interior) edges. Thus, $(d_{x},d_{y})$ is a bad degree pair in
$G$, contracting our assumption that $G$ is positively curved. The case when
$w\in N(y)\setminus N(x)$ is similar.

The remainder of the proof addresses the final case, where $w\in N(x,y)$, so
that $(d_{x},d_{y})=(\tilde{d}_{x}+1,\tilde{d}_{y}+1)$. Note that in this
case, $xy$ has to be exterior edge of $G-w$. Since $xy$ is non-positively
curved in $G-w$, we obtain from Lemma 2 that

$(\tilde{d}_{x},\tilde{d}_{y})\not\in\\{(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,3),(3,4)\\}.$
(11)

Note that by Theorem 4, $\Delta(G)\leq 9$. It follows that
$\max\\{\tilde{d}_{y},\tilde{d}_{x}\\}\leq 8$. By Equation (11), it suffices
to consider $xy$ such that $\tilde{d}_{x}\geq 3$ and $\tilde{d}_{y}\geq 4$,
where $\tilde{d}_{y}>4$ if $\tilde{d}_{x}=3$. Then by Lemma 3,
$(d_{x},d_{y})=(\tilde{d}_{x}+1,\tilde{d}_{y}+1)$ is a bad degree pair (and so
$G$ would be non-positively curved) for all values except
$(d_{x},d_{y})\in\\{(4,6),(5,5),(4,7),(5,6)\\}$. However, note that when
$(d_{x},d_{y})=(4,7)$ or $(5,6)$, $\max\\{\delta_{xw},\delta_{yw}\\}=1$ (see
Table 2 in Lemma 3), which contradicts that $d_{w}=2$. Hence we are left with
two cases when $(d_{x},d_{y})\in\\{(4,6),(5,5)\\}$. We will examine the local
configuration $H_{xy}$ below.

Case 1: Suppose $(d_{x},d_{y})=(4,6).$ Let $C\subseteq G$ be the outer face
cycle in $G$. Using Lemma 4, we have the local configuration $H_{xy}$, labeled
as shown in Figure 2. Let $x^{\prime}\in N_{C}(x)\setminus\\{w\\}$ and
$y^{\prime},v,u\in N_{C}(y)\setminus\\{w\\}$ such that $y^{\prime}vuzxw$ is
the path induced by $N(y)$. Since $d_{y}=6,$ $yy^{\prime}$ is an exterior
edge, and $yz,yu,yv$ are interior edges. Note that $G$ is assumed to be
positively curved. Thus the degree pairs of $yy^{\prime},yz,yu$ and $yv$ all
have to be good. By Lemma 2 and Lemma 3, we have $d_{y^{\prime}}=2$,
$d_{z}\in\\{4,5\\},$ and $d_{u},d_{v}\in\\{3,4,5\\}.$ Since $d_{x}=4,$ and
$xx^{\prime}$ is an exterior edge, $d_{x^{\prime}}\in\\{2,3\\}$.

We first claim that $d_{x^{\prime}}=2$. Otherwise, if $d_{x^{\prime}}=3$, then
there exists $x^{\prime\prime}\in V(G)\setminus\\{x\\}$ such that
$x^{\prime\prime}\in N(x^{\prime},z),$ which implies $d_{z}\geq 5$. By Lemma 2
and Lemma 3, $zu$ must then be an interior edge, which implies that $d_{z}\geq
6$. But now $(d_{y},d_{z})$ is a bad degree pair, contradicting that $yz$ is
positively curved. Hence $d_{x^{\prime}}=2$.

But now if we repeat the argument by considering $G-x^{\prime}$ instead of
$G-w$, we obtain contradictions unless $(d_{x},d_{z})\in\\{(4,6),(5,5)\\}$,
which is impossible in this case since $d_{x}=4$ and $d_{z}<6$.

Figure 2: $H_{xy}$ in Case 1.

Case 2: Suppose $(d_{x},d_{y})=(5,5).$ Let $C\subseteq G$ be the outer face
cycle. Let $x^{\prime},u\in N_{C}(x)\setminus\\{w\\}$ such that
$x^{\prime}uzyw$ is the path induced by $N(x)$ (see Figure 3). Since
$d_{x}=5,$ and $xx^{\prime}$ is an exterior edge, it follows from Lemma 2 that
$d_{x^{\prime}}=2$. Now if we repeat the argument by considering
$G-x^{\prime}$ instead of $G-w$, we obtain contradictions unless
$(d_{x},d_{u})=(5,5)$. However, this is impossible since by the configurations
in Lemma 3, if $(d_{x},d_{u})=(5,5)$, then $d_{x^{\prime}}>2$, giving a
contradiction.

Figure 3: $H_{xy}$ in Case 2.

This completes the proof of Theorem 5. ∎

## Acknowledgments

Most research in this paper took place at the 2023 MRC Summer Conference:
Ricci Curvatures of Graphs and Applications to Data Science supported by the
National Science Foundation under Grant Number 1916439. We heartily thank the
organizers.

## References

  * [1] D. Bakry and M. Emery, Diffusions hypercontractives, Séminaire de probabilités, XIX, 1983/84, 177–206, Lecture Notes in Math. 1123, Springer, Berlin, 1985.
  * [2] B. Bhattacharya and S. Mukherjee, Exact and asymptotic results on coarse Ricci curvature of graphs, Discrete Math., 338(1) (2015), 23–42.
  * [3] D. P. Bourne, D. Cushing, S. Liu, F. Münch, and N. Peyerimhoff, Ollivier-Ricci idleness functions of graphs, SIAM J. Discrete Math., 32(2) (2018), 1408–1424.
  * [4] B. Chen and G. Chen, Gauss-Bonnet formula, finiteness condition, and characterizations of graphs embedded in surfaces, Graphs Combin., 24(3) (2008), 159–183.
  * [5] F. Chung and S.-T. Yau, Logarithmic Harnack inequalities, Math. Res. Lett. 3 (1996), 793–812.
  * [6] M. DeVos and B. Mohar, An analogue of the Descartes-Euler formula for infinite graphs and Higuchi’s conjecture, Trans. Amer. Math. Soc., 359(7) (2007), 3287–3300.
  * [7] K. Devriendt and R. Lambiotte, Discrete curvature on graphs from the effective resistance, J. Phys.: Complex., 3(2) (2022), 025008.
  * [8] Forman, Bochner’s method for cell complexes and combinatorial Ricci curvature, Discrete Comput. Geom., 29 (2003), 323–-374.
  * [9] E. Gamlath, X. Liu, L. Lu and X. Yuan, A tight bound on $\\{C_{3},C_{5}\\}$-free connected graphs with positive Lin-Lu-Yau Ricci curvature, arXiv:2312.16593.
  * [10] L. Ghidelli, On the largest planar graphs with everywhere positive combinatorial curvature, J. Combin. Theory Ser. B., 158(2) (2023), 226–263.
  * [11] Y. Higuchi, Combinatorial curvature for planar graphs, J. Graph Theory 38(4) (2001), 220–229.
  * [12] B. Hua and Y. Su, the set of vertices with positive curvature in a planar graph with nonnegative curvature, Adv. Math. 343 (2019), 789–820.
  * [13] A. Joulin, A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature, Bernoulli 15 (2009), 532–-549.
  * [14] A. Joulin and Y. Ollivier, Curvature, concentration and error estimates for Markov chain Monte Carlo, Ann. Probab. 38(6) (2010), 2418–2442.
  * [15] Y. Lin, L. Lu, S.-T. Yau, Ricci curvature of graphs, Tohoku Math. J. 63 (2011) 605–627.
  * [16] Y. Lin and S.-T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), 345-–358.
  * [17] L. Lu and Z. Wang, On the size of planar graphs with positive Lin-Lu-Yau Ricci curvature, arXiv:2010.03716.
  * [18] F. Münch and R. Wojciechowski, Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds, Adv. Math., 356 (2019).
  * [19] R. Nicholson and J. Sneddon, New graphs with thinly spread positive combinatorial curvature New Zealand J. Math., 41 (2011), 39–43.
  * [20] B.-G. Oh, On the number of vertices of positively curved planar graphs, Discrete Math., 340(6) (2017), 1300–-1310.
  * [21] Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal. 256 (2009), 810–-864.
  * [22] T. Réti, E. Bitay and Z. Kosztolányi, On the polyhedral graphs with positive combinatorial curvature, Acta Polytech. Hungar., 2(2) (2005), 19–37.
  * [23] M.D. Sammer. Aspects of mass transportation in discrete concentration inequalities. PhD thesis, Georgia Institute of Technology, 2005.
  * [24] K.-Th. Sturm. On the geometry of metric measure spaces. I and II. Acta Math., 196(1) (2006), 65–177.
  * [25] L. Sun and X. Yu, Positively curved cubic plane graphs are finite, J. Graph Theory 47(4) (2004), 241–274.
  * [26] L. Zhang, A result on combinatorial curvature for embedded graphs on a surface, Discrete Math., 308(24) (2008), 6588–6595.