Erdős Number

While I’m not strictly speaking a mathematician, I always wondered what my Erdős Number would be. The Erdős number of an author is calculated the following way: Paul Erdős has number 0, people who have coauthored a paper with him have a number 1, people who co-wrote papers with people with a number of 1 have a number of 2, etc.
So I took advantage of this snowy Sunday to search for a path between Paul Erdős and myself. If you have published mathematical papers, you just need to search for yourself on the collaboration distance tool. But as I have not published any mathematical paper, I had to try out the various people I wrote papers with, and see what would come out. I then had to look for the people they wrote with to find a better path. I found the following four step path:

  1. Paul Erdős → Stanley M. Selkow: Random graph isomorphism.
  2. Stanley M. Selkow → Giovanni Coray: Order independence in local clustering algorithms.
  3. Giovanni Coray → André Schiper: Une structure de contrôle à deux niveaux pour la programmation heuristique parallèle.
  4. André Schiper → Matthias Wiesmann: Beyond 1-safety and 2-safety for replicated databases: Group-safety

The first five step path I had found was the following:

  1. Paul Erdős → Shmuel Zaks: Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
  2. Shmuel Zaks → Gerard Tel: Optimal synchronization of ABD networks
  3. Gerard Tel → Bernadette Charron-Bost: Synchronous, asynchronous, and causally ordered communication
  4. Bernadette Charron-Bost → André Schiper: Uniform consensus is harder than consensus
  5. André Schiper → Matthias Wiesmann: Beyond 1-safety and 2-safety for replicated databases: Group-safety

But there is at least another 5 step possibility:

  1. Paul Erdős → Ronald L. Graham: On sums of Fibonnaci numbers.
  2. Ronald L. Graham → John L. Bruno: Computer and job-shop scheduling theory.
  3. John L. Bruno → Divyakant Agrawal: Relative serializability: an approach for relaxing the atomicity of transactions.
  4. Divyakant Agrawal → Gustavo Alonso: Advanced Transaction Models in Workflow Contexts.
  5. Gustavo Alonso → Matthias Wiesmann: Understanding replication in databases and distributed systems.

I also found two different paths of length 6:

  1. Paul Erdős → Fan Chung: On the product of the point and line covering numbers of a graph
  2. Fan Chung → Patrick Solé: Patrick Multidiameters and multiplicities
  3. Patrick Solé → Peter J. Olver: Generalized transvectants and Siegel modular forms
  4. Peter J. Olver → Metin Arık: Multi-Hamiltonian structure of the Born-Infeld equation
  5. Metin Arık → Gökhan Ünel: q-oscillators, the q-epsilon tensor and quantum groups
  6. Gökhan Ünel → Matthias Wiesmann: Deployment and use of the ATLAS DAQ in the combined test beam
  1. Paul Erdős → Alexander Rosa: Decompositions of complete graphs into factors with diameter two.
  2. Alexander Rosa → Jean-Claude Bermond: Decomposition of complete graphs into isomorphic subgraphs with five vertices.
  3. Jean-Claude Bermond → Michel Raynal: General and efficient decentralized consensus protocols.
  4. Michel Raynal → Maria Gradinariu: Stabilizing mobile philosophers.
  5. Maria Gradinariu → Xavier Défago: Fault-tolerant and self-stabilizing mobile robots gathering – feasibility study.
  6. Xavier Défago → Matthias Wiesmann: Anonymous stabilizing leader election using a network sequencer.

Edit:
I found three new paths giving me a level four:

  1. Paul Erdős → Shlomo Moran Extremal problems on permutations under cyclic equivalence
  2. Shlomo Moran → Hagit Attiya Computing in totally anonymous asynchronous shared memory system
  3. Hagit Attiya → André Schiper Structured derivation of semi-synchronous algorithms.
  4. André Schiper → Matthias Wiesmann Understanding replication in databases and distributed systems
  1. Paul Erdős → Pavol Hell Graph theory in memory of G. A. Dirac
  2. Pavol Hell → Masafumi Yamashita Graph endpoint coloring and distributed processing
  3. Masafumi Yamashita → Xavier Défago The gathering problem for two oblivious robots with unreliable compasses.
  4. Xavier Défago → Matthias Wiesmann: Anonymous stabilizing leader election using a network sequencer.
  1. Paul Erdős → Pavel Valtr Pavel Ramsey-remainder
  2. Pavel Valtr → Ivan Stojmenović Whitesides, Sue The largest k-ball in a d-dimensional box.
  3. Ivan Stojmenović → Julien Iguchi-Cartigny Localized minimum-energy broadcasting for wireless multihop networks with directional antennas
  4. Julien Iguchi-Cartigny → Matthias Wiesmann: Collision Prevention Platform for a Dynamic Group of Asynchronous Cooperative Mobile Robots.

Edit:
Microsoft now has a tool to visualise such paths, which gives me four other paths of length four. Here is the embedded visualisation (requires Silverlight).

4 thoughts on “Erdős Number”

  1. What about fractional erdoes number? Like dividing by the number of disjoint paths to Erdoes? My frac EN is one i think..

  2. I would have imagined that Erdoes number would be the minimum value of the set of path lengths. So, in my mind, you have an Erdoes number of four. That’s probably pretty impressive, I’d think, were I able to properly appreciate the significance. Congrats!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.