Graph Theory Day 42
November 10, 2001
DIMACS Center, Rutgers University, Piscataway, New Jersey
Presented under the auspices of the DIMACS Special Focus on Data Mining and Analysis.
- Michael Gargano, Pace University, email@example.com
- John W. Kennedy, Queens College, CUNY, firstname.lastname@example.org
- Louis V. Quintas, Pace University, email@example.com
- Fred Roberts, Rutgers University, firstname.lastname@example.org
- Mel Janowitz, Rutgers University, email@example.com
Co-Sponsored by DIMACS and the New York Academy of Sciences (NYAS)
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.
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
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.
Contacting the Center
Document last modified on October 24, 2001.