Loading...
MATH 482-01, Combinatorics, Fall 2008
Gottlieb, Eric
Gottlieb, Eric
Citations
Altmetric:
Contributor
Photographer
Author
Artist
Editor
Advisor
Keywords
Syllabus, Curriculum, Academic departments, Text, Mathematics and Computer Science, Department of, 2008 Fall
Local ID
Collections
Abstract
Combinatorics is the study of sets, usually but not always finite, endowed with some kind of structure. For example, an ordering of the numbers 1 through n is the set of permutations. This set can be endowed with the algebraic structure of a group or the combinatorial structure of a partially ordered set. There are also natural ways to view the set of permutations as a graph.
There are many other heavily studied combinatorial structures, including other examples of groups, partially ordered sets, and graphs, as well as directed graphs, matroids, Latin squares, integer partitions, set partitions, codes, block designs, and many others. Some of these have important applications to areas such as circuit design, computing, experimental design, phylogeny, transportation, and telecommunications. All are of interest in their own right.
A wide and growing range of techniques are used in combinatorics. Some of these, such as the sum and product principles, are straightforward. Others, like the pigeonhole principle, seem simple but can be applied in subtle ways to prove interesting and hard theorems. Still others are more sophisticated, such as generating functions, recurrence relations, Burnside’s lemma, and Pólya counting.
There are three essential questions that arise in combinatorics, though not every topic fits neatly into one of these categories. The first is that of existence: is there a finite set with some specified structure? For example, can there be a party of six people so that there are neither three people who know each other nor three people who are strangers to each other? In this case, the answer is no, but this is not immediately obvious.
The second main question asked in combinatorics concerns the number of arrangements with the desired structure. Ideally, we seek an answer given by a nice formula. For example, there are n! permutations (i.e., total orders) on n
letters. Unfortunately, many combinatorial structures are not counted so cleanly. One can then proceed by developing bounds on the number of objects in question, by approximating the number when the problem is sufficiently large, or by finding a different set of objects that is in bijection with the set of objects of interest.
The last big question is that of construction. For example, how does one generate a uniformly random permutation? Issues of this type are computational in nature and hence are concerned not just with the correctness of a given algorithm but also with its efficiency.
It is impossible for any text or course on combinatorics to be comprehensive; one could spend one’s entire life studying just the properties of permutations. This class will offer glimpses of combinatorics through selected techniques, theorems, applications, and open questions.
In most mathematical areas, such as analysis and algebra, it is typically necessary to learn a great deal of mathematics in order to even understand what a question is asking. In contrast, research level questions in combinatorics can often be posed in a few minutes to a bright high school student. To some, the abundance of easily stated open questions characterizes combinatorics even more than its theorems.
Description
This syllabus was submitted to the Office of Academic Affairs by the course instructor. Uploaded by Archives RSA Josephine Hill.