프리드먼의 SSCG 함수
Friedman's SSCG function수학에서 SSCG(simple subcubic graph)는 각 정점의 차수가 최대 3개인 유한 단순 그래프입니다. 각 그래프 G가i (일부 정수 k에 대하여) 최대 i + k개의 정점을 가지며, no i < j는 (즉, 의) G에j 동형적으로 임베딩 가능한 G임을i 나타내는 단순한 서브큐브 그래프1 G, G2, ...의 수열을 갖는다고 가정하자.
로버트슨-Seymour 정리는 하위 입방 그래프(단순하든 아니든)가 동형 임베딩 가능성에 의해 잘 근거한다는 것을 증명하며, 이러한 시퀀스가 무한할 수 없음을 의미합니다. 따라서 k의 각 값에 대해 최대 길이를 갖는 수열이 있습니다. 함수 SSCG(k)[1]는 단순한 직육면체 하부 그래프의 길이를 나타냅니다. 함수 SCG(k)[2]는 (일반적인) 하위 입방 그래프의 길이를 나타냅니다.
SCG 시퀀스는 SCG(0) = 6으로 시작되지만 빠르게 성장하는 계층에서 f에 해당하는 값으로 폭발합니다.
SSCG 시퀀스는 SCG, SSCG(0) = 2, SSCG(1) = 5보다 느리게 시작되지만, 이후 빠르게 성장합니다. SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 1035775080127201286522908640065. 처음과 마지막 20자리는 32417042291246009846...34057047399148290040. SSCG(3)는 TREE(3) 및 TREETREE(3)(3)보다 훨씬 큽니다. 즉, TREE 함수는 TREE(3)를 하단에 3개로 중첩했습니다.
아담 P. Goucher는 SSCG와 SCG의 점근 성장률 사이에 질적인 차이가 없다고 주장합니다. 그는 "SCG(n)가 SSCG(n)를 ≥하는 것은 분명하지만 SSCG(4n+3) ≥ SCG(n)를 증명할 수도 있다"고 썼습니다.
