12
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Just a note: Another way to prove this could possibly be by showing that (at least for small $p$) the induced subgraph is essentially like an Erdos-Renyi graph with $O(pq)$ vertices and edge probability 0.5, and thus the second eigenvalue is $O(\sqrt{pq})$. $\endgroup$
    – karakusc
    Jan 8, 2017 at 6:22

1 Answer 1

1
$\begingroup$

Sir-

I would leave this as a comment, but I cannot comment. The following references allude to the method you subscribe- apply Weyl's inequality to receive a bound on each of the eigenvalues. If $\Delta$ is the maximum expected degree and $\bar A$ is the expected adjacency matrix (i.e., p times adjacency matrix of your graph) and $A$ is the realized adjacency matrix , then [4] below gives under mild conditions $| \lambda_2(\bar A) - \lambda_2(A)| < 2(1+o(1)) \sqrt{\Delta} $ with probability $\to 1$ as $n \to \infty$. In your case, it suggests that $| \lambda_2(\bar A) - \lambda_2(A)| < 2(1+o(1)) \sqrt{\frac{(q-1) p}{2}}$. In other words, your desired outcome is correct upto a factor of $\sqrt{p}$.

  1. Internet Mathematics Vol. 4, No. 2–3: 225–244

    The Spectral Gap of a Random Subgraph of a Graph

    Fan Chung and Paul Horn

  2. arXiv:0911.0600

    Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

    Roberto Imbuzeiro Oliveira

  3. The Electronic Journal of Combinatorics, 18(P215):1, 2011.

    Fan Chung and Mary Radcliffe.

    On the spectra of general random graphs.

  4. the electronic journal of combinatorics, 20(4), p.P27.

    Spectra of edge-independent random graphs.

    Linyuan Lu and Xing Peng

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.