Essays in applied combinatorics

Abstract

Combinatorial mathematics concerns itself with the study of discrete structures and relations. It plays a crucial role in computer science, since digital computers manipulate discrete, finite objects. The study of algorithms, particularly algorithms for discrete optimization, and the study of the underlying combinatorial structures have become increasingly important in computer science. At the same time, these topics have also become significant in areas such as communications, manufacturing, computer engineering, and management. Combinatorics interacts with computing in two ways. First, the properties of combinatorial objects such as graphs lead directly to algorithms for solving problems which have widespread applications in numerical as well as non-numerical computing. Second, combinatorial methods provide many analytical tools that can be used to determine worst-case and expected performance of computer algorithms. In this thesis, we explore a few themes in applied combinatorics emphasizing its interactions with computer science and obtain the following results:

Extremal Set Theory: We characterize the optimal collections of generalized antichains. Satisfiability: We solve the MAX-SAT and unique SAT problems for nested formulae and extended nested formulae. We also present a linear-time recognition algorithm for nested formulae. Interconnection Networks: We find the fault diameter of star graphs, diameter and shortest path routing for both modified bubblesort graphs and generalized star graphs.