Харвей Фридман http://en.wikipedia.org/wiki/Harvey_Friedman
Джозеф Крускал http://en.wikipedia.org/wiki/Joseph_Kruskal
Сама задача http://en.wikipedia.org/wiki/Kruskal's_tree_theorem
Теперь своими словами. Джозеф Крускал рассмотрел такую задачу. Для понимания которой нужно возобновить в мозге понятие математического графа, и конкретно древовидного графа. Это вы сделаете сами. Тут я не буду пересказывать то что великолепно описано в Википедии, потому что без картинок это выйдет плохо.
Так вот берём бесконечную последовательность конечных деревьев. Крускал доказал что в такой последовательности обязательно существует поддерево i меньшее чем j которое вкладывается в это j как его часть. То есть всегда есть участок какого-то графа который является частью большего графа, его копией. С точки зрения «житейской логики» тут вроде всё понятно. НА бесконечности всегда найдётся что то являющееся копией чего-то. Но Крускал смог это строго доказать.
Для этого использовалась так называемая логика второго порядка, позволяющая оперировать бесконечными множествами, но это за рамками данной статьи. Вот доберусь об этом детям рассказывать, тогда популярно напишу. Скажу только для возбуждения любопытства, что множества бывают конечные и бесконечные, а бесконечные бывают счётные и несчётные. Это официальная терминология.
Харви Фридман несколько «сузил» эту задачу. Он рассмотрел такие деревья что дерево t с коэффициентом i имеет не более чем i+k вершин. Я по моему правильно понял. И задался вопросом, каково должно быть количество деревьев чтобы при таком способе их задачи всегда нашлось поддерево вкладывающееся в другое дерево. То есть вы мне называете k, а я вычисляю некое N являющимся тем количеством деревьев при котором вышеописанное условие вложения выполняется.
В смысле не я вычисляю, а Харви Фридман вычисляет. Так вот зависимость N от k очень велика. Допустим если k=1 то N=3, k=2 N=11, k=3 то N уже становится большим числом уже многократно превосходящим число Грэма, рассмотренное в предыдущей статье, если число Грэма записать как G64(3) то это FinKraskal(3) имеет порядок G(G(187196)). Хотя я встречал разные варианты записи его "огромности", в общем в невообразимое число раз больше невообразимого числа Грэма.