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