Open Questions: Combinatorics, Graph Theory, and Computation

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

See also: Quantum information and computing -- DNA and molecular computing

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

Copyright © 2002-04 by Charles Daney, All Rights Reserved