Is there interesting structure in the collaboration graph of Paul Erdös?
I used the "Erdos1" list that resides at the Erdös Number Project home page to populate a nonsymmetrical variant of the "communications matrix" used by sociologists. Here each column represents an Erdös-1 author and each row represents either an Erdös-2 author or an Erdös-1 author who has collaborated with at least one other Erdös-1 author. A cell in the matrix is either zero or one. A nonzero cell indicates coauthorship.
I extracted the largest connected component of the graph, which turned out to be most of it, consisting of 441 columns and 4948 rows. I rearranged the rows and columns (by means of a simulated annealing algorithm) to maximize adjacency along the diagonal. The 441x495-pixel image below represents the 441x4948 matrix squashed vertically for a more readable display. The dark areas represent clusters of individuals who have tended to collaborate with each other. I have identifed the more prolific Erdös-1 (column) authors in the most prominent clusters -- see notes 2 through 5.
<---------- Erdos-1 authors (441) ------------->
^ | | | | Note 2 --> | | | | | | | | | Note 3 --> Erdos-2 authors (4948 -- see Note 1) | | Note 4 --> | | | Note 5 --> | | | | | | | | v
1. Row authors include both Erdös-2 authors and those Erdös-1 authors who collaborated with other Erdös-1 authors.
2. This cluster includes RC Mullin, DR Stinson, CJ Colbourn
3. Includes MK Saks, N Alon, DJ Kleitman, RL Graham, FRK Chung, L Lovasz
4. Includes F Harary, G Chartrand
5. Includes S Shelah
Charles Packer firstname.lastname@example.org