Home | english | Impressum | Sitemap | Intranet | KIT
Arbeitsgruppe Diskrete Mathematik

Sekretariat
Kollegiengebäude Mathematik (20.30)
Zimmer 1.044

Adresse
Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Öffnungszeiten:
Di, Do, Fr 8:30-12:00

Tel.: 0721 608 47412

Fax.: 0721 608 46968

Topics in Discrete Mathematics (Wintersemester 2015/16)

Dozent: Prof. Maria Axenovich Ph.D., Torsten Ueckerdt
Veranstaltungen: Proseminar (0121100)
Semesterwochenstunden: 2


THE BOOK ?

---------------------------------------------------------------------------------------------------------------

>> Paul Erdös liked to talk about THE BOOK, in which God maintains the perfect proofs for mathematical theorems, following the dictum of G. H. Hardy that there is no permanent place for ugly mathematics. Erdös also said that you need not believe in God but, as a mathematician, you should believe in THE BOOK. <<

------------------------------------------------- Martin Aigner, Günter M. Ziegler -----------------------

Termine
Proseminar: Mittwoch 11:30-13:00 SR 3.061
Mathematik
Dozenten
Seminarleitung Prof. Maria Axenovich Ph.D.
Sprechstunde: Donnerstags 15:40-16:40
Zimmer 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Seminarleitung Torsten Ueckerdt
Sprechstunde: Montags 14:00-15:00
Zimmer 1.045 Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu

Description

In this proseminar we have a look at some beautiful gems in discrete mathematics: intriguing problems whose elegant solutions involve clever mathematical applications of linear algebra. The material is taken from two popular books that offer, besides the mathematics, interesting background stories, illustrative examples and helpful pictures in still relatively short chapters:

Proofs from THE BOOKThirty-three Miniatures
"Proofs from THE BOOK""Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra"
by Martin Aigner and Günter M. Zieglerby Jiri Matousek

The topics include a number of classic results in discrete mathematics, such as Hamming codes, the matrix-tree theorem, the Lovasz bound on the Shannon capacity, and a counterexample to Borsuk's conjecture.

Both books are available at the KIT library. "Proofs from THE BOOK" is even available as an online ressource. If you need help with accessing "Thirty-three Miniatures", please contact us.


List of Talks

The following is the schedule for the proseminar. Each topics comes with a list of the relevant chapters from "Proofs from THE BOOK" (labeled P) and "Thirty-three Miniatures" (labeled M).

datespeakertopicsources
Oct 21TorstenIntroduction to Graph Theory and Combinatorics--
Oct 28ChristianThe Dinitz Problem (slides)P36
Nov 4LasseCommunication without ErrorsP41, M5, M28, M29
Nov 11EugenShuffling CardsP30

Note that you do not have to present all the material in the corresponding chapters. You may choose yourself which material to present or contact us in this respect.


Successful Participation

Every student prepares a talk based on a chapter in one of the two books. Successful participation in this proseminar includes, besides a well-prepared talk, presence in the proseminar and active participation.


Prerequisites

Solid knowledge of linear algebra and proof techniques.


Language

The proseminar will be exclusively taught in English. This concerns the provided material, the talks of students, as well as the supervision by the lecturers.