A Selection of Working Group Accomplishments: Working Group on
Computer-Generated Conjectures from Graph Theoretic and Chemical Databases I

Proving a Computer-generated Conjecture about the Separator of Fullerenes.
It has long been a goal of artificial intelligence to design machines that can think like human beings. A small but quite remarkable research area related to this is concerned with designing machines that can aid in and eventually replace the process of scientific discovery by human beings. In November 2001, the DIMACS working group on Computer Generated Conjectures from Graph-theoretic and Chemical Databases gathered world experts in the use of computers to generate new scientific conjectures. During the working group meeting, a demonstration of the computer program "Graffiti" led to the computer generation of several conjectures about the chemical structures known as fullerenes. Fullerenes are molecular graphs of carbon isomers. The separator of the fullerene is the difference between the two largest eigenvalues of the graph and is very useful in understanding the structure of these important compounds. "Graffiti" generated a conjecture that the separator of fullerenes was always at most $1 - 3/n,$ where $n$ is the number of vertices of the graph, and then the conjecture that the separator is always at most one. The latter, stronger conjecture ended up being true and was proved during the working group meeting by two of the participants, Gilles Caporossi from Montreal and Dragan Stevanovic from Belgrade. The proof led to insights that gave rise to the result that the dodecahedron has the largest separator of all fullerenes. It was fascinating to see the computer generate new scientific conjectures that captured the attention of leading researchers and led to new scientific knowledge.

Bounding the Irregularity of a Connected Graph: Proving Conjectures Generated by Computer.
The program AutoGraphiX was one of the conjecture-generating programs studied by the DIMACS Working Group on Computer-Generated Conjectures from Graph-theoretic and Chemical Databases. In order to understand the ability of this program to find conjectures in an automated way, help to find further conjectures in an assisted way and help to prove conjectures (or to conjecture proof strategies) the problem of the irregularity of a graph, defined by Albertson as $\sum_{(i,j)\in E} \|d_i - d_j\|$ where $d_j$ is the degree of vertex $j$ was studied by Pierre Hansen (V) and Hadrien Melot (V). An upper bound in function of order $n$ and size $m$ for the irregularity of a connected graph was found, and it is best possible in the strong sense, i.e., attained by a graph for all $n$ and $m$ compatible with the existence of a connected graph.

P. Hansen and H. Merlot, "Variable Neighborhood Search for Extremal Graphs. 9. Bounding the Irregularity of a Graph" to appear in DIMACS volume, Computer Generated Conjectures from Graph-theoretic and Chemical Databases

A Selection of Additional Achievements/Accomplishments

Pierre Hansen:

1. The workshop was the occasion of getting thoroughly acquainted with several systems: GRAPH, Graph Theorist, Graffiti, AutoGraphiX, etc. and comparing them. This led to the realization that these systems had some similar and many different functions and that a bright future might be expected due to corss-fertilization. Reflexions along those lines led me to write a long paper on "How Far Should, Is and Could Conjecture Making in Graph Theory be Automated". This paper is submitted for publication in the Proceedings.

2. A recurrent theme at the workshop, and which is quite general, is "What makes a conjecture interesting?". This appears to be hard to answer, and a preliminary question would be "What Forms Have Interesting Conjectures in Graph Theory?". Beginning with the observation that famous (and less famous) theorems in Graph Theory were first conjectures (if only in the minds of those who found them), together with Mustapha Aouchiche, Gilles Caporossi and Dragan Stavanovic, I investigated this question. It appears that a large variety of forms have been considered, that no single system considers all of them and that many forms are untouched. So automated computer-assisted conjecture-making in graph theory while already quite successful is still pretty much at its beginning. A paper on this topic by the four authors mentionned is submitted for publication in the Proceedings.

3. In order to illustrate AutoGraphiX abilities to (a) find conjectures in an automated way. (b) help to find further conjectures in an assisted way and (c) help to prove conjectures (or to conjecture proof strategies) the problem of the irregularity of a graph, defined by Albertson as $\sum_{(i,j)\in E} \|d_i - d_j\|$ where $d_j$ is the degree of vertex $j$ was studied together with Hadrien Melot. An upper bound in function of order $n$ and size $m$ for the irregularity of a connected graph was found, and is best possible in the strong sense, i.e., attained by a graph for all $n$ and $m$ compatible with the existence of a connected graph. A paper entitled "Variable Neighborhood Search for Extremal Graphs. 9. Bounding the Irregularity of a Graph" is accepted for publication in the Proceedings.

4. The workshop was also the occasion for Gunnar Brinkmann, Gilles Caporossi and myself to put the last touch to two papers on chemical graph enumeration resulting from discussions at the DIMACS Workshop on Discrete Mathematical Chemistry in March 1998.

These papers are

Wendy Myrvold, University of Victoria:

One of the main benefits for me of the meeting was the opportunity to meet with Patrick Fowler. I had been working with him by e-mail but we had never had a chance to meet in person before. He gave me a much better understanding as to how the graph theoretic algorithms relate to chemical molecules. We came up with a new idea for an independent set algorithm for fullerenes. I currently have an Honours Project student working on coding that algorithm so its performance can be tested.

I especially enjoyed the talks describing how Graffiti had been used in an education setting. That sounded like a very fun and exciting way to teach graph theory. I probably will not be able to use that here though because I am in a Computer Science department and our Graph Theory courses are offered by the Mathematics department.

I enjoyed discussing with Gunnar Brinkmann the techniques he has been using for generating objects. Some of the ideas we discussed are being used in my Masters student's thesis (Hongmei Wang, Generating Small Embeddings).

I had been assigned as a mentor to Sandra Kingan by the AWM (Association for Women in Mathematics). This conference was my first (and only) opportunity to meet her in person. She is interested in generating small matroids. We discussed that problem and made substantial progress (together with R. Laue) towards formulating a potential generation algorithm.

Reinhard Laue and I had been doing some work together on some problems regarding permutations and projective planes. We wrote some program on the computer at the workshop. Also, I was able to better describe the problem to him and he was able to teach me some group theory (one of my weaknesses). We currently have a very short elegant proof that there are no projective planes of order 6. It uses group theoretic concepts as opposed to the standard approaches which argue by exhaustion that Latin squares of order 6 have no mates. We hope to extend the technique but have not made further progress so far.

The combined effect of all the talks at the conference was to give me a vision as to how one might put together a very powerful research tool which uses the ideas that the participants had presented and combines them into one package. I frequently use the computer to investigate conjectures, but I generally end up writing code from scratch for each application (as well as using nauty) and I have not had the visual interfaces that the participants demonstrated.

So, the conference was extremely beneficial to me. The format permitted interaction with my colleagues. Also, I enjoyed every talk which was given at the conference.

Jack Graver, Syracuse University:

It is a pleasure to write a few words about the DIMACS meeting last November on Computer Generated Conjectures and its effect on my research. Having just moved into a new area of research (using graph theory to model carbon atoms), the interactions with chemists and computer scientists working in that area was extremely valuable. I am not a chemist nor computer scientist and my research is purely theoretical; but its foundation is the body of their results, many of which were computer generated. As a direct result of my interactions with this group, I have submitted four papers and have made significant progress on two others.

Submitted:

In progress:

Craig Larson, University of Houston (graduate student):

The working group meetings were very helpful. I had never met a number of the participants before, many of whom I have since corresponded with by email regarding various questions, including Myrvold, Lisken and Brinkmann. I have a much better understanding now of what Hansen and Caporossi are doing with their program -- which was useful when I was penning my conference paper.

A paper I am just finishing up on a connection between graph-theoretic independence and the stability of fullerenes grew directly out of comments of Fajtlowicz and Fowler at the conference (I expect to be talking about this at NanoSpace 2003). Most everything I've been working on has some connection to the program at DIMACS and I expect collaborations with the participants in the near future.

Reinhard Laue, University of Bayreuth:

The meeting was very useful, hinting to the research groups of Siemion Fajtlowicz, Pisanski and others. We are just experimenting with a database of graphs which we want to discuss with the working group. A preliminary version that demonstrates some of the principles can be found under http://btm2xg.mat.uni-bayreuth.de/GRAPHDB/

We, that is Axel Kohnert and me, are just writing a paper fixing the ideas. The main point is to use an XML-version of the data for exchange and to access the database with popular browsers via the internet. Mathematically, we compute a canonical form to search for a graph. Our own interest lies in finding stored drawings showing symmetries for a graph that stems from theoretical considerations.

Dragan Stevanovic, University of Nis, Yugoslavia:

Definitely. New research collaborations (with Gilles Caporossi) and proofs for couple of Graffiti's conjectures happened already during the conference and that will appear in standard proceedings, as the paper "On Separators of Fullerenes".

During that meeting I also made fruitful contacts with Pierre Hansen, Patrick Fowler and Gunnar Brinkmann, and during this year we wrote a paper "On the smallest eigenvalue of fullerenes" (with Pierre Hansen and Patrick Fowler, accepted for MATCH) and a preprint "On the independence of fullerenes" (with Pierre Hansen and Gunnar Brinkmann, still in preparation).

Besides that, DIMACS meeting also served as a showroom of software for helping research in graph theory. That enabled me to take all their good and bad features into account when specifying a new version of Dragos Cvetkovic's system GRAPH (which is a project financed by Serbian Ministry for Science, Technology and Development).

Jonathan Berry, Lafayette:

The workshop inspired me to formally write his thoughts up on the future of software systems for discrete mathematics. This paper was submitted to the DIMACS volume based on the working group meeting.

Nate Dean, Rice University:

Minimum Energy Carbon Nanotubes

Many different sizes and shapes of nanotubes have been found experimentally and many others proposed because of their expected energetic, structural, and electronic properties. Even with the most advanced algorithms, sophisticated data structures, and parallel computing, directly determining the energetic stability of nanotubes is a quantum mechanical problem which is still beyond our reach. We attack the problem of determining minimum energy configurations of single-walled carbon nanotubes through the use of a nonlinear programming model. The model includes a potential energy function which is minimized subject to constraints on the angular resolution and bond lengths. Our first implementation of this approach seems to consistently produce stable configurations. Because of its importance to physicists and material scientists we will continue this study.

Approach to Molecular Electronics

Molecular electronics is an emerging field that seeks to build faster, cheaper, denser computers from nanoscale devices. The nanocell is a molecular electronics design wherein a random, self-assembled array of molecules and metallic nanoparticles is addressed by a relatively small number of input/output pins. The challenge then is to program, or train the nanocell post-fabrication. As the nanocell can be modeled as a graph (the vertices are nanoparticles and the edges are molecules), discrete algorithms and graph theoretical approaches are useful in solving many problems arising in nanocell training. We have addressed, solved and published our findings regarding several of these problems.

Publications:

This material is based upon work supported by the National Science Foundation under Grant No. 0100921

Up. Index of Special Focus on Data Analysis and Mining
DIMACS Homepage
Contacting the Center
Document last modified on April 29, 2003.