% \documentstyle[a4,12pt]{article}
\documentclass[a4paper]{article}
\usepackage{a4}
\usepackage{latexsym}
\title{The universal embedding dimension of the near polygon
on the 1-factors of a complete graph}
\author{A. Blokhuis \& A.E. Brouwer}
\date{June 1, 1998}
\begin{document}
\maketitle
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Rr}{{\bf R}}
% \newcommand{\exp}{{\rm exp}}
% \newcommand{\ln}{{\rm ln}}
\newcommand{\infinity}{{\infty}}

\centerline{In memory of E.F. Assmus Jr.}

\abstract{We show that the universal embedding dimensions
(over $\Ff_2$) of the near polygons associated with
${\rm Sym}(2n)$ (viewed as subgroup of ${\rm Sp}(2n-2,2)$)
are the Catalan numbers.}

\section{Introduction}
A {\em near polygon} is a connected partial linear space such that
for any point $x$ and line $L$ there is a unique point on $L$
closest to $x$ in the collinearity graph.
Near polygons were introduced in Shult \& Yanushka \cite{SY},
and Brouwer \& Wilbrink \cite{BW1} give a structure theory.

Consider the near polygon $H_{n-1}$ that has as points the 1-factors
of the complete graph $K_{2n}$, and as lines (of size 3)
the sets of 1-factors on a partial 1-factor of size $n-2$.
(This near polygon was constructed in Brouwer \& Wilbrink \cite{BW2};
see also \cite{BCHW}.)
This near polygon has $v = (2n-1)(2n-3)...1$ points,
and $t+1 = {n \choose 2}$ lines on each point.
For $n > 0$ it is a sub near polygon of the dual symplectic near polygon
$DSp(2n-2,2)$ (and equals $DSp(2n-2,2)$ for $1 \le n \le 3$).

Given a point-line geometry with lines of size 3,
its {\em universal embedding space} (over $\Ff_2$) is
the $\Ff_2$-vector space $U = V / W$, where $V$ is the vector space
that has the point set $X$ as basis, and $W$ is the subspace generated
by the elements $x+y+z$ for each line $\{x,y,z\}$.
% The {\em universal embedding} is the map
% $x \mapsto \langle x \rangle +W$ from $X \setminus W$
% into the projective space $PU$.
The {\em universal embedding dimension} is ${\rm dim\,} U$.

We show that the universal embedding dimension of the geometry
$H_{n-1}$ equals the multiplicity of the eigenvalue
$-t-1$ of the adjacency matrix $A$ of its collinearity graph,
and is the Catalan number $C_n := {1 \over n+1} {2n \choose n}$.
(Thus, the first few values are 1, 1, 2, 5, 14, 42, 132, ...)

For $DSp(2d,2)$ it is conjectured that the universal embedding
dimension is $(2^d + 1)(2^{d-1} + 1)/3$ (so that the first few
values are 1, 2, 5, 15, 51, ...).
This research was motivated by the hope that knowledge of the
universal embedding of a large subgeometry of $DSp(2d,2)$
will help in settling this conjecture.

\section{Upper bound}
Let $u$ be the universal embedding dimension of $H_{n-1}$.
We show $u \le C_n$ by indicating a spanning subset of $H_{n-1}$
of size $C_n$.
And this is easy\footnote{(when one is at the party on the
occasion of the 50th anniversary of Seidel's doctorate)}.
Indeed, $C_n$ is the number of 1-factors of $K_{2n}$
without crossing edges, when the $2n$ vertices are
drawn as the vertices of a convex $2n$-gon $P$ in the plane.
Each line expresses a 1-factor with at least one crossing
as a sum of two 1-factors with strictly fewer crossings.
So, the 1-factors without crossings form a spanning subset.

\subsection*{Geometric description of the spanning subset}
For two 1-factors $x,y$ of $K_{2n}$, let $c(x,y)$ be
the number of connected components of $x \cup y$.

A more geometric description of this spanning subset
may be given as follows. For two vertices $x,y$ of a
near polygon, let $C(x,y)$ be the union of all geodesics
between $x$ and $y$. Our spanning subset is $C(x,y)$
for $x,y$ at maximal distance.

Indeed, let the $2n$ vertices of $P$ be points of a circle $C$,
chosen such that no three diagonals pass through one point.
Take for $x$ and $y$ alternating arcs of $C$. Any further
1-factor $z$ (with its $n$ pairs drawn as straight lines),
partitions the area inside $C$ into $n+1+{\rm cr}(z)$ components,
where ${\rm cr}(z)$ is the number of crossings of $z$.
Any such component has a boundary contained in $x \cup z$
or $y \cup z$, and we see that $c(x \cup z) + c(y \cup z) =
n+1-{\rm cr}(z)$, where $c(x \cup y)$ denotes the number of
connected components of $x \cup y$, and hence
$d(x,z) + d(y,z) = n-1+{\rm cr}(z)$
so that $z \in C(x,y)$ if and only if ${\rm cr}(z) = 0$.

\section{Embedding in an exterior power}
There is also a short computation-free proof of the
independence of the set of 1-factors without crossings.
It shows that a universal embedding of $H_{n-1}$ can be
found inside the exterior product $T := \bigwedge^n S$, where
$S$ is the $2n$-dimensional binary vector space that has
the vertex set $K$ of $K_{2n}$ as basis.

Indeed, map a 1-factor $\{\{x_1,x_2\},...,\{x_{2n-1},x_{2n}\}\}$
of $K_{2n}$ to the element $(x_1 + x_2) \wedge ... \wedge (x_{2n-1} + x_{2n})$
of $T$. Then the sum of the images of three points on a line of
$H_{n-1}$ vanishes, so this defines an embedding of the point-line
geometry $H_{n-1}$.

Now let $K$ be the set of vertices of the convex $2n$-gon $P$,
ordered naturally. Assign to each 1-factor without crossings
the lexicographically least term of its image in $T$ (its `head').
Since different 1-factors have different heads (it is clear how
to reconstruct the 1-factor from its head), the images in $T$ of the
1-factors without crossings are linearly independent.

This proves $u = C_n$.
The above can be viewed as the determination of the 2-rank
of the point-line incidence matrix of $H_{n-1}$.
Below we show that this 2-rank equals the $\Rr$-rank.
First some preparation.

\section{Two identities for 1-factors}
For two 1-factors $x,y$ of $K_{2n}$, let $c(x,y)$ be
the number of connected components of $x \cup y$.

\begin{Proposition}
\label{count}
Fix a 1-factor $x$ of $K_{2n}$, and let $y$ run over the 1-factors
of $K_{2n}$ in the summations below. We have
$$
\sum_y t^{c(x,y)} = t(t+2)...(t+2n-2) .
$$
In particular,
\begin{equation}
\sum_y (-2)^{c(x,y)} = 0 {\mbox{~~if~}} n \ge 2  \label{eq1}
\end{equation}
and
\begin{equation}
\sum_y 4^{c(x,y)} = 2^n (n+1)! {\mbox{~~for~all~}} n . \label{eq2}
\end{equation}
\end{Proposition}
\Proof
We have
$$(1-X)^a = \exp(a \ln(1-X)) =
\exp(-a \sum_{i=1}^\infinity {X^i \over i}) =
\prod_{i=1}^\infinity \exp(-a {X^i \over i}) =
$$
\begin{equation}
= \prod_{i=1}^\infinity \sum_{m=0}^\infinity {1 \over m!}
\left( -a {X^i \over i} \right)^m =
\sum_{n=0}^\infinity \left( \sum_\lambda \prod_{i=1}^\infinity
{1 \over n_i!} \left( -{a \over i} \right)^{n_i} \right) X^n . \label{eq}
\end{equation}
where in the last expression $\lambda$ runs over partition shapes
$1^{n_1} 2^{n_2} ...$ with $n = \sum i n_i$.
The number of partitions $\pi$ of shape $\lambda$ equals
$$
n_{\lambda} = {n! \over \prod_{i=1}^\infinity \left( n_i! (i!)^{n_i} \right)} .
$$

Given two 1-factors $x,y$ of $K_{2n}$, their union $x \cup y$
is a union of even cycles. Thus, if $x$ is fixed then each $y$
induces a partition $\pi = \pi(x,y)$ of the $n$ edges of $x$.
Conversely, given $\pi$ (of shape $\lambda = 1^{n_1} 2^{n_2}...$)
there are
$$
\prod_{i=1}^\infinity (2^{i-1} (i-1)!)^{n_i}
$$
1-factors $y$ with $\pi(x,y) = \pi$.
Thus, given a shape $\lambda$, there are
$$
k_{\lambda} = n! 2^n  \prod_{i=1}^\infinity {1 \over n_i! (2i)^{n_i} }
$$
1-factors $y$ with $\pi(x,y)$ of shape $\lambda$.
Also, $c(x,y) = \sum_i n_i$.
So,
$$
\sum_y (-2a)^{c(x,y)} = n! 2^n \sum_{\lambda} \prod_{i=1}^\infinity
{1 \over n_i!} \left( - {a \over i} \right)^{n_i}
= n! 2^n (-1)^n {a \choose n}
$$
where the last equality follows by taking the coefficient of $X^n$
on both sides of (\ref{eq}). Now let $t := -2a$.
\qed

\section{The real rank}
Let $N$ be the point-line incidence matrix of $H_{n-1}$,
and let $A$ be the adjacency matrix of the collinearity graph.
Then $N N^{\top} = A + (t+1)I$.

For the universal embedding dimension $u$ we have
$u = v - {\rm rk}_2 N \ge v - {\rm rk} N =
v - {\rm rk} N N^{\top}$ (where the unadorned ${\rm rk}$ stands
for the $\Rr$-rank), and this equals the multiplicity
$m$ of $-t-1$ as an eigenvalue of $A$.
So if we show that $m \ge C_n$, then $C_n \ge u \ge m \ge C_n$,
and we will have shown (i) $u = m = C_n$ and
(ii) ${\rm rk}_2 N = {\rm rk\,} N$.

To this end, consider the symmetric association scheme on $X$
with as relations the shapes $\lambda$ of partitions of $n$
(where $x,y$ are in relation $\lambda$ if $\pi(x,y)$ has shape
$\lambda$).
Let $A_\lambda$ be the adjacency matrix for the relation $\lambda$,
and let $A_i$ be the adjacency matrix for distance $i$, so that
$A_h = \sum A_{\lambda}$ where the sum is over the
$\lambda = 1^{n_1} 2^{n_2} ...$ with $\sum n_i = n-h$.
We claim that $E = \sum_i (-{1 \over 2})^i A_i$ is a multiple of
an idempotent that is the projection onto an eigenspace
for the eigenvalue $-t-1$ of $A$. Indeed, in the lemma below
we show that $A_\lambda E = c_\lambda E$ for certain constants
$c_\lambda$, so that $E^2 = cE$ for a certain constant $c$,
and ${1 \over c} E$ is an idempotent,
and ${\rm rk} E = {\rm tr} ({1 \over c} E) = v/c$
is a lower bound for $m$.
But $c = (E^2)_{xx} = \sum_y 4^{-(n-c(x,y))} = 2^{-n} (n+1)!$
by Proposition \ref{count} (\ref{eq2}) so that $v/c = C_n$, as desired.

It remains to show:

\begin{Lemma}
We have $A_\lambda E = c_\lambda E$, where
$$
c_\lambda = (-1)^n n! \prod_{i=1}^\infinity
{1 \over n_i!} \left( - {1 \over i} \right)^{n_i} .
$$
\end{Lemma}
\Proof
Assume $n \ge 2$. By Proposition \ref{count} (\ref{eq1}) we
find $\sum c_{\lambda} = 0$ and $\sum A_{\lambda} E = J E = 0$
so that it suffices to show $A_\lambda E = c_\lambda E$ for the
$\lambda$ with more than one part. Pick for $\psi$ column $p$ of $E$.
We want to show that the sum of $\psi_y$ over all $y$ that have relation
$\lambda$ to $x$ equals $c_\lambda \psi_x$. To this end,
group the contributions of the $y$ in the same geodetically closed
subspace $S(x,y)$ together. There are $n_\lambda$ such subspaces, and we claim
each contributes $c_\lambda / n_\lambda = \prod_i ((-1)^{i-1} (i-1)!)^{n_i}$
to the eigenvalue. Since we are in the case where $\lambda$ has
more than one part, the subspace $S(x,y)$ is a direct product
of near polygons $H_{i-1}$, and by induction we know that
for $\lambda = i^1$ we have $c_\lambda = (-1)^{i-1} (i-1)!$,
and the contribution to the eigenvalue of a direct product
is the product of the contributions of the factors.
This settles everything.
\qed

\begin{thebibliography}{99}

\bibitem{BCHW} A.E. Brouwer, A.M. Cohen, J.I. Hall \& H.A. Wilbrink,
{\it Near polygons and Fischer spaces},
Geometriae Dedicata {\bf 49} (1994) 349-368.

\bibitem{BW1} A.E. Brouwer \& H.A. Wilbrink,
{\it The structure of near polygons with quads},
Geometriae Dedicata {\bf 14} (1983) 145-176.

\bibitem{BW2} A.E. Brouwer \& H.A. Wilbrink,
{\it Two infinite sequences of near polygons},
Math. Centr. Report ZW194, June 1983, Amsterdam.

\bibitem{SY} E.E. Shult \& A. Yanushka,
{\it Near $n$-gons and line systems},
Geometriae Dedicata {\bf 9} (1980) 1-72.

\end{thebibliography}
\end{document}
