Всем привет! В предыдущей статье рассказывал про число TREE(3), которое больше чем число Грэма! Сегодняшней статье Я хочу рассказать про число, которое называется SCG(n).
После того как математики открыли TREE(3), они решили не останавливаться на этом и пойти дальше. Они не пошли открывать число TREE(4), т.к функция более слабая, чем у Subcubic Graphic Numbers. Subcubic Graphic Functions - SCG имеет большой потенциал и будет давать величайший.
История
Ученые Нил Робертсон и Пол Сеймур разработали теорию о том,что любое наследуемое свойство графов имеет конечное число запрещённых подграфов. Их теорема распространяет эти результаты на любые замкнутые по минорам семейства графов. Теорема говорит, что множество тороидальных графов имеет конечное множество, но не даёт при этом ни одного такого множества. Как такое может быть?
Простой субкубический граф - это конечный граф в котором каждая вершина имеет валентность не более 3. Допустим, мы имеем последовательность простых субкубических графов G1,G2,G3... - такая, что каждый граф Gx имеет не более x+k вершин.
Теорема Робертсона-Сеймура доказывает, что подкубические графы не могут быть бесконечными. Значит, для каждого значения k есть последовательность с максимальной длиной. Функция SSCG(k) показывают эту длину для простых графов. Функция SCG(k) обозначает эту длину на общих графов.
Последовательность SSCG начинается с SSCG(0) = 2, SSCG(1) = 5, но потом резко возрастает. SSCG(2) = 23 × 3 × 295 - 8 и примерно равно 103,5775 × 1028. Позже показатель улетает в небеса. SSCG(3) не только больше,чем TREE(3), но и больше числа Грэма. Нет различия между ростом SSCG и SCG. Но ясно,что SCG(n) > SSCG(n).