組合學導論
Introduction to Combinatorics
| 節 | 週二 | 週四 |
|---|---|---|
3 10:10–11:00 | 組合學導論 SA213 2 節連堂 | |
4 11:10–12:00 | ||
8 16:30–17:20 | 組合學導論 SA213 |
* 根據陽明交大上課時間表所列
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.
Use e3 system.
10% appearance, 40% homework, 25% midterm, 25% final.
- Enumerative Combinatorics
- Posets
- Matroids
- Designs
- Extremal and Probabilistic Combinatorics
- Algebraic and Geometric Methods (if time permits)
| 週次 | 主題 |
|---|---|
| 第 1 週 | The twelvefold way; Stirling numbers and Bell numbers |
| 第 2 週 | Principle of inclusion-exclusion; Mobius inversion; basic theory of generating functions |
| 第 3 週 | Ordinary g.f. and Catalan numbers; exponential g.f., exponential formula |
| 第 4 週 | Lagrange inversion formula; Catalan objects and bijections; basic terminology of posets |
| 第 5 週 | Dimension and interval orders; Dilworth and Sperner theorems; definition and examples of lattices |
| 第 6 週 | Semimodular lattices; Mobius inversion, Weisner theorem |
| 第 7 週 | Matroids and independence axiom |
| 第 8 週 | Greedy algorithm, basis axiom; Midterm 10/4 |
| 第 9 週 | Circuit and rank axiom; lattice of flats; representable and transversal matroids; elementary operations of matroids |
| 第 10 週 | Elementary operations of matroids (cont.); characteristic polynomials; advanced examples of matroids |
| 第 11 週 | Finite projective planes; Latin squares and orthogonal arrays; Hadamard matrices |
| 第 12 週 | Conference matrices; Hadamard codes; block designs, derived and residual designs; Erdős-De Bruijn theorem |
| 第 13 週 | Incidence matrices; symmetric designs; Fisher's inequality and BRC theorem; Erdős-Ko-Rado theorem |
| 第 14 週 | Technique of shifting and its applications; Ramsey theorem and its applications |
| 第 15 週 | Schur and van der Waerden theorems; basic probabilistic methods and their applications |
| 第 16 週 | Final exam 5/6 |
J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press. 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.
- 聯絡方式
- chyuen@math.nctu.edu.tw