Discrete and Algebraic Structures, WS 2020/2021
Lecture:
MAT.402UB and Moodle
Exercises:
MAT.403UB - use same Moodle as for lecture

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.