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}.