組合學導論
Introduction to Combinatorics
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 組合學導論 SA214（光復） 2 節連堂 | |
4 11:10–12:00 | ||
6 14:20–15:10 | 組合學導論 SA214（光復） |
* 根據陽明交大上課時間表所列
This is an introductory course on graduate level combinatorics, which is a required course of the Combinatorics Graduate Program and includes half of the syllabus of the Ph.D. qualification exam of Combinatorics (the other half will be from "Graph Theory"). Topics include enumerative combinatorics, extremal combinatorics, and several fundamental combinatorial structures. If times permits, methods from other areas such as probability, (linear) algebra, and discrete geometry/topology are also discussed.
Undergraduate Discrete Mathematics and Linear Algebra.
Topics to be discussed depend on the interest of the class.
Use e3 system.
10% appearance, 55% homework, 35% final.
Enumerative Combinatorics
The twelvefold way (Stirling numbers, partition numbers, Bell numbers), sieve methods, recursion and generating functions
Posets
Dilworth and Sperner theorem, lattices, Möbius inversion
Matroids
Basic definitions, examples, and operations; invariants of matroids
Designs
Fundamental examples (finite projective planes, Hadamard matrices, Latin sqaures), block designs, Erdős-De Bruijn and Bruck-Ryser-Chowla theorem
Extremal and Probabilistic Combinatorics
Extremal set theory, Ramsey theory, basic probabilistic and linear algebraic methods
Algebraic and Geometric Methods (if time permits)
備註：Topics to be discussed depend on the interest of the class.
| 週次 | 主題 |
|---|---|
| 第 1 週 | The twelvefold way; Stirling numbers, Bell numbers, partition numbers |
| 第 2 週 | Principle of inclusion-exclusion; Mobius inversion; formal power series |
| 第 3 週 | Ordinary generating functions; exponential generating functions |
| 第 4 週 | Exponential formula; Lagrange inversion formula; Catalan objects and bijections; basic terminology of posets |
| 第 5 週 | Order dimension; Sperner and Dilworth theorem; lattices |
| 第 6 週 | Geometric lattices; closure operators |
| 第 7 週 | Mobius inversion, Weisner theorem |
| 第 8 週 | Axiom of matroids (independent sets, bases, circuits, rank) |
| 第 9 週 | Lattice of flats; transversal matroids; (23/4) Guest lecture/talk by Michael Zlatin |
| 第 10 週 | Elementary operations of matroids (deletion, contraction, duality); characteristic polynomials |
| 第 11 週 | Characteristic polynomials (cont.); advanced examples of matroids; finite projective planes; Latin squares |
| 第 12 週 | Orthogonal arrays; Hadamard matrices; block designs |
| 第 13 週 | Derived and residual designs; incidence matrices and Fisher's inequality; symmetric designs and BRC theorem; Erdős-Ko-Rado theorem and technique of shifting |
| 第 14 週 | Variations of EKR; Ramsey theorem and its applications; van der Waerden theorem |
| 第 15 週 | Probabilistic methods; linear algebraic methods |
| 第 16 週 | Final 11/6 (tentative) |
J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press. (Main Textbook) Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press. James Oxley, Matroid Theory, 2nd ed., Oxford University Press. Stasys Jukna, Extremal Combinatorics, 2nd ed., Springer (available online via NYCU library)
- 地點
- SA341
- 時間
- Send an e-mail to me to make appointment.
- 聯絡方式
- e3 or chyuen@math.nctu.edu.tw