Кажется, нашел разгадку
Видимо, сон про странную функцию был навеян рассуждениями про число Эрдёша, которое обсуждалось в предыдущем посте. Интуитивно кажется, что оно может быть не монотонно убывающим - по крайней мере, можно сконструировать сеть таким образом. Например, создать искусственные цепочки из двух-трех человек и вставить их в значительное количество цепочек.