HW6

1. Let $\mathcal{D}$ be a $2$-$(v,k,\lambda )$ design with $b$ blocks and $r$ blocks through every point. Let $B$ be any block. Show that the number of blocks that meet $B$ (excluding $B$ ) is at least

$$k(r-1{)}^2/[(k-1)(\lambda -1)+(r-1)].$$

Show that equality holds if and only if any block not disjoint from $B$ meets it in a constant number of points.

\begin{proof} Let $\mathcal{S}=\{B^{\prime }\in \mathcal{B}:B^{\prime }\cap B\ne \varnothing \}$. Consider the tuples $(v,w,B^{\prime })$ such that $B^{\prime }\ne B$, $v,w\in B^{\prime }$. Fix $v\in B$, then

$$|(v,w,B^{\prime })|=|(v,v,B^{\prime })|+|(v,w,B^{\prime }):v\ne w|=r-1+(k-1)(\lambda -1).$$

So number of such triples $=k(r-1+(k-1)(\lambda -1))$.

For each $B^{\prime }\in \mathcal{S}$, define $f(B^{\prime })=|B\cap B^{\prime }|$. Consider the tuples $(v,B,B^{\prime })$ with $v\in B\cap B^{\prime }$. Then we have $|(v,B,B^{\prime })|=k(r-1)={\sum }_{B^{\prime }\in \mathcal{S}}f(B^{\prime }).$

On the other hand, the number of triples $(v,w,B^{\prime })={\sum }_{B^{\prime }\in \mathcal{S}}f(B^{\prime }{)}^2⩾({\sum }_{B^{\prime }\in \mathcal{S}}f(B^{\prime }){)}^2/|\mathcal{S}|$. Hence

$$|\mathcal{S}|⩾k^2(r-1)/k(r-1+(k-1)\lambda -1)=k(r-1{)}^2/[(k-1)(\lambda -1)+(r-1)].$$

Now we finish the proof. \end{proof}

2. A Latin square of order $n$ is a quadruple ( $R,C,S;L$ ) where $R,C$, and $S$ are sets of cardinality $n$ and $L$ is a mapping $L:R\times C\to S$ such that for any $i\in R$ and $x\in S$, the equation

$$L(i,j)=x$$

has a unique solution $j\in C$, and for any $j\in C,x\in S$, the same equation has a unique solution $i\in R{.}^1$ Here is an example of order 5 :

$$\left[\begin{array}{lllll}a& b& c& d& e\\ b& a& e& c& d\\ c& d& b& e& a\\ d& e& a& b& c\\ e& c& d& a& b\end{array}\right]$$

Define

$$B_{ij}:=\{\{(x,y)\in R\times C:x=i\text{ or }y=j\text{ or }L(x,y)=L(i,j)\}\backslash \{(i,j)\}$$

for $(i,j)\in R\times C$.

• (a) Show that a Latin square of order 6 defines a 2-(36, 15, 6) design with the blocks $B_{ij}$.
• (b) Show that for any other $n\ge 3$, the sets $B_{ij}$ do not form a 2-design.

\begin{proof} a) Define $v=|\{(i,j):1⩽i,j⩽6\}|=36$, and

$$\begin{array}{rl}|B_{ij}|& =|\{(i,y):y\ne j\}|+|\{(x,j):x\ne i\}|+|\{(x,y):L(x,y)=L(i,j),x\ne i,y\ne j\}|\\ & =5+5+5=15\end{array}$$

so blocks $B_{ij}$ are $15$-subsets.

For any $2$-subset $\{(x,y),(x^{\prime },y^{\prime })\}$, suppose that $B_{ij}\supseteq \{(x,y),(x^{\prime },y^{\prime })\}$, then one of the following holds.

• If $L(x,y)=L(x^{\prime },y^{\prime })$ and $(x,y)\ne (x^{\prime },y^{\prime })$, then
  • either $L(i,j)=L(x,y)=L(x^{\prime },y^{\prime })$, or
  • $i=x$ and $j=y^{\prime }$, or
  • $i=x^{\prime }$ and $j=y$.
  • There are $6$ blocks containing the $\{(x,y),(x^{\prime },y^{\prime })\}$.
• If $x=x^{\prime }$ or $y=y^{\prime }$, then $L(x,y)\ne L(x^{\prime },y^{\prime })$. WLOG $x=x^{\prime }$, then
  • $L(i,j)=L(x,y)$ and $j=y^{\prime }$, there is $1$ solution
  • $L(i,j)=L(x^{\prime },y^{\prime })$ and $j=y$, there is $1$ solution
  • $i=x=x^{\prime }$, $j\in [6]\setminus \{y,y^{\prime }\}$, there is $n-2=4$ solutions
  • Hence there are $6$ blocks containing the $\{(x,y),(x^{\prime },y^{\prime })\}$.
• If $L(x,y)\ne L(x^{\prime },y^{\prime })$ and $x\ne x^{\prime }$ and $y\ne y^{\prime }$
  • $L(i,j)=L(x,y)$ and $i=x^{\prime }$ or $j=y^{\prime }$, there are $2$ solutions for $(i,j)$
  • $L(i,j)=L(x^{\prime },y^{\prime })$ and $i=x$ or $j=y$, there are $2$ solutions for $i,j$
  • $i=x$ and $j=y^{\prime }$, or
  • $i=x^{\prime }$ and $j=y^{\prime }$.
  • There are $6$ blocks containing the $\{(x,y),(x^{\prime },y^{\prime })\}$.

Therefore, a Latin square of order 6 defines a 2-(36, 15, 6) design with the blocks $B_{ij}$.

b) By the argument in a), for any two points, they are contained in either $6$ blocks or $n$ blocks. So for any other $n\ge 3$, the sets $B_{ij}$ do not form a 2-design. \end{proof}

3. Let $\mathcal{H}$ be a hyperoval in $PG(2,q),q=2^m\ge 4$. Any of the $q^2-1$ points $P$ not in $\mathcal{H}$ has the property that there are exactly $\frac{1}{2}(q+2)$ secants of $\mathcal{H}$ through $P$. Take five points of $\mathcal{H}$ and split them into

$$\left\{\left\{P_1,P_2\right\},\left\{P_3,P_4\right\},\left\{P_5\right\}\right\}.$$

This can be done in $5\times \left(\genfrac{}{}{0ex}{}{4}{2}\right)/2=15$ ways. The two pairs determine two secants that meet a point $P$ not in $\mathcal{H}$. The line through $P$ and $P_5$ meets $\mathcal{H}$ in a second point $P_6$. This defines $15$ $6$-tuples on the points of $\mathcal{H}$, containing five given points.

• (a) Show that this defines a $5$-$(q+2,6,15)$ design.
• (b) Show for some $q$, a convenient choice of $P_1,P_2,P_3,P_4,P_5$, and the canonical hyperoval $\left\{\left(1,t,t^2\right):t\in {\mathbb{F}}_q\right\}\cup \{(0,1,0),(0,0,1)\}$ that this $5$-$(q+2,6,5)$ design is not simple, that is, it is has repeated blocks.

\begin{proof} a) Note that $\mathcal{H}$ contains $q+2$ points. Define blocks as the $6$-tuples defined above, then $k=6$. For each $5$-subset $\{P_1,\cdots ,P_5\}$, there are $15$ $6$-tuples containing these $5$ points, so $\lambda =15$. Therefore, this defines a $5$-$(q+2,6,15)$ design.

b) Take $q=4$, then $\mathcal{H}$ contains $6$ points and each block equals $\mathcal{H}$. Hence each choice of $P_1,P_2,P_3,P_4,P_5$ deduces the same $6$-tuples and so this design is not simple. \end{proof}

4. Show that a symmetric $2$-$(29,8,2)$ design does not exist.

\begin{proof} Recall that

b=\lambda{v\choose t}/{k\choose t}.

Link to original

then we have $b=29$. Hence $b=v$.

By

• $v$ odd $⟹$ $z^2=(k-\lambda )x^2+(-1{)}^{(v-1)/2}\lambda y^2$ has a solution $(x,y,z)\in {\mathbb{Z}}^3\setminus \{(0,0,0)\}$.

Link to original

if such design exists, then we know $z^2=6x^2+2y^2$ has a solution in ${\mathbb{Z}}^3\setminus \{(0,0,0)\}$. Then $2\mid z$ and we get $2z_1^2=3x^2+y^2$. Then $3\mid z_1$ and $3\mid y$, we get $6z_2^2=x^2+3y_1^2$. Then $3\mid x$ and $2z_2^2=3x_1^2+y_1^2$. This procedure can repeat infinitely many times, so it is impossible. \end{proof}

5. The Petersen graph has spectrum $3^1,1^5,(-2{)}^4$. Show that it is not possible to find three edge-disjoint copies of the Petersen graph in $K_{10}$.

\begin{proof} Assume that there are three edge-disjoint copies of the Petersen graph, then there are three $0$-$1$ matrices $A_1,A_2,A_3$ such that

$$A_1+A_2+A_3=J-I\in M_{10\times 10}(\mathbb{Z}).$$

Since Peterson graph is $3$-regular, each $A_i$ has an eigenvector $\vec{j}$ with eigenvalue $3$. For any $v\in ⟨\vec{j}{⟩}^{\perp }$, we have $(J-I)v=-v$. Then in $⟨\vec{j}{⟩}^{\perp }$, $A_1+A_2+A_3=-I$.

Let $E_1$ and $E_2$ be eigenspaces of $A_1$ and $A_2$ with eigenvalue $1$, then $\dim (E_1)=\dim (E_2)=5$. Since $\dim ⟨\vec{j}⟩=9$ and $E_1,E_2\subseteq ⟨\vec{j}⟩$, there exists $v\in ⟨\vec{j}⟩\cap E_1\cap E_2$, then

$$(A_1+A_2+A_3)v=v+v+A_{3}v=-v$$

and so $A_{3}v=-3v$, which is impossible by spectrum of Peterson graph. \end{proof}

6. The line graph $L(\Gamma )$ of a graph $\Gamma$ has the edges of $\Gamma$ as vertices, two vertices adjacent when they share a vertex of $\Gamma$.

• (a) Show that the Petersen graph is not the line graph of any graph.
• (b) Show that the minimum eigenvalue of $L(G)$ is at least $-2$. (Hint: Consider $N^{T}N$, where $N$ is the incidence matrix of $G$.)

\begin{proof} a) Assume that there exists a graph $\Gamma$ such that $L(\Gamma )$ is the Peterson graph. Then

$$|E(\Gamma )|=10=\frac{{\sum }_{v\in V(\Gamma )}\mathrm{deg}(v)}{2}\text{ and }|E(L(\Gamma ))|=\sum _{v\in V(\Gamma )}\left(\genfrac{}{}{0ex}{}{\mathrm{deg}(v)}{2}\right)=15.$$

Hence $\sum \mathrm{deg}(v)=20$ and so $\sum \mathrm{deg}(v{)}^2=50$. 很不幸，这是有解的: $4,3,2,2,2,2,2,2,1$.

If there exists $v\in V(\Gamma )$ such that $\mathrm{deg}(v)⩾3$, then $L(\Gamma )$ contains a subgraph $K_3$, which is impossible. Hence $\mathrm{deg}(v)⩽2$ for all $v\in V(\Gamma )$. Then $\Gamma$ is a union of cycles or a paths. Then $\mathrm{deg}(w)$ for all $w\in V(L(\Gamma ))$ satisfies $\mathrm{deg}(w)⩽2$. Therefore, the Petersen graph is not the line graph of any graph.

b) Notice that $N^{T}N=2I+M$, where $M$ is the adjacency matrix of $L(G)$. Since all eigenvalues of $N^{T}N$ are non-negative, the minimum eigenvalue of $L(G)$ is at least $-2$. \end{proof}