Computer-Generated Conjectures:
a) 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 , 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.
b) 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 where is the degree of
vertex j was studied by Pierre Hansen and Hadrien Melot. 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.
Bounding the Irregularity of a Graph” to appear in DIMACS volume Computer
Generated Conjectures from Graph-theortic and Chemical Databases
c) 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 where 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. 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
- Brinkmann, G., Caporossi, G., Hansen, P., "A Survey
and New Results on Computer Enumeration of Polyhex and Fusene
Hydrocarbons", to appear in Journal of Chemical Information and Computer
Sciences.
- Brinkmann, G., Caporossi, G., Hansen, P., "A
Constructive Enumeration of Fusenes and Benzenoids", Journal of
Algorithms.
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:
The
(m,k)-patch boundary code problem, an 8 typeset page manuscript.
Encoding fullerenes and geodesic domes, a 25 typeset page
manuscript.
The structure of fullerene Signatures, a 29 typeset page
manuscript.
A catalog of all fullerenes with ten or more symmetries, a
22 typeset page manuscript.
In progress:
A complete catalog of nanotube caps. This will be a very long paper or a
monograph. Several parts have been completed.
An extension of The (m,k)-patch boundary code
problem to the continuous case.
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.
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:
- N. Dean, "Mathematical programming model of bond
length and angular resolution for minimum energy carbon nanotubes",
Proceedings of the 2001 1st IEEE Conference on Nanotechnology, (2001) 513-515.
- S. M. Husband, C. P. Husband, N. Dean and J. M. Tour, "Mathematics for the Nanocell Approach
to Molecular Electronics", Graphs and Discovery, the Proceedings of the
DIMACS Workshop on "Computer-Generated Conjectures from Graph Theoretic
and Chemical Databases" - to appear.
- S. M. Husband, C. P. Husband, N. Dean and J. M. Tour, "Mathematical
Details for the Nanocell Approach to Molecular Electronics", submitted to
Discrete Applied Mathematics.
This material is based upon work supported by the National Science Foundation under Grant No. 0100921