Problems from the First

Anglo-Hungarian Groups and Geometry meeting

This list is quite informal. I have not attributed problems (except to the presenter) or provided references. Some of the problems are well-known. If anyone wants to make additions or corrections, please let me know.

Symmetric graph designs

A symmetric graph design, or SGD, with parameters (n, X, λ, F), (where n and λ are positive integers and X and F are graphs on n vertices), is a set {X_{1}, …, X_{n}} of subgraphs of the complete graph on {1, …, n} having the following properties:

(a) X_{i} ≅ X for i = 1, …, n;

(b) X_{i} ∩ X_{j} ≅ F for i, j = 1, …, n, i ≠ j;

(c) any edge of K_{n} lies in exactly λ of the graphs X_{1}, …, X_{n}.

To avoid degenerate cases, we assume that X is neither the complete nor the null graph on n vertices. Symmetric graph designs generalise symmetric BIBDs (symmetric 2-designs, the case where X = K_{k}, F = K_{λ}). In this case, condition (b) follows from conditions (a) and (c).

Problem: Does condition (b) follow from (a) and (c) in general? Does (c) follow from (a) and (b)?

Peter Cameron

Weakly associative lattices

Let X be a set and ≤ a binary relation on X. Assume that

(a) ≤ is reflexive and antisymmetric;

(b) for x ≠ y, there are exactly λ common upper bounds and λ common lower bounds of x and y, with λ > 1.

Let U(x) = {y ∈ X : x ≤ y}. Then (X, {U(x) : x ∈ X}) is a symmetric 2-design (BIBD).

Conversely, if (X, B) is a symmetric design, and ϕ : X → B is a function satisfying

(c) x ∈ ϕ(x) for all x,

(d) for x ≠ y, x ∈ ϕ(y) implies y ∉ ϕ(x),

and we set x ≤ y if y ∈ ϕ(x), then (a) and (b) hold.

Examples can be obtained from difference sets. For example, if q is a prime power congruent to 3 mod 4, and we take X = GF(q) and set x ≤ y if y − x is a square, then we obtain such a structure.

Problem: Find other examples.

Andras Gács

Reconstruction of words

Let ∼_{k} be the relation on words over the alphabet {a, b} defined as follows: w_{1} ∼_{k} w_{2} if every word of length at most k has the same number of occurrences in w_{1} and w_{2} as a (not necessarily consecutive) subword. Thus, for example, abba ∼_{2} baab.

Problem: Given k, find the smallest n for which there exist distinct words w_{1}, w_{2} of length N satisfying w_{1} ∼_{k} w_{2}.

Peter Sziklai

Covering radius

Given a matrix A over a (finite) field F, there are two structures associated with A:

(a) the matroid (representable over F) whose elements are the columns of A, in which independence means linear independence;

(b) the linear code spanned by the rows of A.

It was proved by Curtis Greene that the weight enumerator of the code is a specialisation of the Tutte polynomial of the code.

The covering radius of a code C ⊆ F^{n} is the least number r such that every element of F^{n} lies at distance r or smaller from some word in C. We have examples of codes with the same weight enumerator but different covering radii.

Problem: Do there exist codes whose associated matroids have the same Tutte polynomial but which have different covering radii?

Carrie Rutherford

A representation group

Consider the following geometry. Let V be a vector space of dimension 2n over GF(2) carrying a symplectic form. The points of the geometry are the totally isotropic subspaces of dimension n; the lines are the totally isotropic subspaces of dimension n−1; and a point and line are incident if one contains the other. Then any line has three points. Let P be the set of points.

Let M_{n} be the elementary abelian 2-group with presentation

M_{n} = ⟨a_{x}(x ∈ P) : a_{x}^{2} = 1, [a_{x}, a_{y}] = 1,
a_{x}a_{y}a_{z} = 1 for each line {x, y, z}⟩.

Problem: Prove the conjecture of Brouwer that

dim M_{n} = 1 + \left[{n \atop 1}\right]_{2} + \left[{n \atop 2}\right]_{2} ,

where \left[{n \atop k}\right]_{q} denotes the number of k-dimensional subspaces of GF(q)^{n}.

Sasha Ivanov

Finitary groups

Let G be a subgroup of FGL(V), where V is an infinite-dimensional vector space over a division ring, and FGL(V) is the group of all finitary linear transformations g of V, those for which the image of g − 1 is finite-dimensional. Suppose that G is torsion-free, irreducible (fixes no proper subspace of V), and primitive (fixes no non-trivial direct decomposition of V).

Problem: Prove the conjecture of Phillips that G has a free normal subgroup.

Chris Pinnock

Generating finite simple groups

Any finite simple group S can be generated by two elements. Let m(S) be the cardinality of the largest subset of S any two of whose elements generate S. How large is m(S)?

In the case S = PSL(d, q), let m′(S) be the cardinality of the largest set of Singer elements of S (that is, elements which act irreducibly on the underlying vector space) any two of which generate S. Is m′(S) = m(S)? If not, is m′(S) ∼ m(S) as |S| → ∞?

Aron Bereczky