Computational Combinatorics

Part of the purpose of this blog is to collect enough information on Computational Combinatorics to develop a graduate course on the subject. This page outlines the syllabus of such a course, and how the posts fit within that syllabus.

Preliminaries

1. Ranking and Unranking of Combinations and Permutations
2. Symmetry and Automorphisms
3. Canonical Labelings with nauty
4. Computing Orbits with nauty
5. Best Practices for Scientific Computing

Existing Software Tools

1. Using the Sage Graph Library
2. Using gtools
   1. Piping geng
3. Using GLPK, CPLEX, and other LP Solvers.
4. Using TreeSearch for Parallel Computation

Backtrack Search

1. A Visual Guide to Combinatorial Search
2. Finding Subobjects
   1. Finding and counting cliques with cliquer
   2. Finding cliques and independent sets in circulant graphs
   3. Uniquely -Saturated Graphs: Experiment #2
3. Finding colorings
   1. Search for rainbow-AP-free colorings
4. Best Practices for Backtrack Search

Canonical Deletion

1. Introduction to Canonical Deletion
2. Small Graphs are Reconstructible
3. Generating Cubic Graphs
4. Generating Fullerenes
5. Generating 2-connected Graphs using Ears
6. Generating -Extremal Graphs

Orbit Methods

1. Introduction to Orbital Branching
2. Uniquely -Saturated Graphs, Experiment #1
3. There is no Projective Plane of Order 10.

Planar Graphs

1. Generating planar graphs
2. Hypohamiltonian planar graphs

Linear and Integer Programming

1. Integer Programming as Blackbox
   1. 3-Uniform Friendship Hypergraphs
2. Linear Programming as Subroutine
   1. A Linear Programming Approach to the Manickam-Miklós-Singhi Conjecture
3. The Nullstellensatz/Linear Algebra Method

Flag Algebras

1. Introduction to Flag Algebras
2. Hypergraphs Do Jump
3. On the Ramsey Multiplicity of Triangles with Three Colors

Famous Computer Proofs

1. The Four-Color Theorem
2. Hales’ Proof of the Kepler Conjecture

The Wilf-Zeilberger Method

1. Introduction to the Wilf-Zeilberger Method