ในทางคณิตศาสตร์โดยเฉพาะทฤษฎีกราฟกราฟซับคิวบิกแบบง่าย ( SSCG ) คือกราฟ แบบง่ายที่มีจำนวนสมาชิกจำกัด ซึ่งแต่ละจุดยอดมีดีกรีไม่เกินสาม สมมติว่าเรามีลำดับของกราฟซับคิวบิกแบบง่าย${\displaystyle G_{1}}$,${\displaystyle G_{2}}$...โดยที่กราฟแต่ละกราฟ${\displaystyle G_{i}}$มีมากที่สุด${\displaystyle i+k}$จุดยอด (สำหรับจำนวนเต็มบางค่า)${\displaystyle k}$) และสำหรับไม่มี${\displaystyle i<j}$เป็น${\displaystyle G_{i}}$สามารถฝังตัวแบบโฮโมมอร์ฟิกเข้าไปใน (กล่าวคือ เป็นกราฟไมเนอร์ของ) ได้${\displaystyle G_{j}}$.

ทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์พิสูจน์ว่ากราฟย่อยลูกบาศก์ (ไม่ว่าจะเป็นกราฟแบบง่ายหรือไม่) มีรากฐานที่ดีโดยความสามารถในการฝังแบบโฮมีโอเมอร์ฟิก ซึ่งหมายความว่าลำดับดังกล่าวไม่สามารถเป็นอนันต์ได้ จากนั้น โดยการใช้เลมมาของคอนิกกับต้นไม้ของลำดับดังกล่าวภายใต้การขยาย สำหรับแต่ละค่าของ${\displaystyle k}$มีลำดับที่มีความยาวสูงสุด ฟังก์ชัน${\displaystyle {\text{SSCG}}(k)}$แสดงถึงความยาวสำหรับกราฟย่อยลูกบาศก์แบบง่าย ฟังก์ชัน${\displaystyle {\text{SCG}}(k)}$หมายถึงความยาวสำหรับกราฟย่อยลูกบาศก์ (ทั่วไป)

ฮาร์วีย์ ฟรีดแมนได้นิยามฟังก์ชันไว้สองฟังก์ชัน คือ SSCG และ SCG

ฟรีดแมนได้นิยามไว้ว่า${\displaystyle {\text{SSCG}}(k)}$เนื่องจากเป็นจำนวนเต็มที่มากที่สุด${\displaystyle n}$ตรงตามเงื่อนไขต่อไปนี้: ^{[ 1 ]}

มีลำดับอยู่${\displaystyle G_{1},\ldots ,G_{n}}$ของกราฟย่อยลูกบาศก์แบบง่าย โดยที่แต่ละกราฟ${\displaystyle G_{i}}$มีมากที่สุด${\displaystyle i+k}$จุดยอดและสำหรับไม่มี${\displaystyle i<j}$เป็น${\displaystyle G_{i}}$สามารถฝัง ตัวแบบโฮโมมอร์ฟิกเข้าไปใน${\displaystyle G_{j}}$.

พจน์แรกๆ ของลำดับคือ

${\displaystyle \ชื่อผู้ดำเนินการ {SSCG} (0)=2,}$

${\displaystyle \ชื่อผู้ดำเนินการ {SSCG} (1)=5,}$ และ

${\displaystyle \operatorname {SSCG} (2)=3\cdot 2^{3\cdot 2^{95}}\!\!-8=3\cdot 2^{118\,842\,243\,771\,396\,506\,390\,315\,925\,504}\!-8}$

${\displaystyle \qquad \qquad \;\approx \,3.241\,704\,229\cdot 10^{35\,775\,080\,127\,201\,286\,522\,908\,640\,065}}$

${\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}$^{[ 2 ]}

ได้มีการแสดงให้เห็นแล้วว่าเทอมถัดไป${\displaystyle {\text{SSCG}}(3)}$มีค่ามากกว่าTREE(3) [ ^{3 ] ฟรี}ดแมนแสดงให้เห็นว่า${\displaystyle {\text{SSCG}}(13)}$มีค่ามากกว่าเวลาหยุดของเครื่องจักรทัวริง ใดๆ ที่สามารถพิสูจน์ได้ว่าหยุดในΠ ¹ -CA โดยมีค่าไม่เกิน${\displaystyle 2\uparrow \uparrow 2000}$^[ก]สัญลักษณ์ และไม่สามารถพิสูจน์ได้ว่ามีอยู่จริงในทฤษฎีนั้นด้วยจำนวนน้อยกว่า${\displaystyle 2\uparrow \uparrow 1000}$สัญลักษณ์ ที่${\displaystyle \uparrow \uparrow }$หมายถึงการวนซ้ำเขาทำเช่นนี้โดยใช้แนวคิดที่คล้ายคลึงกับข้อความที่คล้ายกันที่เขาพิสูจน์เกี่ยวกับ${\displaystyle {\text{ต้นไม้}}(3)}$[ ^{1 ]​}

ต่อมา ฟรีดแมนตระหนักว่าไม่มีเหตุผลที่ดีที่จะกำหนดเงื่อนไข "เรียบง่าย" ให้กับกราฟย่อยลูกบาศก์ เขาจึงผ่อนปรนเงื่อนไขและกำหนดนิยามใหม่${\displaystyle {\text{SCG}}(k)}$ในฐานะที่เป็นที่ใหญ่ที่สุด${\displaystyle n}$น่าพอใจ: ^{[ 4 ]}

มีลำดับอยู่${\displaystyle G_{1},\ldots ,G_{n}}$ของกราฟย่อยลูกบาศก์ โดยที่แต่ละ${\displaystyle G_{i}}$มีมากที่สุด${\displaystyle i+k}$จุดยอดและสำหรับไม่มี${\displaystyle i<j}$เป็น${\displaystyle G_{i}}$สามารถฝังตัวแบบโฮโมมอร์ฟิกเข้าไปใน${\displaystyle G_{j}}$.

พจน์แรกของลำดับคือ${\displaystyle {\text{SCG}}(0)=6}$ในขณะที่เทอมถัดไป${\displaystyle {\text{SCG}}(1)}$มีขนาดใหญ่กว่าหมายเลขของเกรแฮมนอกจากนี้${\displaystyle {\text{SCG}}(3)}$ใหญ่กว่า${\displaystyle {\text{ต้นไม้}}^{{\text{ต้นไม้}}(3)}(3)}$[ ^{3 ]​}

อดัม พี. กูเชอร์ อ้างว่าไม่มีความแตกต่างเชิงคุณภาพระหว่างอัตราการเติบโตเชิงเส้นกำกับของ SSCG และ SCG เขาเขียนว่า "เป็นที่ชัดเจนว่า${\displaystyle {\text{SCG}}(n)\geq {\text{SSCG}}(n)}$แต่ฉันก็สามารถพิสูจน์ได้เช่นกัน${\displaystyle {\text{SSCG}}(4n+3)\geq {\text{SCG}}(n)}$“. ^{[ 5 ]}

• ทฤษฎีบทของกูดสไตน์
• ทฤษฎีบทปารีส-แฮร์ริงตัน
• ทฤษฎีบทคานาโมริ-แมคอาลูน
• ทฤษฎีบทต้นไม้ของ Kruskalซึ่งนำไปสู่ฟังก์ชัน TREE ที่คล้ายคลึงกัน
• เกมไฮดรา

^{^} Friedman เขียนสิ่งนี้จริง ๆ ว่า 2^[2000]ซึ่งหมายถึงการเรียงซ้อนเลขยกกำลังของ 2 ที่มีความสูง 2000 โดยใช้สัญลักษณ์ของเขา ^{[ 6 ]}