Course description: Paul Erdős (1913 -- 1996) was one of the greatest mathematicians of the twentieth century. He made pre-eminent contributions to number theory, probability theory, real and complex analysis, discrete geometry, approximation theory, and set theory; some say that he founded the field of discrete mathematics.We will study a selection of his results in number theory, geometry, Ramsey theory, extremal combinatorial problems, and graph theory; in doing so, we shall highlight his methods and proof techniques -- such as the probabilistic method -- that are particularly applicable to computer science. From time to time we will stray from his own work to the work of his disciples, but we shall never escape the gravitational pull of the great man. More detailed outline: Proof of Bertrand's postulate. The Erdős -Szekeres and the de Bruijn-Erdős theorems. Ramsey's theorem and Ramsey numbers. Property B and hypergraph colouring. Van der Waerden's theorem and van der Waerden numbers. Positional games. The Erdős -Ko-Rado theorem. Delta-systems and a proof of the Erdős -Lovász conjecture. Extremal graph theory. Random graphs and graph colouring. The probabilistic method and its applications in theoretical computer science.

The subject and the instructor, ca.1976

• Instructor: Vašek Chvátal
  • Phone: (514) 848-2424   ext. 5767
    
  • Email:     c h v a t a l (at) c s e (dot) c o n c o r d i a (dot) c a
    
  • Office: Engineering, Computer Science, and Visual Arts Complex (EV) 3.107,
    1515 Ste-Catherine West
    
  • Office hours: by appointment

• Classes: Wed 17:45 -- 20:15 in H-537, 1455 de Maisonneuve West.
  

• Prerequisities: Ease with the notation of elementary set theory and with matrix descriptions of systems of linear equations.

• Grading scheme: There will be four homework assignments, a project, a midterm exam, and a final exam. The two exams will be closed-book exams (meaning that the students will be denied access to books, calculators, notes, etc.) and the final will be cumulative (meaning that it can draw on any material covered in the course). The overall numerical score will be calculated as 10% homework + 30% project + 20% midterm + 40% final. Letter grades will be derived from numerical scores roughly as follows:
  • score of at least 95 corresponds to A+
  • score of at least 85 and less than 95 corresponds to A
  • score of at least 75 and less than 85 corresponds to A-
  • score of at least 65 and less than 75 corresponds to B+
  • score of at least 55 and less than 65 corresponds to B
  • score of at least 50 and less than 55 corresponds to B-
  • score of at least 40 and less than 50 corresponds to C
  • score of less than 40 corresponds to F
  This guideline may be adjusted so as not to give students with very close numerical scores differing letter grades.

  Students who will make significant progress towards the solution of any open problem on the list posted here will get the grade of A+ regardless of their numerical score.

• Sources:
  
  • P. Erdős, Beweis eines Satzes von Tschebyschef, Acta Litt. Sci. Szeged 5 (1932), 194--198.
    See also:
    • P. Erdős, Ramanujan and I, Number theory, Madras 1987, Lecture Notes in Math., 1395 , pp. 1--20, Springer, Berlin-New York, 1989.
    • Ramanujan's proof of Bertrand's postulate (pp. 208 --209)
  • P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935), 463--470.
  • N.G. de Bruijn and P. Erdős, On a combinatorial problem, Nederl. Akad. Wetensch., Proc. 51, (1948), 1277--1279 = Indagationes Math. 10, 421--423 (1948). MR0028289
    • V. Chvátal and X. Chen, Problems related to a de Bruijn - Erdős theorem, Discrete Applied Mathematics 156 (2008), 2101 - 2108. (arXiv:math/0610036v1 [math.CO].)
    • V. Chvátal and E. Chiniforooshan, A de Bruijn - Erdös theorem and metric spaces, arXiv:0906.0123v1 [math.CO].
  • J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley, 1995.
  • P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53, (1947), 292--294. MR0019911
  • V. Chvátal, P. Erdős, and Z. Hedrlín, Ramsey's theorem and self-complementary graphs, Discrete Math. 3 (1972), 301--304. MR0313119
  • S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics (2004), DS1.10
  • P. Erdős, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5--10, 40. MR0148554
  • P. Erdős, On a combinatorial problem. II, Acta Math. Acad. Sci. Hungar 15 (1964), 445--447. MR0167427
  • V. Chvátal, Hypergraphs and Ramseyian theorems, Proc. Amer. Math. Soc. 27 (1971), 434--440. MR0270972
  • P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2, (1952), 417--439. MR0065615
    • V. Chvátal, Some unknown van der Waerden numbers, in: Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 31--33 Gordon and Breach, New York, 1970 MR0266891
    • Some New Van der Waerden Numbers and Some Van der Waerden-type Numbers by Tanbir Ahmed, INTEGERS: The Electronic Journal of Combinatorial Number Theory 9 (2009).
  • R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory, Wiley, 1990.
  • P. Erdős and J.L. Selfridge, On a combinatorial game, J. Combinatorial Theory Ser. A 14 (1973), 298--301. MR0327313
  • V. Chvátal and P. Erdős, Biased positional games, in: Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). Ann. Discrete Math. 2 (1978), 221--229. MR0500701
  • P. Erdős, Chao Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313--320. MR0140419
  • V. Chvátal, Some linear programming aspects of combinatorics, in: Proceedings of the Conference on Algebraic Aspects of Combinatorics (Univ. Toronto, Toronto, Ont., 1975), pp. 2--30. Congressus Numerantium, No. XIII, Utilitas Math., Winnipeg, Man., 1975. MR0408802
  • P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85--90. MR0111692
  • M. Deza, Une propriété extrémale des plans projectifs finis dans une classe de codes équidistants, Discrete Math. 6 (1973), 343--352. MR0332310
  • M. Deza, Solution d'un problème de Erdős -Lovász, J. Combinatorial Theory Ser. B 16 (1974), 166--167. MR0337635
  • V. Chvátal, Cutting planes in combinatorics, European J. Combin. 6 (1985), 217--226. MR0818595
  • P. Erdős, On the graph theorem of Turán (in Hungarian), Mat. Lapok 21 (1970), 249--251 (1971). MR0307975
  • V. Chvátal, Hamiltonian cycles, in: The traveling salesman problem, 403--429, Wiley-Intersci. Ser. Discrete Math., Wiley, Chichester, 1985. MR0811478
  • P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52, (1946), 1087--1091. MR0018807
  • P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar 1 (1966), 51--57. MR0205876
  • V. Chvátal and P. Erdős, A note on Hamiltonian circuits, , Discrete Math. 2 (1972), 111--113. MR0297600
  • P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34--38. MR0102081
  • P. Erdős, On circuits and subgraphs of chromatic graphs, Mathematika 9 (1962), 170--175. MR0145504
  • P. Erdős and S. Fajtlowicz, On the conjecture of Hajós, Combinatorica 1 (1981), 141--143. MR0625546
  • V. Chvátal, Probabilistic methods in graph theory, Ann.Oper.Res. 1 (1984), 171--182.
  • P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17--61. MR0125031
  • E.M. Palmer, Graphical evolution. An introduction to the theory of random graphs, Wiley, 1985. MR0795795
  • N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 2000.
  • V. Chvátal and E. Szemerédi, Many hard examples for resolution, J. Assoc. Comput. Mach. 35 (1988), 759--768. MR1072398
  • V. Chvátal and B. Reed, Mick gets some (the odds are on his side), in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Washington, 1992, pp. 620--627.

• Additional reading:

  • Collected Papers of Paul Erdős
    • Index
  • The Prime Pages of Chris K. Caldwell
  • B.Green and T.Tao, The primes contain arbitrarily long arithmetic progressions
  • Adrian Bondy and U.S.R. Murty, Graph Theory with Applications
  • L. Babai, C. Pomerance, and P. Vértesi, The Mathematics of Paul Erdős , Notices of the AMS, January 1998, 19--31.
  • F.R.K. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), 3--36. MR1441976
  • Ronald L. Graham and Fan R. K. Chung, Erdős on Graphs: His Legacy of Unsolved Problems. A K Peters, 1998.
  • Erdős conjectures from Wikipedia
  • M. Aigner and G.M. Ziegler, Proofs from the Book, Third edition. Springer-Verlag, Berlin, 2004. MR2014872
  • Bruce Schechter, My Brain is Open : The Mathematical Journeys of Paul Erdős , Simon & Schuster, 1998.
  • Paul Hoffman, The Man Who Loved Only Numbers , Hyperion, 1999.

• Class cancellations
• Code of Conduct (Academic)

• The statue of Anonymous
• The MacTutor History of Mathematics archive
• The Search for a Finite Projective Plane of Order 10 by C. W. H. Lam
• Take-home midterm (due on Wednesday October 21 in class).
  • Solution: Theorem 1 (pages 10 -- 11) in the lecture notes and paragraph 8 (the last two pages), P. Erdős and R.  Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2, (1952), 417--439.
    Hayk Grigoryan pointed out that the lower bound can be improved by the use of the Lovász Local Lemma: see Zoltán Szabó, An application of Lovász' local lemma -- a new lower bound for the van der Waerden number, Random Structures Algorithms 1 (1990), 343 -- 360.

• Two events on Friday 6 November:
  • Lecture by Daina Taimina at 14:15 in EV-1.605.
  • Screening of two films by George Csicsery:
    "N is a Number: A Portrait of Paul Erdős " and "To Prove and Conjecture: Excerpts from Three Lectures by Paul Erdős" at 18:00 in H-621.

• Field medalists
• The Two Cultures of Mathematics by W. T. Gowers.
• Selected combinatorial research problems (V.C., D.A. Klarner, and D.E. Knuth), STAN CS-72-292, June 1972.

• Solutions of problems from the final exam
• Grades

• Expectation of Originality Form
• Instructions for electronic assignment submissions

• Homework 1 (due on Wednesday September 30 in class).
  • Solution
• Homework 2 (due on Wednesday October 14 in class).
  • Solution
• Take-home midterm (due on Wednesday October 21 in class).
  • Solution: Theorem 1 (pages 10 -- 11) in the lecture notes and paragraph 8 (the last two pages) in P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2, (1952), 417--439.
    Hayk Grigoryan pointed out that the lower bound can be improved by the use of the Lovász Local Lemma: see Zoltán Szabó, An application of Lovász' local lemma -- a new lower bound for the van der Waerden number, Random Structures Algorithms 1 (1990), 343 -- 360.
• Homework 3 (due on Wednesday November 18 in class).
  • Solution
• Homework 4 (due on Wednesday December 2 in class).

Erdős quotations Property is a nuisance. There will be plenty of time to rest in the grave. A theorem a day means promotion and pay; a theorem a year and you're out on your ear. Another roof, another proof. Favourites of Erdős, often attributed to him, but originating elsewhere A mathematician is a machine for turning coffee into theorems. (Alfréd Rényi) Chebyshev said it, and I say it again: There is always a prime between n and 2n. (Nathan Fine) Erdős links Erdős site from Zentralblatt für Mathematik Erdős page from the Mathematical Institute in Budapest References and links to information about Erdős from the Erdös Number Project. Biography from MacTutor Two films by George Csicsery: "N is a Number: A Portrait of Paul Erdős " and "To Prove and Conjecture: Excerpts from Three Lectures by Paul Erdős ". Distributed by MAA Bookstore A letter from Erdös to a president of the University of Waterloo renouncing his honorary degree. (This was one of the outcomes of a conflict between Adrian Bondy and the University.) Articles on Erdős Obituaries from The New York Times and The Washington Post Paul Erdős (1913 -- 1996) by László Babai and Joel Spencer Paul Erdős and Combinatorics by Adrian Bondy Reminiscences of Paul Erdös (1913-1996) by Melvin Henriksen Remembering Paul Erdős by Aleksandar Ivić Two Places at Once (A Remembrance of Paul Erdős ) by János Pach Paul Erdős ; An Infinity of Problems by Ivars Peterson

The P. G. O. M. and an epsilon

To Vašek Chvátal's home page