Combinatorics using computational methods

Computational combinatorics involves combining pure mathematics, algorithms, and computational resources to solve problems in pure combinatorics. This thesis provides a theoretical framework for combinatorial search, which is then applied to several problems in combinatorics. Chain Counting: Linek asked which numbers can be represented as the number of chains in a width-two poset. By developing a method for counting chains in posets generated from small configurations, constructions are found to represent every number from five to 50 million, providing strong evidence that all numbers are representable. Ramsey Theory on the Integers: Van der Waerden\u27s Theorem states that for sufficiently large n the numbers 1, 2, …, n cannot be r-colored while avoiding monochromatic arithmetic progressions. Finding the minimum n with this property is an incredibly difficult problem. We develop methods to compute the minimum n as well as optimal colorings when trying to avoid two generalizations of arithmetic progressions. p-Extremal Graphs: For an integer p, a p-extremal graph is a graph with the maximum number of edges over all graphs of order n with p perfect matchings. We describe the structure of p-extremal graphs in terms of a finite number of fundamental graphs and then discover these fundamental graphs using a computational search. Uniquely Kr-Saturated Graphs: A graph G is uniquely Kr-saturated if G contains no copy of Kr, but adding any missing edge to G creates exactly one copy of Kr as a subgraph. Very little was known about uniquely Kr-saturated graphs, but by adapting a technique from combinatorial optimization we found several new examples of these graphs. One of these graphs led to the discovery of two new infinite families of uniquely Kr-saturated graphs. Some results in space-bounded computational complexity are also presented. First, two nondeterministic complexity classes defined by the number and structure of computation paths are shown to be equal. Second, a log-space algorithm is developed to solve reachability problems on directed graphs that are embedded in surfaces of low genus