Erdös Numbers

Paul Erdös (1913—1996), the widely-traveled and incredibly prolific Hungarian mathematician of the highest caliber, wrote hundreds of mathematical research papers in many different areas, many in collaboration with others.

Erdös's Erdös number is 0. Erdös's coauthors have Erdös number 1. People other than Erdös who have written a joint paper with someone with Erdös number 1 but not with Erdös have Erdös number 2 (like myself), and so on. If there is no chain of coauthorships connecting someone with Erdös, then that person's Erdös number is said to be infinite.

My Erdös Number is 2, and it is unlikely that I will be able to improve this :-). I am connected with Erdös via two separate chains of coauthorships of length two.

The first chain is via Carsten Thomassen and the papers:
  1. M. Fellows, M. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen. On the complexity of some colorful problems parameterized by treewidth. Information and Computation, vol. 209, no. 2, pp. 143-153, 2011.
  2. C. Thomassen, P. Erdös, Y. Alavi, P.J. Malde, and A. Schwenk. Tight bounds on the chromatic sum of a connected graph. J. Graph Theory 13 (1989), no. 3, 353-357.
The second chain is via Noga Alon and the papers:
  1. N. Alon and P Erdös. An application of graph theory to additive number theory. European J. Combin. 6 (1985), no. 3, 201-203.
  2. N. Alon, G. Gutin, E.J. Kim, S. Szeider and A. Yeo. Solving MAX-r-SAT Above a Tight Lower Bound. Algorithmica, to appear. A preliminary version appeared in the proceedings of SODA 2010, the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp. 511-517, SIAM, 2010.