% a plain TeX file for a 20 page document
%**start of header
\magnification=\magstep1
\baselineskip=15pt
\normalbaselineskip=15pt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% paperB.tex
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This give access to the AMS special characters.
%\input amssym.def
%\input amssym
\newif\iftitle
\newtoks\runninghead \runninghead={\hfil}
\newtoks\authors \authors={\hfil}
\newtoks\titlehead
\newtoks\rightheader \newtoks\leftheader \newtoks\pagefoot
\font\hdr=cmssdc10 % running heads
\rightheader={\hdr\hfil\the\authors\hfil}
\leftheader={\hdr\hfil\the\runninghead\hfil}
\titlehead={\hfil}% this should be set to the date and status (e.g., DRAFT)
\pagefoot={\hss\tenrm\folio\hss}
\headline={\ifnum\the\pageno<1 \hfil\else
\iftitle\the\titlehead{\global\titlefalse}\else
\ifodd\pageno\the\rightheader\else\the\leftheader\fi\fi\fi}
\footline={\ifnum\the\pageno<1 \hfil\else\the\pagefoot\fi}
% one of Brendan's little fixes
\fontdimen16\tensy=1\fontdimen17\tensy
\newcount\sectno
\def\newsectno{\global\advance\sectno by1 }
%
% This starts a section
%
\outer\def\section#1#2\par{%
\dimen0=\pagegoal \advance\dimen0 by-120pt
\removelastskip
\vskip 20pt plus 40pt \penalty -400 \vskip 0pt plus -32pt
\newsectno\resno=0\identno=0
\message{#2}
\writexrf{SECT}{#1}{Section\string~\the\sectno}
\leftline{\bf\the\sectno.\enspace#2}
\nobreak\bigskip\noindent}
% This starts an un-numbered section.
\outer\def\nonumsection#1\par{
\resno=0\identno=0
\removelastskip
\vskip 20pt plus 40pt \penalty -400 \vskip 0pt plus -32pt
\message{#1}
\leftline{\bf#1}
\nobreak\bigskip\noindent}
\newcount\resno
\def\newresno{\global\advance\resno by1 }
\newskip\resskipamount
\resskipamount=15pt plus5pt minus3pt
\def\resskip{\vskip\resskipamount}
\def\resbreak{\par\ifdim\lastskip<\resskipamount
\removelastskip \penalty-300 \resskip\fi}
% this fine tunes the spacing in \result
\def\XXmagic{^^C}
\def\math#1{$#1$}
\def\XX#1 $#2$#3\endXX{\def\XXtest{#2}\ifx\XXtest\XXmagic
\def\XXnext{#1}\else\def\XXnext{\XX#1\/ \math{#2}#3\endXX}\fi
\XXnext}
%
% this does cross-referencing
% strict usage \result{label}Theorem. Lots of stuff...
% this can be broken up by putting a percent sign after {label},
% with all remaining text on the next line
%
\def\parse#1 #2\@stp{#1}
\outer\def\result#1#2. #3\par{%
\newresno
\resbreak\noindent
\writexrf{RESU}{#1}{\parse #2 \@stp\string~\the\sectno.\the\resno}
{\bf\the\sectno.\the\resno\enspace#2.\enspace}
{\sl \XX#3 $^^C$\endXX}\par
\ifdim\lastskip<\bigskipamount \removelastskip\penalty55\bigskip\fi}
\def\proof{\noindent{{\sl Proof. }}}
% This is for examples, formatted like the statement of
% a proposition
\def\example #1.{
\newresno
\ifdim\lastskip<\bigskipamount \removelastskip\penalty55\bigbreak\fi
\noindent{\bf\the\sectno.\the\resno\enspace#1.\enspace}}
% This is for claims in proofs
\def\claim#1 #2\par {\smallbreak{\sl #1 #2}\hfil\break\noindent}
% Use \idno in place of \eqno(n); this numbers equations
% automatically.
\newcount\identno
\def\newidentno{\global\advance\identno by 1 }
\newtoks\lasteq
\def\id#1{
\newidentno
\global\lasteq={(\the\sectno.\the\identno)}
\writexrf{EQU}{#1}{(\the\sectno.\the\identno)}
(\the\sectno.\the\identno)}
\def\idno#1{\eqno\id{#1}}
% \preveq gives, e.g., Equation (2.1), where 2.1 is the last
% equation defined
\def\preveq/{\the\lasteq}
\def\sqr#1#2{{\vbox{\hrule height.#2pt
\hbox{\vrule width.#2pt height#1pt \kern#1pt
\vrule width.#2pt}\hrule height.#2pt}}}
\def\eqed{\sqr53}
% Put \qed at the end of each proof, flush against the full stop.
% you cannot use \qed inside \eqalign,
% use \eqalignno instead, and end last equation with &\eqed
\def\qed{%
\ifmmode\eqno\eqed
\else\nobreak\ \hfill\eqed\medbreak\fi}
%
% This is \section for the references;
% perhaps the hyphen penalty should be changed too
%
\outer\def\beginreferences{%
\begingroup\refno=0\tolerance=500
\removelastskip
\vskip 20pt plus 40pt \penalty -400 \vskip 0pt plus -32pt
\message{ References}
\leftline{\bf References}
\nobreak\bigskip\noindent}
\def\endreferences{\endgroup}
% This numbers the references and records the labels
\newcount\refno
\def\newrefno{\global\advance\refno by1 }
\def\ref#1{%
\newrefno
\writexrf{REFE}{#1}{\the\refno}
\medbreak\par\hang\textindent{[\the\refno]}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cross-referencing
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\ifrewritexrffile
\newif\ifxrffileopened
\newif\ifxrfnotdefined \xrfnotdefinedfalse
\newif\ifxrfread \xrfreadfalse
\newif\iffirstbadlabel \firstbadlabeltrue
\newif\iffileexists
\def\testfileexistence#1{\begingroup
\immediate\openin0 = \jobname.#1\space
\ifeof 0\global\fileexistsfalse
\else \global\fileexiststrue\fi
\immediate\closein0
\endgroup}%
\newwrite\xrffile
\def\openxrffile{\ifxrffileopened\else
\xrffileopenedtrue
\immediate\openout\xrffile = \jobname.xrf
\fi}%
\def\readxrffile{
\testfileexistence{xrf}%
\iffileexists
\input \jobname.xrf
\xrfreadtrue
\else
\xrfreadfalse
\fi}%
\outer\def\resulta #1. #2\par{\resbreak\noindent
\newresno
{\bf\the\sectno.\the\resno\enspace#1.\enspace}
{\sl \XX#2 $^^C$\endXX}\par
\ifdim\lastskip<\bigskipamount \removelastskip\penalty55\bigskip\fi}
\def\writexrf#1#2#3{% tag, label, string
\ifrewritexrffile\openxrffile
\immediate\write\xrffile{%
\string\expandafter
\string\edef\noexpand\csname #1.#2\endcsname%
{{#3}}
}%
\ignorespaces\fi}%
\def\xrflab#1#2{\edef\tmp{\csname #1.#2\endcsname}%
\expandafter\ifx\tmp\relax
\iffirstbadlabel
\firstbadlabelfalse
\message{ tag #1 label #2 not defined at line \the\inputlineno}
\fi%
{\bf *#1*}
\else
\tmp
\fi}%
\def\help#1#2{#1 #2}
\def\p#1{\xrflab{RESU}{#1}}
\def\r#1{\xrflab{REFE}{#1}}
\def\sect#1{\xrflab{SECT}{#1}}
\def\eq#1{\xrflab{EQU}{#1}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\Ga{\Gamma}
\def\la{\lambda}
\def\th{\theta}
\def\om{\omega}
\def\Om{\Omega}
\def\aut#1{{\rm Aut}(#1)}
\def\comp#1{{\mkern2mu\overline{\mkern-2mu#1}}}
\def\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus
\def\inv{^{-1}}
\def\match{\mathop{\hbox{$\mu$}}\nolimits}
\def\one{{\bf1}}
\def\re{{\bf R}}
\def\tr{\mathop{\hbox{\rm tr}}\nolimits}
\def\sym#1{{\rm Sym}(#1)}
\authors={C. D. Godsil}
\runninghead={Problems in Algebraic Combinatorics}
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1%
{\smcp the electronic journal of combinatorics 2 (1995),
\#F1\hfill\folio} \fi}
\pagefoot={\hss}
\rewritexrffilefalse
%**end of header
\rewritexrffiletrue
\readxrffile
\null\vskip1.0cm
\centerline{\bf PROBLEMS IN ALGEBRAIC COMBINATORICS}
\vskip1.0cm
\centerline{
C. D. Godsil
\footnote{$^1$}{Support from grant OGP0093041 of the National Sciences and
Engineering Council of Canada is gratefully acknowledged.}}
\vskip0.5cm
\centerline{Combinatorics and Optimization}
\centerline{University of Waterloo}
\centerline{Waterloo, Ontario}
\centerline{Canada N2L 3G1}
\centerline{chris@bilby.uwaterloo.ca}
\bigskip
\centerline{Submitted: July 10, 1994;\quad Accepted: January 20, 1995.}
\vskip1.0cm
\bigskip\noindent{\narrower
{\bf Abstract:} This is a list of open problems, mainly in graph theory and
all with an algebraic flavour. Except for 6.1, 7.1 and 12.2 they are
either folklore, or are stolen from other people.
\medskip\noindent
AMS Classification Number: 05E99\par}
\section{moore}%1
Moore Graphs
We define a {\sl Moore Graph}\/ to be a graph with diameter $d$ and
girth $2d+1$. Somewhat surprisingly, any such graph must necessarily
be regular (see [\r{sing}]) and, given this, it is not hard to show
that any Moore graph is distance regular. The complete graphs and odd
cycles are trivial examples of Moore graphs. The Petersen and
Hoffman-Singleton graphs are non-trivial examples. These examples
were found by Hoffman and Singleton [\r{hfsing}], where they showed
that if $X$ is a $k$-regular Moore graph with diameter two then
$k\in\{2,3,7,57\}$. This immediately raises the following question:
\result{moore}%1.1
Problem. Is there a regular graph with valency 57, diameter two and
girth five?
We summarise what is known. Bannai and Ito [\r{bi}] and,
independently, Damerell [\r{dam}] showed that a Moore graph has
diameter at most two. (For an exposition of this, see Chapter~23 in
Biggs [\r{agt}].) Aschbacher [\r{asch}] proved that a Moore graph
with valency 57 could not be distance transitive and G. Higman (see
[\r{pjc}]) proved that it could not even be vertex transitive.
By either a square-counting or an interlacing argument, one can show
that the maximum number of vertices in an independent set in the
Hoffman-Singleton graph is 15. If $S$ is an independent set of size
15 in this graph then each vertex not in $S$ is adjacent to exactly
three vertices in $S$, and so the graph induced by the vertices not in
$S$ is 4-regular. This leads to a construction of the
Hoffman-Singleton graph. Let $G$ be the graph formed by the 35
triples from a set of seven points, with two triples adjacent if they
are disjoint. (This is the odd graph $O(4)$, with diameter three.)
Call a set of seven triples such that any pair meet in exactly one
point a {\sl heptad}. It is not too hard to show that there are
exactly 30 heptads, all equivalent under the action of $\sym7$ and
falling into two orbits of length 15 under ${\rm Alt}(7)$. Choose one
of these two orbits and then extend $G$ to a graph $H$ by adding 15
new vertices, each adjacent to all seven vertices in a heptad in the
selected orbit. Then $H$ is the Hoffman-Singleton graph.
Note that we may view the vertices in $S$ as points and the vertices
not in $S$ as lines, with a point and line incident if the
corresponding vertices are adjacent. This gives us a $2$-$(15,7,1)$
design and in the construction above this design is the design of
points and lines in $PG(3,2)$. Now consider a possible Moore graph
with valency 57. In this case an independent set has at most 400
vertices. If $S$ is an independent set of cardinality then the
incidence structure formed by the vertices in $S$ and the vertices not
in $S$ is a $2$-$(400,8,1)$ design. The points and lines of $PG(3,7)$
form a design with these parameters.
The Hoffman-Singleton graph contains many copies of the Petersen
graph. It is easy to show that there are subgraphs in it isomorphic
to Petersen's graph with one edge deleted, and it can be shown that
any such subgraph must actually induce a copy of the Petersen graph.
(See [\r{camvl}:~Theorem~6.6], where this is used to show that the
Hoffman-Singleton graph is unique, i.e., it is the only graph of
diameter two, girth five and valency seven.) As far as I know, it has
not been proved that Moore graph with valency 57 must contain even one
copy of the Petersen graph (to say nothing of the Hoffman-Singleton
graph).
\section{trifree}%2
Triangle-free Strongly Regular Graphs
A graph is {\sl strongly regular}\/ if it is not complete or empty and
the number of common neighbours of two vertices is determined by
whether they are equal, adjacent or neither equal nor adjacent. An
$(n,k;a,c)$ strongly regular graph is a $k$-regular graph on $n$
vertices such that any pair of adjacent vertices has exactly $a$
common neighbours while a pair of distinct non-adjacent vertices has
exactly $c$ common neighbours. We are concerned with strongly regular
graphs with no triangles, i.e., with $a=0$. Any Moore graph with
diameter two is an example.
Three have already appeared---the cycle on five vertices, the Petersen
graph and the Hoffman-Singleton graph---but only four more are known.
We describe them. The first is the Clebsch graph, which we build from
Petersen's graph.
We may view the vertices of the Petersen graph as the unordered pairs from
the set
$$
F:=\{0,1,2,3,4\},
$$
where two unordered pairs are adjacent if and only if they are
disjoint. It is not hard to show that the maximum size of an
independent set in Petersen's graph is four, and that any such set
consists of the four pairs containing a given point from our $F$. Let
$S_i$ be the independent set formed of the four pairs containing $i$.
Now construct a graph $C$ as follows. If $P$ denotes the vertex set
of the Petersen graph, vertex set of $C$ is
$$
\infty,\ F,\ P.
$$
The vertex $\infty$ is adjacent to each of the points of $F$ and the
vertex $i$ in $F$ is adjacent to all vertices in $S_i$. Thus $C$ is a
5-regular triangle-free graph on 16 vertices, and it is not difficult
to show that it is strongly regular.
The Higman-Sims graph is also very easy to construct. Let $W_{22}$ be
the Witt design on 23 points. This is a $3$-$(22,6,1)$ design with 77
blocks. Let $V$ be the point set of $W_{22}$ and let $\cal B$ be its
block set. The vertex set of the Higman-Sims graph is the set
$$
\infty\cup V\cup{\cal B}.
$$
The adjacencies are as follows. The vertex $\infty$ is adjacent to
all vertices in $V$ and each block is adjacent to the six points in
$V$ which lie in it, and to all the blocks in $\cal B$ which are
disjoint from it. With some effort it can be shown that this is a
$(100,22;0,6)$ strongly regular graph.
It is possible to partition the vertices of the Higman-Sims graph into
two sets of size 50, with the subgraph induced by each set isomorphic
the Hoffman-Singleton graph. (See, e.g., Exercise~2 in Chapter~8 of
[\r{camvl}] or Chapter~VI of [\r{shs}].)
The graph induced by the vertices at distance two from a chosen vertex
in the Higman-Sims graph form a subgraph isomorphic to the complement
of the block graph of $W_{22}$. (The block graph of a design has the
blocks of the design for vertices, with two blocks adjacent if and
only if the have a point in common.) Thus the complement of the block
graph of $W_{22}$ is triangle-free. It is also a $(77,16;0,4)$
strongly regular graph. (This follows from standard results on
quasi-symmetric designs.) The 21 blocks in $W_{22}$ containing a given
point form an incidence structure isomorphic to the projective plane
of order four. The remaining 56 blocks form another quasi-symmetric
design and the complement of its block graph is a $(56,10;0,2)$
strongly regular graph, known as the {\sl Gewirtz graph}.
Now we have seen seven triangle-free strongly regular graphs, which
leads naturally to the question for this section.
\result{8trifree}% 2.1
Problem. Is there an eighth triangle-free strongly regular graph?
Biggs [\r{fga}:~Section~4.6]] shows that if a $(n,k;0,c)$ strongly
regular graph exists and $c\notin\{2,4,6\}$ then $k$ is bounded by a
function of $c$. This bounds $n$ too, since
$$
n=1+k+{k(k-1)\over c}.
$$
The smallest open case appears to be the existence of a strongly regular
graph with parameters $(162,21;0,3)$.
Triangle-free strongly regular graphs are of interest in knot theory.
For more information about the connection see, e.g., Jaeger
[\r{jaeger}]. Unfortunately for the knot theorists the strongly
regular graphs they need must not only be triangle-free, they should
also be ``formally self-dual''. For what this means see [\r{jaeger}],
(or [\r{cgbk}:~p.~249]); this extra condition does imply that the set
of vertices at distance two from a fixed vertex must also be a
strongly regular graph. The Higman-Sims graph is formally self-dual.
\section{equil}% 3
Equiangular Lines
A set of lines through the origin in $\re^n$ is {\sl equiangular}\/ if
the angle between any two lines is the same. Our general problem is
to determine the maximum size of a set of equiangular lines in
$\re^m$. The diagonals of the icosahedron provide a set of six
equiangular lines in $\re^3$.
Let $\cal L$ be a set of equiangular lines in $\re^m$ and let
$x_1,\ldots,x_m$ be a set of unit vectors such that $x_i$ spans the
$i$-th line of $\cal L$. Let $U$ be the matrix with $i$-column equal
to $x_i$ and let $\ga$ denote $|x_i^Tx_j|\inv$, for $i\ne j$. Then
$$
U^TU=I+\ga\inv S
$$
where $S$ is a symmetric matrix with all diagonal entries equal to
zero, all off-diagonal entries equal to 1 or $-1$, rank $m$ and least
eigenvalue $-\ga$. Since $S$ is an integer matrix this implies that
$\ga$ is an algebraic integer. Further, if $\ga$ is not rational then
its multiplicity $n-m$ can be at most $n/2$. Thus $\ga$ must be
rational if $n>2m$. Since the only rational algebraic integers are
the plain old-fashioned integers, we deduce that if $n>2m$ then $\ga$
is an integer. In fact $\ga$ must be an odd integer, as we now show.
To see this let $A$ be ${1\over2}(S+J-I)$. Then $A$ is a symmetric
$01$-matrix and $S=2A+I-J$. If $n-m>2$ then $\ga$ is an eigenvalue of
$S+J$ (with multiplicity at least $n-m-1$. Hence $(\ga+1)/2$ is a
rational eigenvalue of $A$. Since $A$ is an integer matrix and $\ga$
is rational, this implies that $(\ga+1)/2$ is an integer, and $\ga$
must be an odd integer.
\medbreak
Let $X_i$ be the matrix $xx^T$, which represents orthogonal projection
on the line spanned by $x_i$. (Note that replacing $x_i$ by $-x_i$
does not change $X_i$.) Finally suppose that the square of the cosine
of the angle between any two distinct lines in $\cal L$ is $\la$. The
matrices $X_i$ lie in the vector space of all symmetric $m\times m$
matrices, which has dimension ${m+1\choose2}$. The mapping $(A,B)\to
\tr AB$ is an inner product on this space and the Gram matrix of
$X_1,\ldots,X_n$ with respect to this inner product is
$$
(1-\la)I+\la J.
$$
Since $\la<1$ this is the sum of a positive definite and a positive
semidefinite matrix. Hence it is positive definite and therefore
invertible. Consequently the matrices $X_1,\ldots,X_n$ are linearly
independent and therefore $n\le{m+1\choose2}$. Before discussing how
good this bound is, we examine what happens in the case of equality.
If $n={m+1\choose2}$ then $X_1,\ldots,X_n$ is a basis for the space of
symmetric $m\times m$ matrices. Hence there are constants $c_i$ such
that
$$
I=\sum_{i=1}^n c_i X_i.\idno{itox}
$$
Now
$$
\tr (X_i-\la I)X_j=\cases{1-\la,& if $i=j$;\cr 0,& otherwise\cr}
$$
and therefore \preveq/ yields that
$$
\tr(X_i-\la I)=c_i(1-\la).
$$
Thus $c_i=(1-m\la)/(1-\la)$ and taking the trace of both sides of
\preveq/ yields that
$$
n={m(1-\la)\over1-m\la}.\idno{nmlamb}
$$
Substituting $n={m+1\choose2}$ here and solving for $\la$ yields
$\la=(m+2)\inv$, with the consequence that $m+2$ must be the square of
an odd integer when $m\ge6$.
Examples of sets of $m+1\choose2$ equiangular lines in $\re^m$ are
known to exist, and be unique, when $m=2,3,7$ and $m=23$. (When $m=2$
we may take the diagonals of a regular hexagon and, when $m=3$, the
diagonals of a regular isohedron. For the remaining two cases, see
pages 129--130 and pages 166--167 in [\r{jjs}].)
\result{tight}% 3.1
Problem. Is there a set of $m+1\choose2$ equiangular lines in $\re^m$
when $m>23$?
Infinitely many examples of sets of equiangular lines with cardinality
of order $m^{3/2}$ are known [\r{jjs}:~Theorem~10.5]; it may be that
the $m+1\choose2$ bound is not even asymptotically correct.
\section{2grfs}% 4
Two-graphs
There is another bound on sets of equiangular lines. Consider the
matrix $S$ above. Its least eigenvalue is $-\ga$, and this eigenvalue
has multiplicity $n-m$. Let $\th_1,\ldots,\th_m$ be its remaining
eigenvalues. Since $\tr{S}=0$,
$$
(n-m)\ga=\sum_i \th_i
$$
and, since $\tr{S^2}=n(n-1)$,
$$
n(n-1)-(n-m)\ga^2=\sum_i \th_i.
$$
These two equations imply that
$$
{n(n-1)-(n-m)\ga^2\over m}\ge\left({(n-m)\ga\over m}\right)^2
$$
from which it follows that $m(n-1)-(n-m)\ga^2\ge0$. If equality holds
then the eigenvalues $\th_1,\ldots,\th_m$ must all be equal. If
$m<\ga^2$ then this implies that
$$
n\le{m(\ga^2-1)\over\ga^2-m}.
$$
We also obtain the following.
\result{elbnd}% 4.1
Lemma. Let $\cal L$ be a set of $n$ equiangular lines in $\re^m$, let
$x_1,\ldots,x_n$ be unit vectors spanning these lines with Gram matrix
$I+\ga\inv S$, where $\ga>0$. Then
$$
\ga^2\le{m(n-1)\over n-m}
$$
and, if equality holds then $S$ has exactly two distinct
eigenvalues.\qed
A set of $n$ equiangular lines such that $S$ has only two eigenvalues
is the same thing as a {\sl regular two-graph} on $n$ vertices. Note
that an equiangular set of $m+1\choose2$ lines in $\re^m$ will give
equality in this lemma. (But this only gives two examples.) The
matrix $S$ in the lemma is symmetric with zero diagonal and entries
$\pm1$ off the diagonal. If $D$ is diagonal matrix of the same order
with diagonal entries $\pm1$ then $DSD$ and $S$ are similar and $DSD$
still is symmetric with zero diagonal and entries $\pm1$ off the
diagonal. We may choose $D$ so that all off-diagonal entries of the
first row and column of $DSD$ are positive.
If $S$ has only two eigenvalues then
$$
S^2+\al S+\be I=0\idno{squadr}
$$
for some $\al$ and $\be$. Since $\tr S=0$ and $\tr S^2=n(n-1)$,
taking the trace of \preveq/ yields that $\be=n-1$. If, as we may
assume, $S$ has the form
$$
S=\pmatrix{0&j^T\cr j^T& T\cr}
$$
then \preveq/ implies that
$$
TJ=-\al J,\qquad T^2+\al T-(n-1)I=-J.\idno{}
$$
From \preveq/ we deduce that ${1\over2}(T+J-I)$ is the adjacency
matrix of a strongly regular graph on $n-1$ vertices. Such a graph
must have $k=2c$ and, conversely, any strongly regular graph with
$k=2c$ on $n-1$ vertices determines a regular two-graph on $n$
vertices.
Two surveys on regular two-graphs appear in [\r{jjs}]. We mention one
question.
\result{2grfs}% 4.2
Problem. Is there a regular two-graph on 76 or 96 vertices?
\section{hamcyc}% 5
Hamilton Cycles
We consider the existence of Hamilton cycles in vertex transitive
graphs. Ignoring $K_2$, there are only four known vertex transitive
graphs without Hamilton cycles. Two of these are the Petersen and
Coxeter graphs. The Coxeter graph can be defined as follows. An {\sl
antiflag}\/ in a projective plane is an ordered pair $(p,\ell)$, where
$p$ is a point and $\ell$ is a line such that $p\notin\ell$. The
vertices of the Coxeter graph are the 28 antiflags from the projective
plane of order two. Two such antiflags $(p,\ell)$ and $(q,m)$ are
adjacent if the set
$$
\{p,q\}\cup\ell\cup m
$$
contains all points of the plane. For more on the
Coxeter graph, see Section~12.3 in [\r{bcn}].
The remaining two non-Hamiltonian vertex transitive graphs are
obtained from the Petersen and Coxeter graphs by `blowing up' each
vertex to a triangle. (Formally we take the line graph of the
subdivision graphs of the Petersen and Coxeter graphs. The {\sl
subdivision graph}\/ $S(G)$ of $G$ is obtained by installing one
vertex in the middle of each edge of $G$.) The problem with the
blowing-up process is that the graphs produced by applying it a second
time are no longer vertex transitive, although they are still cubic
and have no Hamilton cycle. For proofs that the Coxeter graph has no
Hamilton cycle, see [\r{trg}, \r{tut}].
\result{vtham}% 5.1
Problem. Are there any more connected vertex-transitive graphs without
Hamilton cycles?
Still ignoring $K_2$, the known non-Hamiltonian vertex-transitive
graphs are not Cayley graphs. Thus we are lead to ask whether all
connected Cayley graphs have Hamilton cycles. All known connected
vertex-transitive graphs have Hamilton paths, and Lov\'asz has
conjectured that all connected vertex-transitive graphs have Hamilton
paths. Witte [\r{witte}] has proved that all Cayley graphs of
$p$-groups have Hamilton cycles. For a survey of results on Hamilton
cycles in Cayley graphs see, e.g., [\r{witgl}].
Babai [\r{bab}] gives an ingenious proof that a connected
vertex-transitive graph on $n$ vertices must contain a cycle of length
at least $\sqrt{3n}$; no better lower bound is known. Mohar [\r{moh}]
derives an algebraic technique for showing that certain graphs do not
have Hamilton cycles. We present a simplified version of this for the
Petersen graph.
Let $P$ denote the Petersen graph and suppose that $C$ is a cycle of
length ten in it. Then the edges not in $C$ form a perfect matching
in $P$ and the vertices in the line graph of $P$ corresponding to the
edges of $C$ induce a cycle of length ten. Thus $P$ has a Hamilton
cycle if and only if there is an induced copy of $C_{10}$ in $L(P)$.
For any graph $X$ let $\th_i(X)$ denote the $i$-th largest eigenvalue
of the adjacency matrix of $X$. By interlacing
[\r{cgbk}:~Theorem~5.4.1], we know that if $Y$ is an induced subgraph
of $X$ then $\th_i(Y)\le\th_i(X)$. Since $\th_7(C_{10})>\th_7(L(P))$,
the Petersen graph cannot have a Hamilton cycle.
The only problem with this argument is that there seems to be no other
interesting case where it works. It fails on the remaining three
vertex-transitive graphs with no Hamilton cycles. It would be very
interesting to find a modification of this technique which could be
used to show that Coxeter's graph has no Hamilton cycle.
\section{matpol}% 6
The Matchings Polynomial
Let $p(X,k)$ denote the number of $k$-matchings in the graph $X$,
i.e., the number of matchings with exactly $k$ edges. If $X$ has $n$
vertices then its {\sl matchings polynomial}\/ of $X$ is defined to be
$$
\match(X,x)=\sum_{k\ge0} (-1)^k p(X,k) x^{n-2k}.
$$
It is known that the zeros of $\match(X,x)$ are all real
[\r{cgbk}:~Corollary~6.1.2] and that, if $X$ has a Hamilton path, they
are all simple. This leads us to ask:
\result{simple}% 6.1
Problem. Is there a connected vertex-transitive graph $X$ such that
$\match(X,x)$ does not have only simple zeros?
This question is discussed at some length in [\r{amt}]. There a graph
$X$ is defined to be $\th$-critical if, for each vertex $u$ of $X$,
the multiplicity of $\th$ as a zero of $\match(X\diff u,x)$ is less
than its multiplicity as a zero of $\match(X,x)$. All vertex
transitive graphs are $\th$-critical, by a straightforward argument.
Therefore we could solve Problem~6.1 by showing that if $X$ were a
connected $\th$-critical graph then $\th$ must be a simple zero of
$\match(X,x)$. This is known to be true if $\th=0$ (Gallai, see
[\r{lv-pl}:~Section~3.1]) or if $X$ is a tree (Neumaier [\r{neu}]).
For details, see [\r{amt}].
\section{lingrfs}% 7
Characterising Line Graphs
If $X$ is a line graph then the least eigenvalue of its adjacency
matrix $A(X)$ is at least $-2$. Cameron, Goethals, Seidel and Shult
proved a converse to this, which we want to discuss.
First, some definitions. A root system is, more or less, a set of
vectors in $\re^m$ which is invariant under reflection in the
hyperplane orthogonal to any vector in it. Let $e_1,\ldots,e_m$ be
the standard basis in $\re^m$. Then the root system $A_m$ is the set
of vectors
$$
e_i-e_j,\quad i\ne j
$$
and the root system $D_m$ is the set of vectors
$$
e_i\pm e_j,\quad i\ne j.
$$
We define $E_8$ to be $D_8$ together with all vectors in $\re^8$ with
entries $\pm{1\over2}$ and an even number of positive entries. It is
not hard to see that a graph $X$ is the line graph of a bipartite
graph if and only if $A(X)+2I$ is the Gram matrix of a subset of
$A_m$. We define $X$ to be a {\sl generalised line graph}\/ is it is
the Gram matrix of a subset of $D_m$. Every line graph lies in $D_m$.
Cameron et al.~proved that if $X$ is a graph with least eigenvalue at
least $-2$ then it is either a line graph, a generalised line graph or
$A(X)+2I$ is the Gram matrix of subset of $E_8$. This extended
earlier work, in particular of Alan Hoffman.
Now Hoffman [\r{hoff}] has also proved that a graph with least
eigenvalue greater than
$$
-1-\sqrt2
$$
and sufficiently large minimum valency is a generalised line graph.
(Here `sufficiently large' is determined by Ramsey theory, which means
that it is only finite in a fairly technical sense :-) .)
\result{leastev}% 7.1
Problem. Is there a classification of the graphs $X$ with
$\th_{\min}(X)>-1-\sqrt2$, analogous to that of the graphs with least
eigenvalue at least $-2$?
Let $\th_2(X)$ denote the second-largest eigenvalue of $X$. Then
for the complement $\comp X$ of $X$ we have
$$
\th_{\min}(\comp X)\le -1-\th_2(X).
$$
(This follows because we obtain $A(\comp X)$ by adding the matrix $J$,
with rank one, to $-I-A(X)$.) Hence if $\th_{\min}(\comp X)>-1-\sqrt2$
then $\th_2(X)<\sqrt2$. This indicates that it should also be
interesting to classify the graphs $X$ such that $\th_2(X)<\sqrt2$.
Woo and Neumaier [\r{woon}] have recently proved that, if $X$ is a
graph with least eigenvalue greater than the smallest root of the
polynomial $x^3+2x^2-2x-2$ (approximately $-2.4812$) and the minimum
valency of $X$ is large enough, then $\th_{\min}(X)\ge-1-\sqrt2$ and
$X$ has a well-determined structure. This result is very interesting,
but it still makes use of Ramsey theory and requires a lower bound on
the minimum valency of $X$.
\section{shancap}% 8
Shannon Capacity
The {\sl strong product}\/ $X*Y$ of the graphs $X$ and $Y$ has vertex
set $V(X)\times V(Y)$, with $(u,v)$ adjacent to $(u',v')$ if and only
if
\medbreak
\item{(a)} $u\sim u'$ and $v\sim v'$,
\item{(b)} $u=u'$ and $v\sim v'$, or
\item{(c)} $u\sim u'$ and $v=v'$.
\medbreak\noindent
We denote the strong product of $n$ copies of $X$ by $X^{(n)}$.
Let $\al(X)$ denote the maximum number of vertices in an independent
set in $X$. It is not hard to show that, for any graphs $X$ and $Y$
we have
$$
\al(X*Y)\ge\al(X)\al(Y)
$$
and from this it follows by Fekete's lemma (see Lemma~11.6 in [\r{vl-wil}])
that the limit
$$
\lim_{n\to\infty} \al(X^{(n)})^{1/n}
$$
always exists. We call it the {\sl Shannon capacity}\/ of $X$. This
quantity is of some interest in coding theory, but for further
information about this we refer the reader to [\r{lovsh}] and the
references given there.
Let $\om(X)$ be the size of the largest clique in the graph $X$. We
recall that $X$ is perfect if, for any induced subgraph $Y$ of $X$,
the chromatic number of $Y$ is equal to $\om(Y)$. All bipartite
graphs are perfect, and there are many other classes of perfect
graphs, almost as many as there are graph theorists who have studied
them. (For more information see, e.g., [\r{lovp}].) Shannon showed
that if $X$ is perfect then its Shannon capacity is equal to $\al(X)$.
However, using the fact that $C_5$ is self-complementary, it is not
hard to show that
$$
\al(C_5*C_5)=5
$$
and so the Shannon capacity of $C_5$ is at least $\sqrt5$, while
$\al(C_5)=2$. In 1979 Lov\'asz [\r{lovp}] settled a long-standing
open problem by proving that the Shannon capacity of $C_5$ is
$\sqrt5$. His methods enabled the Shannon capacity of many other
graphs to be determined, but the following question is still open.
\result{c7cap}% 8
Problem. What is the Shannon capacity of $C_7$?
\section{perfect}% 9
Perfect Codes
The {\sl ball of radius $m$}\/ about a vertex $v$ in a graph $X$ is
the set of all vertices in $X$ at distance at most $m$ from $v$. If
$C$ is a subset of $V(X)$, the {\sl packing radius}\/ of $C$ is
maximum integer $e$ such that the balls of radius $e$ about the
vertices in $C$ are pairwise disjoint. An {\sl $e$-code}\/ in $X$ is
a subset with packing radius at least $e$ and an $e$-code is {\sl
perfect}\/ if the balls of radius $e$ about its vertices partition
$V(X)$. The Hamming graph $H(n,q)$ has the set of all sequences of
length $n$ from $\{0,\ldots,q-1\}$ as its vertices, with two sequences
adjacent if they agree on all but one coordinate. If $X$ is the
Hamming graph, $e$-codes and perfect codes are precisely the $e$-codes
and perfect codes of standard coding theory. If $e\ge3$ and $q$ is a
prime power then there are only two perfect $e$-codes (see, e.g.,
[\r{bcn}:~p.~355], one in $H(11,3)$ and the other in $H(23,2)$.
The Johnson graph $J(v,k)$ has all $k$-subsets of a fixed $v$-subset
as its vertices, with two $k$-subsets adjacent if and only if they
intersect in exactly $k-1$ elements. Two $k$-subsets are then at
distance $i$ if and only if they have exactly $k-i$ elements in
common. The graphs $J(v,k)$ and $J(v,v-k)$ are isomorphic, so we will
assume that $v\ge2k$. When $v=2k$ and $k$ is odd, the pair formed by
a given $k$-subset and it complement is a perfect code with $e$ equal
to $\lfloor k/2\rfloor$. Delsarte [\r{dels}:~p.~55] raised the
following question.
\result{codes}% 9.1
Problem. Is there a perfect code with more than two vertices in a
Johnson graph?
The strongest result is due to Roos [\r{roos}], who proved that if
there is a perfect code in $J(v,k)$ with packing radius $e$ then
$$
v\le{2e+1\over e}(k-1).
$$
Hammond [\r{hamm}] proved that there are no perfect codes in
$J(2v+1,v)$ and $J(2v+2,v)$.
Perfect codes in other classes of distance regular graphs can also be
very interesting. Perfect codes in the Hamming graphs $H(n,q)$ are
part of classical coding theory---if $e\ge3$ and $q$ is a prime power
then the only perfect codes are binary and ternary Golay codes.
Chihara [\r{chi}] has proved that most of the known families of
distance regular graphs do not contain perfect codes. The Johnson
graphs are one family of exceptions here, and the closely related odd
graphs are another.
The odd graph $O(k+1)$ has the $k$-subsets of a $(2k+1)$-set as its
vertices, with two $k$-subsets adjacent if and only if they are
disjoint. (Thus it has the same vertex set as $J(2k+1,k)$.) The
lines of a Fano plane form a perfect 1-code in $O(4)$ and the blocks
of the Witt design on 11 points forms a perfect 1-code in $O(6)$. No
other examples are known. It not hard to show that there is a perfect
1-code in $O(m+1)$ if and only if there is a Steiner system with
parameters
$$
(m-1){\rm-}(2m+1,m,1).
$$
Hence these codes will not be easy to find. Smith [\r{smith}] has
proved that there are no perfect 4-codes in the odd graphs. Perhaps
it can be proved that there are no perfect $e$-codes in the odd graphs
for $e$ sufficiently large (ideally for $e\ge2$).
Of course we should not forget that there may be interesting classes
of codes which are not perfect. Completely regular codes (see
Chapter~11 in [\r{bcn}]) provide one example.
\section{pranks}% 10
$p$-Ranks
Let $H_v(k,\ell)$ be the $01$-matrix with rows and columns
respectively indexed by the $k$- and $\ell$-subsets of a fixed
$v$-set, and with $ij$-entry equal to one if and only if the $i$-th
$k$-subset is contained in the $j$-th $\ell$-subset. When
$k\le\ell\le v-\ell$, the rows of $H_v(k,\ell)$ are linearly
independent over the rationals. A surprisingly large number of the
applications of linear algebra to combinatorics rest on this fact.
(Some of these are presented in [\r{tools}].) For the earliest proof
of independence known to me, see [\r{gott}]. More recently Richard
Wilson [\r{rmwil}] determined the rank of $H_v(k,\ell)$ over all
finite fields. It is not clear what the combinatorial implications of
this will be, but surely it will be useful in time.
There is a so-called $q$-analog of this problem. Consider the
incidence structure formed by the $k$- and $\ell$-subspaces of a
$v$-dimensional vector space over the field with $q$ elements (where a
$k$-space is incident with the $\ell$-spaces which contain it). Then
it is natural to want to know the rank of this matrix. Over what
field? There are three cases. Over the rationals this has been known
at least since Kantor [\r{kant}]. For primes not dividing $q$ the
answer appears in [\r{fryaq}]; the result is in fact analogous to
Wilson's for the rank of $H_v(k,\ell)$ in positive characteristic.
The most interesting case is still open.
\result{subsp}% 10.1
Problem. What is the $p$-rank for the incidence matrix of $k$-spaces
versus $\ell$-spaces of a $v$-dimensional vector space over a field of
order $p^r$?
\section{homs}% 11
Homomorphisms
Let $X$ and $Y$ be graphs. A mapping $f$ from $V(X)$ to $V(Y)$ is a
{\sl homomorphism}\/ if $f(u)$ is adjacent to $f(v)$ in $Y$ whenever
$u$ is adjacent to $v$ in $X$. Since we do not allow vertices to be
adjacent to themselves, $f$ must map edges of $X$ to edges of $Y$. If
$Y$ is a complete graph with $r$ vertices then the homomorphisms from
$X$ into $Y$ correspond to the proper colourings of $X$ using at most
$r$ vertices. The {\sl product}\/ $X\times Y$ of the graphs $X$ and
$Y$ has vertex set
$$
V(X)\times V(Y)
$$
and $(u,v)$ is adjacent to $(u',v')$ if and only if $u$ is adjacent to
$u'$ and $v$ is adjacent to $v'$. (This is the natural product in the
category of graphs and homomorphisms, if it helps.)
S. Hedetniemi has made the following conjecture.
\result{hedconj}% 11.1
Conjecture (Hedetniemi). For any two graphs $X$ and $Y$
$$
\chi(X\times Y)=\min\{\chi(X), \chi(Y)\}.
$$
When $n=3$ we can verify the conjecture by showing that the product of
two odd cycles contains an odd cycle. For $n=4$, it was proved true
by El-Zahar and Sauer in 1985 [\r{elzsau}]. The remaining cases are
still open, in fact we cannot exclude the possibility that
$\chi(X\times Y)$ is less than 16 for some pair of graphs $X$ and $Y$
with arbitrarily large chromatic number! (See [\r{polrdl}] for this
and, for some recent work on this problem, with more references,
see [\r{sauzhu}].)
The {\sl Kneser graph}\/ $K(v,k)$ has all $k$-subsets of a fixed
$v$-set as its vertices, with two $k$-subsets adjacent if they are
disjoint. So $K(v,1)$ is the complete graph $K_v$ and $K(2v+1,v)$ is
the odd graph $O(v+1)$. (In particular, $K(5,2)$ is Petersen's
graph.) The following question was raised by Pavol Hell.
\result{kneserhom}% 11.2
Problem. For which pairs $(X,Y)$ of Kneser graphs is there a
homomorphism from $X$ to $Y$?
Stahl [\r{stahl}:~Section~2] proved that if $v>2k$ there is a
homomorphism from $K(v,k)$ to $K(v-2,k-1)$. Hence there is a
homomorphism from $K(v,k)$ to $K_{v-2k+2}$, i.e., the chromatic number
of $K(v,k)$ is at most $v-2k+2$. Lov\'asz [\r{lovkn}] proved that
equality holds here, from which it follows that if $v-2k>v'-2k'$ then
there is no homomorphism from $K(v,k)$ to $K(v',k')$. Further
$K(v',k)$ is an induced subgraph of $K(v,k)$ whenever $v'\le v$. For
any integer $r$ there is an obvious homomorphism from $K(v,k)$ into
$K(rv,rk)$, but none into $K(v',kr)$ when $v'