COMP 6621: Term project

Winter 2012

COMP 6621: Term project

The aim of the project is to investigate the effect of a particular paper of Paul Erdős (and possibly a co-author or co-authors) on subsequent development of discrete mathematics and computer science. You can work on it on your own or as a part of a team of two or three (but no more than three) students.

By 2 February, send me e-mail to tell me the composition of your team and the paper that you have chosen. This may be any paper from the categories zblmath.fiz-karlsruhe.de/MATH/general/erdos/emis.de/classics/Erdos/
in the list published by Zentralblatt MATH. You will e-mail me
- the URL of the paper's review from the Zentralblat web site,
- the URL of the paper's review from the MathSciNet web site,
- the URL of the paper on the Erdős Papers site
If two or more teams make the same choice, the paper will be assigned to the team whose e-mail I received first.
Papers reserved so far:
- P. Erdős, Chao Ko, R. Rado: Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313-320 (Mathieu Loiselle)
- P. Erdős: Graph theory and probability, II., Canad. J. Math. 13 (1961), 346-352 (Mehdi Abedinpour Fallah)
- P. Erdős, J. Pach, J. H. Spencer: On the mean distance between points of a graph, Congr. Numer. 64 (1988), 121-124 (Tobias Klein)
- B. Bollobás, P. Erdős: Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), 419-427 (Xing Shi Cai, Jason Constandas, Ashkan Ebadi)
- P. Erdős, R. Rado: A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427-489 (Mahmoud Jeet)
- P. Erdős, On integers of the form $2^k + p$ and some related problems, Summa Brasil. Math. 2 (1950), 113-123 (Aryan Bayani, Crystel Bujold)
- P. Erdős, P. Turán: On some problems of a statistical group-theory, I., Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4 (1965), 175-186 (Vincent Gélinas)
- P. Erdős, T. Gallai: On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337--356 (Huining Hu)
- P. Erdős, A. Rényi, On the strength of connectedness of a random graph, Acta Math. Acad. Sci. Hungar. 12 (1961), 261--267 (Julien L'Heureux)
- P. Erdős, L. Lovász, J. H. Spencer: Strong independence of graphcopy functions, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) , pp. 165-172, Academic Press, New York-London, 1979 (Jean-Simon Lapointe)
- P. Erdős, L. Moser, A problem on tournaments, Canad. Math. Bull. 7 (1964), 351-356 (Aziz Chagani)
By 22 March, submit to me a report in .pdf format. This report will include:
1. A short description of the contents of the paper by Erdős. If it solved a problem, where did the problem come from and how long had it been open? What are the proof techniques used here? Which of them had been used before and which of them are novel? What is the importance of this paper?
2. A list of at least ten publications (papers and books) referring to the paper by Erdős that is your starting point (if you cannot get this many, then your choice of the starting point is unsatisfactory) and a list of publications referring to these publications. These lists should be as complete as possible; at the very least, they must contain all the information that you can get from
3. A critical evaluation of these papers and books. Which of these references, if any, are just superficial and which of them rely on the work of Erdős in a substantial way? How?
The ideal length of the report would be five to ten double-spaced pages, excluding references.

Back to COMP 6621 web page