組合學導論
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
The twelvefold way (Stirling numbers, partition numbers, Bell numbers), sieve methods, recursion and generating functions, Catalan numbers
Posets
Dilworth and Sperner theorems, lattices, Möbius inversion
Matroids
Basic definitions, examples, and constructions; invariants of matroids
Designs
Fundamental examples (finite projective planes, Hadamard matrices, Latin sqaures, etc), block designs, Erdős-De Bruijn and Bruck-Ryser-Chowla theorems, applications in coding theory
Extremal and Probabilistic Combinatorics
Extremal set theory, Ramsey theory, basic probabilistic methods
Algebraic and Geometric Methods (if time permits)
Possible topics include: permutation groups and Pólya theory of counting, symmetric groups and further topics in partitions, polynomial methods, linear algebraic methods and determinantal formulae, q-analogs, polyhedral combinatorics, topological methods
備註：Topics to be discussed depend on the interest of the class. (Note after semester: not applicable due to time)
| 週次 | 主題 |
|---|---|
| 第 1 週 | The twelvefold way; Stirling numbers and Bell numbers 2025-02-18(二),2025-02-20(四) |
| 第 2 週 | Principle of inclusion-exclusion; Mobius inversion; basic theory of generating functions 2025-02-25(二),2025-02-27(四) |
| 第 3 週 | Ordinary g.f. and Catalan numbers; exponential g.f., exponential formula 2025-03-04(二),2025-03-06(四) |
| 第 4 週 | Lagrange inversion formula; Catalan objects and bijections; basic terminology of posets 2025-03-11(二),2025-03-13(四) |
| 第 5 週 | Dimension and interval orders; Dilworth and Sperner theorems; definition and examples of lattices 2025-03-18(二),2025-03-20(四) |
| 第 6 週 | Semimodular lattices; Mobius inversion, Weisner theorem 2025-03-25(二),2025-03-27(四) |
| 第 7 週 | Matroids and independence axiom 2025-04-01(二),2025-04-03(四) |
| 第 8 週 | Greedy algorithm, basis axiom; Midterm 10/4 2025-04-08(二),2025-04-10(四) |
| 第 9 週 | Circuit and rank axiom; lattice of flats; representable and transversal matroids; elementary operations of matroids 2025-04-15(二),2025-04-17(四) |
| 第 10 週 | Elementary operations of matroids (cont.); characteristic polynomials; advanced examples of matroids 2025-04-22(二),2025-04-24(四) |
| 第 11 週 | Finite projective planes; Latin squares and orthogonal arrays; Hadamard matrices 2025-04-29(二),2025-05-01(四) |
| 第 12 週 | Conference matrices; Hadamard codes; block designs, derived and residual designs; Erdős-De Bruijn theorem 2025-05-06(二),2025-05-08(四) |
| 第 13 週 | Incidence matrices; symmetric designs; Fisher's inequality and BRC theorem; Erdős-Ko-Rado theorem 2025-05-13(二),2025-05-15(四) |
| 第 14 週 | Technique of shifting and its applications; Ramsey theorem and its applications 2025-05-20(二),2025-05-22(四) |
| 第 15 週 | Schur and van der Waerden theorems; basic probabilistic methods and their applications 2025-05-27(二),2025-05-29(四) |
| 第 16 週 | Final exam 5/6 2025-06-03(二),2025-06-05(四) |
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