Graph Theory Day 42

November 10, 2001
DIMACS Center, Rutgers University, Piscataway, New Jersey

Michael Gargano, Pace University,
John W. Kennedy, Queens College, CUNY,
Louis V. Quintas, Pace University,
Fred Roberts, Rutgers University,
Mel Janowitz, Rutgers University,
Presented under the auspices of the DIMACS Special Focus on Data Mining and Analysis.

Co-Sponsored by DIMACS and the New York Academy of Sciences (NYAS)



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.