HW7

1. Determine all equitable bipartitions of the hypercube $\{0,1{\}}^n$ such that the corresponding quotient matrix has eigenvalues $n$ and $n-2$.

\begin{proof} Recall that hypercube $Q_n$ has vertices $V(Q_n)=\{0,1{\}}^n$, where $\{x,y\}\in \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ iff $x_i\ne y_i$ for exactly one position.

We call the partition equitable if $A_{ij}\vec{j}=b_{ij}\vec{j}$ for all $i,j$, where $\vec{j}=(1,\cdots ,1{)}^T$.

Link to original

原来 bipartition 是分两块的意思。。。

Let $V(Q_n)=C_1\bigsqcup C_2$ be a bipartition. Then $A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)$, where ${\sum }_j{a}_{ij}+{\sum }_k{b}_{\ell k}=n$, where $A_{11}=(a_{ij})$ and $A_{12}=(b_{\ell k})$. Then the quotient matrix $B=\left(\begin{array}{cc}a& n-a\\ b& n-b\end{array}\right)$ for some $a,b\in [n]$. Notice that $(1,1{)}^T$ is an eigenvector of $B$ with eigenvalue $n$, which implies $a+n-b=n+n-2$. Hence $a\in \{n-2,n-1,n\}$. If $a=n-2$ or $n$, then $B$ has an entry $0$, which contradicts with $Q_n$ connected. So $a=n-1$ and $B=\left(\begin{array}{cc}n-1& 1\\ 1& n-1\end{array}\right)$.

Take $C_1=\{(0,e):e\in \{0,1{\}}^{n-1}\}\cong Q_{n-1}$ and $C_2=V(Q_n)\setminus C_1$. Then $A_{11}$ is the adjacent matrix of $Q_{n-1}$ and so $b_{11}=n-1$, $b_{12}=1$. Since $|C_1|=|C_2|=2^{n-1}$ and $Q_n$ is a $n$-regular graph, we have $b_{21}=1$ and so $b_{22}=n-1$. Using similar construction, that is, fix one coordinate $j$ and

• take $C_1=\{x\in Q_n:x_j=0\}$ and $C_2=\{x\in Q_n:x_j=1\}$, or
• take $C_1=\{x\in Q_n:x_j=1\}$ and $C_2=\{x\in Q_n:x_j=0\}$.

Then we get $2n$ bipartitions such that the corresponding quotient matrix has eigenvalues $n$ and $n-2$.

It remains to check there does exist no other bipartition. Since $A_{21}\vec{j}=b_{21}\vec{j}$, we know each row of $A_{21}$ has exactly one $1$ and so for $A_{12}$. Then there exists a $1$-$1$ correspondence between elements of set $C_1$ and $C_2$. Assume that $C_1=\{x_1,\cdots ,x_t\}$ and $C_2=\{y_1,\cdots ,y_t\}$, where $x_i\sim y_i$ and $x_i\nsim y_j$ for any $i\ne j$. If $x_1-y_1=(1,0,\cdots ,0)$, then $x_1+e_k\in C_1$ and $y_1+e_k\in C_2$ for any $k\ne 1$, where $\{e_1,\cdots ,e_n\}$ is the standard basis. Repeat this procedure, we know $x_i-y_i=(1,0,\cdots ,0)$ for all $i\in [t]$. Now we finish the proof. \end{proof}

2. Consider a polarity $\perp$ of a projective plane $(\mathcal{P},\mathcal{L},\mathrm{I})$ of order $m$.

• (a) Define a graph $\Gamma$ with vertex set $\mathcal{P}$, two points $P,Q$ adjacent if $P\in Q^{\perp }$. Determine the spectrum of $\Gamma$. Note that $\Gamma$ has loops.
• (c) Let $\Delta$ be the induced subgraph of $\Gamma$ obtained by removing all vertices adjacent to themselves. Show that the spectrum of $\Delta$ is in $[-\sqrt{m},\sqrt{m}]\cup \{m+1\}$.

\begin{proof} Recall that a polarity $\pi$ is a bijection that sends points to lines and lines to points, $P\mathbf{I}L\iff P^{\pi }\mathbf{I}{L}^{\pi },{\pi }^2=\mathrm{id}$.

$n$ is called the order of the projective plane $\mathcal{G}=(\mathcal{P},\mathcal{L},I)$.

Link to original

a) Let $A$ be a adjacent matrix. Then $A^2$ satisfies $(A^2{)}_{ii}=m+1$ and $(A^2{)}_{ij}=1$ as two lines has exactly one common point. Hence $A^2=mI+J$.

Note that $A\vec{j}=(m+1)\vec{j}$, then $m+1$ is an eigenvalue of $A$. For any eigenvector $x\in {⟨\vec{j}⟩}^{\perp }$ of $A$, we assume that $Ax=\lambda x$. Since $Jx=0$, we have $A^{2}x=mx={\lambda }^{2}x$. So $\lambda =\pm \sqrt{m}$. Therefore, $\mathrm{Spec}(A)=\{m+1,{\sqrt{m}}^r,-{\sqrt{m}}^s\}$.

Since $\mathrm{tr}(A^2)=(m+1)(m^2+m+1)=(m+1{)}^2+(r+s)m$, we have $r+s=m^2+m$. If $m$ is not a perfect square, then by $\mathrm{tr}(A)\in \mathbb{N}$ we have $r=s=(m^2+m)/2$. If $m$ is a perfect square, then $\mathrm{Spec}(A)=\{m+1,{\sqrt{m}}^r,-{\sqrt{m}}^s\}$, where $r+s=m^2+m$.

c) Let $B$ be a adjacent matrix of $\Delta$. Recall that

If $B$ is a principal submatrix of $A$, then the eigenvalues of $B$ interlace the eigenvalues of $A$.

Link to original

Then we know the eigenvalue of $B$ interlace the eigenvalues of $A$. Let ${\mu }_1,\cdots ,{\mu }_k$ be all eigenvalues of $\Delta$. Then ${\mu }_i\in [-\sqrt{m},\sqrt{m}]$ for $2⩽i⩽k$.

It remains to show ${\mu }_1\in [-\sqrt{m},\sqrt{m}]\cup \{m+1\}$. GPT 告诉我这里有一个反例：

Take the projective plane $PG(2,2)$. Define $⟨x,y⟩=x_1{y}_1+x_2{y}_2+x_3{y}_3$, and define $Q^{\perp }=\{P:⟨P,Q⟩=0\}$. Since $⟨x,y⟩=⟨y,x⟩$, we have $P\mathbf{I}L\iff P^{\pi }\mathbf{I}{L}^{\pi }$. Since $⟨x,y⟩=x_1{y}_1+x_2{y}_2+x_3{y}_3$ is non-degenerated, $\ker Q=Q^{\perp }$ has dimension $2$ and so $\ker (\ker Q)=Q$. Hence $\perp$ is a polarity.

There are three vertices adjacent to themselves, and so $|V(\Delta )|=4$. Note that $\Delta =K_3\bigsqcup K_1$. Let $B$ be a adjacent matrix of $\Delta$. Then $\mathrm{Spec}B=\{2,-1,-1,0\}$. Since $m=2$, the spectrum of $\Delta$ is NOT in $[-\sqrt{m},\sqrt{m}]\cup \{m+1\}$. \end{proof}

3.

• (a) Determine the spectrum of the point-line incidence graph of $PG(2,q)$.
• (b) We call a collection $\mathcal{S}=\{S_1,S_2,\dots \}$ of $k$-subsets of points of $PG(2,q)$ a $k$-uniform local arc if the $S_i$ are pairwise disjoint, and $S_i\cup S_j$ is an arc. Show that for $k$ fixed,

$$\left|\bigcup _{S_i\in \mathcal{S}}{S}_i\right|\le \left(\frac{\sqrt{2}}{\sqrt{k-1}}+o(1)\right)q^{1.5}.$$

\begin{proof} a) Let $A$ be a adjacent matrix of the point-line incidence graph. Then $A=\left(\begin{array}{cc}0& N\\ N^T& 0\end{array}\right)$, where $N$ is the point-line incidence matrix. Note that both $N$ and $N^T$ have eigenvector $\vec{j}=(1,\cdots ,1)$, then $\vec{j}$ is an eigenvector of $A$ with eigenvalue $q+1$.

Assume that $(v,w{)}^T$ is an eigenvector of $A$, then $A(v,w{)}^T=(Nw,N^{T}v{)}^T=(\lambda v,\lambda w{)}^T$. It follows that $N^{T}Nw={\lambda }^{2}w$ and $N{N}^{T}v={\lambda }^{2}v$.

Since $N{N}^T=qI+J$, the spectrum of $N{N}^T$ is $\{q^2+2q+1,q^{n-1}\}$, where $n=q^2+q+1$. So $\mathrm{Spec}A=\{q+1,-(q+1),{\sqrt{q}}^{n-1},-{\sqrt{q}}^{n-1}\}$ by ^vnqcpz.

b) 白给的尝试：Assume that $V(PG(2,q))=\{p_1,\cdots ,p_n\}$ and $E(PG(2,q))=(e_1,\cdots ,e_n)$ such that $N=(n_{ij})$ where $n_{ij}=1$ iff $p_i\sim e_j$. Let $v=(x_1,\cdots ,x_n)$, where $x_i=1$ if $p_i\in {\cup }_{S_i\in \mathcal{S}}{S}_i$. Then $vN=(y_1,\cdots ,y_n)$, where $y_i=|L_i\cap ({\cup }_{S_i\in \mathcal{S}}{S}_i)|$. We also have $N^T{v}^T=(y_1,\cdots ,y_n{)}^T$ and so $(q+u)\Vert v^2\Vert =vN{N}^T{v}^T=\Vert \vec{y}{\Vert }^2$, where $u=|{\cup }_{S_i\in \mathcal{S}}{S}_i|$ and $\vec{y}=(y_1,\cdots ,y_n)$. By ^ja6tar, we know $vN{N}^t{v}^T/\Vert v{\Vert }^2⩽(q+1{)}^2$ and so $u⩽n$.

Let $\mathcal{S}=\{S_1,\dots ,S_t\}$ be a $k$-uniform local arc, and let $U={\cup }_{i=1}^t{S}_i$. Then $|U|⩽kt$. Note that the point-line incidence graph of $PG(2,q)$ is $(q+1)$-regular and ${\lambda }_2=\sqrt{q}$ by a). By ^dhoh0u, for any set $X$ of points and any set $Y$ of lines, we have

$$\left|E(X,Y)-\frac{(q+1)|X||Y|}{q^2+q+1}\right|⩽\sqrt{q}\sqrt{\frac{|X||Y|(n-|X|)(n-|Y|)}{n^2}}⩽\sqrt{q}\sqrt{|X||Y|},\text{\hspace{1em}(*)}$$

where $n=q^2+q+1$. Define $T=\{\ell :\ell \text{ contains two points of some }{S}_i\}$. Since $S_i\cup S_j$ is an arc, $S_i$ is also an arc and then each $S_i$ determines exactly $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ secant lines. Note that $|L\cap U|=2$ for any $L\in \mathcal{T}$, which follows that $E(U,T)=2|T|$. By $(\ast )$ we have

$$\frac{(q+1)|U||T|}{q^2+q+1}⩽2|T|+\sqrt{q}\sqrt{|U||T|}.$$

Furthermore, $|T|=t\left(\genfrac{}{}{0ex}{}{k}{2}\right)⩾|U|(k-1)/2$, then we have

$$\frac{(q+1)|U|}{q^2+q+1}⩽2+(q+1)\sqrt{|U|/|T|}⩽2+\sqrt{q}\sqrt{\frac{2}{k-1}}.$$

So

$$|U|⩽\frac{q^2+q+1}{q+1}\left(2+\sqrt{q}\sqrt{\frac{2}{k-1}}\right)=\left(\frac{\sqrt{2}}{\sqrt{k-1}}+o(1)\right)q^{1.5}.$$

Now we finish the proof. \end{proof}

4. Consider the odd cycles $C_{2m+1}$, where $m\ge 1$.

• (a) Use the ratio bound to show that $\alpha (C_{2m+1})\le m$.
• (b) Use the inertia bound to show that $\alpha (C_{2m+1})\le m$.
• (c) Show that both bounds are tight.

\begin{proof} a) Recall that $\alpha (\Gamma )$ is the independence number of $\Gamma$. Since the minimal eigenvalue of $C_{2m+1}$ is $-2$ by ^mt7vc7, there is $\alpha (C_{2m+1})⩽\frac{2}{4}(2m+1)=\frac{2m+1}{2}$ by ^j2qp40. Since $\alpha (C_{2m+1})\in \mathbb{N}$, we have $\alpha (C_{2m+1})⩽m$.

b) By ^s7pdtq, $\alpha (C_{2m+1})⩽\min \{n-n_{-},n-n_{+}\}$. Since there does not exist $j$ such that $\cos (2\pi j/(2m+1))=0$, we have $\min \{n-n_{-},n-n_{+}\}=m$. Therefore, $\alpha (C_{2m+1})⩽m$.

c) Assume that $V(C_{2m+1})=\{v_1,\cdots ,v_{2m+1}\}$, where $v_i\sim v_{i+1}$ and $v_{2m+1}\sim v_1$. Then $\{v_{2k}:1⩽k⩽m\}$ is an independent set and so both bounds are tight. \end{proof}

5. Consider the Johnson graph $J(n,3)$, whose vertices are the $3$-subsets of $\{1,\dots ,n\}$, with two vertices adjacent when their intersection has size $2$. Let $A$ be its adjacency matrix.

• (a) Show that $J(n,3)$ is regular of degree $3(n-3)$.
• (b) Determine the number of common neighbors of two vertices $X,Y$, depending on $|X\cap Y|=0,1,2,3$.
• (c) Write $A^3$ as a linear combination of $J,I,A,A^2$.
• (d) Determine the spectrum of $A$.

\begin{proof} a) For each point $P_0:=\{i,j,k\}$, consider the neighborhoods of $P_0$. If $P\sim P_0$ and $P\cap P_0=\{i,j\}$, then there are $(n-3)$‘s $\ell$ such that $P=\{i,j,\ell \}$. Similarly for $P\cap P_0=\{i,k\}$ and $P\cap P_0=\{j,k\}$. So $J(n,3)$ is regular of degree $3(n-3)$.

b) It is easy to check that

• if $|X\cap Y|=0$, then the number of common neighbors of $X,Y$ is $0$;
• if $|X\cap Y|=1$, then the number of common neighbors of $X,Y$ is $4$;
• if $|X\cap Y|=2$, then the number of common neighbors of $X,Y$ is $n-2$;
• if $|X\cap Y|=3$, then the number of common neighbors of $X,Y$ is $3(n-3)$.

c) By b) we have

$$(A^2{)}_{XY}=\{\begin{array}{ll}0,& |X\cap Y|=0,\\ 4,& |X\cap Y|=1,\\ n-2,& |X\cap Y|=2,\\ 3(n-3),& X=Y.\end{array}$$

Recall that $(A^3{)}_{XY}$ is the number of $3$-walks from $X$ to $Y$, then we have

$$(A^3{)}_{XY}=\{\begin{array}{ll}36,& |X\cap Y|=0,\\ 12n-40,& |X\cap Y|=1,\\ n^2+7n-37,& |X\cap Y|=2,\\ 3(n-3)(n-2),& X=Y.\end{array}$$

The cases of $|X\cap Y|=0,1,3$ are easy to check. When $|X\cap Y|=2$, take $v_1=\{i,j,k\}$ and $v_4=\{i,j,\ell \}$. Then

• $v_2=\{i,j,m\}$ with $m\ne i,j,k,\ell$, and $v_3$ has $n-2$ choices;
• $v_2=\{i,j,\ell \}$, and $v_3$ has $3(n-3)$ choices;
• $v_2=\{i,m,k\}$ with $m\ne i,j,k,\ell$, and $v_3$ has 4 choices;
• $v_2=\{i,\ell ,k\}$, and $v_3$ has $n-2$ choices.

Therefore, one obtains the following table:

$$\begin{array}{ccccc}|X\cap Y|& J_{XY}& I_{XY}& A_{XY}& (A^2{)}_{XY}\\ 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 4\\ 2& 1& 0& 1& n-2\\ 3& 1& 1& 0& 3(n-3)\end{array}$$

Solving for constants $a,b,c,d$ such that $A^3=aJ+bI+cA+d{A}^2$, we get

$$A^3=36J+(3n-19)A^2-(2n^2-32n+111)A-(6n^2-69n+189)I.$$

d) Since $J(n,3)$ is regular of degree $3(n-3)$, $\vec{j}=(1,\cdots ,1)$ is an eigenvector with eigenvalue $3(n-3)$.

On the subspace orthogonal to the all-one vector, we have $J=0$. So every non-principal eigenvalue $\theta$ satisfies

$${\theta }^3-(3n-19){\theta }^2+(2n^2-32n+111)\theta +(6n^2-69n+189)=0.$$

by c). Note that this factors as

$$(\theta -(2n-9))(\theta -(n-7))(\theta +3)=0.$$

Therefore, the eigenvalues are $3(n-3)$, $2n-9$, $n-7$ and $-3$.

Assume that these multiplicities are $1,f_1,f_2,f_3$, respectively. Then we have $1+f_1+f_2+f_3=\left(\genfrac{}{}{0ex}{}{n}{3}\right)$,

$$3(n-3)+f_1(2n-9)+f_2(n-7)-3f_3=0,$$

and

$$9(n-3{)}^2+f_1(2n-9{)}^2+f_2(n-7{)}^2+9f_3=(\genfrac{}{}{0ex}{}{n}{3})3(n-3).$$

Therefore, we have

$$\mathrm{Spec}(A)=\left\{3(n-3{)}^1,(2n-9{)}^{n-1},(n-7{)}^{\frac{n(n-3)}{2}},(-3{)}^{\frac{n(n-1)(n-5)}{6}}\right\}.$$

Now we finish the solution. \end{proof}

6. Determine existence or nonexistence for each of the following SRG parameters:

• (a) $(10,4,1,2)$,
• (b) $(15,8,4,4)$,
• (c) $(16,6,2,2)$,
• (d) $(21,8,1,4)$,
• (e) $(28,9,0,4)$,
• (f) $(50,21,4,12)$.

\begin{proof} Recall that ^bebz6b and ^peg7jo.

a) Since $(v-k-1)\mu =(10-4-1)2=10$ and $k(k-\lambda -1)=4(4-1-1)=8$, such SRG does not exist.

b) $J(6,2)$ is an example.

c) The Shrikhande graph is an example.

d) Eigenvalues are $r=1$ and $s=-4$. Then $f=(-3\times 8\times 12)/(-4\times 5)$ is not an integer and so such SRG does not exist.

e) One can compute that $r=1$, $s=-5$, $f=21$, and $g=6$. Since $v⩽\left(\genfrac{}{}{0ex}{}{g+2}{2}\right)-1$ does not hold, by absolute bound such SRG does not exist.

f) One can compute that $r=1$, $s=-9$, $f=42$, and $g=7$. Since $v⩽\left(\genfrac{}{}{0ex}{}{9}{2}\right)-1$ does not hold, by absolute bound such SRG does not exist. \end{proof}