Dates: November 10, 2001

Location: Rutgers University

Organizers: Mike Gargano, Pace University; John Kennedy, New York Academy of Sciences; Lou Quintas, Pace University

Attendance: 55

Graph Theory Day is a semiannual one day event. Its purpose is to stimulate activity and interest among graph theorists by presenting timely and interesting talks by leading researchers. GTD42 was an opportunity to explore various software packages that in one way or another make or prove conjectures involving graph theory. There were demonstrations of conjecture-generating software and opportunities to try out the software.

The program also included time for the informal exchange of graph theory information, as well as a few short contributions to a Graph Theory Notes session.

This event kicked off the activities of the DIMACS Working Group on Computer Generated Conjectures from Graph Theoretic and Chemical Databases.

Dates: November 12 - 16, 2001

Location: Rutgers University

Organizers: Patrick Fowler, University of Exeter; Pierre Hansen, GERAD - University of Montreal

Attendance: 43

The process of scientific discovery is a very complex one. Computers can aid human beings in the process and, as has been a goal of researchers in artificial intelligence, in an automatic way. In the mathematical sciences, discovery can be thought to have three components: development of conjectures, formation of new concepts, and proving of theorems or disproving of conjectures. There has been a large amount of research done on automatic theorem proving. Here, we concentrated on the use of the computer as a tool in generating conjectures, whether in an automated way or as a tool used interactively by a person.

Over the years, a variety of programs have been written to produce mathematical conjectures, either automatically or interactively. Some of these programs have led to very interesting new conjectures and new theorems. An area of particularly widespread activity and interest recently has been graph theory and related areas of chemistry. Researchers from a variety of groups around the world have been working in this area and are engaged in the tasks of using computational power to develop new conjectures, eliminate uninteresting ones, publicize the remaining conjectures, and aid in their solution by working scientists, with or without the aid of the computer. Many of these efforts start with large databases, for example of graph invariants and of relations among them, or of chemical structures. We brought together a group of researchers working on computer generated conjectures from graph-theoretic and chemical databases, including developers of some of the most important programs being used, to share their ideas and systems and initiate joint research efforts.

The primary goals of the working group was to foster an interchange of ideas among those working on different approaches to the use of computers to generate scientific conjectures, mainly in graph theory and in chemistry, and to initiate new collaborative research in this area. We encouraged exchange of views both about methods and about specific conjectures. Among the questions addressed were the following:

• Can we reinforce existing systems that are knowledge-based and put some knowledge-base into other systems?
• Some of the systems consist of protocols for computing graph invariants. How can these be expanded to include broader concepts of graph invariant and combine various constraints?
• Some of the systems in use depend upon a huge number of heuristics and others upon only a few? Are there general principles as to the usefulness of adding more heuristics?
• Are there metaheuristics such as variable neighborhood search that can be usefully employed by a variety of systems?
• What would be involved in broadening the usefulness of existing systems, applying them for example to biological databases?
• Can we define interesting lists of conjectures in terms of novelty, simplicity, generality?
• Can we specialize systems according to the types of conjectures we wish to find, e.g., ``tightest'' ones (those with best possible upper or lower bounds)?
• Can we build ``self-improving'' systems that use results of their search to improve the search process?
• Can any of these systems be applied to cluster analysis, which tries to form subsets of a set that share some common pattern?
• Can any of these systems be applied to, or benefit from, consensus theory, which looks at several objects and tries to form one or more objects that are ``close'' to the original ones?

Index of Special Focus on Data Analysis and Mining

DIMACS Homepage