% These are the problems from the 14th BCC.

\def\prop{\medskip{\it Proposer}\/:\ }
\def\orig{{\it Originator}\/:\ }
\def\origs{{\it Originators}\/:\ }
\def\prob#1. #2\par{\bigbreak\noindent{\bf#1. #2}\nobreak\medskip}
\def\note{\noindent{\it Editor's note}\/:\ }
\centerline{\bf Problems from the Fourteenth}
\centerline{\bf British Combinatorial Conference}

\bigskip\bigskip

{\it Edited by} P. J. Cameron, School of Mathematical Sciences, Queen Mary
\& Westfield College, Mile End Road, London E1 4NS, U.K.\par
\noindent\qquad{\tt P.J.Cameron@qmw.ac.uk}
\medskip
\rightline{Preliminary version of 28 July 1993}

\bigskip\bigskip

Most of these problems were presented at the Problem Session held at the
conference. However, I have also included some problems from participants
who were unable to attend the session, or remembered afterwards problems
they should have presented. The originator of the problem is given, where
known and different from the proposer. If no originator is given, either
it is the proposer's problem, or my ignorance is to blame. If no proposer
is given, the problem is taken from my incomplete notes at the Problem
Session; I'd be grateful if proposers could claim their problems and
correct them if necessary, or if anyone who remembers who the proposer
was could let me know.

Problems are grouped roughly by subject matter.

The addresses of presenters are given at the end. Communication is
encouraged!

\bigskip\bigskip

\prob 1. Total colourings of hypergraphs

A {\it total colouring} of a hypergraph is a colouring of vertices and
edges such that
\item{(a)} the restrictions to vertices and edges are strong colourings;
\item{(b)} an incident vertex and edge have different colours.

\noindent The {\it total chromatic number} is the least number of colours
required for a total colouring.

\smallskip

\noindent{\bf Conjecture.} If $H=(V,{\cal E})$ is a linear hypergraph (two
vertices on at most one edge) with total chromatic number $\chi_T(H)$, then
$$\chi_T(H)\le\max_{x\in V}\left|\bigcup_{{E\in{\cal E}}\atop{x\in E}}E
\right|+1.$$

\prop Peter Cowling.

\prob 2. Critical $K_l$-free graphs

It is known that $k$-chromatic critical graphs on $n$ vertices have at
least $\left({k-1\over2}\right)n$ edges. Gallai showed that a better
lower bound holds for graphs containing no $K_k$. Can this bound be
further improved for graphs containing no $K_l$, for fixed $l$ with
$3\le l\le k$?

For example, with $k=10$, $l=9$, can the bound $4.5n$ be improved to
$5n-10$?

\prop J. Sch\"onheim.

\prob 3. Bandwidth of a graph

The {\it bandwidth} of an $n$-vertex graph $G$ is
$$\min_f\max_{x\sim y}|f(x)-f(y)|,$$
where the minimum is over all bijections from the vertex set to $\{1, \ldots,
n\}$.

What is the bandwidth of the ``triangular lattice'' graph whose vertices
are the triples of non-negative integers with sum $l$, vertices $(x,y,z)$
and $(x',y',z')$ being adjacent whenever $|x-x'|+|y-y'|+|z-z'|=2$? (A lower
bound of $l/2$ is known, and an upper bound of $l+1$ is obtained by
numbering the vertices by layers.) The upper bound is conjectured to be
best possible.

\prop Douglas B. West

\prob 4. Disjoint circuits

Let $G$ be a 3-regular bridgeless graph. Given a collection ${\cal C}=\{C_1,
\ldots, C_n\}$ of vertex-disjoint circuits in $G$, define
$$\omega_{\cal C}=\left|V(G)-\bigcup_{1\le i\le n}V(C_i)\right|
+|\{i:1\le i\le n,|C_i|\hbox{ odd}\}|.$$
Then $\omega_{\cal C}$ is even.

\noindent{\bf Conjecture.} If $\omega_{\cal C}\le2$, then for any edge $f$
lying in one of the circuits in $\cal C$, there exists another collection
${\cal C}'=\{C_1', \ldots, C_{n'}'\}$ such that $\omega_{{\cal C}'}\le2$
and $f$ lies in no edge of ${\cal C}'$.

This is true with 0 in place of 2. What about larger even numbers?

\prop ??

\prob 5. How small is Tutte's wheel?

W. T. Tutte proved that any 3-connected graph can be obtained from a wheel
by repeatedly adding an edge or splitting the central vertex (keeping the
minimum degree at least 3).

\noindent{\bf Conjecture.} Any 3-connected cubic graph on $n$ vertices may
be obtained by this procedure from a wheel on $k$ vertices, where $k\ge cn$
(for some absolute constant $c$).

\prop Aditya Shastri.

\prob 6. Characteristic polynomials of graphs

How many distinct characteristic polynomials of (adjacency matrices of)
$n$-vertex graphs are there?

The proposer conjectures that a typical $n$-vertex graph has $n^2$ cospectral
mates, so that the answer to the problem is $O(2^{n(n-1)/2}/n^2n!)$.

\prop Roland H\"aggkvist.

\note In discussion of this at the Conference, some scepticism was expressed
about the truth of this conjecture.

\prob 7. Cliques and cocliques in Cayley graphs

\noindent{\bf Conjecture.} There is a constant $c$ such that, for every
finite group $G$ of order $n$, there is a symmetric (i.e., inverse-closed)
generating set $S$ for $G$ such that the Cayley graph $\Gamma(G,S)$ has no
clique or independent set of size $c\log n$.

This is not known for any infinite sequence of finite groups; but it is
true with $\log^2 n$ replacing $\log n$.

\prop Noga Alon.

\prob 8. Local structure in 2-transitive graphs

\noindent{\bf Problem.} Determine the vertex and edge stabilizers in all
locally finite 2-transitive graphs in which $G_1(x)=1$.

(A graph is 2-transitive if it admits a group $G$ acting transitively on
2-arcs. The condition $G_1(x)=1$ means that a vertex stabilizer acts
faithfully (and 2-transitively) on its neighbours. The answer to this
problem would be a list of pairs $(H, t)$, where $H$ is a finite
2-transitive group (the vertex-stabiliser $G(x)$) and $t$ an outer
automorphism of order 2 of the stabilizer $H_y$ (so that $H_y\langle t
\rangle=G(e)$, where $e=\{x,y\}$).)

\prop Sasha Ivanov.

\prob 9. The rows of a Latin square

It is known that, for almost all Latin squares of order $n$ (i.e., a
proportion tending to 1 as $n\to\infty$), the rows of the square (regarded
as permutations) generate $S_n$ or $A_n$. Is this statement still true if
the squares are normalized so that the first row is the identity
permutation?

A subsidiary problem: Is it true that we almost always obtain the
symmetric, rather than the alternating, group?

\prop Peter Cameron.

\prob 10. Even and odd cycles.

If $n$ is even, then the number of permutations of $\{1, \ldots, n\}$ with
all cycles of even length is equal to the number of permutations with all
cycles of odd length. (Both numbers are in fact $(n-1)!!$.) Find a
bijective proof of this fact.

\prop Peter Cameron. 

\prob 11. A bijective proof of the Dyson conjecture

Let $R(r, m, n)$ denote the set of partitions of $n$ whose rank is
congruent to $r$ modulo $m$, where the {\it rank} of a partition is the
largest part minus the number of parts. Freeman Dyson conjectured, and
Atkin and Swinnerton-Dyer proved, that
$$|R(0,5,5n+4)|=|R(1,5,5n+4)|=\ldots=|R(4,5,5n+4)|.$$
The problem is to find a bijective proof.

\prop Richard Lewis. \orig Freeman Dyson, George Andrews.

\prob 12. How many sum-free sets?

Let $s(n)$ be the number of sum-free subsets of $\{1, \ldots, n\}$ (i.e.,
containing no solution to $x+y=z$). Show that there exist constants
$c_o$ and $c_e$ such that $s(n)/2^{n/2}\to c_o$ or $c_e$ as $n\to\infty$
through odd or even values respectively.

It is known only that $s(n)=2^{({1\over2}+o(1))n}$.

\prop Peter Cameron. \orig Peter Cameron \& Paul Erd\H os.

\prob 13. Non-crossing queens

What is the maximum number of non-crossing $n$-queens? It is known that
the maximum is $n$ if $n$ is prime.

\prop Reza Khosrovshahi.

\prob 14. Triples from seven

There is no large set of triple systems on seven points (i.e., partition
of all the triples into triple systems). Find a way to display the
triples to make this obvious.

\prop Reza Khosrovshahi.

\prob 15. Block-transitive designs

A $t$-$(v, k, \lambda)$ design has $v$ points and a collection of
blocks of size $k$, any $t$ points lying in exactly $\lambda$ blocks.
Terms such as ``block-transitive'' apply to the action of the
automorphism group.
\item{(a)} Show that there is no block-transitive 6-design.
\item{(b)} Show that a block-transitive, point-imprimitive 3-design
satisfies $v\le{k\choose2}+1$.
\item{(c)} Is there a block-transitive 2-$(\infty, 4, 1)$ design which
is not point-transitive?

\prop Peter Cameron. \orig Peter J. Cameron and Cheryl Praeger.

\note Part (a) has appeared in the {\it Kourovka Notebook}.

\prob 16. Blocking-set-free configurations

A configuration $n_3$ has $n$ points and $n$ lines, with three points 
on each line and three lines through each point, such that two points 
lie on at most one line. A {\it blocking set} is a set of points 
meeting every line but containing none. For which $n\ge7$ does there exist
a connected $n_3$ configuration with no blocking sets?

It is known that such configurations exist for all but finitely many 
values of $n$. They do not exist for the values 8--12 or 14.
The values in doubt are 15--18, 20, 23, 24, 26. (The value 15 may now be
settled). See J.\ W.\ DiPaola and H.\ Gropp, {\it Mitt. Math. Sem. Gie\ss en} 
(to appear).

\prop H.\ Gropp. \origs J. W. DiPaola \& H.\ Gropp. 

\note This problem is repeated in updated form
from the Problem Session at the $13^{\rm th}$ BCC.

\prob 17. Arranging rows and columns

Consider the following problem: Given a matrix of zeros and ones, permute
the rows and columns such that, in the resulting matrix, it is possible to
label every zero with the symbol R or C such that
\item{$\bullet$} if an entry is labelled R, then every zero to the right is
labelled R;
\item{$\bullet$} if an entry is labelled C, then every zero below it is
labelled C.

\noindent What is the complexity of this problem?

(If the Rs and Cs are allowed to overlap, the problem becomes easy.)

\prop ??

\prob 18. Piles of counters

I learned this problem just after the conference. Suppose that we have
$n$ counters divided into $r$ non-empty piles, of sizes $n_1, \ldots, n_r$.
A {\it move} consists in replacing two piles of sizes $n_i$ and $n_j$ by
a single pile of size $n_i+n_j$; its {\it payoff} is 2 if $n_i=n_j$, 1
otherwise. After $r$ moves, we have a single pile of size $n$.
\item{(a)} Is there a simple formula for the maximum total payoff which can
be achieved?
\item{(b)} If not, what is the complexity of calculating the maximum payoff?

\noindent This problem has a group-theoretic origin. For the case where
$n_i=1$ for $i=1, \ldots, r=n$, the maximum is $\lceil 3n/2 \rceil -b(n)-1$,
where $b(n)$ is the number of ones in the base 2 expansion of $n$.

\prop Peter Cameron. \orig Ron Solomon.

\prob 19. A binomial challenge

This problem arose in the work of two of my colleagues who are astronomers
(interested in solar system dynamics). Let
$$S_l=\sum_{k=0}^l{l\choose k}(-1)^{k+c+d}2^{d+d'-c-c'}k^{c+c'}(k-1)^d
(k+1)^{d'},$$
where $c, c', d, d'$ are given non-negative integers. Show that
$S_l=0$ for all $l>c+c'+d+d'$. (If $k=0$ and $c+c'=0$, take $k^{c+c'}=0$;
and if $k=1$ and $d=0$, take $(k-1)^d=0$. Alternatively, start the summation
at $k=2$.)

\prop Peter Cameron. \orig Carl Murray and David Harper

\bigskip\bigbreak
\centerline{\bf Addresses of proposers}
\medskip
\def\email#1{\nobreak\qquad{\tt#1}}
\frenchspacing
\parindent=0pt
\everypar{\hangindent=1em\hangafter=1}

Noga Alon, Department of Mathematics, Tel-Aviv University, Ramat Aviv,
69978 Tel-Aviv, Israel.
\smallbreak

Peter Cameron, School of Mathematical Sciences, Queen Mary and 
Westfield College, Mile End Road, London E1 4NS, U.K.\par
\email{P.J.Cameron@qmw.ac.uk}
\smallbreak

Peter Cowling, Mathematical Institute, 24--29 St.\ Giles', Oxford OX1 3LB,
U.K.\par
\email{cowling@vax.ox.ac.uk}
\smallbreak

Harald Gropp, Muehlingstra\ss e 19, D-69121 Heidelberg, Germany.
\smallbreak

Roland H\"aggkvist, Department of Mathematics, University of Ume\aa,
S-90187 Ume\aa, Sweden.
\smallbreak

A. A. Ivanov, Institute for Systems Analysis, 9, Prospekt 60-Let Oktyabrya,
117312 Moscow, Russia.
\smallbreak

G. B. Khosrovshahi, Institute for Studies in Theoretical Physics and
Mathematics, University of Tehran, P.O. Box 13145--1873, Tehran, Iran.
\smallbreak

Richard Lewis, Mathematics Subject Group, MAPS, University of Sussex, Brighton
BN1 9QH, U.K.
\smallbreak

J. Sch\"onheim, Department of Mathematics, Tel-Aviv University, Ramat Aviv,
69978 Tel-Aviv, Israel.
\smallbreak

Aditya Shastri, Department of Mathematics and Computer Science, Banasthali
University, P.O. Banasthali Vidyapith--304 022, India.
\smallbreak

Douglas B. West, Department of Mathematics, University of Illinois,
Urbana, IL 61801, U.S.A.
\smallbreak

\bye
