HW5

1. Consider a projective plane $(\mathcal{P},\mathcal{L},\mathbf{I})$ of order $n$ with a polarity $\pi$, that is, $\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}$. Define a graph $G$ with the vertex set $\left\{P\in \mathcal{P}:P\notin P^{\pi }\right\}$; two vertices $P,Q$ adjacent if $Q\in P^{\pi }$.

• (a) Show that the adjacency relation is symmetric.
• (b) Show that $G$ is $C_4$-free.
• (c) Give a precise condition under which $G$ is a witness for $\mathrm{ex}\left(N,C_4\right)\ge (\frac{1}{2}+o(1))N^{1.5}$.

\begin{proof} a) By $P\mathbf{I}L\iff P^{\pi }\mathbf{I}{L}^{\pi }$, $Q\in P^{\pi }$ iff $P\in Q^{\pi }$, so $P\sim Q$ iff $Q\sim P$.

b) If $G$ is not $C_4$-free, there exists $v_1,\cdots ,v_4$ such that $v_2\in v_1^{\pi }$, $v_3\in v_2^{\pi }$, $v_4\in v_3^{\pi }$, $v_1\in v_4^{\pi }$, which deduces that $v_2,v_4\in v_1^{\pi }$ and $v_2,v_4\in v_3^{\pi }$, which deduces that $v_1^{\pi }=v_3^{\pi }$, leading to a contradiction.

c) Define $s=|S:=\{P\in \mathcal{P}:P\in P^{\pi }\}|$. Then $N=n^2+n+1-s$ and in this case $|E(G)|⩽Nn/2$. The inequality holds and so $N⩽n^2$, i.e. $s⩾n+1$ One can verify that a precise condition is $s=n+1$, and each line $P^{\pi }$ contains exactly one point in $S$. \end{proof}

2. Consider $\mathrm{PG}(2,q)$, $q$ odd, with a conic $\mathcal{C}$ defined by $x_1^2+x_2^2+x_3^2=0$ with associated bilinear form $b(x,y)=x_1{y}_1+x_2{y}_2+x_3{y}_3$. Define $\perp$ by $⟨x{⟩}^{\perp }=\left\{y\in {\mathbb{F}}_q^3:b(x,y)=0\right\}$.

• (a) Show that ⟂ is a polarity.
• (b) Define a graph $H$ as in the previous exercise with $\pi =\perp$. Let $H_{\square }$ be the induced subgraph of $H$ on the set of vertices $⟨x⟩$ with $b(x,x)$ a square, and let $H_{⊠}$ be the induced subgraph of $H$ on the set of vertices $⟨x⟩$ with $b(x,x)$ a nonsquare. Show that either $H_{\square }$ or $H_{⊠}$ is triangle-free. (Hint: Consider what happens when $b(x,y)=b(y,z)=b(z,x)=0$.)
• (c) Conclude that $\mathrm{ex}\left(N,\left\{C_3,C_4\right\}\right)\ge \left(\frac{1}{\sqrt{8}}+o(1)\right)N^{1.5}$.

Bonus exercise: Both constructions work for $q$ even. Here the absolute trace of $x$ partitions the points into two halves.

\begin{proof} a) It suffices to check $\perp$ 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}$. 因为非退化所以 kernel 是 2 维的，所以是直线。由 $b(x,y)$ 对称得到$P\mathbf{I}L\iff P^{\pi }\mathbf{I}{L}^{\pi },{\pi }^2=\mathrm{id}$. So $\perp$ is a polarity.

b) If $H_{\square }$ or $H_{⊠}$ is not triangle free, then there exists $x,y,z$ such that $b(x,x),b(y,y),b(z,z)$ are squares, and $y\in {⟨x⟩}^{\perp }$, $z\in {⟨y⟩}^{\perp }$, and $x\in {⟨z⟩}^{\perp }$. It deduces that $\sum x_i{y}_i=\sum y_i{z}_i=\sum x_i{z}_i=0$. Then $x,y,z$ is a set of orthogonal basis of ${\mathbb{F}}_q^3$. Let $M$ be a transform matrix from $\{e_1,e_2,e_3\}$ to $\{x,y,z\}$. Then the gram matrix under the basis $\{x,y,z\}$ is

$$\mathrm{diag}(b(x,x),b(y,y),b(z,z))=M^{T}IM,$$

whose determinant is a square $\det (M{)}^2$. Since the product of three non-square element is non-square, $H_{⊠}$ is triangle-free.

c) By Exercise 1, $H$ is $C_4$-free and so for $H_{⊠}$. Define $\mathcal{S}:=\{x\in \mathrm{PG}(2,q):b(x,x)\text{ is a non-square}\}$. Then $N=|\mathcal{S}|$ and $|E(H_{⊠})|=|\{(x,y):b(x,y)=0,x,y\in \mathcal{S}\}|=N(q+1)/4$. It deduces that $|\mathrm{ex}(N,\{C_3,C_4\})|⩾N(q+1)/4$. Since $N=\frac{q^2-q\chi (-1)}{2}$, we have $N\sim q^2/2$ and $|E(H_{⊠})|\sim q^3/8$. Now we finish the proof.

(Proof of $N=\frac{q^2-q\chi (-1)}{2}$: Number of solutions of $x_1^2+x_2^2+x_3^2=a$ is $q^2+q\chi (-a)$, where $\chi$ is Legendre symbol. It follows that $N=\frac{q-1}{2}(q^2+q\chi (-1))$.) \end{proof}

3. Show all of the following for $a\ge b\ge 0$:

$$q^{b(a-b)}\le \left[\begin{array}{l}a\\ b\end{array}\right]<\left(1+\frac{q+1}{q^2-q-1}\right)q^{b(a-b)},q^{a-1}\le \left[\begin{array}{l}a\\ 1\end{array}\right]<\left(\frac{q}{q-1}\right)q^{a-1}.$$

\begin{proof} Recall that

$$\left[\begin{array}{l}a\\ b\end{array}\right]=\frac{(q^a-1)(q^a-q)\cdots (q^a-q^{b-1})}{(q^b-1)\cdots (q^b-q^{b-1})}$$

Notice that

$$\left[\begin{array}{l}a\\ b\end{array}\right]=q^{b(a-b)}\frac{(1-q^{-a})(1-q^{-a+1})\cdots (1-q^{b-a-1})}{(1-q^{-b})\cdots (1-q^{-1})}:=q^{b(a-b)}A,$$

where $A⩾1$. Furthermore, $A<\frac{1}{(1-q^{-b})\cdots (1-q^{-1})}<{\prod }_{i=1}^{\infty }\frac{1}{1-q^{-i}}={\sum }_{n⩾0}p(n)q^{-n}$, where $p(n)$ is the number of partitions of $n$, see ^5tpltg. By Pentagonal number theorem, $A<\frac{1}{1-q^{-1}-q^{-2}}=\frac{q^2}{q^2-q-1}$.

Since$\left[\begin{array}{l}a\\ 1\end{array}\right]=\frac{q^a-1}{q-1}$, it is easy to check the second inequality. \end{proof}

4. Suppose that $n\ge 2k+1$ and $k\ge 3$.

• (a) Consider an intersecting family $\mathcal{F}$ of $k$-subsets of $\{1,\dots ,n\}$, that is, for all $E,F\in \mathcal{F}$, we have $|E\cap F|\ge 1$. Suppose that $|\mathcal{F}|\ge \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. Show the following:
  • i. If an element $x$ is disjoint from some $k$-subset $Y\in \mathcal{F}$, then $x$ meets at most $k\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)$ elements of $\mathcal{F}$.
  • ii. If $n\ge k^3$, then $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ and $\mathcal{F}$ consists of all $k$-subsets that contain a fixed element.
• (b) Consider an intersecting family $\mathcal{F}$ of $k$-subspace of $V(n,q)$, that is, for all $E,F\in \mathcal{F}$, we have $\dim (E\cap F)\ge 1$. Suppose that $|\mathcal{F}|\ge \left[\begin{array}{c}n-1\\ k-1\end{array}\right]$. Show the following:
  • i. If a 1 -subspace $P$ is disjoint from some $k$-subspace $Y\in \mathcal{F}$, then $P$ meets at most $[k]\left[\begin{array}{c}n-2\\ k-2\end{array}\right]$ elements of $\mathcal{F}$.
  • ii. If $n\ge 3k$, then $|\mathcal{F}|=\left[\begin{array}{c}n-1\\ k-1\end{array}\right]$ and $\mathcal{F}$ consists of all $k$-subspaces that contain a fixed element.

\begin{proof} a) i)The number of elements of $\mathcal{F}$ such that $x$ meets

$$⩽\sum _{y\in Y}|\{E\in \mathcal{F}:\{x,y\}\subseteq E\}|=k\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right).$$

a) ii) Otherwise, if there does not exist $x\in E$ for all $E\in \mathcal{F}$, for any $x\in [n]$, there exists $Y$ such that $x\notin Y\in \mathcal{F}$ and $x$ meets at most $k\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)$ elements of $\mathcal{F}$. We also assume that $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. Since $|E\cap F|⩾1$, fix $Y_0\in \mathcal{F}$, then ${\cup }_{x\in Y_0}\{E\in \mathcal{F}:x\in E\}=\mathcal{F}$. It deduces that

$$\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)<|\mathcal{F}|⩽k\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)\cdot k,$$

which deduces that $n⩽k^3-k^2+1$, which is impossible.

b) i) Similarly, the number $⩽{\sum }_{y\in Y}|\{E\in \mathcal{F}:\mathrm{span}\{x,y\}\subseteq E\}|=[k]\left[\begin{array}{c}n-2\\ k-2\end{array}\right].$

ii) Similarly, assume that $|\mathcal{F}|>\left[\begin{array}{c}n-1\\ k-1\end{array}\right]$ and for each $x\in V(n,q)$, there exists a $k$-subspace in $\mathcal{F}$ such that $x\notin \mathcal{F}$. Still fix $W_0\in \mathcal{F}$, and there is

$$\left[\begin{array}{c}n-1\\ k-1\end{array}\right]<|\mathcal{F}|⩽[k{]}^2\left[\begin{array}{c}n-2\\ k-2\end{array}\right],$$

which deduces that $\frac{q^{n-1}-1}{q^{k-1}-1}⩽{\left(\frac{q^k-1}{q-1}\right)}^2$. Since $\mathrm{LHS}>q^{n-k}$ and $\mathrm{RHS}<{\left(\frac{q}{q-1}\right)}^2{q}^{2k-2}$ by Exercise 3, we have $n<3k$, contradiction. \end{proof}

5. In $V(2k+1,q)$, consider a spread $\mathcal{S}$ of a hyperplane $H_{\infty }$ into $k$-spaces. We define an incidence geometry $(\mathcal{P},\mathcal{L},\mathbf{I})$ as follows:

• (a) The points $\mathcal{P}$ consist of the 1-spaces of $V(2k+1,q)$ not in $H_{\infty }$ and the elements of $\mathcal{S}$.
• (b) The lines $\mathcal{L}$ consist of the $(k+1)$-spaces of $V(2k+1,q)$ that meet $H_{\infty }$ in an element of $\mathcal{S}$, and $H_{\infty }$.
• (c) A point and a line are incident when the corresponding objects are incident in $V(2k+1,q)$.

Show that $(\mathcal{P},\mathcal{L},\mathbf{I})$ is a projective plane of order $q^k$. (See Problem 24C in Van Lint-Wilson for an alternative formulation.)

\begin{proof} Recall that ^zg2bnx.

Any two points are incident with a unique line: For $v=1$-space of $V(2k+1,q)$ not in $H_{\infty }$ and $w\in \mathcal{S}$, $\mathrm{span}⟨v,w⟩$ is the unique common line. For $v,w\in \mathcal{S}$, $\mathrm{span}⟨v,w⟩=H_{\infty }$ and is the unique common line. For $v,w$ are two $1$-spaces of $V(2k+1,q)$ not in $H_{\infty }$, $\mathrm{span}⟨v,w⟩\cap H_{\infty }$ is a $1$-space contained in $H_{\infty }$, which is contained in a unique element of $\mathcal{S}$.

Any two lines are incident with a unique common point. For $L_1,L_2\ne H_{\infty }$, if $L_1\cap H_{\infty }=L_2\cap H_{\infty }:=S_0$, then $S_0$ is the unique common line; otherwise $L_1\cap L_2=$ a unique $1$-space of $V(2k+1,q)$ not in $H_{\infty }$. For $L_1=H_{\infty }$ and $L_2\ne H_{\infty }$, $L_1\cap L_2=H_{\infty }\cap L_2$ is an element of $\mathcal{S}$, which is the unique common point we desired.

There are four points, no three collinear. Take $u,v$ as three $1$-spaces not in $H_{\infty }$ and $w,t\in \mathcal{S}$, such that the common line of $u,v$ is neither $w$ nor $t$.

This projective plane is of order $q^k$. Number of $\mathcal{S}=(q^{2k}-1)/(q^k-1)=q^k+1$. Number of $1$-spaces not in $H_{\infty }=q^{2k}$. So the number of points is $q^{2k}+q^k+1$ and so this projective plane is of order $q^k$. \end{proof}

6. Show that if a $3$-$(v,6,1)$ design exists, then $v\equiv 2$ or $6(\mathrm{mod}20)$.

\begin{proof} Since for each $1⩽i⩽3$, $b_i$ is an integer. Recall that

In the other words, a $t$-design is also a $(t-1)$-design.

Link to original

Thus, $b_1=\left(\genfrac{}{}{0ex}{}{v-1}{2}\right)/\left(\genfrac{}{}{0ex}{}{5}{2}\right)$ and $b_2=\left(\genfrac{}{}{0ex}{}{v-2}{1}\right)/\left(\genfrac{}{}{0ex}{}{4}{1}\right)$ are integers. It follows that $4\mid v-2$ and $20\mid (v-1)(v-2)$. So $v=4k+2$ for some $k\in \mathbb{Z}$, and $20\mid 4k(4k+1)$ yields $k\equiv 1,5(\mathrm{mod}5)$. Consequently, $v\equiv 2,6(\mathrm{mod}20)$. \end{proof}