В математике простой субкубический граф ( SSCG ) — это конечный простой граф , в котором каждая вершина имеет степень не более трёх. Предположим , у нас есть последовательность простых субкубических графов G 1 , G 2 , ... такая, что каждый граф G i имеет не более i + k вершин (для некоторого целого k ) и ни при каком i < j G i гомеоморфно вложим в ( т.е. является минором графа ) G j .
Теорема Робертсона-Сеймура доказывает, что субкубические графы (простые или нет) хорошо обоснованы гомеоморфной вложимостью, а это означает, что такая последовательность не может быть бесконечной. Затем, применив лемму Кенига к дереву таких последовательностей при расширении, для каждого значения k существует последовательность максимальной длины. Функция SSCG( k ) [1] обозначает эту длину для простых субкубических графов. Функция SCG( k ) [2] обозначает эту длину для (общих) субкубических графов.
Последовательность SCG начинается с SCG(0) = 6, но затем расширяется до значения, эквивалентного f ε 2 * 2 в быстрорастущей иерархии . [ нужны разъяснения ]
Последовательность SSCG начинается медленнее, чем SCG, SSCG(0) = 2, SSCG(1) = 5, но затем быстро растет. SSCG(2) = 3 × 2 (3 × 2 95 ) − 8 ≈ 3,241704 × 10 35775080127201286522908640065 . Его первые и последние 20 цифр: 32417042291246009846...34057047399148290040. SSCG(3) намного больше, чем TREE(3) и TREE TREE(3) (3), то есть функция TREE вложена TREE(3) раз с 3 внизу.
Адам П. Гоучер утверждает, что нет качественной разницы между асимптотическими темпами роста SSCG и SCG. Он пишет: «Ясно, что SCG( n ) ≥ SSCG( n ), но я также могу доказать, что SSCG(4 n + 3) ≥ SCG( n )». [3]
Функция была предложена и изучена Харви Фридманом .