% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P24}{19(4)}{2012} \usepackage{latexsym,amsmath,url,amssymb,amsthm} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages %\usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\PG}{\mathsf{PG}} \newcommand{\hkr}{{\rm hr}} \newcommand{\ppr}{{\rm pr}} \newcommand{\vol}{{\rm vol}} \newcommand{\Vol}{{\rm Vol}} \newcommand{\CoVar}{{\rm coVar}} \newcommand{\Var}{{\rm Var}} \newcommand{\vn}[1]{\left|\left| #1 \right|\right|} \renewcommand{\L}{\mathcal{L}} \newcommand{\N}{\mathbb{N}} \newfont{\bss}{cmss12} \newcommand{\p}{\mbox{\bss P}} \newcommand{\e}{\mbox{\bss E}} %\newcommand{\proof}{{\bf Proof:~~~~}} \newcommand{\ignore}[1]{} \newcommand{\Trace}{{\rm Trace}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Large incidence-free sets in geometries} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Stefaan De Winter\\ %\author{Dagwood Remifa\thanks{Supported by NASA grant ABC123.}\\ \small Department of Mathematical Sciences\\ [-0.8ex] \small Michigan Technological University\\ [-0.8ex] \small Michigan, U.S.A.\\ \small\tt sgdewint@mtu.edu\\ \and Jeroen Schillewaert \qquad Jacques Verstraete \thanks{Research supported by NSF Grant DMS 1101489.}\\ \small Department of Mathematics\\[-0.8ex] \small University of California at San Diego\\[-0.8ex] \small California, U.S.A.\\ \small \tt \{jschillewaert,jverstraete\}@math.ucsd.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 6, 2012}{Oct 22, 2012}{Nov 8, 2012}\\ \small Mathematics Subject Classifications: 15A18,05D40,51E12} \begin{document} \maketitle \begin{abstract} Let $\Pi = (P,L,I)$ denote a rank two geometry. In this paper, we are interested in the largest value of $|X||Y|$ where $X \subset P$ and $Y \subset L$ are sets such that $(X \times Y) \cap I = \emptyset$. Let $\alpha(\Pi)$ denote this value. We concentrate on the case where $P$ is the point set of $\mathsf{PG}(n,q)$ and $L$ is the set of $k$-spaces in $\mathsf{PG}(n,q)$. In the case that $\Pi$ is the projective plane $\mathsf{PG}(2,q)$, Haemers proved that maximal arcs in projective planes together with the set of lines not intersecting the maximal arc determine $\alpha(\mathsf{PG}(2,q))$ when $q$ is an even power of $2$. Therefore, in those cases, \[ \alpha(\Pi) = q(q - \sqrt{q} + 1)^2.\] We give both a short combinatorial proof and a linear algebraic proof of this result, and consider the analogous problem in generalized polygons. More generally, if $P$ is the point set of $\mathsf{PG}(n,q)$ and $L$ is the set of $k$-spaces in $\mathsf{PG}(n,q)$, where $1 \leq k \leq n - 1$, and $\Pi_q = (P,L,I)$, then we show as $q \rightarrow \infty$ that \[ \frac{1}{4}q^{(k + 2)(n - k)} \lesssim \alpha(\Pi) \lesssim q^{(k + 2)(n - k)}.\] The upper bounds are proved by combinatorial and spectral techniques. This leaves the open question as to the smallest possible value of $\alpha(\Pi)$ for each value of $k$. We prove that if for each $N \in \mathbb N$, $\Pi_N$ is a partial linear space with $N$ points and $N$ lines, then $\alpha(\Pi_N) \gtrsim \frac{1}{e}N^{3/2}$ as $N \rightarrow \infty$. \end{abstract} \section{Introduction} A {\em rank two geometry} is a triple $\Pi = (P,L,I)$ such that $P$ is a set of {\em points}, $L$ is a collection of subsets of $P$, and $I \subseteq P \times L$ is an {\em incidence relation}. A {\em partial linear space} is a rank two geometry $(P,L,I)$, where the elements of $L$ are referred to as {\em lines}, with the property that any two lines intersect in at most one point and any two points are contained in at most one line. In this paper, we consider the problem of finding the maximum value of $|X||Y|$ such that $X \subset P$ and $Y \subset L$ and $(X \times Y) \cap I = \emptyset$. In words, no points in $X$ are incident to any elements of $Y$. Precisely, we define \[ \alpha(\Pi) = \max\{|X||Y| : X \subset P, Y \subset L, (X \times Y) \cap I = \emptyset\}.\] We concentrate specifically on the case where $\Pi$ is a projective $n$-dimensional space, $\PG(n,q)$, and $P$ is the point set of $\Pi$ and $L$ is the set of $k$-spaces in $\Pi$. Recall that $k$-dimensional projective spaces have vectorial dimension $k+1$. Throughout, $I$ denotes the subspace relation. This problem has been studied in the case of projective planes by Haemers (consider Corollary 3.1.3 on page 29 of his Ph.D. thesis \cite{HPHD} or page 603 in \cite{H}), and is motivated by analogous problems for sets, for instance the well-studied topic of cross-intersecting families (see Tokushige~\cite{Tok}). Our first theorem in the vector space setting is as follows: \begin{theorem}\label{main1a} Let $n>2,k \in \{1,2,\dots,n-1\}$, and for each prime power $q$, let $\Pi_q = (P,L,I)$ be a rank two geometry, where $P$ is the point set of $\PG(n,q)$ and $L$ is the set of $k$-spaces in $\PG(n,q)$. Then as $q \rightarrow \infty$, \[ \frac{1}{4} q^{(k + 2)(n - k)} \lesssim \alpha(\Pi_q) \lesssim q^{(k + 2)(n - k)}.\] Furthermore, if $k = n - 1$, then \[ \alpha(\Pi_q) \geq \left\{\begin{array}{ll} q^{n-1}\lfloor\frac{q+1}{2}\rfloor^2 & \mbox{ if }n\mbox{ is odd}\\ q^{n+1}-q^n + q^{n-1} & \mbox{ if }n \mbox{ is even and }q = 2^{2h} \mbox{ for some }h\in \mathbb N \end{array}\right.\] \end{theorem} Explicit constructions establishing the lower bounds are given in Section \ref{construct}. The upper bound is proved in Subsection \ref{uppermain1}. For general $k$, Theorem \ref{main1a} determines $\alpha(\Pi)$ asymptotically up to a factor $4$. It is an intriguing problem to determine whether the upper or lower bound in Theorem \ref{main1a} is asymptotically tight. \begin{problem}\label{problem} Let $k,n \in \mathbb N$ with $k < n$, and let $\Pi_q = (P,L,I)$ where $P$ is the point set of $\PG(n,q)$ and $L$ is the set of $k$-spaces in $\PG(n,q)$. Determine $\alpha(\Pi_q)$. \end{problem} In particular, one may ask whether $\alpha(\Pi_q) \sim q^{(k + 2)(n - k)}$ as $q \rightarrow \infty$, especially for the case of all projective planes, where $k = 1$ and $n = 2$. If $k = n - 1$, $n$ is even, and $q$ is an even power of two, we obtain $\alpha(\Pi_q) \sim q^{n+1}$ as $q \rightarrow \infty$ from the last inequality in Theorem \ref{main1a}. In the next section, we concentrate on projective planes and obtain some sharper results. \subsection{Projective planes}\label{ph} A {\it projective plane of order $q$} is a partial linear space in which each line is incident with $q+1$ points, in which each point is on $q+1$ lines, and such that every two lines intersect in a unique point, and every two points are on a unique line. We always assume $q\geq2$. Using Corollary 3.1.3 on page 29 in \cite{HPHD} with $s=t=q;\:\alpha=q+1$ it is easy to show that if $\Pi$ is projective plane of order $q$, then $\alpha(\Pi) \leq q(q - \sqrt{q} + 1)^2$ with equality only for the set of points on a {\em maximal arc of degree $\sqrt{q}$} (i.e. a point set such that each line of $\Pi$ intersects $\Sigma$ in either $0$ or $\sqrt{q}$ points) in $\Pi$ and the lines disjoint from the maximal arc. In Section \ref{Combi}, we give a new and combinatorial proof of this result, see Subsection \ref{gp} for the necessary definitions. This result has recently independently been obtained by D. Stinson, see \cite{Stinson}. Projective planes isomorphic to $\PG(2,q)$ for some $q$ are called {\em Desarguesian}. %(a slightly weaker result without the characterization of equality follows from a result by Jungnickel~\cite{Jun} on designs). \begin{theorem}\label{main1} Let $\Pi_q$ consist of the points and lines in a projective plane of order $q$. Then \[ \alpha(\Pi_q) \leq q(q - \sqrt{q} + 1)^2\] with equality only for the set of points on a maximal arc of degree $\sqrt{q}$ in $\Pi_q$ and the lines of $\Pi_q$ not incident with any of these points. \end{theorem} It follows that to achieve equality in Theorem \ref{main1} if $\Pi_q$ is Desarguesian $q$ necessarily is an even square (see Ball, Blokhuis and Mazzocca~\cite{BallBlokMaz}). Note also that if $\Pi_q$ is the Desarguesian projective plane of order $q = 2^{2h}$, a maximal arc of degree $2^h$ always exists (see Denniston~\cite{Den}). For projective planes, Problem \ref{problem} is intriguing, since we are not aware of infinitely many projective planes $\Pi_q$ of order $q$ for which $\alpha(\Pi_q) \leq 0.99q^3$. We believe that projective planes of prime order might be a good candidate for such family. \subsection{Generalized polygons}\label{gp} A {\em generalized $n$-gon}, $n\geq 3$, or a generalized polygon, is a non-empty point-line geometry $\Gamma=(\mathcal{P},\mathcal{L},I)$, the incidence graph of which has diameter $n$ (i.e. any two elements are at most at distance $n$) and girth $2n$ (i.e., the length of any shortest circuit is $2n$; in particular we assume that there is at least one circuit). Recall that the incidence graph is the graph with $\mathcal{P}\cup\mathcal{L}$ as set of vertices, and in which two vertices $x,y$ are adjacent if and only if $x I y$. A {\em thick} generalized polygon is a generalized polygon for which each element is incident with at least three elements. In this case, the number of points on a line is a constant, say $s+1$, and the number of lines through a point is also a constant, say $t+1$. The pair $(s,t)$ is called the order of the polygon; if $s=t$ we say that the polygon has {\em order} $s$. Throughout this paper $s$ and $t$ will always be finite. The spectral proof of Theorem \ref{main1} can be generalized to give bounds for generalized polygons. The Feit-Higman Theorem~\cite{FH} states that finite generalized $n$-gons of order $q \geq 2$ exist only for $n \in \{3,4,6\}$. The thick generalized 3-gons are called projective planes (then necessarily $s=t$); this case is handled by Theorem \ref{main1}. The generalized 4-gons, 6-gons, 8-gons are also called {\em generalized quadrangles}, {\em generalized hexagons}, {\em generalized octagons}, respectively. Our methods work for polygons of order $(s,t)$ as well, however we feel the more tedious calculations involved would decrease the readability of the paper. \begin{theorem}\label{main2} Let $\Pi$ be a generalized $n$-gon of order $q \geq 2$, where $n \in \{4,6\}$. Then \[ \alpha(\Pi) \leq (n/2)q(\frac{q^{n} - 1}{q^{2}-1})^{2}\] Furthermore, if $q$ is an even power of a prime then there exists a generalized $n$-gon $\Pi$ of order $q$ such that $\alpha(\Pi) \geq q^{2n - 3} - q^{2n - 4} + q^{2n - 5}$. \end{theorem} The upper bound is proved in Subsection \ref{uppermain2}, and constructions establishing the lower bound are stated in Section \ref{construct}. This leaves the interesting open problem of determining $\alpha(\Pi_q)$ asymptotically as $q \rightarrow \infty$, where $\Pi_q$ is a generalized quadrangle or hexagon of order $q$, in particular whether the $n/2$ factor is necessary. \begin{remark} A further consequence of the Feit-Higman theorem is that for thick generalized octagons of order $(s,t)$ necessarily $s\neq t$. This is the reason that generalized octagons are not discussed in this paper. \end{remark} \bigskip \subsection{Partial linear spaces}\label{pl} In this section we give a universal and almost tight lower bound on $\alpha(\Pi)$ when $\Pi = (P,L,I)$ is an arbitrary partial linear space with $N$ points and $N$ lines. \begin{theorem}\label{main3} For $N \in \mathbb N$, let $\Pi_N = (P,L,I)$ be a partial linear space with $|P| = |L| = N$. Then as $N \rightarrow \infty$, \[ \alpha(\Pi_N) \gtrsim \frac{1}{e}N^{3/2}.\] \end{theorem} The probabilistic proof of Theorem \ref{main3} is in Section \ref{last}. We also define in a partial linear space $\Pi = (P,L,I)$ the quantity $\bar{\alpha}(\Pi)$ to be the maximum value of $|X||Y|$ such that there exists $X \subset P$ and $Y \subset L$ with $|X|=|Y|$ and with $(X \times Y) \cap I = \emptyset$. The key difference between this and $\alpha(\Pi)$ is the restriction $|X| = |Y|$. The results of Mubayi and Williford (see Theorem 5 in~\cite{MW}) show that $\bar{\alpha}(\Pi) \geq 0.037q^{3}$ when $\Pi$ is a Desarguesian projective plane of order $q$. The following problem is open: \begin{problem} Determine whether there exists $\varepsilon > 0$ such that if $\Pi = (P,L,I)$ is any partial linear space with $|P| = |L| = N$, and $N$ is large enough, then $\bar{\alpha}(\Pi) > N^{1 + \varepsilon}$. \end{problem} This problem on $\bar{\alpha}(\Pi)$ is related to a notoriously difficult conjecture of Erd\H{o}s in Ramsey Theory on quadrilateral-free graphs~\cite{Fan}, which would suggest that for each $\varepsilon > 0$, there exists for infinitely many $N$ a partial linear space $\Pi = (P,L,I)$ such that $\bar{\alpha}(\Pi) \leq N^{1 + \varepsilon}$. Note that this is far removed from projective planes $\Pi$ for which $\bar{\alpha}(\Pi)$ has order $N^{3/2}$. \subsection{Notation} We use the following asymptotic notation throughout this paper: if $f,g :\mathbb N \rightarrow \mathbb R^+$ are functions and \[ \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 1\] then we write $f(n) \sim g(n)$. If \[ \limsup_{n \rightarrow \infty} \frac{f(n)}{g(n)} \leq 1\] then we write $f(n) \lesssim g(n)$. Let $N_{k,n}$ denote the number of $k$-dimensional subspaces of $\PG(n,q)$, namely \[ N_{k,n} = \frac{(q^{n + 1} - 1)(q^n - 1) \dots (q^{n - k + 1} - 1)}{(q^{k + 1} - 1)(q^k - 1) \dots (q - 1)}.\] Note that $N_{k,n} \sim q^{(k + 1)(n - k)}$ as $q \rightarrow \infty$. \section{Combinatorial proof of theorem \ref{main1}}\label{Combi} %It is enough to show that for $k^2 = \alpha(\Pi)$, if every set of $k + 1$ points in a projective plane of order $q$ is not blocking at most $k$ %lines, then $k\leq (q+1)(\sqrt{q}-1)$. Let $\Sigma$ be a set of $k+1$ points in a projective plane $\Pi$ of order $q$ such that $j+1$ lines of $\Pi$ do not contain any point of $\Sigma$. Let $L :=\{\ell_1,\dots,\ell_{q^{2}+q-j}\}$ be the set of lines intersecting $\Sigma$, and set $x_i=\left|\ell_i\cap\Sigma\right|$. We count the pairs $(\wp,\ell)$ with $\wp \in\Sigma$, $\ell \in L$ and $\wp \in \ell$: \[ \sum_{i=1}^{q^{2}+q-j} x_i= (k+1)(q+1). \] Next we count triples $(\wp_1,\wp_2,\ell)$ with $\wp_1,\wp_2\in\Sigma$, $\wp_1\neq \wp_2$, $\ell \in L$ and $\wp_1,\wp_2\in \ell$: \[\sum_{i=1}^{q^{2}+q-j} x_i(x_i-1)=(k+1)k.\] Hence \[\sum_{i=1}^{q^{2}+q-j} x_i^2=(k+1)(q+1+k).\] Now, by the Cauchy-Schwarz inequality, \begin{equation}\label{variance}0\leq (q^2+q-j)\sum_{i=1}^{q^{2}+q-j} x_i^2 -\left( \sum_{i=1}^{q^{2}+q-j} x_i\right)^2 ,\end{equation} and so \begin{equation}0\leq(q^2+q-j)(k+1)(q+1+k) - (k+1)^2(q+1)^2. \end{equation} and as $(k+1)$ is a positive common factor we also have \begin{equation}\label{eq-l} 0\leq(q^2+q-j)(q+1+k) - (k+1)(q+1)^2. \end{equation} Similarly, interchanging the roles of $j$ and $k$, \begin{equation}\label{eq-m} 0 \leq (q^2+q-k)(q+1+j)-(j+1)(q+1)^2 \end{equation} Adding the inequalities (\ref{eq-l}) and (\ref{eq-m}) we obtain after simplification \begin{equation}\label{eq-n} q((j+1)+(k+1))+(j+1)(k+1)\leq q(q^{2}+q+1) \end{equation} Using the inequality of arithmetic and geometric means, \[ 2q\sqrt{(j+1)(k+1)} + (j+1)(k+1) \leq q(q^{2}+q+1)\] Putting $\sqrt{(j+1)(k+1)}=t$ yields the quadratic inequality $$t^{2}+2qt-q(q^{2}+q+1)\leq 0$$ The positive solution of the corresponding quadratic equation is $t=\sqrt{q}(q-\sqrt{q}+1)$. Hence $\alpha(\Pi) \leq q(q-\sqrt{q}+1)^{2}$. So assume now $\alpha(\Pi)=q(q-\sqrt{q}+1)^{2}$. As we used the inequality of arithmetic and geometric means, in order to fulfill (\ref{eq-n}) we need to have $j+1=k+1=\sqrt{q}(q-\sqrt{q}+1)$, implying, using Inequality (\ref{variance}), that the variance of the $x_i$ is zero. We conclude that $x_i=\sqrt{q}$ for all $i$. Consequently $\Sigma$ is a point set such that each line of $\Pi$ intersects $\Sigma$ in either $0$ or $\sqrt{q}$ points, that is, $\Sigma$ is a maximal arc of degree $\sqrt{q}$. This proves the theorem. \qed \section{Spectral proofs of the upper bounds in Theorems \ref{main1a} and \ref{main2}}\label{spec} A rank two geometry $\Pi = (P,L,I)$ can be recast as a bipartite graph whose parts are $P$ and $L$ and such that $\wp \in P$ is joined by an edge to $\ell \in L$ if and only if $(\wp,\ell) \in I$. This bipartite graph is, as mentioned earlier, called the {\em incidence graph of $\Pi$} and denoted $G(\Pi)$. In this section, we use the spectrum of the adjacency matrix of $G(\Pi)$ to prove the upper bounds on $\alpha(\Pi)$ given in Theorems \ref{main1a} and \ref{main1}. \subsection{Linear algebra} We briefly recall some basic linear algebra. If $G$ is a graph then the {\em adjacency matrix} of $G$ is the symmetric matrix $A(G)$ whose rows and columns are indexed by the vertices of $G$ and such that $A_{uv} = 1$ if $\{u,v\}$ is an edge of $G$, and $A_{uv} = 0$ otherwise. We use the convention that the eigenvalues of $A$, which are real, are listed in non-increasing order of absolute value, namely $\lambda_1,\lambda_2,\lambda_3, \dots, \lambda_n$ where $|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_n|$. We shall let $e_1,e_2,\dots,e_n$ be an orthonormal basis of eigenvectors corresponding to the eigenvalues $\lambda_1,\lambda_2,\dots,\lambda_n$. The matrix $A$ is {\em doubly stochastic} if all its row and column sums equal some fixed integer $k$. In that case, if a set $V$ of size $N$ indexes the rows of $A$, then $\lambda_1 = k$. If $A$ is the adjacency matrix of a bipartite graph with parts $U$ and $V$ of sizes $M$ and $N$ respectively, and every vertex in $U$ has degree $a$ and every vertex in $V$ has degree $b$, and $1_U$, respectively $1_V$, denotes a vector which is $1$ on $U$ and zero on $V$, respectively $1$ on $V$ and zero on $U$, then \begin{equation}\label{eigs} e_1 = \frac{\sqrt{a}1_U + \sqrt{b}1_V}{\sqrt{aM + bN}} \quad \mbox{ and } \quad e_2 = \frac{\sqrt{a}1_U - \sqrt{b}1_V}{\sqrt{aM + bN}} \end{equation} are both normalized eigenvectors of $A$ corresponding to eigenvalues $\lambda_1 = \sqrt{ab}$ and $\lambda_2 = -\sqrt{ab}$. All remaining eigenvectors $e_{3},\cdots,e_{n}$ are orthogonal to these eigenvectors. In the particular case that $A$ is doubly stochastic, so every vertex of the bipartite graph has degree $k = a = b$, we get $\lambda_1 = k$ and $\lambda_2 = -k$. \subsection{Main lemma} If $G$ is a bipartite graph with parts $U = \{1,2,\dots,M\}$ and $V = \{M + 1,M + 2,\dots,M + N\}$ and adjacency matrix $A$, and $X$ and $Y$ are subsets of $U$ and $V$ respectively, then $e(X,Y)$ denotes the number of edges of $G$ with one end in $X$ and the other end in $Y$. We observe that \[ e(X,Y) = 1_Y^t A 1_X.\] The main lemma we require is listed below. This appears as Theorem 3.1.1 on page 27 of \cite{HPHD} (see also the paragraph on page 28 following its proof) and as Theorem 5.1 on page 602 in \cite{H}. %S. Cioab\u{a} pointed out that this lemma is a consequence of a result of Haemers from %his Ph.D. thesis (see Cioab\u{a} and Godsil~\cite{Ci}). For completeness, we give a direct proof. \begin{lemma}\label{expander} If $G$ is a bipartite graph with parts $U$ and $V$ such that every vertex of $U$ has degree $a$ and every vertex of $V$ has degree $b$, and $X \subset U$ and $Y \subset V$. Let $A$ be the adjacency matrix of $G$ with eigenvalues $\lambda_1,\lambda_2,\dots$ such that $|\lambda_1| \geq |\lambda_2| \geq \dots$. Then \[ \Bigl|e(X,Y) - \frac{\sqrt{ab}}{\sqrt{|U||V|}} |X||Y|\Bigr| \leq |\lambda_3|\sqrt{|X||Y|\textstyle{(1 - \frac{|X|}{|U|})(1 - \frac{|Y|}{|V|})}}.\] \end{lemma} \begin{proof} Let $|X| = m$, $|Y| = n$, $|U| = M$, $|V| = N$, and let $e_1,e_2,\dots,e_{M + N}$ be an orthonormal basis of eigenvectors of $A$ corresponding to the eigenvalues $\lambda_1,\lambda_2,\dots$ respectively. Since $A^2$ is doubly stochastic with row and column sums equal to $ab$, we must have $\lambda_1 = \sqrt{ab}$ and as the spectrum of a bipartite graph is symmetric around zero $\lambda_2 = -\sqrt{ab}$, with corresponding eigenvectors given by (\ref{eigs}). Note that the number of edges in $G$ is $aM = bN$. Let $1_X = \sum x_i e_i$ and $1_Y = \sum y_i e_i$ for some reals $x_i,y_i$. Since $x_i = \left<1_X,e_i\right>$ and similarly for every $y_i$, we compute \begin{equation}\label{xandy} x_1 = \frac{m}{\sqrt{2M}} = x_2 \quad \mbox{ and } \quad y_1 = \frac{n}{\sqrt{2N}} = -y_2. \end{equation} It follows using (\ref{xandy}) and (\ref{eigs}) that \begin{eqnarray*} e(X,Y) \; \; = \; \; 1_Y^t A 1_X &=& \sum_{i=1}^{M + N} \lambda_i x_i y_i \\ &=& \lambda_1 x_1 y_1 + \lambda_2 x_2 y_2 + \sum_{i=3}^{M + N} \lambda_i x_i y_i \\ &=& \frac{\sqrt{ab}mn}{\sqrt{MN}} + \sum_{i = 3}^{M + N} \lambda_i x_i y_i. \end{eqnarray*} By Cauchy-Schwarz, \[ \sum_{i = 3}^{M + N} \lambda_i x_i y_i \leq |\lambda_3| \left(\sum_{i=3}^{M + N} x_i^2\right)^{1/2} \left(\sum_{i = 3}^{M + N} y_i^2\right)^{1/2}.\] This gives \[ \Bigl|e(X,Y) - \frac{\sqrt{ab}}{\sqrt{MN}}mn\Bigr| \leq |\lambda_3|\sqrt{(m - x_1^2 - x_2^2)(n - y_1^2 - y_2^2)}.\] Using (\ref{xandy}), the lemma follows. \end{proof} \bigskip This lemma is especially applicable when $\lambda_3$ is small: in this case we are dealing with a {\em pseudorandom bipartite graph}, and the quantity $e(X,Y)$ is close to $\sqrt{ab}|X||Y|/\sqrt{MN}$ for all $X,Y$ which are not too small. For further details on pseudorandom graphs, see Krivelevich and Sudakov~\cite{KS}. We now use the lemma to prove Theorems \ref{main1a} and \ref{main2}. We remark that Theorem \ref{main1} can also be proved using the lemma in exactly the same way. \subsection{Proof of the upper bound in Theorem \ref{main1a}}\label{uppermain1} We will count the number of paths of length $3$ between a point $\wp$ and a $k$-space $\Omega$ in $\PG(n,q)$. There are two possibilities, depending on whether $\wp$ is incident with $\Omega$ or not. There are two cases \begin{tabular}{lp{5in}} $\bullet$ & If $\wp$ is incident with $\Omega$ we deduce that there are $(N_{0,k}-1)N_{k-2,n-2} +N_{k-1,n-1}$ such paths.\\ $\bullet$ & If $\wp$ is not incident with $\Omega$ we obtain $N_{0,k}N_{k-2,n-2}$ paths of length $3$. \end{tabular} Let $A$ be the adjacency matrix of the point - $k$-space incidence geometry of $\PG(n,q)$, and let $J$ be $N_{0,n}\times N_{k,n}$ matrix filled with $1$s. We now obtain $$A^3=N_{0,k}N_{k-2,n-2}\left(\begin{array}{ll} 0 & J \\ J^T & 0 \end{array}\right) + (N_{k-1,n-1}-N_{k-2,n-2})A,$$ or, letting $S = \left(\begin{array}{ll} 0 & J \\ J^T & 0 \end{array}\right)$, we obtain $$A^3=N_{0,k}N_{k-2,n-2}S + q^kN_{k-1,n-2}A.$$ Clearly the only non-zero eigenvalues of $S$ are $\sqrt{N_{0,n}N_{k,n}}$ and $-\sqrt{N_{0,n}N_{k,n}}$, and these eigenvalues correspond to the eigenvalues $\sqrt{N_{0,k}N_{k-1,n-1}}$ and $-\sqrt{N_{0,k}N_{k-1,n-1}}$ of $A$ (this can be checked through direct computation). Hence, the other eigenvalues $\lambda$ of $A$ satisfy $$\lambda^3=q^kN_{k-1,n-2}\lambda.$$ So every other non-zero eigenvalue of $A$ satisfies $\left|\lambda\right|=\sqrt{q^kN_{k-1,n-2}}$. Applying Lemma \ref{expander} we obtain, using $a=N_{k-1,n-1}$ and $b=N_{0,k}$, $$ \frac{N_{k-1,n-1}N_{0,k}}{N_{0,n}N_{k,n}}\left|X\right|\left|Y\right|\leq q^kN_{k-1,n-2}.$$ Using $N_{k,n} \sim q^{(k + 1)(n - k)}$ as $q \rightarrow \infty$, we obtain the upper bound \[ \alpha(\Pi) \lesssim q^{(k + 2)(n - k)}.\] This completes the proof of the upper bound in Theorem \ref{main1a}. \subsection{Proof of the upper bound in Theorem \ref{main2}}\label{uppermain2} Let $\Pi$ denote a generalized $n$-gon (see Subsection \ref{gp}) of order $q \geq 2$, let $A$ denote the adjacency matrix of the point-line incidence graph $G(\Pi)$, and let $B = A^{n - 1}$. The entry $B_{ij}$ is the number of walks of length $n - 1$ from vertex $i$ to vertex $j$ in the bipartite graph $G(\Pi)$. We consider the cases $n \in \{3,4,6\}$ separately to prove the upper bounds in Theorem \ref{main2}. The case of projective planes, namely $n = 3$, is covered by Theorem \ref{main1}, so we move on to generalized quadrangles and hexagons. \bigskip {\bf Generalized quadrangles.} Consider the case of a generalized quadrangle of order $q$. Here we consider the equation \[ A^{3}=B = \left(\begin{array}{ll} 0 & J \\ J & 0 \end{array}\right) + 2qA\] which holds since there is a unique path of length three between a non-incident point-line pair, and there are $2q+1$ paths of length three between an incident point-line pair. From the above matrix equation, every eigenvalue $\lambda \not \in \{-(q + 1),q + 1\}$ of $A$ has $|\lambda| \leq \sqrt{2q}$. Apply Lemma \ref{expander}, \[ |e(X,Y) - \frac{(q+1)(q-1)|X||Y|}{q^4-1}| \leq \sqrt{2q} \sqrt{|X||Y|}.\] For there to be no incidences between $X$ and $Y$, we require \[ \frac{(q+1)(q-1)|X||Y|}{q^4-1} \leq \sqrt{2q|X||Y|}\] and this proves the upper bound in Theorem \ref{main2} for generalized quadrangles. \medskip {\bf Generalized Hexagons.} Finally, consider the case of a generalized hexagon of order $q$. Here we consider the equation \[ A^{5}=B = \left(\begin{array}{ll} 0 & J \\ J & 0 \end{array}\right) + 4qA^3 - 3q^2A\] which holds since there is a unique path of length five between a non-incident point-line pair at distance $5$, there are $4q+1$ paths of length five between a non-incident point-line pair at distance $3$, and there are $5q^2+4q+1$ paths of length five between an incident point-line pair. We obtain that every eigenvalue $\lambda \not \in \{-(q + 1),q + 1\}$ of $A$ has $|\lambda| \leq \sqrt{3q}$. Applying Lemma \ref{expander}, \[ |e(X,Y) - \frac{(q+1)(q-1)|X||Y|}{q^6-1}| \leq \sqrt{3q|X||Y|}.\] For there to be no incidences between $X$ and $Y$, we require $e(X,Y) = 0$ and therefore \[ \frac{(q+1)(q-1)|X||Y|}{q^6-1} \leq \sqrt{3q|X||Y|}.\] This proves the upper bound in Theorem \ref{main2} for generalized hexagons. {\bf Remark.} The eigenvalues for generalized quadrangles of order $q$ can also be found on Table 6.4 of \cite{BCN} and those for generalized hexagons in Table 1 of \cite{DWVM}. \bigskip \section{Constructions}\label{construct} In this section we will establish the lower bounds in Theorem \ref{main1a} and Theorem \ref{main2} by providing several constructions. \subsection{Construction for point $k$-space incidences} We construct a set $X$ of points and $Y$ of $k$-spaces in $\PG(n,q),\:n>2$ such that $X$ and $Y$ have no incidences between them and $|X||Y|$ is within a factor four of the upper bound in Theorem \ref{main1a}. Pick $\lfloor q/2 \rfloor$ hyperplanes in $\PG(n,q)$ through an $(n - 2)$-space. Then let $Y$ be the set of $k$-spaces contained in at least one of these hyperplanes, and let $X$ be the set of points not in these hyperplanes. Then \[ |X| = N_{0,n} - \lfloor \frac{q}{2} \rfloor (N_{0,n-1} - N_{0,n-2}) + N_{0,n-2} \sim \frac{1}{2}N_{0,n} \sim \frac{1}{2}q^n.\] The number of $k$-spaces is \[ |Y| = \lfloor \frac{q}{2} \rfloor (N_{k,n-1} - N_{k,n-2}) + N_{k,n-2} \sim \frac{1}{2}q^{1 + (k+1)(n-k-1)}.\] Here we used $N_{k,n} \sim q^{(k + 1)(n - k)}$ as $q \rightarrow \infty$. Therefore \[ |X||Y| \sim \frac{1}{4}q^{1 + (k + 1)(n - k - 1) + n} = \frac{1}{4}q^{(k + 2)(n - k)}.\] This gives the first lower bound in Theorem \ref{main1a}. \subsection{Construction for point-hyperplane incidences} \begin{lemma}\label{Construction1} If in $\PG(n,q)$ there exists a point set $X$ and a hyperplane set $Y$ with no incidences between them, and with $\left| X\right|=\left| Y\right|=k$, then there exists a point set $\overline{X}$ and a hyperplane set $\overline{Y}$ in $\PG(n+2,q)$ with no incidences between them, and with $\left| \overline{X}\right|=\left| \overline{Y}\right|=qk$. \end{lemma} \begin{proof} Let $X$ be a set of $k$ points and let $Y$ be a set of $k$ hyperplanes in $\Pi:=\PG(n,q)$ having no incidences between them. Embed $\Pi$ as a hyperplane in $\Omega:=\PG(n+1,q)$, and consider a point $\wp \in\Omega\setminus\Pi$. Let $Y'$ be the set of all hyperplanes of $\Omega$ spanned by $\wp$ and an element of $Y$. Now embed $\Omega$ as a hyperplane in $\PG(n+2,q)$. Let $\overline{X}$ be the set of all points on the cone $\wp X$ distinct from $\wp$ (this is in fact a subset of $\Omega$) . Let $\overline{Y}$ be the set of all hyperplanes of $\PG(n+2,q)$ intersecting $\Omega$ exactly in an element of $Y'$. Then $\left|\overline{X}\right|=\left|\overline{Y}\right|=qk$, and there are no incidences between $\overline{X}$ and $\overline{Y}$. \end{proof} \begin{cor} In $\PG(n,q)$, $n$ odd, there exists a set of $q^\frac{n-1}{2}\lfloor\frac{q+1}{2}\rfloor$ points and a set of $q^\frac{n-1}{2}\lfloor\frac{q+1}{2}\rfloor$ hyperplanes having no incidences. \end{cor} \begin{proof} Consider two disjoint point sets $X$ and $Y$ of size $\lfloor\frac{q+1}{2}\rfloor$ in $\PG(1,q)$. Now apply Lemma \ref{Construction1} (repeatedly if $n\geq5$). \end{proof} \begin{cor}\label{Mubayi-Williford} In $\PG(n,q)$, $n$ even, there exists a set of at least $cq^{\frac{n+1}{2}}$ points and a set of at least $cq^{\frac{n+1}{2}}$ hyperplanes having no incidences. Here $c=\frac{1}{2}$ if $q$ is an even power of an odd prime, $c=\frac{120}{73\sqrt{73}}$ if $q$ is an odd power of an odd prime, $c=\frac{1}{2\sqrt{2}}$ if $q$ is an odd power of $2$, and where $c=1-\frac{1}{\sqrt{q}}+\frac{1}{q}$ if $q$ is an even power of $2$. \end{cor} \begin{proof} By Theorem 5 in Mubayi and Williford~\cite{MW}, there exist a set of points $X$ of size at least $cq^\frac{3}{2}$, and a set of lines $Y$ of size at least $cq^\frac{3}{2}$ in $\PG(2,q)$ with no incidences between them. Now apply Lemma \ref{Construction1} (repeatedly if $n\geq6$). \end{proof} However, in certain cases we can give more direct constructions. Though the bounds in Corollaries \ref{even dimension1} and \ref{even dimension3} are similar to the bound from Corollary \ref{Mubayi-Williford}, the constructions are somewhat more straightforward since we do not need to care about the existence of a certain polarity (the Mubayi-Williford constructions are done in the polarity graph). \begin{cor}\label{even dimension1} In $\PG(n,q)$, $n$ even, $q$ an even power of $2$, there exists a set of $q^{\frac{n+1}{2}}-q^\frac{n}{2}+q^\frac{n-1}{2}$ points and a set of $q^{\frac{n+1}{2}}-q^\frac{n}{2}+q^\frac{n-1}{2}$ hyperplanes having no incidences. \end{cor} \begin{proof} This follows immediately from the existence of a maximal arc of degree $\sqrt{q}$ in $\PG(2,q)$ together with Lemma \ref{Construction1}. \end{proof} \begin{cor}\label{even dimension2} In $\PG(n,q)$, $n$ even, $q$ an odd power of $2$, there exists a set of $\frac{1}{\sqrt{2}}q^{\frac{n+1}{2}}-q^\frac{n}{2}+\frac{1}{\sqrt{2}}q^\frac{n-1}{2}$ points and a set of $\frac{1}{\sqrt{2}}q^{\frac{n+1}{2}}-q^\frac{n}{2}+\frac{1}{\sqrt{2}}q^\frac{n-1}{2}$ hyperplanes having no incidences. \end{cor} \begin{proof} Consider a maximal arc $\mathcal{K}_1$ of degree $\sqrt{2q}$ containing a maximal arc $\mathcal{K}_2$ of degree $\sqrt{q/2}$ in $\PG(2,q)$ (such arcs always exist by the results of Denniston \cite{Den}). Now let $X$ be the point set of $\mathcal{K}_2$, and let $Y$ be the set of lines exterior to $\mathcal{K}_1$. Then $\left|X\right|= \left|Y\right|= \frac{1}{\sqrt{2}}q^{\frac{3}{2}}-q+\sqrt{q/2}$, and there are clearly no incidences between $X$ and $Y$. The result now follows using Lemma \ref{Construction1}. \end{proof} The lower bound on $\alpha(\PG(n,q))$ arising from the above corollary is a factor $4$ larger than the bound one would obtain using Corollary \ref{Mubayi-Williford}. \begin{cor}\label{even dimension3} In $\PG(n,q)$, $n$ even, $q$ an even power of an odd prime, there exists a set of $\frac{1}{2}(q^{\frac{n+1}{2}}+q^{\frac{n-2}{2}})$ points and a set of $\frac{1}{2}(q^{\frac{n+1}{2}}+q^{\frac{n-2}{2}})$ hyperplanes having no incidences. \end{cor} \begin{proof} Consider a non-degenerate Hermitian curve in $\PG(2,q)$. Let $X$ be half of the points on this curve, and let $Y$ be the tangent lines ($1$-secants) to the other half of the points. Now apply Lemma \ref{Construction1}. \end{proof} In fact, the bound in the above lemma can be slightly improved by choosing the points on the Hermitian curve more carefully. We do not pursue a detailed analysis here of such construction, but it should be clear that any good example in $\PG(2,q)$ (respectively $\PG(3,q)$) will yield good examples in $\PG(2n,q)$ (respectively $\PG(2n+1,q)$). A more interesting open problem here may be the question whether the example from Corollary \ref{even dimension1} is optimal. The results obtained in this section finally prove Theorem \ref{main1a}. \subsection{Construction in generalized quadrangles} If $A$ is a set of points in a generalized polygon we write $A^\perp$ for the set of all points collinear with all points in $A$, and we write $A^{\perp\perp}$ for $(A^\perp)^\perp$ (here a point is considered to be collinear with itself). Let $\mathcal{Q}$ be a GQ of order $q$. A point $\wp$ of $\mathcal{Q}$ is called {\it regular} if and only if $\left|\{\wp,\wp'\}^{\perp\perp}\right|=q+1$ for all points $\wp'\neq\wp$. Let $\mathcal{Q}$ be a GQ of order $q$ with a regular point $\wp$, and let $\Pi$ be the projective plane naturally arising from $\wp$ and $\mathcal{Q}$ (the points of $\Pi$ are $\wp$ and all points collinear with $\wp$ in $\mathcal{Q}$, whereas the lines of $\Pi$ are the lines of $\mathcal{Q}$ through $\wp$, and the sets $\{\wp,\wp'\}^\perp$ of points collinear with both $\wp$ and $\wp'$, where $\wp'$ ranges over the points not collinear with $\wp$). For more on generalized quadrangles and regularity see Chapter 1 of \cite{PT}. \begin{lemma}\label{construction2} Let $\mathcal{Q}$, $\wp$ and $\Pi$ be as above, and suppose that in $\Pi$ there exists a point set $X$, containing $\wp$, and a line set $Y$ with no incidences between them, and with $\left| X\right|=\left| Y\right|=k$. Then there exists a point set $\overline{X}$ and a line set $\overline{Y}$ in $\mathcal{Q}$ with no incidences between them, and with $\left| \overline{X}\right|=qk$ and $\left| \overline{Y}\right|=qk+1$. \end{lemma} \begin{proof} Define $\overline{Y}$ to be the set of lines of $\mathcal{Q}$ that contain a point of $X$. Then $\left|\overline{Y}\right|=qk+1$. Define $\overline{X}$ to be the set of all points, distinct from $\wp$, that are collinear with all points on some element of $Y$. Then, since $\wp$ is regular, $\left|\overline{X}\right|=qk$. Furthermore there are no incidences (in $\mathcal{Q}$) between $\overline{X}$ and $\overline{Y}$. The latter can easily be seen as follows. Assume, by way of contradiction, that $\wp'$ would be a point of $\overline{X}$ incident with an element of $\overline{Y}$. Clearly $\wp'$ cannot be a point of $X$. But then, since $X$ and $Y$ have no incidences, $\wp'$ would be collinear with at least $q+2$ points of $\Pi$, a contradiction. \end{proof} \begin{remark} By duality this construction also works in any generalized quadrangle of order $q$ that contains a regular line. \end{remark} One can now for example apply this construction to the GQ $W(2^{2h})$. \begin{cor} In $W(q)$, with $q=2^{2h}$, there exist a set of $q^{5/2}-q^2+q^{3/2}$ points and a set of $q^{5/2}-q^2+q^{3/2}$ lines, with no incidences between them. \end{cor} \begin{proof} Fix any point $\wp$ in $W(q)$. Then $\wp$ is regular (see e.g. 3.3.1(i) in \cite{PT}), and the resulting plane $\Pi$ is isomorphic to $\PG(2,q)$. Now use Lemma \ref{construction2} starting with a maximal arc of degree $\sqrt{q}$ in $\Pi$. \end{proof} \begin{remark} In fact the result of the previous corollary remains valid in any GQ $T_2(\mathcal{O})$ of Tits of order $q=2^h$. For a definition of and discussion on $T_2(\mathcal{O})$ see Chapter 3 of \cite{PT}. \end{remark} This concludes the proof of the lower bound in Theorem \ref{main2} for $n=4$. \subsection{Construction in generalized hexagons} Here we restrict ourselves to the only known generalized hexagon of order $q$, the split Cayley hexagon $H(q)$. For more on this generalized hexagon, and some of its properties used in the proof of Lemma \ref{construction3}, we refer to Section 2.4 of \cite{HVM}. It is well known that $H(q)$ can be embedded in the $6$-dimensional quadric $Q(6,q)$, and that the points of $H(q)$ are all points of $Q(6,q)$, and the lines of $H(q)$ are certain lines of $Q(6,q)$. The following two properties will be important for us: \begin{center} \begin{tabular}{lp{5in}} (1) & The $q+1$ lines of $H(q)$ through a given point $\wp$ are contained in a plane of $Q(6,q)$ (and such plane is isomorphic to $\PG(2,q)$). \\ (2) & Two distinct points on $Q(6,q)$ are collinear in the quadric if and only if they are at distance $2$ or $4$ in $H(q)$ (in the incidence graph of $H(q)$). \end{tabular} \end{center} \begin{lemma}\label{construction3} Let $X$ be a point set, and let $Y$ be a line set in $\PG(2,q)$ with no incidences between them, and with $\left| X\right|=\left| Y\right|=k$. Then there exists a point set $\overline{X}$ and a line set $\overline{Y}$ in $H(q)$ with no incidences between them, and with $\left| \overline{X}\right|=q^3k$ and $\left| \overline{Y}\right|=kq^{3}+q^{2}+q+1$. \end{lemma} \begin{proof} Consider the classical generalized hexagon $H(q)$ in its natural embedding in the $6$-dimensional quadric $Q(6,q)$. Consider any point $\wp$ of $H(q)$, and let $\Pi$ be the plane containing the lines of $H(q)$ through $\wp$. Let $X$ be a set of $k$ points containing $\wp$ in $\Pi$, and let $Y$ be a set of $k$ lines in $\Pi$, with the property that there are no incidences (in $\Pi$) between $X$ and $Y$. Now define $\overline{Y}$ to be the set of all lines of $H(q)$ at distance $1$ or $3$ from a point of $X$ (in the incidence graph of $H(q)$). Furthermore, define $\overline{X}$ to be the set of all points not in $\Pi$ contained in any plane of $Q(6,q)$ intersecting $\Pi$ exactly in an element of $Y$. Then $\left| \overline{Y}\right|=(k-1)q+q+1+(k-1)q^3 +(q^2+q+1-k)q=kq^3+q^2+q+1$, $\left| \overline{X}\right|=kq^3$, and there are no incidences between $\overline{X}$ and $\overline{Y}$. The latter can be seen as follows. Assume a point of $X$ would be collinear in $Q(6,q)$ with a point $\wp'$ of $\overline{X}$. Then $\wp'$ would be collinear with more than $q+1$ points of $\Pi$ (in $Q(6,q)$), clearly a contradiction. Hence, the points of $\overline{X}$ all are at distance $6$ (in $H(q)$) from all points of $X$. Now, since the lines of $\overline{Y}$ are exactly the lines at distance $1$ and $3$ (in $H(q)$) from the points of $X$, these lines contain only points at distance $2$ and $4$ (in $H(q)$) from the points of $X$. It follows there are no incidences between $\overline{X}$ and $\overline{Y}$. \end{proof} \begin{cor} Let $c = \frac{120}{73\sqrt{73}}$. Then in $H(q)$ there exist a set of at least $cq^{9/2}$ points and a set of at least $cq^{9/2}$ lines, with no incidences between them. \end{cor} \begin{proof} Apply Lemma \ref{construction3} starting with a set $X$ of $cq^{3/2}$ points and a set $Y$ of $cq^{3/2}$ lines in $\Pi$, with no incidences between $X$ and $Y$. Such sets always exist by the results of Theorem 5 in Mubayi and Williford \cite{MW}. \end{proof} \begin{cor} In $H(q)$, $q=2^{2h}$, there exist a set of $q^{9/2}-q^4+q^{7/2}$ points and a set of $q^{9/2}-q^4+q^{7/2}$ lines, with no incidences between them. \end{cor} \begin{proof} Apply Lemma \ref{construction3} starting with a maximal arc of degree $\sqrt{q}$ in $\Pi$. \end{proof} This concludes the proof of the lower bound in Theorem \ref{main2} for $n=6$. \bigskip \section{Proof of the upper bound in Theorem \ref{main3}}\label{last} A key lemma for Theorem \ref{main3} is the following: this lemma shows that most points in a partial linear space $\Pi = (P,L,I)$ with $|P| = |L| = N$ are contained in at most about $\sqrt{N}$ lines, and most lines contain at most about $\sqrt{N}$ points. \begin{claim} Let $\varepsilon > 0$ and let $\Pi = (P,L,I)$ be a partial linear space such that $|P| = |L| = N$. Then the number of lines containing at least $(1 + \varepsilon)\sqrt{N}$ points is less than $\sqrt{N}/\varepsilon$. \end{claim} \begin{proof} Let $T$ be the set of lines each containing at least $(1 + \varepsilon)\sqrt{N}$ points and suppose $|T| = c\sqrt{N}$ -- the proof will be similar if $T$ is the set of points contained in at least $(1 + \varepsilon)\sqrt{N}$ lines. The number of incidences $(\wp,\ell) \in I$ with $\ell \in T$ is at least $(1 + \varepsilon)cN$. This shows that a point $\wp \in P$ is contained on average in at least $(1 + \varepsilon)c$ lines in $T$. Let $T(\wp)$ denote the number of ordered pairs of lines in $T$ both containing $\wp$. Then since every pair of lines in $T$ determines at most 1 point, \[ \sum_{\wp \in P} T(\wp) \leq |T|(|T| - 1) < c^2N.\] On the other hand, using the average, \[ \sum_{\wp \in P} T(\wp) \geq (1 + \varepsilon)c N((1 + \varepsilon)c - 1).\] It follows that \[ (2 + \varepsilon)\varepsilon c < 1 + \varepsilon\] from which $c < 1/\varepsilon$, and the result follows. \end{proof} %This shows that if $\Pi$ is a partial linear space with $N$ points and $N$ lines, we can delete at most $\sqrt{N}/\varepsilon$ points and %$\sqrt{N}/\varepsilon$ lines to obtain a new partial linear space $\Pi(\varepsilon) = (P,L,I)$ with incidences induced from $\Pi$ and prove Theorem \ref{main3} in this new partial linear space. Note that $|P|,|L| \geq N - \sqrt{N}/\varepsilon$. \subsection{Random sets of points and lines} Let $A_1,A_2,\dots$ be a sequence of events in a probability space. Throughout the proof, we write $A_N$ a.a.s (asymptotically almost surely) to denote $\p(A_N) \rightarrow 1$ as $N \rightarrow \infty$. Starting with a partial linear space $\Pi'_N$ with $N$ points and $N$ lines, use Claim 1 to delete points and lines of $\Pi'_N$ to obtain a partial linear space $\Pi_N = (P,L,I)$ with $|P|,|L| \geq N - \sqrt{N}/\varepsilon$ such that every point in $\Pi_N$ is in at most $(1 + \varepsilon)\sqrt{N}$ lines of $\Pi_N$, and every line of $\Pi_N$ contains at most $(1 + \varepsilon)\sqrt{N}$ points of $\Pi_N$. Here $\varepsilon > 0$ is a fixed positive constant. \medskip Now pick points of $P$ with probability $p = 1/\sqrt{N}$ and let $X \subseteq P$ be the random set of picked points and let $Y = \{\ell \in L : X \cap \ell = \emptyset\}$. We will show $|X||Y| \gtrsim N^{3/2}/e^{1 + \varepsilon}$ a.a.s, and since $\varepsilon > 0$ is arbitrary, this shows $|X||Y| \gtrsim N^{3/2}/e$. First, the expected size of $X$ is \[ \e(|X|) = p|P| \geq \sqrt{N} - \frac{1}{\varepsilon}.\] Now $|X|$ has a binomial distribution with success probability $p = 1/\sqrt{N}$ in $N$ trials. By the Chernoff Bound~\cite{C}, for any $\delta \in (0,1)$, and $\varepsilon > 2/\sqrt{N}$, \[ \p(|X| \leq (1 - \delta)\e(|X|)) \leq e^{-\delta^2 \e(|X|)/4} < e^{-\delta^2 \sqrt{N}/8}.\] We conclude that $|X| \gtrsim \sqrt{N} \mbox{ a.a.s}$. \medskip Now we consider $|Y|$. For each $\ell \in L$, let $A_{\ell}$ be the event $X \cap \ell = \emptyset$; then $|Y|$ is the number of events $A_{\ell}$ which occur. As $N \rightarrow \infty$, \[ \p(A_{\ell}) = (1 - p)^{|\ell|} \geq \Bigl(1 - \frac{1}{\sqrt{N}}\Bigr)^{(1 + \varepsilon)\sqrt{N}} \rightarrow e^{-(1 + \varepsilon)}.\] Hence $\e(|Y|) \gtrsim N/e^{1 + \varepsilon}$. We now estimate $\mbox{var}(|Y|)$. Note that $|\ell \cap \ell'| \leq 1$ for every pair of distinct lines $\ell,\ell' \in L$, so \[ \p(A_{\ell} \cap A_{\ell'}) \leq \frac{1}{1 - p} \p(A_{\ell})\p(A_{\ell'}). \] It follows that \[ \mbox{var}(|Y|) \leq \Bigl(\frac{1}{1 - p} - 1\Bigr)\e(|Y|)^2.\] By Chebyshev's Inequality, since $1/(1 - p) - 1 \rightarrow 0$ as $N \rightarrow \infty$, \[ |Y| \gtrsim \frac{N}{e^{1 + \varepsilon}} \quad \mbox{ a.a.s}.\] It follows that $|X| \gtrsim \sqrt{N}$ and $|Y| \gtrsim N/e^{1 + \varepsilon}$ a.a.s. This proves Theorem \ref{main3}. \qed %\bigskip \subsection*{Acknowledgements} \nonumber We would like to thank S. Cioab\u{a} for pointing out his notes with C. Godsil~\cite{Ci}, and pointing out the paper by N. Tokushige~\cite{Tok}. We appreciated the constructive comments of the referees which improved the exposition of this paper. %\bigskip \begin{thebibliography}{20} \bibitem{BallBlokMaz} S. Ball, A. Blokhuis and F. Mazzocca, Maximal arcs in Desarguesian planes of odd order do not exist, {\it Combinatorica} {\bf 17}, 31-41, 1997. \bibitem{B} B. Bollob\'{a}s, Random graphs. Second Edition {\it Cambridge studies in Advanced mathematics} {\bf 73} xviii+498pp., 2001. \bibitem{BCN} A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance regular graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Springer-Verlag, Berlin, 1989. \bibitem{C} H. Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations, {\it Annals of Mathematical Statistics} {\bf 23 (4)} 493-507, 1952. \bibitem{Ci} S. Cioab\u{a} and C. Godsil, Notes on cross-independent sets in graphs and eigenvalues, unpublished manuscript, November 2011. \bibitem{Fan} F. Chung and R. Graham, Erd\H{o}s on Graphs, {\it AK Peters Ltd.} xiv+142pp., 1998. \bibitem{Den} R. Denniston, Some maximal arcs in finite projective planes, {\it J. Comb. Theory} {\bf 6}, 317-319, 1969. \bibitem{DWVM} A. De Wispelaere and H. Van Maldeghem, Regular partitions of (weak) finite generalized polygons {\em Des. Codes. Cryptogr.}, {\bf 47}(1-3): 53-73, 2008. \bibitem{LLL} P. Erd\H{o}s and L. Lov\`asz, Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado and V.T. S\`os, Infinite and finite sets (to Paul Erd\H{o}s on his 60th birthday). {\bf II}. {\it North-Holland} 609-627, 1975. \bibitem{FH} W. Feit and G. Higman, The nonexistence of certain generalized polygons. {\it J. Algebra} {\bf 1} 114-131, 1964. \bibitem{HPHD} W. Haemers, Eigenvalue techniques in design and graph theory, Ph.D. thesis, 1979. Available at his webpage \url{http://lyrawww.uvt.nl/~haemers/home.html}. \bibitem{H} W. Haemers, Interlacing eigenvalues and graphs, {\it Linear algebra Appl.} {\bf 226/228}, 593-616, 1995. %\bibitem{Jun} D. Jungnickel, On Subdesigns of Symmetric Designs, {\it Math. Z.} {\bf 181}, 383-393, 1982. \bibitem{KS} M. Krivelevich and B. Sudakov, Pseudorandom Graphs, {\it Bolyai Soc. Math. Stud.} {\bf 15} 199-262, 2006. \bibitem{MW} D. Mubayi and J. Williford, On the independence number of the Erd\H{o}s-Renyi and Projective Norm graphs and a related hypergraph, {\it J. Graph Theory} {\bf 56 (2)} 113-127, 2007. \bibitem{PT} S. Payne and J. A. Thas, {\it Finite generalized quadrangles}, Research Notes in Mathematics {\bf 110}, Pitman, 1984. \bibitem{Stinson} D. Stinson, Nonincident points and blocks in designs, available on Doug Stinson's webpage \url{http://cacr.uwaterloo.ca/~dstinson}. \bibitem{Tok} N. Tokushige, The eigenvalue method for cross $t$-intersecting families,{\it Preprint} 2011. \bibitem{HVM} H. Van Maldeghem, {\it Generalized polygons}, Birkh\"auser Basel, 1998. \end{thebibliography} \end{document}