Summary of Lectures and links to posted slides

Posted slides

• Part 1 (99 slides), Using Logic to define graph properties and formal languages.
  Dydactic goal: To be able to use (read and write) Second Order logic SOL and its fragments. Special attention to graph classes defined by forbidden substructures, induced substructures, topological minors and minors.
• Part 2 (85 slides), continuation of Part 1.
  Dydactic goal: We show that reglar languages are MSOL-definable. We discuss the role of a linear order on the structures and show that not all graph properties are SOL-definable. HEX and GEOGRAPHY. The complexity classes we will use, and how to possibly separate them. The complexity of evaluating formulas of certain fragments of SOL.
• Part 3, Proving non-definability and the Buchi-Elgot-Trakhtenbrot Theorem (BET Theorem).
  Dydactic goal: To be able to prove non-definability in First Order (FOL) and Monadic Second Order Logic (MSOL) using Ehrenfeucht-Fraisse games aka Back-and-Forth Games.
• Part 4, Translation schemes and the Ferman-Vaught Theorem, Hintikka and Hankel matrices, non-definability via Hankel matrices, SOL-definability of numeric graph parameters.
  Dydactic goal: To be able to prove non-definability in First Order (FOL) and Monadic Second Order Logic (MSOL) using Hankel matrices. Extending the method to numeric parameters of graphs and relational structures.
• Part 5, The Lindstrom Theorems and Implicit definability for FOL with infinite models.
  Dydactic goal: Use EF-games and translation schemes to characterize FOL allowing infinte structures.
• Combinatorics Seminar Lecture 5, The Specker Blatter Theorem.
  The earliest application of Logic to finite combinatorics. A survey with research problems.
• Course and research projects

Not yet posted slides

• Part 6, Automata and Turing machines as relation structures

Summaries of lectures

1. October 28: Part 1, Slides 1-56.
2. November 4: Part 1, Slides 57-99
3. November 11: Part 2, Slides 1- 53
4. November 18: Part 2, Slides 54-99

   ---

5. November 25: Part 3, Slides 01-62

   ---

   ---

   Chanuka

   ---

6. December 9: Part 3, Slides 63-99
7. December 16: Part 4, Slides 01-60
8. December 23: Part 4, Slides 61-90

   ---

   Christmas

   ---

9. December 30: Part 4, Slides 91-132, Part 5, Slides 1-17 (repeated in the next session)

   ---

   Secular New Year

   ---

10. January 6: Part 5, Slides 1-27, Slides about the Specker Blatter Theorem,
    Distributing projects.
11. January 13: Part 5, Slides 31-43. Slides describing projects.
12. January 20: Part X, Slides xx-yy
13. January 27: Part X, Slides xx-yy

    ---

    End of Teaching

    ---