Independence ratio and random eigenvectors in transitive graphs

Introduction

An independent set is a set of vertices in a graph, no two of which are adjacent. The independence ratio of a graph $G$ is the size of its largest independent set divided by the total number of vertices. If $G$ is regular, then the independence ratio is at most $1/2$, and it is equal to $1/2$ if and only if $G$ is bipartite.

The adjacency matrix of a $d$-regular graph has real eigenvalues between $-d$ and $d$. The least eigenvalue $\lambda_{\min}$ is at least $-d$, and it is equal to $-d$ if and only if the graph is bipartite.

So the distance of the independence ratio from $1/2$ and the distance of $\lambda_{\min}$ from $-d$ both measure how far a $d$-regular graph is from being bipartite. The following natural question arises: what kind of connection is there between these two graph parameters?

A theorem of Hoffman gives a partial answer to this question. It says that the independence ratio of a $d$-regular graph is at most

for a simple proof, see , Theorem 11; also see , Section 4, for certain improvements.

Hoffman’s bound implies that $\lambda_{\min}\to-d$ as the independence ratio tends to $1/2$. The converse statement is not true in general: it is easy to construct $d$-regular graphs with $\lambda_{\min}$ arbitrarily close to $-d$ and the independence ratio separated from $1/2$. However, for transitive graphs the converse is also true. A graph $G$ is said to be vertex-transitive (or transitive in short) if its automorphism group $\operatorname{Aut}(G)$ acts transitively on the vertex set $V(G)$.

Let $G$ be a finite, $d$-regular, vertex-transitive graph with least eigenvalue $\lambda_{\min}$. Then the independence ratio of $G$ is at least

In particular, if $\lambda_{\min}\to-d$, then the independence ratio converges to $1/2$.

The idea behind the proof is to consider random eigenvectors with eigenvalue $\lambda_{\min}$. Let $\lambda$ be an arbitrary eigenvalue of the adjacency matrix of some transitive graph $G$, and let $E_{\lambda}$ denote the eigenspace corresponding to $\lambda$, that is, the space of eigenvectors with eigenvalue $\lambda$. (Note that $E_{\lambda}$ is typically more than one dimensional, since $G$ is transitive.) Furthermore, let $S_{\lambda}$ be the unit sphere in $E_{\lambda}$. Now we pick a uniform random vector from $S_{\lambda}$. Note that $S_{\lambda}$ is $\operatorname{Aut}(G)$-invariant, therefore the distribution of this random vector is $\operatorname{Aut}(G)$-invariant, too. Let us choose the vertices $v$ with the property that the value of the eigenvector at $v$ is larger than at each neighbor of $v$. (If $\lambda$ is negative, then we expect many of the vertices with positive value to have this property.) Clearly, these vertices form an independent set. Since our random vector is invariant, the probability $q$ that a given vertex is chosen is the same for all vertices. Therefore the expected size of this random independent set is $q|V(G)|$, and consequently, the independence ratio of $G$ is at least $q$. An estimate of $q$ yields Theorem 1 above. In many cases we obtain much sharper bounds.

When the graph has a lot of symmetry (e.g., when any pair of neighbors of a fixed vertex can be mapped to any other pair by a suitable graph automorphism), then the probability $q$ defined above is actually determined by $\lambda$. In this case it equals $q_{d}(\lambda)$, the relative volume of the $(d-1)$-dimensional regular spherical simplex defined by normal vectors with pairwise scalar product $\frac{d-2-\lambda}{2(d-1)}$; see Definition 2.9. There is a simple formula for $q_{3}(\lambda)$; see Theorem 3.

We conjecture that $q\geq q_{d}(\lambda)$ for arbitrary transitive graphs (provided that $\lambda$ is sufficiently small). In other words, the worst-case scenario is when the graph has a lot of symmetry. Of course, this would yield a lower bound $q_{d}(\lambda_{\min})$ for the independence ratio. We managed to prove this conjecture for $3$-regular transitive graphs and $4$-regular arc-transitive graphs. We also showed that a natural geometric conjecture would imply the $d$-regular, arc-transitive case. [A graph is said to be arc-transitive or symmetric if for any two pairs of adjacent vertices $(u_{1},v_{1})$ and $(u_{2},v_{2})$, there is an automorphism of the graph mapping $u_{1}$ to $u_{2}$ and $v_{1}$ to $v_{2}$.] The following theorems were obtained.

Suppose that $G$ is a finite, $d$-regular, arc-transitive graph with least eigenvalue $\lambda_{\min}$. Then the independence ratio of $G$ is at least

In fact, a natural geometric conjecture (see Conjecture 2.13) would imply that the independence ratio is at least $q_{d}(\lambda_{\min})$. This has been proven in the case $d=4$: the independence ratio of a finite, $4$-regular, arc-transitive graph is at least

Suppose that $G$ is a finite, $3$-regular, vertex-transitive graph with minimum eigenvalue $\lambda_{\min}$. Then the independence ratio of $G$ is at least

In fact, the following stronger statement holds: $G$ contains two disjoint independent sets $I_{1},I_{2}$ with total size $|I_{1}\cup I_{2}|\geq 2q_{3}(\lambda_{\min})|V(G)|$. This means that the induced subgraph $G[I_{1}\cup I_{2}]$ is bipartite and has at least $2q_{3}(\lambda_{\min})|V(G)|$ vertices.

See Figure 1 to compare the lower bound given in Theorem 3 to Hoffman’s upper bound (1). Note that $-3\leq\lambda_{\min}\leq-2$ for any $3$-regular transitive graph with the only exception of the complete graph $K_{4}$ for which $\lambda_{\min}=-1$; see Proposition .3 in the \hyperref[secapp]Appendix.

2 Random wave functions on infinite transitive graphs

These random wave functions will also let us answer an open question concerning factor of i.i.d. processes. Suppose that we have independent standard normal random variables $Z_{u}$ assigned to each vertex $u$ of an infinite transitive graph $G$. By a factor of i.i.d. process on $G$ we mean random variables $X_{v}$, $v\in V(G)$ that are all obtained as measurable functions of the random variables $Z_{u}$, $u\in V(G)$ and that are $\operatorname{Aut}(G)$-equivariant [i.e., they commute with the natural action of $\operatorname{Aut}(G)$]. It is easy to see that for any factor of i.i.d. process $X_{v}$, $v\in V(G)$ with $0<\operatorname{var}(X_{v})<\infty$, the correlation of $X_{v}$ and $X_{v^{\prime}}$ converges to as the distance of $v$ and $v^{\prime}$ goes to infinity; see Proposition .4 in the \hyperref[secapp]Appendix. So a random process that is everywhere with probability $1/2$ and $1$ everywhere with probability $1/2$ cannot be a factor of i.i.d. However, it can be seen easily that this process can be approximated by factor of i.i.d. processes provided that $G$ is amenable. So the space of factor of i.i.d. processes is not closed; that is, the distributions of these processes do not form a closed set w.r.t. the weak topology. It has been an open question whether the same is true on nonamenable graphs, for example, on the $d$-regular tree; see , Section 4, Question 4. We will show that the space of factor of i.i.d. processes is not closed provided that the spectrum of $G$ is uncountable.

We say that a factor of i.i.d. process $X_{v}$, $v\in V(G)$ is a linear factor of i.i.d. if each $X_{v}$ is obtained as a (possibly infinite) linear combination of $Z_{u}$, $u\in V(G)$. Note that linear factors have the following properties.

We call a collection of random variables $X_{v}$, $v\in V(G)$ a Gaussian process on $G$ if they are jointly Gaussian, and each $X_{v}$ is centered (i.e., has mean ). (Random variables are jointly Gaussian if any finite linear combination of them is Gaussian.) We say that a Gaussian process $X_{v}$ is $\operatorname{Aut}(G)$-invariant (or simply invariant) if for any $\Phi\in\operatorname{Aut}(G)$ the joint distribution of the Gaussian process $X_{\Phi(v)}$ is the same as that of the original process.

We will prove that the adjacency operator $A_{G}$ has approximate eigenvectors (satisfying a certain invariance property) for any $\lambda$ in the spectrum $\lambda\in\sigma(A_{G})$. Then we will use these approximate eigenvectors as coefficients to define linear factor of i.i.d. processes converging in distribution to an invariant Gaussian process $X_{v}$ that satisfies the eigenvector equation at each vertex.

Let $G$ be an infinite vertex-transitive graph with adjacency operator $A_{G}$. Then for each point $\lambda$ of the spectrum $\sigma(A_{G})$ there exists a nontrivial invariant Gaussian process $X_{v}$, $v\in V(G)$ such that

where $N(v)$ denotes the set of neighbors of $v$ in $G$. Furthermore, the process $X_{v}$ can be approximated (in distribution) by linear factor of i.i.d. processes. Clearly, we can assume that these approximating linear factors have only finitely many nonzero coefficients.

An invariant Gaussian process satisfying (3) will be called a Gaussian wave function with eigenvalue $\lambda$. If the spectrum of $G$ is not countable, then we can conclude that some of these Gaussian wave functions cannot be obtained as factor of i.i.d. processes.

Let $G$ be an infinite transitive graph such that the spectrum of the adjacency oparator $A_{G}$ is not countable. Then there exist (linear) factor of i.i.d. processes on $G$ with the property that the weak limit of their distributions cannot be obtained as the distribution of a factor of i.i.d. process.

In view of Theorems 4 and 6 there exists a Gaussian wave function with eigenvalue $\lambda_{\max}$ that can be approximated by factor of i.i.d. processes but cannot be obtained as one. An independent and different proof of this result was given by Russell Lyons in the special case when $G$ is a regular tree , Corollary 3.3.

3 Factor of i.i.d. independent sets

In the infinite setting let $\lambda_{\min}$ denote the minimum of the spectrum $\sigma(A_{G})$, and let $X_{v}$ be a linear factor of $Z_{v}$ approximating the Gaussian eigenvector with eigenvalue $\lambda_{\min}$; see Theorem 4. As the process $X_{v}$ converges in distribution to the Gaussian eigenvector, the probability $P(v\in I_{+})$ approaches the corresponding probability for the Gaussian eigenvector process, which, as we will see, can be computed the exact same way as in the finite case.

Theorems 1, 2 and 3 give lower bounds $q$ (in terms of $\lambda_{\min}$) for the independence ratio of finite transitive graphs with least eigenvalue $\lambda_{\min}$. These bounds remain true in the following framework. Let $\lambda_{\min}$ denote the minimum of the spectrum of an infinite transitive graph $G$. Then for any $\varepsilon>0$ there exists a factor of i.i.d. independent set on $G$ such that the probability that any given vertex is in the set is at least $q-\varepsilon$.

A special case of this infinite setting was investigated in . When $G$ is the $d$-regular tree $T_{d}$, then any factor of i.i.d. independent set on $G$ automatically gives a lower bound for the independence ratio of $d$-regular finite graphs with sufficiently large girth. In particular, for the $3$-regular tree, $T_{3}$ one has $\lambda_{\min}=-2\sqrt{2}$. Therefore the infinite version of Theorem 3 tells us that there exists factor of i.i.d. independent set in $T_{3}$ with density

In the somewhat better bound $0.4361$ was obtained. In fact, was the starting point for the work in the present paper. For previous results on the independence ratio of large-girth graphs, see .

Finite vertex-transitive graphs

Throughout this section $G$ will denote a vertex-transitive, finite graph with degree $d$ for some positive integer $d\geq 3$. The least eigenvalue of its adjacency matrix $A_{G}$ will be denoted by $\lambda_{\min}$. For now let $\lambda$ be an arbitrary eigenvalue of $A_{G}$. Eventually, we will choose $\lambda$ as the minimum eigenvalue. First we define what we mean by a random eigenvector.

Let $E_{\lambda}$ be the eigenspace corresponding to $\lambda$, that is,

We fix some orthonormal basis $e_{1},\ldots,e_{l}$ in $E_{\lambda}$, and take independent standard normal random variables $\gamma_{1},\ldots,\gamma_{l}$. We call $\sum_{i=1}^{l}\gamma_{i}e_{i}$ the random eigenvector with eigenvalue $\lambda$.

The (distribution of the) random eigenvector is clearly independent of the choice of the basis $e_{1},\ldots,e_{l}$, so it is well defined. It also follows that the distribution of the random eigenvector is $\operatorname{Aut}(G)$-invariant. (Note that in the \hyperref[sec1]Introduction we defined the random eigenvector differently: a uniform random vector on the unit sphere of $E_{\lambda}$, which is just the normalized version of the random eigenvector of Definition 2.1.)

We will think of this random eigenvector as a collection of real-valued random variables $X_{v}$, $v\in V(G)$ with the property that they are jointly Gaussian and $\operatorname{Aut}(G)$-invariant, each $X_{v}$ is centered, and

where $N(v)$ denotes the set of neighbors of $v$ in $G$. Since $G$ is transitive, each $X_{v}$ has the same variance. After multiplying these random variables with a suitable positive constant we might assume that $\operatorname{var}(X_{v})=1$ for each vertex $v$. Next we define random independent sets by means of these random eigenvectors.

Let $X_{v}$, $v\in V(G)$ denote the random eigenvector corresponding to the eigenvalue $\lambda$ as explained above. The random sets $I_{+}$ and $I_{-}$ are defined as follows:

Clearly, $I_{+}$ and $I_{-}$ are disjoint (random) independent sets in $G$.

The $\operatorname{Aut}(G)$-invariance implies that the probability of the event $v\in I_{+}$ is the same for all vertices $v$. So from now on, we will focus on a fixed vertex and its neighbors. First we introduce the following notation.

Let $v$ be an arbitrary vertex of our vertex-transitive graph $G$. We will call $v$ the root. The neighbors of $v$ are denoted by $w_{1},\ldots,w_{d}$. For $X_{v}$ and $X_{w_{i}}$ we will simply write $X$ and $Y_{i}$, respectively. We will assume that $\operatorname{var}(X)=1$, which implies that $\operatorname{var}(Y_{i})=1$ for each $i$. Since $X_{v}$, $v\in V(G)$ is the random eigenvector with eigenvalue $\lambda$, we have

The covariance $\operatorname{cov}(Y_{i},Y_{j})$ will be denoted by $c_{i,j}$. Then it readily follows from (4) that

Finally, we introduce the following notation for the pairwise angles of the vectors $u_{i}$:

Our goal is to give estimates for the probability that a certain vertex lies in our random independent set $I_{+}$. As we will see, this probability can be expressed as the volume of a certain spherical simplex.

The probability that any fixed vertex is in the random independent set $I_{+}$ is equal to the relative volume of the $(d-1)$-dimensional spherical simplex corresponding to the outer normal vectors $-u_{i}$.

The probability $P(v\in I_{+})$ seems to be the smallest when $G$ has a lot of symmetry. To make this more precise, we first define what we mean by a “lot of symmetry.”

We say that $G$ is cherry-transitive if any cherry (path of length $2$) in $G$ can be mapped to any other cherry using a suitable graph automorphism of $G$.

and, consequently, the pairwise angles $\varphi_{i,j}$ are all equal to

If $G$ is cherry-transitive, then for any $i_{1}\neq j_{1}$ and $i_{2}\neq j_{2}$ there exists an automorphism $\Phi\in\operatorname{Aut}(G)$ such that $\Phi$ fixes the root $v$ and takes the unordered pair $w_{i_{1}},w_{j_{1}}$ to $w_{i_{2}},w_{j_{2}}$, that is,

Together with the $\operatorname{Aut}(G)$-invariance of the random eigenvector this implies that $c_{i_{1},j_{1}}=c_{i_{2},j_{2}}$. Since this holds for any two pairs of indices, it follows that all $c_{i,j}$, $i\neq j$ are the same. Using (5) we conclude that for $i\neq j$

Then easy calculation shows (using notations introduced earlier) that

We are now in a position to define the functions $q_{d}(\lambda)$.

For $-d\leq\lambda\leq d$, let $q_{d}(\lambda)$ denote the volume of the $(d-1)$-dimensional regular spherical simplex corresponding to the angle (9) divided by $\operatorname{vol}(S^{d-1})$. Then $P(v\in I_{+})=q_{d}(\lambda)$ for any cherry-transitive $G$. In particular, the independence ratio of any cherry-transitive graph $G$ is at least $q_{d}(\lambda_{\min})$.

So $P(v\in I_{+})=q_{d}(\lambda)$ provided that $G$ has enough symmetry. The following conjecture says that in the general (i.e., vertex-transitive) case the probability should be larger than that.

For any transitive graph $G$ it holds that

for any $\lambda$, or at least for sufficiently small $\lambda$: $\lambda\leq\lambda_{0}$ for some $\lambda_{0}$.

This would, of course, imply that the independence ratio of $G$ is at least $q_{d}(\lambda_{\min})$ provided that $\lambda_{\min}\leq\lambda_{0}$.

We will prove this conjecture for $d=3$ and $\lambda_{0}=-2$ in Section 2.1. The conjecture might be true for arbitrary $\lambda$, but proving for $\lambda\leq\lambda_{0}=-2$ will be sufficient for our purposes, because $\lambda_{\min}\leq-2$ for any $3$-regular transitive graph except $K_{4}$.

In view of formula (8) the above conjecture would follow from the following statement. Let $(U_{1},\ldots,U_{d})$ be a multivariate Gaussian with each $U_{i}$ centered and with pairwise covariances $m_{i,j}$. We have the following constraints for the covariances:

[Or one might replace these by the weaker constraints $\sum_{1\leq i,j\leq d}m_{i,j}=(d-\lambda)^{2}$ and $\sum_{1\leq i\leq d}m_{i,i}=2(d-\lambda)$.] Then the orthant probability $P(U_{i}>0,1\leq i\leq d)$ is minimized when all $m_{i,i}$, $1\leq i\leq d$ are equal and also all $m_{i,j}$, $i\neq j$ are equal.

A few properties of the functions $q_{d}(\lambda)$ are collected in the next proposition.

For any $d\geq 3$, $q_{d}$ is a monotone decreasing continuous function on $[-d,-1]$ with

As for the behavior of $q_{d}$ around $-d$ we have

The volume of a regular spherical simplex is clearly a continuous and monotone decreasing function of the corresponding angle. Since (9) is a continuous and monotone increasing function of $\lambda\in[-d,-1]$, monotonicity and continuity of $q_{d}$ follow.

For $\lambda=-d$ the angles $\varphi_{i,j}$ are , so the corresponding (degenerate) spherical simplex is a hemisphere, thus $q_{d}(-d)=1/2$ as claimed.

See Section 2.3 for a proof of the claimed behavior around $-d$.

Now we turn to the proof of Theorem 3 that gives a lower bound for the independence ratio of $3$-regular transitive graphs. We will basically show that Conjecture 2.10 is true when $d=3$ and $\lambda_{0}=-2$.

As we have seen, $P(v\in I_{+})$ equals the relative volume of a certain spherical simplex. For $d=3$ the surface of the unit sphere $S^{d-1}=S^{2}$ is $4\pi$ and the area of a spherical triangle with interior angles $\alpha,\beta,\gamma$ is equal to $\alpha+\beta+\gamma-\pi$. The spherical triangle in question is determined by the homogeneous half-spaces with outer normal vectors $-u_{1},-u_{2},-u_{3}$ (recall Proposition 2.6). We denoted the angle enclosed by the outer normal vectors $-u_{i}$ and $-u_{j}$ by $\varphi_{i,j}$. Then the interior angle at the intersection of the two corresponding planes is clearly $\pi-\varphi_{i,j}$. Therefore $P(v\in I_{+})$ equals the relative surface area of a spherical triangle with angles $\pi-\varphi_{1,2}$, $\pi-\varphi_{1,3}$, $\pi-\varphi_{2,3}$,

By Proposition 2.8 we have $c_{i,j}=(\lambda^{2}-3)/6$ and $\varphi_{i,j}=\arccos((1-\lambda)/4)$ in the cherry-transitive case, thus

Proof of Theorem 3 The statement of the theorem is true for the complete graph $K_{4}$ as the independence ratio is $1/4$ and the minimum eigenvalue is $-1$ in that case. For any other $3$-regular transitive graph $G$ we have $\lambda_{\min}\leq-2$; see Proposition .3 in the \hyperref[secapp]Appendix. Therefore it suffices to prove that $P(v\in I_{+})\geq q_{3}(\lambda)$, whenever $\lambda\leq-2$.

Recall that $Y_{1},Y_{2},Y_{3}$ are standard Gaussians with pairwise covariances $c_{i,j}$. Therefore the matrix

is positive semidefinite. In particular, its determinant is nonnegative:

Furthermore, according to (5) we have $c_{1,2}+c_{1,3}+c_{2,3}=(\lambda^{2}-3)/2\geq 1/2$, because $\lambda\leq-2$. It follows that each $c_{i,j}$ must be between $-1/2$ and $1$.

Indeed, let $x,y,z$ be real numbers between $-1$ and $1$ with $x+y+z\geq 1/2$ and $1+2xyz-x^{2}-y^{2}-z^{2}\geq 0$. Assume that $z<-1/2$. Then

contradiction. Therefore $z\geq-1/2$. Similarly, $x,y\geq-1/2$, too.

Next we bound $u_{i}\cdot u_{j}/(\|u_{i}\|\|u_{j}\|)$ from below. Using (2.4), $x=(y_{1}+y_{2}+y_{3})/\lambda$ and $c_{1,2}+c_{1,3}+c_{2,3}=(\lambda^{2}-3)/2$

Similar formulas hold for $x\cdot y_{i}$ and $\|u_{i}\|$, $i=2,3$. By the inequality of arithmetic and geometric means it follows that

Note that this holds with equality when all $c_{i,j}$ are equal. Furthermore,

because the numerator is positive (note that $-3\leq\lambda\leq-2$ and $c_{1,2}\geq-1/2$). The analogous inequality holds for any other pair of indices $i,j$. Since $\arcsin$ is a monotone increasing function, (2.1) yields that

which follows from (11) and the definition of $f$. [It also follows from the fact that when each $c_{i,j}$ is equal to $(\lambda^{2}-3)/6$, then (12) should hold with equality.] In view of (12) and (13) we need to show that

where each $c_{i,j}$ is between $-1/2$ and $1$, and their average is $(\lambda^{2}-3)/6$. This, of course, would follow from the convexity of $f$. Unfortunately, $f$ is not convex on the entire interval $[-1/2,1]$. We claim, however, that the tangent line to $f$ at $t_{0}=(\lambda^{2}-3)/6$ is below $f$ on the entire interval $[-1/2,1]$, which still implies (14). The rather technical proof of this claim can be found in the \hyperref[secapp]Appendix (Lemma .7).

Now let $\lambda=\lambda_{\min}\leq-2$, then $P(v\in I_{+})\geq q_{3}(\lambda_{\min})$. So the expected size of the random independent set $I_{+}$ is at least $q_{3}(\lambda_{\min})|V(G)|$; thus the independence ratio of $G$ is at least $q_{3}(\lambda_{\min})$.

To prove the second part of the statement we notice that the random independent set $I_{-}$ (see Definition 2.3) has the same expected size. Indeed, if we replace $X_{v}$, $v\in V(G)$ with $X^{\prime}_{v}=-X_{v}$, then $X^{\prime}_{v}$, $v\in V(G)$ have the same joint distribution and the roles of $I_{+}$ and $I_{-}$ interchange. Since $I_{+}$ and $I_{-}$ are always disjoint, the expected size of their union $I_{+}\cup I_{-}$ is at least $2q_{3}(\lambda_{\min})|V(G)|$. Consequently, there must exist disjoint independent sets $I_{1},I_{2}$ in $G$ with $|I_{1}\cup I_{2}|\geq 2q_{3}(\lambda_{\min})|V(G)|$.

For graphs with very large odd-girth, Theorem .1 of the \hyperref[secapp]Appendix gives a slightly better bound. The proof is based on the same random eigenvector, but uses a different method to find large independent sets.

2 The arc-transitive case

The following innocent-looking, and very plausible, conjecture is open in dimension $n\geq 4$.

The statement of the conjecture is trivial for $n=2$, while the $n=3$ case follows from the so-called moment theorem of Fejes Tóth , Theorem 2; see also , Section 34. The genereal case would follow from the following conjecture: the volume of the intersection of a fixed spherical cap and a spherical simplex of fixed volume is maximal when the spherical simplex is regular, and its center coincides with the center of the spherical cap (Gábor Fejes Tóth, personal communication, 2012).

In what follows we will explain how the case $n=d-1$ of Conjecture 2.13 implies that $P(v\in I_{+})\geq q_{d}(\lambda)$ holds for every $d$-regular arc-transitive graph $G$, and consequently the independence ratio of $G$ is at least $q_{d}(\lambda_{\min})$. In particular, the $d=4$ case follows from the $n=3$ case of the conjecture, which is known to be true; see Theorem 2. Using our previous notation, $P(v\in I_{+})$ is the volume of the spherical simplex $T$ determined by the half-spaces with outer normal vectors $-u_{i}$, $i=1,\ldots,d$, while $q_{d}(\lambda)$ is the volume of the same simplex in the case when all the angles $\varphi_{i,j}=\angle(u_{i},u_{j})$, $i\neq j$ are the same. In other words, we need to show that the volume of the spherical simplex $T$ is minimal when the angles $\angle(u_{i},u_{j})$ are the same.

If $G$ is arc-transitive, then the covariances $\operatorname{cov}(X,Y_{i})=x\cdot y_{i}$ are all equal. Since

we get that $x\cdot y_{i}=\lambda/d$ for each $i$. It follows that the angle enclosed by $x$ and $u_{i}$

Now let $S_{l}$ be the set of points on $S^{d-1}$ that has some fixed distance $l$ from $x$; thus $S_{l}$ is a $(d-2)$-dimensional sphere for any $l$. The intersection of $S_{l}$ and the half-space with outer normal vector $u_{i}$ is a spherical cap of radius depending only on $l$ and $\lambda$. So the intersection of $S_{l}$ and our spherical simplex $T$ can be obtained by removing $d$ spherical caps of the same given radius from $S_{l}$. If Conjecture 2.13 is true for $n=d-1$, then the total volume of the removed area is maximal for the “regular configuration” when each $\angle(u_{i},u_{j})$ is the same. Therefore the $(d-2)$-dimensional volume of $T\cap S_{l}$ is minimal for the regular configuration for any $l$. It follows that the $(d-1)$-dimensional volume of $T$ is also minimal for the regular configuration, and this is what we wanted to prove.

3 Bounds near −d𝑑-d

Even if Conjecture 2.13 is not assumed to be true, the above observations yield a lower bound for the independence ratio of $d$-regular arc-transitive graphs in the case when the least eigenvalue is close to $-d$.

Proof of Theorem 2 We already explained in Section 2.2 why Conjecture 2.13 implies that the independence ratio is at least $q_{d}(\lambda_{\min})$.

Next we prove tht first part of Theorem 2. As we have seen in (15), $\angle(x,u_{i})=\delta$ for each $i$, which means that each point of $S^{d-1}$ at (spherical) distance less than $\pi/2-\delta$ from $x$ is contained in our spherical simplex $T$. These points form a spherical cap with center $x$ and radius $\pi/2-\delta$. (In fact, this spherical cap is the “inscribed ball” of $T$.) Using (15) and that $\arccos(t)\leq\pi/2\sqrt{1-t}$ for any $t\in$, we get

This spherical cap can be obtained by taking the hemisphere (around $x$), and removing a strip of “width” $\delta$ (in spherical distance). The volume of this strip is clearly at most $\delta\operatorname{vol}(S^{d-2})$. Therefore the volume of the spherical cap is at least $\operatorname{vol}(S^{d-1})/2-\delta\operatorname{vol}(S^{d-2})$, whence

For $d=4$ we have $\operatorname{vol}(S^{2})/\operatorname{vol}(S^{3})=(4\pi)/(2\pi^{2})=2/\pi$, so the bound is

For general $d$, we use the estimate $\operatorname{vol}(S^{d-2})/\operatorname{vol}(S^{d-1})\leq\sqrt{d}/\sqrt{2\pi}$ (see Lemma .6 of the \hyperref[secapp]Appendix) to obtain the following bound:

These are lower bounds for the probability $P(v\in I_{+})$, in particular, for $q_{d}(\lambda)$. Thus the first part of Theorem 2 follows, as well as the estimate (2) for $q_{4}(\lambda)$ and the last statement of Proposition 2.12.

Proof of Theorem 1 In the general (vertex-transitive) case, we use that $x\cdot y_{1}+\cdots+x\cdot y_{d}=\lambda$ and $x\cdot y_{j}\geq-1$:

Therefore the angle $\angle(x,y_{i})$ is at least $\arccos(\lambda+d-1)$. Using that $\arccos(t)\leq\pi/2\sqrt{1-t}$ for any $t\in$, it follows that

provided that $\lambda\leq-d+1$. This means that our spherical simplex $T$ contains the spherical cap with center $x$ and radius $\pi/2-\delta^{\prime}$. Therefore

Since $\sqrt{\pi}/(4\sqrt{2})<1/3$, Theorem 1 follows.

Infinite transitive graphs

Now let $\lambda_{0}$ be an arbitrary element of the spectrum $\sigma(A_{G})$, and set $S=[\lambda_{0}-\varepsilon,\lambda_{0}+\varepsilon]$. We define $\alpha$ as the image of the indicator function $\mathbh{1}_{x}$ under the projection $P_{S}$,

Note that $\mathbh{1}_{x}$ is a fixed point of $U_{\Phi}$ for any $\Phi\in\operatorname{Stab}_{x}(G)$. Therefore

It remains to show that $\alpha=P_{[\lambda_{0}-\varepsilon,\lambda_{0}+\varepsilon]}\mathbh{1}_{x}\neq 0$. Assume that $P_{[\lambda_{0}-\varepsilon,\lambda_{0}+\varepsilon]}\mathbh{1}_{x}=0$. It follows that $P_{[\lambda_{0}-\varepsilon,\lambda_{0}+\varepsilon]}\mathbh{1}_{v}=0$ for every vertex $v\in V(G)$. Indeed, let $\Phi\in\operatorname{Aut}(G)$ such that $\Phi x=v$. Then $U_{\Phi}\mathbh{1}_{x}=\mathbh{1}_{v}$ and

This holds for each vertex $v$, which clearly implies that $P_{[\lambda_{0}-\varepsilon,\lambda_{0}+\varepsilon]}=0$. Then the operator

would be the inverse of $A_{G}-\lambda_{0}I$ contradicting our assumption that $\lambda_{0}\in\sigma(A_{G})$.

There is a general theorem for Hilbert spaces saying that every point of the spectrum of a self-adjoint operator is an approximate eigenvalue , Corollary 4.1.3. So the real content of the above theorem is that one can find approximate eigenvectors that are $\operatorname{Stab}_{x}(G)$-invariant. This invariance will be crucial for us later on, when we will use these approximate eigenvectors as coefficients to define linear factor of i.i.d. processes.

Suppose now that we have an i.i.d. process on $G$: independent standard normal random variables $Z_{u}$ assigned to each vertex $u$. We will consider processes $X_{v}$, $v\in V(G)$, where each $X_{v}$ is a (possibly infinite) linear combination of $Z_{u}$, $u\in V(G)$. We collected some obvious properties of such processes in the next proposition.

Let $\beta_{v,u}$, $v,u\in V(G)$ be real numbers, and let

The infinite sum in (16) converges almost surely if and only if

If (17) is satisfied, then $X_{v}$ is a centered Gaussian with variance $\operatorname{var}(X_{v})=\sum_{u\in V(G)}\beta_{v,u}^{2}$.

The process $X_{v}$, $v\in V(G)$ is $\operatorname{Aut}(G)$-invariant if and only if

Now we are in a position to formally define linear factor of i.i.d. processes.

We say that a process $X_{v}$, $v\in V(G)$ is a linear factor of the i.i.d. process $Z_{u}$ if it can be written as in (16) for some real numbers $\beta_{v,u}$, $v,u\in V(G)$ satisfying (17) and (18).

Recall Definition 1.1 of invariant Gaussian processes.

We call an invariant Gaussian process $X_{v}$, $v\in V(G)$ a Gaussian wave function with eigenvalue $\lambda$ if

where $N(v)$ denotes the set of neighbors of $v$ in $G$.

It was shown in that for the $d$-regular tree $T_{d}$ there exists an essentially unique Gaussian wave function for each $\lambda\in[-d,d]$. Furthermore, this Gaussian wave function can be approximated by factor of i.i.d. processes provided that $\lambda$ is in the spectrum $\sigma(T_{d})=[-2\sqrt{d-1},2\sqrt{d-1}]$.

In general, it is not clear for which $\lambda$ such Gaussian wave functions exist and whether they are unique.

For a transitive graph $G$ we call the closed set

Theorem 4 claims that for any $\lambda\in\sigma(A_{G})$ there exists a Gaussian wave function on $G$, which can be approximated by linear factor of i.i.d. processes. Therefore $\widetilde{\sigma}(G)\supseteq\sigma(A_{G})$.

Proof of Theorem 4 We use the $\operatorname{Stab}_{x}(G)$-invariant approximate eigenvectors of Theorem 3.1 to define linear factor of i.i.d. processes. So let $\varepsilon>0$ be arbitrary and $\alpha^{\varepsilon}$ a $\operatorname{Stab}_{x}(G)$-invariant vector with $\|\alpha^{\varepsilon}\|=1$ and $\|A_{G}\alpha^{\varepsilon}-\lambda\alpha^{\varepsilon}\|\leq\varepsilon$. By Remark 3.5 for each $\alpha^{\varepsilon}$ there is a corresponding linear factor $X_{v}^{\varepsilon}$, $v\in V(G)$. Note that the process

Since the space of invariant Gaussian processes with variance $1$ is compact, it follows that there exists a sequence $\varepsilon_{n}$ converging to such that the processes $X_{v}^{\varepsilon_{n}}$ converge in distribution. The limit process will be a nontrivial invariant Gaussian process $X_{v}$ that satisfies the eigenvector equation (3) at each vertex.

2 Factor of i.i.d. processes

Let $G$ be an infinite transitive graph, and suppose that $F$ is a measurable $\Omega\to\Omega$ function that is $\operatorname{Aut}(G)$-equivariant [i.e., commutes with the $\operatorname{Aut}(G)$-action]. Then $X=F(Z)$ is an invariant process on $G$. Such a process $X=(X_{v})_{v\in V(G)}$ is called a factor of the i.i.d. process $Z$.

where $\Phi_{y\to x}$ is an (arbitrary) automorphism of $G$ taking $y$ to $x$. Since $f$ is $\operatorname{Stab}_{x}(G)$-invariant, $\mathcal{A}$ is well defined.

Suppose now that we have a Gaussian wave function with eigenvalue $\lambda$ that can be obtained as a factor of i.i.d. process. Then the corresponding $f$ satisfies the eigenvector equation $\mathcal{A}f=\lambda f$. In particular, $\lambda$ needs to be in the point spectrum of $\mathcal{A}$. [Note that an eigenvector $f$ of $\mathcal{A}$ does not necessarily give us a Gaussian wave function: although the corresponding factor of i.i.d. process will satisfy the eigenvector equation at each vertex, $f(Z)$ might not have a Gaussian distribution.]

Therefore only for countably many $\lambda$’s can we have a Gaussian wave function on $G$ that can be obtained as a factor of i.i.d. process. However, if $\sigma(A_{G})$ is uncountable, then by Theorem 4, $G$ has Gaussian wave functions for uncountably many different eigenvalues $\lambda$; moreover, they can all be approximated by linear factor of i.i.d. processes.

Proof of Theorem 6 We will use two basic facts about the point spectra of the adjacency operators $A_{G}$ and $\mathcal{A}$. First, $\lambda_{\max}$ is never in the point spectrum $\sigma_{p}(A_{G})$ (we will give a short proof for this in the \hyperref[secapp]Appendix; see Lemma .5). Second, $\sigma_{p}(\mathcal{A})\subseteq\sigma_{p}(A_{G})\cup\{d\}$ for Cayley graphs (this will be explained after the proof). Therefore $\lambda_{\max}$ is not in the point spectrum of $\mathcal{A}$ provided that $\lambda_{\max}<d$, and consequently, a Gaussian wave function with eigenvalue $\lambda_{\max}$ cannot be obtained as a factor of i.i.d. process.

In the case $\lambda_{\max}=d$ the Gaussian wave function has to be constant; that is, $X_{u}=X_{v}$ for any two vertices $u,v$. However, for a factor of i.i.d. process the correlation between $X_{u}$ and $X_{v}$ should tend to as the distance of $u$ and $v$ goes to infinity; see Proposition .4 in the \hyperref[secapp]Appendix.

Note that this is actually a finite product, since all but finitely many terms are equal to $g_{0}\equiv 1$. According to , Lemma 3.1, the functions $W_{q}$, $q\in\mathcal{I}$ form an orthonormal basis of $L_{2}(\Omega,\mu)$. It follows that $L_{2}(\Omega,\mu)$ is separable, which fact was used in the proof of Theorem 5.

(This is often called the generalized Bernoulli shift.) Then for $f\in L_{2}(\Omega,\mu)$, let

This clearly extends our earlier definition of $\mathcal{A}$.

There is a natural $\Gamma$-action on $\mathcal{I}$ as well: for $q\in\mathcal{I}$

It is compatible with the $\Gamma$-action on $\Omega$ in the following sense:

We now consider the orbit $\{\gamma\cdot p\dvtx\gamma\in\Gamma\}$ of a given element $p\in\mathcal{I}$ and the closure of the space spanned by the corresponding functions $W_{\gamma\cdot p}$,

where $q$ is in the orbit of $p$. It is easy to see that $T_{p}$ is a bounded operator for which $T_{p}\mathcal{A}|_{H_{p}}=A_{G}T_{p}$. Since $T_{p}$ is also bounded below, it follows that

with equality when the stabilizer $\Gamma_{p}$ is trivial.

3 Independent sets

Let $G$ be an infinite transitive graph and $\lambda_{\min}$ be the minimum of its spectrum $\sigma(A_{G})$. Consider linear factor of i.i.d. processes $X_{v}^{n}$ converging in distribution to a Gaussian wave function $X_{v}$ with eigenvalue $\lambda_{\min}$ as $n\to\infty$ as in Theorem 4. We define the following independent sets on $G$:

Then for each $n$ the independent set $I_{+}^{n}$ is a factor of the i.i.d. process $Z_{v}$; that is, it is obtained as a measurable function of $Z_{v}$, $v\in V(G)$ that commutes with the natural action of $\operatorname{Aut}(G)$. Furthermore, since the event $v\in I_{+}$ corresponds to an open set, we have

Therefore whenever we have a lower bound $q$ for $P(v\in I_{+})$, it yields that for any $\varepsilon>0$ there exists a factor of i.i.d. independent set with “size” greater than $q-\varepsilon$.

Bounding $P(v\in I_{+})$, however, leads us to the same optimization problem as in the finite case. We need to estimate the volume of the same spherical simplex with the exact same constraints. [Of course, there might be a difference between the finite and infinite setting in terms of what covariances $c_{i,j}$ can actually come up, but our proofs used only the trivial constraints that they form a positive semidefinite matrix and their sum is $(\lambda_{\min}^{2}-d)/2$, which are true in the infinite case, too.] Thus we obtain the exact same bounds, and Theorem 7 follows.

Actually, in Theorem 3 we proved the bound only for graphs with $\lambda_{\min}\leq-2$ and argued that the only finite, $3$-regular, transitive graph for which this does not hold is the complete graph $K_{4}$. For infinite transitive graphs $\lambda_{\min}\leq-2$ holds with no exception. This follows from the fact that they contain arbitrarily long paths as induced subgraphs.

Appendix

Suppose that $G$ is a finite, $3$-regular, vertex-transitive graph with minimum eigenvalue $\lambda_{\min}$ and odd-girth $g$. Then the independence ratio of $G$ is at least

In fact, there exist two disjoint independent sets in $G$ such that their average size divided by $|V(G)|$ is not less than the above bound.

It is easy to check the statement for $K_{4}$. According to Proposition .3 $\lambda_{\min}\leq-2$ holds for any other finite, $3$-regular, transitive graph $G$. Let $X_{v}$, $v\in V(G)$ be the random eigenvector corresponding to $\lambda_{\min}$. Let $V_{+}$ denote the set of “positive vertices,” that is,

The expected size of $V_{+}$ is $|V(G)|/2$.

Since $\lambda_{\min}$ is negative, a vertex and its three neighbors cannot all be positive. Therefore each vertex has degree at most two in the induced subgraph $G[V_{+}]$. Thus each connected component of this subgraph is a path or a cycle. We want to choose an independent set from each component. We can choose at least half the vertices from paths and even cycles. From an odd cycle of length $l\geq g$ we can choose $(l-1)/2$ vertices, which is at least a $(g-1)/(2g)$ proportion of all vertices in that component. (Recall that $g$ denotes the odd-girth of $G$, i.e., the length of the shortest odd cycle in $G$.)

We need one more observation, namely, that many of the components actually contain only one vertex. Using our earlier notation, let $v$ be an arbitrary vertex with neighbors $w_{1},w_{2},w_{3}$, the corresponding random variables are $X$ and $Y_{1},Y_{2},Y_{3}$. Note that $Y_{1}<0$, $Y_{2}<0$ and $Y_{3}<0$ imply that $X>0$. Therefore the probability $p$ that $v$ is an isolated vertex in $G[V_{+}]$ is

Note that $\arcsin$ it is a monotone increasing odd function on $$, which is convex on$$. Furthermore, the average of $c_{i,j}$ is $(\lambda_{\min}^{2}-3)/6\geq(2^{2}-3)/6>0$. It is easy to see that these imply that the right-hand side of (Appendix) decreases (not increases) if we replace each $c_{i,j}$ with their average $(\lambda_{\min}^{2}-3)/6$. Thus

Our independent set will contain all isolated vertices and at least a $(g-1)/(2g)$ proportion of all the other vertices in $V_{+}$. This yields the following lower bound for the independence ratio of $G$:

Combining this with (21) yields the desired bound.

We can choose an independent set with the same expected size from the “negative vertices”

This implies the second part of the theorem.

We mention that the proof also works in the infinite setting, so there is an analogous theorem for infinite transitive graphs (as in Theorem 7).

Any nontrivial lower bound for the density of components of size $3,5,\ldots$ in $G[V_{+}]$ would immediately yield an improvement in the above theorem. In such nontrivial bounds were obtained for the $3$-regular tree $T_{3}$.

Suppose that $G$ is a finite, connected, $3$-regular, vertex-transitive graph. Then either $G$ is isomorphic to the complete graph $K_{4}$, or the least eigenvalue $\lambda_{\min}$ of its adjacency matrix is at most $-2$.

The proof below is due to Péter Csikvári.

Proof of Proposition .3 Let $G$ be a connected, $3$-regular, vertex-transitive graph with $\lambda_{\min}(G)>-2$. We need to show that $G$ must be the complete graph $K_{4}$.

Cauchy’s interlacing theorem implies that $\lambda_{\min}(G)\leq\lambda_{\min}(H)$ whenever $H$ is an induced subgraph of $G$. Therefore $\lambda_{\min}(H)>-2$ must hold for any induced subgraph. Let $T$ denote the tree shown in Figure 2. It is easy to see that the smallest eigenvalue of $T$ is $-2$. We also have $\lambda_{\min}(C_{2k})=-2$ for the cycle of length $2k$ for any $k\geq 2$. Therefore $G$ can contain neither $T$, nor $C_{2k}$ as an induced subgraph.

We will distinguish three cases. {longlist}[Case 3.]

Let $u,v$ be two neighboring vertices, and let $u_{1},u_{2}$ and $v_{1},v_{2}$ denote the remaining two neighbors of $u$ and $v$, respectively. Since $G$ contains no triangles, $u_{1}$, $u_{2}$, $v_{1}$, $v_{2}$ are pairwise distinct vertices. The induced subgraph on the set $\{u,u_{1},u_{2},v,v_{1},v_{2}\}$ must be isomorphic to $T$ (the graph shown in Figure 2), otherwise $G$ would contain a triangle or an induced $C_{4}$. Since $G$ cannot contain $T$ as an induced subgraph, this is a contradiction.