Some Open Problems in Algebraic Combinatorics

NOTE: This is not a well-maintained web page. I have recently deleted some of the problems, some because they were solved, others because they were stupid.

Below, I list some of my favourite unsolved problems. But first, a few warnings. Many of these problems have been posed by other people. I will try to give proper attributions, but I am likely to miss someone's name eventually. Many of the problems I know of were posed by Chris Godsil. Secondly, the problems are all confined to areas in which I work. That is, the list is rather narrow in scope and may not seem thematic.

• (folklore) For a set C of q-ary n-tuples, let t denote the strength of C as an orthogonal array and let s denote the degree of C as a code. Prove that there exists a constant k such that t <= s+k. Note that no examples are known having t>s+4.
• (Delsarte, 1973)Do there exist non-trivial perfect codes in the Johnson graphs J(v,k)?
  This question appears in Delsarte's thesis. He ``almost'' conjectures that the answer is NO. The strongest result to date on this is Roos's bound (see Brouwer, et al.). A recent paper by Tuvi Etzion also has nice results (most notably, that the answer is NO if v-2k is prime). I proved that the derived design of a perfect code is always a completely regular code. This gives more leverage to a number-theoretic attack. For example, there are no perfect 2-codes with v<=5000.

• Classify the completely regular one-designs in J(v,k).
  Those with no pair of adjacent vertices are known. But there are many with minimum distance one and these are not classified.
• Find an infinite family of completely regular codes in the Odd graphs.
  Perfect codes in the Odd graphs are an interesting subclass. For example, perfect 1-codes correspond to certain Steiner systems and only two are known, namely 2-(7,3,1) and 4-(11,5,1).
• Assuming that a Moore graph of valency 57 exists, decide whether or not its vertices can be partitioned into 5-cycles in such a way that the induced subgraph between any two is either empty or a perfect matching.
  OK, that's too much to ask for. I can't even solve the following problem:
• (Godsil) Prove that a Moore graph of valency 57 necessarily contains the Petersen graph as an induced subgraph.
• Let (X,S) and (Y,T) be finite simplicial complexes. That is, X and Y are finite sets, S is a collection of subsets of X and T is a collection of subsets of Y with the property that if a set A belongs to either collection, then so do all of the subsets of A. A simplicial map from (X,S) to (Y,T) is a function f:X --> Y such that, for each A in S, f(A) belongs to T. Such a map is locally injective provided, for each A in S, the elements {f(x): x in A} are pairwise distinct in Y. (Clearly, this condition only depends on the one-skeleton of the complex (X,S): we simply seek a proper colouring of this graph where the elements of Y are the colours.)

  Q: Given (X,S) and (Y,T), does there exist such a locally injective simplicial map?

  Exercise: This problem is NP-complete in general.

  Challenges: Find polynomially solvable subclasses of this problem. Find easy-to-verify sufficient conditions for the existence of such a map.

  Application to numerical integration: Let X={(i,j) : 1 <=i<=s, 1<=j<=k} and let
  S={ {(i,j): j<= t_i } : t₁ + . . . + t_s <= t}. Let T={ B subset of Y: |B| <= t}. Find modest conditions on |Y|, s, k which guarantee the existence of our function f.

• Let G be a simple graph, let n and k be integers with k < n . Does there exist a configuration
  { S_x : x a vertex of G} such that each S_x is a k-dimensional subspace of n-dimensional complex space and, whenever two vertices x and y are adjacent, the corresponding subspaces are isoclinic?

  This is a generalisation of the concept of a quantum error-correcting code. In that special case, the graph consists of all 4-ary n-tuples with those pairs at Hamming distance less than some fixed d joined by an edge. But this is not the full story; the configuration of spaces associated to a quantum code is intricately tied to the so-called "error group".