Discrete and Algebraic Structures, WS 2020/2021
Contents
The course consists of two parts.
- Part I: Combinatorics and Graph Theory (Combinatorics, Graph Theory, Stochastic Aspects),
- Part II: Algebraic Structures (Multilinear Algebra, Rings and Modules).
Lecture
The lecture part of the course is entirely online.- Lecture notes and recorded videos are provided in Moodle.
- The lecture notes are posted section by section and you can ask and answer questions and start discussions directly as annotations in the notes. In addition the Moodle forums can be used for discussion.
- Every Tuesday at 9:00am there is a virtual office hour in which you can ask questions (join uniMEET via Moodle). I will start the video conference room and wait ca. 5 minutes if people show up and have questions (if not I'll leave). Maximal duration: 30-45 minutes.
- This is a new mode for all of us! If you have feedback or suggestions, please let me know. If necessary, we will adjust the mode during the semester to achieve the best possible learning experience for everyone.
- Exam: Written exam. If it is not possible to hold a written exam due to the COVID-19 situation, or you cannot participate in one, it will be replaced by an oral exam (online).
Video Lectures
Week 1: Combinatorics - Basics, Generating Functions
- Video: Intro (6min)
- Organisation of the course and quick overview over the contents.
- Video: Basics (22min)
- 00:00 - Binomial Coefficients, etc.; 13:00 - Landau/Asymptotic Notation
- Video: Generating Functions Part 1 (22min)
- 00:00 - Formal Power series; 12:50 - Example: Fibonacci Sequence
Erratum: In the right hand side of the definition of the product of formal power series (1st slide), the inner sum should go from k to n (not m). - Video: Generating Functions Part 2 (21min)
- 00:00 - OGF/EGF; 3:00 - Combinatorial Classes; 5:30 - Example: Triangulations
Week 2: Combinatorics - Symbolic Method
- Video: Symbolic Method - Unlabeled combinatorial objects (20min)
- 00:00 - Substitution of formal power series; 05:16 - Symbolic method (unlabeled)
- Video: Examples of the symbolic method for unlabeled combinatorial objects (13min)
- 00:00 - Binary trees; 6:47 Triangulations; 9:00 Binary words w/o consecutive 0s
- Video: Symbolic method for labeled combinatorial objects (17min)
- 00:00 - Labeled combinatorial classes; 11:10 - Example: labeled 2-regular graphs.
Week 3: Combinatorics - Analytic Methods
- Video: Lagrange Inversion Theorem (26min)
- 00:00 - Context for Lagrange Inversion; 07:45 - Lagrange Inversion Theorem; 10:40 - Example: Binary Trees; 16:30 Labeled Trees/Cayley's Formula
- Video: Singularity Analysis - Basics (26min)
- 00:00 - Motivation for Singularity Analysis; 09:10 - Singularities; 18:25 Scaling Rule; 21:00 Aside: Fractional Powers/Gamma function
- Video: Singularity Analysis - Transfer Theorems (26min)
- 00:00 - Singularity Analysis/Transfer Theorems; 07:45 - Example: 2-regular labeled graphs; 12:35 - Multiple Singularities; 16:05 - Example: Permutations with Cycles of Odd Length; 22:21 - Conclusion
Week 4: Graph Theory - Eulerian Tours, Hamiltonian Cycles, and Matchings
- Video: Graph Theory - Review of Basic Terminology (23min)
- Video: Eulerian Tours and Hamiltonian Cycles (21min)
- 00:00 - Eulerian Tours; 02:50 - Characterization of Eulerian graphs (proof); 08:23 - Hamiltonian cycles; 09:50 - Dirac's Theorem on Hamiltonian cycles (proof)
- Video: Matchings (20min)
- 00:00 - Matchings; 11:22 Proof of Kőnig's Theorem
Week 5: Graph Theory - Planar Graphs and Trees
- Video: Planar Graphs (15min)
- Video: Trees (21min)
- 00:00 - Definitions & Basic Lemmas; 09:00 - Cayley's formula & illustration of Prüfer sequences
- Video: Bijective proof of Cayley's formula using Prüfer sequences (22min)
Week 6: Stochastic Aspects - First Moment Methods
- Video: Stochastic Aspects - Basics and Random Graphs (21min)
- 00:00 - Probability Theory; 09:35 - First moment method; 11:20 - Random Graphs; 14:05 - Example: Expected number of edges in a binomial random graph
- Video: Ramsey numbers (18min)
- An application of random graphs to get an (asymptotic) lower bound of exponential growth for the Ramsey numbers
- Video: Independence number (14min)
- An application of random graphs to prove a lower bound on the independence number of a graph (Weak Turán Theorem)
Week 7: Stochastic Aspects - Second Moment Methods
- Video: Second Moment Methods (22min)
- 00:00 - Chebychev's inequality and second momemt method; 11:27 - Sums of indicator variables
- Video: Monotone Families (14min)
- 00:00 - Definition and Examples; 08:30 - Thresholds and the Theorem of Bollobas-Thomason
- Video: Subgraph Threshold (20min)
- 00:00 - Triangle thresholds; 14:33 - Subgraph thresholds
Week 8: Algebraic Structures - Multilinear Algebra, Tensor Products
- Video: Multilinear Algebra (19min)
- 00:00 - Motivation; 06:30 - Multilinear maps; 13:40 - Notation: Γ
- Video: Multilinear extension theorem (20min)
- 00:00 - Multilinear extension theorem; 16:55 - Differences between linear and multilinear maps
- Video: Tensor maps (18min)
- 00:00 - Rank, tensor maps; 6:55 - Factorization property for tensor maps; 17:13 Multilinear forms
- Video: Tensor products (24min)
- 00:00 - Tensor products; 4:50 - Universal property of tensor products; 12:45 - Uniqueness of tensor products
Week 9: Properties of Tensor Products
- Video: Basic properties of tensor products (28min)
- 00:00 - Basic properties of tensor products; 16:18 - Tensor rank
- Video: Inner products; Associativity (32min)
- 00:00 - Extension of inner product to tensor products; 29:15 - Associativity of tensor product
- Video: Induced maps (25min)
- 00:00 - Induced maps on tensor products; 9:20 - Ranks of induced maps; 18:28 - Adjoints
Week 10: Models of Tensor Products, Exterior Powers
- Video: Models of Tensor Products (20min)
- Video: Exterior Powers (20min)
- 00:00 - Alternating multilinear maps; 07:13 - Definition of Exterior Powers; 09:55 - Universal Property
- Video: Geometric Motivation & Basic Properties of Exterior Powers (27min)
- 00:00 - Geometric Motivation for Exterior Powers; 06:48 - Basis; 24:50 - Example
Week 11: Exterior Powers continued & Rings and Modules
- Video: Exterior Powers and the Determinant (9min)
- 00:00 - Dimensions of exterior powers; 01:12 - Induced maps and the determinant
- Video: Exterior Algebras and Duals of Exterior Powers (23min)
- 00:00 - Exterior algebra; 10:44 - Duals of exterior powers
- Video: Rings and Modules (27min)
- 00:00 - Rings and Modules; 17:10 - Algebras
- Video: Submodules (14min)
- 00:00 - Submodules; 03:15 - Intersection of submodules; generating sets; 09:30 - Sums of submodules
Week 12: Modular Law, Morphisms, and a Diagram Completion Problem
- Video: Sums of Submodules and the Modular Law (14min)
- 00:00 - Sums of submodules (basic properties); 06:55 - Submodule lattice; 08:38 - Modular law
- Video: Morphisms of R-modules (18min)
- 00:00 - (Homo)morphisms of R-modules; 05:14 - Behavior of submodules under morphisms; 14:37 - Compositions and Inverses of R-morphisms
- Video: A diagram completion problem I (22min)
- 00:00 - Motivation; 01:49 - A basic "diagram completion problem" for maps of sets; 09:30 - Characterization of injective and surjective maps; 13:35 - Example I: Failure of diagram completion with morphisms of modules; 16:18 - Example II: Failure in the dual problem.
- Video: A diagram completion problem II (24min)
- 00:00 - Solution to a diagram completion problem for modules; 13:40 - Dual to previous problem
Week 13: Exact Sequences, Diagram Lemmas, and Quotient Modules
- Video: Exact sequences (23min)
- 00:00 - Commutative Diagrams; 05:25 - (Semi-)exact sequences; 17:20 - Example: Universal Property of the Kernel
- Video: Diagram Chasing (21min)
- 01:25 - Four Lemma; 16:47 - Five Lemma
- Video: Quotient Modules (32min)
- 00:00 - Equivalent characterizations of module structure on equivalence classes; 24:30 Bijection between submodules and compatible equivalence relations; 29:30 - Definition of quotient modules
- Video: Submodules of Quotients (15min)
- 00:00 - Submodules of quotient modules (statement); 05:05 - Proof
Week 14: Isomorphism Theorems
- Video: Isomorphism Theorems I (24min)
- 00:00 - Intro; 01:30 - Theorem 5.4.5; 13:30 - Universal Property of Quotients; 15:54 - First Isomorphism Theorem; 20:33 - Canonical Decomposition of morphisms
- Video: Isomorphism Theorems II (31min)
- 00:00 - Second Isomorphism Theorem; 10:10 - Theorem 5.4.11; 24:30 - Third Isomorphism Theorem
- Video: Butterfly/Zassenhaus Lemma (11min)
Exercise Class
- You have to solve assigned problems and present them.
- The exercise class is held in person (HS 11.02) when the COVID-19 situation allows this (green/yellow/orange traffic light). As usual, students present the solutions on the blackboard.
- If it is not possible to meet in person (e.g., red traffic light), we conduct the exercise class online in uniMEET at the usual time. In this case, students should prepare a scan/photograph/... of their solution that can be uploaded on uniMEET and the presenting student then talks us through the exercise. If you have a tablet, you can also use that to screen-share. We'll be flexible in regards to the technical possibilities of each student.
Exercise Sheets
- 8.10.2020
- Exercise Sheet 1
- 15.10.2020
- Exercise Sheet 2
- 22.10.2020
- Exercise Sheet 3
- 29.10.2020
- Exercise Sheet 4 (Solution for Problem 1(c))
- 5.11.2020
- Exercise Sheet 5
- 12.11.2020
- Exercise Sheet 6
- 19.11.2020
- Exercise Sheet 7
- 26.11.2020
- Exercise Sheet 8
- 3.12.2020
- Exercise Sheet 9
- 10.12.2020
- Exercise Sheet 10 (Solution for Surjectivity in Problem 2)
- 17.12.2020
- Exercise Sheet 11
- 14.1.2021
- Exercise Sheet 12
- 21.1.2021
- Exercise Sheet 13
- 28.1.2021
- Final Exam
- 25.2.2021
- Make-Up Exam
Grading of Exercise Class
- Up to 15 points for solutions with a check mark system: 4/3 times 15 times (marked points)/(possible points), capped at a maximum at 15 and the first sheet does not count in the denominator. So you get full points with 75% of exercises checked;
- up to 5 points for presentations, with 2.5 points awarded per succesful presentation;
- up to 20 points for the final exam.
- If it is not possible to write an exam, the remaining points will be scaled by a factor of 2 and count for the full grade.
To pass the course, you need at least 10 points on the final exam and at least 20 points altogether.
COVID-19 risk groups
For people who belong to a COVID-19 risk group, who are living with people belonging to a COVID-19 risk group, who are in quarantine due to COVID-19, or who are affected by travel restrictions and therefore cannot attend courses personally, individual substitute forms of assessment will be offered to allow for the completion of the required study achievement.