Число Эрдёша

Число Эрдёша показывает количество соавторов между произвольно взятым человеком и великим математиком Полом Эрдёшем.
Под соавторством понимается совместная работа двух и более человек на какую-нибудь научную тему.
Термин был назван по имени Пола Эрдёша, прославившегося тем, что написал, по его собственным словам, 1200+ε (заметьте, до 9000 не дотянул) научных работ, причём треть из них была написана в соавторстве. Соавторство же в математике — вещь исключительная, ибо суровый математик, как правило, работает в одиночку. А посему такой из ряда вон выходящий случай привлёк к себе внимание, и всем стало любопытно узнать, можно ли связать математиков воедино при помощи соавторских работ, или же нет. Как подсказывает педивикия, 90% математиков имеют Число Эрдёша не более 8, что как бы говорит нам, что таки да, связь существует.
Возникает закономерный вопрос: а как же его, родимого, подсчитать-то? Да очень просто.
Данная процедура часто используется в программировании и даже имеет специальное название «поиск в ширину».

Эрдёш Пол (расов. венг. "Erdős Pál" род. 26 марта 1913 — умер 20 сентября 1996) — знаменитый венгерский математик еврейского происхождения. Всю жизнь провёл в скитаниях по миру от одной конференции к другой. Жил у своих коллег, что и является причиной столь большого числа совместных научных работ. Умер во время конференции в Варшаве. В кармане пиджака был обнаружен билет в Вильнюс, где он хотел принять участие в следующей конференции… Goodnight, sweet prince.
После смерти матери в 1971 году у него началась депрессия, от которой врач прописывал стимуляторы. Он принимал бензедрин (aka амфетамин) и риталин до конца жизни (которая составила целых 83+ε лет, что примерно втрое превышает среднюю продолжительность жизни наркоманов), а ещё в колледже пил тонны кофе. Он мыл руки 50 раз в день, ненавидел прикосновения, а любимой заморочкой была математика. Как-то он поспорил на 500$, что сможет продержаться без амфетамина месяц. Продержался, но за этот месяц никаких математических идей в голову не приходило, и он продолжил.
 
Эрдёш был членом научной группы «The Martians», состоявшей из физиков и математиков венгерского происхождения. Надо сказать, что он оказался в хорошей компании: кроме него там состояли такие знаменитые ученые, как Э. Теллер, Л. Силард и Дж. фон Нейман. В то время в США эмигрантов из Венгрии действительно воспринимали как существ с другой планеты: в первую очередь из-за того, что венгры слишком сильно отличаются по культуре и менталитету от всех остальных европейцев. Кроме того, многие из них (см. далеко не полный список выше) были очень сильными физиками и математиками, и в американском научном сообществе их считали чуть ли не сверхчеловеками. Добавить к этому еще и жуткий акцент, с которым они говорили по-английски — и стереотип венгерского учёного-«пришельца с Марса» был готов.
Само название «The Martians» придумал фон Нейман, который вдобавок к этому сочинил ещё и целую легенду про марсиан, высадившихся в конце XIX века где-то в районе Будапешта. По этой легенде, марсиане посчитали Землю непригодной для проживания и улетели обратно, но перед этим им успели попасться на глаза несколько венгерок… Так и появились на свет фон Нейман и компания.