Incidence graphs in finite geometry

The Levi graph of the Fano plane gives rise to the Heawood graph, a bipartite graph with seven vertices on each side, 21 edges, and no 4-cycles.

For ${\displaystyle s=t=2}$, a bipartite graph with ${\displaystyle n}$ vertices on each side, ${\displaystyle \Omega (n^{3/2})}$ edges, and no ${\displaystyle K_{2,2}}$ may be obtained as the Levi graph, or point-line incidence graph, of a projective plane of order ${\displaystyle q}$, a system of ${\displaystyle q^{2}+q+1}$ points and ${\displaystyle q^{2}+q+1}$ lines in which each two points determine a unique line, and each two lines intersect at a unique point. We construct a bipartite graph associated to this projective plane that has one vertex part as its points, the other vertex part as its lines, such that a point and a line is connected if and only if they are incident in the projective plane. This leads to a ${\displaystyle K_{2,2}}$-free graph with ${\displaystyle q^{2}+q+1}$ vertices and ${\displaystyle (q^{2}+q+1)(q+1)}$ edges. Since this lower bound matches the upper bound given by I. Reiman,^[11] we have the asymptotic ^[12]

${\displaystyle z(n;2)=(1/2+o(1))n^{3/2}.}$

For ${\displaystyle s=t=3}$, bipartite graphs with ${\displaystyle n}$ vertices on each side, ${\displaystyle \Omega (n^{5/3})}$ edges, and no ${\displaystyle K_{3,3}}$ may again be constructed from finite geometry, by letting the vertices represent points and spheres (of a carefully chosen fixed radius) in a three-dimensional finite affine space, and letting the edges represent point-sphere incidences.^[13]

More generally, consider ${\displaystyle s=2}$ and any ${\displaystyle t}$. Let ${\displaystyle \mathbb {F} _{q}}$ be the ${\displaystyle q}$-element finite field, and ${\displaystyle h}$ be an element of multiplicative order ${\displaystyle t}$, in the sense that ${\displaystyle H=\{1,h,\dots ,h^{t-1}\}}$ form a ${\displaystyle t}$-element subgroup of the multiplicative group ${\displaystyle \mathbb {F} _{q}^{*}}$. We say that two nonzero elements ${\displaystyle (a,b),(a',b')\in \mathbb {F} _{q}\times \mathbb {F} _{q}}$ are equivalent if we have ${\displaystyle a'=h^{d}a}$ and ${\displaystyle b'=h^{d}b}$ for some ${\displaystyle d}$. Consider a graph ${\displaystyle G}$ on the set of all equivalence classes ${\displaystyle \langle a,b\rangle }$, such that ${\displaystyle \langle a,b\rangle }$ and ${\displaystyle \langle x,y\rangle }$ are connected if and only if ${\displaystyle ax+by\in H}$. One can verify that ${\displaystyle G}$ is well-defined and free of ${\displaystyle K_{2,t+1}}$, and every vertex in ${\displaystyle G}$ has degree ${\displaystyle q}$ or ${\displaystyle q-1}$. Hence we have the upper bound ^[14]

${\displaystyle z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.}$

Norm graphs and projective norm graphs

For ${\displaystyle t}$ sufficiently larger than ${\displaystyle s}$, the above conjecture ${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/s})}$ was verified by Kollár, Rónyai, and Szabó ^[15] and Alon, Rónyai, and Szabó ^[16] using the construction of norm graphs and projective norm graphs over finite fields.

For ${\displaystyle t>s!}$, consider the norm graph NormGraph_p,s with vertex set ${\displaystyle \mathbb {F} _{p^{s}}}$, such that every two vertices ${\displaystyle a,b\in \mathbb {F} _{p^{s}}}$ are connected if and only if ${\displaystyle N(a+b)=1}$, where ${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$ is the norm map

${\displaystyle N(x)=x\cdot x^{p}\cdot x^{p^{2}}\cdots x^{p^{s-1}}=x^{(p^{s}-1)/(p-1)}.}$

It is not hard to verify that the graph has ${\displaystyle p^{s}}$ vertices and at least ${\displaystyle p^{2s-1}/2}$ edges. To see that this graph is ${\displaystyle K_{s,s!+1}}$-free, observe that any common neighbor ${\displaystyle x}$ of ${\displaystyle s}$ vertices ${\displaystyle y_{1},\ldots ,y_{s}\in \mathbb {F} _{p^{s}}}$ must satisfy

${\displaystyle 1=N(x+y_{i})=(x+y_{i})\cdot (x+y_{i})^{p}\cdots (x+y_{i})^{p^{s-1}}=(x+y_{i})\cdot (x^{p}+y_{i}^{p})\cdots (x^{p^{s-1}}+y_{i}^{p^{s-1}})}$

for all ${\displaystyle i=1,\ldots ,s}$, which a system of equations that has at most ${\displaystyle s!}$ solutions.

The same result can be proved for all ${\displaystyle t>(s-1)!}$ using the projective norm graph, a construction slightly stronger than the above. The projective norm graph ProjNormGraph_p,s is the graph on vertex set ${\displaystyle \mathbb {F} _{p^{s-1}}\times \mathbb {F} _{p}^{\times }}$, such that two vertices ${\displaystyle (X,x),(Y,y)}$ are adjacent if and only if ${\displaystyle N(X+Y)=xy}$, where ${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$ is the norm map defined by ${\displaystyle N(x)=x^{(p^{s}-1)/(p-1)}}$. By a similar argument to the above, one can verify that it is a ${\displaystyle K_{s,t}}$ -free graph with ${\displaystyle \Omega (n^{2-1/s})}$ edges.

The above norm graph approach also gives tight lower bounds on ${\displaystyle z(m,n;s,t)}$ for certain choices of ${\displaystyle m,n}$.^[16] In particular, for ${\displaystyle s\geq 2}$, ${\displaystyle t>s!}$, and ${\displaystyle n^{1/t}\leq m\leq n^{1+1/t}}$, we have

${\displaystyle z(m,n;s,t)=\Theta (mn^{1-1/s}).}$

In the case ${\displaystyle m=(1+o(1))n^{1+1/s}}$, consider the bipartite graph ${\displaystyle G}$ with bipartition ${\displaystyle V=V_{1}\cup V_{2}}$, such that ${\displaystyle V_{1}=\mathbb {F} _{p^{t}}\times \mathbb {F} _{p}^{\times }}$ and ${\displaystyle V_{2}=\mathbb {F} _{p^{t}}}$. For ${\displaystyle A\in V_{1}}$ and ${\displaystyle (B,b)\in V_{2}}$, let ${\displaystyle A\sim (B,b)}$ in ${\displaystyle G}$ if and only if ${\displaystyle N(A+B)=b}$, where ${\displaystyle N(\cdot )}$ is the norm map defined above. To see that ${\displaystyle G}$ is ${\displaystyle K_{s,t}}$ -free, consider ${\displaystyle s}$ tuples ${\displaystyle (B_{1},b_{1}),\ldots ,(B_{s},b_{s})\in V_{1}}$. Observe that if the ${\displaystyle s}$ tuples have a common neighbor, then the ${\displaystyle B_{i}}$ must be distinct. Using the same upper bound on he number of solutions to the system of equations, we know that these ${\displaystyle s}$ tuples have at most ${\displaystyle s!<t}$ common neighbors.

Clique partitions

Using a related result on clique partition numbers, Alon, Mellinger, Mubayi and Verstraëte ^[17] proved a tight lower bound on ${\displaystyle z(m,n;2,t)}$ for arbitrary ${\displaystyle t}$: if ${\displaystyle m=(1+o(1))n^{t/2}}$, then we have

${\displaystyle z(m,n;2,t)=(1+o(1))mn^{1/2}}$.

For ${\displaystyle 2\leq t\leq n}$, we say that a collection of subsets ${\displaystyle A_{1},\dots ,A_{\ell }\subset [n]}$ is a clique partition of ${\displaystyle H\subset {[n] \choose t}}$ if ${\displaystyle \bigcup _{i=1}^{\ell }{A_{i} \choose t}}$ form a partition of ${\displaystyle H}$. Observe that for any ${\displaystyle k}$, if there exists some ${\displaystyle H\subset {[n] \choose t}}$ of size ${\displaystyle (1-o(1)){n \choose t}}$ and ${\displaystyle m=(1+o(1)){n \choose t}/{k \choose t}}$, such that there is a partition of ${\displaystyle H}$ into ${\displaystyle m}$ cliques of size ${\displaystyle k}$, then we have ${\displaystyle z(m,n;2,t)=km}$. Indeed, supposing ${\displaystyle A_{1},\dots ,A_{m}\subset [n]}$ is a partition of ${\displaystyle H}$ into ${\displaystyle m}$ cliques of size ${\displaystyle k}$, we can let ${\displaystyle G}$ be the ${\displaystyle m\times n}$ bipartite graph with ${\displaystyle V_{1}=\{A_{1},\dots ,A_{m}\}}$ and ${\displaystyle V_{2}=[n]}$, such that ${\displaystyle A_{i}\sim v}$ in ${\displaystyle G}$ if and only if ${\displaystyle v\in A_{i}}$. Since the ${\displaystyle A_{i}}$ form a clique partition, ${\displaystyle G}$ cannot contain a copy of ${\displaystyle K_{2,t}}$.

It remains to show that such a clique partition exists for any ${\displaystyle m=(1+o(1))n^{t/2}}$. To show this, let ${\displaystyle \mathbb {F} _{q}}$ be the finite field of size ${\displaystyle q}$ and ${\displaystyle V=\mathbb {F} _{q}\times \mathbb {F} _{q}}$. For every polynomial ${\displaystyle p(\cdot )}$ of degree at most ${\displaystyle t-1}$ over ${\displaystyle \mathbb {F} _{q}}$, define ${\displaystyle C_{p}=\{(x,p(x)):x\in \mathbb {F} _{q}\}\subset V}$. Let ${\displaystyle {\mathcal {C}}}$ be the collection of all ${\displaystyle C_{p}}$, so that ${\displaystyle |{\mathcal {C}}|=q^{t}=n^{t/2}}$ and every ${\displaystyle C_{p}}$ has size ${\displaystyle q={\sqrt {n}}}$. Clearly no two members of ${\displaystyle {\mathcal {C}}}$ can share ${\displaystyle t}$ members. Since the only ${\displaystyle t}$-sets in ${\displaystyle V}$ that do not belong to ${\displaystyle H}$ are those that have at least two points sharing the same first coordinate, we know that almost all ${\displaystyle t}$-subsets of ${\displaystyle V}$ are contained in some ${\displaystyle C_{p}}$.

Randomized algebraic constructions

Alternative proofs of ${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$ for ${\displaystyle t}$ sufficiently larger than ${\displaystyle s}$ were also given by Blagojević, Bukh and Karasev ^[18] and by Bukh ^[19] using the method of random algebraic constructions. The basic idea is to take a random polynomial ${\displaystyle f:\mathbb {F} _{q}^{s}\times \mathbb {F} _{q}^{s}\rightarrow \mathbb {F} _{q}}$ and consider the graph ${\displaystyle G}$ between two copies of ${\displaystyle \mathbb {F} _{q}^{s}}$ whose edges are all those pairs ${\displaystyle (x,y)}$ such that ${\displaystyle f(x,y)=0}$.

To start with, let ${\displaystyle q}$ be a prime power and ${\displaystyle n=q^{2}}$. Let

${\displaystyle f\in \mathbb {F} _{q}[x_{1},\dots ,x_{s},y_{1},\dots ,t_{s}]_{\leq s^{2}}}$

be a random polynomial with degree at most ${\displaystyle s^{2}}$ in ${\displaystyle X=(x_{1},\dots ,x_{s})}$, degree at most ${\displaystyle s^{2}}$ in ${\displaystyle Y=(y_{1},\dots ,y_{s})}$, and furthermore satisfying ${\displaystyle f(X,Y)=f(Y,X)}$ for all ${\displaystyle X,Y}$. Let ${\displaystyle G}$ be the associated random graph on vertex set ${\displaystyle \mathbb {F} _{q}^{s}}$, such that two vertices ${\displaystyle x}$ and ${\displaystyle y}$ are adjacent if and only if ${\displaystyle f(x,y)=0}$.

To prove the asymptotic lower bound, it suffices to show that the expected number of edges in ${\displaystyle G}$ is ${\displaystyle \Omega (q^{2s-1})}$. For every ${\displaystyle s}$-subset ${\displaystyle U\subset \mathbb {F} _{q}^{s}}$, we let ${\displaystyle Z_{U}}$ denote the vertex subset of ${\displaystyle \mathbb {F} _{q}^{s}\setminus U}$ that "vanishes on ${\displaystyle f(\cdot ,U)}$":

${\displaystyle Z_{U}=\{x\in \mathbb {F} _{q}^{s}\setminus U:f(x,u)=0{\text{ for all }}u\in U\}}$.

Using the Lang-Weil bound for polynomials ${\displaystyle f(\cdot ,u)}$ in ${\displaystyle \mathbb {F} _{q}^{s}}$, we can deduce that one always has ${\displaystyle Z_{U}\leq C}$ or ${\displaystyle Z_{U}>q/2}$ for some large constant ${\displaystyle C}$, which implies

${\displaystyle \mathbb {P} (|Z_{U}|>C)=\mathbb {P} (|Z_{U}|>q/2)}$.

Since ${\displaystyle f}$ is chosen randomly over ${\displaystyle \mathbb {F} _{q}}$, it is not hard to show that the right-hand side probability is small, so the expected number of ${\displaystyle s}$-subsets ${\displaystyle U}$ with ${\displaystyle |Z_{U}|>C}$ also turned out to be small. If we remove a vertex from every such ${\displaystyle U}$, then the resulting graph is ${\displaystyle K_{s,C+1}}$ free, and the expected number of remaining edges is still large. This finishes the proof that ${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$ for all ${\displaystyle t}$ sufficiently large with respect to ${\displaystyle s}$. More recently, there have been a number of results verifying the conjecture ${\displaystyle z(m,n;s,t)=\Omega (n^{2-1/s})}$ for different values of ${\displaystyle s,t}$, using similar ideas but with more tools from algebraic geometry.^[8][20]