Let $G_q$ be a Paley graph on $q$ vertices, where $q=1 \text{ (mod 4)}$, i.e., the vertices of $G_q$ are the elements of the finite field $\mathbb{F}_q$, and there is an edge between vertices $a,b \in \mathbb{F}_q$ if and only if $a-b$ is the square of an element in $\mathbb{F}_q$. It is known that $G_q$ is a strongly regular graph with parameters \begin{align*} (v,k,\eta,\mu) = \left( q, \frac{q-1}{2}, \frac{q-5}{4}, \frac{q-1}{4}\right), \end{align*} and thus the second eigenvalue (in absolute value) of $G_q$ is $\frac{-1+\sqrt{q}}{2}$.
Consider the random subgraph $\tilde G_q$ of $G_q$, which is the induced subgraph generated by eliminating the vertices i.i.d. with probability $1-p$. I am trying to show that the scaling of the second eigenvalue of $\tilde G_q$ for large $q$ is $O(\sqrt{pq})$. The reason I think this might be true is that because $G_q$ is strongly regular, for large $q$, $\tilde G_q$ will be "close" to a strongly regular graph with parameters $\left( pq, p\frac{q-1}{2}, p\frac{q-5}{4}, p\frac{q-1}{4}\right)$, and thus its spectrum should behave like this reduced strongly regular graph.
I have been thinking of upper bounding the maximum eigenvalue of the "perturbation matrix" that would be required to convert the adjacency matrix of $\tilde G_q$ to the reduced strongly regular graph, and then use Weyl's inequality to show that the spectra are close, but I could not get it to work. Any ideas will be appreciated.
Update: Adding experimental plot comparing the second eigenvalue of the random induced subgraph, second eigenvalue of Erdos-Renyi $G(pq, 0.5)$ graph, and $\sqrt{p}\frac{-1+\sqrt{q}}{2}$. For $p > 0.5$, the second eigenvalue converges to its value for the full Paley graph, which can be shown by the interlacing theorem and the fact that the eigenvalues of the full Paley graph are given by
- $\frac{1}{2}(q-1)$ with multiplicity 1,
- $\frac{-1+\sqrt{q}}{2}$, with multiplicity $\frac{1}{2}(q-1)$,
- $\frac{-1-\sqrt{q}}{2}$, with multiplicity $\frac{1}{2}(q-1)$.
However, the interlacing theorem does not help when $p<0.5$, which is the regime I am more interested, and in this regime the second eigenvalue behaves close to that of a $G(pq, 0.5)$ graph.
Update 2: Following Furedi & Komlos '80 result on the eigenvalues of i.i.d. random matrices, I have done the following:
Let $A$ be the matrix such that $A_{ii}=0$, and for $i \neq j$, $A_{ij}=1$ if $\{i,j\}$ is an edge in $G_q$, $A_{ij}=-1$ otherwise (it is easy to map the eigenvalues of this matrix to the eigenvalues of the adjacency matrix of $G_q$). Define $J_i$ as the 0-1 indicator random variable representing whether vertex $i$ survives in $\tilde G_q$. Then, setting $\tilde A_{ij} = \chi(i-j)J_i J_j$,
\begin{align} \mathbb{E}\left[ \sum_{i=1}^q \lambda_i^k \right] &= \mathbb{E}\left[\text{tr}(\tilde A^k) \right] = \sum_{i_1=1}^q \sum_{i_2=1}^q \cdots \sum_{i_k=1}^q \mathbb{E}\left[ \tilde A_{i_1 i_2} \tilde A_{i_2 i_3}\cdots \tilde A_{i_k i_1} \right] \notag\\ &= \sum_{i_1=1}^q \sum_{i_2=1}^q \cdots \sum_{i_k=1}^q \chi(i_1-i_2)\chi(i_2-i_3) \cdots \chi(i_k-i_1) \mathbb{E} \left[ J_{i_1}J_{i_2}\cdots J_{i_k} \right] \notag\\ &=\sum_{s=1}^k p^s\sum_{\substack{i_1,i_2,\dots,i_k \\ \left| \{ i_1,i_2,\dots,i_k\}\right|=s}} \chi(i_1-i_2)\chi(i_2-i_3) \cdots \chi(i_k-i_1) \;\;\;\;\;\;(*), \end{align} where $s$ is the number of unique values in the set $\{ i_1,i_2,\dots,i_k\}$, and $\chi(\cdot)$ is the quadratic residue character in $\mathbb{F}_q$, i.e., \begin{align*} \chi(x) = \left\{ \begin{array}{ll} 0, & \text{if $x=0$}, \\ 1, & \text{if $x \neq 0$ is a quadratic residue in $\mathbb{F}_q$}, \\ -1, & \text{otherwise} \\ \end{array} \right. \end{align*}
The goal is to eventually use Markov inequality in the following way \begin{align*} \mathbb{P}\left( \max_i \lambda_i > a\right) = \mathbb{P}\left( \max_i \lambda_i^k > a^k\right) \leq \mathbb{P}\left( \sum_i \lambda_i^k > a^k\right) \leq \frac{\mathbb{E}\left[ \sum_i \lambda_i^k\right]}{a^k}, \end{align*}
where $k$ is an appropriately chosen function of $n$. What I am trying to show is that in the sum over $s$ in $(*)$, the dominating term should be the one with $s=k/2$, as in the paper with Furedi & Komlos. However, I don't know how to deal with the character sum term, since I don't know much about character sums or number theory. I am aware of Weil's bound, I am not sure if it's useful here. Any help/pointers would be appreciated.
Update 3: I have realized the following identities (can be proven by induction), which should be helpful in analyzing the trace expression above. With these identities in hand, this should reduce to a combinatorial counting problem, but I still could not finalize the argument despite many efforts. Any help will be greatly appreciated.
\begin{align*} \sum_{x_1,\dots, x_{k-1} \in \mathbb{F}_q} \chi(a-x_1)\chi(x_1-x_2)\dots\chi(x_{k-1}-b) = \left\{ \begin{array}{ll} -q^{\frac{k-2}{2}}, & a \neq b\\ (q-1)q^{\frac{k-2}{2}}, & a=b \end{array} \right. \end{align*} if $k$ is even, and \begin{align*} \sum_{x_1,\dots, x_{k-1} \in \mathbb{F}_q} \chi(a-x_1)\chi(x_1-x_2)\dots\chi(x_{k-1}-b) = \chi(a-b) \end{align*} if $k$ is odd.
