ฟังก์ชัน SSCG ของฟรีดแมน

ฟังก์ชัน SSCG ของฟรีดแมนเป็นฟังก์ชันทางคณิตศาสตร์ที่กำหนดโดยฮาร์วีย์ ฟรีดแมนโดยนิยามว่าคือจำนวนเต็มที่มากที่สุดที่สอดคล้องกับเงื่อนไขต่อไปนี้: ${\displaystyle {\text{SSCG}}(k)}$${\displaystyle n}$

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

ต่อมา ฟรีดแมนได้กำหนด นิยาม ของกราฟย่อยลูกบาศก์ทั่วไปมากขึ้น${\displaystyle {\text{SCG}}(k)}$

ในทางคณิตศาสตร์โดยเฉพาะทฤษฎีกราฟกราฟซับคิวบิกแบบง่าย ( 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

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

มีลำดับของกราฟย่อยลูกบาศก์อย่างง่ายซึ่งแต่ละกราฟมีจุดยอดไม่เกินและสำหรับไม่มีกราฟ ใดที่สามารถฝัง ตัวแบบโฮโมมอร์ฟิกเข้าไปในกราฟ ได้${\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 ]}

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

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

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

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

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

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

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