% These are the problems from the 13th BCC. They are here so you can try
% to FTP them. They will be joined by the problems from the 14th BCC
% when available -- pjc, 17/5/93.

\def\prop{\medskip{\it Proposer}\/:\ }
\def\orig{{\it Originator}\/:\ }
\def\origs{{\it Originators}\/:\ }
\def\prob#1#2{\bigbreak{\bf#1. #2}\medskip}

\centerline{\bf Problems from the Thirteenth}
\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}

\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.

Problems are grouped roughly by subject matter.

The addresses of presenters are given at the end. Communication is
encouraged; indeed, one presenter conjectured that the answer to his
question is known!

\bigskip\bigskip

\prob{1}{Stable partitions of graphs}

A partition of the vertex set $V$ of a (simple) graph $G$ into two non%
-empty parts $V_1$ and $V_2$ is called {\it stable} if, for $i=1, 2$, 
and all vertices $x\in V_i$,
$${\rm deg}_{G|V_i}(x) > {\scriptstyle 1\over2}{\rm deg}_G(x).$$
A graph with a stable partition is also called {\it stable}. The 
complete graph is not stable, but every 3-regular graph other than 
$K_4$ is stable.

What is the number of stable graphs? In particular, is the proportion 
of graphs on $n$ vertices which are stable $o(1)$?

\prop Z.\ F\"uredi.

\prob{2}{Ramsey perfect graphs}

Is it true that, for every prfect graph $G$, there exists a perfect 
graph $H$ such that, for every partition $E(H) = E_1 \cup E_2$, there 
is an induced subgraph $G'$ of $H$ such that $G'$ is isomorphic to $G$
and $E(G') \subseteq E_i$ for some $i$ ($i=1$ or 2)?

We expect a negative answer to this question, despite the fact that 
the analogous question for partitions of vertices has an affirmative 
answer (using the Lov\'asz Multiplication Lemma).

\prop J.\ Ne\v set\v ril.

\prob{3}{Reconstructing spanning trees}

Is the number of spanning trees with exactly $d$ automorphisms 
reconstructible from the deck of vertex-deleted subgraphs of a graph,
for each $d$?

\prop C.\ Wakelin. \orig W. L. Kocay.

\prob{4}{1 time 2-tough implies 2 times 1-tough?}

Prove that the edge set of a 2-tough graph $G$ can be partitioned into
two sets $E_1$ and $E_2$ such that each of $E_1$ and $E_2$ induces a
1-tough spanning subgraph of $G$.

If this conjecture is true, then a 4-regular 2-tough graph would 
consist of two edge-disjoint Hamiltonian cycles. One could accordingly
extend Thomassen's conjecture to the assertion that any 2-tough graph 
contains two edge-disjoint Hamiltonian cycles.

(A graph is $t$-tough if,
for any vertex cutset $S$, $G-S$ has at most $|S|/t$ components. Chv\'atal
conjectured that, for $t>3/2$, a $t$-tough graph is Hamiltonian. This
was refuted by Thomassen, who conjectured instead that a 2-tough graph
is Hamiltonian.)

\prop C.\ Hoede.

\prob{5}{Path-tough graphs}

Let $G$ be a simple graph on $n$ vertices, where $n \ge 3$, which is 
{\it path-tough} (that is, $G-v$ has a Hamiltonian path for any vertex
$v$.) Suppose that $d(u)+d(v)+d(w) \ge n-2$ for any three independent 
vertices $u, v, w$. Prove that either $G$ is Hamiltonian, or $G$ is 
isomorphic to the Petersen graph.

\prop I.\ Schiermeyer.

\prob{6}{Hamilton cycles and a bit more}

Prove that any graph of order $n$ and minimum degree at least 
${1\over2}(n+1)$ contains a subgraph which is a Hamiltonian cycle 
together with a longest diagonal.

\prop R.\ H\"aggkvist.

\prob{7}{The second longest cycle}

Give lower bounds for the length of the second longest cycle in a 
Hamiltonian 3-regular graph. (The best bound currently is $n-4\sqrt 
n$.) More generally, the same problem with ``minimum degree 3'' in 
place of ``3-regular''.

\prop R.\ H\"aggkvist.

\prob{8}{4-chromatic covering graphs}

What is the smallest 4-chromatic covering graph? (A graph is a {\it 
covering graph} if its edges can be oriented in such a way that it 
becomes a Hasse diagram of a poset.) The answer lies between 12 and 14
inclusive.

\prop D.\ Youngs.

\prob{9}{Special Hamiltonian paths}

Consider the diagram of the poset of all subsets of $\{1, 2, 
\ldots, n\}$. As a graph, this is the $n$-cube. Does the graph have a 
Hamiltonian path  $A_1, A_2, \ldots, A_{2^n}$ starting at
$A_1 = \emptyset$ and having the following property?
\item{$\bullet$} {\sl If, at step $i$, you visit a set $A_i$, then you must 
previously have visited all subsets of $A_i$ with at most one 
exception. If there is an exception, you must visit it next (that is, 
it is $A_{i+1}$).}

For example, with $n=4$,
$$\emptyset, 1, 12, 2, 23, 3, 34, 4, 24, 124, 14, 134, 13, 123, 1234, 
234$$
is such a path.

\prop T.\ Trotter. \origs T. Trotter \& S. Felsner.

\prob{10}{Interval-regular graphs}

Let $G$ be a connected simple graph. The {\it interval} $I(u, v)$ 
between vertices $u$ and $v$ is the set of vertices which lie on some 
shortest path from $u$ to $v$. The graph is called {\it interval-regular}
if, for any two vertices $u$ and $v$, we have
$$|N(u) \cap I(u, v)| = d(u, v),$$
where $N(u)$ is the set of neighbours of $u$.

Examples of interval-regular graphs include hypercubes, and the 2-cube
and 3-cube with added edges joining all vertices in $N(u)$ for some 
vertex $u$. The class of interval-regular graphs is closed under taking
Cartesian products. See Mulder, {\it Math. Centre Tracts} {\bf 132} (1980),
or {\it Discrete Math.} {\bf 41} (1983), 253--269.

Conjecture: Let $G$ be interval-regular. Then
$$x, y\in I(u, v) \Rightarrow I(x, y) \subseteq I(u, v)$$
for any vertices $u$ and $v$.

\prop H.\ M.\ Mulder.

\prob{11}{Permutations of a cube}

Let $C$ be the $n$-cube graph, $d$ the graph metric. Is any 
permutation of the vertices of $C$ the composite of at most $n$ 
permutations $s_i$, each satisfying
$$d(x,s_i(x)) \le 1$$
for all $x \in C$\/?

{\it Editor's note\/}: More generally, which graphs of diameter $n$
have this property?

\prop M.\ K.\ Siu

\prob{12}{Permutations of projective space}

For which $n$ and $q$ does there exist a permutation $\pi$ of the 
point set of $PG(n, q)$ with the property that, for any hyperplane 
$H$, there exists a hyperplane $H'$ with $\pi(H) \cap H' = \emptyset$?
It is known that the answer is ``yes'' for $n=2$ (asymptotically, 
almost all permutations have this property), and ``no'' for $n>q$ (by 
a short argument due to A.\ Blokhuis).

\prop P.\ J.\ Cameron. \orig A.\ Gy\'arf\'as.

\prob{13}{$q$-polynomials}

A polynomial $c(z) = \sum c_iz^i$ over $GF(q)$ is said to be a
$q$-{\it polynomial} if $c_i\not=0$ only if $i$ is a power of $q$. 
(See Lidl \& Niederreiter, {\it Finite Fields}, Cambridge Univ. Press.)
Let $m=2^d-1$ be a Mersenne prime. Does there exist a 2-polynomial
$$c(z) = \sum_{i=0}^d c_iz^{2^i}$$
of degree $2^d$ such that $c(z)/z$ is irreducible over $GF(2)$? (The 
answer is ``yes'' for the first four Mersenne primes, viz.\ 3, 7, 31, 
127.)

\prop A.\ Bonisoli.

\prob{14}{Cyclic shifts of binary words}

For odd $n$, let $W_n$ be the space of binary words of length $n$ and 
even weight. Let $f(n)$ be the maximum codimension of a subspace of 
$W_n$ such that the union of all cyclic shifts of $U$ is equal to 
$W_n$. It is known that $f(n) \ge 2$ for $n>3$, but little more is 
known. Does $f(n)\to\infty$ as $n\to\infty$? Or is $f(n)=2$ for 
infinitely many $n$?

\prop P.\ J.\ Cameron.

\prob{15}{A generalisation of arcs}

Let $(V, {\cal B})$ be an affine plane of odd order $q$. Given a function 
$w : V \to {\bf Z}$ such that
$$\sum_{p\in L} w(p) \le 2$$
for all $L \in {\cal B}$, set
$$\hbox{mass}(w) = \sum_{p\in V} w(p).$$
Then $\hbox{mass}(w) \le q+2$ holds. The value $q+1$ can be attained
(by the characteristic function of a conic). Prove that necessarily
$\hbox{mass}(w) \le q+1$.

\prop J.\ Bierbrauer.

\prob{16}{Perfect Steiner triple systems}

Let $(V, {\cal B})$ be a Steiner triple system of order $v$ (an STS($v$)).
For distinct points $x, y$, contained in the block $\{x, y, z\}$,
the {\it interlacing graph} $G_{xy}$ is the 2-regular graph on 
the vertex set $V \setminus \{x, y, z\}$, in which $a$ and $b$ are 
adjacent whenever $\{a, b, x\}$ or $\{a, b, y\} \in {\cal B}$. The STS
is called {\it perfect} if $G_{xy}$ is a Hamiltonian cycle for all $x,y$.

Problem: Find more perfect STS. Are there infinitely many? (Only four 
are known, with orders 7, 9, 25, and 33. There is none of order 13 or 
15. All known examples have point-transitive automorphism groups.)

\prop A.\ Rosa. \origs C.\ J.\ Colbourn \& A.\ Rosa.

\prob{17}{A generalisation of affine designs}

An {\it affine design} is a 2-design in which any two non-parallel 
blocks meet in a constant number $y$ of points. What happens if we 
replace ``non-parallel'' by ``non-disjoint'' in this definition? In 
addition to the affine designs, there are resolvable designs with 
$\lambda=1$ (and $y=1$), for example Kirkman systems. No others are 
known; the first unknown case is a resolvable 2-(70, 10, 6) design 
with $y=2$.

\prop P.\ J.\ Cameron.

\prob{18}{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, 29, 30, 32, 38, 44.
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. 

\prob{19}{Permutations with few distances}

For fixed $s$, or for $s<n/2$, the best known upper and lower bounds 
for the maximum number of permutations of an $n$-set with $s$ 
differences are both roughly $(cn/s)^{2s}$ (with different values of 
$c$. Find the correct value.

\prop P.\ J.\ Cameron.

\prob{20}{Partial transversals of Latin rectangles}

Let $R$ be an $n \times 2n$ Latin rectangle on $2n$ symbols. A partial
transversal $T$ of size $s$ of $R$ is a collection of $s$ cells, no 
two in the same row or column, and no two containing the same symbol. 
Is it true that $R$ can be expressed as the union of $2n$ partial 
transversals of size $n$?

An equivalent formulation: Call two $n \times 2n$ Latin rectangles 
$R$, $S$ on the same set of symbols {\it orthogonal} if the pairs
$(r_{ij},s_{ij})$, for $i=1, \ldots, n$, $j=1, \ldots, 2n$, are all 
distinct. Does every $n \times 2n$ Latin rectangle have an orthogonal 
mate?

\prop A.\ J.\ W.\ Hilton.

\prob{21}{Semi-Latin squares}

A {\it semi-Latin square} is an $n \times n$ array with $k$ symbols
(chosen from an alphabet of size $nk$) in each cell, so that each 
symbol occurs once in each row or column. We impose the further 
property
\item{$\bullet$} {\sl No two symbols occur together in a cell more than once.}

Such a structure clearly exists if there are $k$ mutually orthogonal Latin 
squares of order $n$, on distinct sets of symbols.

Problem: Find constructions for values $(n, k)$ for which a set of $k$
m.o.l.s.\ of order $n$ does not exist (or is unknown). (Examples are 
known for $(n, k)=(6, 2)$ or (6, 3). What about (6, 4)? (10, 3)?)

\prop R.\ A.\ Bailey.

\prob{22}{Tiling the square}

(a) What is the least {\it odd} number of congruent non-rectangular 
tiles needed to tile a square?

(b) Is there such a tiling in which the tiles are not polyominoes?

The best tiling known to the proposer uses 25 copies of the polyomino 
with two rows containing 6 and 3 squares, aligned at one end.

\prop D.\ Youngs.

\prob{23}{Covering the square}

(a) Prove that, for any partition of the plane into sets (or regions) 
of diameter 1, the density must be at least $8/3\sqrt3$.

(b) A finite variation. What is the largest square which can be 
partitioned into $n$ sets of diameter (at most) 1? The answer is known
for $n \le 5$. In general, we would expect a hexagonal honeycomb with 
some distortion at the edges.

An equivalent formulation asks for the chromatic number of the graph 
whose vertices are the points of the unit square, two points adjacent 
if their distance exceeds $d$.

\prop F.\ Barnes.

\prob{24}{Sum-free sets containing 2}

What is the probability that, in a random sum-free set $S$ of natural 
numbers, 2 is the only even number in $S$? (Is it zero or not?)

(The probability measure is defined by the following rule. Consider 
the natural numbers in their usual order. If $n$ is the sum of two 
numbers in $S$, then $n \not\in S$; otherwise, decide on the toss of a
fair coin. It is known that the probability that $S$ contains no even 
numbers is non-zero, but the present problem seems a bit more 
delicate.)

\prop N.\ J.\ Calkin. \orig P.\ J.\ Cameron.

\prob{25}{Partitions of intersecting families}

Let $\cal F$ be an intersecting family of $k$-subsets of the
$n$-element set $V$, that is, $F \cap F' \not= \emptyset$ for all $F, F' 
\in {\cal F}$. Let $p({\cal F})$ be the minimum $p$ for which one can 
find $p$ pairs (2-subsets) $P_1, \ldots, P_p$ of $V$ such that every 
member of $\cal F$ contains some $P_i$. Now let $f(n,k)$ be the maximum
of $p({\cal F})$, over all such intersecting families. Is it true that
$f(n,k)\le n$ for all $n$?

If true, this would imply a strengthened form of the case $t=1$ of
Larman's conjecture, since
$${\cal F}_i = \{F \in {\cal F} : P_i \subseteq F, P_j \not\subseteq F
\hbox{ for } j<i,$$
for $i=1, \ldots, n$, is a decomposition of $\cal F$ into
2-intersecting families.

({\it Larman's conjecture} (D. G. Larman, {\it Ann. Discrete Math.} {\bf 20}
(1984)), asserts that if $\cal F$ is a $t$-intersecting family of
$k$-subsets of the $n$-set $V$, that is, $|F\cap F'|\ge t$ for all
$F, F'\in{\cal F}$, then $\cal F$ can be decomposed into $n$ subfamilies
each of which is $(t+1)$-intersecting.)

{\it Editor's Note:} A similar question can be asked for arbitrary families
of sets (not all of the same size).

\prop Z.\ F\"uredi. \origs N.\ Alon, P.\ Seymour \& Z. F\"uredi.

\prob{26}{Some families of sets}

What can be said about families $\cal F$ of subsets of an $n$-set $V$ 
satisfying
\item{(i)} $F_1, F_2 \in {\cal F} \Rightarrow F_1 \not\subset F_2$;
\item{(ii)} $F_1, F_2 \in {\cal F} \Rightarrow F_1 \cap F_2 \not= 
\emptyset$;
\item{(iii)} $(\forall x \in V)(\exists F_1, F_2\in {\cal F})\; F_1 \cap 
F_2 = \{x\}$.

\prop N.\ J.\ Calkin.

\prob{27}{Some problems on perfect groups}

(a) Prove the Feit--Thompson theorem by elementary means. (Remark: either
of the following equivalents of the Feit--Thompson theorem may be more
convenient:
\item{$\bullet$} A finite perfect group can be generated by a self-inverse
conjugacy class of elements of odd order (Heineken, unpublished);
\item{$\bullet$} If $G$ has odd order $n$, then some element of $G$ is not
the product of $n$ distinct factors (D\'enes and Hermann, {\it Ann. Discrete
Math.} {\bf 15} (1982), 105--109).)

(b) Show that a perfect group can be generated by an involution and an
element of odd order which is conjugate to its inverse.

(c) Characterise finite groups in which every element is a commutator. In
particular, show that every non-abelian simple group has this property
(Ore's conjecture).

(d) Characterise finite groups $G$ in which every element of the derived
group is the product of $k$ commutators. (This condition can be expressed
in terms of the notion of $k$-conjugacy (Yff, {\it Proc. Edin. Math. Soc.}
{\bf 14} (1964), 1--4).)

\prop{P.\ Yff.} \origs{J.\ D\'enes \& P.\ Yff.}

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

Rosemary Bailey, Department of Mathematics and Statistics, Goldsmiths 
College, Lewis\-ham Way, London SE14 6NW, U.K.\par
\email{r.bailey@gold.lon.ac.uk}
\smallbreak
Frank Barnes, Department of Mathematics, Kenyatta University, P.O.\ Box
43844, Nairobi, Kenya.
\smallbreak
Jurgen Bierbrauer, Mathematisches Institut der Universit\"at, Im Neuenheimer
Feld 288, 69 Heidelberg, Germany.
\smallbreak
Arrigo Bonisoli, Dipartimento di Matematica, Universit\`a della 
Basilicata, via N. Sauro 85, 85100 Potenza, Italy.\par
\email{bonisoli@pzvx85.cineca.it}
\smallbreak
Neil Calkin, Department of Mathematics, Georgia Institute of Technology,
Atlanta, GA, 30332, U.S.A.\par
\email{calkin@math.gatech.edu}
\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
Zoltan F\"uredi, Department of Mathematics, University of Illinois at 
Urbana-Champaign, 1409 W Green St., Urbana, IL, 61801-2917, U.S.A.\par
\email{zoltan@symcom.math.uiuc.edu}
\smallbreak
Harald Gropp, Muehlingstra\ss e 19, D-6900 Heidelberg, Germany.
\smallbreak
Roland H\"aggkvist, Department of Mathematics, University of Ume\aa,
S-90187 Ume\aa, Sweden.
\smallbreak
A. J. W. Hilton, Department of Mathematics, University of Reading, 
Whiteknights, Reading, U.K.
\smallbreak
C. Hoede, Department of Applied Mathematics, University of Twente, P.O. 
Box 217, 7500AE Enschede, The Netherlands.
\smallbreak
Henry Martyn Mulder, Department of Mathematics, Erasmus Universiteit, 
Postbus 1738, 3000DR Rotterdam, The Netherlands.\par
\email{martyn@cvx.eur.nl}
\smallbreak
J. Ne\v set\v ril, KAM, Department of Applied Mathematics, Charles
University, Malostransk\'e n\'am.\ 25, 11800 Praha 1, Czechoslovakia.
\smallbreak
Alex Rosa, Department of Mathematics, McMaster University, Hamilton, 
Ontario, Canada L8S 4K1.\par
\email{rosa@sscvax.cis.mcmaster.ca}
\smallbreak
Ingo Schiermeyer, Lehrstuhl C f\"ur Mathematik, Technische Hochschule 
Aachen, Templergraben 55, W-5100 Aachen, Germany.
\smallbreak
M. K. Siu, Department of Mathematics, University of Hong Kong.\par
\email{mathsiu@hkucc.earn}
\smallbreak
Tom Trotter, Department of Mathematics, Arizona State University, Tempe,
AZ 85287-1804, U.S.A.\par
\email{iacwtt@asuacad.bitnet}
\smallbreak
Chris Wakelin, Department of Mathematics, University of Nottingham,
University Park, Nottingham NG7 2RD, U.K.
\smallbreak
Peter Yff, Department of Mathematical Sciences, Ball State University,
Muncie, IN 47306-0001, U.S.A.
\smallbreak
Dale Youngs, Racal Research Ltd., Worton Drive, Reading, Berks.
RG2 0SB, U.K.
\bigskip\bigskip
\line{\hfil Version of 3 September 1991}
\bye

