To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
This volume resulted from scientific discussions of the DIMACS "Working Group" on "Computer-Generated Conjectures from Graph Theoretic and Chemical Databases." A "working group" at DIMACS consists of researchers with expertise in the field and/or in one of the applications areas. DIMACS brings these working groups together for a first meeting with informal presentations and lots of time for discussion and interaction. There is often also a proximate public workshop with more formal presentations. Working groups formulate problems, share ideas and approaches, and set an agenda for future interactions which are pursued in small subgroups, follow-up meetings, and individual collaborations.
The members of the working group on "Computer-Generated Conjectures" represent the variety of disciplines that have contributed to the literature of this subject. They include theoretical and applied computer scientists, statisticians, discrete and non-discrete mathematicians, chemists, information theorists, and others.
The Computer-Generated Conjectures Working Group held a meeting at DIMACS on November 12-16, 2001, preceded by a public meeting on November 10, 2001 in conjunction with the New York Area "Graph Theory Day" meeting sponsored jointly with the New York Academy of Science. The organizers of the working group meeting were Patrick Fowler and Pierre Hansen. The organizers of the Graph Theory Day event were Michael Gargano and Louis Quintas (Pace University), John W. Kennedy (Queens College), as well as Fred Roberts and Mel Janowitz of DIMACS.
Both events involved some very lively and productive discussions. Several open problems were resolved during these discussions, and a number of successful research collaborations were begun. Details of all this may be accessed through the working group web page. This can be found at the following address: http://dimacs.rutgers.edu/archive/SpecialYears/2001 Data/Conjectures/index.
The Process of Discovery in the Mathematical Sciences
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, sometimes 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. In this volume, we concentrate 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 hav eled 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. This volume presents the work of a variety of researchers working on computer-generated conjectures from graph-theoretic and chemical databases, including developers of some of the most important programs being used around the world. It is hoped that the volume will introduce many other researchers and students to this fascinating field.
Software for Automatic Generation of Conjectures
The use of computers in scientific discovery, and in particular in the development of mathematical conjectures, is not new. The paper by Larsen [46] surveys automatic conjecture-generating software, tracing it back to the work of Wang in the late 1950's. (See [51].)
Graffiti, a program developed by Siemion Fajtlowicz, was introduced in 1986. For a given set of invariants, conjectures are automatically generated and tested on a database of examples. The system discards many of the conjectures automatically, for instance those implied by others. The most interesting conjectures are proposed to the community of researchers and counterexamples that are produced are added to the database. There are now over 900 conjectures developed through Graffiti, many in graph theory and related areas of chemistry, but others in geometry, number theory, and other fields. See the URL http://www.math.uh.edu/~clarson/#fajt. This website provides information about the current status of these conjectures - open, refuted, or proved - and on developments related to these conjectures, such as new conjectures or theorems. Early descriptions of the Graffiti system can be found in a series of papers [29, 30, 31, 32, 33]. Some of the world's most distinguished graph theorists have worked on the conjectures generated by Graffiti. They include Noga Alon, Bela Bollobas, Fan Chung, Paul Erdos, Jerry Griggs, Daniel Kleitman, Laszlo Lovasz, Paul Seymour, and Joel Spencer. (See [4, 17, 27, 28, 39, 43] for examples.) Among the more exciting products of Graffiti are conjectures in chemistry on the structure of fullerenes (as represented by graphs). The papers by Patrick Fowler and colleagues, one, [37], motivated by Graffiti, show how some very simple ideas of symmetry, geometry, and graph theory can be used to count, construct, and classify fullerenes and make predictions about the types and structures of their chemical derivatives. See [38]. As an aside, we comment on the chemistry involved. The main point of much of the conjecture-generating software we are summarizing is to use theory to give models and physical pictures that can be used to understand complicated chemical systems. The all-carbon fullerenes give an example of a relatively new class of molecules for which these conjecture-generating systems have already been very useful. Among the questions of interest about these molecules are: How many fullerenes are there? Which have greatest overall stability? What are their likely patterns of reactivity? Graph theory can be used to answer some of these questions since fullerenes can be viewed as planar cubic graphs having only faces of size 5 or 6. Collaborations between chemists and graph theorists in the working group follow on collaborations stimulated by the DIMACS workshop on Discrete Mathematical Chemistry ([42]) and through workshops on computational chemistry in the DIMACS Special Year on Mathematical Support for Molecular Biology (see http://dimacs.rutgers.edu/archive/SpecialYears/1994 1995/index.html).
The system INGRID was developed by Robert Brigham, Ronald Dutton, and Felix Gomez in the late 1980's. INGRID was used to generate patterns, thus suggesting conjectures to its users, with an emphasis on parameters of graph theory. This system and results obtained from it are summarized in [5] and [8]. INGRID automatically bounded invariants of graphs from values for some given invariants stored in a database and by manipulation of a database of formulas between graph invariants. A summary of results obtained by INGRID can be found in [6, 7]. Whether or not INGRID can be said to have "automatically generated conjectures" or even to have "generated conjectures" is a point of dispute to which we return below.
The AutoGraphiX (AGX) system was developed more recently by Pierre Hansen and co-workers at GERAD, HEC Montreal. See the paper [14] for an introduction to this system. The AGX system is designed to find (heuristically) extremal graphs for some invariant. To that effect, Caporossi and Hansen [14] have made use of a "variable neighborhood search" metaheuristic within AGX, developed by viewing the conjecture generation task as a combinatorial optimization problem on an infinite family of graphs. By making use of parametrization, the system produces a set of presumably extremal graphs in an automated way. Conjectures can then be found either interactively or automatically. In the latter case, the process exploits a numerical approach based upon principle components analysis, a geometric approach using the notion of convex hull in a space of chosen invariants, or an algebraic approach based on graph recognition and known relations among families of graphs. In applications in graph theory, AGX has been used, for example, to obtain results about the largest eigenvalue for color-constrained trees (see [22]). In applications related to chemistry, the system AGX has been used to obtain bounds for the connectivity of chemical trees and for the "energy" of a graph, a problem for which much more complicated bounds had previously been obtained. See [12, 13]. It has also found tight bounds on extremal chemical graphs for the much-studied Randic index (see [13]).
An earlier system we should mention is called GRAPH (see [19]). This system, due to Dragos Cvetkovic and colleagues, is aimed at enhancing the capacity of the graph theorist to explore graphs and families of related graphs through computation of invariants and visualization. In an updated survey [21] on GRAPH in this volume, by Cvetkovic and Simic, 92 papers using it are mentioned. Brief mention should also be made of the system HR (for Hardy-Ramanujan) that was developed by Simon Colton and others to form concepts, make conjectures, and use a theorem prover and model generator to prove or disprove those conjectures. HR has so far produced conjectures in group theory, number theory, and graph theory. See [10, 11, 18].
Other Relevant Software
We mention a number of other systems that do not generate conjectures automatically, but have been widely used as tools in scientific discovery/conjecture generation and also in education in discrete mathematics.
The LINK software system was developed at DIMACS starting in 1991. (See paper [3] and see the URL http://dimacs.rutgers.edu/archive/~berryj/LINK.html.) LINK resulted from the DIMACS workshop on Software for Discrete Mathematics, during which DIMACS brought together researchers working on software from different points of view, using different platforms, emphasizing different fields of discrete mathematics. (See [23].) LINK is a software system designed to be a general-purpose environment for experimentation with discrete mathematics. The environment is friendly enough for non-technical users to be able to visualize problems easily, yet powerful enough for computer scientists and mathematicians to express complicated computations. The system is designed to support educational pursuits, to be used as a research tool, and to be useful in solving real-life problems. LINK grew out of the experiences of the authors of Combinatorica, due to Steven Skiena (see [50]), NETPAD, due to Nate Dean and others at Bellcore (see [48]), SetPlayer, due to Mark Goldberg and his students (see [1]), and GraphLab, due to Greg Shannon, et al. (see [49]). Skiena, Dean, Goldberg, and Shannon came together through DIMACS to develop LINK. Also, Jonathan Berry, then a DIMACS postdoc, played an important role in developing LINK and currently maintains the LINK website. LINK has been used as a tool to develop and analyze graphtheoretical conjectures, as well as a tool to explain graph-theoretical concepts and a tool for practical applications of graph theory and discrete mathematics. For example, Brenda Latka has used the system to generate conjectures about infinite antichains of tournaments (complete directed graphs) ([16, 47]). Of some interest are some of the non-mathematical uses of LINK. Berry and Dean [2] used LINK to analyze correlations between purchases using supermarket data. An interesting offshoot of LINK has been its adoption by the Internal Revenue Service in fraud detection. This resulted from the system's ability to detect common patterns.
Briefly, here are some other systems of interest. VEGA, of which Tomasz Pisanski is a major developer, is a system for "doing" discrete mathematics that is based on Mathematica and springs from the Combinatorica system developed by Steve Skiena (see [50]) and the nauty system developed by Brendan McKay (see the URL http://cs.anu.edu.au:80/people/bdm/nauty). VEGA allows researchers, teachers, and students to quickly test ideas on small and mid-size examples. (See the URL http://vega.ijp.si/Htmldoc/vinfo.htm.)
Plantri, developed by Brendan McKay and Gunnar Brinkmann, is a program for generating planar triangulations and planar cubic graphs. It includes a fullerene generator fullgen, written by Brinkmann. Fullerenes, as we have noted, can be viewed as planar cubic graphs having only faces of size 5 or 6. See http://cs.anu.edu.au/people/bdm/plantri for general information about plantri and fullgen and [9] for information on generation of fullerenes.
LEDA (Library of Efficient Data Types and Algorithms) was started in 1988. Stefan Naeher is a primary developer. LEDA provides a collection of data types and algorithms for "combinatorial computing". (See http://www2.informatik.unihalle.de/~naeher/Manual/Preface.html.) The Graph Theorist, GT, is an older system developed by Susan Epstein (see [26]). It is a learning system that uses algorithmic class descriptions to discover and prove relations among mathematical concepts. CABRI, developed by Jean Marie Laborde, has recently been aimed at the use of the computer to learn about and explore concepts of geometry. (See [44, 45].) However, it has also been widely used for exploring graphs and families of related graphs, as summarized in [15].
Some Controversial Issues
The literature is filled with illustrations of the fact that it is extremely difficult to define what constitutes "intelligence" and exactly what would constitute "automatic generation" of new scientific ideas. Indeed, there is even controversy in what it means for a computer to "generate" new scientific ideas, let alone whether the generation is "automatic." Fajtlowicz, in an early version of the paper [36], argues: "When the act of 'making a conjecture' is attributed to a machine, the author of the program should be expected to clearly explain how the program, as opposed to its users, reached these conclusions." In an early version of [36] and elsewhere, he explains how this was done with Graffiti. See also the paper by Ermelinda Delavina [25] in this volume for a description of successive versions of Graffiti and demonstration of their use. In his paper [40] in this volume, Pierre Hansen argues that several steps in the process of finding conjectures with Graffiti (i.e., mainly, but not only, finding and adding counter-examples) are not automated. He therefore views such conjectures as obtained interactively, with Graffiti, not by Graffiti. Siemion Fajtlowicz, in early versions of [35, 36], disagrees, viewing such steps as happening between "rounds" of the use of Graffiti. He notes that a system can, as does a mathematician, formulate several successive conjectures on the same topic, based on increasing knowledge. Fajtlowicz therefore wishes to "attribute to Graffiti all of its conjectures". In their paper [41], also in this volume, Hansen and his collaborators observe, using the definition of conjecture in Bouvier and George's Dictionnaire des Mathematiques, that conjectures in graph theory may take many different forms. As a consequence, they view two of the six functions of the system INGRID, mentioned above, as providing conjectures automatically. Again, Simeon Fajtlowicz disagrees. In an early version of [36], referring to AGX, he says: "It is self-evident that attributing to a program conjecture-making abilities automatically excludes from this category programs written for the purpose of assisting humans in making conjectures, or for the purpose of verification or confirmation of existing conjectures." It is reasonable to infer that he feels the same way about INGRID. The authors of INGRID have never claimed that the program generates conjectures without the intervention of human beings. However, whether or not it is reasonable to refer to such a program as a "conjecture-making program" remains a bone of contention. Neither this preface nor this volume will resolve the issue. We recommend that the reader peruse the articles [34, 35, 36, 40, 41] to get the flavor of the debate. In particular, the reader might wish to note that there are further arguments in early drafts of [36] that take issue with the comments about Graffiti in [40].
Closing Comments
The primary goals of the working group have been 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. It is hoped that this volume will contribute to the achievement of these goals.
We wish to acknowledge the support provided by the National Science Foundation under Grant No. 0100921 to Rutgers University. That grant supported the work of the DIMACS working group on "Computer-Generated Conjectures" that led to this volume. Additional support for the working group came from the New Jersey Commission on Science and Technology and the DIMACS partner institutions at AT&T Labs, Bell Labs, NEC Laboratories America, and Telcordia Technologies. Their help is very much appreciated.
Patrick W. Fowler
Pierre Hansen
Melvin F. Janowitz
Fred S. Roberts
Bibliography
[1] D. Berque, R. Cechini, M. Goldberg, and R. Rivenburgh, The SetPlayer system for symbolic computation on power sets, J. Symbolic Computation, 14 (1992), 645-662.
[2] J. Berry and N. Dean, Market basket analysis with LINK, preprint, Elon College, 1996.
[3] J. Berry, N. Dean, M. K. Goldberg, G. E. Shannon, and S. Skiena, LINK: A system for graph computation, Software - Practice and Experience, to appear.
[4] B. Bollobas and P. Erdos, Graphs of extremal weights, Ars Combinatoria, 50 (1998), 225-233.
[5] R. C. Brigham and R. D. Dutton, Ingrid: A software tool for extremal graph theory research, Congressus Numerantium, 39 (1983), 337-352.
[6] R. C. Brigham and R. D. Dutton, A compilation of relations between graph invariants, Networks, 15 (1985), 73-107.
[7] R. C. Brigham and R. D. Dutton, A compilation of relations between graph invariants, Supplement 1, Networks, 21 (1991), 421-455.
[8] R. C. Brigham, R. D. Dutton, and F. Gomez, INGRID: A graph invariant manipulator, J. Symbolic Computation, 7 (1989), 163-177.
[9] G. Brinkmann and A. W. M. Dress, A constructive enumeration of fullerenes, J. Algorithms, 23 (1997), 345-358.
[10] A. Bundy and S. Colton, Automatic concept formation in pure mathematics, in Proceedings of IJCAI-99, Stockholm, 1999.
[11] A. Bundy, S. Colton, and T. Walsh, HR: A system for machine discovery in finite algebras, in Proceedings of the Machine Discovery Workshop ECAI-98, Brighton, 1998.
[12] G. Caporossi, D. Cvetkovic, I. Gutman, and P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, J. Chemical Information and Computer Sciences, 39 (1999), 984-996.
[13] G. Caporossi, I. Gutman, and P. Hansen, Variable neighborhood search for extremal graphs 4: Chemical trees with extremal connectivity index, Computers and Chemistry, 23 (1999), 469-477.
[14] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 1. The AutoGraphiX system, Discrete Math., 212 (2000), 29-44.
[15] Y. Carbonneaux, J.-M. Laborde, and M. Madani, Cabri-graphs: A tool for research and teaching in graph theory, Lecture Notes in Computer Science, 1027 (1995), 123-127.
[16] G. Cherlin and B. Latka, A decision problem involving tournaments, DIMACS Technical Report 96-11, Piscataway, 1996.
[17] F. Chung, The average distance and the independence number, Journal of Graph Theory, 2 (1988), 229-235.
[18] S. Colton, Refactorable numbers - a machine invention, J. of Integer Sequences, 2 (1999).
[19] D. Cvetkovic, L. L. Kraus, and S. K. Simi´c, Discussing graph theory with a computer, I. Implementation of graph theoretic algorithms, Univ. Beograd Publ. Eletrotehn. Fak. 733 (1981), 100-104.
[20] D. Cvetkovic, and I. Pevac, Man-machine theorem proving in graph theory, Artificial Intelligence, 35 (1988), 1-23.
[21] D. Cvetkovic, and S. Simic, Graph theoretical results obtained by the support of the expert system "Graph" - An extended survey, this volume.
[22] D. Cvetkovic, S. Simic, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 3. On the largest eigenvalue of color-constrained trees, Linear and Multilinear Algebra, 49(2) (2001), 143-146.
[23] N. Dean and G. E. Shannon, (eds.), Computational Support for Discrete Mathematics, DIMACS Series, vol. 15, American Mathematical Society, Providence, 1994.
[24] E. DeLaVina, Graffiti.pc: A variant of Graffiti, this volume.
[25] E. DeLaVina, Some history of the development of Graffiti, this volume.
[26] S. Epstein, On the discovery of mathematical concepts, International J. of Intelligent Systems, 3 (1988), 167-178.
[27] P. Erdos, J. Spencer and J. Pach, On the mean distance between points of a graph, Congressus Numerantium, 64 (1988), 121-124.
[28] P. Erdos, S. Fajtlowicz, and W. Staton, Degree sequences in triangle-free graphs, Discrete Math., 92 (1991), 85-88.
[29] S. Fajtlowicz, On conjectures of Graffiti, Discrete Mathematics, 72 (1988), 113-118.
[30] S. Fajtlowicz, On conjectures of Graffiti, II, Congressus Numerantium, 60 (1987), 189-197.
[31] S. Fajtlowicz, On conjectures of Graffiti, III, Congressus Numerantium, 66 (1988), 23-32.
[32] S. Fajtlowicz, On conjectures of Graffiti, IV, Congressus Numerantium, 70 (1990), 231-240.
[33] S. Fajtlowicz, On conjectures of Graffiti, V, in Graph Theory, Combinatorics, and Algorithms: Proceedings of the Quadrennial Conference on the Theory and Applications of Graphs, vol. 1, 1995, 367-376.
[34] S. Fajtlowicz, Toward fully automated fragments of graph theory, Graph Theory Notes, New York Academy of Science, XLII (2002), 18-25.
[35] S. Fajtlowicz, Toward fully automated fragments of graph theory, preprint, University of Houston.
[36] S. Fajtlowicz, Postscript to fully automated fragments of graph theory, preprint, University of Houston.
[37] P. W. Fowler, Fullerene graphs with more negative than positive eigenvalues: The exceptions that prove the rule of electron deficiency, J. Chem. Soc., Faraday, 93 (1997), 1-3.
[38] P. W. Fowler and D. E. Manolopoulos, An Atlas of Fullerenes, Oxford University Press, Oxford, 1995.
[39] J. Griggs and D. Kleitman, Independence and the Havel-Hakimi residue, Discrete Math., 127 (1994), 209-212.
[40] P. Hansen, How far is, should, and could be conjecture-making in graph theory an automated process?, this volume.
[41] P. Hansen, A. Aouchiche, G. Caporossi, H. M´elot, and D. Stevanovi´c, What forms do interesting conjectures have in graph theory?, this volume.
[42] P. Hansen, P. Fowler, and M. Zheng, (eds.), Discrete Mathematical Chemistry, DIMACS Series, vol. 51, American Mathematical Society, Providence, 2000.
[43] A. Kotlov and L. Lovasz, The rank and size of graphs, J. of Graph Theory, 23 (1996), 185-189.
[44] J.-M. Laborde, (ed.), Intelligent Learning Environments, the Case of Geometry, NATO ASI Series, Springer Verlag, Berlin, 1995.
[45] C. Laborde and J.-M. Laborde, What about a learning environment where Euclidean concepts are manipulated with a mouse? in (A. Dil Sessa, C. M. Hoyles, R. Noss, and L. Edwards, eds.), Computers and Exploratory Learning, NATO ASI Series, Springer Verlag, Berlin, 1995.
[46] C. E. Larson, A survey of research in automated mathematical conjecture-making, this volume.
[47] B. Latka, Finitely constained classes of homogeneous directed graphs, J. Symbolic Logic, 59 (1994), 124-139.
[48] M. Mevenkamp, N. Dean, and C. Monma, NETPAD user's guide and reference guide, Technical Memorandum TM-ARH-018080, Bellcore, Morristown, 1990.
[49] G. Shannon, L. Meeden, and D. Friedman, SchemeGraphs: An object-oriented environment for manipulating graphs, Indiana University, Bloomington, 1990.
[50] S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, Reading, 1990.
[51] H. Wang, Toward mechanical mathematics, in (J. Siekmann and G. Wrightson, eds.), Automation of Reasoning: Classical Papers on Computational Logic, 1957-1966, Springer-Verlag, Berlin, 1983, 244-264.
Contents
Forward v
Preface vii
Considerations for Future Designers of General
Purpose Graph Software
J.W. Berry 1
Discovering Optimization Algorithms Through Automated
Learning
E. Breimer, M. Goldberg, D. Hollinger, and D. Lim 7
Numbers of Faces and Boundary Encodings of Patches
G. Brinkmann, O. Delgado-Friedrichs, and
U. von Nathusius 27
Graph Theoretical Results Obtained by the Support of
the Expert System "Graph" - An Extended Survey
D. Cvetkovic and S. Simic 39
Graffiti.pc: A Variant of Graffiti
E. DeLaVina 71
Some History of the Development of Graffiti
E. DeLaVina 81
On Some Conjectures of Griggs and Graffiti
E. DeLaVina, S. Fajtlowicz, and W. Waller 119
On The Representation and Characterization of
Fullerene C60
S. Fajtlowicz 127
The Structure of Fullerene Signatures
J.E. Graver 137
Catalog of All Fullerenes with Ten or More Symmetries
J.E. Graver 167
How Far Is, Should and Could Be Conjecture-Making
in Graph Theory an Automated Process?
P. Hansen 189
What Forms Do Interesting Conjectures Have in Graph
Theory?
P. Hansen, M. Aouchiche, G. Caporossi, H. Melot,
and D. Stevanovic 231
Variable Neighborhood Search for Extremal Graphs. 9.
Bounding the Irregularity of a Graph
P. Hansen and H. Melot 253
Mathematics for the Nanocell Approach to Molecular
Electronics
S.M. Husband, C.P. Husband, N. Dean, and J.M. Tour 265
A Software System for Matroids
R.J. Kingan and S.R. Kingan 287
A Survey of Research in Automated Mathematical
Conjecture-Making
C.E. Larson 297
Constrained Generation of Molecular Graphs
R. Laue, Th. Gruner, M. Meringer, and A. Kerber 319
A Dynamic Programming Approach for Timing and Designing
Clique Algorithms
W. Myrvold, T. Prsa, and N. Walker 333
On New Didactics of Mathematics: Learning Graph Theory
via Graffiti
R.D. Pepper 341
Interactive Conjecturing with Vega
T. Pisanski, M. Boben, and A. Zitnik 351
On the (1, 2)-Spectral Spread of Fullerenes
D. Stevanovic and G. Caporossi 365
Index of Volumes
DIMACS Homepage