DIMACS Center, Rutgers University, Piscataway, New Jersey

**Organizers:****Michael Gargano**, Pace University, mgargano@pace.edu**John W. Kennedy**, Queens College, CUNY, jkennedy@nyas.org**Louis V. Quintas**, Pace University, lquintas@pace.edu**Fred Roberts**, Rutgers University, froberts@dimacs.rutgers.edu**Mel Janowitz**, Rutgers University, melj@dimacs.rutgers.edu

1. POSING, VERIFYING AND DISPROVING CONJECTURES: EXPERIENCES IN USING A PROGRAMMING PACKAGE FOR GRAPH THEORY Dragos Cvetkovic, University of Belgrade An interactive programming package, called GRAPH, an expert system for graph theory, was developed at the University of Belgrade, Faculty of Electrical Engineering, during the period 1980-1984. GRAPH was designed to support research in graph theory, among other things by helping to pose, verify and disprove conjectures. We report on the twenty years long experience in using GRAPH. The results obtained by some help of GRAPH have been published in about 70 papers written by about 20 authors. Most of the results belong to the theory of graph spectra.

2. Toward Fully Automated Fragments of Graph Theory. Siemion Fajtlowicz, University of Houston. Some versions of Graffiti, starting with the Dalmatian one, developed jointly with Ermelinda DeLaVina, are fully automated apart from the invention of invariants and counterexamples. Every conjecture of this version is made with purpose and in some runs, for example in those in which the goal is discovery of new easily-computable bounds for NP-hard invariants, every one of them has a motivation. The collection of these bounds can be viewed as a hypothetical theory in which the main issue is significance, as opposed to the truth of the formulas. Examples of such theories of the independence number, include some runs of Minuteman - the fullerene version of Graffiti and among its by-products are hypotheses concerning stability of these new carbon forms. I will also discuss modification of these hypotheses suggested by nanotubes and other materials. Another by-product of a conjecture about the independence number of stable fullerenes is a new representation of buckminsterfullerene - the icosahedral C60. The most automated example, to be discussed, are conjectures of Red Burton - the educational version of the program designed to teach graph theory, Texas-style, eventually without any help of instructors. The discovery of new bounds makes it all but necessary sometimes to address the issue of concept formation and this problem naturally leads to questions (and one solution) related to 17th and 18t century interpolation problems.

3. COMPUTERS IN GRAPH THEORY Pierre Hansen, GERAD and Ecole des HEC,Montreal Computer aids to Graph Theory, i.e. finding proofs, conjectures and refutations are reviewed. After discussing the four-color theorem and other computer aided proofs, ways to get conjectures and refutations are examined: (i) graph enumeration; (ii) interactive computing, (iii) formula manipulation, (iv) a priori generation and filtering, (v) heuristic optimization. Open questions and areas for development are emphasized.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on October 24, 2001.