Функция SSCG Фридмана - Friedman's SSCG function
В математике , А простой subcubic граф ( SSCG ) является конечной простой граф , в котором каждая вершина имеет степень не более трех. Предположу , что мы имеем последовательность простой subcubic граф G 1 , G 2 , ..., что каждый граф G я имею самое я + K вершины (для некоторых целого числа к ) и для не я < J является G я гомеоморфно вкладывается в ( т.е. является второстепенным графом ) Gj .
Теорема Робертсона – Сеймура доказывает, что субкубические графы (простые или нет) основаны на гомеоморфной вложимости, из чего следует, что такая последовательность не может быть бесконечной. Итак, для каждого значения k существует последовательность максимальной длины. Функция SSCG ( k ) обозначает эту длину для простых субкубических графов. Функция SCG ( k ) обозначает эту длину для (общих) субкубических графов.
Последовательность SCG начинается с SCG (0) = 6, но затем увеличивается до значения, эквивалентного f ε 2 * 2 в быстрорастущей иерархии .
Последовательность SSCG начинается с SSCG (0) = 2, SSCG (1) = 5, но затем быстро растет. SSCG (2) = 3 × 2 (3 × 2 95 ) - 8 ≈ 3,241704 ⋅ 10 35775080127201286522908640066 и его десятичное разложение заканчивается на ... 11352349133049430008.
SSCG (3) намного больше, чем ДЕРЕВО (3) и ДЕРЕВО (3) (3). Адам П. Гушер утверждает, что нет качественной разницы между асимптотическими темпами роста SSCG и SCG. Он пишет: «Ясно, что SCG ( n ) ≥ SSCG ( n ), но я также могу доказать, что SSCG (4 n + 3) ≥ SCG ( n )».