Combinatorics and graph theory 2 2022 fall
Requirements:
Homeworks each week. 1 or 2 problems per week, each problem worth 10 points. Homework points are topped at 100 which is equivalent to 10% in your total score. If you have more than 100 points then it is also considered 10%. The deadline for submission is two weeks after they are announced.
Two midterms on 12th of October and 28th of November at lecture time, which require problem solving. Theorems, definitions and proofs will not be asked in the midterms, but you may need some of them to solve the problems.
40% of the possible points are required to pass each of them and obtain signature. 2 retake occasions later.
Oral exam in the exam period.
Midterm(s):
There will be 2 midterms during the semester. Both midterms contain 6 problems, which are similar to the practice problems. Each problem worth 10 points. 24 points are required to pass a midterm. You need to pass both midterms to receive signature.
Dates:
1st midterm 12th of October at lecture time
2nd midterm 28th of November at lecture time
Retake of the 1st midterm: 12th of December, 10:00 Building I IB.134
Retake of the 2nd midterm: 12th of December, 13:00 Building I IB.134
2nd retake occasion: 16th of December, 10:00 IB.134, You need to apply for it in the NEPTUN system
Exams:
There will be in person oral exams. Check the Neptun system for date and location. You need to apply in the Neptun system at least a day before.
You will receive one topic from the topic sheet and you will have half an hour for preparation.
Grading:
The final grade is combined of the above with the following weights:
Homework: 10%
Midterms: 40%
Oral exam: 50%
Agenda:
Week |
Time |
Info |
Problem sheet/notes |
1. |
5th of September |
|
Perfect graphs |
7th of September |
|
Perfect graphs practice, some not complete solutions |
2. |
12th of September |
|
Proof of the weak perfect graph theorem |
14th of September |
No lecture |
|
3. |
19st of September |
|
Posets, Dilworth's theorem, Mirsky's theorem. Direct proof of Dilworth's thm was not discussed |
21nd of September |
|
Poset practice, some not complete solutions |
4. |
26th of September |
|
Planar graphs, Euler's formula, Kuratowsky's theorem |
28th of September |
|
Planar graph practicesome not complete solutions |
5. |
3rd of October |
|
Dual graph, Whitney's theorems |
5th of October |
|
Planar graps, duality practice, some not completesolutions |
6. |
10th of October |
|
List coloring, Voights example was discussed at the next lecture. |
12th of October |
1st midterm |
|
15th of October |
Instead of 31st of October |
List coloring practice, some not completesolutions |
7. |
17th of October |
|
Ramsey type problems. (pages 1-3 were discussed) |
19th of October |
|
Ramsey practice, Solutions |
8. |
24th of October |
|
Ramsey type problems. (pages 4-5 were discussed) |
26th of October |
|
Ramsey II practice, Solutions |
9. |
31st of October |
No lecture |
|
2nd of November |
|
Turán's theorem |
10. |
7th of November |
|
Turán practice, Solutions |
9th of November |
|
Erdős-Stone theorem, Erdős-Simonovits |
11. |
14th of November |
|
Erdős-Ko-Rado, Fischer, Ray-Chaudhuri-Wilson, De Bruijn-Erdos |
16th of November |
|
Extremal Set theory practice 1., Solutions |
12. |
21st of November |
|
Sperner systems, LYM inequality |
23rd of November |
|
Extremal Set theory practice 2. |
13. |
28th of Novermber |
2nd Midterm |
|
30th of November |
|
Generating functions, Fibonacci numbers, Homogenous linear recurrences |
14. |
5th of December |
|
Catalan numbers |
7th of December |
|
Linear recurrences, Catalan numbers practice |