Summary of Lectures and links to posted slides
Under construction
Last updated: January 10, 2022 (previous update December 30, 2021)
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 MSOLdefinable.
We discuss the role of a linear order on the structures and show that not all graph properties
are SOLdefinable. 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 nondefinability and
the BuchiElgotTrakhtenbrot Theorem (BET Theorem).
Dydactic goal: To be able to prove nondefinability in First Order (FOL) and Monadic Second Order Logic (MSOL)
using EhrenfeuchtFraisse games aka BackandForth Games.

Part 4, Translation schemes and the FermanVaught Theorem, Hintikka and Hankel matrices,
nondefinability via Hankel matrices, SOLdefinability of numeric graph parameters.
Dydactic goal: To be able to prove nondefinability 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 EFgames 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

October 28: Part 1, Slides 156.

November 4: Part 1, Slides 5799

November 11: Part 2, Slides 1 53

November 18: Part 2, Slides 5499

November 25: Part 3, Slides 0162
Chanuka

December 9: Part 3, Slides 6399

December 16: Part 4, Slides 0160

December 23: Part 4, Slides 6190
Christmas

December 30: Part 4, Slides 91132, Part 5, Slides 117 (repeated in the next session)
Secular New Year

January 6: Part 5, Slides 127, Slides about the Specker Blatter Theorem,
Distributing projects.

January 13: Part 5, Slides 3143. Slides describing projects.

January 20: Part X, Slides xxyy

January 27: Part X, Slides xxyy
End of Teaching