# Continuous Phase Modulation of Phase Coded Transmit Waveforms using Multi-
Tone Sinusoidal Frequency Modulation ††thanks: This research was funded by the
Office of Naval Research grant # N0001421WX00843.

David A. Hague  Sensors and Sonar Systems Department
Naval Undersea Warfare Center
Newport, RI USA
<EMAIL_ADDRESS>
###### Abstract

Phase Coded (PC) waveforms possess desirable Auto-Correlation Function (ACF)
properties for use in radar and sonar systems. However, their spectra possess
high spectral leakage due to the abrupt phase transitions between the chips in
the waveform. This paper describes a method of Continuous Phase Modulation
(CPM) to reduce a PC waveform’s spectral leakage using the Multi-Tone
Sinusoidal Frequency Modulation (MTSFM) model. The MTSFM-CPM model represents
the PC waveform’s instantaneous phase as a finite Fourier series. This
representation smooths the abrupt phase transitions between chips resulting in
a spectrally compact waveform. This smoothing of the PC waveform’s
instantaneous phase introduces perturbations to the waveform’s ACF mainlobe
and sidelobe structure. Adjusting the MTSFM-CPM waveform’s parameters refines
its ACF mainlobe and sidelobe structure while also preserving its compact
spectral shape.

###### Index Terms:

Continuous Phase Modulation, Waveform Diversity, Multi-Tone Sinusoidal
Frequency Modulation

##  I Introduction

The vast majority of waveform diversity research over the last several decades
has focused on the design of Phase Coded (PC) waveforms [1]. These waveforms
are composed of a set of continguous sub-pulses, also known as chips, each
possessing its own phase shift. The set of phase-shifts, known as the phase
code, is utilized as a discrete set of parameters that are selected to
generate a waveform with distinct properties such as low sidelobes in its
Ambiguity Function (AF) or Auto-Correlation Function (ACF) [2]. Theoretically
there exists a nearly endless combination of employable phase codes making PC
waveforms an extremely versatile parameterized waveform model. There continues
to be extensive research on designing optimal PC waveforms for Multiple-Input
Multiple-Output (MIMO) radar applications [3, 4, 5] and cognitive radar
applications [6, 7, 8]. Additionally, the developement of computationally
efficient algorithms to design PC waveforms with specific ACF/AF properties is
very much of interest to the radar and sonar communities [9, 10, 11, 12, 13].

In addition to possessing a desired AF/ACF shape and being constant modulus,
waveforms are also generally required to be spectrally compact where the vast
majority of the waveform’s energy is densely concentrated in the system’s
operational band of frequencies. Radar transmissions are often constrained by
spectral masks which strictly limit the amount of waveform energy that resides
outside the radar’s allocated spectral band [14]. Additionally, the frequency
response of the transmitter imparts spectral shaping of the physically emitted
waveform. The resulting transmitted signal therefore contains Amplitude
Modulation (AM) and Phase Modulation (PM) effects which can perturb the
waveform’s spectral and AF/ACF shape characteristics [15, 16, 17]. These
deleterious effects can be minimized by transmitting waveforms that densely
concentrate their energy in a band of frequencies where the transmitter’s
frequency response does not vary substantially.

Most Frequency Modulated (FM) waveforms are quite spectrally compact. This is
largely because FM waveforms have modulation functions that are smooth,
differentiable, and free of transient artifacts. The spectra of PC waveforms
however possess excessive spectral leakage outside their band of operation due
to the abrupt phase transitions between chips [2]. The PM and AM effects
imposed by practical transmitters and their driving electronics distort the
waveform transmitted into the medium thus corrupting its AF/ACF properties.
There are a number of Continuous Phase Modulation (CPM) methods which smooth
the transition between chips by introducing continuity in the first several
derivatives of the PC waveform’s instantaneous phase [18]. This smoothing
results in a more spectrally compact waveform while still retaining the
waveform diversity afforded by phase coding [16]. However, the degree of
smoothing necessary to synthesize waveforms with high spectral compactness
also introduces perturbations to the waveform’s instantaneous phase. These
perturbations degrade the waveform’s properties such as AF/ACF shape [19]
necessitating re-optimization of the waveform’s phase code [17].

This paper investigates another method of CPM for PC waveforms using Multi-
Tone Sinusoidal Frequency Modulation (MTSFM) henceforth referred to as the
MTSFM-CPM waveform. The PC waveform’s instantaneous phase is represented as a
finite Fourier series via the MTSFM model. This results in a waveform with an
infinitely differentiable and therefore smooth instantaneous phase function
which substantially improves the waveform’s spectral compactness properties.
Reducing the number of harmonics in the representation increases the degree of
smoothing of the PC waveform’s instantaneous phase and therefore increases its
spectral compactness. While these more spectrally compact waveforms also
possess degraded AF/ACF properties due to the perturbations inherent in the
CPM process, the parameters of the MTSFM-CPM model can be modified to refine
those AF/ACF properties. This smoothing and re-optimization process results in
waveforms with desireably low AF/ACF sidelobes and the spectral compactness
properties necessary for transmission on practical transmitter devices and
their driving electronics.

##  II Waveform Signal Model

This paper assumes a monostatic radar/sonar system that transmits narrowband
(i.e, small fractional bandwidth) waveforms. A basebanded PC waveform with $N$
chips and pulse length $T$ defined over the interval $-T/2\leq t\leq T/2$ is
expressed as

$s_{pc}\left(t\right)=\frac{1}{\sqrt{T}}\sum_{i=1}^{N}\operatorname{rect}\left[\dfrac{t-\left(i-1\right)t_{b}+\left(T-t_{b}\right)/2}{t_{b}}\right]e^{j\phi_{i}}$
(1)

where $t_{b}=T/N$ is the chip duration, $\phi_{i}$ is the phase code of the PC
waveform, and the amplitude term $1/\sqrt{T}$ normalizes the waveform to unit
energy. The general model for a unit energy Phase Modulated (PM) transmit
waveform $s\left(t\right)$ is modeled as a complex analytic signal expressed
as

$s\left(t\right)=\dfrac{\operatorname{rect}\left(t/T\right)}{\sqrt{T}}e^{j\varphi\left(t\right)}$
(2)

where $\varphi\left(t\right)$ is the instantaneous phase of the waveform. The
waveform’s corresponding modulation function maps its instantaneous frequency
as a function of time

$m\left(t\right)=\frac{1}{2\pi}\dfrac{\partial\varphi\left(t\right)}{\partial
t}.$ (3)

A PC waveform’s instantaneous phase can be interpreted as a PM waveform with a
piecewise continuous instantaneous phase $\varphi_{pc}\left(t\right)$
expressed as

$\varphi_{pc}\left(t\right)=\sum_{i=1}^{N}\operatorname{rect}\left[\dfrac{t-\left(i-1\right)t_{b}+\left(T-t_{b}\right)/2}{t_{b}}\right]\phi_{i}.$
(4)

One of the primary waveform design considerations for this paper is how
densely the waveform concentrates its energy in a specified operational band
of frequencies. A commonly utilized method of measuring this property,
referred to here as Spectral Compactness (SC), is defined as the ratio of
waveform energy in a contiguous band of frequencies $\Delta f$ to the total
energy of the waveform across all frequencies expressed as [1, 15, 20]

$\displaystyle\Phi\left(\Delta f\right)=\dfrac{\int_{-\Delta f/2}^{\Delta
f/2}|S\left(f\right)|^{2}df}{\int_{-\infty}^{\infty}|S\left(f\right)|^{2}df}=\int_{-\Delta
f/2}^{\Delta f/2}|S\left(f\right)|^{2}df.$ (5)

where $S\left(f\right)$ is the waveform’s Fourier transform. Note that the
second integral results from the assumption that the basebanded waveform’s
energy in the denominator is unity. This SC measure is often utilized as it
provides a fair means of comparison between FM waveforms and coded waveform
techniques such as PC and Frequency Shift Keying (FSK) [15].

This paper assumes a Matched-Filter (MF) receiver is used to process target
echoes. The narrowband AF measures the correlation between a waveform and its
Doppler shifted versions expressed as

$\chi\left(\tau,\nu\right)=\int_{-\infty}^{\infty}s\left(t-\frac{\tau}{2}\right)s^{*}\left(t+\frac{\tau}{2}\right)e^{j2\pi\nu
t}dt.$ (6)

where $\nu$ is the Doppler frequency shift [21, 2]. Of primary interest in
this paper is the mainlobe and sidelobe structure of the zero-Doppler cut of
the AF, the ACF, expressed as

$R\left(\tau\right)=\int_{-\infty}^{\infty}s\left(t-\frac{\tau}{2}\right)s^{*}\left(t+\frac{\tau}{2}\right)dt.$
(7)

A metric that accurately describes the ACF mainlobe structure is the area
$A_{0}$ under the mainlobe region of the ACF which can be approximated as [21]

$\displaystyle
A_{0}=\int_{-\Delta\tau}^{\Delta\tau}|R\left(\tau\right)|^{2}d\tau\cong\dfrac{\pi}{2\beta_{rms}}$
(8)

where $\Delta\tau$ denotes the first null of the ACF and therefore the null-
to-null mainlobe width is $2\Delta\tau$. The $\beta_{rms}$ term is the
waveform’s RMS bandwidth which for unit energy waveforms is expressed as

$\displaystyle\beta_{rms}=2\pi\sqrt{\int_{-\infty}^{\infty}\left(f-f_{0}\right)^{2}|S\left(f\right)|^{2}df}$
(9)

where $f_{0}$ is the spectral centroid of $S\left(f\right)$.

There are several metrics that describe the sidelobe structure of a waveform’s
ACF. Two of the most common metrics are the Peak Sidelobe Level (PSL) and the
Integrated Sidelobe Ratio (ISR). The PSL is expressed as

$\displaystyle\text{PSL}=\dfrac{\text{max}\bigl{\\{}|R\left(\tau\right)|\bigr{\\}}_{\Delta\tau}^{T}}{\text{max}\bigl{\\{}|R\left(\tau\right)|\bigr{\\}}_{0}^{\Delta\tau}}=\text{max}\bigl{\\{}|R\left(\tau\right)|\bigr{\\}}_{\Delta\tau}^{T}.$
(10)

Note that the rightmost expression in (10) results from the assumption that
the waveform is unit energy and thus the maximum value of
$|R\left(\tau\right)|$ is unity which occurs at $\tau=0$. Another extensively
utilized metric is the Integrated Sidelobe Ratio (ISR) which is the ratio of
the area under the sidelobe region of $|R\left(\tau\right)|^{2}$ to the area
under mainlobe region as shown in (8) expressed as

$\displaystyle\text{ISR}~{}=\dfrac{A_{\tau}}{A_{0}}=\dfrac{\int_{\Delta\tau}^{T}|R\left(\tau\right)|^{2}d\tau}{\int_{0}^{\Delta\tau}|R\left(\tau\right)|^{2}d\tau}.$
(11)

Note that the integration is performed only over positive time-delays since
the ACF is even-symmetric in $\tau$.

Another sidelobe metric which is gaining increasing use for waveform
optimization is the Generalized Integrated Sidelobe Ratio (GISR) [22]. The
GISR generalizes the ISR metric in (11) by evaluating a $\ell_{p}$-norm [23,
24] on the sidelobe and mainlobe regions of the ACF expressed as

$\displaystyle\text{GISR}~{}=\left(\dfrac{\int_{\Delta\tau}^{T}|R\left(\tau\right)|^{p}d\tau}{\int_{0}^{\Delta\tau}|R\left(\tau\right)|^{p}d\tau}\right)^{2/p}$
(12)

where $p\geq 2$ is an integer. When $p=2$, the GISR becomes the standard ISR
metric. As $p\rightarrow\infty$, the integrals in (12) approach the infinity
norm $||\cdot||_{\infty}$, also known as the max norm, and the GISR approaches
the PSL metric (10) [22]. However, the max-norm tends to result in a
discontinuous objective function which prevents the use of gradient-descent
based waveform optimization methods. Making $p$ large but finite results in a
smooth objective function which allows for the use of gradient-descent based
methods in the waveform optimization problem. For this reason, the GISR metric
will be the primary design metric this work uses to synthesize spectrally
compact waveforms with desirably low ACF sidelobe levels.

##  III CPM using the MTSFM Waveform Model

The MTSFM waveform’s instantaneous phase is represented as a finite Fourier
series expansion

$\varphi\left(t\right)=\frac{\alpha_{0}}{2}+\sum_{k=1}^{K}\alpha_{k}\sin\left(\frac{2\pi
kt}{T}\right)+\beta_{k}\cos\left(\frac{2\pi kt}{T}\right)$ (13)

where $\alpha_{0}$ is a constant phase term, $\alpha_{k}$ and $\beta_{k}$ are
the Fourier coefficients, also known as modulation indices, and $K$ is the
number of harmonics in the representation. The MTSFM model has existed since
at least the 1940’s where it was used for the analysis of the spectra of
arbitrary FM signals for use in analog communication systems [25]. More
recently, the author first utilized the MTSFM model to represent a class of
Generalized Sinusoidal FM (GSFM) waveforms [26]. Representing the modulation
and phase functions of the GSFM waveform family allowed for deriving precise
closed-form expressions for their spectra and AFs. The MTSFM model can be used
for waveform analysis in that it can represent any waveform whose modulation
and phase functions meet the Dirichlet conditions [27]. More recently, the
author has utilized the MTSFM model for waveform synthesis where the
modulation indices $\alpha_{k}$ and $\beta_{k}$ are modified to design
waveforms with distinct AF/ACF properties [20, 28]. This paper utilizes the
MTSFM-CPM waveform model for both waveform analysis and synthesis. The PC
waveform’s instantaneous phase is first approximated by a finite Fourier
series. This approximation is used as a form of CPM to smooth abrupt phase
transitions in the PC waveform’s instantaneous phase resulting in a more
spectrally compact waveform. The MTSFM-CPM waveform model is then used for
waveform synthesis by modifying its modulation indices to refine the
waveform’s ACF sidelobe structure via the GISR metric defined in (12).

The MTSFM-CPM waveform model in (13) is used to approximate the instantaneous
phase of a PC waveform in (4) by numerically computing the Fourier
coefficients $\alpha_{k}$ and $\beta_{k}$. As $K\to\infty$, the MTSFM-CPM
approaches an exact representation of the PC waveform. However, if $K$ is made
finite, the Fourier series approximation to (4) is infinitely differentiable
[27] and therefore smooth. This smoothing of the PC waveform’s instantaneous
phase removes abrupt phase transitions and correspondingly improves the
waveform’s SC. Reducing $K$ further smoothes the phase transitions and
therefore further improves the waveform’s SC. To loosely derive a supremum on
the number of harmonics $K$, consider the phase transition between two chips
each of duration $t_{b}$. The lowest frequency harmonic that can approximate
this phase transition has a period $T_{b}=2t_{b}$ and corresponding frequency
$f_{b}=1/2t_{b}$. At a bare minimum then, the max frequency harmonic in the
MTSFM, $K/T$, should be greater than or equal to $f_{b}$. Noting that
$T=Nt_{b}$, setting $K/T\geq 1/2t_{b}$ and solving for $K$ results in the
inequality

$\displaystyle K\geq\lceil N/2\rceil.$ (14)

The MTSFM-CPM approximation introduces perturbations to the PC waveform’s
instantaneous phase in the form of Gibbs phenomena. These perturbations become
substantial as $K$ approaches the limit (14) and degrades the waveform’s
AF/ACF sidelobe levels. The MTSFM-CPM waveform’s ACF properties must then be
refined by modifying the modulation indices $\alpha_{k}$ and $\beta_{k}$.

##  IV Two Illustrative Design Examples

This section demonstrates the MTSFM-CPM techique via two illustrative design
examples. The first PC waveform example utilizes a binary M-Sequence code and
the second example uses a polyphase Barker code from [2].

###  IV-A M-Sequence Design Example

The following design example demonstrates the MTSFM based CPM method for a PC
waveform with $N=63$ chips utilizing an M-Sequence phase code [2]. Figure 1
shows the instantaneous phases, spectra, and ACFs of the initial PC waveform
and MTSFM-CPM waveforms composed of $K=64$ and $32$ harmonics. The original PC
waveform possessed a SC (5) of $90.27\%$ across the first spectral nulls (i.e,
$\pm 1/t_{b}$) with ACF ISR and PSL values of -3.99 dB and -15.91 dB
respectively. The MTSFM-CPM waveforms possess spectra whose sidelobes fall off
much more rapidly than the original PC waveform. Their SC values across the
same bandwidth as the PC waveform were $91.51\%$ and $98.85\%$ for $K=64$ and
$32$ harmonics respectively. The higher SC values for these waveforms are a
direct result of their increasingly smooth instantaneous phase functions.
However, the instantaneous phase of both MTSFM-CPM waveforms are perturbed by
Gibbs phenomena, an artifact of the finite Fourier series representation of
the PC waveform’s instantaneous phase. These perturbations in instantaneous
phase degrade other properties of the waveform, specifically the ACF
sidelobes. The more spectrally compact MTSFM-CPM waveform with $K=32$
harmonics sees drastically increased ISR and PSL values of -1.43 dB and -10.73
dB respectively. The MTSFM-CPM waveform is substantially more spectrally
compact than the initial PC waveform at the expense of higher ACF sidelobes.

Figure 1: Instantaneous phase (a), spectra (b), and ACFs (c) of the initial PC
waveform with an M-Sequence phase code and MTSFM-CPM waveforms with $K=64$ and
$32$ harmonics. The MTSFM-CPM waveform smoothes the abrupt phase transitions
of the PC waveform’s instantaneous phase resulting in a more spectrally
compact waveform at the cost of noticeably increased ACF sidelobes.

However, the MTSFM-CPM waveform’s ACF properties can be refined. This is
achieved by modifying the modulation indices $\alpha_{k}$ and $\beta_{k}$ to
optimize the waveform’s GISR. This re-optimization results in a MTSFM-CPM
waveform with desireably low ACF sidelobes while retaining its compact
spectral shape. Formally, the optimization problem is defined as

$\underset{\alpha_{k},\beta_{k}}{\text{min}}\left(\dfrac{\int_{\Delta\tau}^{T}|R\left(\tau\right)|^{p}d\tau}{\int_{0}^{\Delta\tau}|R\left(\tau\right)|^{p}d\tau}\right)^{2/p}\text{s.t.~{}}\\\
\beta_{rms}^{2}\left(\\{\alpha_{k},\beta_{k}\\}\right)\in\left(1\pm\delta\right)\tilde{\beta}_{rms}^{2}$
(15)

where $\delta=0.1$ is a unitless bound parameter and the GISR parameter $p=10$
favors a PSL optimization metric. The $\tilde{\beta}_{rms}^{2}$ and
$\beta_{rms}^{2}\left(\\{\alpha_{k},\beta_{k}\\}\right)$ terms are the
initialized and optimized MTSFM-CPM waveforms’ RMS bandwidths respectively
which are expressed in terms of $\alpha_{k}$ and $\beta_{k}$ as [20]

$\beta_{rms}^{2}\left(\\{\alpha_{k},\beta_{k}\\}\right)=\left(\frac{2\pi}{T}\right)^{2}\sum_{k=1}^{K}k^{2}\dfrac{\left(\alpha_{k}^{2}+\beta_{k}^{2}\right)}{2}.$
(16)

Recall from (8) that the ACF mainlobe area is inversely proportional to RMS
bandwidth [21] and thus the constraint on $\beta_{rms}^{2}$ will preserve the
ACF mainlobe widith. The _fmincon_ function in MATLAB’s Optimization Toolbox
[29] is used to minimize (15). This optimization function utilizes a
Sequential Quadratic Programming (SQP) method in order to handle the nonlinear
constraints in (15) and does not guarantee convergence to a global minimum.
Figure 2 shows the spectra and ACFs of the initial PC waveform as well as the
initial and optimized MTSFM-CPM waveforms. The optimized MTSFM-CPM waveform
retains a compact spectral shape with a SC of $98.13\%$ while also possessing
substantially lower ACF sidelobes than the initial MTSFM-CPM waveform. The ISR
and PSL values for this optimized MTSFM-CPM waveform are $-5.86$ dB and
$-25.63$ dB respectively. The optimized MTSFM-CPM waveform is not only more
spectrally compact than the original PC waveform, but also possesses
substantially lower ACF sidelobes than it as well.

Figure 2: Spectra (a) and ACFs (b) of the initial and optimized MTSFM-CPM
waveforms. The optimized MTSFM-CPM waveform possesses lower ACF sidelobes than
both the initial MTSFM-CPM and PC waveform while also preserving the
waveform’s compact spectral shape.

###  IV-B Polyphase Barker Code Design Example

The results from the previous design example showed that re-optimizing the
MTSFM-CPM waveform’s modulation indices produced a spectrally compact waveform
with ACF sidelobes that were lower than the initial PC waveform from which the
MTSFM-CPM was derived. However, the following design example shows that such a
result is not always possible. Figure 3 shows the spectra and ACFs of a PC
waveform with $N=65$ chips employing a polyphase Barker code and two optimized
MTSFM-CPM waveforms derived from it with $K=65$ and $K=33$ harmonics
representing their instantaneous phase. While the MTSFM-CPM waveform with
$K=33$ harmonics was clearly the most spectrally compact, its ACF sidelobes
were more than 10 dB higher than the initial PC waveform’s ACF sidelobes. The
MTSFM-CPM waveform with $K=65$ harmonics achieved much lower ACF sidelobes and
were closer to that of the initial PC waveform’s ACF sidelobes. This waveform
also possessed a spectrum whose sidelobes fell off more rapidly with
increasing frequency than the inital PC waveform. However, it did not
concentrate as much of its spectral energy as densely as the initial PC
waveform with a SC of $83.39\%$ computed over the PC waveform’s null-to-null
bandwidth. Increasing $K$ produced a MTSFM-CPM waveform with lower ACF
sidelobes at the expense of reduced SC. This example shows that the choice of
$K$ in the MTSFM-CPM introduces a tradeoff between SC and low ACF sidelobes.

Figure 3: Spectra (a) and ACFs (b) of original PC waveform and optimized
MTSFM-CPM waveforms with $K=33$ and $65$ harmonics. The MTSFM-CPM waveform
with $K=33$ harmonics possesses better SC but higher sidelobes than the $K=65$
harmonic MTSFM-CPM waveform. Neither MTSFM-CPM waveform achieves the same low
sidelobe levels as the original PC waveform.

##  V Conclusion

This paper describes a CPM technique for improving on a PC waveform’s SC
properties utilizing the MTSFM-CPM waveform model. The PC waveform’s
instantaneous phase is represented as a finite Fourier series which smooths
its abrupt phase transitions resulting in a more spectrally compact waveform.
This smoothing of the PC waveform’s instantaneous phase introduces
perturbations to it which degrades the resulting MTSFM-CPM waveform’s ACF
sidelobe structure. Adjusting the MTSFM-CPM waveform’s modulation indices
refines its ACF sidelobes while also largely preserving its compact spectral
shape. Adjusting the number of harmonics $K$ in the MTSFM-CPM model
facilitates trading off between SC and preserving the original PC waveform’s
low ACF sidelobe levels. A lower $K$ produces MTSFM-CPM waveforms with higher
SC but increased ACF sidelobe levels. A higher K produces MTSFM-CPM waveforms
with lower ACF sidelobes at the expense of degraded SC. Future efforts will
focus on a more through analysis of the tradeoff between SC and ACF sidelobe
levels through the choice of the number of harmonics $K$ for a wide variety of
phase code lengths $N$. Also of interest is extending this method to designing
families of spectrally compact waveforms with desireable Auto and Cross-
Correlation Function properties.

## Acknowledgment

The author would like to thank Professor John R. Buck at the University of
Massachusetts Dartmouth for the many insightful converstations during the
author’s dissertation studies that inspired this work.

## References

  * [1] S. D. Blunt and E. L. Mokole, “Overview of radar waveform diversity,” _IEEE Aerospace and Electronic Systems Magazine_ , vol. 31, no. 11, pp. 2–42, November 2016.
  * [2] E. M. N. Levanon, _Radar Signals_. Wiley-Interscience, 2004.
  * [3] P. Stoica, J. Li, and Y. Xie, “On probing signal design for mimo radar,” _IEEE Transactions on Signal Processing_ , vol. 55, no. 8, pp. 4151–4161, Aug 2007.
  * [4] L. Wu, P. Babu, and D. P. Palomar, “Transmit waveform/receive filter design for mimo radar with multiple waveform constraints,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 6, pp. 1526–1540, March 2018\.
  * [5] G. Cui, H. Li, and M. Rangaswamy, “Mimo radar waveform design with constant modulus and similarity constraints,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 2, pp. 343–353, Jan 2014.
  * [6] A. Aubry, A. DeMaio, A. Farina, and M. Wicks, “Knowledge-aided (potentially cognitive) transmit signal and receive filter design in signal-dependent clutter,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 49, no. 1, pp. 93–117, Jan 2013.
  * [7] A. Aubry, A. De Maio, M. Piezzo, M. M. Naghsh, M. Soltanalian, and P. Stoica, “Cognitive radar waveform design for spectral coexistence in signal-dependent interference,” in _2014 IEEE Radar Conference_ , May 2014, pp. 0474–0478.
  * [8] L. Wu, P. Babu, and D. P. Palomar, “Cognitive radar-based sequence design via sinr maximization,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 3, pp. 779–793, Feb 2017.
  * [9] A. Aubry, A. De Maio, B. Jiang, and S. Zhang, “Ambiguity function shaping for cognitive radar via complex quartic optimization,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 22, pp. 5603–5619, Nov 2013\.
  * [10] J. Song, P. Babu, and D. P. Palomar, “Sequence set design with good correlation properties via majorization-minimization,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 11, pp. 2866–2879, June 2016\.
  * [11] R. Zhou, Z. Zhao, and D. P. Palomar, “Unified framework for minimax mimo transmit beampattern matching under waveform constraints,” in _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , May 2019, pp. 4150–4154.
  * [12] L. Wu and D. P. Palomar, “Sequence design for spectral shaping via minimization of regularized spectral level ratio,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 18, pp. 4683–4695, Sep. 2019.
  * [13] A. Bose and M. Soltanalian, “Constructing binary sequences with good correlation properties: An efficient analytical-computational interplay,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 11, pp. 2998–3007, June 2018.
  * [14] _Radar Spectrum Engineering Criteria_. U.S. National Telecommunications and Information Administration., Jan 2008.
  * [15] D. A. Hague and J. R. Buck, “An experimental evaluation of the generalized sinusoidal frequency modulated waveform for active sonar systems,” _The Journal of the Acoustical Society of America_ , vol. 145, no. 6, pp. 3741–3755, 2019.
  * [16] S. D. Blunt, M. Cook, J. Jakabosky, J. D. Graaf, and E. Perrins, “Polyphase-coded fm (pcfm) radar waveforms, part i: implementation,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 50, no. 3, pp. 2218–2229, July 2014.
  * [17] S. D. Blunt, J. Jakabosky, M. Cook, J. Stiles, S. Seguin, and E. L. Mokole, “Polyphase-coded fm (pcfm) radar waveforms, part ii: optimization,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 50, no. 3, pp. 2230–2241, July 2014.
  * [18] P. S. Tan, J. Jakabosky, J. M. Stiles, and S. D. Blunt, “On higher-order representations of polyphase-coded fm radar waveforms,” in _2015 IEEE Radar Conference (RadarCon)_ , May 2015, pp. 0467–0472.
  * [19] Y. Sun, H. Fan, J. Wang, L. Ren, E. Mao, and T. Long, “Optimization of diverse pcfm waveforms and joint mismatched filters,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 57, no. 3, pp. 1840–1854, 2021.
  * [20] D. A. Hague, “Adaptive transmit waveform design using multitone sinusoidal frequency modulation,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 57, no. 2, pp. 1274–1287, 2021.
  * [21] A. Rihaczek, _Principles of high-resolution radar_. McGraw-Hill, 1969.
  * [22] C. A. Mohr, P. M. McCormick, C. A. Topliff, S. D. Blunt, and J. M. Baden, “Gradient-based optimization of pcfm radar waveforms,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 57, no. 2, pp. 935–956, 2021.
  * [23] J. Song, P. Babu, and D. P. Palomar, “Sequence design to minimize the weighted integrated and peak sidelobe levels,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 8, pp. 2051–2064, 2016.
  * [24] E. Raei, M. Alaee-Kerahroodi, P. Babu, and M. R. B. Shankar, “Design of mimo radar waveforms based on lp-norm criteria,” 2021.
  * [25] L. J. Giacoletto, “Generalized theory of multitone amplitude and frequency modulation,” _Proceedings of the IRE_ , vol. 35, no. 7, pp. 680–693, July 1947.
  * [26] D. A. Hague, “The generalized sinusoidal frequency modulated waveform for active sonar,” Ph.D. dissertation, Univ. of Massachusetts Dartmouth, Dartmouth, MA, 2015.
  * [27] J. P. Boyd, _Chebyshev and Fourier spectral methods_. Courier Corporation, 2001.
  * [28] D. A. Hague, “Transmit waveform design using multi-tone sinusoidal frequency modulation,” in _2017 IEEE Radar Conference (RadarConf)_ , 2017, pp. 0356–0360.
  * [29] “Matlab optimization toolbox,” 2018b, the MathWorks, Natick, MA, USA.


Lipschitz Functions on Sparse Graphs

Samuel Korsky, Tahsin Saffat, Dhroova Aiylam

October 2, 2023

Abstract

  * In this work we attempt to count the number of integer-valued $\displaystyle h$-Lipschitz functions (functions that change by at most $\displaystyle h$ along edges) on two classes of sparse graphs; grid graphs $\displaystyle L_{m,n}$, and sparse random graphs $\displaystyle G(n,d/n)$. We find that for all $\displaystyle n$-vertex graphs $\displaystyle G$ with $\displaystyle k$ connected components, the number of such functions grows as $\displaystyle(ch)^{n-k}$ for some $\displaystyle 1\leq c\leq 2$. In particular, letting $\displaystyle\alpha\approx 1.16234$ be the largest solution to $\displaystyle\tan{(1/x)}=x$, we prove that as $\displaystyle n\to\infty$

    * –

$\displaystyle c=\alpha\sqrt{2}\approx 1.6438$ when $\displaystyle G=L_{2,n}$

    * –

$\displaystyle 1.351\approx\alpha^{2}\leq c\leq\arctan{(3/4)}^{-1}\approx
1.554$ when $\displaystyle G=L_{n,n}$

    * –

$\displaystyle 1+\frac{1}{2d}+O\left(\frac{1}{d^{2}}\right)\leq c\leq
1+\frac{4\ln^{2}{d}}{d}+O\left(\frac{1}{d}\right)$ (w.h.p.) when
$\displaystyle G=G(n,d/n)$

##  1 Introduction

An $\displaystyle h$-Lipschitz function on a connected graph $\displaystyle G$
is an integer-valued function on the vertices of $\displaystyle G$ which
changes by at most $\displaystyle h$ between adjacent vertices, and where the
function’s value at a fixed vertex in $\displaystyle G$ is $\displaystyle 0$.
In this work we seek to count the number of such functions in the setting
where $\displaystyle h$ is large, for various classes of sparse graphs; in
particular, for grid graphs and sparse Erdős-Renyi random graphs.

Our motivation for this work comes from the extensive literature pertaining to
$\displaystyle h$-Lipschitz functions [1, 2, 3] and the related concept of
$\displaystyle\mathbb{Z}$-homomorphisms (integer functions on the vertices of
$\displaystyle G$ which change by exactly one along edges) [4, 5]. In
particular, the study of $\displaystyle h$-Lipschitz functions on
$\displaystyle d$-regular expanders [1] is closely related to our work on
random graphs, and previous work on $\displaystyle h$-Lipschitz functions on
tori [2] and $\displaystyle\mathbb{Z}$-homomorphisms on lattices [4, 5]
partially inspires our investigation on grid graphs.

The principal difference between our work and the existing literature is that
we study $\displaystyle h$-Lipschitz functions for large $\displaystyle h$
(indeed, we take $\displaystyle h\to\infty$ for the majority of our results).
In previous work [1, 2, 3], $\displaystyle h$ is generally bounded as a
function of the average or maximum degree of the graph in question. And
$\displaystyle\mathbb{Z}$-homomorphisms are more different still, with their
closest equivalent being $\displaystyle h$-Lipschitz functions for
$\displaystyle h=1$.

Note that (as mentioned in [1]) our work also has potential applications to
surface models in statistical mechanics; counting the number of $\displaystyle
h$-Lipschitz functions on a large grid graph can be interpreted as finding the
entropy of surface energy models (satisfying certain constraints) at high
temperature, where the probability distribution over valid energy
configurations is uniform.

###  1.1 Definitions

We begin with a formal definition:

Definition 1.1.1. For a given connected graph $\displaystyle G$ and a fixed
vertex $\displaystyle v\in V(G)$, let $\displaystyle\text{Lip}_{v}(G;h)$
denote the set of $\displaystyle h$-Lipschitz functions from the vertices of
$\displaystyle G$ to $\displaystyle\mathbb{Z}$ that send $\displaystyle v$ to
$\displaystyle 0$; that is, functions $\displaystyle
f:V(G)\rightarrow\mathbb{Z}$ such that $\displaystyle f(v)=0$ and
$\displaystyle|f(x)-f(y)|\leq h$ for every $\displaystyle\\{x,y\\}\in E(G)$.
It is clear that $\displaystyle\left\lvert\text{Lip}_{v}(G;h)\right\rvert$
remains the same regardless of choice of $\displaystyle v$, so we will
generally eschew the “$\displaystyle v$” subscript as we are primarily
interested in the cardinality of the set.

Note that we can extend this definition naturally to disconnected graphs by
requiring each function in $\displaystyle\text{Lip}(G;h)$ to take a fixed
vertex in each connected component of $\displaystyle G$ to $\displaystyle 0$.

Remark 1.1.2. For any $\displaystyle n$-vertex connected graph $\displaystyle
G$, $\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert$ is a polynomial of
degree $\displaystyle n-1$ in $\displaystyle\mathbb{Q}[h]$.

Proof. Enumerate the vertices of $\displaystyle G$ as
$\displaystyle\\{1,2,\dots,n\\}$. Let $\displaystyle P$ be the
$\displaystyle\left(n-1\right)$-dimensional polytope in
$\displaystyle\mathbb{R}^{n-1}$ determined by the hyperplanes
$\displaystyle|x_{i}-x_{j}|\leq 1$ for each edge in $\displaystyle G$ with
vertex labels $\displaystyle i$ and $\displaystyle j$, and $\displaystyle
x_{v}=0$ for a fixed vertex with label $\displaystyle v$. Letting
$\displaystyle\mathcal{L}=\mathbb{Z}^{n-1}$, it’s easy to see that
$\displaystyle\left\lvert\text{Lip}_{v}(G;h)\right\rvert=\\#(hP\ \cap\
\mathcal{L})$ and so $\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert$ is
an Ehrhart polynomial [6] of degree $\displaystyle n-1$.
$\displaystyle\blacksquare$

Thus when $\displaystyle h$ is large, the growth rate of
$\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert$ is governed by the
leading coefficient of the associated polynomial. This observation motivates
the following definition:

Definition 1.1.3. For any graph $\displaystyle G$ with $\displaystyle n$
vertices and $\displaystyle k<n$ connected components, let $\displaystyle
c(G)=\lim_{h\to\infty}\frac{1}{h}\cdot\left\lvert\text{Lip}(G;h)\right\rvert^{1/(n-k)}$.

It’s clear due to Remark 1.1.2 that $\displaystyle c(G)$ exists for all graphs
$\displaystyle G$. The focus of this paper is to determine exactly or to bound
$\displaystyle c(G)$ for a variety of graphs.

###  1.2 Preliminaries

We begin with basic information about $\displaystyle c(G)$ that will be useful
later.

Theorem 1.2.1. For all non-empty graphs $\displaystyle G$, we have that
$\displaystyle 1\leq c(G)\leq 2$.

Proof. Fix $\displaystyle h$ and suppose $\displaystyle
v_{1},v_{2},\dots,v_{k}\in V(G)$ are our chosen fixed vertices in each of the
$\displaystyle k$ connected components of $\displaystyle G$ that
$\displaystyle h$-Lipschitz functions will send to $\displaystyle 0$. For the
lower bound, consider the functions $\displaystyle
f:V(G)\rightarrow\mathbb{Z}$ satisfying $\displaystyle
f(v_{1})=f(v_{2})=\dots=f(v_{k})=0$ and $\displaystyle
f(w)\in\\{0,1,\dots,h\\}$ for all $\displaystyle w\in
V(G)\backslash\\{v_{1},v_{2},\dots,v_{k}\\}$. It is clear that all such
functions belong to $\displaystyle\text{Lip}(G;h)$ which implies that
$\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert\geq(h+1)^{n-k}$ and thus
$\displaystyle c(G)\geq 1$.

For the upper bound, take a maximal spanning forest of $\displaystyle G$ with
trees rooted at $\displaystyle v_{1},v_{2},\dots,v_{k}$ and perform a depth-
first search of each tree. For each vertex $\displaystyle w$, suppose the
value of a function $\displaystyle f\in\text{Lip}(G;h)$ at its parent
$\displaystyle u$ has already been determined. Then we must have that
$\displaystyle f(w)\in\\{f(u)-h,f(u)-h+1,\dots,f(u)+h\\}$ so there are at most
$\displaystyle 2h+1$ possible values that each $\displaystyle f(w)$ can
attain. Therefore we have
$\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert\leq(2h+1)^{n-k}$ and thus
$\displaystyle c(G)\leq 2$. $\displaystyle\blacksquare$

Intuitively, dense graphs should have $\displaystyle c(G)$ closer to
$\displaystyle 1$, while sparse graphs should have $\displaystyle c(G)$ closer
to $\displaystyle 2$. We formalize this intuition using the most extreme
examples of dense graphs (complete graphs) and connected sparse graphs (trees)
below:

Theorem 1.2.2.
$\displaystyle\left\lvert\text{Lip}(T;h)\right\rvert=(2h+1)^{n-1}$ for all
trees $\displaystyle T$ with $\displaystyle n$ vertices.

Proof. This follows immediately from the proof of the upper bound in Theorem
1.2.1, where we have equality. Note that this implies that $\displaystyle
c(T)=2$. $\displaystyle\blacksquare$

Corollary 1.2.3. If we are counting the number of $\displaystyle h$-Lipschitz
functions $\displaystyle f$ on a connected $\displaystyle n$-vertex graph
$\displaystyle G$ and the values of $\displaystyle f$ on $\displaystyle j$
vertices have already been determined, there are at most
$\displaystyle(2h+1)^{n-j}$ ways to assign the remaining values of
$\displaystyle f$.

We will make extensive use of Corollary 1.2.3 in Section 3 of the paper.

Theorem 1.2.4.
$\displaystyle\left\lvert\text{Lip}(K_{n};h)\right\rvert=(h+1)^{n}-h^{n}$ for
the $\displaystyle n$-vertex complete graph $\displaystyle K_{n}$.

Proof. For each $\displaystyle f\in\text{Lip}(K_{n};h)$, consider the function
$\displaystyle g=f-\min_{w\in V(K_{n})}f(w)$. Then $\displaystyle g$ is a
function from $\displaystyle V(K_{n})$ to $\displaystyle\mathbb{N}$ that
includes $\displaystyle 0$ in its range and satisfies
$\displaystyle|g(u)-g(w)|\leq h$ for each pair of vertices $\displaystyle
u,w\in K_{n}$. It is clear that there is a bijective mapping between functions
$\displaystyle f$ and $\displaystyle g$, so it suffices to count the number of
such functions $\displaystyle g$.

Since $\displaystyle 0$ is in the range of $\displaystyle g$, we must have
that $\displaystyle g(w)\in\\{0,1,\dots,h\\}$ for all $\displaystyle w\in
V(K_{n})$. There are then $\displaystyle(h+1)^{n}$ ways in which to construct
the function $\displaystyle g$. However $\displaystyle h^{n}$ of those do not
include $\displaystyle 0$ in their range, hence the total number of such
functions is $\displaystyle(h+1)^{n}-h^{n}$ as desired. Note that this implies
that $\displaystyle c(K_{n})=\sqrt[n-1]{n}$. $\displaystyle\blacksquare$

###  1.3 Main Results

Below we present our main results, as well as discuss the organization of the
paper:

Let $\displaystyle L_{m,n}$ denote the $\displaystyle m\times n$ grid graph
(the graph Cartesian product of two paths of length $\displaystyle m$ and
$\displaystyle n$), and let $\displaystyle G(n,p)$ denote the Erdős-Renyi
random graph on $\displaystyle n$ vertices with edge probability
$\displaystyle p$. Additionally, let $\displaystyle\alpha\approx 1.16234$ be
the largest solution to $\displaystyle\tan{(1/x)}=x$. Our main results are as
follows:

  * •

$\displaystyle\lim_{n\to\infty}c(L_{2,n})=\alpha\sqrt{2}\approx 1.6437$

  * •

$\displaystyle
1.351\approx\alpha^{2}\leq\lim_{n\to\infty}c(L_{n,n})\leq\frac{1}{\arctan(3/4)}\approx
1.554$

  * •

$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[1+\frac{1}{2d}+O\left(\frac{1}{d^{2}}\right)\leq
c\left(G\left(n,d/n\right)\right)\leq
1+\frac{4\ln^{2}{d}}{d}+O\left(\frac{1}{d}\right)\right]=1$

The paper is organized as follows: In Section $\displaystyle 2$ we study
$\displaystyle h$-Lipschitz functions on grid graphs, and in Section
$\displaystyle 3$ we study $\displaystyle h$-Lipschitz functions on sparse
random graphs.

##  2 Grid Graphs

Grid graphs are a particularly interesting domain in which to study
$\displaystyle h$-Lipschitz functions, in part due to their natural connection
with surface models in statistical mechanics. These graphs have unique
characteristics which prevent us from using some of the techniques we apply
later for random graphs; specifically, the diameter of grid graphs is
polynomial in number of vertices, rather than logarithmic.

###  2.1 Upper-Bounding $\displaystyle\lim_{n\to\infty}c(L_{n,n})$

Our main idea for upper bounding $\displaystyle c(L_{n,n})$ is to upper bound
the number of ways to construct an $\displaystyle h$-Lipschitz function
$\displaystyle f$ on each row of the grid, given that the values of
$\displaystyle f$ have already been determined for the row above. We first
utilize a beautiful lemma that lets us assume that $\displaystyle f$ attains
the value $\displaystyle 0$ on each vertex in the row above, which makes it
easy to write a recurrence for the number of ways we can construct
$\displaystyle f$ on our given row. Taking $\displaystyle h\to\infty$ then
allows us to convert this recurrence into a solvable differential equation.

We begin our exposition with this lemma:

Lemma 2.1.1. Given two centrally-symmetric convex sets $\displaystyle A,B$ in
$\displaystyle\mathbb{R}^{n}$ where $\displaystyle A\cap(B+v)$ is compact for
any vector $\displaystyle v\in\mathbb{R}^{n}$, let $\displaystyle
f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be the function $\displaystyle
f(v)=\text{Vol}(A\cap(B+v))$, where Vol denotes $\displaystyle n$-dimensional
volume. Then $\displaystyle f(v)$ is maximized at $\displaystyle v=0$.

Proof. Fix $\displaystyle v$, and note that by symmetry $\displaystyle
f(v)=f(-v)$. Consider any two $\displaystyle x\in A\cap(B+v)$ and
$\displaystyle y\in A\cap(B-v)$. Since $\displaystyle x,y\in A$ by convexity
we have that $\displaystyle\frac{x+y}{2}\in A$. Similarly, since
$\displaystyle x-v,y+v\in B$ we have that
$\displaystyle\frac{(x-v)+(y+v)}{2}\in B$, so $\displaystyle\frac{x+y}{2}\in
A\cap B$. Therefore
$\displaystyle\frac{1}{2}\left(A\cap(B+v)\right)+\frac{1}{2}\left(A\cap(B-v)\right)\subseteq
A\cap B$.

Now, by the Brunn-Minkowski Theorem [7] we have that

$\displaystyle\displaystyle f(0)$ $\displaystyle\displaystyle=\text{Vol}(A\cap
B)$
$\displaystyle\displaystyle\geq\text{Vol}\left(\frac{1}{2}\left(A\cap(B+v)\right)+\frac{1}{2}\left(A\cap(B-v)\right)\right)$
$\displaystyle\displaystyle\geq\left(\text{Vol}\left(\frac{1}{2}\left(A\cap(B+v)\right)\right)^{1/n}+\text{Vol}\left(\frac{1}{2}\left(A\cap(B-v)\right)\right)^{1/n}\right)^{n}$
$\displaystyle\displaystyle=\left(\frac{1}{2}\cdot f(v)^{1/n}+\frac{1}{2}\cdot
f(-v)^{1/n}\right)^{n}$ $\displaystyle\displaystyle=f(v)$

as desired. $\displaystyle\blacksquare$

This lemma is quite useful for upper-bounding $\displaystyle c(G)$ because it
will let us show that the scenario in which the number of $\displaystyle
h$-Lipschitz functions on a given set of vertices is (roughly) maximized is
when $\displaystyle f$ attains the value of $\displaystyle 0$ on the
neighboring vertices. We formalize this below:

Corollary 2.1.2. Let $\displaystyle G$ be an $\displaystyle n$-vertex
connected graph and let $\displaystyle T=\\{v_{1},v_{2},\dots,v_{m}\\}\subset
V(G)$ be a proper subset of vertices in $\displaystyle G$. For any
$\displaystyle w=(w_{1},w_{2},\dots,w_{m})\in\mathbb{Z}^{m}$ with
$\displaystyle w_{1}=0$, let $\displaystyle V_{w}$ denote the set of
$\displaystyle h$-Lipschitz functions $\displaystyle f$ (that fix
$\displaystyle f(v_{1})=0$) on $\displaystyle G$ satisfying $\displaystyle
f(v_{i})=w_{i}$ for all $\displaystyle i$. Then
$\displaystyle|V_{0}|\geq\left(1-O(h^{-1})\right)\max_{w}|V_{w}|$

Proof. Let $\displaystyle V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$ (the first
$\displaystyle m$ of these vertices belong to $\displaystyle T$).
Additionally, let $\displaystyle A$ be the set of points
$\displaystyle(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$ satisfying
$\displaystyle|x_{i}-x_{j}|\leq h$ for all $\displaystyle\\{v_{i},v_{j}\\}\in
E(G)$ and let $\displaystyle B$ be the set of points in
$\displaystyle\mathbb{R}^{n}$ satisfying $\displaystyle x_{i}=0$ for all
$\displaystyle i\in\\{1,2,\dots,m\\}$. Finally, let $\displaystyle
w^{*}=(w_{1},w_{2},\dots,w_{m},0,0,\dots,0)\in\mathbb{Z}^{n}$. It is clear
that there is a one-to-one correspondence between lattice points in
$\displaystyle A\cap(B+w^{*})$ and $\displaystyle h$-Lipschitz functions in
$\displaystyle V_{w}$.

Letting Vol denote $\displaystyle(n-m)$-dimensional volume, it is
geometrically evident [8] that

$\displaystyle\\#\left(\left(A\cap(B+w^{*})\right)\cap\mathbb{Z}^{n}\right)-\text{Vol}(A\cap(B+w^{*}))=O(h^{n-m-1})$

Because $\displaystyle A$ and $\displaystyle B$ are both convex and centrally-
symmetric, an application of Lemma 2.1.1 then immediately implies that
$\displaystyle|V_{0}|\geq\left(1-O(h^{-1})\right)|V_{w}|$ as desired.
$\displaystyle\blacksquare$

Corollary 2.1.3. If the subgraph $\displaystyle G[T]$ induced by the vertices
in $\displaystyle T$ is connected, then
$\displaystyle|V_{0}|\geq\left(1-O(h^{-1})\right)(2h+1)^{1-|T|}\left\lvert\text{Lip}(G;h)\right\rvert$.

Proof. Because $\displaystyle G[T]$ is connected, the argument from the proof
of the upper bound in Theorem 1.2.1 implies that the number of possible
vectors $\displaystyle w$ satisfying the Lipschitz condition is
$\displaystyle(2h+1)^{|T|-1}$. The result then follows immediately from
Corollary 2.1.2. $\displaystyle\blacksquare$

Using the idea from Corollary 2.1.2, we can prove our first main result:

Theorem 2.1.4.
$\displaystyle\lim_{n\to\infty}c(L_{n,n})\leq\frac{1}{\arctan(3/4)}\approx
1.554$.

Proof. Fix $\displaystyle n$, and suppose we have some $\displaystyle
h$-Lipschitz function $\displaystyle f$ on our grid graph $\displaystyle
L_{n,n}$. Consider some row (other than the top row) of the grid, and denote
by $\displaystyle v_{1},v_{2},\dots,v_{n}$ the vertices (in order) of this
row. Furthermore, fix the values (in order) of $\displaystyle f$ on the
vertices in the row above this row as $\displaystyle
w=(w_{1},w_{2},\dots,w_{n})\in\mathbb{Z}^{n}$.

Let $\displaystyle\beta=\arctan(3/4)^{-1}\approx 1.554$. The key idea will be
to prove that there are $\displaystyle O\left((\beta{h}+o(h))^{n}\right)$ ways
to assign values of $\displaystyle f(v_{i})$ that satisfy the Lipschitz
condition - this will imply the theorem, since we can build $\displaystyle f$
one row at a time and bound the number of possibilities each time.

By Corollary 2.1.2, for bounding purposes we can assume that $\displaystyle
w=0$. Under this assumption, let $\displaystyle a(r,s)$ denote the number of
ways to assign values to each of $\displaystyle
f(v_{1}),f(v_{2}),\dots,f(v_{r})$ such that $\displaystyle f(v_{r})=s$. We
immediately obtain the recurrence $\displaystyle
a(r,s)=\sum_{i=s-h}^{h}a(r-1,i)$ for $\displaystyle s\geq 0$ (note that by
symmetry $\displaystyle a(r,s)=a(r,-s)$). Letting $\displaystyle a(r)$ be the
column vector $\displaystyle\left[a(r,-h),a(r,-h+1),\dots,a(r,h)\right]^{T}$
this recurrence is equivalent to the equation:

$\displaystyle M_{h}\cdot a(r-1)=a(r)$

where $\displaystyle M_{h}$ is a binary $\displaystyle(2h+1)\times(2h+1)$
matrix with entries satisfying $\displaystyle m_{ij}=1$ when
$\displaystyle|i-j|\leq h$ and $\displaystyle m_{ij}=0$ otherwise.

Clearly, to determine the growth rate of $\displaystyle a(r,s)$ it suffices to
determine the largest eigenvalue of $\displaystyle M_{h}$. As $\displaystyle
h\to\infty$, $\displaystyle M_{h}$ becomes a more and more granular discrete
approximation of the linear operator $\displaystyle M_{\infty}$ on
$\displaystyle\mathcal{L}^{2}([-1,1])$ that satisfies (for $\displaystyle
x\geq 0$)

$\displaystyle M_{\infty}\cdot g(x)=\int_{x-1}^{1}g(t)\ dt$

Now let $\displaystyle b(x)$ be the eigenfunction of $\displaystyle
M_{\infty}$ corresponding to its largest eigenvalue - because $\displaystyle
b$ is symmetric about $\displaystyle 0$, we may restrict our attention to the
interval $\displaystyle[0,1]$. It is clear that $\displaystyle b(x)$ satisfies
the following differential equation for some eigenvalue
$\displaystyle\lambda$:

$\displaystyle\displaystyle\lambda\cdot b(x)$
$\displaystyle\displaystyle=\int_{0}^{1}b(t)\ dt+\int_{0}^{1-x}b(t)\ dt$ (1)

Differentiating both sides we obtain

$\displaystyle\displaystyle\lambda\cdot b^{\prime}(x)$
$\displaystyle\displaystyle=-b(1-x)$ (2)

and differentiating again we obtain the second-order linear differential
equation

$\displaystyle\displaystyle\lambda^{2}\cdot b^{\prime\prime}(x)$
$\displaystyle\displaystyle=-b(x)$ (3)

The solution to equation (3) is then given by $\displaystyle
b(x)=c_{1}\cos\left(\frac{x}{\lambda}\right)+c_{2}\sin\left(\frac{x}{\lambda}\right)$
for some $\displaystyle c_{1},c_{2}\in\mathbb{R}$. Plugging this solution in
to the equation (2) and using the cosine and sine sum formulas, we match terms
and obtain

$\displaystyle
c_{1}\cos\left(\frac{1}{\lambda}\right)+c_{2}\sin\left(\frac{1}{\lambda}\right)=c_{2}$

Additionally, by letting $\displaystyle x=0$ and $\displaystyle x=1$ in
equation (1) we see that $\displaystyle b(1)=2b(0)$, or

$\displaystyle
c_{1}\cos\left(\frac{1}{\lambda}\right)+c_{2}\sin\left(\frac{1}{\lambda}\right)=2c_{1}$

Thus $\displaystyle\frac{1}{\lambda}$ is the solution to
$\displaystyle\cos(x)+2\sin(x)=2$ which we can easily solve to find
$\displaystyle\lambda=\frac{1}{\arctan(3/4)}=\beta$.

Returning to discrete space, this implies that the largest eigenvalue of
$\displaystyle M_{h}$ is given by $\displaystyle\beta{h}+o(h)$, so
$\displaystyle a(r,s)=O\left((\beta{h}+o(h))^{r-1}\right)$ for all
$\displaystyle r$ and $\displaystyle s$. Taking $\displaystyle r=n$ we have

$\displaystyle\sum_{s=-h}^{h}a(n,s)=O\left((\beta{h}+o(h))^{n}\right)$

as desired. The theorem then immediately follows from an application of
Corollary 2.1.2. $\displaystyle\blacksquare$

###  2.2 Lower-Bounding $\displaystyle\lim_{n\to\infty}c(L_{n,n})$

We first take a brief detour, and devote our attention to $\displaystyle
L_{2,n}$. We will find $\displaystyle\lim_{n\to\infty}c(L_{2,n})$ using the
same techniques as in the proof of Theorem 2.1.4, although the resulting
differential equation will be slightly more complex.

Our method of proof for the $\displaystyle L_{n,n}$ case will then be to
analyze $\displaystyle\text{Lip}(L_{2,n};h)$ and use our findings to lower
bound the average number of ways we can assign values to an $\displaystyle
h$-Lipschitz function $\displaystyle f$ on a row of the grid $\displaystyle
L_{n,n}$ given that the values on the row below have already been determined.

Theorem 2.2.1. $\displaystyle\lim_{n\to\infty}c(L_{2,n})=\alpha\sqrt{2}\approx
1.6437$, where $\displaystyle\alpha$ is the largest solution to $\displaystyle
x=\tan\left(\frac{1}{x}\right)$.

Proof. Fix $\displaystyle n$, and suppose we have some $\displaystyle
h$-Lipschitz function $\displaystyle f$ on our grid graph $\displaystyle
L_{2,n}$ that takes the vertex in the top left corner of the grid to
$\displaystyle 0$. Suppose we assign values to $\displaystyle f$ one column at
a time, and let $\displaystyle a(r,s)$ denote the number of ways to assign
values to the first $\displaystyle r$ columns of $\displaystyle L_{2,n}$ such
that if $\displaystyle v_{r,1},v_{r,2}$ are the top and bottom vertices
respectively in the $\displaystyle r$th column of $\displaystyle L_{2,n}$,
then $\displaystyle f(v_{r,1})-f(v_{r,2})=s$. Note that $\displaystyle
a(1,s)=1$ for all $\displaystyle s\in\\{-h,-h+1,\dots,h\\}$.

We immediately obtain the recurrence

$\displaystyle a(r,s)=\sum_{i=-h}^{h}a(r-1,i)\cdot(2h+1-|s-i|)$

Letting $\displaystyle a(r)$ be the column vector $\displaystyle
h^{-r+1}\cdot\left[a(r,-h),a(r,-h+1),\dots,a(r,h)\right]^{T}$ this recurrence
is equivalent to the equation:

$\displaystyle M_{h}\cdot a(r-1)=a(r)$

where $\displaystyle M_{h}$ is a $\displaystyle(2h+1)\times(2h+1)$ matrix with
entries satisfying $\displaystyle m_{ij}=2-\frac{|i-j|-1}{h}$.

Clearly, to determine the growth rate of $\displaystyle h^{-r+1}\cdot a(r,s)$
it suffices to determine the largest eigenvalue of $\displaystyle M_{h}$. By
taking $\displaystyle h\to\infty$, we can (as in the proof of Theorem 2.1.4)
consider the corresponding linear operator $\displaystyle M_{\infty}$ on
$\displaystyle\mathcal{L}^{2}([-1,1])$. Let $\displaystyle b(x)$ be the
eigenfunction of $\displaystyle M_{\infty}$ corresponding to its largest
eigenvalue $\displaystyle\lambda$ \- it is clear that $\displaystyle b(x)$
satisfies:

$\displaystyle\displaystyle\lambda\cdot b(x)$
$\displaystyle\displaystyle=\int_{-1}^{x}(2+t-x)b(t)\
dt+\int_{x}^{1}(2-t+x)b(t)\ dt$ (4)

Note that $\displaystyle b(x)=b(-x)$ so we will restrict our attention to
$\displaystyle x\geq 0$. Differentiating both sides with respect to
$\displaystyle x$ we obtain

$\displaystyle\displaystyle\lambda\cdot b^{\prime}(x)$
$\displaystyle\displaystyle=\left(2b^{\prime}(x)-\int_{-1}^{x}b(t)\
dt\right)+\left(-2b^{\prime}(x)+\int_{x}^{1}b(t)\
dt\right)=-2\int_{0}^{x}b(t)\ dt$ (5)

and differentiating again we obtain the second-order linear differential
equation

$\displaystyle\displaystyle\lambda\cdot b^{\prime\prime}(x)$
$\displaystyle\displaystyle=-2b(x)$ (6)

Let $\displaystyle\gamma=\sqrt{2/\lambda}$. Once again the solution to
equation (6) is then given by $\displaystyle
b(x)=c_{1}\cos\left(\gamma{x}\right)+c_{2}\sin\left(\gamma{x}\right)$ for some
$\displaystyle c_{1},c_{2}\in\mathbb{R}$. But note that from equation (5) we
have that $\displaystyle b^{\prime}(0)=0$, so $\displaystyle c_{2}=0$ and
$\displaystyle b(x)=c_{1}\cos\left(\gamma{x}\right)$, and we may assume
without loss of generality that $\displaystyle c_{1}=1$. Finally, plugging
this expression in to the equation (4) we obtain

$\displaystyle\lambda\cdot b(x)=\frac{2}{\gamma^{2}}\cdot
b(x)+\frac{2}{\gamma}\cdot\sin(\gamma)-\frac{2}{\gamma^{2}}\cos(\gamma)$

But since $\displaystyle\lambda=\frac{2}{\gamma^{2}}$ after canceling we have
that $\displaystyle\gamma$ is the smallest positive solution to
$\displaystyle\tan(\gamma)=\frac{1}{\gamma}$. Thus
$\displaystyle\gamma=\frac{1}{\alpha}$ and $\displaystyle\lambda=2\alpha^{2}$.

Returning to discrete space, this implies that the largest eigenvalue of
$\displaystyle M_{h}$ is given by $\displaystyle 2\alpha^{2}{h}+o(h)$, so
$\displaystyle h^{-r+1}\cdot
a(r,s)=\Omega\left(\left(2\alpha^{2}\cdot{h}+o(h)\right)^{r-1}\right)$ for all
$\displaystyle s$. Taking $\displaystyle r=n$ we have

$\displaystyle\sum_{s=-h}^{h}a(n,s)=\Omega\left((\alpha\sqrt{2}h+o(h))^{2n-1}\right)$

which immediately implies that
$\displaystyle\lim_{n\to\infty}c(L_{2,n})=\alpha\sqrt{2}$ as desired.
$\displaystyle\blacksquare$

We can use this result about $\displaystyle L_{2,n}$ to obtain an upper bound
on $\displaystyle\lim_{n\to\infty}c(L_{n,n})$. In particular, we can show:

Theorem 2.2.2. $\displaystyle\lim_{n\to\infty}c(L_{n,n})\geq\alpha^{2}\approx
1.35103$.

Proof. Fix $\displaystyle n$ and let $\displaystyle S\subset\mathbb{Z}^{n}$ be
the set of all vectors $\displaystyle(0,x_{2},\dots,x_{n})\in\mathbb{Z}^{n}$
such that $\displaystyle|x_{2}|\leq h$ and $\displaystyle|x_{i+1}-x_{i}|\leq
h$ for all $\displaystyle i\geq 2$. For simplicity, we will focus on
constructing $\displaystyle h$-Lipschitz functions $\displaystyle f$ that
attain $\displaystyle 0$ on each vertex of the left-most column of the
$\displaystyle L_{n,n}$ grid.

Call two vectors $\displaystyle x,y\in S$ mutually close if
$\displaystyle\|x-y\|_{\infty}\leq h$ and, let $\displaystyle S(x)\subset S$
denote the set of vectors $\displaystyle y\in S$ such that $\displaystyle y$
is close to $\displaystyle x$. We will build an $\displaystyle h$-Lipschitz
function $\displaystyle f$ on the vertices of the $\displaystyle L_{n,n}$ one
row at a time, and count how many such functions exist.

Let $\displaystyle a(k,x)$ denote the number of $\displaystyle h$-Lipschitz
functions $\displaystyle f$ on $\displaystyle L_{k,n}$ where $\displaystyle
x\in S$ corresponds to the values of $\displaystyle f$ of the top row, and
where $\displaystyle f$ attains $\displaystyle 0$ on each vertex in the left-
most column of $\displaystyle L_{k,n}$. Then it’s clear that $\displaystyle
a(k,x)=\sum_{y\in S(x)}a(k-1,y)$.

Now, enumerate the $\displaystyle(2h+1)^{n-1}$ elements of $\displaystyle S$.
In the spirit of the proofs of Theorems 2.1.4 and 2.2.1, let $\displaystyle
M_{h}$ be the $\displaystyle(2h+1)^{n-1}\times(2h+1)^{n-1}$ binary matrix with
entries satisfying $\displaystyle m_{ij}=1$ if elements $\displaystyle i$ and
$\displaystyle j$ of $\displaystyle S$ are close and $\displaystyle 0$
otherwise. Based on the recurrence in the preceding paragraph, the growth rate
of $\displaystyle a(k,x)$ corresponds to the largest eigenvalue of
$\displaystyle M_{h}$.

In the proof of Theorem 2.2.1, we established that
$\displaystyle\left|\text{Lip}_{v}(L_{2,n})\right|=\Omega\left((\alpha\sqrt{2}\cdot
h+o(h))^{2n-1}\right)$ where $\displaystyle v$ denotes the vertex in the
bottom left-hand corner of the $\displaystyle L_{2,n}$ grid. Corollary 2.1.3
then implies that the number of $\displaystyle h$-Lipschitz functions on
$\displaystyle L_{2,n}$ that attain $\displaystyle 0$ on both vertices in the
left-most column of $\displaystyle L_{2,n}$ is least
$\displaystyle\left(1-O(h^{-1})\right)(2h+1)^{-1}\left|\text{Lip}_{v}(L_{2,n})\right|=\omega\left((\alpha\sqrt{2}\cdot
h+o(h))^{2n-2}\right)$.

But note also that the number of such functions $\displaystyle f$ is given by
$\displaystyle\sum_{x\in S}|S(x)|$, which can be seen by picking any vector in
$\displaystyle x\in S$ to correspond to the values of $\displaystyle f$ on the
bottom row of the grid, and then any vector in $\displaystyle S(x)$ to
correspond to the values of $\displaystyle f$ on the row above.

Therefore we have that $\displaystyle{\bf{1}}^{T}\cdot
M_{h}\cdot{\bf{1}}=\sum_{x\in S}|S(x)|=\omega\left((\alpha\sqrt{2}\cdot
h+o(h))^{2n-2}\right)$. But then we know that the largest eigenvalue
$\displaystyle\lambda$ of $\displaystyle M_{h}$ satisfies

$\displaystyle\lambda\geq\frac{{\bf{1}}^{T}\cdot
M_{h}\cdot{\bf{1}}}{{\bf{1}}^{T}\cdot{\bf{1}}}=\omega\left(\left(\alpha^{2}{h}+o(h)\right)^{n-1}\right)$

which immediately implies the result. $\displaystyle\blacksquare$

###  2.3 Improving Bounds on $\displaystyle\lim_{n\to\infty}c(L_{n,n})$

Remark 2.3.1. We can use the same techniques as in the proofs of Theorems
2.1.4 and 2.2.2 to improve both our upper and lower bound.

Indeed, suppose we knew that the number of $\displaystyle h$-Lipschitz
functions on $\displaystyle L_{3,n}$ taking a value of $\displaystyle 0$ at
each vertex in the top row of the $\displaystyle L_{3,n}$ was given by
$\displaystyle\Omega\left((\zeta{h}+o(h))^{2n}\right)$ for some
$\displaystyle\zeta\in[1,2]$. Then repeating the argument from the proof of
Theorem 2.1.4, by building an $\displaystyle h$-Lipschitz function on
$\displaystyle L_{n,n}$ two rows at a time, we would have that
$\displaystyle\lim_{n\to\infty}c(L_{n,n})\leq\zeta$.

Additionally, suppose we knew that
$\displaystyle\left|\text{Lip}(L_{3,n};h)\right|=\Omega\left((\psi{h}+o(h))^{3n-1}\right)$
for some $\displaystyle\psi\in[1,2]$. Then, re-using $\displaystyle M_{h}$ and
$\displaystyle\lambda$ and repeating the argument from the proof of Theorem
2.2.2, we have that $\displaystyle{\bf{1}}^{T}\cdot M_{h}^{2}\cdot{\bf{1}}$ is
at least
$\displaystyle\left(1-O(h^{-1})\right)(2h+1)^{-2}\left|\text{Lip}(L_{3,n};h)\right|$.
Therefore

$\displaystyle\lambda^{2}\geq\frac{{\bf{1}}^{T}\cdot
M_{h}^{2}\cdot{\bf{1}}}{{\bf{1}}^{T}\cdot{\bf{1}}}=\omega\left(\left(\frac{\psi^{3}{h^{2}}}{2}+o(h^{2})\right)^{n-1}\right)$

which implies a lower bound of
$\displaystyle\lim_{n\to\infty}c(L_{n,n})\geq\frac{\psi^{3/2}}{\sqrt{2}}$

Calculating $\displaystyle\zeta$ is quite similar to calculating
$\displaystyle\lim_{n\to\infty}c(L_{2,n})$, although it requires solving the
following more complicated differential equation:

$\displaystyle\zeta^{2}\cdot b(x,y)=\iint_{R}b(s,t)\ ds\ dt$

where $\displaystyle R$ is the region in $\displaystyle\mathbb{R}^{2}$
determined by $\displaystyle|s|,|t|\leq 1$ and $\displaystyle|x-s|\leq 1$ and
$\displaystyle|x+y-s-t|\leq 1$.

Calculating $\displaystyle\psi$ is more difficult still, with corresponding
differential equation:

$\displaystyle\psi^{3}\cdot b(x,y)=\int_{-1}^{1}\iint_{R_{k}}b(s,t)\ ds\ dt\
dk$

where $\displaystyle R_{k}$ is the region in $\displaystyle\mathbb{R}^{2}$
determined by $\displaystyle|s|,|t|\leq 1$ and $\displaystyle|x-s-k|\leq 1$
and $\displaystyle|x+y-s-t-k|\leq 1$.

We leave precise calculation of $\displaystyle\zeta$ and $\displaystyle\psi$
for future work, although a computer-assisted calculation suggests that
$\displaystyle\zeta\approx 1.4895$ and $\displaystyle\psi\approx 1.553$.
Applying these approximations results in lower and upper bounds on
$\displaystyle\lim_{n\to\infty}c(L_{n,n})$ of $\displaystyle 1.3685$ and
$\displaystyle 1.4895$ respectively.

##  3 Random Graphs

Random graphs are another natural class of graphs on which to study
$\displaystyle c(G)$. Because these graphs have much less defined structure
than grid graphs, our methods in this section are understandably more
probabilistic in nature.

###  3.1 Lower-Bounding
$\displaystyle\lim_{n\to\infty}c\left(G\left(n,d/n\right)\right)$

We begin with our lower bound, which utilizes the Losávz Local Lemma (LLL)
[9]. The main idea is to carefully construct a large number of potential
functions $\displaystyle f$, and prove that a sufficiently large proportion of
them satisfy the $\displaystyle h$-Lipschitz conditions.

Theorem 3.1.1.
$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[c\left(G\left(n,d/n\right)\right)\geq
1+\frac{1}{2d}+O\left(\frac{1}{d^{2}}\right)\right]=1$.

Proof. Let $\displaystyle G=G\left(n,d/n\right)$ for some fixed $\displaystyle
n$. It is well-known [10] that as $\displaystyle n$ increases, the degree
distribution of $\displaystyle G$ approaches a
$\displaystyle\text{Poisson}(d)$ distribution. Using the standard Poisson tail
bound

$\displaystyle\mathbf{Pr}(X\geq d+x)\leq e^{-\frac{x^{2}}{2(x+d)}}$

we have that the proportion of vertices in $\displaystyle G$ of degree at
least $\displaystyle 2d$ is with high probability at most $\displaystyle
2e^{-d/4}$.

Now, consider a function $\displaystyle f$ on the vertices of $\displaystyle
G$. For each vertex $\displaystyle v\in V(G)$ with degree less than
$\displaystyle 2d$, assign to $\displaystyle f(v)$ uniformly at random an
integer in $\displaystyle\\{0,1,\dots,\lfloor{(1+c)h}\rfloor\\}$ for some
constant $\displaystyle c>0$ to be determined later. For all other vertices
$\displaystyle v$, assign to $\displaystyle f(v)$ uniformly at random an
integer in $\displaystyle\\{\lceil{ch}\rceil,\lceil{ch}\rceil+1,\dots,h\\}$.
Using the bound proven above as well as the fact that
$\displaystyle(1+c)(1-c)<1$, with high probability there are at least
$\displaystyle((1+c)(1-c)^{4e^{-d/4}}h+o(h))^{n}$ such functions.

Now, we will lower-bound the probability that such a function $\displaystyle
f$ is $\displaystyle h$-Lipschitz. First, we will modify $\displaystyle f$
slightly so that it satisfies the condition that a fixed vertex in each
connected component in $\displaystyle G$ is sent to $\displaystyle 0$. Suppose
there are $\displaystyle k$ connected components in $\displaystyle G$; after
our initial construction of $\displaystyle f$, we level shift $\displaystyle
f$ in each connected component so that this condition is satisfied. Clearly
this transformation is at most $\displaystyle(1+c)^{k}h^{k}$-to-one (which can
be seen by considering the original value of $\displaystyle f$ on each fixed
vertex in each connected component of $\displaystyle G$).

Furthermore, it is well-known [10] that with high probability, the giant
component of $\displaystyle G$ contains at least
$\displaystyle\left(1-\frac{x}{d}+o(1)\right)n$ vertices, where $\displaystyle
x=-W\left(-de^{-d}\right)\approx de^{-d}$ and $\displaystyle W$ is the Lambert
$\displaystyle W$-function. Thus with high probability we have that
$\displaystyle k\leq e^{-d/4}n$ for sufficiently large $\displaystyle d$, so
that the number of distinct transformed functions $\displaystyle f$ is at
least $\displaystyle\left((1+c)(1-c)^{5e^{-d/4}}+o(1)\right)^{n}\cdot
h^{n-k}$, where we once again use the fact that $\displaystyle(1+c)(1-c)<1$.
With the $\displaystyle 0$ condition accounted for, it remains to lower bound
the probability that $\displaystyle|f(a)-f(b)|\leq h$ for all
$\displaystyle\\{a,b\\}\in E(G)$.

Enumerate each edge in $\displaystyle G$, and let $\displaystyle A_{i}$ be the
event that edge $\displaystyle i$ fails the Lipschitz condition. With high
probability, there are $\displaystyle\frac{dn}{2}+o(n)$ such events. It is
easy to see that any edge incident to a vertex of degree at least
$\displaystyle 2d$ cannot fail the Lipschitz condition, and for all other
edges $\displaystyle i$ we have that
$\displaystyle\mathbf{Pr}(A_{i})=\frac{c^{2}}{(1+c)^{2}}+o(1)$. Furthermore,
each of these $\displaystyle A_{i}$ is only dependent on events $\displaystyle
A_{j}$ where edge $\displaystyle j$ is incident to edge $\displaystyle i$, of
which there are at most $\displaystyle 4d-4$. Thus, letting $\displaystyle
h\to\infty$ so that we can ignore the $\displaystyle o(1)$ terms, by LLL we
have that for any $\displaystyle x>0$

$\displaystyle\frac{c^{2}}{(1+c)^{2}}\leq
x(1-x)^{4d-4}\Longrightarrow\mathbf{Pr}\left(\bigcup_{i}\bar{A_{i}}\right)\geq(1-x)^{\frac{dn}{2}+o(n)}$

Let $\displaystyle x=\frac{1}{d(d-1)}-\frac{1}{2d^{2}(d-1)^{2}}$ and
$\displaystyle c=\frac{1}{d}\sqrt{1-\frac{4}{d}}$. Noting that $\displaystyle
1-r+\frac{r^{2}}{2}\geq e^{-r}\geq 1-r$ for all $\displaystyle r\geq 0$ we
have that $\displaystyle(1-x)^{4d-4}\geq e^{-4/d}\geq 1-\frac{4}{d}$.
Furthermore, it is easy to compute that $\displaystyle x\geq\frac{1}{d^{2}}$.
Therefore

$\displaystyle\frac{c^{2}}{(1+c)^{2}}\leq
c^{2}=\frac{1}{d^{2}}\left(1-\frac{4}{d}\right)\leq x(1-x)^{4d-4}$

Thus for this choice of $\displaystyle x$ and $\displaystyle c$ we have

$\displaystyle\mathbf{Pr}\left(\bigcup_{i}\bar{A_{i}}\right)\geq(1-x)^{\frac{dn}{2}+o(n)}\geq
e^{-\frac{1}{d(d-1)}\left(\frac{dn}{2}+o(n)\right)}\geq\left(1-\frac{1}{d-1}\right)^{n/2+o(n)}$

Multiplying this lower bound on the probability that a randomly selected
$\displaystyle f$ is $\displaystyle h$-Lipschitz by the number of potential
functions $\displaystyle f$ and noting that

$\displaystyle\left(1+\frac{1}{d}\sqrt{1-\frac{4}{d}}\right)\left(1-\frac{1}{d}\sqrt{1-\frac{4}{d}}\right)^{5e^{-d/4}}\sqrt{1-\frac{1}{d-1}}=1+\frac{1}{2d}+O\left(\frac{1}{d^{2}}\right)$

then completes the proof. $\displaystyle\blacksquare$

###  3.2 Upper-Bounding
$\displaystyle\lim_{n\to\infty}c\left(G\left(n,d/n\right)\right)$

We continue with the upper bound. The main idea follows an argument made in
[1], which is that for any $\displaystyle h$-Lipschitz function $\displaystyle
f$ on a graph $\displaystyle G$, the set of vertices $\displaystyle\\{v\in
V(G)\ |\ f(v)\leq j\\}$ and the set of vertices $\displaystyle\\{v\in V(G)\ |\
f(v)>j+h\\}$ can have no edges between them. We will show that in a random
graph, with high probability there do not exist two large sets of vertices
with no edges between them. This will prove that any $\displaystyle
h$-Lipschitz function on a random graph must be “flat” (i.e. take only
$\displaystyle h+1$ distinct values) on a large portion of the graph.

We will then provide a sketch of an argument showing that the function
$\displaystyle f$ is extremely constrained on the majority of vertices outside
the “flat” portion of the graph, which improves the bound further for most
random graphs.

We begin with a helpful lemma:

Lemma 3.2.1. Let $\displaystyle G=G(n,d/n)$ and let
$\displaystyle\alpha=\frac{2\ln{d}}{d}$. Then as $\displaystyle n\to\infty$,
with high probability there do not exist disjoint vertex sets $\displaystyle
A,B\subset V(G)$ satisfying
$\displaystyle\min\left(|A|,|B|\right)\geq\alpha{n}$ with no edge between
them.

Proof. let $\displaystyle H$ denote the standard entropy function
$\displaystyle H(p)=-p\log_{2}(p)-(1-p)\log_{2}(1-p)$ and let $\displaystyle
X$ be a random variable representing the number of pairs of disjoint sets
$\displaystyle A,B\subset V(G)$ satisfying
$\displaystyle|A|=|B|=\left\lceil\alpha{n}\right\rceil$ with no edge between
them. There at most
$\displaystyle\binom{n}{2\left\lceil{\alpha{n}}\right\rceil}\cdot\binom{2\left\lceil{\alpha{n}}\right\rceil}{\left\lceil{\alpha{n}}\right\rceil}<e^{nH(2\alpha)\ln{2}}\cdot
e^{2n\alpha\ln{2}}$ pairs of sets $\displaystyle(A,B)$ satisfying the size
conditions, and the probability that any such pair contains no edges between
them is
$\displaystyle\left(1-\frac{d}{n}\right)^{{\left\lceil{\alpha{n}}\right\rceil}^{2}}\leq
e^{-dn\alpha^{2}}$. Mutliplying these values to upper bound
$\displaystyle\mathbb{E}[X]$ and noting that
$\displaystyle\mathbf{Pr}(X=0)\geq 1-\mathbb{E}[X]$, we see that it suffices
to show that $\displaystyle d\alpha^{2}-2\alpha\ln{2}-H(2\alpha)\ln{2}>0$.

Using the inequality $\displaystyle-(1-x)\ln{(1-x)}<x$ we have $\displaystyle
H(2\alpha)<-2\alpha\log_{2}\left(\frac{2\alpha}{e}\right)$. Then it’s easy to
see that

$\displaystyle
2\alpha\ln{2}+H(2\alpha)\ln{2}<-2\alpha\ln\left(\frac{\alpha}{e}\right)=\frac{4\ln{d}}{d}\cdot\ln{\left(\frac{ed}{2\ln{d}}\right)}<\frac{4\ln^{2}{d}}{d}=d\alpha^{2}$

which completes the proof. $\displaystyle\blacksquare$

Note that a similar lemma was proven in Chapter 6 of [10]. With this lemma in
hand, we may now begin the proof of our main result in this subsection:

Theorem 3.2.2.
$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[c\left(G\left(n,d/n\right)\right)\leq
1+\frac{4\ln^{2}{d}}{d}+O\left(\frac{1}{d}\right)\right]=1$.

Proof. As before, let $\displaystyle\alpha=\frac{2\ln{d}}{d}$ and let
$\displaystyle G=G(n,d/n)$. Furthermore, let $\displaystyle G^{\prime}$ denote
the largest connected component (the giant component) of $\displaystyle G$.
Consider an $\displaystyle h$-Lipschitz function $\displaystyle f$ on
$\displaystyle G^{\prime}$. We will first show that there exists
$\displaystyle j\in\mathbb{Z}$ such that for a large proportion of vertices
$\displaystyle v\in V(G^{\prime})$, $\displaystyle
f(v)\in\\{j,j+1,\dots,j+h\\}$.

Indeed let $\displaystyle j$ be the smallest integer for which
$\displaystyle|\\{v\in V(G^{\prime})\ |\ f(v)\leq j\\}|\geq\alpha{n}$. Then
using Lemma 3.2.1 we have that with high probability $\displaystyle|\\{v\in
V(G^{\prime})\ |\ f(v)>j+h\\}|<\alpha{n}$, since by the Lipschitz condition
there are no edges between these two subsets of $\displaystyle V(G^{\prime})$.
Thus

$\displaystyle|\\{v\in V(G^{\prime})\ |\
f(v)\in\\{j,j+1,\dots,j+h\\}|>m-2\alpha{n}$

where $\displaystyle|G^{\prime}|=m$. Now, let

$\displaystyle\displaystyle S$ $\displaystyle\displaystyle=\\{v\in V(G)\ |\
f(v)\in\\{j,j+1,\dots,j+h\\}\\}$ $\displaystyle\displaystyle S_{1}$
$\displaystyle\displaystyle=\\{v\in V(G)\ |\ f(v)<j\\}$
$\displaystyle\displaystyle S_{2}$ $\displaystyle\displaystyle=\\{v\in V(G)\
|\ f(v)>j+h\\}$

and suppose these vertex sets are fixed. We have that
$\displaystyle|S_{1}|,|S_{2}|<\alpha{n}$ and $\displaystyle|S|>m-2\alpha{n}$.

Let us now count the number of $\displaystyle h$-Lipschitz functions
$\displaystyle f$ satisfying these conditions. Without loss of generality we
may assume that $\displaystyle f$ sends a vertex in $\displaystyle S$ to
$\displaystyle 0$. Following the proof of Theorem 1.2.4, this implies that
there are $\displaystyle(h+1)^{|S|}-h^{|S|}<n(h+1)^{|S|-1}$ ways to assign
values for $\displaystyle f$ on the vertices in $\displaystyle S$. Once these
values have been chosen, using Corollary 1.2.3 there are at most
$\displaystyle(2h+1)^{m-|S|}$ ways to assign the remaining values of
$\displaystyle f$. Thus we have that

$\displaystyle\displaystyle\left\lvert\text{Lip}(G^{\prime};h)\right\rvert$
$\displaystyle\displaystyle\leq\sum_{\begin{subarray}{c}S\subseteq[m]\\\
|S|>m-2\alpha{n}\end{subarray}}n(h+1)^{|S|-1}(2h+1)^{m-|S|}$
$\displaystyle\displaystyle\leq n(h+1)^{m-1}\cdot\sum_{i\leq
2\alpha{n}}\binom{m}{i}\cdot 2^{2\alpha{n}}$ $\displaystyle\displaystyle\leq
n(h+1)^{m-1}\cdot 2^{H(2\alpha)n}\cdot 2^{2\alpha{n}}$
$\displaystyle\displaystyle\leq n(h+1)^{m-1}\cdot e^{d\alpha^{2}{n}}$

where the last inequality follows from the fact that $\displaystyle
H(2\alpha)\ln{2}+2\alpha\ln{2}<d\alpha^{2}$ as shown in the proof of Lemma
3.2.1. If $\displaystyle G$ has $\displaystyle k$ connected components,
Corollary 1.2.3 implies that

$\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert\leq\left\lvert\text{Lip}(G^{\prime};h)\right\rvert\cdot(2h+1)^{n-m-k+1}$

But as discussed in the proof of Theorem 3.1.1 we have with high probability
that $\displaystyle m\geq(1-e^{-d/4})n$, which immediately implies a bound of

$\displaystyle 2^{e^{-d/4}}\cdot
e^{d\alpha^{2}\cdot(1-e^{-d/4})^{-1}}=1+d\alpha^{2}+O\left(\frac{1}{d}\right)=1+\frac{4\ln^{2}{d}}{d}+O\left(\frac{1}{d}\right)$

as desired. $\displaystyle\blacksquare$

Remark 3.2.3. We will now provide a sketch of an argument that shows for most
random graphs, we can actually improve our upper bound to $\displaystyle
1+O\left(\frac{\ln{d}}{d}\right)$. In particular, that there exist fixed
constants $\displaystyle b,B>1$ such that for all sufficiently large
$\displaystyle d$,
$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[c\left(G\left(n,d/n\right)\right)\leq
1+\frac{b\ln{d}}{d}+O\left(\frac{1}{d}\right)\right]\geq 1-B^{-d/\ln{d}}$.

Sketch. As before, let $\displaystyle\alpha=\frac{2\ln{d}}{d}$ and let
$\displaystyle G=G(n,d/n)$. For simplicity, we will assume $\displaystyle G$
is connected. Once again we let $\displaystyle S$ denote the set of vertices
for which an $\displaystyle h$-Lipschitz function on $\displaystyle G$ is
“flat;” from the proof of Theorem 3.2.2, we have that
$\displaystyle|S|\geq(1-2\alpha)n$. In our proof of Theorem 3.2.2, for
vertices in $\displaystyle V(G)\backslash S$ we bounded the number of possible
values of $\displaystyle f$ on each of these vertices by $\displaystyle 2h+1$.
It turns out that this bound is incredibly weak; we claim now that for the
majority of these vertices, the number of possible values of $\displaystyle f$
is actually $\displaystyle O\left(\alpha{h}\right)$.

Indeed, suppose we remove edges in $\displaystyle G$ at random with
probability $\displaystyle 1-\Omega\left(\frac{1}{\ln{d}}\right)$. Then by a
simple probabilistic alteration argument, for all but a small number of lonely
vertices in $\displaystyle V(G)\backslash S$, we can associate with that non-
lonely vertex a set of $\displaystyle\Omega\left(\frac{1}{\alpha}\right)$
vertices in $\displaystyle S$ connected to that vertex but connected to no
other vertex in $\displaystyle V(G)\backslash S$ (post-edge removal). In
particular, use of the Poisson tail bound shows that the number of lonely
vertices roughly follows a binomial distribution with mean and variance
$\displaystyle\text{exp}\left(-\Omega(\alpha)\right)\cdot n$.

Now, recall that $\displaystyle f$ must take a value between $\displaystyle j$
and $\displaystyle j+h$ for each vertex in $\displaystyle S$. For a given non-
lonely vertex in $\displaystyle V(G)\backslash S$, because it has
$\displaystyle\Omega\left(\frac{1}{\alpha}\right)$ neighbors in $\displaystyle
S$, over all possible values of $\displaystyle f$ on the vertices in
$\displaystyle S$ the expected number of possible values of $\displaystyle f$
on this vertex that satisfy the Lipschitz condition is then
$\displaystyle\Omega\left(\alpha{h}\right)$. This proves the claim, and by
replacing the $\displaystyle 2h+1$ in the proof of Theorem 3.2.2 we find that
the claim implies the $\displaystyle 1+O\left(\alpha\right)$ bound, assuming
that there are not too many lonely vertices.

The last remaining step is to bound the probability that there is some
“adversarial” $\displaystyle S\subset V(G)$ that (post edge-removal) produces
many lonely vertices. Recall that the number of lonely vertices each set
$\displaystyle S$ produces roughly follows a binomial distribution with mean
and variance $\displaystyle\text{exp}\left(-\Omega(\alpha)\right)\cdot n$ and
the number of possible subsets $\displaystyle S$ is at most $\displaystyle
2^{n}$. Furthermore, it is well-known that the expected maximum of
$\displaystyle N$ sub-Gaussian random variables each with mean
$\displaystyle\mu$ and variance $\displaystyle\sigma^{2}$ can be bounded by
$\displaystyle\mu+\sigma\sqrt{2\log{N}}$. Applying this bound on random
variables representing the number of lonely vertices produced by a set
$\displaystyle S$ with $\displaystyle N\leq 2^{n}$ and using Markov’s
inequality then immediately implies the desired result.
$\displaystyle\blacksquare$

Remark 3.2.4. Note that the upper bound in Theorem 3.2.2 is only non-trivial
for large $\displaystyle d$. Thus we must utilize a different argument to show
that
$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[c\left(G\left(n,d/n\right)\right)<2\right]=1$
for all $\displaystyle d>1$.

The idea will be to with high probability find a “ladder-like” structure in
$\displaystyle G(n,d/n)$, consisting of two vertex-disjoint paths
$\displaystyle P_{1}$ and $\displaystyle P_{2}$ each of size
$\displaystyle\Omega(n)$, where $\displaystyle\Omega(n)$ distinct vertices in
$\displaystyle P_{1}$ are adjacent to a vertex in $\displaystyle P_{2}$. We
will then repeat arguments similar to those in the proof of Theorem 2.1.4 (two
adjacent rows in an $\displaystyle L_{n,n}$ form a similar ladder-like
structure) to bound the number of ways we can assign values to an
$\displaystyle h$-Lipschitz function $\displaystyle f$ for vertices on path
$\displaystyle P_{1}$.

Theorem 3.2.5.
$\displaystyle\lim_{n\to\infty}\mathbf{Pr}\left[c\left(G\left(n,d/n\right)\right)\leq
2-2^{-18}\epsilon^{5}\right]=1$ for $\displaystyle d=1+\epsilon$, where
$\displaystyle\epsilon$ is sufficiently small.

Proof. Let $\displaystyle G$ be the graph with $\displaystyle n$ (for
sufficiently large $\displaystyle n$) vertices and no edges, and suppose we
randomly construct edges in $\displaystyle G$ in two stages; in Stage
$\displaystyle 1$, for each pair of vertices we construct the edge between
them with probability $\displaystyle(1+\epsilon)/n$, and in Stage
$\displaystyle 2$ we again attempt to construct those edges with probability
$\displaystyle\epsilon/n$ (the same edge may be constructed twice). It is
clear that the resulting graph is equivalent to a $\displaystyle
G\left(n,(1+2\epsilon)/n-\epsilon(1+\epsilon)/n^{2}\right)\subseteq
G\left(n,(1+2\epsilon)/n\right)$ random graph.

Let $\displaystyle E_{1}(G)$ and $\displaystyle E_{2}(G)$ denote the edges
constructed in Stages $\displaystyle 1$ and $\displaystyle 2$ respectively. By
Theorem 3.2 in [11], with high probability there is a path $\displaystyle P$
of length111All path lengths and vertex counts are integral; we eschew the use
of floor functions for the sake of readability $\displaystyle\epsilon^{2}n/5$
in $\displaystyle G$ consisting solely of edges in $\displaystyle E_{1}(G)$.
Split this path into two connected halves $\displaystyle P_{1}$ and
$\displaystyle P_{2}$, with $\displaystyle|P_{1}|,|P_{2}|=\epsilon^{2}n/10$.
For each vertex in $\displaystyle P_{1}$ there are
$\displaystyle\epsilon^{2}n/10$ potential edges between that vertex and a
vertex in $\displaystyle P_{2}$, and each of these edges has probability
$\displaystyle\epsilon/n$ of being present in $\displaystyle E_{2}(G)$.

Let $\displaystyle X$ be a random variable representing the number of vertices
in $\displaystyle P_{1}$ for which there is an edge in $\displaystyle
E_{2}(G)$ connecting that vertex to $\displaystyle P_{2}$. We have that

$\displaystyle
X\sim\text{Binomial}\left(\frac{\epsilon^{2}n}{10},1-\left(1-\frac{\epsilon}{n}\right)^{\epsilon^{2}n/10}\right)\dot{\sim}\
\text{Binomial}\left(\frac{\epsilon^{2}n}{10},\frac{\epsilon^{3}}{10}\right)$

thus with high probability $\displaystyle X\geq\epsilon^{5}n/200$.

Let $\displaystyle F$ be a maximal spanning forest of the edge-induced
subgraph $\displaystyle G[E_{1}]$ that contains $\displaystyle P$, and add the
edges in $\displaystyle E_{2}(G)$ (so that $\displaystyle F$ is no longer a
forest). We will upper bound
$\displaystyle\left\lvert\text{Lip}(F;h)\right\rvert$.

Construct $\displaystyle h$-Lipschitz functions $\displaystyle f$ on
$\displaystyle F$ as follows; select a vertex in each of the $\displaystyle k$
connected components of $\displaystyle F$ that $\displaystyle f$ will send to
$\displaystyle 0$. Then for each edge $\displaystyle\\{x,y\\}\in E(F)\cap
E_{1}(G)$ choose $\displaystyle f(x)-f(y)$ uniformly at random from
$\displaystyle\\{-h,-h+1,\dots,h\\}$. This process constructs
$\displaystyle(2h+1)^{n-k}$ functions $\displaystyle f$ with uniform
probability, including all valid $\displaystyle h$-Lipschitz functions. We
will upper bound the probability that for a given function $\displaystyle f$
constructed in this manner, the edges in $\displaystyle E_{2}(G)$ satisfy the
$\displaystyle h$-Lipschitz condition.

Denote by $\displaystyle v_{1},v_{2},\dots,v_{m}$ (in order) the vertices in
$\displaystyle P_{1}$ connected to vertices in $\displaystyle P_{2}$, where
with high probability $\displaystyle m\geq\epsilon^{5}n/200$. Using Corollary
2.1.2, for sufficiently large $\displaystyle h$ we can assume that
$\displaystyle f(w)=0$ for each vertex $\displaystyle w\in P_{2}$. Then we
must have that $\displaystyle|f(v_{i})|\leq h$ for all $\displaystyle i$. Now,
consider every third vertex $\displaystyle v_{1},v_{4},v_{7},\dots$ (there are
at least $\displaystyle\epsilon^{5}n/600$ such vertices). Then there are at
least two vertices between $\displaystyle v_{1}$ and $\displaystyle v_{4}$ in
path $\displaystyle P_{1}$, so let these vertices be $\displaystyle
u_{1},u_{2},\dots,u_{j}$ for some $\displaystyle j\geq 2$. We have that

$\displaystyle|(f(u_{1})-f(v_{1}))+(f(u_{2})-f(u_{1}))+\dots+(f(v_{3})-f(u_{j}))|=|f(v_{3})-f(v_{1})|\leq
2h$

But each of the terms in the left-most summation is uniformly distributed from
$\displaystyle\\{-h,-h+1,\dots,h\\}$. Clearly the maximum probability that the
above inequality is satisfied occurs when $\displaystyle j=2$, and we can
easily compute this probability as approaching $\displaystyle 23/24$ as
$\displaystyle h\to\infty$. Indeed, geometrically the possibility space is a
$\displaystyle 2h\times 2h\times 2h$ cube and the space corresponding to
failure corresponds to two tri-rectangular tetrahedrons, each with volume
$\displaystyle h^{3}/6$.

We can perform the same calculation with vertices $\displaystyle v_{4}$ and
$\displaystyle v_{7}$, then $\displaystyle v_{7}$ and $\displaystyle v_{10}$,
and so on. Thus, as $\displaystyle h\to\infty$ the probability that our
randomly chosen function $\displaystyle f$ satisfies the Lipschitz condition
is at most
$\displaystyle(23/24+o(1))^{\epsilon^{5}n/600}<\left(1-2^{-14}\epsilon^{5}\right)^{n-k}$.
Thus

$\displaystyle\left\lvert\text{Lip}(G;h)\right\rvert<\left\lvert\text{Lip}(F;h)\right\rvert\leq\left(1-2^{-14}\epsilon^{5}\right)^{n-k}\cdot(2h+1)^{n-k}$

Replacing $\displaystyle\epsilon$ with $\displaystyle\epsilon/2$ now implies
the desired result. $\displaystyle\blacksquare$

##  4 Acknowledgements

The authors would like to thank Mark Selke for pointing us towards Lemma
2.1.1, and Yonah Borns-Weil for his input on the spectral theory of operators.
Additionally, we would like to thank Franklyn Wang and Ryan Alweiss for
helpful discussions pertaining to our investigations in this paper.

## References

  * [1] Peled, Ron, Wojciech Samotij, and Amir Yehudayoff. ”Lipschitz functions on expanders are typically flat.” Combinatorics, Probability and Computing 22.4 (2013): 566-591.
  * [2] Peled, Ron. ”High-dimensional Lipschitz functions are typically flat.” arXiv preprint arXiv:1005.4636 (2010).
  * [3] Peled, Ron, Wojciech Samotij, and Amir Yehudayoff. ”Grounded Lipschitz functions on trees are typically flat.” (2013): 1-9.
  * [4] Benjamini, Itai, Olle Häggström, and Elchanan Mossel. ”On Random Graph Homomorphisms into $\displaystyle\mathbb{Z}$.” Journal of Combinatorial Theory, Series B, Volume 78, Issue 1,ISSN 0095-8956 (2000): 86-114.
  * [5] Galvin, David. ”On homomorphisms from the Hamming cube to $\displaystyle\mathbb{Z}$”. Israel J. Math. 138 (2003): 189–213.
  * [6] Braun, Benjamin, and Mike Develin. ”Ehrhart polynomial roots and Stanley’s non-negativity theorem.” arXiv preprint math/0610399 (2006).
  * [7] Böröczky, Károly, and Pavlos Kalantzopoulos. ”Log-Brunn-Minkowski inequality under symmetry.” Transactions of the American Mathematical Society 375.08 (2022): 5987-6013.
  * [8] Guo, Jingwei. ”Two bounds for the lattice point problem.” The University of Wisconsin - Madison Dissertations Publishing 3488582 (2011).
  * [9] Lovász, László, Paul Erdős. “Problems and Results on 3-chromatic Hypergraphs and Some Related Questions.” (1975).
  * [10] Frieze, Alan, and Michał Karoński. ”Introduction to Random Graphs.” Cambridge University Press (2015).
  * [11] Krivelevich, Michael. ”Long paths and Hamiltonicity in random graphs.” Random graphs, geometry and asymptotic structure 84.1 (2016).