Число подкубического графа

Число подкубического графа
Темпы роста	>* '"`UNIQ--postMath-00000001-QINU`"'-'"`UNIQ--postMath-00000002-QINU`"'
Автор(ы)	Харли Фридман
Нотация	'"`UNIQ--postMath-00000003-QINU`"'
Год	2006

Число подкубического графа — это выходные данные быстрорастущей комбинаторной функции. Они были разработаны Харви Фридманом, который показал, что оно в конечном итоге доминирует над каждой рекурсивной функцией, доказуемо полной в теории $\Pi^1_1$-$\text {CA} _0$, и само по себе является доказуемо полным в теории $\Pi_1 ^ 1-\textrm {CA} +\textrm{BI}$(требуется цитирование).

Один из выходных данных последовательности, SCG(13), является предметом обширного исследования. Известно, что оно превосходит TREE(3), число, возникающее из связанной последовательности.

Определение

Подкубический граф - это конечный граф, в котором каждая вершина имеет валентность не более трёх, т.е. ни одна вершина не связана более чем с тремя рёбрами. (Для целей этой статьи подкубическим графам разрешено быть мультиграфами, и они не обязаны быть подключенными.) Мы также определяем отношение минорный граф следующим образом: A называется младшим графом B, если мы можем вывести A из следующего процесса: начните с B, удалите вершины и рёбра и сократите рёбра. Пример вывода минорного графа показан в информационном блоке этой статьи.

Учитывая целое число k, предположим, что у нас есть последовательность подкубических графов G₁, G₂, ... таких, что каждый граф G _i имеет не более i + k вершин и ни для кого i < j не является G_i гомеоморфно встраиваемым в G _j (т.е. является минором графома).

Теорема Робертсона—Сеймура доказывает, что подкубические графы являются хорошо квазиупорядоченными по гомеоморфной вложимости, подразумевая, что такая последовательность не может быть бесконечной. Итак, для каждого значения k существует последовательность с максимальной длиной. Мы обозначим эту максимальную длину с помощью SCG(k).

Конкретные значения

Можно показать, что SCG(0) = 6. Первый график представляет собой одну вершину с петлей,

Графики SCG(0)

второй - это две вершины, соединённые одним ребром, а следующие четыре графика состоят из 3, 2, 1 и 0 несвязанных вершин. Все максимальные последовательности будут достигать максимума и снижаться таким образом.

Следующие ограничения были заявлены пользователем англоязычной гугология вики Hyp cos.

• $SCG(1) > f_{\varepsilon_{22}}(f_{\varepsilon_{0}2}(f_{\varepsilon_{0}+1}(f_{\varepsilon_{0}}(f_{\omega^{\omega}+1}(f_{\omega^{5} + \omega^{2} + \omega}(f_{\omega^{2} 3 + 1}(f_{\omega^{2} 2 + 1}(f_{\omega^{2} + \omega 3 + 1}(f_{\omega^{2} + 1}(f_{\omega^{2}}(3 \times 2^{3 \times 2^{95}})))))))))))$.

• $SCG(2) > f_{\vartheta (\Omega^{\omega})}(f_{\varepsilon_{22}}(f_{\varepsilon_{0}2}(f_{\varepsilon_{0}+1}(f_{\varepsilon_{0}}(f_{\omega^{\omega}+1}(f_{\omega^{5} + \omega^{2} + \omega}(f_{\omega^{2} 3 + 1}(f_{\omega^{2} 2 + 1}(f_{\omega^{2} + \omega 3 + 1}(f_{\omega^{2} + 1}(f_{\omega^{2}}(3 \times 2^{3 \times 2^{95}}))))))))))))$.

Эти оценки используют нестандартный выбор фундаментальной последовательности для ординалов - используя особую, очень сложную биекцию между ординалами и малыми графами, которую мы обозначим здесь через $f$, мы определяем $\alpha[n]=\max\{\beta: \beta<\alpha\text{ и } f(\beta)\text{ - это граф с }\leq n\text{ вершинами}\}$.

Поскольку индексы графика начинаются с единицы, также справедливо сказать, что SCG(-1) = 1, состоящий только из пустого графика.

Фридман заявил, что SCG(13) больше, чем время остановки любой машины Тьюринга, так что можно доказать, что она останавливается не более чем за 2 ↑↑ 2000 символы в $\Pi^1_1$-$\text {CA} _0$. Следовательно, он намного больше, чем TREE(3).

SCG (n) вычислимо, поэтому оно, естественно, превосходит $\Sigma(n)$ для некоторого n.

Интерпретация матрицы

Альтернативный способ описания функции SCG заключается в следующем. Определите матрицу инцидентности как матрицу с элементами в {0, 1, 2}, где каждый столбец суммируется ровно до 2, а каждая строка суммируется максимум до 3. Учитывая неотрицательное целое число k, мы построим последовательность n матриц инцидентности M₁, M₂, ..., M_n так, что каждая матрица M_i содержит не более i + k строк, и никакая матрица не может быть изменена на более ранний путём повторного применения любого из следующих процессов:

• Изменение порядка строк или столбцов.
• Удаление столбцов.
• Удаление строк, затем удаление всех столбцов, сумма которых не равна 2.
• Возьмите две строки A и B так, чтобы A + B содержали 2 в позиции i для некоторого i. Удалите A и B, добавьте A + B к матрице и, наконец, удалите столбец i.

Таким образом, SCG("k") - это максимально возможное значение "n".

Простое число подкубического графа

Если мы требуем, чтобы подкубические графы были простыми (т.е. без петель или множественных рёбер), мы получаем "простые числа подкубических графов", обозначаемые SSCG. Хотя это сообщество считало, что Адам П. Гоучер показал, что SSCG(2) << TREE(3) << SSCG(3) в своей статье, он просто содержит приблизительную оценку без доказательства. Более того, сообщество посчитало, что он показал, что даже TREEⁿ(3) даже для очень большого "n" (например, n=TREE(3)) вообще не конкурирует с SSCG(3). Позже он доказал, что TREE(3) < SSCG(3) в другом сообщении в блоге.

Гоучер утверждал, что он доказал, что $\text{SSCG}(4n+3) \geq \text{SCG}(n)$ в своём комментарии и следовательно, SCG(n) и SSCG(n) имеют сопоставимые темпы роста. Позже он доказал это в более позднем сообщении в блоге.

Подобно тому факту, что существует много неправильных утверждений о "фактических результатах на TREE с доказательствами", в SCG есть много утверждений, которые считаются доказанными, но не имеют фактических доказательств. Смотрите также вопросы по анализу TREE.

Значения и границы

• SSCG(0) = 2
• SSCG(1) = 5
• SSCG(2) $\geq 3 \cdot 2^{3 \cdot 2^{95}}-8 \approx 10^{3.5775 \cdot 10^{28}}$ (возможно, что последовательность подкубических графов, которую показал Адам П. Гоучер, действительно оптимальна, но это остаётся недоказанным.)
• SSCG(3) > $\underbrace{TREE(TREE(TREE \cdots (TREE(3)) \cdots ))}_{TREE(3)}$