Weight distribution bounds and Fields

Proof. Suppose $Ac=\theta c,\theta \ne 0$ where $c$ is a nonzero vector indexed by the vertices. For every vertex $v$, denote the neighborhood $N(v)$ as the set of all adjacent vertices, and $$\sum _{w\in N(v)}{c}_w=\theta c_v.$$

Define the support: $$S=\{v\in V:c_v\ne 0\},s=|S|.$$

Also, $d_v=|N(v)\cap S|$, denoting the number of neighbors of $v$ that belong to the support.

Finally, denote the number of edges contained entirely within the support as $$e=|E(\Gamma [S])|.$$

Take $v\in S$. By definition, $c_v\ne 0$. Since $\theta \ne 0$, then $\theta c_v\ne 0$$$\Rightarrow \sum _{w\in N(v)}{c}_w=\theta c_v\ne 0.$$

Therefore, $v\in S\Rightarrow d_v\ge 1$, i.e. the induced graph $\Gamma [S]$ contains no isolated vertices.

Since a support consisting of only one vertex would have an isolated vertex, we know $s\ge 2$.

Also, the handshake lemma states that $$2e=\sum _{v\in S}{d}_v$$ and since every $d_v\ge 1$, $$2e\ge s\Rightarrow \boxed{e\ge \lceil \frac{s}{2}\rceil }.$$

Now take $v\notin S$. Since $c_v=0$, we have$$\sum _{w\in N(v)}{c}_w=0,\text{or equivalently, }\sum _{w\in N(v)\cap S}{c}_w=0.$$

Suppose $v$ has exactly one neighbor in $S$, that is, $N(v)\cap S=\{u\}$. Then $c_u=0$ contradicting $u\in S$. Hence$$\boxed{v\notin S\Rightarrow d_v\ne 1}.$$

Let’s now inspect only vertices with exactly two neighbors within the support. Define $$n_2=\#\{v\notin S:d_v=2\}.$$

Every support vertex has degree $k$. There are $s$ support vertices, so the total number of incident edge$\sim$end pairs is $ks$. The number of edges leaving $S$ is $D:=ks-2e$.

Now suppose a vertex $v$ has $d_v$ neighbors inside $S$. We can form exactly $\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)$ unordered pairs from these neighbors. Consider$$W=\sum _{v\in V}\left(\genfrac{}{}{0ex}{}{d_v}{2}\right).$$

We can count this in an alternative method. Let $\{u,w\}$ be a pair of distinct support vertices. Since the graph is strongly regular, if $u\sim w$ they share $\lambda$ common neighbors, and if $u\nsim w$ they share $\mu$ common neighbors. There are $e$ adjacent pairs inside $S$ and $\left(\genfrac{}{}{0ex}{}{s}{2}\right)-e$ nonadjacent pairs. Thus, $$W=\lambda e+\mu ((\genfrac{}{}{0ex}{}{s}{2})-e)=\boxed{\mu \left(\genfrac{}{}{0ex}{}{s}{2}\right)+(\lambda -\mu )e}.$$

Now, consider the contributions individually from the support vertices and non-support vertices. Let $$W=W_{in}+W_{out}=\sum _{v\in S}\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)+\sum _{v\notin S}\left(\genfrac{}{}{0ex}{}{d_v}{2}\right).$$

Recall that $v\in S\Rightarrow d_v\ge 1$. For every integer $d\ge 1,\left(\genfrac{}{}{0ex}{}{d}{2}\right)\ge d-1$. Thus, $$W_{in}=\sum _{v\in S}\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)\ge \sum _{v\in S}(d_v-1)=2e-s.$$

Substituting, $$\boxed{W_{out}\le \mu \left(\genfrac{}{}{0ex}{}{s}{2}\right)+(\lambda -\mu )e-2e+s}.$$

Consider the difference $d_v-\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)$. For integer $d$, this difference achieves positive contribution at $d_v=1,2$ where $d_v-\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)=1$. So $$1\ge d_v-\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)$$for every $v\notin S$ when $d_v=2$ and zero otherwise (since $d_v\ne 1)$.

Take the sum:$$n_2\ge \sum _{v\notin S}\left(d_v-\left(\genfrac{}{}{0ex}{}{d_v}{2}\right)\right)=D-W_{out}$$$$\ge ks-2e-\left(\mu \left(\genfrac{}{}{0ex}{}{s}{2}\right)+(\lambda -\mu )e-2e+s\right)=(k-1)s-\mu \left(\genfrac{}{}{0ex}{}{s}{2}\right)+(\mu -\lambda )e.$$

Recall that every outside vertex with exactly two support neighbors $u,w$ satisfies $c_u+c_w=0$, or $c_u=-c_w$. Let’s call such $\{u,w\}$ an opposite-value pair, which are unique to witnesses.

Define:$$b_1=\text{number of witnessed pairs }u\sim w$$$$b_0=\text{number of witnessed pairs }u\nsim w.$$

It follows that $n_2\le \lambda b_1+\mu b_0$, in addition to $b_1\le e,b_0\le \left(\genfrac{}{}{0ex}{}{s}{2}\right)-e$.

Construct a graph $H$ with vertex set $S$. We join $u,w$ when some vertex $v\notin S$ has $N(v)\cap S=\{u,w\}$. Thus, each edge in $H$ is an opposite-value pair. Note that $H\ne \Gamma [S]$.

Suppose $H$ contains an odd cycle, then$$v_1\sim v_2\sim \cdots \sim v_{2m+1}\sim v_1.$$

However, since these are opposite value pairs, $$c_{v_2}=-c_{v_1},c_{v_3}=c_{v_1},\dots ,c_{v_{2m+1}}=c_{v_1}$$which implies that $2c_{v_1}=0$. But $v_1\in S$, so $c_{v_1}\ne 0$, and since we operate in ${\mathbb{F}}_p,p\ne 2$, $2\ne 0$.

Therefore $H$ has no odd cycles and by definition is a bipartite graph.

Mantel’s bound states that any bipartite graph on $s$ vertices has at most $\lfloor \frac{s^2}{4}\rfloor$ edges. $H$ has exactly $b_1+b_0$ edges, so therefore $$b_1+b_0\le \lfloor \frac{s^2}{4}\rfloor .$$

Combining the upper and lower bounds on $n_2$, we obtain$$(k-1)s-\mu \left(\genfrac{}{}{0ex}{}{s}{2}\right)+(\mu -\lambda )e\le n_2\le \lambda b_1+\mu b_0.$$

It remains to establish the upper bound on $e$. Since any two adjacent vertices have exactly $\lambda$ common neighbors, a clique can contain at most $\lambda +2$ vertices, thus $\Gamma [S]$ contains no clique of size $\lambda +3$. By Turàn’s Theorem, $$e\le \lfloor \frac{(\lambda +1)s^2}{2(\lambda +2)}\rfloor .$$

Together with the trivial bound, this yields $e\le E_s$. We have therefore shown that the integers $s,e,b_0,b_1$ satisfy every inequality in the definition of $B$. Since $B$ is the smallest integer $s$ for which such a choice is possible, we must have $s\ge B$.

Hence, every nonzero eigenvector $c$ has at least $B$ nonzero entries.