SubjectsSubjects(version: 928)
Course, academic year 2022/2023
   Login via CAS
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
Virtual mobility / capacity: no
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Additional information:
Guarantor: 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
Annotation -
Last update: prof. RNDr. Tomáš Bureš, Ph.D. (15.11.2019)
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.
Course completion requirements -
Last update: Mgr. Tereza Klimošová, Ph.D. (18.11.2019)

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

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

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.

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

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.

Charles University | Information system of Charles University |