“Future Directions in Applied and Theoretical Combinatorics”: A View from a Corner

An experimental format for a research meeting

What would happen if thirteen mathematicians were to meet for twelve hours a day for three days with only five presentations around one gigantic table? That’s exactly what happened at the University of Richmond, Virginia in September 2002, at a meeting on “Future Directions in Applied and Theoretical Combinatorics”. Overlooking the reflective campus lake and green lawns, lively conversation in a relaxed atmosphere continued late into the evening. Discussion of questions and issues well beyond the scope of the traditional conference model created a unique and exciting meeting for all the participants.

The organizers designed the meeting with fond memories of their invitations to the Mathematics Institute at Oberwolfach in mind. The University kindly granted exclusive use of the peaceful and attractive setting of the Trustees’ Suite, with excellent meals catered in an adjoining room. There was ample time to stroll outdoors and to chat informally. Apart from the five scheduled talks, the entire meeting time was reserved for extended discussion of the meaning and significance of the presented results, and a wide-ranging exploration of more general themes as they emerged.

The presenters were asked to talk about an influential result (not necessarily their own), explaining from first principles the context, what was achieved, and why they considered this significant and interesting. They were asked to keep their one-hour talks completely accessible to the entire group by emphasizing principles and methods rather than specialist technical details, and to give presentations that would act as a springboard to more general discussion. The presentations covered a range of applications as diverse as testing for HIV efficiently using pooled blood tests, improving cellular phone reception via multiple antennas, and overcoming physical limitations in designing a hypothetical quantum computer. The presentations involved many technical areas and their interconnections, including coding theory, design theory, finite geometry, combinatorial optimization and Ramsey theory.

In the ensuing discussions the group considered questions such as: What is the central novelty of the result and where else might these methods be applied? What role can combinatorics play in interdisciplinary research? Are new and correct results always deserving of publication? When are computational approaches valuable in combinatorics? What impact does the structure of reward systems have?

The distinguishing feature of the meeting was the central role allocated to unusually extended group discussion, which allowed for a deep level of reflection about the subject and an exploration of themes that are seldom addressed explicitly in public. Although stepping back to critique one’s own subject is an unconventional activity for many mathematicians, at least in a formal setting, we found that for the most part the conversation flowed easily. Occasional differences of opinion acted as a positive stimulus and sometimes suggested new themes for exploration.

We feel that the number of participants was well suited to the discussion-based format. We were very pleased to include one participant whose research interests are mostly peripheral to the subject, who was often able to help the rest of us to see things from an outsider’s point of view. If we were to repeat the experimental meeting format we would certainly wish to retain this feature. We also found it useful for one of the participants to take notes of the discussion sessions and to circulate a very rough preliminary draft of this report midway through the meeting. In this way we were able to identify points of potentially serious disagreement early on and resolve them before closing the meeting. The final session was devoted to discussion of the form, content, and means of publication of this report.

We hope this report will encourage others within the mathematical community to experiment with alternative meeting formats. We also hope to spark a discussion about some of the general issues that emerged. However we recognize that our areas of expertise, while not identical, do not collectively represent any more than a “corner” of the broad study of combinatorics – hence the title of this article. Likewise the examples in the text, which are drawn largely from our personal experience, are intended to be illustrative rather than prescriptive. In short, we do not claim to represent anyone other than ourselves, recognizing that the composition of the group was determined simply by personal preference of the organizers. Finally, if some of our observations appear to be obvious we can only say that they did not appear so to several of us for many years!

In the rest of this report we describe the general themes that emerged from the presentations and discussions.

What role can combinatorics play in interdisciplinary research?

A recurring theme in our discussion was the relationship between theory and application. We believe that it is highly productive when there is a “dynamic tension” (in other words a continual interplay) between theory and application, with each one enriching the other. When this tension is present, the evolving applications context helps to define new areas of theory and provides a criterion for what is considered interesting. In turn the development of a fundamental theory from specific examples of applied solutions can reveal a general underlying structure that will lead to better applied solutions in the future. On the other hand if this tension is absent then there is a risk that the theory will become detached from its original applications context and no longer relevant there. For example, the Gaussian channel seems to have become an object of study in its own right in communications theory, even though other channels such as wireless recently offered the opportunity for coding gains two orders of magnitude greater (expressed in dB).

We believe that the model of theory and application continually developing in tandem with each other is a very fruitful one for combinatorics as part of an interdisciplinary research effort. Those of us that have worked within teams drawn from diverse disciplines in order to solve applied problems have found that:

In our experience, the successful application of combinatorics in interdisciplinary teams depends to some extent on luck and opportunism. However it seems that preparatory steps such as the following can increase the chances of success: maintaining a large combinatorial toolkit; seeking out experts in other disciplines to discuss their pressing issues; and constantly updating one’s view as to what the important issues are according to developments in both theory and application.

Are new and correct results always deserving of publication?

We would argue that, to be deserving of publication, a result should in some sense be “interesting” as well as new and correct. While it would be difficult to provide a precise definition of when a problem or result is interesting we identified certain characteristics, one or more of which might well be present. “Interesting” problems can often be related to other mathematical structures and sometimes occur naturally as the solution to an applied problem. They might have resisted attack for a long time, and their study can lead to better insights and tools even if a solution is not reached. An “interesting” result often allows a better understanding of some underlying structure or provides a simpler explanation for observed phenomena. A solution that is unexpected, or that unifies results previously thought to be unrelated, is likely to be “interesting” whereas an incremental result that uses routine techniques is not.

This point arose many times during the discussions, particularly in connection with the practice of compiling tables of combinatorial results. Such tables can be tremendously useful in summarizing the state of knowledge about a subject, making it more accessible to other researchers, directing attention to particular unsolved cases of special interest, and allowing larger patterns to be spotted. However we feel there is also a danger that, beyond a certain point, filling in missing table entries can become an objective in its own right without necessarily leading to increased understanding. Indeed it is even possible that the publication of too much data can obscure rather than clarify a subject. In our opinion an example of this would be the study of Hadamard matrices, where the original compilation of tables helped to spur many advances but where reaching a better understanding of what is already known would now be preferable to finding and publishing new examples.

A view from a corner of an interesting combinatorial table

Computational approaches in combinatorics: opportunities and pitfalls

The explosive growth in computer power of recent years presents an opportunity to incorporate computational exploration as an essential component of much combinatorial research. In this model, researchers explore a large search space by computer, discover patterns amongst key examples, formulate and test conjectures based on these patterns, and ultimately prove some of the conjectures either via traditional methods or else by introducing new methods which in turn further enrich the subject. We believe this is a powerful model, especially when there is insufficient data at the outset even to guess what a general solution might look like. For example, recent work generalizing the classical binary Singer difference sets to produce infinite p-ary families followed this model, with researchers publishing the computational evidence for their conjectures (for example in [1]) and so allowing others to complete the process with a proof. Many parts of combinatorics, particularly those that are highly accessible, seem to lend themselves readily to such a model of discovery.

However there are also potential pitfalls associated with this approach. It is not always easy to know in advance which examples will turn out to be key. If too much data is built up it can become very difficult to determine underlying patterns, as mentioned earlier. Regular behaviour might not actually emerge until the objects involved become very large and this might become apparent only with hindsight. Consequently the decision as to whether to publish the results of computational exploration that have not yet been fully explained seems to require careful judgement on the part of author, referee and editor. Some researchers choose to maintain collections of such results via the Web but this demands significant effort that is not always recognised as worthwhile by employers. 

An occasional large enumerative computer search, while not necessarily increasing understanding, can be useful in indicating the limit of exhaustive computation with given resources, a limit which continues to increase dramatically. We would view the recent calculation of the precise number of Steiner triple systems on 19 points (in excess of 11 billion) [2] in this light.

There seems to be little doubt that the introduction of symbolic algebra packages has transformed the way many combinatorialists (and other mathematicians) work. One participant went so far as to declare the development of these packages to be “the most significant mathematical event of the last 25 years”. Another remarked during his presentation that while attempting to solve a problem he incorrectly typed a formula into such a package; when the software returned an unexpected identity he discovered he was able to use this as part of the solution!

The impact of reward systems

We believe that universities, funding agencies, and technology companies can significantly influence scientific development, both positively and negatively, according to their choice of reward systems.

For example, a university or company wishing to raise its scientific profile via publication might choose to reward individual employees according to a simple count of their published papers. Indeed, we are aware of more than one such organisation. A policy like this is likely to encourage the publication of a large number of papers of lower quality than one employing a more careful measure of scientific impact. The overall effect might well be the opposite of what was intended, namely to reduce the standing of the organization in the scientific community. Similar unintended effects can easily result from policies which appear to be widespread, such as making funding for conference attendance conditional on the acceptance of a submitted presentation abstract.

In another example, journals and funding bodies seeking to encourage interplay between mathematics and other disciplines sometimes require mathematical authors to include in their submission a description of “relevant applications”, regardless of the actual purpose of the research. This can inadvertently produce an incentive to write papers and funding proposals that claim a motivating applications context even when it has not been convincingly demonstrated. The effect might actually be to persuade the knowledgeable reader of the lack of relevance of the mathematical area to the claimed application.

It is clearly difficult to anticipate all possible consequences of a reward system designed to encourage a specific outcome. But our belief and experience is that a carefully-designed reward system, matching deed with word, really can achieve a desired objective. For example one university, wishing to encourage interdisciplinary research, has made it a requirement at tenure hearings to produce documented evidence of having carried out research across departments. This clearly demonstrates support for the stated goal, and contrasts with another university at which supposed enthusiasm for joint appointments between departments does not always translate into practical or financial support. Consequently, at this latter institution, proposals for such appointments tend to be viewed with suspicion by members of both affected departments.

Conclusions

We find combinatorics (or at least the “corner” with which we are familiar) to be a fascinating and accessible study. It commands a considerable body of theory of great intrinsic beauty that is intimately linked to many other branches of mathematics. At the same time it has played a powerful enabling role in applications over several decades, particularly in digital communications, and appears ideally suited to future interdisciplinary research in several application areas. Two likely areas of important future application are computational biology, which would benefit from more efficient computational algorithms for genome mapping, and medicine, which in the view of one participant “is becoming a branch of signal processing”.

We believe that a dynamic tension between theory and application is healthy for the development of both. While not all applied problems will lead to interesting theory, and some theory developed in isolation may eventually be applied, the model of continually monitoring both theory and application as they develop in tandem with each other appears to be very fruitful.

We propose that, to be deserving of publication, it is not sufficient for a combinatorial (or other mathematical) result only to be new and correct: it should also be “interesting” in some sense as well. The compilation of combinatorial tables can clarify the status of a subject and act as a stimulus for further research but carries a danger that the filling in of missing table entries will become an end in itself.

The availability of ever greater computer power offers the opportunity to conduct much combinatorial research according to a model of initial computational exploration followed by pattern-spotting, conjecture-making and testing, and ultimately proof. It is a delicate decision as to whether and how to publish the results of computational exploration prior to the final proof step having been achieved.

The structure of a reward system by universities, funding agencies, and technology companies often determines in large part whether its intended goals will be met. We suggest that careful design of these systems stimulates the development of good and interesting combinatorics (and other science).

The Small Print

The participants at the September 2002 meeting on “Future Directions in Applied and Theoretical Combinatorics” were Peter Borwein, Rob Calderbank, Charlie Colbourn, Jim Davis, John Dillon, Jeff Dinitz, Gary Ebert, Jonathan Jedwab, Bill Kantor, Bob Liebler, Alex Pott, Rick Wilson, and Qing Xiang. The meeting was organized by Jim Davis and Jonathan Jedwab.

The presentations that motivated our discussions were:

John Dillon – Perfect sequences and difference sets with Singer parameters
Charlie Colbourn – Using combinatorial designs to test for defectives
Rob Calderbank – Combinatorics, quantum computers and cellular phones
Peter Borwein – Three highly computational problems somewhere between Diophantine number theory and combinatorics
Rick Wilson – Incidence matrices of t-subsets and hypergraphs.

We are very grateful to the University of Richmond for hosting the meeting.

References

[1] J.-S. No, S.W. Golomb, G. Gong, H.-K. Lee and P. Gaal, “Binary pseudorandom sequences of period 2n-1 with ideal autocorrelation”, IEEE Trans. Inform. Theory 44 (1998), 814-817.

[2] P. Kaski and P.R.J. Östergĺrd, “The Steiner triple systems of order 19”, available from <http://tltpc54.hut.fi/>.

 

Hit Counter