ขอบเขตล่างที่สร้างสรรค์ของตัวเลขแรมซีย์
ทฤษฎีบทของแรมซีย์ระบุว่า
ให้ $s, t\in \mathbb{N}$มี $n\in \mathbb{N}$ เช่นนั้นสำหรับทุกกราฟที่มี $n$ จุดยอดประกอบด้วยไฟล์ $s$-clique หรือส่วนเสริมประกอบด้วยไฟล์ $t$- เมฆ
ที่เล็กที่สุด $n$ ความพึงพอใจในคำสั่งนั้นแสดงโดย $R(s, t)$.
ฉันพบในบทความ"The Probabilistic Method in Combinatorics, Lectures โดย Niranjan Balachandran"ข้อความต่อไปนี้:
ขอบเขตล่างที่สร้างสรรค์บน R (s, s) ซึ่งค้นพบโดย Nagy มีดังต่อไปนี้: $$R(s, s)\ge \binom{s}{3}$$ (อย่างชัดเจนการก่อสร้างของเขามีดังนี้: ใช้ชุดใดก็ได้ $S$และเปลี่ยนคอลเล็กชันทั้งหมด $3$- องค์ประกอบย่อยของ $S$ ลงในกราฟโดยเชื่อมต่อส่วนย่อยถ้าจุดตัดของมันเป็นเลขคี่)
ฉันไม่สามารถพิสูจน์ได้ว่ากราฟนี้และส่วนเติมเต็มไม่มี $s$- เทคนิค ความช่วยเหลือใด ๆ ในเรื่องนี้จะได้รับการชื่นชมอย่างมาก
คำตอบ
เอาเถอะ $S = \{1, 2, \dots, s\}$. สิ่งที่เราสามารถแสดงได้จริงก็คือกราฟของ Nagy มี
- ขนาดเล็กมากที่สุด $\max\{7, \frac{s-1}{2}\}$และ
- ชุดขนาดอิสระมากที่สุด $s-1$ หรือน้อยกว่าเมื่อ $s \not\equiv 0 \pmod 4$และมากที่สุด $s$ เมื่อไหร่ $s \equiv 0 \pmod 4$.
นี่ไม่ได้แสดงว่า $R(s,s) \ge \binom s3$ เพื่อทุกสิ่ง $s$แต่มันแสดงให้เห็นว่า $R(s,s) > \binom s3$และถึงอย่างนั้น $R(\frac{s}{2}, s) > \binom s3$สำหรับค่ามากมายของ $s$.
ก่อนอื่นให้หากลุ่มที่ใหญ่ที่สุด มีสองกรณี:
- กลุ่มประกอบด้วย $4$ จุดยอดที่ตัดกับองค์ประกอบเดียวกันของ $S$: พูด, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$และ $\{1,8,9\}$. จากนั้นทุกจุดยอดอื่น ๆ จะต้องมี$1$: มิฉะนั้นจะต้องมีองค์ประกอบจากแต่ละไฟล์ $\{2,3\}$, $\{4,5\}$, $\{6,7\}$และ $\{8,9\}$ซึ่งเป็นไปไม่ได้ กลุ่มดังกล่าวสามารถมีได้มากที่สุด$\frac{s-1}{2}$ จุดยอด
- กลุ่มมีมากที่สุด $3$ จุดยอดที่ตัดกับองค์ประกอบเดียวกันของ $S$. พูด$\{1,2,3\}$เป็นหนึ่งในจุดยอด จากนั้นสามารถมีได้มากที่สุด$2$ จุดยอดอื่น ๆ ที่มีแต่ละจุด $1$, $2$, หรือ $3$ดังนั้นกลุ่มมีมากที่สุด $7$ จุดยอด
ต่อไปมาหาเซตอิสระที่ใหญ่ที่สุด ที่นี่โปรดทราบว่าหากจุดยอดสองจุดในเซตที่เป็นอิสระร่วมกัน$2$ องค์ประกอบและจุดยอดที่สามในหุ้นชุดอิสระ $2$ องค์ประกอบที่มีหนึ่งในนั้นจะต้องแบ่งปันอย่างน้อยหนึ่งองค์ประกอบ (ดังนั้น $2$องค์ประกอบ) กับอื่น ๆ ดังนั้นเซตอิสระจะต้องประกอบด้วยคลัสเตอร์โดยที่จุดยอดสองจุดในคลัสเตอร์ใช้ร่วมกัน$2$ องค์ประกอบและจุดยอดสองจุดภายนอกคลัสเตอร์ที่ใช้ร่วมกัน $0$.
อีกครั้งคลัสเตอร์สามารถมีรูปร่างได้สองแบบ:
- สมมติว่าคลัสเตอร์มี $3$ จุดยอดที่เหมือนกันทั้งหมด $2$ องค์ประกอบ: พูดว่า $\{1,2,3\}$, $\{1,2,4\}$,และ $\{1,2,5\}$. จุดยอดอื่นในคลัสเตอร์ที่มีเพียงหนึ่งใน$\{1,2\}$ จะต้องมีไฟล์ $3$, $4$และ $5$ซึ่งเป็นไปไม่ได้ คลัสเตอร์จึงประกอบด้วย$k$ จุดยอดของแบบฟอร์ม $\{1,2,x\}$ซึ่ง "ใช้จนหมด" $k+2$ องค์ประกอบของ $S$.
- สมมติว่าคลัสเตอร์มีมากที่สุด $2$ จุดยอดร่วมใด ๆ $2$องค์ประกอบ แล้วถ้า$\{1,2,3\}$ เป็นจุดยอดในคลัสเตอร์จุดยอดซึ่งกันและกันในคลัสเตอร์ต้องมีสองจุด $\{1,2,3\}$แต่อาจมีได้ไม่เกินหนึ่งประเภทสำหรับ $4$จุดยอดทั้งหมด สิ่งเหล่านี้ต้องใช้อย่างน้อยที่สุด$4$ องค์ประกอบของ $S$เช่นกับ $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
เราจะเห็นว่าคลัสเตอร์ใช้หมดแล้ว $k$ องค์ประกอบของ $S$ สามารถมีได้มากที่สุด $k$ จุดยอดดังนั้นคลัสเตอร์ทั้งหมดสามารถมีได้มากที่สุด $S$จุดยอด แต่จะเกิดขึ้นได้ก็ต่อเมื่อคลัสเตอร์ทั้งหมดเป็นประเภทที่สองและครอบคลุมองค์ประกอบทั้งหมดของ$S$ซึ่งต้องใช้ $s \equiv 0 \pmod 4$.