Subjects

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

Discrete Mathematics of Paul Erdős - NDMI107

Title:	Discrete Mathematics of Paul Erdős
Guaranteed by:	Department of Applied Mathematics (32-KAM)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2019
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English, Czech
Teaching methods:	full-time
Additional information:	https://kam.mff.cuni.cz/~chvatal/NDMI107

Guarantor:	prof. Václav Chvátal, Ph.D.
Teacher(s):	prof. Václav Chvátal, Ph.D.
Classification:	Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science

Opinion survey results Examination dates Noticeboard

Annotation -

Paul Erdős (1913 -- 1996) was an outstanding, prolific, influential, legendary mathematician. We will study a selection of his results in number theory, geometry, Ramsey theory, extremal combinatorial problems, and graph theory that laid the foundations of discrete mathematics before it matured into the rich and vibrant disciplin of today. From time to time we will stray from his own work to the work of his confrères and disciples, but we shall never escape the gravitational pull of the great man.

Last update: Bureš Tomáš, prof. RNDr., Ph.D. (15.11.2019)

Course completion requirements -

To learn the subject as described in the syllabus and be able to solve appropriate problems.

Last update: Klimošová Tereza, Mgr., Ph.D. (18.11.2019)

Literature -

Collected Papers of Paul Erdős up to 1989

S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics DS1: Mar 3, 2017

F.R.K. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), 3-36.

Ronald L. Graham and Fan R. K. Chung, Erdős on Graphs: His Legacy of Unsolved Problems. A K Peters, 1998.

J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley, 1995.

R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory, Wiley, 1990.

E.M. Palmer, Graphical evolution. An introduction to the theory of random graphs, Wiley, 1985.

N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 2016.

V. Chvátal, A De Bruijn-Erdős theorem for graphs? In: Graph Theory Favorite Conjectures and Open Problems - 2, edited by Ralucca Gera, Teresa W. Haynes, and Stephen T. Hedetniemi, Springer Nature Switzerland (2018), pp. 149--176.

Last update: Klimošová Tereza, Mgr., Ph.D. (18.11.2019)

Syllabus -

Proof of Bertrand's postulate. The Erdős-Szekeres, the Sylvester-Gallai, and the De Bruijn-Erdős theorems. Ramsey's theorem and Ramsey numbers. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. Sperner's theorem and the Erdős-Ko-Rado theorem. Turán numbers. Property B and hypergraph colouring. Van der Waerden's theorem and van der Waerden numbers. Extremal graph theory. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. Chromatic number of graphs and the probabilistic method. The Erdős-Rényi random graphs and their evolution. Hamilton cycles.

Last update: Bureš Tomáš, prof. RNDr., Ph.D. (15.11.2019)