What are the major open problems in design theory nowaday?

Question

I gather that the question whether the Bruck-Chowla-Ryser condition was sufficient used to top the list, but now that that's settled - what is considered the most interesting open question?

Answer 1

Edit: Since this just became available on arXiv, Peter Keevash solved the existence conjecture of Steiner $t$-designs, which means that what I wrote below a year ago as one of the most important open problems in design theory is now settled.

Here's a brief summary of the history of progress on Gil Kalai's blog "Combinatorics and more":

http://gilkalai.wordpress.com/2014/01/16/amazing-peter-keevash-constructed-general-steiner-systems-and-designs/

Congratulations, Peter Keevash!

---

I think this kind of question is inherently subjective, but I'll try my best to be as objective as possible by limiting myself to the classical kind of stuff that is expected to be covered in a well-rounded graduate level textbook if published in 2013. I also deliberately avoid repeating what is already said in The Princeton Companion to Mathematics. Also omitted are things that are clearly mentioned by Colbourn's "Opening the Door" and Anderson, Colbourn, Dinitz, Griggs' "Design Theory: Antiquity to 1950" in the Handbook of Combinatorial Designs.

One more caveat is that I personally don't see some branches of mathematics like coding theory and finite geometry any different than design theory. So my view must be biased toward interactions with those adjacent fileds, and I wouldn't be surprised if hardcore design theorists disagree with me at every turn in my post.

To clarify what I mean by the above caveat, for instance, take the Bruck-Chowla-Ryser theorem you brought up. If you see it from a finite geometric viewpoint, you can rule out the existence of finite projective planes of order $6$ and $14$. But as you mentioned, Lam proved the nonexistence of such planes of order $10$. So, to my eye, it's definitely one of the most interesting problems whether finite projective planes exist only for prime and prime power orders. Similarly, because many problems in coding theory are of design theory to me, a large chunk of my answer to "What's hot topics in error-correcting codes?" asked by Alex on MO counts as one of the more interesting problems in design theory. But I don't think every design theorist agrees with me here.

Anyway, one of the most important open problems about objects with the word "design" in their names is, in my opinion, the existence of Steiner $t$-designs. For total newbies, a Steiner $t$-design block size $k$ is an ordered pair $(V, \mathcal{B})$ of finite sets $V$ and $\mathcal{B}$, where $\mathcal{B}$ is a set of $k$-subsets of $V$ such that any $t$-subset of $V$ is contained in exactly one element of $\mathcal{B}$. The cardinality $\vert V \vert$ is the order of the design. A Steiner $t$-design of order $v$ and block size $k$ is written as $S(t,k,v)$. (Infinite Steiner designs have also been considered in design theory, but they haven't caught on, at least not yet.)

One of the main goals is to understand the spectrum of those parameters that admit the existence of an $S(t,k,v)$. The problem is said to originate Kirkman's study in the 19th century, and elementary combinatorics works relatively well for small $t$. The problem becomes extremely difficult for large $t$.

The most successful methods for finding $S(t,k,v)$s with larger $t$ is investigating interesting finite groups. For instance, as I said in the linked answer to Alex's question about coding theory, the known $S(5,8,24)$ has the the Mathieu group $M_{24}$ as its automorphism group. It is very interesting and often powerful to see interactions between $S(t,k,v)$s and, say, sporadic simple groups. But this line of work soon hits the wall because, for example, you would like to use a $t$-transitive group to find an $S(t,k,v)$ in its orbit and, alas, there are no $6$-transitive groups (other than the symmetric groups and the alternating groups). In fact, there are no known nontrivial $S(t,k,v)$ for $t \geq 6$ when apparently there isn't any plausible argument against their existence.

Wilson's existence theory (aka Wilson's Fundamental Construction published as a series of papers in J. Combin. Theory Ser. A) takes a different approach and proves, as its corollary, that the necessary conditions for the existence of an $S(2,k,v)$ (which can be obtained by a simple counting argument) are always sufficient for sufficiently large $v$. So, for $t=2$, the problem is solved in an asymptotic sense. This approach is very design theoretic (or the definition of "design theoretic" had changed a little by this), and there have been effort to generalize it to the case $t \geq 3$. Unfortunately, we've seen rather limited success, and while the case when $t=3$ has made some progress, only finitely many $S(t,k,v)$s are known for $t \geq 4$.

Steiner $t$-designs have numerous applications to other fields both inside and outside mathematics. This one-century-and-a-half old study gave a new, solid foundation to design theory by tidying up the mess of ad hoc techniques. So, I vote for "developing a general theory of existence of $S(t,k,v)$s" as one of the most interesting problems in design theory. (If you're familiar with design theory and are wondering why I put Wilson's existence theory only in the context of $S(t,k,v)s$ and not of $t$-designs of larger index $\lambda$, that's because such designs exist if $\lambda$ is sufficiently large, and also because the larger $\lambda$ case is mentioned in the intro section of the Handbook, which disqualifies the problem.)

But there are many other important and intriguing problems out there in design theory. For instance, the existence of difference sets is classical and has always been in the center of design theory because of its intrinsic importance (perceived by many) and connections to other fields. The recent revival of additive combinatorics/number theory may be a big push to the study of difference sets as well. It is closely related to the study of symmetric designs, which is already mentioned by Chris. Those classical problems like MOLS and others are often related and inter-winded. So, any of them is equally interesting, at least to my eye.

Also, as is the case with any other branch of math, design theory has also been driven by interactions with other fields. For instance, spherical $t$-designs are gaining more and more attention not only because of its combinatorial appeal but also because of its applications to numerical analysis, quantum information, and so on. So, the study of these types of designs may have a different flavor than traditional design theory like the one stemming from the Bruck-Chowla-Ryser theorem, but I think it's definitely among the most important subfields of combinatorial design theory.

Answer 2

Fix $\lambda>1$. Are there infinitely many symmetric $(v,k,\lambda)$ designs? (The Hadamard conjectures would be at the top of my list though.)

Answer 3

These four below problems are interesting and still open conjecture in design theory and its related topics:

$1.$ There exist Ucycles for $k$-subsets of $[n]$, provided $k$ divides $Cr(n-1,k-1)$ and $n$ is sufficiently large.

$2.$ For $n≥6$ even, it is not possible to have a length $\frac{n^2}{2}$ cyclic covering word for the $(n−2)$-subsets of an $n$-set.

$3.$ For each $k≥3$, there exists a constant $c_k$ such that for all $v≥c_k$ and $λ≥1$, the $1$ block-intersection graph of any $BIBD(v,k,λ)$ is Hamiltonian.

$4.$ For each $k≥3$, there exists a constant $c_k$ such that for all $v≥c_k$ and $λ≥1$, the ${1,2}$-block-intersection graph of any $BIBD(v,k,λ)$ is Hamiltonian.

These four conjectures are respectively from:

$1.$ Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discrete Math.110, 43–59 (1992)

$2.$ Stevens, B., Buskell, P., Ecimovic, P., Ivanescu, C., Malik, A., Savu, A., Vassilev, T., Verrall, H., Yang, B., Zhao, Z.: Solution of an outstanding conjecture: the non-existence of universal cycles withk=n−2. Discrete Math.258, 193–204 (2002)

$3.$ Jesso, Andrew T.(3-NF); Pike, David A.(3-NF); Shalaby, Nabil(3-NF) Hamilton cycles in restricted block-intersection graphs. (English summary) Des. Codes Cryptogr.61(3), 345–353

$Also,$ I believe that Hadamard conjecture is a nice diamond in the conjectures land.

Answer 4

Personally, I am most interested in design theory with an "asymptotic flavor", and I think there are (edit: were, pre-Keevash) some very interesting open questions in this direction.

To cut to the chase, I think asymptotic design theory today is effectively searching for a constructive proof of Gustavsson's Theorem: All "admissible" graphs $G$ which are sufficiently large and dense (i.e. $\delta(G) \gtrapprox (1-\epsilon(k)) v$) can be edge-decomposed into cliques of size $k$.

There are loads of spin-off questions, such as completion of sparse partial latin squares, construction of optimal packings and coverings, or imposing extra structure on the graph decompositions.

(edit: I do agree that the Hadamard conjecture is bigger, for sure.)