Department of Applied Mathematics & Theoretical Physics -- (302) 857-7516 (main), -7517 (fax)

Combinatorics
Math-641 (17595) : TR, 4:30–5:45 pm, place TBA
[Topics][Daily Schedule][Assignments][Welcome]

Instructor: Tristan Hübsch, ETV 103, (302) 857-6603, thubsch@mac.com, thubsch@desu.edu
Office hours: M: 2:00–4:30 pm, T: 6:00–7:30 pm, R: 2:00–4:00 pm

Textbook (required): Fred Roberts and Barry Tesman, Applied Combinatorics (2nd ed.)

---

Grading recipe (no make-ups are given, except in cases of proven medical emergency):

Component	Time	Remark	% of Grade
Homework	See in daily schedule	Late HW = 0 credit !!!	60%
Term-paper	Last week of semester	Chosen topic	40%

Combinatorics (Math 641) is a course that introduces some essential topics in discrete, combinatorial mathematics and samples their applications in sciences and otherwise. paraphrasing from the text: The applications that motivate both the development and also the use of combinatorics are expanding, and occur throughout the sciences, both natural and social, but also in practical daily life and business, such as scheduling complex inter-related tasks and activities. It is important to identify the common underlying principles, methods and techniques, as they can then freely be used in a vast variety of applications.

“Success = 1% inspiration + 99% perspiration”--T.A. Edison
But, learning is still 100% learning!

§1: What is combinatorics
§2: Basic counting rules
§3: Introduction to graph theory
§4: Relations
§5: Generating functions and their applications
§6: Recurrence relations
§7. The principle of inclusion and exclusion
§8: The Pólya theory of counting

01/15: Introductory Matters §1.1–2
Basic Counting Rules
01/17: Counting rules, strategies and caveats: §2.1–4
01/22: More on counting rules, strategies and caveats: §2.5–10
01/24: Multinomials, permutations and simple games—incl. legislatures: §2.11–16
01/29: Generating subsets, good algorithms, and the pidgeonhole principle: §2.17–19
Introduction to Graph Theory
01/31: Fundamentals of graph theory: §3.1–2
02/05: Graph colorings: §3.3
02/07: Chromatic polynomials and trees: §3.4–5
02/12: Applications of rooted trees: §3.6
02/14: Graph theory methods in representation theory: extra
02/19: Adinkras: graphs for supersymmetry representaions: extra
Relations
02/21: Binary and order relations: §4.1–2
02/26: Linear extensions of partial orders: §4.3
02/28: Lattices and Boolean algebras, §4.4
Generating Functions
03/04: Generating functions: examples, operations and applications, §5.1
03/06: Binomial theorem, and the exponential generating function: §5.4–5
03/11: Relations to probability, and the Coleman and Banzhaf indices: §5.6–7
03/13: Generating functions in algebraic geometry: extra
03/17-21: Spring Recess
03/25: Generating functions from string theory and mirror symmetry: extra
Recurrence Relations
03/27: Recurrence relations: examples, and the method of characterisitc roots: §6.1–2
04/01: Generating functions and convolutions: §6.3–4
04/03: The principle of Inclusion and Exclusion: §7.1
The Principle of Inclusion and Exclusion
04/08: The number of objects with exactly m properties: §7.2
The Pólya Theory of Counting
04/10: Equivalence relations: §8.1
04/15: Permutation groups: §8.2
04/17: Representations of the permutation group and Young tableaux: extra
04/22: Applications of Young tableaux: extra
04/24: Burnside’s Lemma: §8.3
04/29: Distinct colorings, the cycle index: §8.4–5
05/01: Pólya’s theorem: §8.6

Homework assignments

To be announced by 01/29/07

All homework assignments are due by 5:00 pm of the day indicated and should be either given to the instructor in hand, left in the instructor's mailbox in ETV#116. Late homework will not be accepted, except in cases of proven emergency.

Collaboration policy

Collaboration -- but not blind copying -- on the homework assignments is strongly encouraged; students should use this to learn from each other. All exams and quizzes are open text and open class-notes (including notebooks and class handouts), but no collaboration is allowed; by signing the exams and quizzes, the student implicitly agrees to abide by this policy. Violation of this policy is covered under University regulations on academic dishonesty and cheating.

Presentation and organization

While a neat presentation of home,- quiz- and exam-work is not required for full credit, it certainly makes it easier to assess the quality of the work and give the proper credit due. In all cases, include a simple sketch if it might help conveying the approach or the calculations. Where necessary, include all units and symbols such as the measure of an integral, arrow on a vector, vertical bars for the absolute value of a quantity, for the magnitude of a vector or for the determinant of a matrix, etc.

• Homework: Submitted answer sheets should be stapled (preferably in the top-left corner). The Student's full name (and ID number) should be indicated on the first (cover) page. Solutions should be labeled and ordered consecutively by the problem numbers. Include all calculation/work and give full reference to any result quoted from any source other than the text, and page/equation number for results quoted from the text.
• Term paper: Written in the format of a research, this paper should address a topic from either (1) the Student’s degree (MS/Ph.D) research work, or (2) the remaining chapters of the text: Combinatorial designs, Coding theory, Existence problems in graph theory, Matching and covering, Optimization problems for graphs and networks. The paper itself should be between 12–15 page (+ title page & references list) term paper on the topic. The term papers are expected to consist of a brief (< 5 pages) introduction of the problem at hand and the background information to understand the problem. The remainder of the paper is expected to address the problem with a combination of a survey of the research done on the topic and solutions presented and an original attempt to solve the problem using the methods covered in the course.

© Tristan Hübsch, 2007