COMP 691E: Term project

Fall 2009

COMP 691E: 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 30 September, 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
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 Alfréd Rényi 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:
- R. B. Eggleton, P. Erdős, D. K. Skilton: Colouring the real line, J. Combin. Theory Ser. B 39 (1985) no. 1, 86--100 (Katherine Edwards).
- P. Erdős, On the difference of consecutive primes. Q. J. Math., Oxf. Ser. 6 (1935), 124-128 (Farzad Aryan).
- P. Erdős, Note on sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935), 126--128 (Antoine Poirier).
- P. Erdős and R.J. Wilson, On the chromatic index of almost all graphs, J. Comb. Theory, Ser. B 23 (1977), 255-257 (Nan Yang).
- P. Erdős, Graph theory and probability, II., Canad. J. Math. 13 (1961), 346--352 (Roberto Persechino)
- P. Erdős, P. Frankl, and Z. Füredi, Families of finite sets in which no set is covered by the union of r others, Israel Journal of Mathematics 51 (1985), 79-89 (Sadegh Bolouki).
- P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, (1980) 125-157 (Hayk Grigoryan).
By 25 November, 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 691E web page