
The potential for computer tools in the mathematical sciences has been 
appreciated since the introduction of digital machines.  Numerical 
computation has a history of widely used software such as the IMSL 
\cite{IMSL-80} and NAG \cite{NAG-80} libraries, which shaped the growth of 
the field by providing ready access to a variety of sophisticated algorithms
for scientists as well as numerical analysts.  A similar situation exists 
in statistical computing with packages such as SPSS \cite{SPSS-75} and BMDP 
\cite{BMDP-77}, and symbolic computation with Macsyma \cite{Macsyma-87}, 
Maple \cite{Maple-85}, and Mathematica \cite{Mathematica}.  However, despite
many independent efforts, including those by four of the creators of this
system, there has not yet emerged a comprehensive, portable, and 
widely-used environment for combinatorial computing comparable in influence 
to any of the systems listed above.  

Link is our attempt to create such an environment.  This 
system will include an object-oriented combinatorial 
library, which together with graphical and functional-language interfaces 
form an interactive workbench.  Our system will be significantly 
more powerful than any combinatorial computing environment to date.  

There is considerable debate about the role of
computational tools in mathematics.  However, 
we see such tools as intelligent ``scratch pads'' or ``research 
assistants'' rather than theorem provers.  We are confident that these 
tools will enable theorists and applied users to gain significant
insights into 
combinatorial problems by
investigating non-trivial examples in an organized and visual manner.  

The level of interest in environments for combinatorial computing is perhaps
best demonstrated by the fact that there have been well over twenty 
different projects to date in this area.  There has been considerable 
duplication of effort, and it is fair to say that no existing system has 
gone beyond the prototype stage, including previous work by the four of us. 
With the possible exception of {\em Combinatorica}, no software has achieved
a substantial user community, and performance problems restrict {\em 
Combinatorica}'s use to prohibitively small problems.  By working together 
with sufficient support, we can aspire to a significantly higher level.  

That there is increasing interest in combinatorial computing and systems to 
support experimental research is clear: 

\begin{itemize}

\item {\em The Emergence of Experimental Discrete Mathematics and 
Computer Science} -
Beginning with Appel and Haken's proof of
the Four-Color Theorem \cite{AHK-77,AH-77}, and more recently with
Lam's proof \cite{Lam-91} of the non-existence of a finite projective 
plane of order 10 and McKay's \cite{MZ-91} determination of the Ramsey 
number $R(3,8)$, extensive computation has been used to resolve several 
longstanding open problems in discrete mathematics.
This work has attracted 
considerable notice in both the scholarly and popular
press \cite{NYT-91,CC85}.
Within traditionally theoretical areas of computer science there has also 
been increasing interest in experimental research.

\item {\em Educational Impact of Combinatorial Computing Environments} - 
These environments have to date received their most 
extensive applications in education.  {\em Combinatorica} was
awarded a 1991 EDUCOM award for Distinguished Mathematics Software for 
Higher Education, and both {\em NETPAD} and {\em GraphLab} have been used at
a variety of educational institutions, at both the high school and college 
levels.  

\item {\em Applications of Combinatorial Computing} - The High Performance 
Computing Initiative seeks order-of-magnitude improvements in a variety of 
computing technologies, with a particular emphasis on applications to the 
set of Grand Challenge problems, emerging from disciplines other than 
computer science.  Several of these problems, particularly in computational 
biology, have a strong combinatorial components.  Tools previously developed
by the principal investigators have been applied to computational biology, 
network analysis, and VLSI automation.  

\end{itemize}

Despite the success and potential of combinatorial computing, all
previous software systems have serious drawbacks, 
as summarized in Appendix \ref{appendix-previous}.
Better tools will enable a larger community to do experimental work in
discrete mathematics, and render tractable
many problems which are currently difficult to approach computationally.
The environment we propose differs 
significantly from any previous initiative in software
for discrete mathematics:

\begin{itemize}

\item {\em Scale of Effort} - 
For the first time four researchers, each with 
significant experience in combinatorial computing, are combining forces to 
build a {\em single} system more sophisticated than any of us could
build individually.  Together, we have developed an ambitious design 
incorporating a comprehensive object-oriented library, a graphical 
user-interface with animation capabilities, and a state-of-the-art functional 
programming language interface.  When completed, the resulting system will 
be an important addition to the research infrastructure in the fields of 
computer science and discrete mathematics, as well as a variety of 
applications areas.  

\item {\em Research Agenda} - There
are several research problems fundamental to building this tool and to 
enhancing such tools in the future.  These include developing algorithms for
implicit representations of combinatorial objects, techniques for 
visualizing and animating large structures, efficient and expressive 
language support for on-line algorithms, heuristic algorithms for hard 
problems, and techniques for the experimental analysis of graphical
enumeration problems.

\item {\em A Bridge to Applications} - Our current systems have already 
attracted users from biology, electrical engineering, and mathematics, as 
well as computer science.  The proposed environment will enable an even 
larger scientific community to understand and use what combinatorial 
computing has to offer.
To demonstrate that this environment can 
be used for substantial applied problems, we will develop application 
packages in combinatorial biology, network analysis, and scheduling.  
Finally, this tool will be designed to serve as a powerful front end for the 
experimental design and analysis of parallel combinatorical algorithms.  

\item {\em Educational Agenda} - 
To maximize the educational benefits of the resulting software, we have
developed a coherent educational agenda.
Educators from a variety of different levels will be involved with the
project from its early stages, both through annual workshops and joint
efforts with existing DIMACS programs.
We will provide an educational version of the software, and facilitate the
development of course materials.

\end{itemize}

A brief survey of existing software for discrete mathematics is given in 
Section \ref{previous-work},
but the rest of this proposal concentrates on our plans for future work.
Section \ref{tool} presents a description of the tool which we propose
to build.


%-----------------------------------------------------------------------------
\subsubsection{Previous Work}
\label{previous-work}

Each of the four principal investigators has independently developed a 
significant combinatorial computing environment.  These systems, {\em 
NETPAD} (Dean) \cite{Dean-90}, {\em SetPlayer} (Goldberg) \cite{BCGR-91}, 
{\em GraphLab} (Shannon) \cite{BS-89}, and {\em Combinatorica} 
(Skiena)\cite{Skiena-90}, are discussed in Appendix \ref{appendix-previous},
along with related work by other researchers.  Section \ref{appendix-faults}
discusses the most significant shortcomings of current systems.  This experience, 
as well as our leadership efforts in organizing ICIAM and DIMACS workshops 
on software for discrete mathematics, makes us uniquely qualified for the 
proposed work.  

We have had considerable success applying experimental techniques towards 
research in discrete mathematics, as illustrated by our results in 
rectilinear crossing numbers \cite{Dean-91}, coloring problems on 
hypergraphs \cite{GR-91}, square roots of graphs \cite{YS-90}, graceful 
labelings for prisms \cite{Huang-90}, and heuristics for improved
grid embeddings of planar graphs \cite{DEMSS91}.  Further details about
these results and other applications of our work appear in Appendix 
\ref{appendix-experimental-work-and-applications}.  

