\documentclass{elsart}

\begin{document}

\begin{frontmatter}
\title{Self-dual, not self-polar}
\author[eind]{A. E. Brouwer}
\author[qm]{Peter J. Cameron\thanksref{ca}}
\author[uvt]{W. H. Haemers}
\author[qm,kent]{D. A. Preece}
\thanks[ca]{Corresponding author; email: \texttt{p.j.cameron@qmul.ac.uk}.}
\address[eind]{Department of Mathematics, Technological University Eindhoven,
P.O. Box 513, 5600MB Eindhoven, The Netherlands}
\address[qm]{School of Mathematical Sciences,
Queen Mary, University of London, London E1~4NS, U.K.}
\address[uvt]{Department of Econometrics and Operations Research,
Tilburg University, P.O.~Box 90153, 5000~LE Tilburg, The Netherlands}
\address[kent]{Institute of Mathematics, Statistics and Actuarial Science,
University of Kent, Canterbury, Kent, CT2~7NZ, U.K.}

\begin{abstract}
The smallest number of points of an incidence structure which is self-dual
but not self-polar is~$7$. For non-binary structures (where a point may
occur more than once in a block) the number is~$6$.
\end{abstract}
\begin{keyword}
incidence structure, self-dual, self-polar
\end{keyword}
\end{frontmatter}

At the IPM workshop in Tehran in August 2003, the second author asked for
a small (preferably the smallest) example of an incidence structure whose 
incidence matrix $N$ is self-dual but not self-polar. That is, $N$ is a 
zero-one matrix such that there exist permutation matrices $P_1,P_2$ with 
$P_1N=N^\top P_2$, but there does not exist a permutation matrix $P_3$ with 
$P_3N=N^\top P_3^\top$.

Such matrices are known to exist, but the proofs depend on rather subtle
properties of groups of Lie type and the matrices themselves are rather large.
In this paper, we show:

\begin{thm}
The smallest order of a self-dual but not self-polar incidence structure
is~$7$. Up to isomorphism there are exactly eight incidence structures on
$7$ points with this property.
\end{thm}

\begin{pf}
The incidence graph $G$ of such a structure $G$ be a bipartite graph admitting 
an automorpism $\sigma$ of order~$2^d$ which interchanges the two bipartite 
blocks, for some $d>1$, but no such automorphism of order~$2$.

Suppose first that $d=2$. We claim that if
$G$ has at most~$12$ vertices, then $G$ also admits an automorphism $\tau$ of
order~$2$ interchanging the bipartite blocks.
Let $\sigma$ have $4$-cycles $(a_i,b_i,c_i,d_i)$ for $i\in I$ and $2$-cycles
$(e_j,f_j)$ for $j\in J$. We may assume that the points $a_i$, $c_i$ and $e_j$
form one bipartite block and $b_i$, $d_i$, and $f_j$ the other.

Our first candidate for $\tau$ will be a permutation whose structure on 
the set $\{a_i,b_i,c_i,d_i\}$ is either $(a_i,b_i)(c_i,d_i)$ or
$(a_i,d_i)(b_i,c_i)$, and which has cycles $(e_j,f_j)$ for $j\in J$.
Since $\tau$ agrees with $\sigma$ on the union of the cycles of length~$2$,
it preserves all edges and non-edges here. Moreover, if, say, $f_j$ is
joined to $a_i$, then it is also joined to $c_i$, while $e_i$ is joined
to $b_i$ and $d_i$. So edges between $2$-cycles and $4$-cycles are
preserved by $\tau$. Also, edges within a $4$-cycle are obviously preserved
by $\tau$. This shows that, if $\sigma$ has only one $4$-cycle, then $\tau$
is an automorphism.

Consider two $4$-cycles of $\sigma$, say $(a_1,\ldots,d_1)$ and
$(a_2,\ldots,d_2)$. Then $a_1$ is joined to both, one or neither of $b_2$ 
and $d_2$, and the other edges between the cycles follow from this. If 
$a_1$ is joined to both or neither, then either choice of $\tau$ on each
cycle preserves these edges. If $a_1$ is joined to one of $b_2$ and $d_2$,
then we can (and must) take $\tau=(a_1,b_1)(c_1,d_1)(a_2,d_2)(b_2,c_2)\ldots$.
So if $\sigma$ has two $4$-cycles then an automorphism $\tau$ exists. Hence
we may assume that $\sigma$ has three $4$-cycles and there are $12$ vertices
altogether.

In this case, we can still choose $\tau$ unless a point of each cycle is 
joined to one point in each of the others; then the three requirements for
$\tau$ conflict. The graph formed by the edges between
the $4$-cycles is a $12$-gon, and the three $4$-cycles are the ``squares''
formed by the diagonals of length~$3$. Whichever set of squares are chosen
to be edges, there is always a reflection of the 12-gon interchanging the
two bipartite blocks.

Now suppose that there are $14$ vertices. The argument shows that the
induced subgraph on the $4$-cycles must be of the above form, and there
is one $2$-cycle $(e,f)$. Now, in order to destroy the reflection symmetry,
we must take a set $S_1$ of one or two squares to be edges of the graph,
and a set $S_2$ of one or two squares whose vertices are joined alternately
to $e$ and $f$ (where $S_2$ is not equal or complementary to $S_1$); moreover,
we can choose whether or not to join $e$ and $f$. This gives eight graphs
forming four complementary pairs within $K_{7,7}$; the numbers of edges
are $20$, $21$, $24$ (twice), $25$ (twice), $28$ and $29$. It is simple to
check that the eight graphs all have the required property and are pairwise
non isomorphic.

A similar but easier argument shows that no such graph on $14$ or fewer
vertices can have a duality of order~$8$ but none of order~$2$ or~$4$.
\end{pf}

If we allow multiple edges, then $12$ vertices suffice: we can take the
$12$-gon whose vertices are the integers mod~$12$ and edges $\{i,i+1\}$,
duplicate the edges $\{3i,3i+1\}$, and add the diagonals $\{3i,3i+3\}$.
Similar arguments show that no smaller number of vertices is possible.

\begin{center}
\setlength{\unitlength}{1mm}
\begin{picture}(100,40)
\multiput(15,5)(10,0){2}{\circle*{1.5}}
\multiput(5,15)(10,0){4}{\circle*{1.5}}
\multiput(5,25)(10,0){4}{\circle*{1.5}}
\multiput(15,35)(10,0){2}{\circle*{1.5}}
\multiput(18.33,18.33)(3.33,3.33){2}{\circle*{1.5}}
\multiput(5,15)(0,10){2}{\line(1,0){30}}
\multiput(15,5)(0,30){2}{\line(1,0){10}}
\multiput(15,5)(10,0){2}{\line(0,1){30}}
\multiput(5,15)(30,0){2}{\line(0,1){10}}
\put(5,25){\line(5,-1){16.67}}
\put(35,15){\line(-2,1){13.33}}
\put(15,5){\line(1,4){3.33}}
\put(25,35){\line(-2,-5){6,67}}
\multiput(75,5)(10,0){2}{\circle*{1.5}}
\multiput(65,15)(10,0){4}{\circle*{1.5}}
\multiput(65,25)(10,0){4}{\circle*{1.5}}
\multiput(75,35)(10,0){2}{\circle*{1.5}}
\multiput(75,15)(-10,10){2}{\line(1,0){20}}
\multiput(75,5)(0,30){2}{\line(1,0){10}}
\multiput(75,5)(10,10){2}{\line(0,1){20}}
\multiput(65,15)(30,0){2}{\line(0,1){10}}
\multiput(65,14.5)(0,1){2}{\line(1,0){10}}
\multiput(74.5,25)(1,0){2}{\line(0,1){10}}
\multiput(85,24.5)(0,1){2}{\line(1,0){10}}
\multiput(84.5,5)(1,0){2}{\line(0,1){10}}
\end{picture}
\end{center}

Graphs with fewest vertices, without and with multiple edges, are shown 
in the above figure; the $12$-gon is the outer boundary. 

More generally, if we take a regular $2^d$-gon, erect a square on each side,
and join one new vertex of each square alternately to one of two further
vertices preserving the cyclic symmetry, we obtain a bipartite graph having
$2(3\cdot2^{d-1}+1)$ vertices, whose automorphism group is cyclic of
order~$2^d$, such that an automorphism interchanges the two bipartite blocks
if and only if it has order~$2^d$. That is, there is an incidence structure
with $3\cdot2^{d-1}+1$ points having a duality of order~$2^d$ but none of
smaller order.

\end{document}
