hlavni banner

kudy kam

Jan Kratochvil - Výuka v zimním semestru ak. roku 2019/20

NMAG403 Kombinatorika - pondeli 15:40 v K12
First exam is on Thursday Dec 19 at 2 p.m. in S10. Topics examined are below.

References for graph theory are to the textbook R. Diestel: Graph Thoery, most topics can also be found in Czech in skripticka Tomase Vally .
Network flows. (Chapter 6.2)
Systems of distinct representatives and Hall theorem. (Thm 2.1.2)
Matchings in general graphs, Tutte theorem. (Thm 2.2.1)
Edmonds algorithm for maximum matching. (http://en.wikipedia.org/wiki/Blossom_algorithm)
Vertex- and edge-connectivity of graphs. (Chapters 3.1, 3.2, 3.3)
Planar graphs, Kuratowski theorem (Chapter 4.4)
Hamiltonian cycles in graphs (Chapter 10.1), Smith theorem on Ham cycles in cubic graphs (A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs (Advances in Graph Theory, Cambridge Combinatorics Conference, Trinity College. Cambridge, 1977,) Ann. Discrete Math. 3 (1978) 259-268).

References for combiatorial structures are from Marshall Hall: Combinatorial Theory, Wiley 1986.
Latin squares, finite projective planes and orthogonal arrays. (Chapters 13.1, 12.3, 13.2)
Construction of 2 orthogonal Latin squares of order 12t+10. (Chapter 13.3 - Thm 13.3.1)
Block designs BIBD(v,k,lambda). Relations among the parameters, Fisher inequality. (Chapters 10.1., 10.2)
Symmetric designs. Bruck-Ryser-Chowla theorem. (Chapter 10.3)
Steiner triple systems. Algebraic formulation. Construction for all v=1,3 mod 6. (Chapter 15.4) Construction by Bose and Skolem can be found in Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press.
Hadamard matrices. (Chapter 14.1)
The topic covered in the class in January is Hamiltonicity of the block intersection graph of any BIBD, see A.A. Abueida and D.A. Pike. Cycle extensions in BIBD block-intersection graphs, Journal of Combinatorial Designs 21 (2013) 303-310.


NDMI037 Geometricke reprezentace grafu I - utery 14:00 v S11


Konzultační hodiny

různě - po emailové dohodě


poslední aktualizace 9.10. 2019

© m@f# for contents, RooT for design