Erd\H{o}s numberErdHosNumber2006-09-18 13:50:042006-09-19 17:30:33Definition% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
The shortest number of collaborations with other mathematicians through which a particular mathematician can be connected to Paul Erd\H{o}s is the {\em Erd\H{o}s number} of that mathematician. For example, N. J. A. Sloane coauthored {\it Sphere Packings, Lattices and Groups} with John Horton Conway. In turn, Conway coauthored a paper with Erd\H{o}s in 1979, thus Sloane's Erd\H{o}s number is 2. Since Erd\H{o}s died in 1996, 2 is the lowest Erd\H{o}s number a mathematician working today can achieve.
One way to visualize the Erd\H{o}s number is by drawing up a collaboration graph $G$ whose vertex set consists of all persons, where two vertices $x$ and $y$ are connected by an edge if and only if $x$ and $y$ have a joint publication. Then the Erd\H{o}s number of a person $x$ is the distance in $G$ (possibly infinity) of $x$ from Erd\H{o}s.