Computers in Scientific Discovery III - Goals

Background

This workshop will be the third in a series that started in November 2001 with the Workshop of the DIMACS Working group on Computer-Generated Conjectures from Graph Theoretic and Chemical Databases at DIMACS, and extends a theme from the earlier Discrete Mathematical Chemistry workshop that took place at DIMACS in 1998. All of these events were well attended, with participation from North America and Europe, and showed the existence of a community of researchers active at the interfaces between chemistry, computer science and discrete mathematics. Two AMS proceedings volumes have been generated under the DIMACS aegis (Discrete Mathematical Chemistry). A survey volume based in part on the 2004 workshop is in the planning stage.

The latest workshop in the series took place in June 2004 in Montreal, under the title Computers and Discovery. This time the scope was a little different -- concentrating more on the philosophy, nature and mechanics of the conjecture-making activity and somewhat less on the possible applications in theoretical chemistry and related subjects. Nevertheless, several chemical and broader mathematical software collaborative applications were initiated, such as the "House of Graphs" concept proposed by Pierre Hansen, which aims to align the efforts of a number of groups working worldwide in the area of implementing graph algorithms and developing user interfaces for automation, in whole or part, of graph handling and conjecture making.

This aspect of computer implementation, with direct contact to potential scientific users, which played a background role in the most recent workshop, will play a more central role in the next. In order to keep the developers of mathematical software in touch with possible and likely applications in theoretical chemistry, in the third workshop we will re-emphasize the theoretical/mathematical chemistry applications and extend the scope to mathematical biology and bioinformatics. These are areas that have been richly developed in both Europe and North America, and by holding this latest meeting on a different side of the Atlantic, we hope to encourage wider participation. It is important that the strong connections and co-operations resulting from the previous workshops be maintained and that those already working on the various mathematical and software projects presented at previous workshops come into early contact with potential users and applications in other fields. Much of the importance of these interdisciplinary meetings comes from their influence in breaking down 'language barriers' between fields, and in opening the eyes of researchers in one field to the expertise available in another. The workshop format, with formal presentations from invited speakers but plenty of time for structured and free discussion between active researchers, should facilitate these aims.

Applications for Chemistry

One scientific emphasis of the meeting will be on the manifold applications of Graph Theory in Chemistry. Graph theory originally emerged from investigations of chemical problems connected with isomerism and established itself as a main tool of qualitative electronic structure theory with the study of unsaturated carbon-based systems. Perhaps not all chemists know it, but when they perform Hückel calculations on π systems, they are in fact dealing with properties of adjacency matrices of molecular graphs. With the revolution in carbon chemistry and physics that stemmed from the discovery of the fullerenes, graph theory has come to new prominence in chemistry, as a means of obtaining systematic qualitative information about isomerism, shape, stability, electronic structure and reactivity of these previously unsuspected forms of the most well-studied element in the Periodic Table. An exciting spin-off from this frenetic activity (over 10,000 papers in chemistry and physics journals in the past decade) has been the upsurge of mathematical interest in the graphs and polyhedra related to the fullerenes, with participation of a number of mathematicians in a conferences on cluster molecules (ZiF, Bielefeld, 1998), graph invariants in chemistry (Bielefeld 2002) and bi-faced polyhedra (Pohang, Korea, 2004), and contributions from mathematical chemists to mainstream mathematical conferences (Canadian Mathematical Society, Montreal, 1999, Algebraic Graph Theory meeting, Edinburgh, 2001, Group24 on applications of groups in physics and chemistry, Paris, 2003), all in addition to the DIMACS workshop series. This in turn has suggested new directions for chemical application, for example, the use of independence numbers as indicators of stable addition patterns in fullerene compounds.

A main challenge in this multidisciplinary area, and one that will be addressed at the workshop, is the relation between graph invariants and real-world applications. It is clear that many of the classical graph invariants have a role in chemistry -- theories of molecular electronic structure depend on properties of the adjacency eigenvalue spectrum, qualitative theories of stability invoke the Kekule count or number of perfect matchings, and in the fullerene area counting of pentagon-pentagon adjacencies gives a first filter to separate stable and unstable isomers, and independence number an indication of limits to chemical reactivity.

However, proliferation of graph invariants in the mathematical chemistry literature has produced literally hundreds of mathematical objects with claims for chemical and physical relevance, and the field is in danger of being choked by its own creativity. There are two directions in which a timely workshop can help: assessment of the practical utility of the more promising invariants, and grouping of the invariants into families that carry similar information content. This is a fruitful area for collaboration, in which knowledge of the scientific background, technical expertise in computation of invariants, and theories for classification all have a role. Invitations to the workshop will be used to assemble a concerted attack on this problem.

Applications for Bioinformatics

In this workshop we also want to make a first approach in the direction of bioinformatics, to see whether invariants may be helpful in that field. Alhough the applications of the techniques discussed in the previous workshops are not as obvious in bioinformatics as they are in chemistry, graph theory is clearly used in mathematical biology as a whole. Discussions in the recent literature of brain network topologies involve the identification and enumeration of 'motifs' -- in fact subgraphs. There also exist graph-theoretical connections in phylogeny reconstruction and related problems. The workshop atmosphere of the meeting will give enough room to discuss possible applications of the tools developed by the various mathematical and computer science groups also in the field of bioinformatics.

Applications for Conjecture making

Applications in the physical and life sciences will be one, but not the only, topic of the workshop. The area of topological invariants has been a fertile one for the making of conjectures, and for the study of the conjecture-making process, with varying proportions of user input vs. automation. In the program Graffiti.pc, for example, the objects abstractly called 'concepts' are in fact what a chemist would call topological invariants, and the various notions of relatedness of concepts used in conjecture automation express degrees of similarity between invariants. The topic was intensively discussed at the earlier workshops, and has seen considerable recent progress which it will be timely to review and consolidate in the new meeting.

Applications for Mathematical Education

Another field of application to be discussed in the workshop is the application of graph-theory and conjecture-making software in teaching. Some early steps in this direction were taken some years ago by Chinn, who used the graph-theory program INGRID in her courses. More recently, the program GRAFFITI was adapted and GRAFFITI-PC created for use in teaching graph theory at University level and through a collaboration with DeLaVina (Houston), initiated at a previous DIMACS workshop, one of the organisers is exploring the use of Graffiti-PC in teaching mathematics. Gunnar Brinkmann gave a course for high-school teachers using this software and the University of Ghent has a 4-year PhD project to develop a completely new version that is on one hand better suited for use in education, taking into account the proposals of the high-school teachers during the course, and on the other hand extendable so that the user can add invariants in a simple way as, e.g., in newGRAPH. The latter feature will make it likely that the software will be used in a research context, by chemistry researchers as well as mathematicians, to examine relations between invariants. The aim is to develop a new version where easy use in schools as well as in research and even industry are already built-in right from the beginning and are assured by basic design features of extendability and the possibility of using plug-ins.

Another approach, which again can be seen in both teaching and research contexts, is offered by the AGX software, in which users pose questions for exploration by sophisticated search and optimisation routines within a chosen class of graphs. The Ghent development work will be done in close cooperation with the groups in Niš, Montreal and Houston, and there will be talks and demonstrations from all the contributing groups on the new programs and their possible classroom and research use.