Vybrané kapitoly z kombinatoriky I - NDMI055

• Anglický název: Selected Chapters on Combinatorics I
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2014
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jaroslav Nešetřil, DrSc.; Andrew Goodall, D.Phil.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: T_KAM (26.04.2002)

Přednáška určená doktorandskému studiu.

angličtina

Poslední úprava: JUDr. Dana Macharová (01.10.2013)

The selection of topics from combinatorics in this course varies from year to year, but will include aspects of graph homomorphisms, graph polynomials (in particular the Tutte polynomial and related polynomials) and their applications (e.g. in statistical physics), and duality in combinatorics (e.g. colourings and flows, geometric duality, Ramsey duality, categorical duality). The course is offered to doctoral students, and will be given in English. Prerequisite for the course is a background in discrete mathematics and graph theory.

Literatura

čeština

Poslední úprava: IUUK (04.05.2015)

Literatura závisí na zvoleném tématu a bude oznámena během semestru.

angličtina

Poslední úprava: IUUK (04.05.2015)

[1] M. Aigner, A Course in Enumeration, Springer, Berlin-Heidelberg, 2007

[2] B. Bollobás, Modern Graph Theory, Springer, New York, 1998

[3] R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, New York: John Wiley and Sons, 1990

[4] J. Nešetřil, A combinatorial classic - sparse graphs with high chromatic number, IUUK-CE-ITI series no. 572, 2013

[5] D.J.A.Welsh, Complexity: Knots, Colourings and Counting, Cambridge Univ. Press, Cambridge 1993

Other references will be given during the course.

Sylabus

čeština

Poslední úprava: IUUK (04.05.2015)

Přednáška určená magisterskému i doktorandskému studiu.

This year (2013) we shall focus on duality and its relationship to the Tutte polynomial, and on the historical context surrounding seminal combinatorial results of Tutte, Erdős (high girth and chromatic number) and Ramsey (his eponymous theorem for coloured graphs). There may also be time to study polynomials related to the Tutte polynomial, such as the Jones polynomial of a knot, and the Penrose polynomial of a plane graph.

angličtina

Poslední úprava: IUUK (04.05.2015)

This year (2013) we shall focus on duality and its relationship to the Tutte polynomial, and on the historical context surrounding seminal combinatorial results of Tutte, Erdős (high girth and chromatic number) and Ramsey (his eponymous theorem for coloured graphs). There may also be time to study polynomials related to the Tutte polynomial, such as the Jones polynomial of a knot, and the Penrose polynomial of a plane graph.