Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Combinatorics and Graph Theory 1 - NDMI011

Title:	Kombinatorika a grafy 1
Guaranteed by:	Computer Science Institute of Charles University (32-IUUK)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
Semester:	winter
E-Credits:	5
Hours per week, examination:	winter s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	doc. RNDr. Vít Jelínek, Ph.D. doc. RNDr. Jiří Fiala, Ph.D.
Class:	Informatika Bc.
Classification:	Informatics > Discrete Mathematics
Incompatibility :	NDMA001, NDMX011
Interchangeability :	NDMX011
Is incompatible with:	NDMI031, NDMX011
Is pre-requisite for:	NDMI069, NDMI021, NDMI068, NPFL049
Is interchangeable with:	NDMA001, NDMI031, NDMX011

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

Last update: PANGRAC/MFF.CUNI.CZ (08.04.2010)

Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.

Course completion requirements -

Last update: Irena Penev, Ph.D. (29.09.2020)

Irena Penev (Winter 2020/2021): To obtain tutorial credit, students must obtain at least 40% total on HW assignments. The lowest two HW scores will be dropped. To take the exam, students must first obtain tutorial credit.

Literature -

Last update: doc. RNDr. Vít Jelínek, Ph.D. (22.11.2012)

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)

R. Diestel: Graph Theory (4th edition), Springer (2010)

Requirements to the exam -

Last update: Irena Penev, Ph.D. (29.09.2020)

Irena Penev (Winter 2020/2021): To take the exam, students must first obtain tutorial credit. The exam will be written, and it will consist of problems similar to HW problems from the tutorial (English section). It will be possible to take the exam online (over Zoom). Depending on the COVID-19 situation, it may or may not be possible to take the exam in person at the Department.

Syllabus -

Last update: doc. RNDr. Vít Jelínek, Ph.D. (06.09.2023)

Double Counting: Sperner Theorem, The maximum number of edges in a graph without C4 and without K3.

Number of spanning trees (determinant proof) and electrical networks.

Generating functions (understood as Taylor series), applications: Catalan, Fibonacci numbers, solving recurrences, asymptotics of the solution.

Finite projective planes.

Error-correcting codes, basic properties. Hammnig code, Hadamard code. Existence of asymptotically good codes (Gilbert-Varshamov). Hamming's lower bound.

Maximum matching in graphs, Hall's theorem and its applications (Birkhoff-von Neumann theorem), Tutte theorem.

k-connectivity, Menger's theorem. Ear lemma, structure of 2-connected graphs.

Ramsey theorem, Ramsey theorem for p-tuples, Ramsey infinite theorem.

König's theorem on the infinite branch.

Course web page (Irena Penev, Winter 2020/2021): https://iuuk.mff.cuni.cz/~ipenev/NDMI011.html