Maximum spread of graphs and bipartite graphs

Abstract

Given any graph $G$, the spread of $G$ is the maximum difference between any two eigenvalues of the adjacency matrix of $G$. In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers $n$, the $n$-vertex graph $G$ that maximizes spread is the join of a clique and an independent set, with $\lfloor 2n/3 \rfloor$ and $\lceil n/3 \rceil$ vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all $n$ sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over $\mathscr{L}^2[0,1]$. The second conjecture claims that for any fixed $m \leq n^2/4$, if $G$ maximizes spread over all $n$-vertex graphs with $m$ edges, then $G$ is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms.

1. Introduction

The spread $s(M)$ of an arbitrary $n\times n$ complex matrix $M$ is the diameter of its spectrum; that is,

$$\begin{equation*} s(M)\coloneq \max _{i,j} |\lambda _i-\lambda _j|, \end{equation*}$$

where the maximum is taken over all pairs of eigenvalues of $M$. This quantity has been well studied in general (see 11162233 for details and additional references). Most notably, Johnson, Kumar, and Wolkowitz 16, Theorem 2.1 obtained the lower bound

$$\begin{equation*} s(M) \ge \textstyle { \big | \sum _{i \ne j} m_{i,j} \big |/(n-1)} \end{equation*}$$

for normal matrices $M = (m_{i,j})$, and Mirsky 22, Theorem 2 determined the upper bound

$$\begin{equation*} s(M) \le \sqrt {\textstyle {2 \sum _{i,j} |m_{i,j}|^2 - (2/n)\big | \sum _{i} m_{i,i} \big |^2}} \end{equation*}$$

for any $n \times n$ matrix $M$, which is tight for any normal matrix with $n-2$ of its eigenvalues all equal and equal to the arithmetic mean of the other two.

The spread of a matrix has also received interest in some particular cases. Consider a simple undirected graph $G = (V(G),E(G))$ of order $n$. The adjacency matrix $A$ of $G$ is the $n \times n$ matrix whose rows and columns are indexed by the vertices of $G$, with entries satisfying $A_{u,v} = 1$ if $\{u,v\} \in E(G)$ and $A_{u,v} = 0$ otherwise. This matrix is real and symmetric, and so its eigenvalues are real and can be ordered $\lambda _1(G) \geq \lambda _2(G)\geq \cdots \geq \lambda _n(G)$. When considering the spread of the adjacency matrix $A$ of some graph $G$, the spread is simply the distance between $\lambda _1(G)$ and $\lambda _n(G)$, denoted by

$$\begin{equation*} s(G) \coloneq \lambda _1(G) - \lambda _n(G). \end{equation*}$$

In this instance, $s(G)$ is referred to as the spread of the graph $G$.

In 13, Gregory, Hershkowitz, and Kirkland investigated a number of properties regarding the spread of a graph, determined upper and lower bounds on $s(G)$, and made two key conjectures. Let us denote the maximum spread over all $n$-vertex graphs by $s(n)$, the maximum spread over all $n$-vertex graphs of size $m$ by $s(n,m)$, and the maximum spread over all $n$-vertex bipartite graphs of size $m$ by $s_b(n,m)$. The join of two vertex-disjoint graphs $G \vee H$ is the graph containing both $G$ and $H$, and all edges between the two. The complement of a graph $\overline{G}$ is the graph on $V(G)$ containing only the edges not in $E(G)$. Let $K_k$ be the clique of order $k$ and $G(n,k) \coloneq K_k \vee \overline{K_{n-k}}$ be the join of the clique $K_k$ (the graph with all possible edges included) and the independent set $\overline{K_{n-k}}$ (the graph with no edges). We say a graph is spread extremal if it has spread $s(n)$. The conjectures addressed in this article are as follows.

Conjecture 1 (13, Conjecture 1.3).

For any positive integer $n$, the graph of order $n$ with maximum spread is $G(n,\lfloor 2n/3 \rfloor )$; that is, $s(n) = \lfloor (4/3)(n^2-n+1)\rfloor ^{1/2}$ and this value is attained only by $G(n,\lfloor 2n/3 \rfloor )$.

Conjecture 2 (13, Conjecture 1.4).

If $G$ is a graph with $n$ vertices and $m \leq \lfloor n^2/4\rfloor$ edges attaining the maximum spread $s(n,m)$, then $G$ must be bipartite. That is, $s_b(n,m) = s(n,m)$ for all $m \le \lfloor n^2/4\rfloor$.

Conjecture 1 is referred to as the Spread Conjecture, and Conjecture 2 is referred to as the Bipartite Spread Conjecture. Much of what is known about Conjecture 1 is contained in 13, but the reader may also see 29 for a description of the problem and references to other work. In this paper, we resolve both conjectures. We prove the Spread Conjecture for all $n$ sufficiently large, prove an asymptotic version of the Bipartite Spread Conjecture, and provide an infinite family of counterexamples to illustrate that our asymptotic version of the Bipartite Spread Conjecture is tight up to lower-order error terms. These results are given by Theorems 1.1, 1.2, and 1.3.

Theorem 1.1.

There exists a constant $N$ so that the following holds: Suppose $G$ is a graph on $n\geq N$ vertices with maximum spread. Then $G$ is the join of a clique on $\lfloor 2n/3\rfloor$ vertices and an independent set on $\lceil n/3\rceil$ vertices.

Theorem 1.2.

For all $n,m \in \mathbb{N}$ satisfying $m \le \lfloor n^2/4\rfloor$,

$$\begin{equation*} s(n,m) - s_b(n,m) \le \frac{1+16 m^{-3/4}}{m^{3/4}} s(n,m). \end{equation*}$$

Theorem 1.3.

For any $\varepsilon >0$, there exists some $n_\varepsilon$ such that

$$\begin{equation*} s(n,m) - s_b(n,m) \ge \frac{1-\varepsilon }{m^{3/4}} s(n,m) \end{equation*}$$

for all $n\ge n_\varepsilon$ and some $m \le \lfloor n^2/4\rfloor$ depending on $n$.

The proof of Theorem 1.1 constitutes the main subject of this work. The general technique consists of showing that a spread-extremal graph has certain desirable properties, solving an analogous problem for graph limits, and then using this result to say something about the Spread Conjecture for sufficiently large $n$. For the interested reader, we state the analogous graph limit result in the language of functional analysis (see 18 for an introduction to graph limits).

Theorem 1.4.

Let $W:[0,1]^2\to [0,1]$ be a Lebesgue-measurable function such that $W(x,y) = W(y,x)$ for a.e. $(x,y)\in [0,1]^2$, and let $A = A_W$ be the kernel operator on $\mathscr{L}^2[0,1]$ associated with $W$. For all unit functions $f,g\in \mathscr{L}^2[0,1]$,

$$\begin{align*} \langle f, Af\rangle - \langle g, Ag\rangle &\leq \dfrac{2}{\sqrt {3}}. \end{align*}$$

Moreover, equality holds if and only if there exists a measure-preserving transformation $\sigma$ on $[0,1]$ such that for a.e. $(x,y)\in [0,1]^2$,

$$\begin{align*} W(\sigma (x),\sigma (y)) &= \left\{\begin{array}{rl} 0, & \text{if } (x,y)\in [2/3, 1]\times [2/3, 1]\\1, &\text{otherwise} \end{array}\right. . \end{align*}$$

The bound of $2/\sqrt {3}$ in Theorem 1.4 is the scaled limit of the spread $s\big (G(n,\lfloor 2n/3 \rfloor ) \big ) = \lfloor (4/3)(n^2-n+1)\rfloor ^{1/2}$, and the function $W$ (up to a set of measure zero) corresponds to a scaled limit of $G(n,\lfloor 2n/3 \rfloor )$. In addition to being a key ingredient in the proof of Theorem 1.1, Theorem 1.4 also immediately implies a result for arbitrary symmetric nonnegative matrices.

Corollary 1.5.

Let $A =(a_{i,j})$ be an $n \times n$ symmetric nonnegative matrix. Then

$$\begin{equation*} \lambda _1(A) - \lambda _n(A) \le \frac{2n}{\sqrt {3}} \, \max _{i,j} a_{i,j}, \end{equation*}$$

and

$$\begin{equation*} \max _{\substack{\|u\|=\|v\|=1 \\ \langle u, v\rangle = 0}} |\langle u, Av\rangle | \le \frac{n}{\sqrt {3}} \, \max _{i,j} a_{i,j}. \end{equation*}$$

Corollary 1.5, paired with the lower bound provided by graph $G(n,\lfloor 2n/3 \rfloor )$, implies that $(2n-1)/\sqrt {3} < s(n) \le 2n/\sqrt {3}$ for all $n >1$, i.e. the spread conjecture is true for all $n$ up to an additive $1/\sqrt {3}$ factor. Furthermore, Corollary 1.5 implies that the maximum spread of a symmetric $0-1$ matrix is exactly $2n/\sqrt {3}$ for $n \equiv 0 \mod 3$ and is within $1/(2\sqrt {3}n)$ of $2n/\sqrt {3}$ for $n \not \equiv 0 \mod 3$. The second part of Corollary 1.5 gives a bound on the magnitude of off-diagonal entries of a nonnegative matrix under a unitary change of basis, and is also tight for $n \equiv 0 \mod 3$ (and tight up to $O(1/n)$ for $n \not \equiv 0 \mod 3$).

The proof of Theorem 1.1 can be found in Sections 2 through 6, with certain technical details reserved for Appendices A and B. We provide an in-depth overview of the proof of Theorem 1.1 in Subsection 1.1. By comparison, the proofs of Theorems 1.2 and 1.3 are surprisingly short, making use of the theory of equitable decompositions and a well-chosen class of counterexamples. Their proof can be found in Section 7. Finally, in Section 8, we discuss further questions and possible future avenues of research.

1.1. High-level outline of spread proof

Here, we provide a concise, high-level description of our asymptotic proof of the Spread Conjecture. The proof itself is quite involved, making use of interval arithmetic and a number of fairly complicated symbolic calculations, but conceptually, it is quite intuitive. It consists of four main steps.

Step 1 (Graph-theoretic results).

In Section 2, we observe a number of important structural properties of any graph that maximizes spread for a given order $n$. In particular, we show that

•

any graph that maximizes spread must be the join of two threshold graphs (Lemma 2.1),

•

both graphs in this join have order linear in $n$ (Lemma 2.2),

•

any unit eigenvectors $\mathbf{x}$ and $\mathbf{z}$ corresponding to $\lambda _1(A)$ and $\lambda _n(A)$ have infinity norms of order $n^{-1/2}$ (Lemma 2.3),

•

the quantities $\lambda _1 \mathbf{x}_u^2 - \lambda _n \mathbf{z}_u^2$, $u \in V$, are all nearly equal, up to a term of order $n^{-1}$ (Lemma 2.4).

This last structural property serves as the backbone of our proof. In addition, we note that, by a tensor argument, an asymptotic upper bound for $s(n)$ implies a bound for all $n$.

Step 2 (Graphons and a finite-dimensional eigenvalue problem).

In Sections 3 and 4, we make use of graphons to understand how spread-extremal graphs behave as $n$ tends to infinity. Section 3 consists of a basic introduction to graphons, and a translation of the graph results of Step 1 to the graphon setting. In particular, we prove the graphon analogue of the spread-extremal graph properties that

•

vertices $u$ and $v$ are adjacent if and only if $\mathbf{x}_u \mathbf{x}_v - \mathbf{z}_u \mathbf{z}_v >0$ (Lemma 3.6),

•

the quantities $\lambda _1 \mathbf{x}_u^2 - \lambda _n \mathbf{z}_u^2$, $u \in V$, are all nearly equal (Lemma 3.7).

Next, in Section 4, we show that the spread-extremal graphon for our problem takes the form of a particular stepgraphon with a finite number of blocks (Theorem 4.1). Through an averaging argument, we note that the spread-extremal graphon takes the form of a stepgraphon with a fixed structure of symmetric $7 \times 7$ blocks, illustrated below (black equals one, white equals zero).

The lengths $\alpha = (\alpha _1,\dots ,\alpha _7)$, $\alpha ^T {\mathbf{1}} = 1$, of each row and column in the spread-extremal stepgraphon are unknown. For any choice of lengths $\alpha$, we can associate a $7\times 7$ matrix whose spread is identical to that of the associated stepgraphon pictured above. Let $B$ be the $7\times 7$ matrix with $B_{i,j}$ equal to the value of the above stepgraphon on block $i,j$, and $D = \text{diag}(\alpha _1,\dots ,\alpha _7)$ be a diagonal matrix with $\alpha$ on the diagonal. Then the matrix $D^{1/2} B D^{1/2}$ has spread equal to the spread of the associated stepgraphon.

Step 3 (Computer-assisted proof of a finite-dimensional eigenvalue problem).

In Section 5, we show that the optimizing choice of $\alpha$ is, without loss of generality, given by $\alpha _1 = 2/3$, $\alpha _7 =1/3$, and all other $\alpha _i =0$ (Theorem 5.1). This is exactly the limit of the conjectured spread-extremal graph as $n$ tends to infinity. The proof of this fact is extremely technical, and relies on a computer-assisted proof using both interval arithmetic and symbolic computations. This is the only portion of the proof (of Theorem 1.1) that requires the use of interval arithmetic. Though not a proof, in Figure 1 we provide intuitive visual justification of this result. In this figure, we provide contour plots resulting from numerical computations of the spread of the above matrix for various values of $\alpha$. The numerical results suggest that the $2 \times 2$ block stepgraphon with lengths $2/3$ and $1/3$ is indeed optimal. See Figure 1 and the associated caption for details.

The actual proof of this fact consists of the following steps:

•

we reduce the possible choices of nonzero $\alpha _i$ from $2^7$ to $17$ different cases (Lemma A.2),

•

using eigenvalue equations, the graphon versions of $\lambda _1 \mathbf{x}_u^2 - \lambda _n \mathbf{z}_u^2$ all nearly equal, and interval arithmetic, we prove that, of the $17$ cases, only the cases

–

$\alpha _1,\alpha _7 \ne 0$

–

$\alpha _4,\alpha _5,\alpha _7 \ne 0$

can produce a spread-extremal stepgraphon (Lemma 5.2),

•

prove that the $3 \times 3$ case cannot be spread extremal, using basic results from the theory of cubic polynomials and computer-assisted symbolic calculations (Lemma 5.4).

This proves that the spread-extremal graphon is a $2 \times 2$ stepgraphon that, without loss of generality, takes value zero on the block $[2/3,1]^2$ and one elsewhere (Theorem 1.4/Theorem 5.1).

Step 4 (From graphons to an asymptotic proof of the spread conjecture).

Finally, in Section 6, we convert our result for the spread-extremal graphon to a statement for graphs. This process consists of two main parts:

•

using our graphon theorem (Theorem 5.1), we show that any spread-extremal graph takes the form $(K_{n_1}\dot{\cup } \overline{K_{n_2}})\vee \overline{K_{n_3}}$ for $n_1 = (2/3+o(1))n$, $n_2 = o(n)$, and $n_3 = (1/3+o(1))n$ (Lemma 6.2), i.e. any spread-extremal graph is equal up to a set of $o(n)$ vertices to the conjectured optimal graph $K_{\lfloor 2n/3\rfloor } \vee \overline{K_{\lceil n/3 \rceil }}$,

•

we show that, for $n$ sufficiently large, the spread of $(K_{n_1}\dot{\cup } \overline{K_{n_2}})\vee \overline{K_{n_3}}$, $n_1 + n_2 + n_3 = n$, is maximized when $n_2 = 0$ (Lemma 6.3).

Together, these two results complete our proof of the spread conjecture for sufficiently large $n$ (Theorem 1.1).

2. Properties of spread-extremal graphs

In this section, we review what has already been shown about spread-extremal graphs ($n$-vertex graphs with spread $s(n)$) in 13. We then prove a number of properties of spread-extremal graphs and properties of the eigenvectors associated with the maximum and minimum eigenvalues of a spread-extremal graph.

Let $G$ be a graph, and let $A$ be the adjacency matrix of $G$, with eigenvalues $\lambda _1 \geq \cdots \geq \lambda _n$. For unit vectors $\mathbf{x}$, $\mathbf{z} \in \mathbb{R}^n$, we have

$$\begin{equation*} \lambda _1 \geq \mathbf{x}^T A \mathbf{x} \quad \text{and} \quad \lambda _n \leq \mathbf{z}^TA\mathbf{z}. \end{equation*}$$

Hence (as observed in 13), the spread of a graph can be expressed as

$$\begin{equation} s(G) = \max _{\mathbf{x}, \mathbf{z}}\sum _{u\sim v} (\mathbf{x}_u\mathbf{x}_v-\mathbf{z}_u\mathbf{z}_v),{\tag{1}} \end{equation}$$

where the maximum is taken over all unit vectors $\mathbf{x}, \mathbf{z}$. This maximum is attained only for $\mathbf{x}, \mathbf{z}$ orthonormal eigenvectors corresponding to the eigenvalues $\lambda _1, \lambda _n$, respectively. We refer to such a pair of vectors $\mathbf{x}, \mathbf{z}$ as extremal eigenvectors of $G$. For any two vectors $\mathbf{x}$, $\mathbf{z}$ in $\mathbb{R}^n$, let $G(\mathbf{x}, \mathbf{z})$ denote the graph for which distinct vertices $u, v$ are adjacent if and only if $\mathbf{x}_u\mathbf{x}_v-\mathbf{z}_u\mathbf{z}_v\geq 0$. As noted in 13, Proposition 3.3, any spread-extremal graph must be connected (as the join $G_1 \vee G_2$ of nontrivial vertex-disjoint graphs is strictly greater than their union $G_1 \cup G_2$). Then from the above, there is some graph $G(\mathbf{x}, \mathbf{z})$ that is a spread-extremal graph, with $\mathbf{x}$, $\mathbf{z}$ orthonormal and $\mathbf{x}$ positive 13, Lemma 3.5. By the Perron-Frobenius Theorem, $\lambda _1$ is a simple eigenvalue. However, $\lambda _n$ may be repeated, and so $\mathbf{z}$ may not be unique up to normalization.

In addition, we enhance 13, Lemmas 3.4 and 3.5 using some helpful definitions and the language of threshold graphs. Whenever $G = G(\mathbf{x}, \mathbf{z})$ is understood, let $P = P(\mathbf{x}, \mathbf{z}) \coloneq \{u \in V(G) : \mathbf{z}_u \geq 0\}$ and $N = N(\mathbf{x}, \mathbf{z}) \coloneq V(G)\setminus P$. In addition, let $G[S]$, $S \subset V$, be the subgraph induced by $S$, i.e., the graph with vertex set $S$ and containing all edges of $G$ between vertices in $S$.

For our purposes, we say that $G$ is a threshold graph if and only if there exists a function $\varphi :V(G)\to (-\infty ,\infty ]$ such that for all distinct $u,v\in V(G)$, $uv\in E(G)$ if and only if $\varphi (u)+\varphi (v) \geq 0$.⁠¹ Here, $\varphi$ is a threshold function for $G$ (with $0$ as its threshold). The following detailed lemma shows that any spread-extremal graph is the join of two threshold graphs with threshold functions that can be made explicit.

¹

Here, we take the usual convention that for all $x\in (-\infty , \infty ]$, $\infty + x = x + \infty = \infty$.

✖

Lemma 2.1.

Let $n> 2$, and suppose $G$ is an $n$-vertex graph such that $s(G) = s(n)$. Denote by $\mathbf{x}$ and $\mathbf{z}$ extremal unit eigenvectors for $G$. Then

(i)

For any two vertices $u,v$ of $G$, $u$ and $v$ are adjacent whenever $\mathbf{x}_u\mathbf{x}_v-\mathbf{z}_u\mathbf{z}_v>0$ and $u$ and $v$ are nonadjacent whenever $\mathbf{x}_u\mathbf{x}_v-\mathbf{z}_u\mathbf{z}_v<0$.

(ii)

For any distinct $u,v\in V(G)$, $\mathbf{x}_u\mathbf{x}_v-\mathbf{z}_u\mathbf{z}_v\not =0$.

(iii)

Let $P \coloneq P(\mathbf{x}, \mathbf{z})$, $N \coloneq N(\mathbf{x}, \mathbf{z})$ and let $G_1 \coloneq G[P]$ and $G_2 \coloneq G[N]$. Then $G = G(\mathbf{x}, \mathbf{z}) = G_1\vee G_2$.

(iv)

For each $i\in \{1,2\}$, $G_i$ is a threshold graph with threshold function defined on all $u\in V(G_i)$ by$$\begin{align*} \varphi (u) \coloneq \log \left| \dfrac{\mathbf{x}_u}{\mathbf{z}_u} \right| . \end{align*}$$

Proof.

Suppose $G$ is an $n$-vertex graph such that $s(G) = s(n)$, and write $A = (a_{uv})_{u,v\in V(G)}$ for its adjacency matrix. Item i is equivalent to Lemma 3.4 from 13. For completeness, we include a proof. By Equation 1 we have that

$$\begin{align*} s(G) &= \max _{ \mathbf{x},\mathbf{z}} \mathbf{x}^T A\mathbf{x}-\mathbf{z}^TA\mathbf{z}= \sum _{u,v\in V(G)} a_{uv}\cdot \left(\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v\right), \end{align*}$$

where the maximum is taken over all unit vectors of length $n$. If $\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v > 0$ and $a_{uv} = 0$, then $s(G+uv) > s(G)$, a contradiction. And if $\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v < 0$ and $a_{uv} = 1$, then $s(G-uv) > s(G)$, a contradiction. So Item i holds.

For a proof of Item ii, suppose $\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v = 0$ and denote by $G'$ the graph formed by adding or deleting the edge $uv$ from $G$. With $A'$ denoting the adjacency matrix of $G'$,

$$\begin{align*} s(G') \geq \mathbf{x}^T A'\mathbf{x}-\mathbf{z}^TA'\mathbf{z}= \mathbf{x}^T A\mathbf{x}-\mathbf{z}^TA\mathbf{z}= s(G) &\geq s(G'), \end{align*}$$

so each inequality is an equality. It follows that $\mathbf{x}, \mathbf{z}$ are eigenvectors for $A'$. Furthermore, without loss of generality, we may assume that $uv\in E(G)$. In particular, there exists some $\lambda '$ such that

$$\begin{align*} A\mathbf{x}&= \lambda \mathbf{x},\\ (A -{\mathbf{e}}_u{\mathbf{e}}_v^T -{\mathbf{e}}_v{\mathbf{e}}_u^T )\mathbf{x}&= \lambda '\mathbf{x}. \end{align*}$$

So $( {\mathbf{e}}_u{\mathbf{e}}_v^T +{\mathbf{e}}_v{\mathbf{e}}_u^T )\mathbf{x}= (\lambda - \lambda ')\mathbf{x}$. Let $w\in V(G)\setminus \{u,v\}$. By the above equation, $(\lambda -\lambda ')\mathbf{x}_w = 0$ and either $\lambda ' = \lambda$ or $\mathbf{x}_w = 0$. To find a contradiction, it is sufficient to note that $G$ is a connected graph with Perron-Frobenius eigenvector $\mathbf{x}$. Indeed, let $P \coloneq \{w\in V(G) : \mathbf{z}_w \geq 0\}$ and let $N \coloneq V(G)\setminus P$. Then for any $w\in P$ and any $w'\in N$, $\mathbf{x}_w\mathbf{x}_{w'} - \mathbf{z}_w\mathbf{z}_{w'} > 0$, and by Item i, $ww'\in E(G)$. So $G$ is connected. This completes the proof of Item ii.

Now, we prove Item iii. To see that $G = G(\mathbf{x}, \mathbf{z})$, note by Items i and ii, for all distinct $u,v\in V(G)$, $\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v > 0$ if and only if $uv\in E(G)$, and otherwise, $\mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v < 0$ and $uv\notin E(G)$. To see that $G = G_1\vee G_2$, note that for any $u\in P$ and any $v\in N$, $0 \neq \mathbf{x}_u\mathbf{x}_v - \mathbf{z}_u\mathbf{z}_v \geq \mathbf{z}_u\cdot (-\mathbf{z}_v)\geq 0$.

Finally, we prove Item iv. Suppose $u,v$ are distinct vertices such that either $u,v\in P$ or $u,v\in N$. Allowing the possibility that $0\in \{\mathbf{z}_u, \mathbf{z}_v\}$, the following equivalence holds:

$$\begin{align*} \varphi (u) + \varphi (v) &\geq 0 & \text{ if and only if }\\ \log \left| \dfrac{\mathbf{x}_u\mathbf{x}_v}{\mathbf{z}_u\mathbf{z}_v} \right| &\geq 1 & \text{ if and only if }\\ \mathbf{x}_u\mathbf{x}_v - |\mathbf{z}_u\mathbf{z}_v| &\geq 0. \end{align*}$$

Since $\mathbf{z}_u,\mathbf{z}_v$ have the same sign, Item iv holds. This completes the proof.

■

From 21, we recall the following useful characterization in terms of “nesting” neighborhoods: $G$ is a threshold graph if and only there exists a numbering $v_1,\cdots , v_n$ of $V(G)$ such that for all $1\leq i<j\leq n$, if $v_k\in V(G)\setminus \{v_i,v_j\}$, $v_jv_k\in E(G)$ implies that $v_iv_k\in E(G)$. Given this ordering, if $k$ is the largest natural number such that $v_kv_{k+1}\in E(G)$, then the set $\{v_1,\cdots , v_k\}$ induces a clique and the set $\{v_{k+1},\cdots , v_n\}$ induces an independent set.

Lemma 2.2 shows that both $P$ and $N$ have linear size.

Lemma 2.2.

If $G$ is a spread-extremal graph, then both $P$ and $N$ have size $\ge n/100$.

Proof.

We will show that $P$ and $N$ both have size at least $\frac{n}{100}$. First, since $G$ is spread-extremal, it has spread more than $1.1n$ and hence has smallest eigenvalue $\lambda _n < -\frac{n}{10}$. Without loss of generality, for the remainder of this proof we will assume that $|P| \leq |N|$, and that $v$ is a vertex satisfying $| \mathbf{z}_v| = \|\mathbf{z}\|_\infty$. By way of contradiction, assume that $|P|< \frac{n}{100}$.

If $v\in N$, then we have

$$\begin{equation*} -\lambda _n = \lambda _n \frac{\mathbf{z}_v}{|\mathbf{z}_v|} = \sum _{u\sim v} \frac{\mathbf{z}_u}{|\mathbf{z}_v|} \leq \sum _{u\in P} \frac{\mathbf{z}_u}{|\mathbf{z}_v|} \leq |P| < \frac{n}{100}, \end{equation*}$$

contradicting that $\lambda _n < \frac{-n}{10}$. Therefore, assume that $v\in P$. Then

$$\begin{align*} \lambda _n^2 &= \lambda _n^2 \frac{\mathbf{z}_v}{|\mathbf{z}_v|} = \sum _{u\sim v} \sum _{w\sim u}\frac{\mathbf{z}_w}{|\mathbf{z}_v|} \leq \sum _{u\sim v} \sum _{\substack{w\sim u\\w\in P}} \frac{\mathbf{z}_w}{|\mathbf{z}_v|} \\ &\leq |P| |N| + 2|E(G[P])| \leq |P| |N| + |P|^2 \leq \frac{99n^2}{100^2} + \frac{n^2}{100^2}. \end{align*}$$

This gives $|\lambda _n| \leq \frac{n}{10}$, a contradiction.

■

Lemma 2.3.

If $\mathbf{x}$ and $\mathbf{z}$ are unit eigenvectors for $\lambda _1$ and $\lambda _n$, then $\left\lVert \mathbf{x}\right\rVert _\infty = O(n^{-1/2})$ and $\left\lVert \mathbf{z}\right\rVert _\infty = O(n^{-1/2})$.

Proof.

During this proof we will assume that $\hat{u}$ and $\hat{v}$ are vertices satisfying $\left\lVert \mathbf{x}\right\rVert _\infty = \mathbf{x}_{\hat{u}}$ and $\left\lVert \mathbf{z}\right\rVert _\infty = |\mathbf{z}_{\hat{v}}|$ and without loss of generality that $\hat{v} \in N$. We will use the weak estimates that $\lambda _1 > \frac{n}{2}$ and $\lambda _n < -\frac{n}{10}$. Define sets

$$\begin{align*} A &= \left\{ w: \mathbf{x}_w > \frac{\mathbf{x}_{\hat{u}}}{4} \right\},\\ B &= \left\{ w: \mathbf{z}_w >- \frac{\mathbf{z}_{\hat{v}}}{20} \right\}. \end{align*}$$

We have the estimates

$$\begin{equation*} 1 = \mathbf{x}^T \mathbf{x} \geq \sum _{w\in A} \mathbf{x}_w^2 \geq |A| \frac{\left\lVert \mathbf{x}\right\rVert ^2_\infty }{16} \qquad \text{and} \qquad 1 = \mathbf{z}^T \mathbf{z} \geq \sum _{w\in B} \mathbf{z}_w^2 \geq |B| \frac{\left\lVert \mathbf{z}\right\rVert ^2_\infty }{400}, \end{equation*}$$

and so $\|\mathbf{x}\|_\infty \le 4/\sqrt {|A|}$ and $\|\mathbf{z}\|_\infty \le 20/\sqrt {|B|}$. To complete the proof, it suffices to show that $A$ and $B$ both have size $\Omega (n)$.

We now give a lower bound on the sizes of $A$ and $B$ using the eigenvalue-eigenvector equation and the weak bounds on $\lambda _1$ and $\lambda _n$.

$$\begin{equation*} \frac{n}{2} \left\lVert \mathbf{x}\right\rVert _\infty = \frac{n}{2} \mathbf{x}_{\hat{u}} < \lambda _1 \mathbf{x}_{\hat{u}} = \sum _{w\sim \hat{u}} \mathbf{x}_w \leq \left\lVert \mathbf{x}\right\rVert _\infty \left(|A| + \frac{1}{4}(n-|A|) \right), \end{equation*}$$

giving that $|A| > \frac{n}{3}$. Similarly,

$$\begin{equation*} \frac{n}{10} \left\lVert \mathbf{z}\right\rVert _\infty = - \frac{n}{10} \mathbf{z}_{\hat{v}} < \lambda _n \mathbf{z}_{\hat{v}} = \sum _{w\sim \hat{v}} \mathbf{z}_w \leq \left\lVert \mathbf{z}\right\rVert _\infty \left( |B| + \frac{1}{20}(n-|B|)\right), \end{equation*}$$

and so $|B| > \frac{n}{19}$. This implies that $\|\mathbf{x}\|_\infty < \frac{4}{\sqrt {3}} n^{-1/2}$ and $\|\mathbf{z}\|_\infty \le \frac{20}{\sqrt {19}} n^{-1/2}$.

■

Lemma 2.4.

Assume that $\mathbf{x}$ and $\mathbf{z}$ are unit vectors. Then there exists a constant $C$ such that for any pair of vertices $u$ and $v$, we have

$$\begin{equation*} |(\lambda _1 \mathbf{x}_u^2 - \lambda _n\mathbf{z}_u^2) - (\lambda _1 \mathbf{z}_v^2 - \lambda _n \mathbf{z}_v^2)| < \frac{C}{n}. \end{equation*}$$

Proof.

Let $u$ and $v$ be vertices, and create a graph $\tilde{G}$ by deleting $u$ and cloning $v$. That is, $V(\tilde{G}) = \{v'\} \cup V(G) \setminus \{u\}$ and

$$\begin{equation*} E(\tilde{G}) = E(G\setminus \{u\}) \cup \{v'w:vw\in E(G)\}. \end{equation*}$$

Note that $v \not \sim v'$. Let $\tilde{A}$ be the adjacency matrix of $\tilde{G}$. Define two vectors $\mathbf{\tilde{x}}$ and $\mathbf{\tilde{z}}$ by

$$\begin{equation*} \mathbf{\tilde{x}}_w = \begin{cases} \mathbf{x}_w & w\not =v',\\ \mathbf{x}_v & w=v', \end{cases} \end{equation*}$$

and

$$\begin{equation*} \mathbf{\tilde{z}}_w = \begin{cases} \mathbf{z}_w & w\not =v',\\ \mathbf{z}_v & w=v. \end{cases} \end{equation*}$$

Then $\mathbf{\tilde{x}}^T \mathbf{\tilde{x}} = 1 - \mathbf{x}_u^2 + \mathbf{x}_v^2$ and $\mathbf{\tilde{z}}^T \mathbf{\tilde{z}} = 1 - \mathbf{z}_u^2 + \mathbf{z}_v^2$. Similarly,

$$\begin{align*} \mathbf{\tilde{x}}^T\tilde{A}\mathbf{\tilde{x}} &= \lambda _1 - 2\mathbf{x}_u \sum _{uw\in E(G)} \mathbf{x}_w + 2\mathbf{x}_{v'} \sum _{vw \in E(G)} \mathbf{x}_w - 2A_{uv}\mathbf{x}_v\mathbf{x}_u \\ &= \lambda _1 - 2\lambda _1\mathbf{x}_u^2 + 2\lambda _1 \mathbf{x}_v^2 - 2A_{uv} \mathbf{x}_u \mathbf{x}_v, \end{align*}$$

and

$$\begin{align*} \mathbf{\tilde{z}}^T\tilde{A}\mathbf{\tilde{z}} &= \lambda _n - 2\mathbf{z}_u \sum _{uw\in E(G)} \mathbf{z}_w + 2\mathbf{z}_{v'} \sum _{vw \in E(G)} \mathbf{z}_w - 2A_{uv}\mathbf{z}_v\mathbf{z}_u \\ &= \lambda _n - 2\lambda _n\mathbf{z}_u^2 + 2\lambda _n \mathbf{z}_v^2 - 2A_{uv} \mathbf{z}_u \mathbf{z}_v. \end{align*}$$

By Equation 1,

$$\begin{align*} 0 & \geq \left(\frac{\mathbf{\tilde{x}}^T\tilde{A}\mathbf{\tilde{x}}}{\mathbf{\tilde{x}}^T \mathbf{\tilde{x}}} - \frac{\mathbf{\tilde{z}}^T\tilde{A}\mathbf{\tilde{z}}}{\mathbf{\tilde{z}}^T \mathbf{\tilde{z}}} \right) - (\lambda _1 - \lambda _n) \\ & = \left(\frac{\lambda _1 - 2\lambda _1 \mathbf{x}_u^2 + 2\lambda _1 \mathbf{x}_v^2 - 2A_{uv}\mathbf{x}_u\mathbf{x}_v}{1 - \mathbf{x}_u^2 + \mathbf{x}_v^2} - \frac{\lambda _n - 2\lambda _n \mathbf{z}_u^2 + 2\lambda _n \mathbf{z}_v^2 - 2A_{uv} \mathbf{z}_u\mathbf{z}_v}{1-\mathbf{z}_u^2 + \mathbf{z}_v^2}\right) - (\lambda _1 - \lambda _n) \\ & = \frac{-\lambda _1 \mathbf{x}_u^2 + \lambda _1\mathbf{x}_v^2 - 2A_{ij}\mathbf{x}_u\mathbf{x}_v}{1 - \mathbf{x}_u^2 + \mathbf{x}_v^2} - \frac{-\lambda _n \mathbf{z}_u^2 + \lambda _n\mathbf{z}_v^2 - 2A_{ij}\mathbf{z}_u \mathbf{z}_v}{1 - \mathbf{z}_u^2 + \mathbf{z}_v^2}. \end{align*}$$

Rearranging terms, we obtain

$$\begin{equation*} (\lambda _1 \mathbf{x}_u^2 - \lambda _1 \mathbf{x}_v^2) - (\lambda _n \mathbf{z}_u^2 - \lambda _n \mathbf{z}_v^2) \ge \frac{\lambda _n(\mathbf{z}_u^2 - \mathbf{z}_v^2)^2 + 2A_{u,v}\mathbf{z}_u \mathbf{z}_v}{1 - \mathbf{z}_u^2 + \mathbf{z}_v^2}- \frac{\lambda _1(\mathbf{x}_u^2 - \mathbf{x}_v^2)^2 + 2A_{u,v}\mathbf{x}_u\mathbf{x}_v}{1 - \mathbf{x}_u^2 + \mathbf{x}_v^2}. \end{equation*}$$

By Lemma 2.3, we have that $|\mathbf{x}_u|$, $|\mathbf{x}_v|$, $|\mathbf{z}_u|$, and $|\mathbf{z}_v|$ are all $O(n^{-1/2})$, and so the right-hand side of the previous inequality is $O(1/n)$. It follows that

$$\begin{equation*} |(\lambda _1 \mathbf{x}_u^2 - \lambda _1\mathbf{x}_v^2) - (\lambda _n \mathbf{z}_u^2 - \lambda _n \mathbf{z}_v^2)| < \frac{C}{n}, \end{equation*}$$

for some absolute constant $C$. Rearranging terms gives the desired result.

■

3. The spread-extremal problem for graphons

Graphons (or graph functions) are analytical objects that may be used to study the limiting behavior of large, dense graphs. They were originally introduced in 6 and 19.

3.1. Introduction to graphons

Consider the set $\mathcal{W}$ of all bounded symmetric measurable functions $W:[0,1]^2 \to [0,1]$ (by symmetric, we mean $W(x, y)=W(y,x)$ for all $(x, y)\in [0,1]^2$). A function $W\in \mathcal{W}$ is called a stepfunction if there is a partition of $[0,1]$ into subsets $S_1, S_2, \ldots , S_m$ such that $W$ is constant on every block $S_i\times S_j$. Every graph has a natural representation as a stepfunction in $\mathcal{W}$ taking values either 0 or 1 (such a graphon is referred to as a stepgraphon). In particular, given a graph $G$ on $n$ vertices indexed $\{1, 2, \ldots , n\}$, we can define a measurable set $K_G \subseteq [0,1]^2$ as

$$\begin{equation*} K_G = \bigcup _{u \sim v} \left[\frac{u-1}{n}, \frac{u}{n}\right]\times \left[\frac{v-1}{n}, \frac{v}{n}\right]. \end{equation*}$$

This represents the graph $G$ as a bounded symmetric measurable function $W_G$ that takes value $1$ on $K_G$ and $0$ everywhere else. For a measurable subset $U$, we will use $m(U)$ to denote its Lebesgue measure.

This representation of a graph as a measurable subset of $[0,1]^2$ lends itself to a visual presentation sometimes referred to as a “pixel picture”; see, for example, Figure 2 for two representations of a bipartite graph as a measurable subset of $[0,1]^2$. Clearly, this indicates that such a representation is not unique; neither is the representation of a graph as a stepfunction. Using an equivalence relation on $\mathcal{W}$ derived from the so-called cut metric, we can identify graphons that are equivalent up to relabeling, and up to any differences on a set of measure zero (i.e. equivalent almost everywhere).

For all symmetric, bounded Lebesgue-measurable functions $W:[0,1]^2\to \mathbb{R}$, we let

$$\begin{equation*} \|W\|_\square = \sup _{S, T\subseteq [0,1]} \left|\int _{S\times T} W(x,y)\,dx\,dy \right|. \end{equation*}$$

Here, $\|\cdot \|_\square$ is referred to as the cut norm. Next, we can also define a semidistance $\delta _\square$ on $\mathcal{W}$ as follows. First, we define the weak isomorphism of graphons. Let $\mathcal{S}$ be the set of all measure-preserving functions on $[0,1]$. For every $\varphi \in \mathcal{S}$ and every $W\in \mathcal{W}$, define $W^\varphi :[0,1]^2\to [0,1]$ by

$$\begin{align*} W^\varphi (x,y) \coloneq W(\varphi (x),\varphi (y)) \end{align*}$$

for a.e. $(x,y)\in [0,1]^2$. Now for any $W_1,W_2\in \mathcal{W}$, let

$$\begin{equation*} \delta _\square (W_1, W_2) = \inf _{\phi \in \mathcal{S}} \|W_1-W_2\circ \phi \|_\square . \end{equation*}$$

Define the equivalence relation $\sim$ on $\mathcal{W}$ as follows: for all $W_1, W_2\in \mathcal{W}$, $W_1\sim W_2$ if and only if $\delta _\square (W_1,W_2) = 0$. Furthermore, let $\hat{\mathcal{W}}\coloneq \mathcal{W}/\sim$ be the quotient space of $\mathcal{W}$ under $\sim$. Note that $\delta _\square$ induces a metric on $\hat{\mathcal{W}}$. Crucially, by 20, Theorem 5.1, $\hat{\mathcal{W}}$ is a compact metric space.

Given $W\in \hat{\mathcal{W}}$, we define the Hilbert-Schmidt operator $A_W: \mathscr{L}^2[0,1]\to \mathscr{L}^2[0,1]$ by

$$\begin{equation*} (A_Wf)(x) \coloneq \int _0^1 W(x,y)f(y) \,dy \end{equation*}$$

for all $f\in \mathscr{L}^2[0,1]$ and a.e. $x\in [0,1]$.

Since $W$ is symmetric and bounded, $A_W$ is a compact Hermitian operator. In particular, $A_W$ has a discrete, real spectrum $\Lambda (W)$ whose only possible accumulation point is $0$ (cf. 5), and so the maximum and minimum eigenvalues exist. Let $\mu (W)$ and $\nu (W)$ be the maximum and minimum eigenvalues of $A_W$, respectively, and define the spread of $W$ as

$$\begin{equation*} \mathrm{spr}(W) \coloneq \mu (W) - \nu (W). \end{equation*}$$

By the Min-Max Theorem, we have that

$$\begin{equation*} \mu (W) = \max _{\|f\|_2 = 1} \int _0^1\int _0^1 W(x,y)f(x)f(y) \, dx\, dy, \end{equation*}$$

and

$$\begin{equation*} \nu (W) = \min _{\|f\|_2 = 1} \int _0^1\int _0^1 W(x,y)f(x)f(y) \, dx\, dy. \end{equation*}$$

Both $\mu$ and $\nu$ are continuous functions with respect to $\delta _\square$. In particular, we have the following.

Theorem 3.1 (cf. 6, Theorem 6.6 or 18, Theorem 11.54).

Let $\{W_i\}_i$ be a sequence of graphons converging to $W$ with respect to $\delta _\square$. Then as $n\to \infty$,

$$\begin{align*} \mu (W_n)\to \mu (W) \quad \text{ and }\quad \nu (W_n)\to \nu (W). \end{align*}$$

If $W \sim W'$ then $\mu (W) = \mu (W')$ and $\nu (W) = \nu (W')$. By compactness, we may consider the optimization problem on the factor space $\hat{\mathcal{W}}$

$$\begin{equation*} \mathrm{spr}(\hat{\mathcal{W}})=\max _{W\in \hat{\mathcal{W}}} \, \mathrm{spr}(W), \end{equation*}$$

and there is a $W \in \hat{\mathcal{W}}$ that attains the maximum. Since every graph is represented by $W_G\in \hat{\mathcal{W}}$, this allows us to give an upper bound for $s(n)$ in terms of $\mathrm{spr}(\hat{\mathcal{W}})$. Indeed, by replacing the eigenvectors of $G$ with their corresponding stepfunctions, we can show Proposition 3.2.

Proposition 3.2.

Let $G$ be a graph on $n$ vertices. Then

$$\begin{align*} \lambda _1(G) = n \, \cdot \, \mu ({W_G}) \quad \text{ and }\quad \lambda _n(G) = n \, \cdot \, \nu ({W_G}). \end{align*}$$

Proposition 3.2 implies that $s(n) \leq n\cdot \mathrm{spr}(\hat{\mathcal{W}})$ for all $n$. Combined with Theorem 1.4, this gives Corollary 3.3 (a similar argument implies Corollary 1.5).

Corollary 3.3.

For all $n$, $s(n) \leq \frac{2n}{\sqrt {3}}$.

This can be proved more directly using Theorem 1.1 and taking tensor powers.

3.2. Properties of spread-extremal graphons

Our main objective in the following two sections is to solve the maximum spread problem for graphons, in order to produce a tight estimate for $s(n)$. In this subsection, we prove some preliminary results that are largely a translation of what is known in the graph setting (see Section 2). First, we define what it means for a graphon to be connected, and show that spread-extremal graphons must be connected. We then prove a standard corollary of the Perron-Frobenius theorem. Finally, we prove graphon versions of Lemma 2.1 and Lemma 2.4.

Let $W_1$ and $W_2$ be graphons, and let $\alpha _1,\alpha _2$ be positive real numbers with $\alpha _1+\alpha _2 = 1$. We define the direct sum of $W_1$ and $W_2$ with weights $\alpha _1$ and $\alpha _2$, denoted $W = \alpha _1W_1\oplus \alpha _2W_2$, as follows. Let $\varphi _1$ and $\varphi _2$ be the increasing affine maps that send $J_1 \coloneq [0,\alpha _1]$ and $J_2 \coloneq [\alpha _1,1]$ to $[0,1]$, respectively. Then for all $(x,y)\in [0,1]^2$, let

$$\begin{align*} W(x,y) \coloneq \left\{\begin{array}{rl} W_i(\varphi _i(x),\varphi _i(y)), &\text{if }(x,y)\in J_i\times J_i\text{ for some }i\in \{1,2\}\\0, & \text{otherwise} \end{array}\right. . \end{align*}$$

A graphon $W$ is connected if $W$ is not weakly isomorphic to a direct sum $\alpha _1W_1\oplus \alpha _2W_2$ where $\alpha _1\neq 0,1$. Equivalently, $W$ is connected if there does not exist a measurable subset $A\subseteq [0,1]$ of positive measure such that $W(x,y) = 0$ for a.e. $(x,y)\in A\times A^c$.

Proposition 3.4.

Suppose $W_1,W_2$ are graphons and $\alpha _1,\alpha _2$ are positive real numbers summing to $1$. Let $W\coloneq \alpha _1W_1\oplus \alpha _2W_2$. Then as multisets,

$$\begin{align*} \Lambda (W) = \{\alpha _1 u : u \in \Lambda (W_1) \}\cup \{ \alpha _2v : v\in \Lambda (W_2)\}. \end{align*}$$

Moreover, $\mathrm{spr}(W)\leq \alpha _1 \mathrm{spr}(W_1) + \alpha _2 \mathrm{spr}(W_2)$ with equality if and only if $W_1$ or $W_2$ is the all-zeroes graphon.

Proof.

For convenience, let $\Lambda _i \coloneq \{\alpha _iu : u\in \Lambda (W_i)\}$ for each $i\in \{1,2\}$ and $\Lambda \coloneq \Lambda (W)$. The first claim holds simply by considering the restriction of eigenfunctions to the intervals $[0,\alpha _1]$ and $[\alpha _1,1]$.

For the second claim, we first write $\mathrm{spr}(W) = \alpha _i\mu (W_i)-\alpha _j\nu (W_j)$, where $i,j\in \{1,2\}$. Let $I_i \coloneq [\min (\Lambda _i), \max (\Lambda _i)]$ for each $i\in \{1,2\}$ and $I \coloneq [\min (\Lambda ), \max (\Lambda )]$. Clearly $\alpha _i \mathrm{spr}(W_i) = \mathrm{diam}(I_i)$ for each $i\in \{1,2\}$ and $\mathrm{spr}(W) = \mathrm{diam}(I)$. Moreover, $I = I_1\cup I_2$. Since $0\in I_1\cap I_2$, $\mathrm{diam}(I)\leq \mathrm{diam}(I_1)+\mathrm{diam}(I_2)$ with equality if and only if either $I_1$ or $I_2$ equals $\{0\}$. So the desired claim holds.

■

Furthermore, the following basic corollary of the Perron-Frobenius holds. For completeness, we prove it here.

Proposition 3.5.

Let $W$ be a connected graphon, and write $f$ for an eigenfunction corresponding to $\mu (W)$. Then $f$ is nonzero with constant sign a.e.

Proof.

Let $\mu = \mu (W)$. Since

$$\begin{align*} \mu = \max _{\|h\|_2 = 1}\int _{(x,y)\in [0,1]^2}W(x,y)h(x)h(y) \,dx\,dy , \end{align*}$$

it follows without loss of generality that $f\geq 0$ a.e. on $[0,1]$. Let $Z\coloneq \{x\in [0,1] : f(x) = 0\}$. Then for a.e. $x\in Z$,

$$\begin{align*} 0 = \mu f(x) = \int _{y\in [0,1]}W(x,y)f(y) \, dy = \int _{y\in Z^c} W(x,y)f(y) \, dy. \end{align*}$$

Since $f > 0$ on $Z^c$, it follows that $W(x,y) = 0$ a.e. on $Z\times Z^c$. Clearly $m(Z^c) \neq 0$. If $m(Z) = 0$ then the desired claim holds, so without loss of generality, $0 < m(Z),m(Z^c)<1$. It follows that $W$ is disconnected, a contradiction to our assumption, which completes the proof.

■

We may now prove a graphon version of Lemma 2.1.

Lemma 3.6.

Suppose $W$ is a graphon achieving maximum spread, and let $f,g$ be eigenfunctions for the maximum and minimum eigenvalues for $W$, respectively. Then the following claims hold:

(i)

For a.e. $(x,y)\in [0,1]^2$,$$\begin{align*} W(x,y) = \left\{\begin{array}{rl} 1, & \text{if }f(x)f(y) > g(x)g(y) \\0, & \text{otherwise} \end{array} \right. . \end{align*}$$

(ii)

$f(x)f(y)-g(x)g(y) \neq 0$ for a.e. $(x,y)\in [0,1]^2$.

Proof.

We proceed in the following order:

•

Prove Item i holds for a.e. $(x,y)\in [0,1]^2$ such that $f(x)f(y)\neq g(x)g(y)$. We will call this Item i*.

•

Prove Item ii.

•

Deduce Item i also holds.

By Propositions 3.4 and 3.5, we may assume without loss of generality that $f > 0$ a.e. on $[0,1]$. For convenience, we define the quantity $d(x,y) \coloneq f(x)f(y)-g(x)g(y)$. To prove Item i*, we first define a graphon $W'$ by

$$\begin{align*} W'(x,y) = \left\{\begin{array}{rl} 1, & \text{if }d(x,y) > 0 \\0, & \text{if }d(x,y) < 0 \\W(x,y), & \text{otherwise} \end{array} \right. . \end{align*}$$

Then by inspection,

$$\begin{align*} \mathrm{spr}(W') &\geq \int _{(x,y)\in [0,1]^2} W'(x,y)(f(x)f(y)-g(x)g(y)) \,dx\,dy \\ &= \int _{(x,y)\in [0,1]^2} W(x,y)(f(x)f(y)-g(x)g(y)) \,dx\,dy \\ &\quad + \int _{d(x,y) > 0} (1-W(x,y))d(x,y) \,dx\,dy - \int _{d(x,y) < 0} W(x,y)d(x,y) \,dx\,dy \\ &= \mathrm{spr}(W) + \int _{d(x,y) > 0} (1-W(x,y))d(x,y) \,dx\,dy - \int _{d(x,y) < 0} W(x,y)d(x,y) \,dx\,dy . \end{align*}$$

Since $W$ maximizes spread, both integrals in the last line must be $0$, and hence Item i* holds.

Now, we prove Item ii. For convenience, we define $U$ to be the set of all pairs $(x,y)\in [0,1]^2$ so that $d(x,y) = 0$. Now let $\tilde{W}$ be any graphon that differs from $W$ only on $U$. Then

$$\begin{align*} \mathrm{spr}(\tilde{W}) &\geq \int _{(x,y)\in [0,1]^2} \tilde{W}(x,y)(f(x)f(y)-g(x)g(y)) \,dx\,dy \\ &= \int _{(x,y)\in [0,1]^2} W(x,y)(f(x)f(y)-g(x)g(y)) \,dx\,dy \\ &\quad + \int _{(x,y)\in U} ( \tilde{W}(x,y)-W(x,y))(f(x)f(y)-g(x)g(y)) \,dx\,dy \\ &= \mathrm{spr}(W). \end{align*}$$

Since $\mathrm{spr}(W)\geq \mathrm{spr}(\tilde{W})$, $f$ and $g$ are eigenfunctions for $\tilde{W}$, and we may write $\tilde{\mu }$ and $\tilde{\nu }$ for the corresponding eigenvalues. Now, we define

$$\begin{align*} I_{\tilde{W}}(x) &\coloneq (\tilde{\mu }-\mu )f(x) \\ &= \int _{y\in [0,1]}(\tilde{W}(x,y)-W(x,y))f(y) \, dy\\ &= \int _{y\in [0,1], \, (x,y)\in U} (\tilde{W}(x,y)-W(x,y))f(y) \, dy. \end{align*}$$

Similarly, we define

$$\begin{align*} J_{\tilde{W}}(x) &\coloneq (\tilde{\nu }-\nu )g(x) \\ &= \int _{y\in [0,1]}(\tilde{W}(x,y)-W(x,y))g(y) \, dy\\ &= \int _{y\in [0,1],\, (x,y)\in U} (\tilde{W}(x,y)-W(x,y))g(y) \, dy. \end{align*}$$

Since $f$ and $g$ are orthogonal,

$$\begin{align*} \int _{x\in [0,1]} I_{\tilde{W}}(x)J_{\tilde{W}}(x) \, dx &= 0. \end{align*}$$

By definition of $U$, we have that for a.e. $(x,y) \in U$, $0 = d(x,y) = f(x)f(y) - g(x)g(y)$. In particular, since $f(x),f(y) > 0$ for a.e. $(x,y)\in [0,1]^2$, then a.e. $(x,y)\in U$ has $g(x)g(y) > 0$. So by letting

$$\begin{align*} U_+ &\coloneq \{(x,y)\in U: g(x),g(y) > 0\}, \\ U_- &\coloneq \{(x,y)\in U:g(x),g(y)<0\},\text{ and} \\ U_0 &\coloneq U\setminus (U_+\cup U_-), \end{align*}$$

$U_0$ has measure $0$.

First, let us fix $\tilde{W}$ to be the graphon defined by

$$\begin{align*} \tilde{W}(x,y) &= \left\{\begin{array}{rl} 1, & \text{if } (x,y)\in U_+\\W(x,y), &\text{otherwise} \end{array} \right. . \end{align*}$$

For this choice of $\tilde{W}$,

$$\begin{align*} I_{\tilde{W}}(x) &= \int _{y\in [0,1], \, (x,y)\in U_+} (1-W(x,y))f(y) \, dy, \text{ and} \\ J_{\tilde{W}}(x) &= \int _{y\in [0,1], \, (x,y)\in U_+} (1-W(x,y))g(y) \, dy. \end{align*}$$

Clearly $I_{\tilde{W}}$ and $J_{\tilde{W}}$ are nonnegative functions, so $I_{\tilde{W}}(x)J_{\tilde{W}}(x) = 0$ for a.e. $x\in [0,1]$. Since $f(y)$ and $g(y)$ are positive for a.e. $(x,y)\in U$, $W(x,y) = 1$ for a.e. on $U_+$.

If instead we fix $\tilde{W}(x,y)$ to be $0$ for all $(x,y)\in U_+$, it follows by a similar argument that $W(x,y) = 0$ for a.e. $(x,y)\in U_+$. So $U_+$ has measure $0$. Repeating the same argument on $U_-$, we similarly conclude that $U_-$ has measure $0$. This completes the proof of Item ii.

Finally we note that Items i* and ii together imply Item i.

■

From here, it is easy to see that any graphon maximizing the spread is a join of two threshold graphons. Next we prove the graphon version of Lemma 2.4.

Lemma 3.7.

If $W$ is a graphon achieving the maximum spread with corresponding eigenfunctions $f,g$, then $\mu f^2 - \nu g^2 = \mu -\nu$ almost everywhere.

Proof.

We will use the notation $(x,y) \in W$ to denote that $(x,y)\in [0,1]^2$ satisfies $W(x,y) =1$. Let $\varphi :[0,1]\to [0,1]$ be an arbitrary homeomorphism that is orientation-preserving in the sense that $\varphi (0) = 0$ and $\varphi (1) = 1$. Then $\varphi$ is a continuous strictly monotone increasing function which is differentiable almost everywhere. Now let $\tilde{f}\coloneq \varphi '\cdot (f\circ \varphi )$, $\tilde{g}\coloneq \varphi '\cdot (g\circ \varphi )$ and $\tilde{W} \coloneq \{ (x,y)\in [0,1]^2 : (\varphi (x),\varphi (y))\in W \}$. Using the substitutions $u = \varphi (x)$ and $v = \varphi (y)$,

$$\begin{align*} \tilde{f}\tilde{W} \tilde{f}&= \int _{ (x,y)\in [0,1]^2 } \chi _{(\varphi (x),\varphi (y))\in \tilde{W}}\; \varphi '(x)\varphi '(y)\cdot f(\varphi (x))f(\varphi (y)) \, dx\, dy\\ &= \int _{ (x,y)\in [0,1]^2 } \chi _{(x,y)\in W}\; f(u)f(v) \, du\, dv\\ &= \mu . \end{align*}$$

Similarly, $\tilde{g}\tilde{W}\tilde{g}= \nu$.

Note however that the $L_2$ norms of $\tilde{f},\tilde{g}$ may not be $1$. Indeed using the substitution $u = \varphi (x)$,

$$\begin{equation*} \|\tilde{f}\|_2^2 = \int _{x\in [0,1]} \varphi '(x)^2f(\varphi (x))^2\, dx = \int _{u\in [0,1]} \varphi '(\varphi ^{-1}(u))\cdot f(u)^2\, du . \end{equation*}$$

We exploit this fact as follows. Suppose $I,J$ are disjoint subintervals of $[0,1]$ of the same positive length $m(I) = m(J) = \ell > 0$, and for any $\varepsilon > 0$ sufficiently small (in terms of $\ell$), let $\varphi$ be the (unique) piecewise linear function that stretches $I$ to length $(1+\varepsilon )m(I)$, shrinks $J$ to length $(1-\varepsilon )m(J)$, and shifts only the elements in between $I$ and $J$. Note that for a.e. $x\in [0,1]$,

$$\begin{equation*} \varphi '(x) = \left\{\begin{array}{rl} 1+\varepsilon , & \text{if } x\in I, \\1-\varepsilon , & \text{if } x\in J, \\1, & \text{otherwise}. \end{array}\right. \end{equation*}$$

Again with the substitution $u = \varphi (x)$,

$$\begin{align*} \|\tilde{f}\|_2^2 &= \int _{x\in [0,1]} \varphi '(x)^2\cdot f(\varphi (x))^2\, dx\\ &= \int _{[u\in [0,1]} \varphi '(\varphi ^{-1}(u))f(u)^2\, du \\ &= 1 + \varepsilon \cdot ( \|\chi _If\|_2^2 -\|\chi _Jf\|_2^2 ). \end{align*}$$

The same equality holds for $\tilde{g}$ instead of $\tilde{f}$. After normalizing $\tilde{f}$ and $\tilde{g}$, by optimality of $W$, we get a difference of Rayleigh quotients as

$$\begin{align*} 0 &\leq (fWf-gWg) - \dfrac{\tilde{f}\tilde{W}\tilde{f}}{\|\tilde{f}\|_2^2} - \dfrac{\tilde{g}\tilde{W}\tilde{g}}{\|\tilde{g}\|_2^2} \\ &= \dfrac{ \mu \varepsilon \cdot ( \|\chi _If\|_2^2 -\|\chi _Jf\|_2^2) }{1+\varepsilon \cdot ( \|\chi _If\|_2^2 -\|\chi _Jf\|_2^2) } - \dfrac{ \nu \varepsilon \cdot ( \|\chi _Ig\|_2^2 -\|\chi _Jg\|_2^2) }{1+\varepsilon \cdot ( \|\chi _Ig\|_2^2 -\|\chi _Jg\|_2^2) }\\ &= (1+o(1))\varepsilon \cdot \left( \int _I (\mu f(x)^2-\nu g(x)^2) \, dx -\int _J (\mu f(x)^2-\nu g(x)^2) \, dx \right) \end{align*}$$

as $\varepsilon \to 0$. It follows that for all disjoint intervals $I,J\subseteq [0,1]$ of the same length, the corresponding integrals are the same. Taking finer and finer partitions of $[0,1]$, it follows that the integrand $\mu f(x)^2-\nu g(x)^2$ is constant almost everywhere. Since the average of this quantity over all $[0,1]$ is $\mu -\nu$, the desired claim holds.

■

4. From graphons to stepgraphons

The main result of this section is as follows.

Theorem 4.1.

Suppose $W$ maximizes $\mathrm{spr}(\hat{\mathcal{W}})$. Then $W$ is a stepfunction taking values $0$ and $1$ of the following form

Furthermore, the internal divisions separate according to the sign of the eigenfunction corresponding to the minimum eigenvalue of $W$.

We begin Section 4.1 by mirroring the argument in 30, which proved a conjecture of Nikiforov regarding the largest eigenvalue of a graph and its complement, $\mu +\overline{\mu }$. There, Terpai showed that performing two operations on graphons leads to a strict increase in $\mu +\overline{\mu }$. Furthermore based on previous work of Nikiforov from 24, the conjecture for graphs reduced directly to maximizing $\mu +\overline{\mu }$ for graphons. Using these operations, Terpai 30 reduced to a $4\times 4$ stepgraphon and then completed the proof by hand.

In our case, we are not so lucky and are left with a $7\times 7$ stepgraphon after performing similar but more technical operations, detailed in this section. In order to reduce to a $3\times 3$ stepgraphon, we make use of interval arithmetic (see Section 5.2 and Appendices A and B). Furthermore, our proof requires an additional technical argument to translate the result for graphons (Theorem 5.1) to our main result for graphs (Theorem 1.1). In Section 4.2, we prove Theorem 4.1.

4.1. Averaging

For convenience, we introduce some terminology. For any graphon $W$ with $\lambda$-eigenfunction $h$, we say that $x\in [0,1]$ is typical (with respect to $W$ and $h$) if

$$\begin{align*} \lambda \cdot h(x) = \int _{y\in [0,1]}W(x,y)h(y) \, dy. \end{align*}$$

Note that a.e. $x\in [0,1]$ is typical. Additionally if $U\subseteq [0,1]$ is measurable with positive measure, then we say that $x_0\in U$ is average (on $U$, with respect to $W$ and $h$) if

$$\begin{align*} h(x_0)^2 = \dfrac{1}{m(U)}\int _{y\in U}h(y)^2 \, dy. \end{align*}$$

Given $W,h,U$, and $x_0$ as above, we define the $L_2[0,1]$ function $\mathrm{av}_{U,x_0}h$ by setting

$$\begin{align*} (\mathrm{av}_{U,x_0}h)(x) \coloneq \left\{\begin{array}{rl} h(x_0), & \text{if } x\in U\\h(x), & \text{otherwise} \end{array}\right. . \end{align*}$$

Clearly $\|\mathrm{av}_{U,x_0}h\|_2 = \|h\|_2$. Additionally, we define the graphon $\mathrm{av}_{U,x_0}W$ by setting

$$\begin{align*} \mathrm{av}_{U,x_0}W (x,y) \coloneq \left\{\begin{array}{rl} 0, & (x,y)\in U\times U \\W(x_0,y), &(x,y)\in U\times U^c \\W(x,x_0), &(x,y)\in U^c\times U \\W(x,y), & (x,y)\in U^c\times U^c \end{array}\right. . \end{align*}$$

In the graph setting, this is analogous to replacing $U$ with an independent set whose vertices are clones of $x_0$. Lemma 4.2 indicates how this cloning affects the eigenvalues.

Lemma 4.2.

Suppose $W$ is a graphon with a $\lambda$-eigenfunction $h$, and suppose there exist disjoint measurable subsets $U_1,U_2\subseteq [0,1]$ of positive measures $\alpha$ and $\beta$, respectively. Let $U\coloneq U_1\cup U_2$. Moreover, suppose $W = 0$ a.e. on $(U\times U)\setminus (U_1\times U_1)$. Additionally, suppose $x_0\in U_2$ is typical and average on $U$, with respect to $W$ and $h$. Let $\tilde{h}\coloneq \mathrm{av}_{U,x_0}h$ and $\tilde{W}\coloneq \mathrm{av}_{U,x_0}W$. Then for a.e. $x\in [0,1]$,

$$\begin{align} (A_{\tilde{W}}\tilde{h})(x) &= \lambda \tilde{h}(x) + \left\{\begin{array}{rl} 0, & \text{if } x\in U\\m(U)\cdot W(x_0,x)h(x_0) - \int _{y\in U} W(x,y)h(y) \, dy, &\text{otherwise} \end{array}\right. . {\tag{2}} \end{align}$$

Furthermore,

$$\begin{align} \langle A_{\tilde{W}}\tilde{h}, \tilde{h}\rangle = \lambda + \int _{(x,y)\in U_1\times U_1}W(x,y)h(x)h(y) \, dx \, dy. {\tag{3}} \end{align}$$

Proof.

We first prove Equation 2. Note that for a.e. $x\in U$,

$$\begin{align*} (A_{\tilde{W}}\tilde{h})(x) &= \int _{y\in [0,1]} \tilde{W}(x,y)\tilde{h}(y) \, dy \\ &= \int _{y\in U} \tilde{W}(x,y)\tilde{h}(y) \, dy + \int _{y\in [0,1]\setminus U} \tilde{W}(x,y)\tilde{h}(y) \, dy \\ &= \int _{y\in [0,1]\setminus U} W(x_0,y)h(y) \, dy \\ &= \int _{y\in [0,1]} W(x_0,y)h(y) \, dy - \int _{y\in U} W(x_0,y)h(y) \, dy \\ &= \lambda h(x_0)\\ &= \lambda \tilde{h}(x), \end{align*}$$

as desired. Now note that for a.e. $x\in [0,1]\setminus U$,

$$\begin{align*} (A_{\tilde{W}}\tilde{h})(x) &= \int _{y\in [0,1]} \tilde{W}(x,y)\tilde{h}(y) \, dy \\ &= \int _{y\in U} \tilde{W}(x,y)\tilde{h}(y) \, dy + \int _{y\in [0,1]\setminus U} \tilde{W}(x,y)\tilde{h}(y) \, dy \\ &= \int _{y\in U} W(x_0,x)h(x_0) \, dy + \int _{y\in [0,1]\setminus U} W(x,y)h(y) \, dy \\ &= m(U)\cdot W(x_0,x)h(x_0) + \int _{y\in [0,1]} W(x,y)h(y) \, dy - \int _{y\in U} W(x,y)h(y) \, dy \\ &= \lambda h(x) + m(U)\cdot W(x_0,x)h(x_0) - \int _{y\in U} W(x,y)h(y) \, dy . \end{align*}$$

So again, the claim holds and this completes the proof of Equation 2. Now we prove Equation 3. Indeed by Equation 2,

$$\begin{align*} \langle (A_{\tilde{W}}\tilde{h}), \tilde{h}\rangle &= \int _{x\in [0,1]} (A_{\tilde{W}}\tilde{h})(x) \tilde{h}(x) \, dx \\ &= \int _{x\in [0,1]} \lambda \tilde{h}(x)^2 \, dx \\ &\quad + \int _{x\in [0,1]\setminus U} \left( m(U)\cdot W(x_0,x)h(x_0) - \int _{y\in U}W(x,y)h(y) \, dy \right) \cdot h(x) \, dx \\ &= \lambda + m(U)\cdot h(x_0) \left( \int _{x\in [0,1]} W(x_0,x)h(x) \, dx - \int _{x\in U} W(x_0,x)h(x) \, dx \right) \\ &\quad - \int _{y\in U} \left( \int _{x\in [0,1]} W(x,y)h(x) \, dx -\int _{x\in U} W(x,y)h(x) \, dx \right) \cdot h(y) \, dy \\ &= \lambda + m(U)\cdot h(x_0)\left( \lambda h(x_0) - \int _{y\in U} 0 \, dy \right) \\ &\quad - \int _{y\in U} \left( \lambda h(y)^2 -\int _{x\in U} W(x,y)h(x)h(y) \, dx \right) \, dy \\ &= \lambda + \lambda m(U)\cdot h(x_0)^2 - \lambda \int _{y\in U} h(y)^2 \, dy + \int _{(x,y)\in U\times U} W(x,y)h(x)h(y) \, dx \, dy \\ &= \lambda + \int _{(x,y)\in U_1\times U_1} W(x,y)h(x)h(y) \, dx \, dy, \end{align*}$$

and this completes the proof of desired claims.

■

We have the following useful corollary.

Corollary 4.3.

Suppose $\mathrm{spr}(W) = \mathrm{spr}(\hat{\mathcal{W}})$ with maximum and minimum eigenvalues $\mu ,\nu$ corresponding respectively to eigenfunctions $f,g$. Moreover, suppose that there exist disjoint subsets $A,B\subseteq [0,1]$ and $x_0\in B$ so that the conditions of Lemma 4.2 are met for $W$ with $\lambda = \mu$, $h = f$, $U_1=A$, and $U_2=B$. Then,

(i)

$W(x,y) = 0$ for a.e. $(x,y)\in U^2$, and

(ii)

$f$ is constant on $U$.

Proof.

Without loss of generality, we assume that $\|f\|_2 = \|g\|_2 = 1$. Write $\tilde{W}$ for the graphon and $\tilde{f},\tilde{g}$ for the corresponding functions produced by Lemma 4.2. By Proposition 3.5, we may assume without loss of generality that $f > 0$ a.e. on $[0,1]$. We first prove Item i. Note that

$$\begin{align} \mathrm{spr}(\tilde{W}) &\geq \int _{(x,y)\in [0,1]^2} \tilde{W}(x,y)(\tilde{f}(x)\tilde{f}(y)-\tilde{g}(x)\tilde{g}(y)) \, dx \, dy \\ &= (\mu -\nu ) + \int _{(x,y)\in A\times A}W(x,y)(f(x)f(y)-g(x)g(y)) \, dx \, dy \\ &= \mathrm{spr}(W) + \int _{(x,y)\in A\times A}W(x,y)(f(x)f(y)-g(x)g(y)) \, dx \, dy. {\tag{4}} \end{align}$$

Since $\mathrm{spr}(W)\geq \mathrm{spr}(\tilde{W})$ and by Lemma 3.6ii, $f(x)f(y)-g(x)g(y) > 0$ for a.e. $(x,y)\in A\times A$ such that $W(x,y) \neq 0$. Item i follows.

For Item ii, we first note that $f$ is a $\mu$-eigenfunction for $\tilde{W}$. Indeed, if not, then the inequality in 4 holds strictly, a contradiction to the fact that $\mathrm{spr}(W)\geq \mathrm{spr}(\tilde{W})$. Again by Lemma 4.2,

$$\begin{align*} m(U)\cdot W(x_0,x)f(x_0) = \int _{y\in U}W(x,y)f(y) \, dy \end{align*}$$

for a.e. $x\in [0,1]\setminus U$. Let $S_1 \coloneq \{x\in [0,1]\setminus U : W(x_0,x) = 1\}$ and $S_0 \coloneq [0,1]\setminus (U\cup S_1)$. We claim that $m(S_1) = 0$. Assume otherwise. By Lemma 4.2 and by Cauchy-Schwarz, for a.e. $x\in S_1$

$$\begin{align*} m(U)\cdot f(x_0) &= m(U)\cdot W(x_0,x)f(x_0) \\ &= \int _{y\in U}W(x,y)f(y) \, dy \\ &\leq \int _{y\in U} f(y) \, dy \\ &\leq m(U)\cdot f(x_0), \end{align*}$$

and by sandwiching, $W(x,y) = 1$ and $f(y) = f(x_0)$ for a.e. $y\in U$. Since $m(S_1) > 0$, it follows that $f(y) = f(x_0) = 0$ for a.e. $y\in U$, as desired.

So we assume otherwise, that $m(S_1) = 0$. Then for a.e. $x\in [0,1]\setminus U$, $W(x_0,x) = 0$ and

$$\begin{align*} 0 &= m(U)\cdot W(x_0,x)f(x_0)= \int _{y\in U} W(x,y)f(y) \, dy \end{align*}$$

and since $f>0$ a.e. on $[0,1]$, it follows that $W(x,y) = 0$ for a.e. $y\in U$. Altogether, $W(x,y) = 0$ for a.e. $(x,y)\in ([0,1]\setminus U)\times U$. So $W$ is a disconnected, a contradiction to Proposition 3.4. The desired claim holds.

■

4.2. Proof of Theorem 4.1

Proof.

For convenience, we write $\mu \coloneq \mu (W)$ and $\nu \coloneq \nu (W)$ and let $f,g$ denote the corresponding unit eigenfunctions. By Proposition 3.5, we may assume without loss of generality that $f>0$.

First, we show without loss of generality that $f,g$ are monotone on the sets $P \coloneq \{x\in [0,1] : g(x)\geq 0\}$ and $N \coloneq [0,1]\setminus P$. Indeed, we define a total ordering $\preccurlyeq$ on $[0,1]$ as follows. For all $x$ and $y$, we let $x \preccurlyeq y$ if:

(i)

$g(x)\geq 0$ and $g(y)<0$, or

(ii)

Item (i) does not hold and $f(x) > f(y)$, or

(iii)

Item (i) does not hold, $f(x) = f(y)$, and $x\leq y$.

By inspection, the function $\varphi :[0,1]\to [0,1]$ defined by

$$\begin{align*} \varphi (x) \coloneq m(\{y\in [0,1] : y\preccurlyeq x\}) \end{align*}$$

is a weak isomorphism between $W$ and its entrywise composition with $\varphi$. By invariance of $\mathrm{spr}(\cdot )$ under weak isomorphism, we make the above replacement and write $f,g$ for the replacement eigenfunctions. That is, we are assuming that our graphon is relabeled so that $[0,1]$ respects $\preccurlyeq$.

As above, let $P \coloneq \{x\in [0,1] : g(x) \geq 0\}$ and $N\coloneq [0,1]\setminus P$. By Lemma 3.7, $f$ and $-g$ are monotone nonincreasing on $P$. Additionally, $f$ and $g$ are monotone nonincreasing on $N$. Without loss of generality, we may assume that $W$ is of the form from Lemma 3.6. Now we let $S \coloneq \{x\in [0,1] : f(x) < |g(x)|\}$ and $C\coloneq [0,1]\setminus S$. By Lemma 3.6 we have that $W(x,y)=1$ for almost every $x,y\in C$ and $W(x,y)=0$ for almost every $x,y\in S \cap P$ or $x,y\in S\cap N$. We have used the notation $C$ and $S$ because the analogous sets in the graph setting form a clique or a stable set respectively. We first prove Claim A.

Claim A.

Except on a set of measure $0$, $f$ takes on at most $2$ values on $P\cap S$, and at most $2$ values on $N\cap S$.

We first prove Claim A for $f$ on $P\cap S$. Let $D$ be the set of all discontinuities of $f$ on the interior of the interval $P\cap S$. Clearly $D$ consists only of jump-discontinuities. By the Darboux-Froda Theorem, $D$ is at most countable and moreover, $(P\cap S)\setminus D$ is a union of at most countably many disjoint intervals $\mathcal{I}$. Moreover, $f$ is continuous on the interior of each $I\in \mathcal{I}$.

We show now that $f$ is piecewise constant on the interiors of each $I\in \mathcal{I}$. Indeed, let $I\in \mathcal{I}$. Since $f$ is a $\mu$-eigenfunction function for $W$,

$$\begin{align*} \mu f(x) = \int _{y\in [0,1]}W(x,y)f(y) \, dy \end{align*}$$

for a.e. $x\in [0,1]$. By continuity of $f$ on the interior of $I$, this equation holds everywhere on the interior of $I$. Additionally, since $f$ is continuous on the interior of $I$, by the Mean Value Theorem, there exists some $x_0$ in the interior of $I$ so that

$$\begin{align*} f(x_0)^2 = \dfrac{1}{m(U)}\int _{x\in U}f(x)^2 \, dx. \end{align*}$$

By Corollary 4.3, $f$ is constant on the interior of $U$, as desired.

If $|\mathcal{I}|\leq 2$, the desired claim holds, so we may assume otherwise. Then there exists distinct $I_1,I_2,I_3\in \mathcal{I}$. Moreover, $f$ equals a constant $f_1,f_2,f_3$ on the interiors of $I_1$, $I_2$, and $I_3$, respectively. Additionally, since $I_1$, $I_2$, and $I_3$ are separated from each other by at least one jump discontinuity, we may assume without loss of generality that $f_1 < f_2 < f_3$. It follows that there exists a measurable subset $U\subseteq I_1\cup I_2\cup I_3$ of positive measure so that

$$\begin{align*} f_2^2 &= \dfrac{1}{m(U)}\int _{x\in U}f(x)^2 \, dx. \end{align*}$$

By Corollary 4.3, $f$ is constant on $U$, a contradiction. So Claim A holds on $P\cap S$. For Claim A on $N\cap S$, we may repeat this argument with $P$ and $N$ interchanged, and $g$ and $-g$ interchanged.

Now we show Claim B.

Claim B.

For a.e. $(x,y) \in (P\times P)\cup (N\times N)$ such that $f(x)\geq f(y)$, we have that for a.e. $z\in [0,1]$, $W(x,z) = 0$ implies that $W(y,z) = 0$.

We first prove Claim B for a.e. $(x,y)\in P\times P$. Suppose $W(y,z) = 0$. By Lemma 3.6, in this case $z\in P$. Then for a.e. such $x,y$, by Lemma 3.7, $g(x)\leq g(y)$. By Lemma 3.6i, $W(x,z) = 0$ implies that $f(x)f(z) < g(x)g(z)$. Since $f(x)\geq f(y)$ and $g(x)\leq g(y)$, $f(y)f(z) < g(y)g(z)$. Again by Lemma 3.6i, $W(y,z) = 0$ for a.e. such $x,y,z$, as desired. So the desired claim holds for a.e. $(x,y)\in P\times P$ such that $f(x)\geq f(y)$. We may repeat the argument for a.e. $(x,y)\in N\times N$ to arrive at the same conclusion.

Claim C follows directly from Lemma 3.7.

Claim C.

For a.e. $x\in [0,1]$, $x\in C$ if and only if $f(x) \geq 1$, if and only if $|g(x)| \leq 1$.

Finally, we show Claim D.

Claim D.

Except on a set of measure $0$, $f$ takes on at most $3$ values on $P\cap C$, and at most $3$ values on $N\cap C$.

For a proof, we first write $P\cap S = S_1 \cup S_2$ so that $S_1,S_2$ are disjoint, $f$ equals some constant $f_1$ a.e. on $S_1$, and $f$ equals some constant $f_2$ a.e. on $S_2$. By Lemma 3.7, $g$ equals some constant $g_1$ a.e. on $S_1$ and $g$ equals some constant $g_2$ a.e. on $S_2$. By definition of $P$, $g_1,g_2\geq 0$. Now suppose $x\in P\cap C$ so that

$$\begin{align*} \mu f(x) &= \int _{y\in [0,1]}W(x,y)f(y) \, dy. \end{align*}$$

Then by Lemma 3.6i,

$$\begin{align*} \mu f(x) &= \int _{y\in (P\cap C)\cup N} f(y) \, dy + \int _{y\in S_1}W(x,y)f(y) \, dy + \int _{y\in S_2}W(x,y)f(y) \, dy. \end{align*}$$

By Claim B, this expression for $\mu f(x)$ may take on at most $3$ values. So the desired claim holds on $P\cap C$. Repeating the same argument, Claim D also holds on $N\cap C$.

We are nearly done with the proof of the theorem, as we have now reduced $W$ to a $10\times 10$ stepgraphon. To complete the proof, we show that we may reduce to at most $7\times 7$. We now partition $P\cap C, P\cap S, N\cap C$, and $N\cap S$ so that $f$ and $g$ are constant a.e. on each part as:

•

$P\cap C = U_1\cup U_2\cup U_3$,

•

$P\cap S = U_4\cup U_5$,

•

$N\cap C = U_6\cup U_7\cup U_8$, and

•

$N\cap S = U_9\cup U_{10}$.

Then by Lemma 3.6i, there exists a matrix $(m_{ij})_{i,j\in [10]}$ so that for all $(i,j)\in [10]\times [10]$,

•

$m_{ij}\in \{0,1\}$,

•

$W(x,y) = m_{ij}$ for a.e. $(x,y)\in U_i\times U_j$,

•

$m_{ij} = 1$ if and only if $f_if_j > g_ig_j$, and

•

$m_{ij} = 0$ if and only if $f_if_j < g_ig_j$.

Additionally, we set $\alpha _i = m(U_i)$ and also denote by $f_i$ and $g_i$ the constant values of $f,g$ on each $U_i$, respectively, for each $i= 1, \ldots , 10$. Furthermore, by Claim C and Lemma 3.6 we assume without loss of generality that $f_1 > f_2 > f_3 \geq 1 > f_4 > f_5$ and that $f_6 > f_7 > f_8 \geq 1 > f_9 > f_{10}$. Also by Lemma 3.7, $0 \leq g_1 < g_2 < g_3 \leq 1 < g_4 < g_5$ and $0 \leq -g_1 < -g_2 < -g_3 \leq 1 < -g_4 < -g_5$. Also, by Claim B, no two columns of $m$ are identical within the sets $\{1,2,3,4,5\}$ and within $\{6,7,8,9,10\}$. Shading $m_{ij} = 1$ black and $m_{ij} = 0$ white, we let

Therefore, $W$ is a stepgraphon with values determined by $M$ and the size of each block determined by the $\alpha _i$.

We claim that $0\in \{\alpha _3, \alpha _4, \alpha _5\}$ and $0\in \{\alpha _8,\alpha _9,\alpha _{10}\}$. For the first claim, assume to the contrary that all of $\alpha _3, \alpha _4, \alpha _5$ are positive and note that there exists some $x_4\in U_4$ such that

$$\begin{align*} \mu f_4 = \mu f(x_4) = \int _{y\in [0,1]}W(x_4,y)f(y) \, dy. \end{align*}$$

Moreover for some measurable subsets $U_3'\subseteq U_3$ and $U_5'\subseteq U_5$ of positive measure so that with $U \coloneq U_3'\cup U_4\cup U_5'$,

$$\begin{align*} f(x_4)^2 = \dfrac{1}{m(U)}\int _{y\in U}f(y)^2 \, dy. \end{align*}$$

Note that by Lemma 3.7, we may assume that $x_4$ is average on $U$ with respect to $g$ as well. The conditions of Corollary 4.3 are met for $W$ with $A=U_3', B=U_4\cup U_5',x_0 = x_4$. Since $\int _{A\times A}W(x,y)f(x)f(y) \, dx \, dy > 0$, this is a contradiction to Corollary 4.3, so the desired claim holds. The same argument may be used to prove that $0\in \{\alpha _8,\alpha _9,\alpha _{10}\}$.

We now form the principal submatrix $M'$ by removing the $i$-th row and column from $M$ if and only if $\alpha _i = 0$. Since $\alpha _i=0$, $W$ is a stepgraphon with values determined by $M'$. Let $M_P'$ denote the principal submatrix of $M'$ corresponding to the indices $i\in \{1,\dots ,5\}$ so that $\alpha _i>0$. That is, $M_P'$ corresponds to the upper left hand block of $M$. We use red to indicate rows and columns present in $M$ but not $M_P'$. When forming the submatrix $M_P'$, we borrow the internal subdivisions which are present in the definition of $M$ above to denote where $f\geq 1$ and where $f<1$ (or between $S \cap P$ and $C \cap P$). Note that this is not the same as what the internal divisions denote in the statement of the theorem. Since $0\in \{\alpha _3,\alpha _4,\alpha _5\}$, it follows that $M_P'$ is a principal submatrix of

In the second case, columns $2$ and $3$ are identical in $M'$, and in the third case, columns $1$ and $2$ are identical in $M'$. So without loss of generality, $M_P'$ is a principal submatrix of one of

In each case, $M_P'$ is a principal submatrix of

An identical argument shows that the principal submatrix of $M'$ on the indices $i\in \{6,\dots ,10\}$ such that $\alpha _i>0$ is a principal submatrix of

Finally, we note that $0\in \{\alpha _1,\alpha _6\}$. Indeed otherwise the corresponding columns are identical in $M'$, a contradiction. So without loss of generality, row and column $6$ were also removed from $M$ to form $M'$. This completes the proof of the theorem.

■

5. Spread maximum graphons

In this section, we complete the proof of the graphon version of the spread conjecture of Gregory, Hershkowitz, and Kirkland from 13. In particular, we prove Theorem 5.1. For convenience and completeness, we state this result in the following level of detail.

Theorem 5.1.

If $W$ is a graphon that maximizes spread, then $W$ may be represented as follows. For all $(x,y)\in [0,1]^2$,

$$\begin{align*} W(x,y) =\left\{\begin{array}{rl} 0, &\text{if }(x,y)\in [2/3, 1]^2\\1, &\text{otherwise} \end{array}\right. . \end{align*}$$

Furthermore,

$$\begin{align*} \mu &= \dfrac{1+\sqrt {3}}{3} \quad \text{ and } \quad \nu = \dfrac{1-\sqrt {3}}{3} \end{align*}$$

are the maximum and minimum eigenvalues of $W$, respectively, and if $f,g$ are unit eigenfunctions associated to $\mu ,\nu$, respectively, then, up to a change in sign, they may be written as follows. For every $x\in [0,1]$,

$$\begin{align*} f(x) &= \dfrac{1}{2\sqrt {3+\sqrt {3}}} \cdot \left\{\begin{array}{rl} 3+\sqrt {3}, & \text{if } x\in [0,2/3] \\2\cdot \sqrt {3}, & \text{otherwise} \end{array}\right. , \text{ and }\\ g(x) &= \dfrac{1}{2\sqrt {3-\sqrt {3}}} \cdot \left\{\begin{array}{rl} 3-\sqrt {3}, & \text{if }x\in [0,2/3] \\-2\cdot \sqrt {3}, & \text{otherwise} \end{array}\right. . \end{align*}$$

To help outline our proof of Theorem 5.1, let the spread-extremal graphon have block sizes $\alpha _1,\ldots , \alpha _7$. Note that the spread of the graphon is the same as the spread of matrix $M^*$ in Figure 3, and so we will optimize the spread of $M^*$ over choices of $\alpha _1,\dots , \alpha _7$. Let $G^*$ be the unweighted graph (with loops) corresponding to the matrix.

We proceed in the following steps.

(1)

In Section A.1, we reduce the proof of Theorem 5.1 to $17$ cases, each corresponding to a subset $S$ of $V(G^*)$. For each such $S$ we define an optimization problem $\mathrm{SPR}_S$, the solution to which gives us an upper bound on the spread of any graphon in the case corresponding to $S$.

(2)

In Section 5.2, we appeal to interval arithmetic to translate these optimization problems into algorithms. Based on the output of the $17$ programs we wrote, we eliminate $15$ of the $17$ cases. We address the multitude of formulas used throughout and relocate their statements and proofs to Appendix B.1.

(3)

Finally in Section 5.3, we complete the proof of Theorem 5.1 by analyzing the $2$ remaining cases. Here, we apply Viète’s Formula for roots of cubic equations and make a direct argument.

For concreteness, we define $G^*$ on the vertex set $\{1,\dots ,7\}$. Explicitly, the neighborhoods $N_1,\dots , N_7$ of $1,\dots , 7$ are defined as:

$$\begin{align*} \begin{array}{ll} N_1 \coloneq \{1,2,3,4,5,6,7\} & N_2 \coloneq \{1,2,3,5,6,7\} \\N_3 \coloneq \{1,2,5,6,7\} & N_4 \coloneq \{1,5,6,7\} \\N_5 \coloneq \{1,2,3,4,5,6\} & N_6 \coloneq \{1,2,3,4,5\} \\N_7 \coloneq \{1,2,3,4\} \end{array} . \end{align*}$$

More compactly, we may note that

$$\begin{align*} \begin{array}{llll} N_1 = \{1,\dots , 7\} & N_2 = N_1\setminus \{4\} & N_3 = N_2\setminus \{3\} & N_4 = N_3\setminus \{2\} \\& N_5 = N_1\setminus \{7\} & N_6 = N_5\setminus \{6\} & N_7 = N_6\setminus \{5\} \end{array} . \end{align*}$$

5.1. Stepgraphon case analysis

Let $W$ be a graphon maximizing spread. By Theorem 4.1, we may assume that $W$ is a $7\times 7$ stepgraphon corresponding to $G^\ast$. We will break into cases depending on which of the $7$ weights $\alpha _1, \ldots \alpha _7$ are zero and which are positive. For some of these combinations the corresponding graphons are isomorphic, and in this section we will outline how one can show that we need only consider $17$ cases rather than $2^7$.

We will present each case with the set of indices which have strictly positive weight. Additionally, we will use vertical bars to partition the set of integers according to its intersection with the sets $\{1\}$, $\{2,3,4\}$ and $\{5,6,7\}$. Recall that vertices in block $1$ are dominating vertices and vertices in blocks $5$, $6$, and $7$ have negative entries in the eigenfunction corresponding to $\nu$. For example, we use $4|57$ to refer to the case that $\alpha _4, \alpha _5, \alpha _7$ are all positive and $\alpha _1 = \alpha _2 = \alpha _3 = \alpha _6 = 0$; see Figure 4.

To give an upper bound on the spread of any graphon corresponding to case $4|57$ we solve a constrained optimization problem. Let $f_4, f_5, f_7$ and $g_4, g_5, g_7$ denote the eigenfunction entries for unit eigenfunctions $f$ and $g$ of the graphon. Then we maximize $\mu - \nu$ subject to

$$\begin{align*} \alpha _4 + \alpha _5 + \alpha _7 &=1,\\ \alpha _4f_4^2 + \alpha _5f_5^2 + \alpha _7 f_7^2 &=1 ,\\ \alpha _4g_4^2 + \alpha _5g_5^2 + \alpha _7 g_7^2 &= 1,\\ \mu f_i^2 - \nu g_i^2 &= \mu -\nu \quad \text{for all } i \in \{4,5,7\},\\ \mu f_4 = \alpha _5 f_5 + \alpha _7 f_7, \quad \mu f_5 &= \alpha _4 f_4 + \alpha _5 f_5, \quad \mu f_7 = \alpha _4 f_4,\\ \nu g_4 = \alpha _5 g_5 + \alpha _7 g_7, \quad \nu g_5 &= \alpha _4 g_4 + \alpha _5 g_5, \quad \nu g_7 = \alpha _4 g_4. \end{align*}$$

The first three constraints say that the weights sum to $1$ and that $f$ and $g$ are unit eigenfunctions. The fourth constraint is from Lemma 3.7. The final two lines of constraints say that $f$ and $g$ are eigenfunctions for $\mu$ and $\nu$ respectively. Since these equations must be satisfied for any spread-extremal graphon, the solution to this optimization problem gives an upper bound on any spread-extremal graphon corresponding to case $4|57$. For each case we formulate a similar optimization problem in Appendix A.1.

First, if two distinct blocks of vertices have the same neighborhood, then without loss of generality we may assume that only one of them has positive weight. For example, see Figure 5: in case $123|567$, blocks $1$ and $2$ have the same neighborhood, and hence without loss of generality we may assume that only block $1$ has positive weight. Furthermore, in this case the resulting graphon could be considered as case $13|567$ or equivalently as case $14|567$; the graphons corresponding to these cases are isomorphic. Therefore cases $123|567$, $13|567$, and $14|567$ reduce to considering only case $14|567$.

Additionally, if there is no dominant vertex, then some pairs cases may correspond to isomorphic graphons and the optimization problems are equivalent up to flipping the sign of the eigenvector corresponding to $\nu$. For example, see Figure 6, in which cases $23|457$ and $24|567$ reduce to considering only a single one. However, because of how we choose to order the eigenfunction entries when setting up the constraints of the optimization problems, there are some examples of cases corresponding to isomorphic graphons that we solve as separate optimization problems. For example, the graphons corresponding to cases $1|24|7$ and $1|4|57$ are isomorphic, but we will consider them separate cases; see Figure 7.

Repeated applications of these three principles show that there are only $17$ distinct cases that we must consider. The details are straightforward to verify, see Lemma A.2.

The distinct cases that we must consider are the following, summarized in Figure 8.

$$\begin{align*} \mathcal{S}_{17}&\coloneq \left\{\begin{array}{r} 1|234|567, 1|24|567, 1|234|57, 1|4|567, 1|24|57, 1|234|7, 234|567, \\24|567, 4|567, 24|57, 1|567, 1|4|57, 1|2|47, 1|57, 4|57, 1|4|7, 1|7 \end{array} \right\}. \end{align*}$$

5.2. Interval arithmetic

Interval arithmetic is a computational technique which bounds errors that accumulate during computation. For convenience, let $\mathbb{R}^* \coloneq [-\infty , +\infty ]$ be the extended real line. To enhance order floating point arithmetic, we replace extended real numbers with unions of intervals which are guaranteed to contain them. Moreover, we extend the basic arithmetic operations $+, -, \times , \div$, and $\sqrt {}$ to operations on unions of intervals. This technique has real-world applications in the hard sciences, but has also been used in computer-assisted proofs. For two famous examples, we refer the interested reader to 15 for Hales’ proof of the Kepler Conjecture on optimal sphere-packing in $\mathbb{R}^2$, and to 31 for Warwick’s solution of Smale’s $14$th problem on the Lorenz attractor as a strange attractor.

As stated before, we consider extensions of the binary operations $+$, $-$, $\times$, and $\div$ as well as the unary operation $\sqrt {}$ defined on $\mathbb{R}$ to operations on unions of intervals of extended real numbers. For example if $[a,b], [c,d]\subseteq \mathbb{R}$, then we may use the following extensions of $+, -,$ and $\times$:

$$\begin{align*} [a,b] + [c,d] &= [a+c,b+d], \\ [a,b] - [c,d] &= [a-d,b-c], \text{and}\\ [a,b] \times [c,d] &= \left[ \min \{ac, ad, b c, b d\}, \max \{a c, a d, b c, b d\} \right]. \end{align*}$$

For $\div$, we must address the cases $0\in [c,d]$ and $0\notin [c,d]$. Here, we take the extension

$$\begin{align*} [a,b] \div [c,d] &= \left[ \min \bigg \{\frac{a}{c}, \frac{a}{d}, \frac{b}{c}, \frac{b}{d}\bigg \}, \max \bigg \{\frac{a}{c}, \frac{a}{d}, \frac{b}{c}, \frac{b}{d}\bigg \} \right], \end{align*}$$

where

$$\begin{align*} 1 \div [c,d] &= \left\{\begin{array}{rl} \left[ \min \{ c^{-1}, d^{-1} \}, \max \{ c^{-1}, d^{-1} \} \right], & 0\notin [c,d] \\\left[ d^{-1}, +\infty \right], & \text{c=0} \\\left[ -\infty , c^{-1} \right], & d = 0 \\\left[ -\infty ,\frac{1}{c} \right] \cup \left[ \frac{1}{d},+\infty \right], & c < 0 < d \end{array}\right. . \end{align*}$$

Additionally, we may let

$$\begin{align*} \sqrt {[a,b]} &= \left\{\begin{array}{rl} \emptyset , & b < 0\\\left[ \sqrt {\max \left\{ 0, a \right\}} , \sqrt {b} \right], & \text{otherwise} \end{array}\right. . \end{align*}$$

When endpoints of $[a,b]$ and $[c,d]$ include $-\infty$ or $+\infty$, the definitions above must be modified slightly in a natural way.

We use interval arithmetic to prove the strict upper bound $<2/\sqrt {3}$ for the maximum graphon spread claimed in Theorem 5.1, for any solutions to $15$ of the $17$ constrained optimization problems $\mathrm{SPR}_S$ stated in Lemma A.2. The constraints in each $\mathrm{SPR}_S$ allow us to derive equations for the variables $(\alpha _i,f_i,g_i)_{i\in S}$ in terms of each other, and $\mu$ and $\nu$. For the reader’s convenience, we relocate these formulas and their derivations to Appendix B.1. In the programs corresponding to each set $S\in \mathcal{S}_{17}$, we find two indices $i\in S\cap \{1,2,3,4\}$ and $j\in S\cap \{5,6,7\}$ such that for all $k\in S$, $\alpha _k$, $f_k$, and $g_k$ may be calculated, step-by-step, from $\alpha _i$, $\alpha _j$, $\mu$, and $\nu$. See Table 1 for each set $S\in \mathcal{S}_{17}$, organized by the chosen values of $i$ and $j$.

In the program corresponding to a set $S\in \mathcal{S}_{17}$, we search a carefully chosen set $\Omega \subseteq [0,1]^3\times [-1,0]$ for values of $(\alpha _i,\alpha _j,\mu ,\nu )$ which satisfy $\mathrm{SPR}_S$. We first divide $\Omega$ into a grid of “boxes”. Starting at depth $0$, we test each box $B$ for feasibility by assuming that $(\alpha _i,\alpha _j,\mu ,\nu )\in B$ and that $\mu -\nu \geq 2/\sqrt {3}$. Next, we calculate $\alpha _k$, $f_k$, and $g_k$ for all $k\in S$ in interval arithmetic using the formulas from Appendix B. When the calculation detects that a constraint of $\mathrm{SPR}_S$ is not satisfied, e.g., by showing that some $\alpha _k$, $f_k$, or $g_k$ lies in an empty interval, or by constraining $\sum _{i\in S}\alpha _i$ to a union of intervals which does not contain $1$, then the box is deemed infeasible. Otherwise, the box is split into two boxes of equal dimensions, with the dimension of the cut alternating cyclically.

For each $S\in \mathcal{S}_{17}$, the program $\mathrm{SPR}_S$ has $3$ norm constraints, $2|S|$ linear eigenvector constraints, $|S|$ elliptical constraints, $\binom{|S|}{2}$ inequality constraints, and $3|S|$ interval membership constraints. By using interval arithmetic, we have a computer-assisted proof of the following result.

Lemma 5.2.

Suppose $S\in \mathcal{S}_{17}\setminus \{\{1,7\}, \{4,5,7\}\}$. Then any solution to $\mathrm{SPR}_S$ attains a value strictly less than $2/\sqrt {3}$.

To better understand the role of interval arithmetic in our proof, consider Example 5.3.

Example 5.3.

Suppose $\mu ,\nu$, and $(\alpha _i,f_i,g_i)$ is a solution to $\mathrm{SPR}_{\{1,\dots ,7\}}$. We show that $(\alpha _3, \mu ,\nu )\notin [.7,.8]\times [.9,1]\times [-.2,-.1]$. By Proposition B.1, $\displaystyle {g_3^2 = \frac{\nu (\alpha _3 + 2 \mu )}{\alpha _3(\mu + \nu ) + 2 \mu \nu }}$. Using interval arithmetic,

$$\begin{align*} \nu (\alpha _3 + 2 \mu ) &= [-.2,-.1] \times \big ([.7,.8] + 2 \times [.9,1] \big ) \\ &= [-.2,-.1] \times [2.5,2.8] = [-.56,-.25], \text{ and } \\ \alpha _3(\mu + \nu ) + 2 \mu \nu &= [.7,.8]\times \big ([.9,1] + [-.2,-.1]\big ) + 2 \times [.9,1] \times [-.2,-.1] \\ &= [.7,.8] \times [.7,.9] + [1.8,2] \times [-.2,-.1] \\ &= [.49,.72] + [-.4,-.18] = [.09,.54]. \end{align*}$$

Thus

$$\begin{align*} g_3^2 &= \frac{ \nu (\alpha _3 + 2 \mu ) }{ \alpha _3(\mu + \nu ) + 2 \mu \nu } = [-.56,-.25] \div [.09,.54] = [-6.\overline{2},-.4\overline{629}]. \end{align*}$$

Since $g_3^2\geq 0$, we have a contradiction.

Example 5.3 illustrates a number of key elements. First, we note that through interval arithmetic, we are able to provably rule out the corresponding region. However, the resulting interval for the quantity $g_3^2$ is over fifty times bigger than any of the input intervals. This growth in the size of intervals is common, and so, in some regions, fairly small intervals for variables are needed to provably illustrate the absence of a solution. For this reason, using a computer to complete this procedure is ideal, as doing millions of calculations by hand would be untenable.

However, the use of a computer for interval arithmetic brings with it another issue. Computers have limited memory, and therefore cannot represent all numbers in $\mathbb{R}^*$. Instead, a computer can only store a finite subset of numbers, which we will denote by $F\subsetneq \mathbb{R}^*$. This set $F$ is not closed under the basic arithmetic operations, and so when some operation is performed and the resulting answer is not in $F$, some rounding procedure must be performed to choose an element of $F$ to approximate the exact answer. This issue is the cause of roundoff error in floating point arithmetic, and must be treated in order to use computer-based interval arithmetic as a proof.

PyInterval is one of many software packages designed to perform interval arithmetic in a manner which accounts for this crucial feature of floating point arithmetic. Given some $x \in \mathbb{R}^*$, let $fl_-(x)$ be the largest $y \in F$ satisfying $y \le x$, and $fl_+(x)$ be the smallest $y \in F$ satisfying $y \ge x$. Then, in order to maintain a mathematically accurate system of interval arithmetic on a computer, once an operation is performed to form a union of intervals $\bigcup _{i=1}^k[a_i, b_i]$, the computer forms a union of intervals containing $[fl_-(a_i),fl_+(b_i)]$ for all $1\leq i\leq k$. The programs which prove Lemma 5.2 can be found in 27.

5.3. Completing the proof of Theorem 5.1

Finally, we complete the second main result of this paper. We will need Lemma 5.4.

Lemma 5.4.

If $(\alpha _4,\alpha _5,\alpha _7)$ is a solution to $\mathrm{SPR}_{\{4,5,7\}}$, then $\alpha _7=0$.

We delay the proof of Lemma 5.4 to Appendix A because it is technical. We now proceed with the Proof of Theorem 5.1.

Proof of Theorem 5.1.

Let $W$ be a graphon such that $\mathrm{spr}(W) = \max _{U\in \mathcal{W}}\mathrm{spr}(U)$. By Lemma 5.2 and Lemma 5.4, $W$ is a $2\times 2$ stepgraphon. Let the weights of the parts be $\alpha _1$ and $1-\alpha _1$.

Thus, it suffices to demonstrate the uniqueness of the desired solution $\mu , \nu ,$ and $(\alpha _i,f_i,g_i)_{i\in \{1,7\}}$ to $\mathrm{SPR}_{\{1,7\}}$. Indeed, we first note that with

$$\begin{align*} N(\alpha _1) \coloneq \left[\begin{array}{ccc} \alpha _1 & 1-\alpha _1\\\alpha _1 & 0 \end{array}\right], \end{align*}$$

the quantities $\mu$ and $\nu$ are precisely the eigenvalues of the characteristic polynomial

$$\begin{align*} p(x) = x^2-\alpha _1x-\alpha _1(1-\alpha _1). \end{align*}$$

In particular,

$$\begin{align*} \mu &= \dfrac{ \alpha _1 + \sqrt {\alpha _1(4-3\alpha _1)} }{2} , \quad \nu = \dfrac{ \alpha _1 - \sqrt {\alpha _1(4-3\alpha _1)} }{2} , \end{align*}$$

and

$$\begin{align*} \mu -\nu &= \sqrt {\alpha _1(4-3\alpha _1)}. \end{align*}$$

Optimizing, it follows that $(\alpha _1, 1-\alpha _1) = (2/3, 1/3)$. Calculating the eigenfunctions and normalizing them gives that $\mu , \nu ,$ and their respective eigenfunctions match those from the statement of Theorem 5.1.

■

6. From graphons to graphs

In this section, we show that Theorem 5.1 implies Conjecture 1 for all $n$ sufficiently large; that is, the solution to the problem of maximizing the spread of a graphon implies the solution to the problem of maximizing the spread of a graph for sufficiently large $n$.

The outline for our argument is as follows. First, we define the spread-maximum graphon $W$ as in Theorem 5.1. Let $\{G_n\}$ be any sequence where each $G_n$ is a spread-maximum graph on $n$ vertices and denote by $\{W_n\}$ the corresponding sequence of graphons. We show that, after applying measure-preserving transformations to each $W_n$, the extreme eigenvalues and eigenvectors of each $W_n$ converge suitably to those of $W$. It follows for $n$ sufficiently large that except for $o(n)$ vertices, $G_n$ is a join of a clique of $2n/3$ vertices and an independent set of $n/3$ vertices (Lemma 6.2). Using results from Section 2, we precisely estimate the extreme eigenvector entries on this $o(n)$ set. Finally, Lemma 6.3 shows that the set of $o(n)$ exceptional vertices is actually empty, completing the proof.

Before proceeding with the proof, we state Corollary 6.1 of the Davis-Kahan theorem 10, stated for graphons.

Corollary 6.1.

Suppose $W,W':[0,1]^2\to [0,1]$ are graphons. Let $\mu$ be an eigenvalue of $W$ with $f$ a corresponding unit eigenfunction. Let $\{h_k\}$ be an orthonormal eigenbasis for $W'$ with corresponding eigenvalues $\{\mu _k'\}$. Suppose that $|\mu _k'-\mu | > \delta$ for all $k\neq 1$. Then

$$\begin{align*} \sqrt {1 - \langle h_1,f\rangle ^2} \leq \dfrac{\|A_{W'-W}f\|_2}{\delta }. \end{align*}$$

Before proving Theorem 1.1, we prove the following approximate result. For all nonnegative integers $n_1,n_2,n_3$, let $G(n_1,n_2,n_3) \coloneq (K_{n_1}\dot{\cup } K_{n_2}^c)\vee K_{n_3}^c$.

Lemma 6.2.

For all positive integers $n$, let $G_n$ denote a graph on $n$ vertices which maximizes spread. Then $G_n = G(n_1,n_2,n_3)$ for some nonnegative integers $n_1,n_2,n_3$ such that $n_1 = (2/3+o(1))n$, $n_2 = o(n)$, and $n_3 = (1/3+o(1))n$.

Proof.

Our argument outline is:

(1)

show that the eigenvectors for the spread-extremal graphs resemble the eigenfunctions of the spread-extremal graphon in an $L_2$ sense

(2)

show that with the exception of a small proportion of vertices, a spread-extremal graph is the join of a clique and an independent set

Let $\mathcal{P}\coloneq [0,2/3]$ and $\mathcal{N}\coloneq [0,1]\setminus \mathcal{P}$. By Theorem 5.1, the graphon $W$ which is the indicator function of the set $[0,1]^2\setminus \mathcal{N}^2$ maximizes spread. Denote by $\mu$ and $\nu$ its maximum and minimum eigenvalues, respectively. For every positive integer $n$, let $G_n$ denote a graph on $n$ vertices which maximizes spread, let $W_n$ be any stepgraphon corresponding to $G_n$, and let $\mu _n$ and $\nu _n$ denote the maximum and minimum eigenvalues of $W_n$, respectively. By Theorems 3.1 and 5.1, and compactness of $\hat{\mathcal{W}}$,

$$\begin{align*} \max \left\{ |\mu -\mu _n|, |\nu -\nu _n|, \delta _\square (W, W_n) \right\}\to 0. \end{align*}$$

Moreover, we may apply measure-preserving transformations to each $W_n$ so that without loss of generality, $\|W-W_n\|_\square \to 0$. As in Theorem 5.1, let $f$ and $g$ be unit eigenfunctions that take values $f_1,f_2, g_1, g_2$. Furthermore, let $\varphi _n$ be a nonnegative unit $\mu _n$-eigenfunction for $W_n$ and let $\psi _n$ be a $\nu _n$-eigenfunction for $W_n$.

We show that without loss of generality, $\varphi _n\to f$ and $\psi _n\to g$ in the $L_2$ sense. Since $\mu$ is the only positive eigenvalue of $W$ and it has multiplicity $1$, taking $\delta \coloneq \mu /2$, Corollary 6.1 implies that

$$\begin{align*} 1-\langle f,\varphi _n\rangle ^2 &\leq \dfrac{4\|A_{W-W_n}f\|_2^2}{\mu ^2} \\ &= \dfrac{4}{\mu ^2} \cdot \left\langle A_{W-W_n}f, A_{W-W_n}f \right\rangle \\ &\leq \dfrac{4}{\mu ^2} \cdot \| A_{W-W_n}f \|_1 \cdot \| A_{W-W_n}f \|_\infty \\ &\leq \dfrac{4}{\mu ^2} \cdot \left( \|A_{W-W_n}\|_{\infty \to 1}\|f\|_\infty \right) \cdot \|f\|_\infty \\ &\leq \dfrac{ 16\|W-W_n\|_\square \cdot \|f\|_\infty ^2}{\mu ^2}, \end{align*}$$

where the last inequality follows from Lemma 8.11 of 18. Since $\|f\|_\infty \leq 1/\mu$, this proves the first claim. The second claim follows by replacing $f$ with $g$, and $\mu$ with $|\nu |$.

Note.

For the remainder of the proof, we will introduce quantities $\varepsilon _i > 0$ in lieu of writing complicated expressions explicitly. When we introduce a new $\varepsilon _i$, we will remark that given $\varepsilon _0,\dots ,\varepsilon _{i-1}$ sufficiently small, $\varepsilon _i$ can be made sufficiently small enough to meet some other conditions.

Let $\varepsilon _0 > 0$ and for all $n\geq 1$, define

$$\begin{align*} \mathcal{P}_n &\coloneq \{ x\in [0,1] : |\varphi _n(x) - f_1| < \varepsilon _0 \text{ and } |\psi _n(x)-g_1| < \varepsilon _0 \}, \\ \mathcal{N}_n &\coloneq \{ x\in [0,1] : |\varphi _n(x) - f_2| < \varepsilon _0 \text{ and } |\psi _n(x)-g_2| < \varepsilon _0 \}, \text{ and } \\ \mathcal{E}_n &\coloneq [0,1]\setminus (\mathcal{P}_n\cup \mathcal{N}_n). \end{align*}$$

Since

$$\begin{align*} \int _{|\varphi _n-f|\geq \varepsilon _0} |\varphi _n-f|^2 \, dx &\leq \int _{} |\varphi _n-f|^2 \, dx \to 0, \text{ and }\\ \int _{|\psi _n-g|\geq \varepsilon _0} |\psi _n-g|^2 \, dx &\leq \int _{} |\psi _n-g|^2 \, dx \to 0, \end{align*}$$

it follows that

$$\begin{align*} \max \left\{ m(\mathcal{P}_n\setminus \mathcal{P}), m(\mathcal{N}_n\setminus \mathcal{N}), m(\mathcal{E}_n) \right\} \to 0. \end{align*}$$

For all $u\in V(G_n)$, let $S_u$ be the subinterval of $[0,1]$ corresponding to $u$ in $W_n$, and denote by $\varphi _u$ and $\psi _u$ the constant values of $\varphi _n$ on $S_u$. For convenience, we define the following discrete analogues of $\mathcal{P}_n, \mathcal{N}_n, \mathcal{E}_n$:

$$\begin{align*} P_n &\coloneq \{ u\in V(G_n) : |\varphi _u - f_1| < \varepsilon _0 \text{ and } |\psi _u-g_1| < \varepsilon _0 \}, \\ N_n &\coloneq \{ u\in V(G_n) : |\varphi _u - f_2| < \varepsilon _0 \text{ and } |\psi _u-g_2| < \varepsilon _0 \}, \text{ and } \\ E_n &\coloneq V(G_n) \setminus (P_n\cup N_n). \end{align*}$$

Let $\varepsilon _1>0$. By Lemma 2.4 and using the fact that $\mu _n\to \mu$ and $\nu _n\to \nu$,

$$\begin{align} \left| \mu \varphi _u^2 - \nu \psi _u^2 - (\mu -\nu ) \right| &< \varepsilon _1 \quad \text{ for all }u\in V(G_n) {\tag{5}} \end{align}$$

for all $n$ sufficiently large. Let $\varepsilon _0'>0$. We next need Claim I, which says that the eigenvector entries of the exceptional vertices behave as if they have neighborhood $N_n$.

Claim I.

Suppose $\varepsilon _0$ is sufficiently small and $n$ is sufficiently large in terms of $\varepsilon _0'$. Then for all $v\in E_n$,

$$\begin{align} \max \left\{ \left| \varphi _v - \dfrac{f_2}{3\mu } \right|, \left| \psi _v - \dfrac{g_2}{3\nu } \right| \right\} < \varepsilon _0'. {\tag{6}} \end{align}$$

Indeed, suppose $v \in E_n$ and let

$$\begin{align*} U_n \coloneq \{w\in V(G_n) : vw\in E(G_n)\} \quad \text{ and }\quad \mathcal{U}_n \coloneq \bigcup _{w\in U_n} S_w. \end{align*}$$

We take two cases, depending on the sign of $\psi _v$.

Case A.

$\psi _v \geq 0$.

Recall that $f_2 > 0 > g_2$. Furthermore, $\varphi _v \geq 0$ and by assumption, $\psi _v\geq 0$. It follows that for all $n$ sufficiently large, $f_2\varphi _v - g_2\psi _v > 0$, so by Lemma 2.1, $N_n\subseteq U_n$. Since $\varphi _n$ is a $\mu _n$-eigenfunction for $W_n$,

$$\begin{align*} \mu _n \varphi _v &= \int _{y\in [0,1]}W_n(x,y)\varphi _n(y) \, dy \\ &= \int _{y\in \mathcal{P}_n\cap \mathcal{U}_n}\varphi _n(y) \, dy + \int _{y\in \mathcal{N}_n}\varphi _n(y) \, dy + \int _{y\in \mathcal{E}_n\cap \mathcal{U}_n}\varphi _n(y) \, dy. \end{align*}$$

Similarly,

$$\begin{align*} \nu _n \psi _v &= \int _{y\in [0,1]}K_n(x,y)\psi _n(y) \, dy \\ &= \int _{y\in \mathcal{P}_n\cap \mathcal{U}_n}\psi _n(y) \, dy + \int _{y\in \mathcal{N}_n}\psi _n(y) \, dy + \int _{y\in \mathcal{E}_n\cap \mathcal{U}_n}\psi _n(y) \, dy. \end{align*}$$

Let $\rho _n \coloneq m(\mathcal{P}_n\cap \mathcal{U}_n)$. Note that for all $\varepsilon _2 > 0$, as long as $n$ is sufficiently large and $\varepsilon _1$ is sufficiently small, then

$$\begin{align} \max \left\{ \left| \varphi _v-\dfrac{3\rho _n f_1 + f_2}{3\mu } \right| , \left| \psi _v-\dfrac{3\rho _n g_1 + g_2}{3\nu } \right| \right\} < \varepsilon _2. {\tag{7}} \end{align}$$

Let $\varepsilon _3 > 0$. By Equations 5 and 7 and with $\varepsilon _1,\varepsilon _2$ sufficiently small,

$$\begin{align*} \left| \mu \cdot \left( \dfrac{3\rho _n f_1 + f_2}{3\mu } \right)^2 -\nu \cdot \left( \dfrac{3\rho _n g_1 + g_2}{3\nu } \right)^2 - (\mu -\nu ) \right| < \varepsilon _3. \end{align*}$$

Substituting the values of $f_1,f_2, g_1,g_2$ from Theorem 5.1 and simplifying, it follows that

$$\begin{align*} \left| \dfrac{\sqrt {3}}{2} \cdot \rho _n(3\rho _n-2) \right| < \varepsilon _3. \end{align*}$$

Let $\varepsilon _4 > 0$. It follows that if $n$ is sufficiently large and $\varepsilon _3$ is sufficiently small, then

$$\begin{align} \min \left\{ \rho _n, |2/3-\rho _n| \right\} < \varepsilon _4. {\tag{8}} \end{align}$$

Combining Equations 7 and 8, it follows that with $\varepsilon _2,\varepsilon _4$ sufficiently small, then

$$\begin{align*} \max \left\{ \left| \varphi _v - \dfrac{f_2}{3\mu } \right|, \left| \psi _v - \dfrac{g_2}{3\mu } \right| \right\} &< \varepsilon _0', \text{ or } \\ \max \left\{ \left| \varphi _v - \dfrac{2f_1 + f_2}{3\mu } \right|, \left| \psi _v - \dfrac{2g_1 + g_2}{3\mu } \right| \right\} &< \varepsilon _0'. \end{align*}$$

Note that

$$\begin{align*} f_1 &= \dfrac{2f_1 + f_2}{3\mu } \quad \text{ and }\quad g_1 = \dfrac{2g_1 + g_2}{3\nu }. \end{align*}$$

Since $v\in E_n$, the second inequality does not hold, which completes the proof of the desired claim.

Case B.

$\psi _v < 0$.

Recall that $f_1 > g_1 > 0$. Furthermore, $\varphi _v \geq 0$ and by assumption, $\psi _v < 0$. It follows that for all $n$ sufficiently large, $f_1\varphi _v - g_1\psi _v > 0$, so by Lemma 2.1, $P_n\subseteq U_n$. Since $\varphi _n$ is a $\mu _n$-eigenfunction for $W_n$,

$$\begin{align*} \mu _n \varphi _v &= \int _{y\in [0,1]}W_n(x,y)\varphi _n(y) \, dy \\ &= \int _{y\in \mathcal{N}_n\cap \mathcal{U}_n}\varphi _n(y) \, dy + \int _{y\in \mathcal{P}_n}\varphi _n(y) \, dy + \int _{y\in \mathcal{E}_n\cap \mathcal{U}_n}\varphi _n(y) \, dy. \end{align*}$$

Similarly,

$$\begin{align*} \nu _n \psi _v &= \int _{y\in [0,1]}W_n(x,y)\psi _n(y) \, dy \\ &= \int _{y\in \mathcal{N}_n\cap \mathcal{U}_n}\psi _n(y) \, dy + \int _{y\in \mathcal{P}_n}\psi _n(y) \, dy + \int _{y\in \mathcal{E}_n\cap \mathcal{U}_n}\psi _n(y) \, dy. \end{align*}$$

Let $\rho _n \coloneq m(\mathcal{N}_n\cap \mathcal{U}_n)$. Note that for all $\varepsilon _5 > 0$, as long as $n$ is sufficiently large and $\varepsilon _1$ is sufficiently small, then

$$\begin{align} \max \left\{ \left| \varphi _v-\dfrac{2f_1 + 3\rho _n f_2}{3\mu } \right| , \left| \psi _v-\dfrac{2g_1 + 3\rho _n g_2}{3\nu } \right| \right\} < \varepsilon _5. {\tag{9}} \end{align}$$ Let $\varepsilon _6 > 0$. By Equations 5 and 9 and with $\varepsilon _1,\varepsilon _2$ sufficiently small,

$$\begin{align*} \left| \mu \cdot \left( \dfrac{2f_1 + 3\rho _n f_2}{3\mu } \right)^2 -\nu \cdot \left( \dfrac{2g_1 + 3\rho _n g_2}{3\nu } \right)^2 - (\mu -\nu ) \right| < \varepsilon _6. \end{align*}$$

Substituting the values of $f_1,f_2, g_1,g_2$ from Theorem 5.1 and simplifying, it follows that

$$\begin{align*} \left| 2\sqrt {3} \cdot \rho _n(3\rho _n-1) \right| < \varepsilon _6. \end{align*}$$

Let $\varepsilon _7 > 0$. It follows that if $n$ is sufficiently large and $\varepsilon _6$ is sufficiently small, then

$$\begin{align} \min \left\{ \rho _n, |1/3-\rho _n| \right\} < \varepsilon _7. {\tag{10}} \end{align}$$

Combining Equations 7 and 10, it follows that with $\varepsilon _2,\varepsilon _4$ sufficiently small, then

$$\begin{align*} \max \left\{ \left| \varphi _v - \dfrac{2f_1}{3\mu } \right|, \left| \psi _v - \dfrac{2g_1}{3\mu } \right| \right\} &< \varepsilon _0', \text{ or } \\ \max \left\{ \left| \varphi _v - \dfrac{2f_1 + f_2}{3\mu } \right|, \left| \psi _v - \dfrac{2g_1 + g_2}{3\mu } \right| \right\} &< \varepsilon _0'. \end{align*}$$

Again, note that

$$\begin{align*} f_1 &= \dfrac{2f_1 + f_2}{3\mu } \quad \text{ and }\quad g_1 = \dfrac{2g_1 + g_2}{3\nu }. \end{align*}$$

Since $v\in E_n$, the second inequality does not hold.

Similarly, note that

$$\begin{align*} f_2 &= \dfrac{2f_1}{3\mu } \quad \text{ and }\quad g_2 = \dfrac{2g_1}{3\nu }. \end{align*}$$

Since $v\in E_n$, the first inequality does not hold, a contradiction. So the desired claim holds.

We now complete the proof of Lemma 6.3 by showing that for all $n$ sufficiently large, $G_n$ is the join of an independent set $N_n$ with a disjoint union of a clique $P_n$ and an independent set $E_n$.

As above, we let $\varepsilon _0,\varepsilon _0'>0$ be arbitrary. By definition of $P_n$ and $N_n$ and by Equation 6 from Claim I, then for all $n$ sufficiently large,

$$\begin{align*} \max \left\{ \left| \varphi _v - f_1 \right|, \left| \psi _v - g_1 \right| \right\} &< \varepsilon _0 &\text{ for all }v\in P_n, \\ \max \left\{ \left| \varphi _v - \dfrac{f_2}{3\mu } \right|, \left| \psi _v - \dfrac{g_2}{3\nu } \right| \right\} &< \varepsilon _0' &\text{ for all }v\in E_n, \\ \max \left\{ \left| \varphi _v - f_2 \right|, \left| \psi _v - g_2 \right| \right\} &< \varepsilon _0 &\text{ for all }v\in N_n. \end{align*}$$

With rows and columns respectively corresponding to the vertex sets $P_n$, $E_n$, and $N_n$, we note the following inequalities: Indeed, note the following inequalities:

$$\begin{align*} \begin{array}{c|c| |c} f_1^2 > g_1^2 & f_1\cdot \dfrac{f_2}{3\mu } < g_1\cdot \dfrac{g_2}{3\nu } & f_1f_2 > g_1g_2\\\hline & \left(\dfrac{f_2}{3\mu }\right)^2 < \left(\dfrac{g_2}{3\nu }\right)^2 & \dfrac{f_2}{3\mu }\cdot f_2 > \dfrac{g_2}{3\nu }\\\hline \hline && f_2^2 < g_2^2 \end{array} \quad . \end{align*}$$

Let $\varepsilon _0, \varepsilon _0'$ be sufficiently small. Then for all $n$ sufficiently large and for all $u,v\in V(G_n)$, then $\varphi _u\varphi _v-\psi _u\psi _v < 0$ if and only if $u,v\in E_n$, $u,v\in N_n$, or $(u,v)\in (P_n\times E_n)\cup (E_n\times P_n)$. By Lemma 2.1, since $m(P_n) \to 2/3$ and $m(N_n) \to 1/3$, the proof is complete.

■

We have now shown that the spread-extremal graph is of the form $(K_{n_1}\dot{\cup } K_{n_2}^c)\vee K_{n_3}^c$ where $n_2 = o(n)$. Lemma 6.3 refines this to show that actually $n_2 = 0$.

Lemma 6.3.

For all nonnegative integers $n_1,n_2,n_3$, let $G(n_1, n_2, n_3) \coloneq (K_{n_1}\cup K_{n_2}^c)\vee K_{n_3}^c$. Then for all $n$ sufficiently large, the following holds. If $\mathrm{spr}(G(n_1,n_2,n_3))$ is maximized subject to the constraint $n_1+n_2+n_3 = n$ and $n_2 = o(n)$, then $n_2 = 0$.

Proof outline. We aim to maximize the spread of $G(n_1, n_2, n_3)$ subject to $n_2 = o(n)$. The spread of $G(n_1, n_2, n_3)$ is the same as the spread of the quotient matrix

$$\begin{equation*} Q_n = \begin{bmatrix} n_1 - 1 & 0 & n_3\\ 0 & 0 & n_3 \\ n_1 & n_2 & 0 \end{bmatrix}. \end{equation*}$$

We reparametrize with parameters $\varepsilon _1$ and $\varepsilon _2$ representing how far away $n_1$ and $n_3$ are proportionally from $\frac{2n}{3}$ and $\frac{n}{3}$, respectively. Namely, $\varepsilon _1 = \frac{2}{3} - \frac{n_1}{n}$ and $\varepsilon _2 = \frac{1}{3} - \frac{n_3}{n}$. Then $\varepsilon _1 + \varepsilon _2 = \frac{n_2}{n}$. Hence maximizing the spread of $G(n_1,n_2,n_3)$ subject to $n_2 = o(n)$ is equivalent to maximizing the spread of the matrix

$$\begin{equation*} n\begin{bmatrix} \frac{2}{3} - \varepsilon _1 - \frac{1}{n} & 0 & \frac{1}{3} - \varepsilon _2 \\ 0 & 0 & \frac{1}{3} - \varepsilon _2 \\ \frac{2}{3} - \varepsilon _1 & \varepsilon _1 + \varepsilon _2 & 0 \end{bmatrix} \end{equation*}$$

subject to the constraint that $\frac{2}{3}-\varepsilon _1$ and $\frac{1}{3}-\varepsilon _2$ are nonnegative integer multiples of $\frac{1}{n}$ and $\varepsilon _1+\varepsilon _2 = o(1)$. In order to utilize calculus, we instead solve a continuous relaxation of the optimization problem.

As such, consider the following matrix.

$$\begin{align*} M_z(\varepsilon _1,\varepsilon _2) \coloneq \left[\begin{array}{ccc} \dfrac{2}{3}-\varepsilon _1-z & 0 & \dfrac{1}{3}-\varepsilon _2\\0 & 0 & \dfrac{1}{3}-\varepsilon _2\\\dfrac{2}{3}-\varepsilon _1 & \varepsilon _1+\varepsilon _2 & 0 \end{array}\right] . \end{align*}$$

Since $M_z(\varepsilon _1,\varepsilon _2)$ is diagonalizable, we may let $S_z(\varepsilon _1,\varepsilon _2)$ be the difference between the maximum and minimum eigenvalues of $M_z(\varepsilon _1,\varepsilon _2)$. We consider the optimization problem $\mathcal{P}_{z,C}$ defined for all $z\in \mathbb{R}$ and all $C>0$ such that $|z|$ and $C$ are sufficiently small, by

$$\begin{align*} (\mathcal{P}_{z,C}): \left\{\begin{array}{rl} \max & S_z(\varepsilon _1,\varepsilon _2)\\\text{s.t}. & \varepsilon _1,\varepsilon _2\in [-C,C]. \end{array}\right. \end{align*}$$

We show that as long as $C$ and $|z|$ are sufficiently small, then the optimum of $\mathcal{P}_{z,C}$ is attained by

$$\begin{align*} (\varepsilon _1, \varepsilon _2) &= \left( (1+o(z))\cdot \dfrac{7z}{30}, (1+o(z))\cdot \dfrac{-z}{3} \right). \end{align*}$$

Moreover we show that in the feasible region of $\mathcal{P}_{z,C}$, $S_{z,C}(\varepsilon _1,\varepsilon _2)$ is concave-down in $(\varepsilon _1,\varepsilon _2)$. We return to the original problem by imposing the constraint that $\frac{2}{3}-\varepsilon _1$ and $\frac{1}{3}-\varepsilon _2$ are multiples of $\frac{1}{n}$. Together these two observations complete the proof of the lemma. Under these added constraints, the optimum is obtained when

$$\begin{align*} (\varepsilon _1, \varepsilon _2) &= \left\{\begin{array}{rl} (0,0), & n\equiv 0 \pmod {3}\\(2/3,-2/3), & n\equiv 1 \pmod {3}\\(1/3,-1/3), & n\equiv 2 \pmod {3} \end{array}\right. . \end{align*}$$

Since the details are straightforward but tedious calculus, we delay this part of the proof to Section A.3.

We may now complete the proof of Theorem 1.1.

Proof of Theorem 1.1.

Suppose $G$ is a graph on $n$ vertices which maximizes spread. By Lemma 6.2, $G = (K_{n_1}\dot{\cup } K_{n_2}^c)\vee K_{n_3}^c$ for some nonnegative integers $n_1,n_2,n_3$ such that $n_1+n_2+n_3 = n$ where

$$\begin{align*} (n_1,n_2,n_3) &= \left( \left( \dfrac{2}{3}+o(1) \right), o(n), \left( \dfrac{1}{3}+o(1) \right) \cdot n \right). \end{align*}$$

By Lemma 6.3, if $n$ is sufficiently large, then $n_2 = 0$. To complete the proof of the main result, it is sufficient to find the unique maximum of $\mathrm{spr}( K_{n_1}\vee K_{n_2}^c )$, subject to the constraint that $n_1+n_2 = n$. This is determined in 13 to be the join of a clique on $\lfloor \frac{2n}{3}\rfloor$ and an independent set on $\lceil \frac{n}{3} \rceil$ vertices. The interested reader can prove that $n_1$ is the nearest integer to $(2n-1)/3$ by considering the spread of the quotient matrix

$$\begin{align*} \left[\begin{array}{cc} n_1-1 & n_2\\n_1 & 0 \end{array}\right] \end{align*}$$

and optimizing the choice of $n_1$.

■

7. The Bipartite Spread Conjecture

In 13, the authors investigated the structure of graphs that maximize spread over all graphs with a fixed number of vertices $n$ and edges $m$. In particular, they proved the upper bound

$$\begin{equation} s(G) \le \lambda _1 + \sqrt {2 m - \lambda ^2_1} \le 2 \sqrt {m}, {\tag{11}} \end{equation}$$

and noted that equality holds throughout if and only if $G$ is the union of isolated vertices and $K_{p,q}$, for some $p+q \le n$ satisfying $m=pq$ 13, Theorem 1.5. This led the authors to make Conjecture 2, namely, that if $G$ has $n$ vertices, $m \le \lfloor n^2/4 \rfloor$ edges, and spread $s(n,m)$, then $G$ is bipartite 13, Conjecture 1.4. Recall that $s(n,m)$ is the maximum spread over all graphs with $n$ vertices and $m$ edges, and $s_b(n,m)$, $m \le \lfloor n^2/4 \rfloor$, is the maximum spread over all bipartite graphs with $n$ vertices and $m$ edges. This conjecture can be equivalently stated as $s(n,m)=s_b(n,m)$ for all $n \in \mathbb{N}$ and $m \le \lfloor n^2/4 \rfloor$. In this section, we prove an asymptotic form of this conjecture and provide an infinite family of counterexamples to the exact conjecture, which verifies that the error in our asymptotic result is of the correct order of magnitude (Theorem 1.2).

To compute the spread of certain graphs explicitly, we make use of the theory of equitable partitions. In particular, we note that if $\phi$ is an automorphism of $G$, then the quotient matrix of $A(G)$ with respect to $\phi$, denoted by $A_\phi$, satisfies $\Lambda (A_\phi ) \subset \Lambda (A)$, and therefore $s(G)$ is at least the spread of $A_\phi$ (for details, see 9, Section 2.3). Additionally, we require two propositions, one regarding the largest spectral radius of subgraphs of $K_{p,q}$ of a given size, and another regarding the largest gap between sizes that correspond to a complete bipartite graph of order at most $n$.

Let $K_{p,q}^m$, $0 \le pq-m <\min \{p,q\}$, be the subgraph of $K_{p,q}$ resulting from removing $pq-m$ edges all incident to some vertex in the larger side of the bipartition (if $p=q$, the vertex can be from either set). In 17, the authors proved the following result.

Proposition 7.1.

If $0 \le pq-m <\min \{p,q\}$, then $K_{p,q}^m$ maximizes $\lambda _1$ over all subgraphs of $K_{p,q}$ of size $m$.

We also require estimates regarding the longest sequence of consecutive sizes $m < \lfloor n^2/4\rfloor$ for which there does not exist a complete bipartite graph on at most $n$ vertices and exactly $m$ edges. As pointed out by 4, the result follows quickly by induction. However, for completeness, we include a brief proof.

Proposition 7.2.

The length of the longest sequence of consecutive sizes $m < \lfloor n^2/4\rfloor$ for which there does not exist a complete bipartite graph on at most $n$ vertices and exactly $m$ edges is zero for $n \le 4$ and at most $\sqrt {2n-1}-1$ for $n \ge 5$.

Proof.

We proceed by induction. By inspection, for every $n \le 4$, $m \le \lfloor n^2/4 \rfloor$, there exists a complete bipartite graph of size $m$ and order at most $n$, and so the length of the longest sequence is trivially zero for $n \le 4$. When $n =m = 5$, there is no complete bipartite graph of order at most five with exactly five edges. This is the only such instance for $n =5$, and so the length of the longest sequence for $n = 5$ is one.

Now, suppose that the statement holds for graphs of order at most $n-1$, for some $n > 5$. We aim to show the statement for graphs of order at most $n$. By our inductive hypothesis, it suffices to consider only sizes $m \ge \lfloor (n-1)^2/4 \rfloor$ and complete bipartite graphs on $n$ vertices. We have

$$\begin{equation*} \left( \frac{n}{2} + k \right)\left( \frac{n}{2} - k \right) \ge \frac{(n-1)^2}{4} \qquad \text{ for} \quad |k| \le \frac{\sqrt {2n-1}}{2}. \end{equation*}$$

When $1 \le k \le \sqrt {2n-1}/2$, the difference between the sizes of $K_{n/2+k-1,n/2-k+1}$ and $K_{n/2+k,n/2-k}$ is at most

$$\begin{align*} \big | E\big (K_{\frac{n}{2}+k-1,\frac{n}{2}-k+1}\big )\big | - \big | E\big (K_{\frac{n}{2}+k,\frac{n}{2}-k}\big )\big | &=2k-1 \le \sqrt {2n-1} -1. \end{align*}$$

Let $k^*$ be the largest value of $k$ satisfying $k \le \sqrt {2n-1}/2$ and $n/2 + k \in \mathbb{N}$. Then

$$\begin{align*} \big | E\big (K_{\frac{n}{2}+k^*,\frac{n}{2}-k^*}\big )\big | &< \left(\frac{n}{2} + \frac{\sqrt {2n-1}}{2} -1 \right)\left(\frac{n}{2} - \frac{\sqrt {2n-1}}{2} +1 \right) \\ &= \sqrt {2n-1} + \frac{(n-1)^2}{4} - 1, \end{align*}$$

and the difference between the sizes of $K_{n/2+k^*,n/2-k^*}$ and $K_{\lceil \frac{n-1}{2}\rceil ,\lfloor \frac{n-1}{2}\rfloor }$ is at most

$$\begin{align*} \big | E\big (K_{\frac{n}{2}+k^*,\frac{n}{2}-k^*}\big )\big | - \big | E\big (K_{\lceil \frac{n-1}{2}\rceil ,\lfloor \frac{n-1}{2}\rfloor }\big )\big | &< \sqrt {2n-1} + \frac{(n-1)^2}{4} -\left\lfloor \frac{(n-1)^2}{4} \right\rfloor - 1 \\ &< \sqrt {2n-1}. \end{align*}$$

Combining these two estimates completes our inductive step, and the proof.

■

We are now prepared to prove an asymptotic version of 13, Conjecture 1.4, and provide an infinite class of counterexamples that illustrates that the asymptotic version under consideration is the tightest version of this conjecture possible.

Theorem 7.3 (Restatement of Theorems 1.2 and 1.3).

For all $n,m \in \mathbb{N}$ satisfying $m \le \lfloor n^2/4\rfloor$,

$$\begin{equation} s(n,m) - s_b(n,m) \le \frac{1+16 m^{-3/4}}{m^{3/4}} s(n,m). {\tag{12}} \end{equation}$$

In addition, for any $\varepsilon >0$, there exists some $n_\varepsilon$ such that

$$\begin{equation} s(n,m) - s_b(n,m) \ge \frac{1-\varepsilon }{m^{3/4}} s(n,m) {\tag{13}} \end{equation}$$

for all $n\ge n_\varepsilon$ and some $m \le \lfloor n^2/4\rfloor$ depending on $n$.

Proof.

The main idea of the proof is as follows. To obtain Inequality 12 (the upper bound on $s(n,m) - s_b(n,m)$), we upper bound $s(n,m)$ by $2 \sqrt {m}$ using Inequality 11, and we lower bound $s_b(n,m)$ by the spread of some specific bipartite graph. To obtain Inequality 13 (the lower bound on $s(n,m) - s_b(n,m)$) for a specific $n$ and $m$, we explicitly compute $s_b(n,m)$ using Proposition 7.1, and lower bound $s(n,m)$ by the spread of some specific non-bipartite graph.

First, we analyze the spread of $K_{p,q}^m$, $0 < pq-m <q \le p$, a quantity that will be used in the proofs of both Inequalities 12 and 13. Let us denote the vertices in the bipartition of $K_{p,q}^m$ by $u_1,\dots ,u_p$ and $v_1,\dots ,v_{q}$, and suppose without loss of generality that $u_1$ is not adjacent to $v_1,\dots ,v_{pq-m}$. Then

$$\begin{equation*} \phi = (u_1)(u_2,\dots ,u_p)(v_1,\dots ,v_{pq-m})(v_{pq-m+1},\dots ,v_{q}) \end{equation*}$$

is an automorphism of $K^m_{p,q}$. The corresponding quotient matrix is given by

$$\begin{equation*} A_\phi = \begin{pmatrix} 0 & 0 & 0 & m-(p-1)q \\ 0 & 0 & pq-m & m-(p-1)q \\ 0 & p-1 & 0 & 0 \\ 1 & p-1 & 0 & 0 \end{pmatrix}, \end{equation*}$$

and has characteristic polynomial

$$\begin{equation*} Q(p,q,m) = \det [A_\phi - \lambda I] = \lambda ^4 -m \lambda ^2 + (p-1)(m-(p-1)q)(pq-m), \end{equation*}$$

and, therefore, by the Perron-Frobenius Theorem,

$$\begin{equation} s\left(K^m_{p,q}\right) = 2 \left( \frac{m + \sqrt {m^2-4(p-1)(m-(p-1)q)(pq-m)}}{2} \right)^{1/2}. {\tag{14}} \end{equation}$$

We are now prepared to prove Inequality 12 (the upper bound). For some fixed $n$ and $m\le \lfloor n^2/4 \rfloor$, let $m = pq -r$, where $p,q,r \in \mathbb{N}$, $p+q \le n$, and $r$ is as small as possible. If $r = 0$, then by 13, Theorem 1.5 (described above), $s(n,m) = s_b(n,m)$, and we are done. Otherwise, we note that $0<r < \min \{p,q\}$, and so Equation 14 is applicable (in fact, by Proposition 7.2, $r = O(\sqrt {n})$). Using the upper bound $s(n,m) \le 2 \sqrt {m}$ and Equation 14, we have

$$\begin{equation} \frac{s(n,pq-r)-s\left(K^{m}_{p,q}\right)}{s(n,pq-r)} \le 1 - \left(\frac{1}{2}+\frac{1}{2} \sqrt {1-\frac{4(p-1)(q-r) r}{(pq-r)^2}} \right)^{1/2}. {\tag{15}} \end{equation}$$

To upper bound $r$, we use Proposition 7.2 with $n'=\lceil 2 \sqrt {m}\rceil \le n$ and $m$. This implies that

$$\begin{equation*} r \le \sqrt {2 \lceil 2 \sqrt {m}\rceil -1} -1 < \sqrt {2 ( 2 \sqrt {m}+1) -1} -1 = \sqrt { 4 \sqrt {m} +1}-1 \le 2 m^{1/4}. \end{equation*}$$

Recall that $\sqrt {1-x} \ge 1 - x/2 - x^2/2$ for all $x \in [0,1]$, and so

$$\begin{align*} 1 - \big (\tfrac{1}{2} + \tfrac{1}{2} \sqrt {1-x} \big )^{1/2} &\le 1 - \big ( \tfrac{1}{2} + \tfrac{1}{2} (1 - \tfrac{1}{2}x - \tfrac{1}{2}x^2) \big )^{1/2} = 1 - \big (1 - \tfrac{1}{4} (x + x^2) \big )^{1/2} \\ &\le 1 - \big (1 - \tfrac{1}{8}(x + x^2) - \tfrac{1}{32}(x + x^2)^2 \big ) \\ &\le \tfrac{1}{8} x + \tfrac{1}{4} x^2 \end{align*}$$

for $x \in [0,1]$. To simplify Inequality 15, we observe that

$$\begin{equation*} \frac{4(p-1)(q-r)r}{(pq-r)^2} \le \frac{4r}{m} \le \frac{8}{m^{3/4}}. \end{equation*}$$

Therefore,

$$\begin{equation*} \frac{s(n,pq-r)-s\left(K^{m}_{p,q}\right)}{s(n,pq-r)} \le \frac{1}{m^{3/4}}+ \frac{16}{m^{3/2}}. \end{equation*}$$

This completes the proof of Inequality 12 (the upper bound).

Finally, we proceed with the proof of Inequality 13 (the lower bound). Let us fix some $0<\varepsilon <1$, and consider some sufficiently large $n$. Let $m = (n/2+k)(n/2-k)+1$, where $k$ is the smallest number satisfying $n/2 + k \in \mathbb{N}$ and $\hat{\varepsilon }\coloneq 1 - 2k^2/n < \varepsilon /2$ (here we require $n = \Omega (1/\varepsilon ^2)$). Denote the vertices in the bipartition of $K_{n/2+k,n/2-k}$ by $u_1,\dots ,u_{n/2+k}$ and $v_1,\dots ,v_{n/2-k}$, and consider the graph $K^+_{n/2+k,n/2-k}\coloneq K_{n/2+k,n/2-k} \cup \{(v_1,v_2)\}$ resulting from adding one edge to $K_{n/2+k,n/2-k}$ between two vertices in the smaller side of the bipartition. Then

$$\begin{equation*} \phi = (u_1 ,\dots ,u_{n/2+k})(v_1, v_2)(v_3,\dots ,v_{n/2-k}) \end{equation*}$$

is an automorphism of $K^+_{n/2+k,n/2-k}$, and

$$\begin{equation*} A_\phi = \begin{pmatrix} 0 & 2 & n/2- k - 2 \\ n/2+k & 1 & 0 \\ n/2+k & 0 & 0 \end{pmatrix} \end{equation*}$$

has characteristic polynomial

$$\begin{align*} \det [A_\phi - \lambda I] &= -\lambda ^3 +\lambda ^2 + \left(n^2/4 - k^2\right) \lambda - (n/2+k)(n/2-k-2) \\ &= -\lambda ^3 + \lambda ^2 + \left(\frac{ n^2}{4} - \frac{(1-\hat{\varepsilon }) n}{2} \right)\lambda - \left(\frac{n^2}{4} - \frac{(3-\hat{\varepsilon })n}{2} -\sqrt {2(1-\hat{\varepsilon })n} \right). \end{align*}$$

By matching higher order terms, we obtain

$$\begin{equation*} \lambda _{max}(A_\phi ) = \frac{n}{2}-\frac{1-\hat{\varepsilon }}{2} + \frac{\left( 8-(1-\hat{\varepsilon })^2 \right)}{4 n} +o(1/n), \end{equation*}$$

$$\begin{equation*} \lambda _{min}(A_\phi ) = -\frac{n}{2}+\frac{1-\hat{\varepsilon }}{2} + \frac{\left( 8+(1-\hat{\varepsilon })^2 \right)}{4 n} +o(1/n), \end{equation*}$$ and

$$\begin{equation*} s(K^+_{n/2+k,n/2-k}) \ge n-(1-\hat{\varepsilon })-\frac{(1-\hat{\varepsilon })^2}{2n} + o(1/n). \end{equation*}$$

Next, we aim to compute $s_b(n,m)$, $m = (n/2+k)(n/2-k)+1$. By Proposition 7.1, $s_b(n,m)$ is equal to the maximum of $s(K^m_{n/2+\ell ,n/2-\ell })$ over all $\ell \in [0,k-1]$, $k-\ell \in \mathbb{N}$. As previously noted, the quantity $s(K^m_{n/2+\ell ,n/2-\ell })$ is given exactly by Equation 14, and so the optimal choice of $\ell$ minimizes

$$\begin{align*} f(\ell ) &\coloneq (n/2+\ell -1)(k^2-\ell ^2-1)(n/2-\ell -(k^2-\ell ^2-1))\\ &\;=(n/2+\ell )\big ((1-\hat{\varepsilon })n/2-\ell ^2\big )\big (\hat{\varepsilon }n/2 +\ell ^2-\ell \big ) + O(n^2). \end{align*}$$

We have

$$\begin{equation*} f(k-1) = (n/2+k-2)(2k-2)(n/2-3k+3), \end{equation*}$$

and if $\ell \le \frac{4}{5} k$, then $f(\ell ) = \Omega (n^3)$. Therefore the minimizing $\ell$ is in $[\frac{4}{5} k,k]$. The derivative of $f(\ell )$ is given by

$$\begin{align*} f'(\ell ) &=(k^2-\ell ^2-1)(n/2-\ell -k^2+\ell ^2+1)\\ &\qquad -2\ell (n/2+\ell -1)(n/2-\ell -k^2+\ell ^2+1)\\ &\qquad +(2\ell -1)(n/2+\ell -1)(k^2-\ell ^2-1). \end{align*}$$

For $\ell \in [\frac{4}{5} k,k]$,

$$\begin{align*} f'(\ell ) &\le \frac{n(k^2-\ell ^2)}{2}-\ell n(n/2-\ell -k^2+\ell ^2)+2\ell (n/2+\ell )(k^2-\ell ^2)\\ &\le \frac{9 k^2 n}{50} - \tfrac{4}{5} kn(n/2-k- \tfrac{9}{25} k^2)+ \tfrac{18}{25} (n/2+k)k^3 \\ &= \frac{81 k^3 n}{125}-\frac{2 k n^2}{5} + O(n^2)\\ &=kn^2\left(\frac{81(1-\hat{\varepsilon })}{250}-\frac{2}{5}\right)+O(n^2)<0 \end{align*}$$

for sufficiently large $n$. This implies that the optimal choice is $\ell = k-1$, and $s_b(n,m) = s(K^m_{n/2+k-1,n/2-k+1})$. The characteristic polynomial $Q(n/2+k-1,n/2-k+1,n^2/4 -k^2+1)$ equals

$$\begin{equation*} \lambda ^4 - \left(n^2/4 -k^2+1 \right)\lambda ^2+2(n/2+k-2)(n/2-3k+3)(k-1). \end{equation*}$$

By matching higher order terms, the extreme root of $Q$ is given by

$$\begin{equation*} \lambda = \frac{n}{2} -\frac{1-\hat{\varepsilon }}{2} - \sqrt {\frac{2(1-\hat{\varepsilon })}{n}}+\frac{27-14\hat{\varepsilon }-\hat{\varepsilon }^2}{4n}+o(1/n), \end{equation*}$$

and so

$$\begin{equation*} s_b(n,m) = n -(1-\hat{\varepsilon }) - 2 \sqrt {\frac{2(1-\hat{\varepsilon })}{n}}+\frac{27-14\hat{\varepsilon }-\hat{\varepsilon }^2}{2n}+o(1/n), \end{equation*}$$

and

$$\begin{align*} \frac{s(n,m)-s_b(n,m)}{s(n,m)} &\ge \frac{2^{3/2}(1-\hat{\varepsilon })^{1/2}}{n^{3/2}} - \frac{14-8\hat{\varepsilon }}{n^2}+o(1/n^2)\\ &=\frac{(1-\hat{\varepsilon })^{1/2}}{m^{3/4}} + \frac{(1-\hat{\varepsilon })^{1/2}}{(n/2)^{3/2}}\bigg [1-\frac{(n/2)^{3/2}}{m^{3/4}}\bigg ] - \frac{14-8\hat{\varepsilon }}{n^2}+o(1/n^2)\\ &\ge \frac{1-\varepsilon /2}{m^{3/4}} +o(1/m^{3/4}). \end{align*}$$

This completes the proof.

■

A concrete example where the Bipartite Spread Conjecture fails is as follows.

Example 7.4.

Let $n = 10$ and $m = 22$, and consider the graphs $K^+_{7,3}$, $K^{22}_{6,4}$, and $K^{22}_{5,5}$ (see Figure 9 for a visual representation). We have

$$\begin{align*} s(K^+_{7,3}) &= 8 \cos \bigg (\frac{1}{3} \tan ^{-1}\big (3 \sqrt {29127}\big )\bigg ) + \frac{8}{\sqrt {3}} \sin \bigg (\frac{1}{3} \tan ^{-1}\big (3 \sqrt {29127}\big )\bigg ) \approx 9.238, \\ s(K^{22}_{6,4}) &= 2(11+\sqrt {101})^{1/2} \approx 9.176, \text{ and} \\ s(K^{22}_{5,5}) &= 2(11+\sqrt {97})^{1/2} \approx 9.132. \end{align*}$$

Every bipartite graph with $10$ vertices and $22$ edges is either a subgraph of $K_{5,5}$ or $K_{6,4}$, and so, by Proposition 7.1, $s_b(10,22) = \max \{s(K^{22}_{6,4}),s(K^{22}_{5,5})\} = s(K^{22}_{6,4})$. The graph $K^+_{7,3}$ is a lower bound for $s(10,22)$, and so

$$\begin{equation*} s(10,22) - s_b(10,22) \ge s(K^+_{7,3}) - s(K^{22}_{6,4}) \ge .06. \end{equation*}$$

It is unclear whether this is the smallest counterexample (w.r.t. $n$) to the Bipartite Spread Conjecture, though we note that in 13 the authors verified the conjecture by computer for all graphs of order $n \le 8$. Verifying that Example 7.4 is the smallest counterexample would require computations for $n = 9$, a task that we leave to the motivated reader.

8. Concluding remarks

In this work we provided a proof of the spread conjecture for sufficiently large $n$, a proof of an asymptotic version of the bipartite spread conjecture, and an infinite class of counterexamples illustrating that our asymptotic version of this conjecture is the strongest result possible. There are a number of interesting future avenues of research, some of which we briefly describe below. These avenues consist primarily of considering the spread of more general classes of graphs (for instance, directed graphs, graphs with loops) or considering more general objective functions.

Our proof of the spread conjecture for sufficiently large $n$ immediately implies a nearly-tight estimate for the adjacency matrix of undirected graphs with loops, also commonly referred to as symmetric $0-1$ matrices. Given a directed graph $G = (V,\mathcal{A})$, the corresponding adjacency matrix $A$ has entry $A_{i,j} = 1$ if the arc $(i,j) \in \mathcal{A}$, and is zero otherwise. In this case, $A$ is not necessarily symmetric, and may have complex eigenvalues. One interesting question is what digraph of order $n$ maximizes the spread of its adjacency matrix, where spread is defined as the diameter of the spectrum. Is this more general problem also maximized by the same set of graphs as in the undirected case? This problem for either loop-less directed graphs or directed graphs with loops is an interesting question, and the latter is equivalent to asking the above question for the set of all $0-1$ matrices.

Another approach is to restrict ourselves to undirected graphs or undirected graphs with loops, and further consider the competing interests of simultaneously producing a graph with both $\lambda _1$ and $-\lambda _n$ large by understanding the trade-off between these two goals. To this end, we propose considering the class of objective functions

$$\begin{equation*} f(G; \beta ) = \beta \lambda _1(G) - (1-\beta ) \lambda _n(G), \qquad \beta \in [0,1]. \end{equation*}$$

When $\beta = 0$, this function is maximized by the complete bipartite graph $K_{\lceil n /2 \rceil , \lfloor n/2 \rfloor }$ and when $\beta = 1$, this function is maximized by the complete graph $K_n$. This paper treats the specific case of $\beta = 1/2$, but none of the mathematical techniques used in this work rely on this restriction. In fact, the structural graph-theoretic results of Section 2, suitably modified for arbitrary $\beta$, still hold (see the thesis 32, Section 3.3.1 for this general case). Understanding the behavior of the optimum between these three well-studied choices of $\beta = 0,1/2,1$ is an interesting future avenue of research.

More generally, any linear combination of graph eigenvalues could be optimized over any family of graphs. Many sporadic examples of this problem have been studied. Nikiforov 23 proposed a general framework for it and proved some conditions under which the problem is well behaved. We conclude with some specific instances of the problem that we think deserve consideration.

Given a graph $F$, maximizing $\lambda _1$ over the family of $n$-vertex $F$-free graphs can be thought of as a spectral version of Turán’s problem. Many papers have been written about this problem, which was proposed in generality in 25. We remark that these results can often strengthen classical results in extremal graph theory. Maximizing $\lambda _1 + \lambda _n$ over the family of triangle-free graphs has been considered in 8 and is related to an old conjecture of Erdős on how many edges must be removed from a triangle-free graph to make it bipartite 12. In general it would be interesting to maximize $\lambda _1 + \lambda _n$ over the family of $K_r$-free graphs. When a graph is regular, the difference between $\lambda _1$ and $\lambda _2$ (the spectral gap) is related to the graph’s expansion properties. Aldous and Fill 3 asked for the minimum of $\lambda _1 - \lambda _2$ over the family of $n$-vertex connected regular graphs. Partial results were given by 12714. A nonregular version of the problem was proposed by Stanić 28, who asked for the minimum of $\lambda _1-\lambda _2$ over connected $n$-vertex graphs. Finally, maximizing $\lambda _3$ or $\lambda _4$ over the family of $n$-vertex graphs seems to be a surprisingly difficult question and even the asymptotics are not known (see 26).

Figure 1.

Contour plots of the spread for some choices of $\alpha$. Each point $(x,y)$ of Plot (a) illustrates the maximum spread over all choices of $\alpha$ satisfying $\alpha _3 + \alpha _4 = x$ and $\alpha _6 + \alpha _7 = y$ (and therefore, $\alpha _1 + \alpha _2 + \alpha _5 = 1 - x - y$) on a grid of step size $1/100$. Each point $(x,y)$ of Plot (b) illustrates the maximum spread over all choices of $\alpha$ satisfying $\alpha _2=\alpha _3=\alpha _4=0$, $\alpha _5 = y$, and $\alpha _7 = x$ on a grid of step size $1/100$. The maximum spread of Plot (a) is achieved at the two black “x”s, and implies that, without loss of generality, $\alpha _3 + \alpha _4=0$, and therefore $\alpha _2 = 0$ (indices $\alpha _1$ and $\alpha _2$ can be combined when $\alpha _3 + \alpha _4=0$). Plot (b) treats this case when $\alpha _2 = \alpha _3 = \alpha _4 = 0$, and the maximum spread is achieved on the black line. This implies that either $\alpha _5 =0$ or $\alpha _7 = 0$. In both cases, this reduces to the block $2\times 2$ case $\alpha _1,\alpha _7 \ne 0$ (or, if $\alpha _7 = 0$, then $\alpha _1,\alpha _6 \ne 0$).

Figure 1(a)

$\alpha _i \ne 0$ for all $i$

 

Figure 1(b)

$\alpha _2=\alpha _3=\alpha _4 = 0$

Figure 2.

Two presentations of a bipartite graph as a stepfunction

Figure 3.

The matrix $M^*$ with corresponding graph $G^*$, where $D_\alpha$ is the diagonal matrix with entries $\alpha _1, \ldots , \alpha _7$

$\displaystyle M^* \coloneq D_\alpha ^{1/2}\left[\begin{array}{cccc|ccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\1 & 1 & 1 & 0 & 1 & 1 & 1 \\1 & 1 & 0 & 0 & 1 & 1 & 1 \\1 & 0 & 0 & 0 & 1 & 1 & 1 \\\hline 1 & 1 & 1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array}\right]D_\alpha ^{1/2}$

Figure 4.

The family of graphons and the graph corresponding to case $4|57$

Figure 5.

Redundancy, then renaming: we can assume $\alpha _2=0$ in the family of graphons corresponding to $123|567$, which produces families of graphons corresponding to both cases $13|567$ and $14|567$

Figure 6.

Changing the sign of $g$: The optimization problems in these cases are equivalent

Figure 7.

The cases $1|24|7$ and $1|4|57$ correspond to the same family graphons but we consider the optimization problems separately, due to our prescribed ordering of the vertices

Figure 8.

The set $\mathcal{S}_{17}$, as a poset ordered by inclusion. Each element is a subset of $V(G^*) = \{1,\dots ,7\}$, written without braces and commas. As noted in the proof of Lemma A.2, the sets $\{1\}$, $\{2,3,4\}$, and $\{5,6,7\}$ have different behavior in the problems $\mathrm{SPR}_S$. For this reason, we use vertical bars to separate each $S\in \mathcal{S}_{17}$ according to the corresponding partition.

Table 1.

The indices $i,j$ corresponding to the search space used to bound solutions to $\mathrm{SPR}_S$

	$1$	$2$	$3$	$4$
$5$	$1|57$	$24|57$	$1|234|57$	$4|57$
		$1|24|57$		$1|4|57$
$6$	$1|567$	$24|567$	$234|567$	$4|567$
		$1|24|567$	$1|234|567$	$1|4|57$
$7$	$1|7$	$1|24|7$	$1|234|7$	$1|4|7$

Figure 9.

The graphs $K^+_{7,3}$, $K^{22}_{6,4}$, and $K^{22}_{5,5}$ from Example 7.4. The additional edge in $K_{7,3}^+$ is between the two pink vertices, and the missing edges in $K^{22}_{6,4}$ and $K^{22}_{7,3}$ are between the black vertex and the grey vertices.

Figure 9(a)

$K^+_{7,3}$

Figure 9(b)

$K^{22}_{6,4}$

Figure 9(c)

$K^{22}_{5,5}$

Figure 10.

Intervals containing the quantities $f_i$ and $g_i$. Note that $f_i$ and $g_i$ are only defined for all $i\in S$.

Table 2.

The $21$ sets which arise from repeated applications of Claim B

	$\emptyset$	$\{4\}$	$\{2,4\}$	$\{2,3,4\}$
$\{7\}$	$1|7$	$4|7$	$24|7$	$234|7$
		$1|4|7$	$1|24|7$	$1|234|7$
$\{5,7\}$	$1|57$	$4|57$	$24|57$	$234|57$
		$1|4|57$	$1|24|57$	$1|234|57$
$\{5,6,7\}$	$1|567$	$4|567$	$24|567$	$234|567$
		$1|4|567$	$1|24|567$	$1|234|567$