Open Questions: Combinatorics, Graph Theory, and Computation

[Home] [Up] [Glossary] [Topic Index] [Site Map]

Introduction

The P vs. NP problem

The linear programming problem

Hadwiger's conjecture (chromatic numbers of graphs)

Computer theorem-proving

Recommended references: Web sites

Recommended references: Magazine/journal articles

Recommended references: Books

Introduction

Recommended references: Web sites

Site indexes

Math Forum Internet Mathematics Library: Discrete Math: Alphabetized list of links with extensive annotations.
Math Forum: Advanced Discrete Mathematics: Selected list of links with extensive annotations.
Mathematics Archives - Combinatorics: Extensive annotated list of links.
Mathematics Archives - Discrete Mathematics: Extensive annotated list of links.
Open Directory Project: Combinatorics: Categorized and annotated combinatorics links. A version of this list is at Google, with entries sorted in "page rank" order.
Galaxy: Combinatorics: Categorized site directory. Entries usually include descriptive annotations. Has a subcategory for graph theory.

Sites with general resources

The Electronic Journal of Combinatorics and The World Combinatorics Exchange: And online journal and Web site with resources for combinatorial people.
Open Problems for Undergraduates: About open problems in discrete mathematics -- graph theory and combinatorial geometry mostly. Although the problems are easily stated, they may be quite hard. By Robert Hochberg, located at the Center for Discrete Mathematics & Theoretical Computer Science (DIMACS) site.
An Introduction to the Theory of Computation: Material from a course at Ohio State University, by Eitan M. Gurari. Includes information on NP and NP-complete problems.

Algorithms, computability, computational complexity

Computational complexity theory: Article from Wikipedia. See also Computation, Computabililty theory, Decision problem.
Wikibooks: Discrete Mathematics: Textbook in the Wikibooks collection. A work in progress, but already contains much useful information.
Algorithmns and Complexity: Complete first edition (1986) of a book by Herbert S. Wilf, in PDF format.
An Introduction to the Theory of Computation: Complete 1989 book by Eitan M. Gurari (HTML/hypertext).

P, NP, and NP-complete problems

The P versus NP Problem: Brief description of the problem at the Clay Mathematics Institute site by Stephen Cook. (A more complete description is available as a PDF file.)
Complexity classes P and NP: Article from Wikipedia.
Million-Dollar Minesweeper: Well-written article for a general audience on the Minesweeper game, by Ian Stewart. This is used to explain the P vs. NP problem.
CMU professor honored for computational complexity breakthrough: May 2007 news article about award of 2007 ACM Gödel Prize to Steven Rudich and Alexander A. Razborov for their work on the P vs. NP problem, in which they showed that the type of proof technique known as "natural proofs" cannot solve the problem.
Heuristic Algorithms: This is the text for a course given by Forbes Lewis. Several introductory chapters deal with P, NP, and NP-complete problems. There is also material on neural networks, genetic algrorithms, and DNA computing.
Data Structures and Algorithms: Hard or Intractable Problems: Part of course material by John Morris. This page is on the distinction between "easy" problems (class P) and harder problems (NP). The problems of traversing a graph so that each edge is crossed exactly once is compared with graph traversal where each vertex is encountered exactly once. Other examples of NP problems are given.
TSPBIB Home Page: "A comprehensive listing of papers, source code, preprints, technical reports, etc, available on the Internet about the Traveling Salesman Problem (TSP) and some associated problems." Compiled by Pablo Moscato.
The Travelling Salesman Problem: Nice tutorial page by Robert Dakin

Graph theory

Graph theory: Article from Wikipedia. See also Graph (mathematics), Glossary of graph theory.
Perfect Graphs: An outline (literally) of some of the conjectures and open problems related to perfect graphs. Part of the Workshop Website Network of the American Institute of Matheamtics.
Unsolved Problems in Graph Theory: Mostly from the book Graph Theory with Applications, by Bondy and Murty.
Problems in Topological Graph Theory: Compiled by Dan Archdeacon.
Graph Theory: Complete online book by Reinhard Diestel, in PDF format (printing disabled).
Data Structures and Algorithms: Graph Algorithms: Part of course material by John Morris. This page is on minimal spanning trees. There's another page on Dijkstra's algorithm for finding the shortest path between points in a graph.
Journal of Graph Algorithms and Applications: Free, refereed online journal.

Discrete mathematics, combinatorics

Combinatorics: Article from Wikipedia. See also List of combinatorics topics.
Open Problems in Discrete Math: Collected by Matt DeVos.
The Electronic Journal of Combinatorics: Dynamic Surveys: Survey articles (in various formats) on contemporary2 research topics in combinatorics, periodically updated. The journal's home page has other useful information and external links.
Discrete Mathematics & Theoretical Computer Science: Free, refereed online journal.

Computer theorem-proving

The Coq proof assistant: "The Coq tool is a formal proof management system: a proof done with Coq is mechanically checked by the machine." The site provides news and general information about Coq, documentation, related tools, as well as ability to download Coq.

Recommended references: Magazine/journal articles

Minesweeper is NP-complete
Richard Kaye
Mathematical Intelligencer, Spring 2000, pp. 9-15: The article elucidates the concepts of NP and NP-complete problems through a proof that the game of Minesweeper is NP-complete.
Descriptive Complexity: A Logician's Approach to Computation
N. Immerman
Notices of the AMS, October 1995, pp. 1127-1133: As usually described, the complexity of a computation is evaluated in terms of some specific computational model -- some sort of abstract computing device. However, the notion of complexity can be described completely in terms of traditional mathematical logic.
[Article in PDF format]

Recommended references: Books

David Harel -- Computers Ltd.: What They Really Can't Do
Oxford University Press, 2000: What computers really can't do is to solve NP-complete problems within the probable lifetime of the universe. This short book by a distinguished computer scientist provides an elementary explanation of this limitation. It also discusses something that computers can do with very clever algorithms -- cryptogrphy.

Home