BCC Problem List

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

                     p.j.cameron@qmw.ac.uk

This document contains the problems presented at problem sessions at the British Combinatorial Conference, from BCC12 to the present. All those problems which were published in the Conference proceedings, and some others, are included. I have annotated and updated them with further references wherever I know of any. Further information on any of the problems are very welcome, and will be included in subsequent versions of the problems. The proposers’ addresses are the most recent known to me; again, updates are welcome.

From BCC13 onwards, the problems (together with the contributed papers) have been published in the Research Problems section of Discrete Mathematics. Each problem appearing in this section receives a unique number, which I have given in the form DMnnn.

BCC12

BCC12 was held at the University of East Anglia, Norwich, 3–7 July 1989. Contributed papers were published in Ars Combinatoria 29 (1990); the problems were not included.

Problem BCC12.1: Some doubly resolvable designs. Proposed by R. A. Bailey. Correspondent: R. A. Bailey.

For which n and k does there exist a doubly resolvable incomplete block design for nk treatments in n^{2} blocks of size k, so that all concurrences are 0 or 1?

Such a design exists if there are k MOLS of order n. What about other values? In particular, does it exist for (n, k) = (6, 3), (6, 4), (6, 5) or (10, 3)?

Editor’s Note: These designs are now known as SOMAs (see Phillips and Wallis [70]). For recent results on their structure and classification, including existence for (10, 3), see Soicher [80]. Further information on semi-Latin squares is available from [7].

Problem BCC12.2: Latin squares with transitive groups. Proposed by R. A. Bailey. Correspondent: R. A. Bailey.

Do there exist any Latin squares, other than Cayley tables, whose automorphism groups are transitive?

Problem BCC12.3: Two Diophantine equations. Proposed by Peter Cameron. Correspondent: Peter Cameron.

Let q, n, k be positive integers with q > 1, n > 3.

(a) Show that

\binom{k}{2} − 1 = \frac{q^{n} − 1}{q − 1}

has no solutions.

(b) Show that

\binom{k}{2} − 1 = q^{n} + 1

has only the solution q^{n} = 64, k = 12.

Remark: Richard Guy remarks that, for fixed n, these equations are presumably of the sort to which Faltings’ theorem applies, in which case there are only finitely many solutions for each n. But surely these equations are less difficult than Fermat’s last theorem!

Editor’s Note: Hering [47] has obtained further results on these equations, including the fact that the second equation has only finitely many solutions if q < 47 or if n is divisible by 3.

Problem BCC12.4: Generalised quadrangles. Proposed by J. Tits and P. J. Cameron. Correspondent: Peter Cameron.

Show that there is no generalised quadrangle with parameters s, t, where s is finite and greater than 1, and t is infinite.

Note: A generalised quadrangle is a geometry of points and lines, with any two points on at most one line, such that if point P is not on line L, then P is collinear with a unique point of L. It has parameters s, t if each line contains s + 1 points and each point lies on t + 1 lines. If s = 1, it is a complete bipartite graph. The finiteness of t when s = 2, 3 was shown by Cameron and Kantor respectively.

Editor’s Note: A simplified proof for the case s = 3 was given by Brouwer [14]. Finiteness in the case s = 4 was shown by Cherlin (unpublished), who gave a general method which can in principle deal with larger values of s (with ever-increasing amounts of hard labour).

Problem BCC12.5: Edge-density of infinite graphs. Proposed by Peter Cameron. Correspondent: Peter Cameron.

Let G be an infinite graph. List all labelled n-vertex subgraphs of G (a finite list, for each n), and let d_{n} be the average density of edges in the list (that is, the total number of edges divided by \binom{n}{2} times the number of graphs in the list. Does lim_{n→∞} d_{n} exist?

Problem BCC12.6: Intersecting families. Proposed by P. J. Cameron, P. Frankl and W. M. Kantor. Correspondent: Peter Cameron.

Let F ⊆ P({1, 2, …, n}) be an intersecting family of sets which is maximal (that is, |F| = 2^{n−1}) and regular (each point lies in the same number of elements of F). Let m be the size of the smallest set in F. It is known that m ≥ \frac{1}{2} log n + c; examples are known with m ∼ \sqrt{n}. (See [23]). What is the truth?

Editor’s Note: This problem has been solved by Aaron Meyerowitz [66], who showed that the lower bound is correct.

Problem BCC12.7: Forbidding divisibility. Proposed by P. J. Cameron and P. Erdős. Correspondent: Peter Cameron.

Let f(n) be the number of sequences

1 ≤ a_{1} < … < a_{t} ≤ n

with a_{i} |̸ a_{j} for i ≠ j. Prove that lim_{n→∞} f(n)^{1/n} exists.

Note: The limit should be about 1.58: see [22].

Problem BCC12.8: Inverting sign matrices. Proposed by Ömer Eğecioğlu. Correspondent: .

Consider two disjoint finite sets A and B, each partitioned into n^{2} not necessarily nonempty subsets A_{ij} and B_{ij} for i, j = 1, …, n, respectively. Suppose that we have a mapping sign : A ∪ B → {−1, 1}. Let

a_{ij} = ∑_{x∈A_{ij}} sign(x), b_{ij} = ∑_{y∈B_{ij}} sign(y).

In many combinatorial situations, the numbers a_{ij} and b_{ij} are given not explicitly but algorithmically.

Put

I_{ij} = ⋃_{k=1}^{n} A_{ik} × B_{kj}, I = ⋃_{i,j=1}^{n} I_{ij}.

Clearly I ⊆ A×B. Denote by x_{ij} and u_{ij} generic elements of A_{ij}, and by y_{ij} and v_{ij} elements of B_{ij}. We turn I into a signed space by defining, for every (x_{ik}, y_{kj}) ∈ I,

sign(x_{ik}, y_{kj}) = sign(x_{ik}) sign(y_{kj}).

Let A = ||a_{ij}||, and B = ||b_{ij}||, and suppose that AB = I. In many instances (for example, in the combinatorics of the transition matrices for symmetric function bases), one can provide a combinatorial proof of this fact (viz., AB = I) by means of a sign-reversing involution on I. That is, we can construct a permutation α on I satisfying

(i) α : I_{ij} → I_{ij};

(ii) if α(x_{ik}, y_{kj}) = (u_{il}, v_{lj}) ≠ (x_{ik}, y_{kj}), then sign(x_{ik}, y_{kj}) ≠ sign(u_{il}, v_{lj}) (that is, α is sign-reversing outside its fixed point set);

(iii) α has no fixed points in I_{ij} for i ≠ j, and a unique fixed point (with positive sign) in I_{ii} for each i;

α is an involution, that is, α^{2} is the identity.

Then it is easy to see, by using α, that

∑_{k=1}^{n} a_{ik}b_{kj} = δ_{ij},

where δ_{ij} is the Kronecker delta.

Since AB = I if and only if BA = I, it is natural to ask if BA = I admits a combinatorial proof via a sign-reversing involution β defined on

J = ⋃_{i,j=1}^{n} J_{ij},

where

J_{ij} = ⋃_{k=1}^{n} B_{ik} × A_{kj},

where β is constructed directly from α. We would also like the construction to be natural, in the sense that the map α → β itself should be an involution.

Problem: Give such a construction of β from α.

Problem BCC12.9: Subgraphs of the n-cube. Proposed by Paul Erdős. Correspondent: Paul Erdős.

Let Q_{n} denote the n-cube, a graph with n2^{n−1} edges.

(a) Show that a subgraph of Q_{n} with at least (\frac{1}{2} + ϵ)n2^{n−1} edges contains a C_{4}.

(b) Show that a subgraph of Q_{n} with at least ϵn2^{n−1} edges contains a C_{6}.

Of course, the assertion is to be shown for all sufficiently large n, for any given ϵ > 0. Each of these problems is worth $100.

Editor’s Note: Part (b) has been disproved by Conder [29], who partitioned the edge-set of Q_{n} into three C_{6}-free subsets. For up-to-date results on both problems, see Chung and Graham [27], p. 43.

Problem BCC12.10: Sum-free sets containing a small even number. Proposed by Paul Erdős. Correspondent: Paul Erdős.

Let S be a sum-free subset of {1, …, n} (that is, for all x, y, z ∈ S, x + y ≠ z). Clearly |S| ≤ ⌈\frac{1}{2}n⌉. Now suppose that S contains an even number less than \frac{1}{2}n − f(n). Is it true that |S| ≤ \frac{1}{2}n − ϵf(n)?

The hypothesis is clearly necessary: the set of odd numbers, and the set of numbers greater than \frac{1}{2}n, are both sum-free. It is known that, if 2 ∈ S, then |S| ≤ (\frac{2}{5} + o(1))n.

Editor’s Note: Deshouillers, Freiman, Sós and Temkin [31] have shown that a sum-free set S which contains an even number satisfies either |S| ≤ min(S) or |S| ≤ \frac{2}{5}(n + 2). More generally, they have given a description of all such sets satisfying |S| > \frac{2}{5}n−c with n > n_{0}(c) for fixed c.

Problem BCC12.11: Forbidding x + y = 4z. Proposed by Paul Erdős. Correspondent: Paul Erdős.

Let S be a set of positive integers containing no solution to x + y = 4z. Does S have lower density less than \frac{1}{2}?

Note that the set of integers congruent to 1 or 4 modulo 5 satisfies the constraint and has density \frac{2}{5}.

Problem BCC12.12: Sets with all subset-sums distinct. Proposed by Paul Erdős. Correspondent: Paul Erdős.

Let S be a subset of {1, …, n} with all sums of subsets distinct. Is it true that

|S| < \frac{log n}{log 2} + c?

It is known that |S| < \frac{log n}{log 2} + \frac{log log n}{2 log 2}, and that there is such a set with n = 2^{m} and |S| = m + 2. This problem is worth $500.

Problem BCC12.13: Some distance-regular graphs. Proposed by Tony Gardiner. Correspondent: Tony Gardiner.

Is there a distance-regular graph with diameter 3 having intersection array

( \begin{matrix}∗ & 1 & c & m \\ 0 & 0 & a & 0 \\ m & m − 1 & b & ∗ \end{matrix} )

with b ≠ 1, a ≠ 0?

The ith column of the intersection array gives the number of vertices adjacent to y and at distance i − 1, i, i + 1 respectively from x, where x and y are at distance i these numbers being (by definition) constant. The smallest such feasible graph has valency 126.

Problem BCC12.14: Determining a graph from its cycle space. Proposed by Oliver Pretzel. Correspondent: Oliver Pretzel.

Given a cycle basis of a graph G, one can view the cycles of G as elements of a free abelian group (or, if orientation is disregarded, of a vector space over ℤ/2). Many functions on the cycles are linear on this algebraic structure, but the length function (the number of edges in the cycle) is not. Informally, the question is: “how closely does the length function determine G?”

More formally, suppose that two graphs G and H are given with isomorphic cycle spaces. Suppose further that G is known and that, for suitable cycle bases, the length functions on the cycle spaces of G and H are the same. What can be said about H?

For example, if G is a tree, then H is a forest. If G is a cycle with two chords and H is 2-connected, then H is a cycle of the same length with two chords, but the chords can be moved slightly. So H need not be isomorphic to G.

Conjecture: If G and H are 3-connected and have the same length function for cycles, then G and H are isomorphic

Problem BCC12.15: A double Youden rectangle. Proposed by Donald A. Preece. Correspondent: Donald A. Preece.

Construct a 5 × 11 double Youden rectangle.

For the definition, see Bailey [5]. Briefly: what is required is a 5 × 11 rectangle, each cell containing a symbol from {a_{1}, …, a_{11}} and a symbol from {b_{1}, …, b_{5}}, such that

(i) the a’s form a Latin rectangle, and the sets of a’s appearing in the columns are the blocks of a symmetric (11, 5, 2) BIBD;

(ii) each b appears once in each column and once paired with each a;

(iii) For i ≠ j, the numbers of occurrences of b_{i} and b_{j} in any row differ by at most 1.

Of course, this definition is much less “symmetrical” than that in Bailey [5].

Editor’s Note: This problem has been solved by the proposer [71].

Problem BCC12.16: Monotone directed paths in tournaments. Proposed by V. Linek, B. Sands, N. Sauer and R. E. Woodrow. Correspondent: Bill Sands.

Problem 1: If the edges of a tournament are coloured with three colours, is there a set of three vertices such that there is a monochromatic directed path from any other vertex to one of these three?

It is known that, if only two colours are used, then a single vertex will suffice. For three colours, three vertices are necessary but it is not known whether any finite number is sufficient. See [76].

Problem 2: Let P be a poset, and colour the edges of a tournament with the elements of P. Call a directed path x_{1}, x_{2}, …, x_{k} monotone if

colour(x_{i}x_{i+1}) ≤ colour(x_{i+1}x_{i+2})

for all i. If P is the poset {|• • •}, is there a set of three vertices of T such that there is a monotone directed path from any other vertex of T to one of these three?

Again it is known that two vertices will not always do, but no fixed number is known to suffice. Problem 1 is just Problem 2 with P a 3-element antichain. Linek and Sands [62] have found all posets P for which a single vertex suffices; they are exactly those containing neither {• • •} nor {|• • •}.

Problem 3: Problem 2 can be generalised by replacing the poset P by a directed graph D, and replacing “monotone” paths by paths x_{1}, …, x_{k} such that

(colour(x_{i}x_{i+1}), colour(x_{i+1}x_{i+2})) is an edge of D

for all i. For example, if D = C_{5}, the undirected 5-cycle (with each edge directed both ways), is there always a vertex in any tournament reachable from all others by a D-path?

Problem BCC12.17: Independence numbers in non-Hamiltonian graphs. Proposed by Douglas R. Woodall. Correspondent: Douglas R. Woodall.

Let G be a k-connected graph with vertex independence number α(G).

Conjecture 1: If G is not Hamiltonian, C is a longest circuit in G, and k ≥ 2, then

α(G − C) ≤ α(G) − k.

Conjecture 2: If G is not traceable, P is a longest path in G, and k ≥ 1, then

α(G − P) ≤ α(G) − k − 1.

Here, G − C means the graph obtained by removing the vertices of C from G.

If true, both conjectures are best possible: let G be the union of a large number of complete graphs, all having exactly k vertices in common. Conjecture 2 is obvious if k = 1 (since the end vertices of P are not adjacent to each other or to anything outside P), and has been proved for k = 2, but is open for k ≥ 3, as is Conjecture 1 in all cases.

Problem BCC12.18: Zara graphs. Proposed by François Zara. Correspondent: François Zara.

A Zara graph is a graph with the properties that, for some natural numbers r and t,

(i) each maximal clique is of cardinality r;

(ii) if C is a maximal clique and x a vertex not in C, then x is adjacent to exactly t vertices in C.

Problems:

1. Find new Zara graphs.

2. A Zara graph with t = 2 is a special kind of “extended generalised quadrangle” (see [24]). Can these graphs be classified?

For further background, see [11, 89, 90].

Editor’s note: At the Second Franco-Chinese Conference on Counting and Coding, held at ENST, Paris, 6–8 September 1989, Tayuan Huang (Department of Applied Mathematics, National Chiao-Tung University, Hsin Chu 30050, Taiwan, ROC; thuang@twnctu01.bitnet) proposed a solution to Problem 1, involving a family of Zara graphs with r = q^{3}, t = q^{2} for any prime power q, constructed from alternating bilinear forms in 4 variables over GF (q). (Join two forms if their difference is singular.) Subsequently, it turned out that these are isomorphic to some of the known examples.

Of course, by definition, Problem 1 remains open!

Final note. Participants at the problem session will recall some discussion of a problem posed by Oliver Pretzel. Subsequently, a message reached me by an indirect route from Noga Alon, pointing out that the problem had been solved “decades ago” by Erdős and Selfridge. The proof is elegant, and participants may be interested in seeing it.

The problem was as follows. Let A and B be distinct finite sets of positive integers for which the multisets

A_{2} = {a + a′ : a, a′ ∈ A, a ≠ a′}, B_{2} = {b + b′ : b, b′ ∈ B, b ≠ b′}

coincide. Is it true that |A| = |B| is a power of 2?

Solution. Put f(x) = ∑_{a∈A} x^{a} and g(x) = ∑_{b∈B} x^{b}. Then

f(x)^{2} − f(x^{2}) = 2 ∑_{r∈A_{2}} x^{r},
g(x)^{2} − g(x^{2}) = 2 ∑_{s∈B_{2}} x^{s}.

Hence f(x)^{2} − f(x^{2}) = g(x)^{2} − g(x^{2}), that is, (f − g)(x)(f + g)(x) = (f − g)(x^{2}). Suppose that (f − g)(x) = (1 − x)^{k}P (x) where P (1) ≠ 0. Then

(f = g)(x) + \frac{(f − g)(x^{2})}{(f − g)(x)} = (1 + x)^{k} \frac{P (x^{2})}{P (x)}.

Put x = 1 to get

2|A| = (f + g)(1) = 2^{k} \frac{P (1)}{P (1)} = 2^{k},

so the answer is affirmative.

BCC13

BCC13 was held at the University of Surrey, Guildford, 8-12 July 1991. The contributed papers were published in Discrete Mathematics 125 (1994). The problems appear on pages 407–417 of the journal.

Problem BCC13.1 (DM178): Stable partitions of graphs. Proposed by Z. Füredi. Correspondent: Z. Füredi.

A partition of the vertex set V of a (simple) graph G into two non-empty parts V_{1} and V_{2} is called stable if, for i = 1, 2 and all vertices x ∈ V_{i},

deg_{G|V_{i}}(x) > \frac{1}{2} deg_{G}(x).

A graph with a stable partition is called 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)?

Problem BCC13.2 (DM179): Ramsey perfect graphs. Proposed by J. Nešetřil. Correspondent: J. Nešetřil.

Is it true that, for every perfect graph G, there exists a perfect graph H such that, for every partition E(H) = E_{1} ∪ E_{2}, there is an induced subgraph G′ of H such that G′ is isomorphic to G and E(G′) ⊆ 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ász Multiplication Lemma).

Problem BCC13.3 (DM180): Reconstructing spanning trees. Proposed by W. L. Kocay. Correspondent: C. Wakelin.

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

Problem BCC13.4 (DM181): 1 time 2-tough implies 2 times 1-tough?. Proposed by C. Hoede. Correspondent: C. Hoede.

Prove that the edge-set of a 2-tough graph 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 edgedisssjoint 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 is, for any vertex cutset Sm G − S has at most |S|/t components. Chvátal conjectured that, for t > \frac{3}{2}, a t-tough graph is Hamiltonian. This was refuted by Thomassen, who conjectured instead that a 2-tough graph is Hamiltonian.]

Problem BCC13.5 (DM182): Path-tough graphs. Proposed by I. Schiermeyer. Correspondent: I. Schiermeyer.

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

Problem BCC13.6 (DM183): Hamiltonian cycles and a bit more. Proposed by R. Häggkvist. Correspondent: R. Häggkvist.

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

Problem BCC13.7 (DM184): The second longest cycle. Proposed by R. Häggkvist. Correspondent: R. Häggkvist.

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

Problem BCC13.8 (DM185): 4-chromatic covering graphs. Proposed by D. Youngs. Correspondent: D. Youngs.

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

Problem BCC13.9 (DM186): Special Hamiltonian paths. Proposed by W. T. Trotter and S. Felsner. Correspondent: W. T. Trotter.

Consider the diagram of the poset of all subsets of {1, 2, …, n}. As a graph, this is the n-cube. Does the graph have a Hamiltonian path A_{1}, A_{1}, …, A_{2^{n}} starting at A_{1} = ∅ and having the following property?

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,

∅, 1, 12, 2, 23, 3, 34, 4, 24, 124, 14, 134, 13, 123, 1234, 234

is such a path.

Problem BCC13.10 (DM187): Interval-regular graphs. Proposed by H. M. Mulder. Correspondent: H. M. Mulder.

Let G be a connected simple graph. The interval I(u, v) between vertices u and v is the set of all vertices which lie on some shortest path form u to v. The graph is called interval-regular if, for any two vertices u and v, we have

||N(u) ∩ 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 [67].

Conjecture: Let G be interval-regular. Then

x, y ∈ I(u, v) ⟹ I(x, y) ⊆ I(u, v)

for any vertices u and v.

Problem BCC13.11 (DM188): Permutations of a cube. Proposed by M. K. Siu. Correspondent: M. K. Siu.

Let C be the n-cube graph, d the graph metric. Is every permutation of the vertices of c the composite of at most n permutations s_{i}, each satisfying

d(x, s_{i}(x)) ≤ 1

for all x ∈ C?

Editor’s Note: More generally, which graphs of diameter n have this property?

Note that it is not true that a permutation s he vertices of C which satisfies d(x, s(x)) ≤ k can be written as the product of at most k permutations s_{i} as above.

Problem BCC13.12 (DM189): Permutations of projective space. Proposed by A.Gyárfás. Correspondent: P. J. Cameron.

For which n and q does there exist a permutation π of the point set of P G(n, q) with the property that, for any hyperplane H, there exists a hyperplane H′ with π(H) ∩ H′ = ∅? 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).

Problem BCC13.13: q-polynomials. Proposed by A. Bonisoli. Correspondent: A. Bonisoli.

A polynomial c(z) = ∑ c_{i}z^{i} ovber GF (q) is said to be a q-polynomial if c_{i} ≠ 0 only if i is a power of q. (See [61].) Let m = 2^{d} −1 be a Mersenne prime. Does there exist a 2-polynomial

c(z) = ∑_{i=0}^{d} x_{i}z^{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.

Problem BCC13.14 (DM190): Cyclic shifts of binary words. Proposed by P. J. Cameron. Correspondent: P. J. Cameron.

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 U of W_{n} such that the union of all cyclic shifts of U is equal to W_{n}. It is known that f(n) ≥ 2 for n > 3, but little more is known. Does f(n) → ∞ as n → ∞? Or is f(n) = 2 for infinitely many n?

Problem BCC13.15 (DM191): A generalisation of arcs. Proposed by J. Bierbrauer. Correspondent: J. Bierbrauer.

Let (V, B) be an affine plane of odd order q. Given a function w : V → ℤ such that

∑_{p∈L} w(p) ≤ 2

for all L ∈ B, set

mass(w) = ∑_{p∈V} w(p).

Then mass(w) ≤ q + 2 holds. The value q + 1 can be attained (by the characteristic function of a conic). Prove that necessarily mass(w) ≤ q + 1.

Problem BCC13.16 (DM192): Perfect Steiner triple systems. Proposed by C. J. Colbourn and A. Rosa. Correspondent: A. Rosa.

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

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.

Problem BCC13.17 (DM193): A generalisation of affine designs. Proposed by P. J. Cameron and M. E. Kimberley. Correspondent: P. J. Cameron.

An affine design is a resolvable 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 affine designs, there are resolvable designs with λ = 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. See [19].

Problem BCC13.18 (DM194): Blocking-set-free configurations. Proposed by J. W. DiPaola and H. Gropp. Correspondent: H. Gropp.

A configuration n_{3} has n points and n lines, with three points on each line and three lines through each point, so that two points lie on at most one line. A blocking set is a set of points meeting every line but containing none. For which n ≥ 7 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 falues 8–12 or 14. The values in doubt are 15–18, 20, 23, 24, 26, 29, 30, 32, 38, 44. See [33].

Editor’s Note: See also BCC14.14 and BCC16.20.

Problem BCC13.19 (DM195): Permutations with few distances. Proposed by P. J. Cameron. Correspondent: P. J. Cameron.

For fixed s and large n, the best known upper and lower bounds for the maximum number of permutations of an n-set with s different distances are both roughly (cn/s)^{2s} (with different values of c). (See [18].) Find the correct value.

Problem BCC13.20 (DM196): Partial transversals of Latin rectangles. Proposed by A. J. W. Hilton. Correspondent: A. J. W. Hilton.

Let R be an n × 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 × 2n Latin rectangles R, S on the same set of symbols orthogonal if the pairs (r_{ij}, s_{ij}), for i = 1, …, n and j = 1, …, 2n, are all distinct. Does every n × 2n Latin rectangle have an orthogonal mate?

Problem BCC13.21 (DM197): Semi-Latin squares. Proposed by R. A. Bailey. Correspondent: R. A. Bailey.

A semi-Latin square is an n × n array with k symbols (chosen from a set of size nk) in each cell, such that each symbol occurs once in each row or column. We impose the further property:

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 disjoint 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) or (10, 3)?

Editor’s Note: See comments on BCC12.1 above.

Problem BCC13.22 (DM198): Tiling the square. Proposed by D. Youngs. Correspondent: D. Youngs.

(a) What is the least 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.

Problem BCC13.23 (DM199): Covering the square. Proposed by F. Barnes. Correspondent: F. Barnes.

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

(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 ≤ 5. In general, we would expect a hexagonal honeycomb with some distortion at the edges.

An alternative formulation of (b) 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.

Problem BCC13.24 (DM200): Sum-free sets containing 2. Proposed by P. J. Cameron. Correspondent: N. J. Calkin.

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 ∉ S; otherwise, decide on the toss of a fair coin. It is known that the probability that S contains no even number is non-zero, but the present problem seems a bit more delicate.

Editor’s Note: This problem has been solved by the proposer and the presenter [16], who showed that the probability is strictly positive and gave a heuristic estimate for it.

Problem BCC13.25 (DM201): Partitions of intersecting families. Proposed by N. Alon, P. Seymour and Z. Füredi. Correspondent: Z. Füredi.

Let F be an intersecting family of k-subsets of the n-element set V, that is, F ∩ F′ ≠ ∅ for all F, F′ ∈ F. Let p(F) be the minimum p for which one can find p pairs (2-subsets) P_{!}, …, P_{p} of V such that every member of F contains some P_{i}. Now let f(n, k) be the maximum of p(F), over all such intersecting families. Is it true that f(n, k) ≤ n for all n?

If true, this would imply a strengthened form of the case t + 1 of Larman’s conjecture, since, setting

F_{i} = {F ∈ F : p_{i} ⊆ F, P_{j} ⊈ F for j < i},

then {F_{i} : i = 1, …, n} is a decomposition of F into 2-intersecting families.

(Larman’s conjecture [59] asserts that, if F is a t-intersecting family of k-subsets of the n-set V, that is, |F ∩ F′| ≥ t for all F, F′ ∈ F, then F can be decomposed into n subfamilies each of which is (t + 1)-intersecting.

Editor’s note: A similiar question can be asked for arbitrary families of sets (not all of the same size).

Problem BCC13.26 (DM202): Some families of sets. Proposed by N. J. Calkin. Correspondent: N. J. Calkin.

What can be said about families F of subsets of an n-set V such that

(a) F_{1}, F_{2} ∈ F ⟹ F_{1} ⊄ F_{2};

(b) F_{1}, F_{2} ∈ F ⟹ F_{1} ∩ F_{2} ≠ ∅;

(c) (∀x ∈ V)(∃F_{1}, F_{2} ∈ F)(F_{1} ∩ F_{2} = {x})?

Problem BCC13.27 (DM203): Some problems on perfect groups. Proposed by J. Dénes and P. Yff. Correspondent: P. Yff.

(a) Prove the Feit–Thompson Theorem by elementary means. (Remark: either of the following equivalents of the Feit–Thompson Theorem may be more convenient:

• A finite perfect group can be generated by a self-inverse conjugacy class of elements of odd order (Heineken, unpublished);

• If G has odd order n, then some element of G is not the product of n distinct factors (Dénes and Hermann [32]).)

(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 finite simple group has this peroperty (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 kconjugacy (Yff [87]).

BCC14

BCC14 was held at the University of Keele, 5–9 July 1993. The contributed papers were published in Discrete Mathematics 138 (1995). The problems appear on pages 405–411 of the journal.

Problem BCC14.1 (DM215): Total colourings of hypergraphs. Proposed by P. Cowling. Correspondent: P. Cowling.

A total colouring of a hypergraph is a colouring of vertices and edges such that

(a) the restrictions to vertices and edges are strong colourings;

(b) an incident vertex and edge have different colours.

The total chromatic number is the least number of colours required for a total colouring. See [30].

Conjecture: If H = (V, E) is a linear hypergraph (two vertices on at most one edge) with total chromatic number χ_{T} (H), then

χ_{T} (H) ≤ max_{x∈V} | ⋃_{{E∈E \atop x∈E}} E| + 1.

Problem BCC14.2 (DM216): Critical K_{l}-free graphs. Proposed by J. Schöhheim. Correspondent: J. Schöhheim.

It is known that k-chromatic critical graphs on n vertices have at least (\frac{k − 1}{2}) 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 ≤ l ≤ k?

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

Problem BCC14.3 (DM217): Bandwidth of a graph. Proposed by D. B. West. Correspondent: D. B. West.

The bandwidth of an n-vertex graph G is

min_{f} max_{x∼y} |f(x) − f(y)|,

where the minimum is over all bijections from the vertex set to {1, …, n}.

What is the bandwidth of the “triangular lattice” graph whose vertices are all 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 in layers.)

Editor’s Note: This problem was solved immediately after the conference. The solution [49] appears in the volume of contributed papers.

Problem BCC14.4 (DM218): How small is Tutte’s wheel?. Proposed by A. Shastri. Correspondent: A. Shastri.

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

Conjecture. Any 3-connected cubic graph on n vertices may be obtained by this procedure from a wheel on k vertices, where k ≥ cn (for some absolute constant c).

Problem BCC14.5 (DM219): Characteristic polynomials of graphs. Proposed by R. Häggkvist. Correspondent: R. Häggkvist.

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^{2}n!).

Problem BCC14.6 (DM220): Cliques and cocliques in Cayley graphs. Proposed by N. Alon. Correspondent: N. Alon.

Conjecture. There is a constant c such that, for every finite group G of order n > 1, there is a symmetric (i.e., inverse-closed) generating set S for G such that the Cayley graph Γ(G, S) has neither a clique nor an 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.

Problem BCC14.7 (DM221): Local structure in 2-transitive graphs. Proposed by A. A. Ivanov. Correspondent: A. A. Ivanov.

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}⟨t⟩ = G(e), where e = {x, y}), along with the trivial possibility that G(e) = H_{y} × 2.)

Problem BCC14.8 (DM222): The rows of a Latin square. Proposed by P. J. Cameron and J. C. M. Janssen. Correspondent: P. J. Cameron.

(a) It is known that, for almost all Latin squares of order n (that is, a proportion tending to 1 as n → ∞), 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?

(b) Is it true that the distribution of the number of rows of a random Latin square which are odd permutations is “approximately” binomial B(n, \frac{1}{2})?

(c) Let M(n) and m(n) denote the maximum and minimum numbers of extensions of a 2×n Latin rectangle to an n × n Latin square. Find a good upper bound for M(n)/m(n).

(d) How do you choose a random Latin square of order n?

Editor’s Note: In connection with (b), Häggkvist and Janssen [44] have shown that the proportion of Latin squares in which all rows are even permutations is exponentially small. This was the form asked at the Conference; the strengthened version was suggested by Jeannette Janssen.

A Markov chain method for choosing a random Latin square was given by Jacobson and Matthews [50].

Problem BCC14.9 (DM223): A bijective proof of the Dyson conjecture. Proposed by R. Lewis. Correspondent: R. Lewis.

Let R(r, m, n) denote the set of partitions of n whose rank is congruent to r modulo m, where the rank of a partition is the largest part minus the number of parts. Freeman Dyson conjectured, and Atkin and Swinnerton-Dyer [4] proved, that

|R(0, 5, 5n + 4)| = |R(1, 5, 5n + 4)| = … = |R(4, 5, 5n + 4)|.

The problem is to find a bijective proof.

Problem BCC14.10 (DM224): Even and odd permutations. Proposed by P. J. Cameron. Correspondent: P. J. Cameron.

For even n, the number of permutations of {1, …, n} with all cycles of even length is equal to the number of permutations with all cycles of odd length. Find a bijective proof of this fact.

Editor’s Note: After the conference, this problem was solved independently by Richard Lewis and Simon Norton. Their joint paper [60] appears in the volume of contributed papers.

Problem BCC14.11 (DM225): How many sum-free sets?. Proposed by P. J. Cameron and P. Erdős. Correspondent: P. J. Cameron.

Let s(n) be the number of sum-free subsets of {1, …, n} (that is, containing no solution to x + y = z). Show that there exist constants c_{o} and c_{e} such that s(n)/2^{n/2} → c_{o} or c_{e} as n → ∞ through odd or even values respectively.

It is known only that s(n) = 2^{( \frac{1}{2} +o(1))n}: see [2, 15].

Editor’s Note: For the motivation, and conjectured values of the constants c_{e} and c_{o}, see [22].

Problem BCC14.12 (DM226): Non-crossing queens. Proposed by G. B. Khosrovshahi. Correspondent: G. B. Khosrovshahi.

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

Problem BCC14.13 (DM227): Block-transitive designs. Proposed by P. J. Cameron and C. E. Praeger. Correspondent: P. J. Cameron.

A t-(v, k, λ) design has v points and a collection of blocks of size k, any t points lying in exactly λ blocks. Terms such as “block-transitive” apply to the action of the automorphism group.

(a) Show that there is no block-transitive 6-design.

(b) Show that a block-transitive, point-imprimitive 3-design satisfies v ≤ \binom{k}{2} + 1.

(c) Is there a block-transitive 2-(∞, 4, 1) design which is not point-transitive?

Editor’s Note: For background to (a) and (b) see [25, 26]. The design asked for in (c) has been constructed by David Evans [36].

Problem BCC14.14 (DM228): Blocking-set-free configurations. Proposed by J. W. DiPaola and H. Gropp. Correspondent: H. Gropp.

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 blocking set is a set of points meeting every line but containing none. For which n ≥ 7 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 [33].

Editor’s Note: This problem an updated form of BCC13.18. See also BCC16.20.

Problem BCC14.15 (DM229): Arranging rows and columns. Proposed by D. B. West. Correspondent: D. B. West.

A matrix of zeros and ones is said to be “zero-partitionable” if its rows and columns can be permuted independently so that the zeros of the resulting matrix can be labeled R or C such that • every position to the right of an R is a 0 labeled R, and

• every position below a C is a 0 labeled C.

What is the complexity of recognizing zero-partitionable matrices?

This is equivalent to recognition of interval digraphs. If a 0 is allowed to receive both R and C, this becomes recognition of digraphs with Ferrers dimension 2, which runs in polynomial time.

BCC15

BCC15 was held at the University of Stirling, 3-7 July 1995. The contributed papers were published in Discrete Mathematics 167/168 (1997). The problems appear on pages 605–615 of the journal.

Problem BCC15.1 (DM271): A generalization of Hadwiger’s conjecture. Proposed by Ding, Oporowski, Sanders, and Vertigan. Correspondent: D. P. Sanders.

A vertex partition of G is a set {A_{1}, …, A_{k}} of induced subgraphs such that V (G) is the disjoint union V (A_{1}) ∪ … ∪ V (A_{k}).

Conjecture: Every graph with no K_{n} minor has a vertex partition into n − m + 1 graphs with no K_{m} minor.

For m = 2, this is Hadwiger’s conjecture. It is known to be true for n ≤ 5 (Wagner [83]; Ding, Oporowski, Sanders, Vertigan); for n = 6, m = 2 (Robertson, Seymour, Thomas [74]), and for 6 ≤ n ≤ 8, m = 3 (Jørgensen [51]).

Problem BCC15.2 (DM272): Uniquely total colourable graphs. Proposed by M. Behzad and E. S. Mahmoodian. Correspondent: E. S. Mahmoodian.

A total colouring of a graph is a colouring of the vertices and edges in such a way that no two adjacent or incident elements have the same colour.

Problem: Show that, apart from empty graphs, paths, and cycles C_{3k}, there is no graph which has a unique total colouring (in the minimum number of colours).

A prize of 500000 Iranian rials is offered for this problem. See [64].

Problem BCC15.3 (DM273): 1-track-less orientations. Proposed by Jörg Zuther. Correspondent: Jörg Zuther.

A 1-track is a one-way infinite directed path (which may be directed either in or out).

Problem: Characterize those graphs which admit a 1-track-less orientation.

Note that every locally finite graph, and every m-partite graph (for finite m) has a 1track-less orientation, but the countable complete graph does not.

Problem BCC15.4 (DM274): Continuous maps between graphs. Proposed by Anthony Hilton. Correspondent: Anthony Hilton.

A map is k-to-1 if the inverse of every point in the codomain has cardinality k. See [48].

Problem: Determine the triples (k, m, n) for which there is a k-to-1 continuous map from K_{m,m} to K_{n,n}, where these graphs are regarded as 1-dimensional simplicial complexes in the usual way (with edges homeomorphic to [0, 1]).

Problem BCC15.5 (DM275): A generalization of Tarsi’s problem. Proposed by R. Klein and J. Schönheim. Correspondent: J. Schönheim.

A graph is m-degenerate if every subgraph has a vertex of valency at most m.

Problem: Prove or disprove that a graph which is the edge-disjoint union of subgraphs G_{1}, …, G_{s}, where G_{i} is m_{i}-degenerate, can be coloured with

∑_{i=1}^{s} m_{i} + ⌊\frac{1}{2} (1 + \sqrt{1 + 8 ∑_{1≤i<j≤s} m_{i}m_{j}})⌋

colours.

For s = 2, m_{1} = 1, m_{2} = 2, this is M. Tarsi’s problem [55].

Problem BCC15.6 (DM276): Common vertices on longest paths. Proposed by T. Gallai. Correspondent: Sandi Klavžar.

Let G be a finite connected graph. Do any three longest paths in G have a common vertex? It is trivially true that every two longest paths have a common vertex; but there are graphs in which no vertex lies on all the longest paths. (The problem is due to Gallai [39]; see also [88, 54]

Problem BCC15.7 (DM277): Edge-colourings of complete graphs. Proposed by Peter Johnson. Correspondent: Peter Johnson.

Suppose that the edges of the complete graph K_{n} (n > 1) are coloured with four colours R, G, B, Y such that each colour-class gives a connected subgraph on n vertices. It is easy to see from Satz 1.2(3) of Gallai [38] that at least three of the four triangles with edge colourings RGB, RGY, RBY, GBY occur.

Questions:

• (a) Do all four occur?

• (b) If not, how small can n be?

• (c) What happens with more than four colours?

Problem BCC15.8 (DM278): On the probability of connectedness. Proposed by P. J. Cameron. Correspondent: P. J. Cameron.

Which graphs G have the property that, in the class X (G) of graphs having no induced subgraph isomorphic to G, the limiting probability of connectedness is strictly between zero and one (in either the unlabelled or the labelled case)? (The smallest G with this property is the path of length 3; the probability of connectedness in X (G) is \frac{1}{2} if the number of vertices is greater than one.)

Editor’s Note: See [9] for more information.

Problem BCC15.9 (DM279): Characteristic and chromatic polynomials. Proposed by Roland Häggkvist. Correspondent: Roland Häggkvist.

The characteristic polynomial of a graph G is the polynomial det(xI −A(G)), where A(G) is the adjacency matrix of G. Its roots are the eigenvalues of G.

Question: Are there more characteristic polynomials than chromatic polynomials of graphs on n vertices?

Editor’s Note: See also BCC14.5.

Problem BCC15.10 (DM280): Graphs with three eigenvalues. Proposed by Willem Haemers. Correspondent: Willem Haemers.

Let G be a connected graph with just three distinct eigenvalues. Such a graph, if regular, must be strongly regular; and any strongly regular graph has this property. Non-regular examples include the complete bipartite graphs, and one further example on 36 vertices constructed by M. Muzychuk.

Questions:

(a) Is it true that G has at most two distinct valencies?

(b) Is G switching-equivalent to a null or strongly regular graph?

(c) Find more examples.

(The operation of switching a graph with respect to a set X of vertices replaces each edge from X to its complement by a non-edge and each such non-edge by an edge, leaving edges within or outside X unaltered.)

Editor’s Note: M. Klin and M. Muzychuk [68] have pointed out that a family of examples were found in 1981 by Bridges and Mena [13], and have also constructed some ‘sporadic’ examples and re-formulated and analysed the question.

Problem BCC15.11 (DM281): Spectra of K_{s+1}-free graphs. Proposed by Stephan Brandt. Correspondent: Stephan Brandt.

Let λ_{1} and λ_{n} be the greatest and smallest eigenvalues of a graph on n vertices.

Conjecture: (λ_{1} + λ_{n})/n ≤ 4/25 for any regular triangle-free graph on n vertices.

This conjecture would be true if any of the following two old Erdős conjectures holds (see e.g. [34]): Let G be a triangle-free graph on n vertices. Then (a) G contains a set of ⌊n/2⌋ vertices which span at most n^{2}/50 edges, and (b) G can be made bipartite by the omission of at most n^{2}/25 edges.

Problem: Let ξ(s) be the supremum of (λ_{1} +λ_{n})/n over the class of regular K_{s+1}-free graphs on n vertices. Determine or estimate ξ(s).

The author [12] can show that

0.14 ≤ ξ(2) ≤ 3 − 2\sqrt{2} = 0.1715 …
(s − 2)/s ≤ ξ(s) ≤ (s − 2)/(s − 1)  for s ≥ 3.

Problem BCC15.12 (DM282): Semiregular automorphism groups. Proposed by Dragan Marušič, Mikhail Klin. Correspondent: Mikhail Klin.

A permutation group is semiregular if no non-identity group element fixes a point. It is regular if it is transitive and semiregular. A graph is a Cayley graph if and only if its automorphism group contains a regular subgroup. It is known that there are vertex-transitive graphs which are not Cayley graphs (the smallest such being the Petersen graph.)

Question: Is there a vertex-transitive graph whose automorphism group contains no nonidentity semiregular subgroup?

More generally, is there a 2-closed transitive permutation group containing no non-identity semiregular subgroup? (A permutation group is 2-closed if it is the automorphism group, preserving the colours, of some edge-coloured directed graph.)

Editor’s Note: Not every transitive permutation group contains a non-identity semiregular subgroup: the smallest counterexample has degree 12 (see [68]). Recently, Giudici [40] has determined all the quasiprimitive permutation groups which contain no non-identity semiregular subgroup; none of them is 2-closed.

Problem BCC15.13 (DM283): A distance-regular graph. Proposed by Leonard Soicher. Correspondent: Leonard Soicher.

Let C_{22} be the code obtained by puncturing the non-extended binary Golay code C_{23} in one coordinate. Then C_{22} is a [22, 12, 6] code with automorphism group M_{22} : 2. Let M be the set of words of minimum non-zero weight in C_{22}, so that |M| = 77.

Let V be the set of pairs {v_{1}, v_{2}} of words of C_{22} which satisfy wt(v_{1}) = wt(v_{2}) and v_{1} + v_{2} = 1, where 1 is the all-1 word. Then |V | = 672. For v = {v_{1}, v_{2}} ∈ V, define

M(v) = {m ∈ M| wt(v_{1} + m) = wt(v_{2} + m)}.

Then |M(v)| = 55 for all v ∈ V.

Define a graph Γ with vertex set V, in which v ∼ w if and only if |M(v) ∩ M(w)| = 43. Then Γ is a distance-regular, but not distance-transitive graph. Moreover, the distance function in Γ is given by

d_{Γ}(v, w) = \frac{1}{4}(47 − |M(v) ∩ M(w)|)

for v, w ∈ V, v ≠ w.

These facts have been proved using the package GRAPE (see [79]).

Problem:

(a) Prove this by hand, to help understand Γ.

(b) Can a similar construction be applied to other codes with even length and minimum weight, to construct other distance-regular graphs?

Problem BCC15.14 (DM284): Pasch configurations in 3-hypergraphs. Proposed by G. B. Khosrovshahi. Correspondent: G. B. Khosrovshahi.

Let X = {1, 2, …, v}. Denote the set of all 3-subsets of X by P_{3}(X). Show that for v ≥ 6, any (\binom{v}{2}+1)-subset of P_{3}(X) must contain a Pasch configuration, that is, \{abc, axy, bxz, cyz\} for some a, b, c, x, y, z ∈ X.

Editor’s Note: A. Blokhuis (personal communication) has constructed hypergraphs with more than \binom{v}{2} + 1 edges with no Pasch configuration. The question should be modified to read: how many edges can a hypergraph with no Pasch configuration have?

Problem BCC15.15 (DM285): Critical sets in Latin squares. Proposed by Ebad Mahmoodian. Correspondent: Ebad Mahmoodian.

A critical set in an n × n array with entries from the set {1, …, n} is a set S of the positions of the array with the property that the entries in the positions of S have a unique extension to a Latin square of order n.

Problem: Show that any critical set in a Latin square of order n has cardinality at least ⌊n^{2}/4⌋.

Problem BCC15.16 (DM286): Loops with conditions on area. Proposed by Alain Valette. Correspondent: Alain Valette.

A loop γ is a closed trajectory in the square lattice. Its algebraic area is A(γ) = ∮_{γ} xdy. Let N(2k; P) be the number of loops based at 0, of length 2k, which satisfy property P. So, for example, N(2k; ∅) = \binom{2k}{k}^{2}.

Problem: Find either formulae or asymptotics for N(2k; A = l) and N(2k; A ≡ l (mod q)), for given l, q.

For example, lim_{k→∞} N(2k; A = 0)^{1/2k} = 4. Also, if n(2k, l, q) denotes N(2k; A ≡ l (mod q)), then it is known that

lim_{k→∞}(n(2k; 0, 2) − n(2k; 1, 2))^{1/2k} = 2\sqrt{2},

lim_{k→∞}(n(2k; 0, 3) − n(2k; 1, 3))^{1/2k} = 1 + \sqrt{3},

lim_{k→∞}(n(2k; 0, 4) − n(2k; 2, 4))^{1/2k} = 2\sqrt{2}.

This problem (secretly) deals with the walk generating function of the discrete Heisenberg group in its 2-generator presentation.

Problem BCC15.17 (DM287): Proof of an identity. Proposed by Richard Lewis. Correspondent: Richard Lewis.

For complex numbers z ≠ 0, |w| < 1, set [z; w] = ∏_{n=1}^{∞}(1 − zw^{n−1})(1 − z^{−1}w^{n}). It can be shown, using Cauchy’s theorem, that for any non-zero complex numbers a_{1}, …, a_{n}, b_{1}, …, b_{n} with a_{1} … a_{n} = b_{1} … b_{n}, and any q with |q| < 1,

∑_{r=1}^{n} \frac{[a_{1}b_{r}^{−1}; q][a_{2}b_{r}^{−1}; q] … [a_{n}b_{r}^{−1}; q]}{[b_{1}b_{r}^{−1}; q][b_{2}b_{r}^{−1}; q] … ˆ … [b_{n}b_{r}^{−1}; q]} = 0,

where the ˆ means to omit the term [b_{r}b_{r}^{−1}; q].

Problem: Find a combinatorial (bijective) proof of this inequality.

Problem BCC15.18 (DM288): Counting classes of graphs. Proposed by Peter Cameron. Correspondent: Peter Cameron.

Find good asymptotic estimates for the numbers of

(a) line graphs,

(b) line graphs of bipartite graphs,

(c) comparability graphs of 2-dimensional posets

on n vertices? (The last class of graphs are defined as follows: Take a permutation π of {1, …, n}, and join i to j whenever (i − j)(iπ − jπ) > 0.)

Problem BCC15.19 (DM289): Antichains in products of chains. Proposed by Jonathan D. Farley. Correspondent: Jonathan D. Farley.

Let θ(P) be the set of antichains of the poset P, and let \underline{n} be the n-element chain. Dedekind’s problem [56] asks for the value of |θ(\underline{2}^{n})|. It is easy to show that |θ(\underline{n})| = n + 1 and |θ(\underline{m} × \underline{n})| = \binom{m+n}{m}. MacMahon, Stanley [81, 82], Berman and Köhler [10] showed that

|θ(\underline{k} × \underline{m} × \underline{n})| = ∏_{j=0}^{k−1} \binom{m + n + j}{m}/\binom{m + j}{m}.

(Despite appearances, this function is symmetric!)

Problem: What is |θ(\underline{j} × \underline{k} × \underline{m} × \underline{n})|?

Problem BCC15.20 (DM290): Cycles of a permutation. Proposed by Peter Cameron. Correspondent: Peter Cameron.

As an example of a “typical” automorphism of the space of periodic integrable functions (acting on Fourier coefficients), W. Rudin [75] considered the permutation of the integers defined by

3n ↦ 2n,  3n + 1 ↦ 4n + 1,  3n − 1 ↦ 4n − 1.

Problem: Describe the cycles of this permutation. In particular, does it have only finitely many finite cycles?

Editor’s Note: This problem is older: it is the “original Collatz problem” from the 1930s (before the famous 3x + 1 problem), though never published by him. A paper by Jeff Lagarias [58] gives details.

Problem BCC15.21 (DM291): Combinatorics and control theory. Proposed by Holger Schellwat. Correspondent: Holger Schellwat.

In place of the Laplace transform, which is used to model continuous time control systems, in discrete control the Z-transform is the basic tool. For a function f : ℤ → ℂ, its Z– transform is defined by Z(f)(z) = ∑_{k=0}^{∞} f(k)z^{−k}. One problem, for example, is the stability of an inert linear controller and is determined by the loci of poles of a fraction of polynomials in ℝ[x], constituting the Z-transform of the transfer function [3]. On the other hand, the method of generating functions [84] is used widely in combinatorics to solve enumeration problems. If (a_{i} : i ∈ ℕ) is a sequence of numbers, for instance counting the number of distinct combinatorial objects of a certain kind, its associated ordinary generating function is the formal power series ∑_{n=0}^{∞} a_{n}z^{n}. But up to the sign of the exponent, this is the defining sum for the Z-transform of the sequence, viewed as a function. Thus it seems natural to explore the implications of this correspondence. Is it even possible to use it to translate problems in control theory into problems in combinatorics and/or vice versa? Could representation theory help to establish such a correspondence?

BCC16

BCC16 was held at Queen Mary and Westfield College, London, 7-11 July 1997. The contributed papers were published in Discrete Mathematics 197/198 (1999). The problems appear on pages 799–812 of the journal.

Problem BCC16.1 (DM315): Hamiltonian planar cubic graphs. Proposed by S. Jendrol’ and Z. Skupień. Correspondent: S. Jendrol’.

Let G be a cubic bipartite 3-connected planar graph whose edge set E(G) can be partitioned into three subsets E(G) = E_{1} ∪ E_{2} ∪ E_{3} such that ⟨E_{1}⟩ and ⟨E_{2}⟩ are trees and ⟨E_{3}⟩ is a cycle. Prove that G is hamiltonian.

Remark: This is true if E_{2} is empty (Halin) or if E_{2} consists of a single edge (Skupień).

Problem BCC16.2: Quasi Hamiltonian-Connected Graphs. Proposed by M. Alabdullatif. Correspondent: M. Alabdullatif.

Consider a Hamiltonian graph with the following property: for each pair {u, v} of nonadjacent vertices, there exists a hamiltonian path joining u and v. Call such graph quasi hamiltonian-connected (QHc).

Unlike a hamiltonian-connected graph, a QHc graph may have connectivity 2. It has been shown that a k-regular QHc graph is necessarily 3-connected for k = 3 or 4 (see [1]).

Problem: Let G be a k-regular QHc graph (k = 3 or 4). Is G necessarily hamiltonianconnected?

The proposer checked the case when G is of order less than or equal to 10, and it turned out that G is hamiltonian-connected.

Remark: Counterexamples to this problem, both for k = 3 and for k = 4, have been found by Gunnar Brinkmann. The smallest counterexample has 16 vertices. (This information is from Stefan Brandt.)

Editor’s Note: In the preliminary version, the proposer asked whether a 3-connected kregular QHc graph is necessarily hamiltonian-connected? A negative answer was given by Stefan Brandt at the conference. He constructed, for each k, a k-connected, (2k − 1)-regular graph which is QHc but not hamiltonian-connected.

Problem BCC16.3 (DM316): A condition for pancyclicity. Proposed by Uwe Schelten and Ingo Schiermeyer. Correspondent: Ingo Schiermeyer.

The k-closure C_{k}(G) of a graph G was defined by Bondy and Chvátal (1976): recursively join all pairs of non-adjacent vertices whose degrees have sum at least k. They showed that, for an n-vertex graph G,

If C_{n}(G) = K_{n} then G is Hamiltonian.

Faudree, Flandrin, Favaron and Li (1992) showed that

If C_{n+1}(G) = K_{n} then G is pancyclic.

The examples G = K_{n/2,n/2} (and many others) show that it is not true that if C_{n}(G) = K_{n} then G is pancyclic.

Conjecture: If C_{n}(G) = K_{n} and n is odd then G is pancyclic.

Problem BCC16.4 (DM317): Cutsets in bridged graphs. Proposed by Geña Hahn. Correspondent: Geña Hahn.

A graph G is bridged if every cycle of length of at least 4 has a bridge, that is, if every cycle C of length 4 contains two vertices u and v such that d_{G}(u, v) < d_{C}(u, v) (distance).

Conjecture: For any pair of vertices u, v in a minimum cutset in a bridged graph G, d_{G}(u, v) ≤ 2.

Problem BCC16.5 (DM318): 4-cycles in regular spanning subgraphs. Proposed by Ian Wanless. Correspondent: Ian Wanless.

Let n and k be integers satisfying n ≥ 2k. Let G be a k-regular spanning subgraph of K_{n,n} and let s(G) be the number of 4-cycles in G. Suppose that G is chosen to maximise s(G).

Conjecture: G contains K_{k,k} as a component.

Notes: The conjecture is easily proved if

(1) k divides n, or

(2) n is sufficiently large.

If it is true in toto, then G is determined up to isomorphism. This follows from the fact that if G maximises s(G) then s(\overline{G}) is also maximised, where \overline{G} denotes the bipartite complement of G.

A weaker result along the same lines would be to show that G is necessarily disconnected.

Problem BCC16.6 (DM319): Alternating cycles in 2-arc-coloured tournaments. Proposed by G. Gutin, B. Sudakov and A. Yeo. Correspondent: Gregory Gutin.

A cycle C in a 2-arc-coloured digraph is alternating if any two consecutive arcs in C have different colours.

Problem: Does there exist a polynomial algorithm to check whether a 2-arc-coloured tournament has an alternating cycle?

The same problem for 2-arc-coloured digraphs has been proved to be NP-complete.

Problem BCC16.7 (DM320): Monochromatically absorbing sets in tournaments. Proposed by Geña Hahn. Correspondent: Geña Hahn.

Call a set S of vertices in an edge-coloured tournament monochromatically absorbing if, from any u ∈ V (D) \ S there is a monochromatic directed path from u to S.

It follows from a theorem of Sands, Sauer and Woodrow [76] that any tournament not containing a ray (directed infinite path) whose arcs are coloured in two colours contains a vertex v such that {v} is monochromatically absorbing.

Problems:

(i) Is there a function f : ℕ → ℕ such that in any tournament without a ray, edge-coloured in k colours, there is a monochromatically absorbing set of size at most f(k)? (It is known that if such a function exists, then f(3) ≥ 3.)

(ii) Shen has shown that in a 3-arc-coloured finite tournament without 3-coloured triples (that is, such that between any three points two of the three arcs have the same colour) always contains a monochromatically absorbing vertex; this can be generalized to k colours. Is this true if the 3-coloured tournament has no 3-coloured directed cycles (as Shen [78] conjectures)?

(iii) If an infinite tournament without rays is arc-coloured with k colours, is there always a finite monochromatically absorbing set?

Editor’s Note: See also BCC12.16.

Problem BCC16.8 (DM321): The ultimate independence ratio of a wheel. Proposed by Geña Hahn. Correspondent: Geña Hahn.

Define the independence ratio of a graph G by i(G) = α(G)/|G|, and the ultimate independence ratio by I(G) = lim_{k→∞} i(G^{k}), with G^{1} = G and G^{k} = G□G^{k−1}.

Conjecture: I(W_{5}) = I(W_{2n+1}) = \frac{1}{4} (where W_{2n+1} is the odd wheel).

Problem BCC16.9 (DM322): Colorings with minimum sum. Proposed by H. Hajiabolhassan, M.L. Mehrabadi, and R. Tusserkani. Correspondent: E.S. Mahmoodian.

Let G be a graph. A minimal coloring of G is a coloring which has the smallest possible sum among all proper colorings of G, using natural numbers. The vertex–strength of G, denoted by s(G), is the minimum number of colors which is necessary to obtain a minimal coloring. Prove or disprove:

s(G) ≤ ⌈\frac{χ(G) + Δ(G)}{2}⌉ .

We have already proved that:

s(G) ≤ ⌈\frac{col(G) + Δ(G)}{2}⌉.

where col(G) is the smallest number d such that for some linear ordering < of the vertex set, the back degree |{v : v < u, vu ∈ E(G)}| of every vertex u is strictly less than d. Therefore for all graphs G with χ(G) = col(G) e.g. all trees, the conjecture is verified. Also, we have verified this conjecture for line graphs.

Problem BCC16.10 (DM323): Colouring Kempe chains. Proposed by F. C. Holroyd, W. S. Leng. Correspondent: W. S. Leng.

Let G be a plane graph all of whose faces except the infinite face are triangles, and whose vertex set can be expressed as the disjoint union V_{0} ∪ … ∪ V_{n}, where

(i) V_{0} is a single vertex and, for each i = 1, …, n, V_{i} induces a cycle;

(ii) each vertex in V_{i} is adjacent only to vertices in V_{i−1}, V_{i+1} and two other vertices of V_{i}.

Can it be shown, without assuming the four-colour theorem, that there is a proper 4-colouring of G such that each V_{i} receives at most three colours?

Problem BCC16.11 (DM324): Linkages and flows. Proposed by Bruce Reed. Correspondent: Bruce Reed.

Find a short proof of the following theorem of Robertson and Seymour:

There is a function f such that, if the vertex set of a graph can be partitioned into a unique k-linkage (that is, k disjoint rooted paths as on page 101 of the proposer’s paper [73] in the Proceedings), then it can be partitioned into a unique f(k)-flow.

Problem BCC16.12 (DM325): Second neighbourhoods in digraphs. Proposed by Paul Seymour. Correspondent: Bruce Reed.

Does every digraph D have a vertex v such that

|N^{+}(v)| ≤ |N^{++}(v)|,

where N^{+}(v) is the (out-)neighbourhood of v and N^{++}(v) the strict second neighbourhood, the set of vertices reachable by directed paths of length 2 but not by single arcs from v?

The truth of this would imply that of the Caccetta–Häggkvist conjecture, according to which a digraph on n vertices with in- and out-degrees at least n/3 contains a directed triangle.

Remark: Gregory Gutin has pointed out that a special case of this problem, known as Dean’s Conjecture, was recently solved by Fisher [37].

Problem BCC16.13 (DM326): Book numbers of graphs. Proposed by E. Győri. Correspondent: E. Győri.

The book B_{k} is the graph consisting of k triangles sharing an edge. For a graph G, define bn(G) = max{k : B_{k} ⊆ G}.

For \frac{1}{2} < c < 1, define

b(c) = lim_{n→∞} \frac{1}{n} min\{bn(G) : |V (G)| = n, d(x) ≥ cn∀x\}.

The problem is to determine b(c). The intriguing conjecture about its value follows. Let x be rational with \frac{1}{2} < x < 1. The “greedy representation” of x is given by

x = \frac{k_{1} − 1}{k_{2}} · \frac{k_{2} − 1}{k_{2}} ⋯ \frac{k_{r} − 1}{k_{r}},

where k_{i} > (k_{i−1} − 1)^{2} for i = 2, 3, …, r. (This representation is unique.) Then set

f(x) = \frac{k_{1} − 2}{k_{2}} · \frac{k_{2} − 2}{k_{2}} ⋯ \frac{k_{r} − 2}{k_{r}}.

Then f extends to a function on the real interval (\frac{1}{2}, 1), continuous on every irrational. It is monotonic increasing left continuous but jumps at each rational.

Conjecture: b(c) = f(c).

Remark: This is easy for r = 1, and is true (with a 20-page proof, see [35]) for r = 2.

Problem BCC16.14 (DM327): Automorphisms of lexicographic squares. Proposed by Gert Sabidussi. Correspondent: Geña Hahn.

Let G be a graph such that G[G] ≃ G, where G[G] is the lexicographic product of G with itself.

Conjecture: There is an automorphism ϕ of G[G] and vertices u, v, w, x, y of G such that ϕ(u, x) ∈ {v} × V (G), ϕ(u, y) ∈ {w} × V (G), and v ≠ w.

Problem BCC16.15 (DM328): Simultaneous edge-colourings. Proposed by A. D. Keedwell. Correspondent: P. J. Cameron.

Suppose that x_{1}, …, x_{m}, y_{1}, …, y_{m} are positive integers such that there exists a bipartite graph with vertex degrees x_{1}, …, x_{m} in one bipartite block and y_{1}, …, y_{n} in the other. (This is equivalent to asserting that the conditions of the Gale–Ryser theorem are satisfied.) Suppose further that all the x_{i} and y_{j} are greater than 1. Show that there is a bipartite graph having these vertex degrees, which has two proper edge-colourings such that

• for any vertex, the sets of colours appearing on edges at that vertex are the same in both colourings;

• no edge receives the same colour in both colourings.

Note: M. Mahdian, E. S. Mahmoodian, A. Saberi, M. R. Salavatipour and R. Tusserkani [63] have made a stronger conjecture, namely, that any bridgeless bipartite graph has a pair of colourings satisfying the above properties. They have shown that this conjecture is equivalent to the celebrated ‘oriented cycle double cover conjecture’ of Paul Seymour [77].

Problem BCC16.16 (DM329): Abnormal strongly regular graphs. Proposed by P. J. Cameron and P. H. Fisher. Correspondent: P. J. Cameron.

Call a strongly regular graph Γ abnormal if it contains vertices x, y, z such that x ≁ y, x ≁ z, y ∼ z, and Γ(x) ∩ Γ(y) = Γ(x) ∩ Γ(z).

Problem: Does an abnormal strongly regular graph exist?

Remark: Such a graph must have λ ≥ μ, and not all the induced subgraphs on the nonneighbours of a vertex can be edge-regular. Any strongly regular graph with λ > 0 and μ = 1 is abnormal; but no such graphs are known.

Problem BCC16.17 (DM330): A problem on Soicher’s graph. Proposed by Bill Martin. Correspondent: Bill Martin.

This problem concerns a distance-regular graph Γ on 672 vertices, based on the punctured Golay code of length 22, constructed by Leonard Soicher [79] (see Problem BCC15.13). It turns out that Soicher’s graph, as well as being P-polynomial (that is, distance-regular), is also Q-polynomial; indeed, it is one of only two “sporadic” P- and Q-polynomial graphs (that is, not having classical parameters) which are known to the proposer. (The other is the doubled Higman–Sims graph.)

Problems:

(a) Find a simple description of Γ in PG(2, 4).

(b) Is there a Q-poset for Γ? (See below.)

Let Γ be a distance-regular graph of diameter d. Let E_{0}, E_{1}, …, E_{d} be the minimal idempotents in the Bose–Mesner algebra for Γ (in some order). The poset (P, ≤) of height d is a Q-poset for Γ if

(i) the dth level P_{d} of P is the vertex set of Γ;

(ii) for 0 ≤ i ≤ d, the incidence matrix W_{i} between the ith and dth levels of P has constant row sums;

rowspace(E_{i}) ⊆ rowspace(W_{i}) ⊆ ⨁_{j=0}^{i} rowspace(E_{j})

for 0 ≤ i ≤ d.

Remark: The standard example: the Boolean lattice of subsets of an n-set, truncated to height d, is a Q-poset for the Johnson graph J(n, d). If we require equality on the right-hand side of the inequality in (iii), and if rank(W_{i}) = |P_{i}| (both of which occur in the standard example), then the Q-poset for Soicher’s graph would satisfy

|P_{0}| = 1,
|P_{1}| = 1 + 55 = 56,
|P_{2}| = 1 + 55 + 385 = 441,
|P_{3}| = 1 + 55 + 385 + 231 = 672.

Also, presumably, the poset must be constructed from the punctured Golay code (or from PG(2, 4), if problem (a) is solved). Since M_{22} has no permutation action on 56 points, a construction from the punctured Golay code would require some “symmetry-breaking”.

Problem BCC16.18 (DM331): The Canterbury Parades. Proposed by D. A. Preece. Correspondent: D. A. Preece.

The organisers of the Seventeenth British Combinatorial Conference are planning a series of parades to entertain the delegates. Seventy-six trombones will lead the parades, with one hundred and ten cornets close behind. Since the mediaeval streets of Canterbury are quite narrow, the trombonists can march four abreast, and the cornettists five abreast. It is required first that any three trombonists march in the same row in exactly one parade. This of course means constructing a resolvable 3-(76, 4, 1) design. Such designs are known, and have 925 parallel classes, which means that the daily parades will last for about two and a half years.

The marching orders for the cornettists require a resolvable 3-(110, 5, 1) design.

Problem: Construct such a design.

Editor’s Note: The required design has 981 parallel classes. So, for the parades, it would suffice to find a “partial design” in which any three trombonists march together at most once, and there are 925 parallel classes.

In general, one could ask for solutions to the diophantine equation

\binom{v_{1} − 1}{t_{1} − 1}/\binom{k_{1} − 1}{t_{1} − 1} = \binom{v_{2} − 1}{t_{2} − 1}/\binom{k_{2} − 1}{t_{2} − 1},

and then ask for a solution to the corresponding parade problem.

Problem BCC16.19 (DM332): Semi-Latin squares which are partial linear spaces. Proposed by L. H. Soicher, R. A. Bailey and P. J. Cameron. Correspondent: R. A. Bailey.

An (n × n)/k semi-Latin square is an arrangement of nk letters in an n × n square, with k letters per cell, such that each letter occurs once in each row and once in each column. It is a Trojan square if it can be obtained by superimposing k mutually orthogonal n × n Latin squares. It is a partial linear space if no two letters occur together in the same cell more than once. Trojan squares are partial linear spaces.

Bailey [6] showed that when k = n−1 then any semi-Latin square which is a partial linear space must be Trojan, and arises from an affine plane with two distinguished parallel classes of lines.

Problem: If k = n−2, must any semi-Latin square which is a partial linear space be Trojan?

Editor’s Note: Semi-Latin squares which are partial linear spaces are known as SOMAs. See also BCC12.1 and BCC13.21.

Recent exhaustive checking by Soicher [80] shows that the answer to the problem stated is affirmative when n = 6 (there are no SLS-PLS or Trojan squares) and when n = 7.

Problem BCC16.20 (DM333): Blocking-set-free configurations. Proposed by H. Gropp. Correspondent: H. Gropp.

Is there a 3-chromatic linear 3-regular 3-uniform hypergraph with 16 vertices and 16 hyperedges? (Equivalently, a configuration 16_{3} with no blocking set.)

Remark: This is an update of problems from earlier British Combinatorial Conferences: see Problems BCC13.18 and BCC14.14. See also [42] for the background and current state of knowledge.)

In particular, in BCC14.14 the proposer asked whether there is a 15_{3} with no blocking set. This has been resolved negatively by unpublished results of Kel’mans, Lomonosov and Kornerup.

Problem BCC16.21 (DM334): A non-Desarguesian configuration. Proposed by Jane W. Di Paola. Correspondent: Jane W. Di Paola.

Prove that a non-Desarguesian projective plane must contain Martinetti’s third configuration. (The lines of the configuration are ABF, BCD, CAE, DEI, EF G, F DH, AGJ, BHJ, CIJ and GHI.)

Remark: Killgrove has shown that each of the three non-Desarguesian planes of order 9 contains this configuration.

Problem BCC16.22 (DM335): A matrix problem. Proposed by David Bedford and Roger Whitaker. Correspondent: David Bedford.

Let

X = ( \begin{matrix}B_{11} & B_{12} & ⋯ & B_{1t} \\ ⋮ & & & ⋮ \\ B_{t1} & B_{t2} & ⋯ & B_{tt} \end{matrix} ) ,

where each B_{ij} is a n × n matrix. Assume that B_{ii} = nI for all i, and that, for i ≠ j, B_{ij} has the following properties:

• entries on the leading diagonal are 1 and all other entries are 0, 1 or 2;

• B_{ij} has row and column sums n;

• B_{ij}^{⊤} = B_{ji} (and hence X is symmetric);

• B_{ij} + B_{ji} = 2J, where J is the n × n matrix with every entry 1.

Problem: Prove that X has nullity t − 1. (It is easily seen that t − 1 is a lower bound for the nullity.)

Problem BCC16.23 (DM336): Representing orthogonal matroids. Proposed by P. J. Cameron. Correspondent: P. J. Cameron.

Let V and W be vector spaces over a field F. Suppose that v_{1}, …, v_{n} ∈ V and w_{1}, …, w_{n} ∈ W satisfy

∑_{i=0}^{n} v_{i} ⊗ w_{i} = 0.  (1)

Then the matroids M and M′ on the ground set {1, …, n} represented by (v_{1}, …, v_{n}) and (w_{1}, …, w_{n}) are orthogonal, in the sense that any base of M is disjoint from some base of M′ and vice versa.

Problem: Let M and M′ be matroids on {1, …, n} which are both representable over a field F and are orthogonal in the above sense. Do there exist representations of M and M′ (by v_{1}, …, v_{n} ∈ V and w_{1}, …, w_{n} ∈ W) over F such that (1) holds?

Problem BCC16.24 (DM337): Subsums of signed permutations. Proposed by J. Schönheim. Correspondent: J. Schönheim.

Given a sequence a_{1}, a_{2}, …, a_{n}, being a permutation of the first n positive integers, we say it has the NZS property if it is possible to assign ± to its members so that no subsequence of consecutive elements has a zero sum modulo 2n + 1.

(a) Which permutations of {1, 2, …, n} have the NZS property?

(b) Show that for every n there exists a latin square of order n with entries from {1, 2, …, n} such that each of its rows has the NZS property.

(c) Find for every n a sequence a_{1}, a_{2}, …, a_{n}, being a permutation of the first n positive integers, such that every cyclic permutation of a_{1}, a_{2}, …, a_{n} has the NZS property.

Problem BCC16.25 (DM338): Erdős–Ko–Rado at the court of King Arthur. Proposed by Fred Holroyd. Correspondent: Fred Holroyd.

King Arthur has n knights, who have permanent places round the Table. They are to be arranged into sorties, of k knights each, such that:

(a) any two sorties intersect;

(b) because of courtly rivalries, any two knights in any sortie must sit at least d places apart round the Table (where d ≥ 2; that is, d = 2 means adjacent knights cannot be in the same sortie).

Is it true that the Erdős–Ko–Rado theorem still holds, in the sense that to maximize the number of sorties, King Arthur should belong to all of them?

Remark: This is known to be true if n is sufficiently large (in terms of d and k) or if kd ≤ n < (k + 1)d.

Problem BCC16.26: The thrackle problem. Proposed by J. H. Conway. Correspondent: J. H. Conway.

A thrackle consists of a set of points in the plane called spots, and a set of differentiable simple curves called paths, such that

• the ends of each path are distinct spots, and it contains no other spot;

• any two paths must hit once and only once, that is, have just one common point, at which they must have different tangents;

• every spot is a hit.

Problem: Is there a thrackle with more paths than spots?

The proposer has offered $1000 for this problem. For registered delegates of BCC16 only, the value of the prize is increased to £1000. For more information, see [85].

BCC17

BCC17 was held at the University of Kent at Canterbury, 12-16 July 1999. The contributed papers have not yet appeared.

Problem BCC17.1: Drawing configurations in the plane. Proposed by Harald Gropp. Correspondent: Harald Gropp.

The projective plane PG(2, 2) has a familiar drawing in the euclidean plane with six of its seven lines drawn as Euclidean straight lines. What is the maximum number of straight lines in a Euclidean drawing of PG(2, 3)? (A drawing with eight straight lines is known.)

Problem BCC17.2: Nested BIBDs. Proposed by D. A. Preece and R. A. Bailey. Correspondent: R. A. Bailey.

Let Δ be a balanced incomplete block design (BIBD) on v letters, having b blocks of size k. Let Γ be a BIBD on the same v letters having bs blocks of size k/s (with s > 1), its blocks obtained by splitting the blocks of Δ into s subblocks. Then Γ is nested in Δ.

(a) Find examples with Aut(Δ) = Aut(Γ) = 1.

(b) Do almost all pairs of nested BIBDs satisfy this?

Problem BCC17.3: Intersecting families and S(4, 7, 23). Proposed by Peter Rowlinson. Correspondent: Peter Rowlinson.

The family F of 7-subsets of a 23-set has the property that any two members of F intersect in 1 or 3 elements. (Hence |F| ≤ 253.) How large must |F| be to guarantee that F can be embedded in S(4, 7, 23)?

Problem BCC17.4: An extremal problem related to biplanes. Proposed by Gretgory Gutin. Correspondent: P. J. Cameron.

Given n, what is the smallest m such that there exist m subsets (called blocks) of the point set {1, …, n} such that

(a) any two points lie in at least two blocks,

(b) any two blocks meet in at most two points?

Remark: It is known that n ≤ m ≤ (2 + o(1))n; the lower bound comes from a simple counting argument, and the upper bound is obtained by taking blocks to be the translates of D and −D, where D is a planar difference set in C_{n}, with n = q^{2} +q +1. For more details, see [20].

Problem BCC17.5: Some 1-factorizations. Proposed by Chris Rodger. Correspondent: Chris Rodger.

Let G be the multigraph whose vertex set is ℤ_{2n}, the integers modulo 2n, in which i and j are joined by two edges if j = i + n and one edge otherwise. Give an easy way to find a 1-factorization of G in which each of the 2n 1-factors contains one of the doubled edges {i, i + n}.

This 1-factorization is equivalent to a symmetric Latin square with holes of size 2, so can be constructed reasonably easily using design-theoretic techniques.

Editor’s note: There is a simple solution when n is odd. Take the vertices to be those of a regular 2n-gon, the doubled edges being the long diagonals. Now let one 1-factor containing a long diagonal {i, i + n} contain all edges and short diagonals parallel to {i, i + n}, and the other contain all short diagonals perpendicular to {i, i + n}.

A solution for n ≡ 0 (mod 4) is given by Bailey and Monod [8]; but this perhaps does not qualify as “easy”.

Problem BCC17.6: Unions of random matchings. Proposed by Nick Wormald. Correspondent: Nick Wormald.

Choose k perfect matchings of the complete graph K_{n} (for n even) at random. Denote them by M_{1}, …, M_{k}. Let p_{k}(n) denote the probability that for every i ≠ j, the union of M_{i} and M_{j} forms a Hamilton cycle. How does this probability behave as n → ∞ with k fixed? In particular, is it true that

p_{k}(n) ∼ (p_{2}(n))^{\binom{k}{2}}?

Remark: The answer to the last question is known to be “yes” for k = 3 (shown in joint work of the proposer and J. H. Kim [52]).

Problem BCC17.7: Edge-colouring nearly complete graphs. Proposed by N. Zagaglia Salvi. Correspondent: N. Zagaglia Salvi.

Let G be a graph obtained from K_{n}, where n = 2t + 1, by deleting any t edges. Let α be a proper χ′-edge-colouring of G, where χ′ = χ′(G) = n − 1.

Problems: (a) Does there exist a subgraph of G having n − 1 edges and maximum degree Δ = 2, whose edges all have different colours in the colouring α?

(b) For every edge e ∈ E(G), does there exist a subgraph of G containing e which has n − 2 edges and has maximum degree Δ = 2, whose edges all have different colours in the colouring α?

Problem BCC17.8: Caterpillar-arboricity of planar graphs. Proposed by Y. Roditty. Correspondent: Y. Roditty.

The arboricity a(G) of a graph G is defined to be the smallest number of forests containing all the edges of G. In a similar way, the linear arboricity la(G) (resp., star arboricity sa(G), caterpillar arboricity ca(G)) of G is the smallest number of forests containing all edges of G such that each component of each forest is a path (resp., a star, a caterpillar). (A caterpillar is a tree with the property that removal of all the end vertices and the edges containing them yields a path.)

Nash-Williams [69] proved that any planar graph G satisfies a(G) ≤ 3. Hakimi, Mitcham and Schmeichel [45] showed that a planar graph satisfies sa(G) ≤ 5.

Conjecture: A planar graph G satisfies ca(G) ≤ 4.

Problem BCC17.9: Binding functions for graphs. Proposed by Ingo Schiermeyer and Bert Randerath. Correspondent: Ingo Schiermeyer.

As introduced by Gyárfás [43], a family G of graphs is called χ-bound with χ-binding function f if χ(G′) ≤ f(ω(G′)) holds whenever G′ is an induced subgraph of G ∈ G. (Here as usual ω(G′) and χ(G′) are the clique number and chromatic number of G′.)

Let G^{I}(3, 4) denote the class of graphs whose induced cycles have length 3 or 4 only.

Problem: Determine a χ-binding function for G^{I}(3, 4).

Remark: The authors [72] have shown that this class does not have a linear χ-binding function.

Problem BCC17.10: Group analogues of graph problems. Proposed by Frank Harary. Correspondent: Frank Harary.

Find and solve problems about finite groups (or finite abelian groups) motivated by results in graph theory.

For example, Harary and Hawthorn [46] found the minimum number of elements in a set S ⊆ A \ {0} such that A \ S has no subgroup isomorphic to B, where A and B are finite abelian groups; this is an analogue of Turán’s Theorem for graphs.

Problem BCC17.11: Neighbourhood-symmetric graphs. Proposed by Dalibor Fronček. Correspondent: Dalibor Fronček.

The neighbourhood of a vertex x in a graph G, denoted N_{G}(x), is the subgraph of G induced on the set of all neighbours of x. We say that G has constant neighbourhood H if N_{G}(x) ≅ H for all x ∈ V (G). We say that G is a neighbourhood-symmetric graph (or NSG) if N_{G}(x) ≅ N\overline{G}(x) ≅ H, for some H, and all x ∈ V (G). Clearly any vertex-transitive self-complementary graph is a NSG.

Problem: Construct a counterexample to the converse assertion; that is, find a NSG which fails to be vertex-transitive and self-complentary.

Problem BCC17.12: Semiregular automorphisms. Proposed by Peter Cameron and John Sheehan. Correspondent: P. J. Cameron.

Marušič and Scapellato [65] proved that a vertex-transitive connected cubic simple graph has a non-trivial semiregular automorphism (one for which all cycles have the same length). Is it true that there exists such an automorphism having order at least f(n), where n is the number of vertices and f is a function for which f(n) → ∞ as n → ∞? Easy examples show that f(n) cannot exceed O(n^{1/3}).

Problem BCC17.13: Regular graphs admitting a given group. Proposed by Peter J. Cameron. Correspondent: Peter J. Cameron.

It is known (see [17]) that, for any finite group Γ, there exists a rational number a(Γ) ∈ [0, 1] such that, if G denotes a random graph on the vertex set {1, …, n} (with all graphs equally likely), then

Prob(Aut(G) = Γ | | Aut(G) ≥ Γ) → a(Γ) as n → ∞.

Does a similar result hold for other random graph models, in particular for random regular graphs of degree d > 2 (as described by Nick Wormald [86] at the conference)?

Problem BCC17.14: Symmetry groups of boolean functions. Proposed by Andrzej Kisielewicz. Correspondent: Andrzej Kisielewicz.

Let f be a k-valued boolean function of n variables, that is, a function from {0, 1}^{n} to {0, 1, …, k − 1}. If k = 2, we simply call f a boolean function. The symmetry group G(f) of f is the group of all permutations σ ∈ S_{n} such that

f(x_{σ(1)}, …, x_{σ(n)}) = f(x_{1}, …, x_{n})

for all (x_{1}, …, x_{n}) ∈ {0, 1}^{n}.

We say that a subgroup G of S_{n} is k-representable if G = G(f) for some k-valued boolean function f. Clote and Kranakis [28] proved that, if G is k-representable for some k ≥ 2, then G is 2-representable. However, the Klein group

V_{4} = ⟨(1 2)(3 4), (1 3)(2 4)⟩ ≤ S_{4}

is a counterexample: it is 3-representable but not 2-representable. The proof in [28] has a gap, which does not seem to be fixable. For more information see [53].

Problem: Are there any other counterexamples?

Problem BCC17.15: Non-zero-sum sequences. Proposed by J. Schönheim. Correspondent: J. Schönheim.

Let a_{i} ∈ ℤ_{2m+1} (the integers modulo 2m + 1) for i = 1, …, t. We say that the sequence a = (a_{1}, …, a_{t}) has the k-NZS property if no subsequence of k or fewer consecutive terms has sum zero (mod 2m + 1).

In these problems, a = (a_{1}, …, a_{m}) denotes a permutation of (1, …, m), and ϵ = (ϵ_{1}, …, ϵ_{m}) a sequence of signs (ϵ_{i} = ±1 for all i).

It is known that there exist such sequences a, ϵ such that the sequence (ϵ_{1}a_{1}, …, ϵ_{m}a_{m}) has sum zero (mod 2m + 1) but has the (m − 1)-NZS property.

Problem: Given b_{1}, …, b_{m}, show that there exist c_{1}, …, c_{m} such that

(a) (c_{1}, …, c_{m}) is a permutation of (ϵ′_{1}b_{1}, …, ϵ′_{m}b_{m}) for some choice of signs ϵ′ = (ϵ′_{1}…. , ϵ′_{m});

(b) each row in the array

b_{1} b_{2} … b_{m−1} c_{m}
b_{2} b_{3} … b_{m}  c_{1}
b_{3} b_{4} … b_{1}  c_{2}
⋮
b_{m} b_{1} … b_{m−2} c_{m−1}

is m-NZS.

Problem: Prove that given ϵ, there exists a such that the sequence ϵa has the m-NZS property.

Problem BCC17.16: Acceptable cross-sections. Proposed by Nigel Martin. Correspondent: Nigel Martin.

A cross-section of a sequence (S_{1}, …, S_{k}) of sets of integers is a sequence (x_{1}, …, x_{k}) with x_{i} ∈ S_{i} for i = 1, …, k. A cross-section is acceptable if for all i, j with i ≠ j,

x_{j} − x_{i} ≢ j − i (mod k).

Fix p = 2r + 1, and consider the sets S_{1}, …, S_{p} given by

S_{i} = {j : i ≤ j ≤ r + i − 1} for 1 ≤ i ≤ r,
S_{r+1} = {j : 1 ≤ j ≤ r},
S_{r+i+1} = {j : i ≤ j ≤ r + i} for 1 ≤ i ≤ r − 1,
S_{2r+1} = {j : r ≤ j ≤ r − 1}

Find p − 2 acceptable cross-sections for this sequence so that, in aggregate, every number in the range {1, …, p − 2} occurs p + 1 times.

Solutions are known for p = 2^{n} ± 1, p = 6 · 2^{n} − 1 and finitely many other values.

Problem BCC17.17: Evaluating inversion numbers. Proposed by Timothy R. Walsh. Correspondent: Timothy R. Walsh.

The number M(n, r) of permutations of {1, 2, …, n} with r inversions is the coefficient of x^{r} in

(1 + x)(1 + x + x^{2}) ⋯ (1 + x + x^{2} + ⋯ + x^{n−1}).

To find a single value of M(n, r) by evaluating M(n′, r′) for all n′ ≤ n and r′ ≤ r takes O(nr) = O(n^{3}) arithmetic operations.

Problem: Find a non-recursive formula for M(n, r) which can be evaluated in at most the same time.

Donald E. Knuth [57], page 16 gave a simple formula in the case r ≤ n. The proposer has given a monstrously complicated formula for the general case.

Problem BCC17.18: Sets of permutations with given minimum distance. Proposed by Wendy Myrvold. Correspondent: Wendy Myrvold.

What is the largest number of permutations of n symbols in a set with the property that any two agree in at most r columns? This number is at most n!/(n − r − 1)!, with equality if and only if the set is sharply (r + 1)-transitive.

For further details on this problem, see Section 5 of the survey [21].

Problem BCC17.19: Covering radius and Tutte polynomial. Proposed by Carrie G. Rutherford, Fuad Shareef. Correspondent: Peter J. Cameron.

Associated with any matrix A over a field F, there is a matroid representable over F (whose elements are the columns of A, and in which dependence is linear dependence) and a linear code (spanned by the rows of F. Greene [41] showed that the weight enumerator of the code is a specialisation of the Tutte polynomial of the matroid.

Do there exist two binary linear codes which have the same Tutte polynomials but different covering radii? (There are codes with the same weight enumerators but different covering radii.)

Editor’s Note: At the conference, the following problem was presented:

Problem BCC17.20: Derangements in the alternating group. Proposed by Ömer Eceğlioğlu. Correspondent: Ömer Eceğlioğlu.

Let d_{n} be the number of derangements (fixed-point-free permutations) in the symmetric group S_{n}, and a_{n} the number of derangements in the alternating group A_{n}. It is known that

a_{n} = \binom{n}{2}d_{n−2} + (−1)^{n−1}(n − 1).

Problem: Find a bijective proof of this fact.

The problem is equivalent to the statement that the numbers d_{n}^{+} = a_{n} and d_{n}^{−} of derangements which are even and odd permutations satisfy

d_{n}^{+} − d_{n}^{−} = (−1)^{n−1}(n − 1).

This was subsequently solved by Robin Chapman. His elegant solution follows.

Let D_{n} the be set of derangements. We can split this set into n − 1 equal parts according to where the permutation sends n. We look therefore only at D′_{n} = {σ ∈ D_{n} : σ(n) = n−1}. Define a sign-reversing involution on the set D′_{n} \ {(1 2 3 … n − 2 n n − 1)}. This will give us what we want.

For σ ∈ D′_{n} let a(σ) be the least number a with σ(a) < a. Then a(σ) < n−1 with the sole exception σ = (1 2 3 … n − 2 n n − 1). For all σ ∈ D′_{n} apart from this one permutation, let f(σ) = (a(σ) n) ∘ σ.

It suffices to show that τ = f(σ) satisfies τ ∈ D′_{n} and a(τ) = a(σ).

First of all σ(n) = n − 1 which is not in {a, n}, so τ(n) = n − 1. Suppose τ(j) = j for some j. Then τ(j) ≠ σ(j), so that σ(j) = a or n and τ(j) = j = n or a respectively. But σ(a) < a, so j = a and σ(j) = n is impossible. Also τ(n) = n − 1 > a, so that j = n and σ(j) = a is impossible. Hence τ lies in D′_{n}.

If j < a, then σ(j) > j and τ(j) equals one of σ(j), a and n, all of which exceed j. But σ(a) < a < n and so τ(a) = σ(a) < a. Hence a(τ) = a.

Proposers’ addresses

M. Alabdullatif University of Keele

mad32@keele.ac.uk

Noga Alon Department of Mathematics Tel-Aviv University Ramat Aviv 69978 Tel-Aviv Israel

R. A. Bailey School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

r.a.bailey@qmw.ac.uk

Frank Barnes Department of Mathematics Kenyatta University P.O. Box 43844 Nairobi Kenya

David Bedford Mathematics Department Keele University Keele, Staffs ST5 5BG

maa19@keele.ac.uk

Jürgen Bierbrauer Mathematisches Institut deer Universität Im Neuenheimer Feld 288 69 Heidelberg Germany

Arrigo Bonisoli Dipartimento di Matematica Università della Basilicata via N. Sauro 85 85100 Potenza Italy

ba008ing@unibas.it

Stephan Brandt FB Mathematik Freie Universität Berlin Arnimallee 2–6 14195 Berlin Germany

brandt@math.fu-berlin.de

Neil J. Calkin Department of Mathematical Sciences Martin Hall Box 341907 Clemson, SC 29634-1907

calkin@math.clemson.edu

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

p.j.cameron@qmw.ac.uk

R. J. Chapman Department of Mathematics University of Exeter North Park Road Exeter EX4 4QE U.K.

rjc@maths.ex.ac.uk

J. H. Conway Department of Mathematics Princeton University Princeton, NJ 08544 USA

conway@math.princeton.edu

Peter Cowling Mathematical Institute 24–29 St. Giles’ Oxford OX1 3LB U.K.

Jane W. Di Paola 340 Pine Ridge Circle #A1 Greenacres, FL 33463 USA

Ömer Eğecioğlu Department of Computer Science University of California Santa Barbara, CA 93106 USA

omer@cs.ucsb.edu

Paul Erdős Mathematical Institute of the Hungarian Academy of Sciences Reáltanoda u. 13–15 H-1053 Budapest Hungary

Jonathan D. Farley Mathematical Institute St. Giles’ Oxford OX1 3LB U.K.

farley@maths.ox.ac.uk

Dalibor Fronček Department of Applied Mathematics Technical University Ostrava 17 listopadu 708 33 Ostrava-Poruba Czech Republic

dalibor.froncek@vsb.cz

Zoltan Füredi Department of Mathematics University of Illinois at Urbana-Champaign 1409 W Green St. Urbana, IL 61801-2975 USA

z-furedi@math.uiuc.edu

Tony Gardiner Department of Mathematics University of Birmingham P.O. Box 363 Birmingham B15 2TT U.K.

a.d.gardiner@bham.ac.uk

Harald Gropp Mühlingstr. 19 D-69121 Heidelberg Germany

d12@ix.urz.uni-heidelberg.de

Gregory Gutin Department of Mathematics and Statistics Brunel University Uxbridge, Middx UB8 3PH

z.g.gutin@brunel.ac.uk

Ervin Győri Mathematical Institute of the Hungarian Academy of Sciences PO Box 127 H-1364 Budapest Hungary

ervin@math-inst.hu

Willem Haemers Department of Mathematics University of Tilburg Tilburg The Netherlands

haemers@kub.nl

Roland Häggkvist Department of Mathematics University of Umeå S-90187 Umeå

Sweden rolandh@biovax.umdc.umu.se

Geña Hahn IRO, Université de Montréal 2920 Chemin de la tour Montréal, Québec, Canada

hahn@iro.umontreal.ca

Frank Harary Department of Computer Science New Mexico State University PO Box 30001 Las Cruces, NM 88003 USA

fnh@nmsu.edu

Anthony Hilton Department of Mathematics University of Reading Whiteknights Reading RG6 2AX U.K.

a.j.w.hilton@reading.ac.uk

C. Hoede Department of Applied Mathematics University of Twente P.O. Box 217 7500AE Enschede The Netherlands

Fred Holroyd Faculty of Mathematics and Computing The Open University Milton Keynes MK 7 6AA

f.c.holroyd@open.ac.uk

A. A. Ivanov Department of Mathematics Imperial College Huxley Building Queen’s Gate London SW7 2BZ U.K.

a.ivanov@imperial.ac.uk

S. Jendrol’ Department of Geometry and Algebra P.J.Šafárik University 04154 Košice, Jesenná 5 Slovak Republic

jendrol@kosice.upjs.sk

Peter M. Johnson Departamento de Matemática Universidade Federal de Pernambuco Recife Brazil

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

rezagbk@zagros.ipm.ac.ir

Andrzej Kisielewicz Mathematical Institute University of Wroclaw Pl. Grunwaldski 2 50-384 Wroclaw Poland

kisiel@math.uni.wroc.pl

Sandi Klavžar Department of Mathematics, PeF University of Maribor Koroška cesta 160 62000 Maribor Slovenia

sandi.klavzar@uni-lj.si

Mikhail Klin Department of Mathematics and Computer Science Ben-Gurion University of the Negev P.O.Box 653 Beer-Sheva 84105 Israel

klin@indigo.cs.bgu.ac.il

W. S. Leng

London TOE group 22 Birch Tree Walk London CR0 7JY

Richard P. Lewis

School of Mathematical and Physical Sciences University of Sussex Falmer Brighton BN1 9QH U.K.

                                      r.p.lewis@sussex.ac.uk

Ebad Mahmoodian

Department of Mathematical Sciences Sharif University of Technology Iran

                                      emahmood@vax.ipm.ac.ir

Nigel Martin

Department of Mathematics

University of Durham

Durham U.K.

                                      nigel.martin@durham.ac.uk

Bill Martin

University of Winnipeg Winnipeg, MB R3T 5J5 Canada

                                      william.martin@uwinnipeg.ca

Henry Martyn Mulder

Department of Mathematics

Erasmus Universiteit

Postbus 1738

3000DR Rotterdam The Netherlands

martyn@cvx.eur.nl

Wendy Myrvold Department of Computer Science University of Victoria PO Box 3055, Stn CSC Victoria, BC V8W 3P6 Canada

wendym@csr.uvic.ca

Jaroslav Nešetřil KAM Department of Applied Mathematics Charles University Malostranské nám. 25 11800 Praha 1 Czech Republic

D. A. Preece Institute of Mathematics and Statistics Cornwallis Building University of Kent at Canterbury Canterbury, Kent CT2 7NF

d.a.preece@ukc.ac.uk

Oliver Pretzel Department of Mathematics Imperial College Huxley Building Queen’s Gate London SW7 2BZ U.K.

o.pretzel@imperial.ac.uk

Bruce Reed Equipe Combinatoire CNRS Universite Pierre et Marie Curie (Paris 6) 4, Place Jussieu 75252 Paris cedex 05 France

                                      reed@ccr.jussieu.fr

Chris Rodger 120 Math Annex Auburn University Auburn, AL 36849-5307 USA

                                      rodgec1@mail.auburn.edu

Y. Roddity

School of Mathematical Sciences

Tel-Aviv University Tel-Aviv 69978 Israel

                                      jr@math.tau.ac.il

Alex Rosa

Department of Mathematics

McMaster University Hamilton, Ontario Canada L8S 4K1

                                      rosa@sscvax.cis.mcmaster.ca

Peter Rowlinson

Department of Computing Science & Mathematics University of Stirling Scotland FK9 4LA

                                      p.rowlinson@stirling.ac.uk

Bill Sands

Department of Mathematics and Statistics University of Calgary 2500 University Drive N.W.

Calgary, Alberta Canada T2N 1N4

Daniel P. Sanders Department of Mathematics The Ohio State University 231 West 18th Avenue Columbus, OH 43210 U.S.A.

dsanders@math.ohio-state.edu

Holger Schellwat Department of Technology and Natural Sciences University College of Örebro Box 923 S–701 30 Örebro Sweden

holger.schellwat@hoe.se

Ingo Schiermeyer Technische Universität Bergakademie Freiberg Fakultätfür Mathematik und Informatik D-09596 Freiberg Germany

schierme@math.tu-freiberg.de

J. Schönheim Department of Mathematics Tel-Aviv University Ramat Aviv 69978 Tel-Aviv Israel

shanan@math.tau.ac.il

A. Shastri Department of Mathematics and Computer Science Banasthali University P.O. Banasthali Vidyapith–304 022 India

M. K. Siu

Department of Mathematics University of Hong Kong

                                      mathsiu@hkucc.earn

Leonard Soicher

School of Mathematical Sciences Queen Mary and Westfield College Mile End Road London E1 4NS U.K.

                                      l.h.soicher@qmw.ac.uk

Tom Trotter

Department of Mathematics Arizona State University Tempe, AZ 85287-1804 USA

Alain Valette

Département de Mathematique Université de Neuchâtel Neuchâtel Switzerland

                                      valette@maths.unine.ch

Chris Wakelin

Department of Mathematics University of Nottingham University Park Nottingham NG7 2RD U.K.

Timothy R. Walsh

walsh.timothy@uqam.ca

Ian Wanless Department of Computer Science Australian National University Canberra

Australia imw@ra0.anu.edu.au

D. B. West Department of Mathematics University of Illinois Urbana, IL 61801 USA

Douglas R. Woodall Department of Mathematics University of Nottingham University Park Nottingham NG7 2RD U.K.

drw@maths.nott.ac.uk

Nick Wormald Department of Mathematics and Statistics University of Melbourne Parkville, Vic. 3052 Australia

nick@ms.unimelb.edu.au

Peter Yff Department of Mathematical Sciences Ball State University Muncie, IN 47306-0001 USA

Dale Youngs Racal Research Ltd.

Worton Drive

Reading, Berks. RG2 0SB U.K.

N. Zagaglia Salvi Dip. di Matematica Politecnico di Milano P.za L. da Vinci 32 20133 Milano Italy

                                      norzag@mate.polimi.it

François Zara

U.F.R. de Mathématiques 33, rue Saint-leu F80039 Amiens cedex France

Jörg Zuther

Technische Universität Berlin Fachbereich Mathematik Sekretariat 8-1 Straße des 17. Juni 135 10623 Berlin Germany

                                      zuther@math.tu-berlin.de

References

[1] M. Alabdullatif, On quasi-Hamiltonian-connected graphs, J. Comb. Inf. Syst. Sci. 22 (1997), 1–8.

[2] N. Alon and D. J. Kleitman, Sum-free subsets, pp. 13–26 in A tribute to Paul Erdős (ed. A. Baker, B. Bollobás and A. Hajnal), Cambridge University Press, Cambridge, 1990.

[3] K. J. Åström, B. Wittenmark, Computer Control Systems, Prentice Hall, Englewood Cliffs, NJ, 1990.

[4] A. O. L. Atkin and P. Swinnerton-Dyer, Some properties of partitions, Proc. London Math. Soc. (3) 4 (1954), 84–106.

[5] R. A. Bailey, Designs: mappings between structured sets, pp. 22–51 in Surveys in Combinatorics, 1989 (ed. J. Siemons), Cambridge Univ. Press, Cambridge, 1989.

[6] R. A. Bailey, Efficient semi-Latin squares, Statistica Sinica 2 (1992), 413–437.

[7] R. A. Bailey, Semi-Latin squares, available at

http://www.maths.qmw.ac.uk/~rab/sls.html

[8] R. A. Bailey and H. Monod, Efficient semi-Latin rectangles: designs for plant disease experiments, preprint. [Currently available from

http://www.maths.qmw.ac.uk/~rab/preprint.html]

[9] E. A. Bender, P. J. Cameron, A. M. Odlyzko and B. L. Richmond, Connectedness, classes and cycle index, Combinatorics, Probability and Computing 8 (1999), 31–43.

[10] J. Berman and P. Kohler, Cardinalities of Finite Distributive Lattices, Mitt. Math. Sem. Giessen 121 (1976), 103–124.

[11] A. Blokhuis and H. Wilbrink, Characterization theorems for Zara graphs, Europ. J. Combinatorics 10 (1989), 57–68.

[12] S. Brandt, The local density of triangle-free graphs, Discrete Math. 183 (1998), 17–25.

[13] W. G. Bridges and R. A. Mena, Multiplicative cones — a family of three eigenvalue graphs, Aequat. Math. 22 (1981), 208–214.

[14] A. E. Brouwer, A non-degenerate generalized quadrangle with lines of size four is finite, pp. 47–49 in Advances in finite geometries and designs, Proc. 3rd Isle of Thorns Conf. (ed. J. W. P. Hirschfeld, D. R. Hughes, J. A. Thas), Oxford University Press, Oxford, 1991.

[15] N. J. Calkin, On the number of sum-free sets, Bull. London Math. Soc. 22 (1990), 141–144.

[16] N. J. Calkin and P. J. Cameron, Almost odd random sum-free sets, Combinatorics, Probability and Computing 7 (1998), 27–32.

[17] P. J. Cameron, On graphs with given automorphism group, Europ. J. Combinatorics 1 (1980), 91–96.

[18] P. J. Cameron, Metric and geometric properties of sets of permutations, pp. 39–53 in Algebraic, Extremal and Metric Combinatorics (ed. M.-M. Deza, P. Frankl & I. G. Rosenberg), London Math. Soc. Lecture Notes 131, Cambridge Univ. Press, Cambridge, 1988.

[19] P. J. Cameron, Quasi-symmetric designs possessing a spread, pp. 231–236 in Combinatorics ’88 (ed. A. Barlotti et al.), Mediterranean Press, Roma, 1992.

[20] P. J. Cameron, An extremal problem related to biplanes, Australasian J. Combinatorics 20 (1999), 97–100.

[21] P. J. Cameron, Permutations, in preparation. [Currently available from

http://www.maths.qmw.ac.uk/~pjc/papers.html]

[22] P. J. Cameron and P. Erdős, On the number of sets of integers with various properties, pp. 61–79 in Number Theory (ed. R. A. Mollin), Walter de Gruyter, Berlin, 1990.

[23] P. J. Cameron, P. Frankl and W. M. Kantor, Intersecting families of finite sets and fixed-point-free 2-elements, Europ. J. Combinatorics 10 (1989), 149–160.

[24] P. J. Cameron, D. R. Hughes and A. Pasini, Extended generalized quadrangles, Geometriae Dedicata 35 (1990), 193–228.

[25] P. J. Cameron and C. E. Praeger, Block-transitive t-designs, I: point-imprimitive designs, Discrete Math. 118 (1993), 33–43.

[26] P. J. Cameron and C. E. Praeger, Block-transitive t-designs, II: large t, pp. 103–119 in Finite Geometry and Combinatorics (ed. A. Beutelspacher et al.), Cambridge University Press, Cambridge, 1993.

[27] F. R. K. Chung and R. L. Graham, Erdős on Graphs: His Legacy of Unsolved Problems, A. K. Peters, Wellesley, MA, 1998.

[28] P. Clote and E. Kranakis, Boolean functions, invariance groups, and parallel complexity, SIAM J. Comput. 20 (1991), 553–590.

[29] M. D. E. Conder, Hexagon-free subgraphs of hypercubes, J. Graph Theory 17 (1993), 477–479.

[30] P. Cowling, Total colouring of hypergraphs, J. Comb. Math. Comb. Comput. 19 (1995), 151-160.

[31] J.-H. Deshouillers, G. Freiman, V. T. Sós and M. Temkin, On the structure of sum-free sets, Asterisque 258 (1999), 149-161.

[32] J. Dénes and P. Hermann, On the product of all elements in a finite group, Ann. Discrete Math. 15 (1982), 105-109.

[33] J. W. DiPaola and H. Gropp, Symmetric configurations without blocking sets, Mitt. Math. Semin. Giessen 201 (1991), 49-54.

[34] P. Erdős, Problems and results in graph theory and combinatorial analysis, in: Proc. 5th British Combinatorial Conference (Aberdeen, 1975), Utilitas Math., Winnipeg, pp. 169–192.

[35] P. Erdős, R. Faudree and E. Győri, On the book size of graphs with large minimum degree, Studia Sci. Math. Hungar. 30 (1995), 25–46.

[36] D. M. Evans, A block-transitive 2-design with two point orbits, to appear.

[37] D. C. Fisher, Squaring a tournament: a proof of Dean’s Conjecture, J. Graph Theory 23 (1996), 43-48.

[38] T. Gallai, Transitiv Orientbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.

[39] T. Gallai, Problem 4, in: P. Erdős, G. Katona, Eds., Theory of Graphs, Proc. Colloq. Tihany, Hungary, Sept. 1966, Academic Press, New York, 1968, p. 362.

[40] M. R. Giudici, in preparation.

[41] C. Greene, Weight enumeration and the geometry of linear codes, Studies in Applied Math. 55 (1976), 119–128.

[42] H. Gropp, Blocking set free configurations and their relations to digraphs and hypergraphs, Discrete Math. 165/166 (1997), 349–360.

[43] A. Gyárfás, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math. 55 (1985), 161–166.

[44] R. Häggkvist and J. C. M. Janssen, All-even latin squares, Discrete Math. 157 (1996), 199–206

[45] S. L. Hakimi, J. Mitchem and E. E. Schmeichel, Star arboricity of graphs, Discrete Math. 149 (1996), 93–98.

[46] F. Harary and I. Hawthorn, in preparation.

[47] C. Hering, A remark on two diophantine equations of Peter Cameron, pp. 448–458 in Groups, combinatorics and geometry (ed. M. W. Liebeck and J. Saxl), London Math. Soc. Lecture Notes 165, Cambridge University Press, Cambridge, 1992.

[48] A. J. W. Hilton, Initial and threshold values for exactly k-to-1 continuous maps between graphs, Congressus Numerantium 91 (1992), 254–270.

[49] R. Hochberg, C. J. H. McDiarmid and M. Saks, On the bandwidth of triangulated triangles, Discrete Math. 138 (1995), 261–265.

[50] M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. Combinatorial Design 4 (1996), 405–437.

[51] L. K. Jørgensen, Contractions to K_{8}, J. Graph Theory 18 (1994), 431–448.

[52] J. H. Kim and N. C. Wormald, Random matchings which induce Hamilton cycles, and hamiltonian decompositions of regular graphs, in preparation.

[53] A. Kisielewicz, Symmetry groups of boolean functions and constructions of permutation groups, J. Algebra 199 (1998), 379–403.

[54] S. Klavžar and M. Petkovšek, Graphs with nonempty intersection of longest paths, Ars Combinatoria 29 (1990), 43–52. Prentice Hall, Englewood Cliffs, NJ, 1990 [55] R. Klein, On the colorability of m-composed graphs, Discrete Math. 133 (1994), 181–

190.

[56] D. J. Kleitman and G. Markovsky, On Dedekind’s problem: the number of isotone boolean functions, II, Trans. Amer. Math. Soc. 213 (1975), 373–390.

[57] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.

[58] J. Lagarias, The 3x + 1 problem and its generalizations, Amer. Math. Monthly 92 (1985), 3–23. Available at

    http://www.cecm.sfu.ca/organics/papers/lagarias/index.html

[59] D. G. Larman and N. K. Tamvakis, The decomposition of the n-sphere and the boundaries of plane convex domains, Ann. Discrete Math. 20 (1984), 209–214.

[60] R. P. Lewis and S. P. Norton, On a problem raised by P. J. Cameron, Discrete Math. 138 (1995), 315–318.

[61] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1996.

[62] V. Linek and B. Sands, A note on paths in edge-coloured tournaments, Ars Combinatoria 44 (1996), 225-228.

[63] M. Mahdian, E. S. Mahmoodian, A. Saberi, M. R. Salavatipour and R. Tusserkani, On a conjecture of Keedwell and the cycle double cover conjecture, preprint.

[64] E. S. Mahmoodian, Defining sets and uniqueness in graph colourings: a survey, submitted.

[65] D. Marušič and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, Europ. J. Combinatorics 19 (1998), 707–712.

[66] A. Meyerowitz, Maximal intersecting families, Europ. J. Combinatorics 16 (1995), 491– 501.

[67] H. M. Mulder, The interval function of a graph, Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980.

[68] M. Muzychuk and M. Klin, On graphs with three eigenvalues, in preparation.

[69] C. St.J. A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12.

[70] N. C. K. Phillips and W. D. Wallis, All solutions to a tournament problem. Congressus Numerantium 114 (1996), 193–196.

[71] D. A. Preece, Double Youden rectangles – an update with examples of size 5 × 11, Discrete Math. 125 (1994), 309–317.

[72] B. Randerath and I. Schiermeyer, Colouring graphs with prescribed induced cycle lengths, in Proceedings of SODA’99, to appear

[73] B. Reed, Tree width and tangles: a new cinnectivity measure and some applications, pp. 87–162 in Surveys in Combinatorics, 1997 (ed. R. A. Bailey), London Math. Soc. Lecture Note Series 241, Cambridge University Press, Cambridge, 1997.

[74] N. Robertson, P. Seymour and R. Thomas, Hadwiger’s conjecture for K_{6}-free graphs, Combinatorica 13 (1993), 279–361.

[75] W. Rudin, The automorphisms and the endomorphisms of the group algebra of the unit circle, Acta Math. 95 (1956), 39–56.

[76] B. Sands, N. Sauer, and R. E. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combinatorial Theory (B) 33 (1982), 271–275.

[77] P. D. Seymour, Sums of circuits, pp. 341–355 in Graph Theory and Related Topics (ed. J. A. Bondy and U. S. R. Murty), Academic Press, New York, 1979.

[78] M. Shen, On monochromatic paths in m-coloured tournaments, J. Combinatorial Theory (B) 45 (1988), 108–111.

[79] L. H. Soicher, Yet another distance-regular graph related to a Golay code, Electronic J. Combinatorics 2 (1995), #N1. Available at http://www.combinatorics.org.

[80] L. H. Soicher, On the structure and classification of SOMAs: generalizations of mutually orthogonal Latin squares, Electronic J. Combinatorics, 6(1) (1999), #R32 (15 pages).

    Available at http://www.combinatorics.org.

[81] R. P. Stanley, Ordered Structures and Partitions, Mem. Amer. Math. Soc. 119 (1972).

[82] R. P. Stanley, Enumerative Combinatorics, I, Wadsworth & Brooks, Monterey, 1986.

[83] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570– 590.

[84] H. S. Wilf, generatingfunctionology, Academic Press, San Diego, 1994.

[85] D. R. Woodall, Thrackles and deadlock, pp. 335–347 in Combinatorial Mathematics and its Applications (ed. D. J. A. Welsh), Academic Press, New York, 1971.

[86] N. C. Wormald, Models of random regular graphs, pp. 239–298 in Surveys in Combinatorics, 1999 (ed. J. D. Lamb and D. A. Preece), London Math. Soc. Lecture Notes Series 267, Cambridge University Press, Cambridge, 1999.

[87] P. Yff, On k-conjugacy in a group, Proc. Edinburgh Math. Soc. II 14 (1964), 1-4.

[88] T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combinatorial Theory Ser. B 13 (1972), 116–121.

[89] F. Zara, Graphes lies aux espaces polaires, Europ. J. Combinatorics 5 (1984), 255–290.

[90] F. Zara, Graphes lies aux espaces polaires, II, Europ. J. Combinatorics 8 (1987), 335– 340.