Advanced Topics in Computer Science (236601)

Logical Methods in Combinatorics, Abstracts of lectures

Last updated: 07. Mai 2005

NEW: You can use the program line

psnup -2 -r -d -b10 -pa4 -m10 $1.ps > $1-medium.ps
or
psnup -4 -r -d -b10 -pa4 -m10 $1.ps > $1-small.ps
to print two resp. four slides per page (from ps-file only).

  1. Sunday, March 13, 2005

    Introduction. Motivating examples. Density function and asymptotic probabilities of graph properties.
    Slides in ps of lecture 1 (actual lecture)
    Slides in pdf of lecture 1 (actual lecture)

    Outlook on graph polynomials
    Slides in ps of lecture 1, part 2 (not presented in class)
    Slides in pdf of lecture 1, part 2 (not presented in class)

  2. Sunday, March 20, 2005

    Proof of 0-1 law for first order logic.
    After presentation in Libkin's book Elements of finite model theory, chapter on 0-1 laws.
    Slides in ps of lecture 2 (actual lecture)
    Slides in pdf of lecture 2 (actual lecture)

  3. Sunday, March 27, 2005 (Easter of the Western Church)

    Recapitulation of previous lecture.
    Answering questions.

    Proof of 0-1 law for extensions of first order logic.
    After presentation in Libkin's book chapters 10 and 11
    Slides in ps of lecture 3 (revised 29.3.2005 )
    Slides in pdf of lecture 3 (revised 29.3.2005)

  4. Sunday, April 03, 2005

    Completion of proof of Theorem A.
    More on the expressive power of logics with 0-1 laws.


    Slides in ps of lecture 4
    Slides in pdf of lecture 4

  5. Sunday, April 10, 2005

    More on pebble games.
    Density function of regular languages.


    Slides in ps of lecture 5
    Slides in pdf of lecture 5

  6. Sunday, April 17, 2005

    More on density functions and linear recurrences.
    Why it does not work in general. Case studies.
    Towards Theorem C (Specker-Blatter)


    Slides in ps of lecture 6 (revision posted 30.4.2005)
    Slides in pdf of lecture 6

    PESSACH

  7. Sunday, May 01, 2005
    (Labour Day, Easter of the Eastern Church, Mimouna)

    More on $DU$-index and modular recurrences.

    Proof of the Specker Blatter Theorem for finite degree.


    Slides in ps of lecture 7 and 8
    Slides in pdf of lecture 7 and 8

  8. Sunday, May 08, 2005
    Due to Ceremony, lecture postponed to 16:30, 401 Taub

    Continuation of lecture 7, end of Specker Blatter Theorem.

    Slides (revised and expanded) from Lecture 7-8.

  9. Sunday, May 15, 2005

    New Topic: Graph polynomials. NEW: (posted 07.5.2005 )
    Slides in ps of lecture 9 (identical with part 2 of lecture 1 which was not presented).
    Slides in pdf of lecture 9

  10. Sunday, May 22, 2005

    Continuation of lecture 9 (more examples)

  11. Sunday, May 29, 2005

    Student lecture: Eyal Rosenberg (On tree width of graphs)

  12. Sunday, June 05, 2005

    Feferman Vaught Theorem for Graph polynomials, I

    Shavuot

  13. Sunday, June 19, 2005

    NEW: (posted 20.6.2005 ) Feferman Vaught Theorem for Graph polynomials, II
    Slides in ps of lecture 12-13
    Slides in pdf of lecture 12-13

  14. Sunday, June 26, 2005

    Guest lecture: Eldar Fischer (A counter example to the Specker Blatter Theorem for relations of arity 4)