\problemdata     
{relations-6}           
{relations, composition, Erdos numger}              
{Rosen 6.supplementary.14}              
{SO2 ps3} 		
{SO2 Radhika}        	


\begin{problem} (Rosen \S 6, Supplementary Exercise 14) Let $R$ be the
relation on the set of all mathematicians that contains the ordered
pair (a,b) if and only if $a$ and $b$ have written a paper together

\begin{problemparts}
\problempart Describe the relation $R^2$.

\solution{Two mathematicians are related under $R^2$ if and only if
each has written a joint paper with some mathematician $c$.}

\problempart Describe the relation $R^*$.

\solution{Two mathematicians are related under $R^*$ if there is a
finite sequence of mathematicians $a=c_0, c_1, c_2,..., c_{m-1},
c_m=b$, with $m \geq 1$, such that for each $i$ from 1 to $m$,
mathematician $c_i$ has written a joint paper with mathematician
$c_{i-1}$.}

\problempart The \textit{Erd\H{o}s number} of a mathematician is 1 if
this mathematician wrote a paper with the prolific Hungarian
mathematician Paul Erd\H{o}s, it is 2 if this mathematician did not
write a joint paper with Erd\H{o}s but wrote a joint paper with
someone who wrote a joint paper with Erd\H{o}s, and so on (except that
the Erd\H{o}s number of Erd\H{o}s himself is 0). Give a definition of
the Erd\H{o}s number in terms of paths in $R$.

\solution{The Erd\H{o}s number of $a$ is the length of a shortest path
in $R$ from $a$ to Erd\H{o}s, if such a path exists.  (Some
mathematicians have no Erd\H{o}s number).}

\end{problemparts}
\end{problem}
