SCG(13)

В математике "простой подкубический граф" ("SSCG") - это конечный простой граф, в котором каждая вершина имеет Степень вершины самое большее из трех. Предположим, у нас есть последовательность простых подкубических графов "G"₁, "G"₂, ... таких, что каждый граф "G"_"i" содержит не более "i" + "k" вершины (для некоторого целого числа "k") и без "i" < "j" - это "G"_"i" гомеоморфно встраиваемый в (т.е. является младшим графом из) "G"_"j".

Теорема Робертсона–Сеймура доказывает, что подкубические графы (простые или нет) хорошо обоснованы гомеоморфной встраиваемостью, подразумевая, что такая последовательность не может быть бесконечной. Затем, применяя лемму Кенига к дереву таких расширяемых последовательностей, для каждого значения "k" существует последовательность максимальной длины. Функция SSCG("k") обозначает эту длину для простых подкубических графов. Функция SCG("k")<ссылка>[FOM] 279:Номера подкубических графиков/пересчитано</ref> обозначает эту длину для (общих) подкубических графов.

Последовательность "SCG" начинается с SCG(0) = 6, но затем увеличивается до значения, эквивалентного f_ε2*2 в быстрорастущей иерархии.

Последовательность "SSCG" начинается медленнее, чем SCG, SSCG(0) = 2, SSCG(1) = 5, но затем быстро увеличивается. SSCG(2) = 3 × 2^{(3 × 295)} − 8 ≈ 3,241704 × 10^{35775080127201286522908640065}. Его первая и последние 20 цифр - 32417042291246009846...34057047399148290040. SSCG(3) намного больше, чем TREE(3) и TREE^TREE(3)(3), то есть функция TREE вложила ДЕРЕВО(3) в число раз больше, чем 3 в нижней части.

Адам П. Гаучер утверждает, что между асимптотическими темпами роста SSCG и SCG нет качественной разницы. Он пишет: "Ясно, что SCG("n") ≥ SSCG("n"), но я также могу доказать, что SSCG(4"n" + 3) ≥ SCG("n")".<ссылка>ДРЕВОВИДНЫЕ(3) и беспристрастные игры | Сложный проект 4-Пробел</ref>

Функция была предложена и изучена Харви Фридманом.

Смотрите также

• Теорема Гудстайна
• Теорема Пэриса–Харрингтона
• Теорема Канамори–Макалуна