กราฟ Kneser
กราฟ Kneser K (5, 2)สมมาตร กับกราฟPetersen
ตั้งชื่อตาม	มาร์ติน คเนเซอร์
จุดยอด	${\displaystyle {\binom {n}{k}}}$
ขอบ	${\displaystyle {\frac {1}{2}}{\binom {n}{k}}{\binom {nk}{k}}}$
หมายเลขสี	${\displaystyle {\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}}$
คุณสมบัติ	${\displaystyle {\tbinom {nk}{k}}}$-ส่วนโค้ง ปกติ-ทรานซิทีฟ
สัญกรณ์	K ( n , k ), KG n , k .
ตารางกราฟและพารามิเตอร์

ในทฤษฎีกราฟกราฟKneser K ( n , k ) (หรือเขียนอีกแบบว่าKGn _{, k} ) คือกราฟที่จุดยอดแต่ละจุดสอดคล้องกับเซต ย่อยที่มี kสมาชิกของเซตที่มีnสมาชิก และจุดยอดสอง _จุดจะอยู่ติดกันก็ต่อเมื่อเซตย่อยทั้งสองที่สอดคล้องกันนั้นไม่มีสมาชิกทับซ้อนกันกราฟ Kneser ตั้งชื่อตามMartin Kneserผู้ซึ่งศึกษากราฟชนิดนี้เป็นครั้งแรกในปี 1956

กราฟ Kneser K ( n , 1)คือกราฟสมบูรณ์บนจุดยอด n จุด

กราฟ Kneser K ( n , 2)คือ กราฟ ส่วนเติมเต็มของกราฟเส้นของกราฟสมบูรณ์บนจุดยอด n จุด

กราฟ Kneser K (2 n − 1, n − 1)คือกราฟคี่O _nโดยเฉพาะอย่างยิ่งO ₃ = K (5, 2)คือกราฟ Petersen (ดูรูปด้านบนขวา)

กราฟ Kneser O ₄ = K (7, 3)แสดงอยู่ทางด้านขวา

กราฟ Kneser มีจุดยอดจำนวน จุด แต่ละจุดยอดมีจุดข้างเคียง จำนวน จุด${\displaystyle K(n,k)}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {nk}{k}}}$

กราฟ Kneser เป็นกราฟที่ถ่ายทอดจุดยอดและถ่ายทอดส่วนโค้งได้เมื่อกราฟ Kneser เป็นกราฟปกติอย่างเข้มแข็ง (strongly regular graph ) โดยมีพารามิเตอร์อย่างไรก็ตาม กราฟนี้จะไม่ใช่กราฟปกติอย่างเข้มแข็งเมื่อเนื่องจากจุดยอดที่ไม่ติดกันแต่ละคู่จะมีจำนวนเพื่อนบ้านร่วมกันที่แตกต่างกัน ขึ้นอยู่กับขนาดของส่วนร่วมของเซตคู่ที่สอดคล้องกัน ${\displaystyle k=2}$${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})}$${\displaystyle k>2}$

เนื่องจากกราฟ Kneser เป็นกราฟปกติและ กราฟ ที่ขอบสามารถส่งผ่านได้การเชื่อมต่อจุดยอดจึงเท่ากับดีกรียกเว้นกราฟที่ไม่มีการเชื่อมต่อ กล่าว คือ การเชื่อมต่อของกราฟจะเท่ากับจำนวนเพื่อนบ้านต่อจุดยอด^{[ 1 ]}${\displaystyle K(2k,k)}$${\displaystyle K(n,k)}$${\displaystyle {\tbinom {nk}{k}},}$

ตามที่ Kneser ( 1956 ) ตั้งข้อสันนิษฐานไว้จำนวนสีของกราฟ Kneser คือn − 2k + 2 พอดี ตัวอย่างเช่น กราฟ Petersen ต้องการสามสีในการระบายสีที่เหมาะสม ใดๆ ข้อสันนิษฐานนี้ได้รับการพิสูจน์แล้วในหลายวิธี ${\displaystyle K(n,k)}$${\displaystyle n\geq 2k}$

• László Lovászพิสูจน์สิ่งนี้ในปี 1978 โดยใช้วิธีการทางโทโพโลยี^{[ 2 ]}ทำให้เกิดสาขาการจัดเรียงเชิงโทโพโลยีขึ้น
• หลังจากนั้นไม่นานImre Bárányก็ได้พิสูจน์อย่างง่ายโดยใช้ทฤษฎีบท Borsuk–Ulamและบทพิสูจน์ย่อยของDavid Gale ^{[ 3 ]}
• Joshua E. Greene ได้รับรางวัล Morgan Prize ประจำปี 2002 สำหรับงานวิจัยระดับปริญญาตรีที่โดดเด่นจากบทพิสูจน์ทางทอพอโลยีที่เรียบง่ายขึ้นแต่ยังคงเรียบง่ายอยู่^{[ 4 ]}
• ในปี 2004 Jiří Matoušekพบข้อพิสูจน์เชิงผสมผสาน เพียงอย่าง เดียว^{[ 5 ]}

ในทางตรงกันข้ามจำนวนสีเศษส่วนของกราฟเหล่านี้คือ[ ^{6 ] เมื่อ} ไม่มีขอบและจำนวนสีคือ 1 เมื่อกราฟจะเป็นการจับคู่ที่สมบูรณ์แบบและจำนวนสีคือ 2${\displaystyle n/k}$${\displaystyle n<2k}$${\displaystyle K(n,k)}$${\displaystyle n=2k}$

เป็นที่ทราบกันดีว่ากราฟ Petersenไม่ใช่กราฟ Hamiltonianแต่มีการคาดการณ์กันมานานแล้วว่านี่เป็นข้อยกเว้นเพียงอย่างเดียว และกราฟ Kneser ที่เชื่อมต่อกันอื่นๆ ทุกกราฟK ( n , k )เป็นกราฟ Hamiltonian

ในปี พ.ศ. 2546 Ya-Chen Chen แสดงให้เห็นว่ากราฟ Kneser K ( n , k )มีวงจรแฮมิลโทเนียนหาก^{[ 7 ]}

${\displaystyle n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).}$

เนื่องจาก

${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1}$

ใช้ได้กับทุกกรณีเงื่อนไขนี้จะเป็นจริงก็ต่อเมื่อ ${\displaystyle k}$

${\displaystyle n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.}$

ในเวลาเดียวกัน Shields ได้แสดงให้เห็น (โดยการคำนวณ) ว่า ยกเว้นกราฟ Petersen กราฟ Kneser ที่เชื่อมต่อทั้งหมดK ( n , k )โดยที่n ≤ 27เป็นกราฟ Hamiltonian ^{[ 8 ]}

ในปี 2021 Mütze, Nummenpalo และ Walczak พิสูจน์ว่ากราฟ Kneser K ( n , k )มีวงจรแฮมิลโทเนียน ถ้ามีจำนวนเต็มที่ ไม่เป็นลบ อยู่จริงที่^{[ 9 ]}โดยเฉพาะอย่างยิ่งกราฟคี่O _nมีวงจรแฮมิลโทเนียน ถ้าn ≥ 4ในที่สุด ในปี 2023 Merino, Mütze และ Namrata ได้ทำการพิสูจน์ข้อสันนิษฐานนี้เสร็จสมบูรณ์^{[ 10 ]}${\displaystyle a}$${\displaystyle n=2k+2^{a}}$

เมื่อn < 3k กราฟ Kneser K ( n , k )จะไม่มีสามเหลี่ยม โดยทั่วไปแล้ว เมื่อn < ckจะไม่มีคลิกขนาดcในขณะที่จะมีคลิกดังกล่าวเมื่อn ≥ ckยิ่งไปกว่านั้น แม้ว่ากราฟ Kneser จะมีวงจรที่มีความยาวสี่เสมอเมื่อn ≥ 2k + 2แต่สำหรับค่าnที่ใกล้เคียงกับ2k วงจร คี่ที่สั้นที่สุดอาจมีความยาวแปรผันได้^{[ 11 ]}

เส้นผ่านศูนย์กลางของกราฟ Kneser ที่เชื่อมต่อK ( n , k )คือ^{[ 12 ]}$${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$$

สเปกตรัม ของ กราฟ Kneser K ( n , k )ประกอบด้วยค่าลักษณะเฉพาะ ที่แตกต่างกัน k + 1 ค่า : ยิ่งไปกว่านั้นเกิดขึ้นด้วยความซ้ำซ้อนสำหรับและมีความซ้ำซ้อน 1 ^{[ 13 ] [ 14 ]}$${\displaystyle \lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots ,k.}$$${\displaystyle \lambda _{j}}$${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$${\displaystyle j>0}$${\displaystyle \lambda _{0}}$

ทฤษฎีบท Erdős –Ko–Radoระบุว่าจำนวนความเป็นอิสระของกราฟ Kneser K ( n , k )สำหรับคือ แต่ถ้าแล้วเซตย่อยของจุดยอดทุกจุด ที่มีขนาดเกินกว่าจำนวนความเป็นอิสระจะมีจุดยอดที่อยู่ติดกับ จุดยอดอื่นอย่างน้อย ใน^{[ 15 ]}${\displaystyle n\geq 2k}$$${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}},}$$${\displaystyle n>10000k}$${\displaystyle S}$$${\displaystyle \left({\frac {1}{2}}-O\left({\sqrt {\frac {k}{n}}}\right)\right){\binom {nk-1}{k-1}}}$$${\displaystyle S}$

กราฟจอห์นสันJ ( n , k )คือกราฟที่มีจุดยอดเป็น เซตย่อย kสมาชิกของ เซต nสมาชิก โดยจุดยอดสองจุดจะอยู่ติดกันเมื่อมาบรรจบกันใน เซตที่มีสมาชิก ( k  − 1)สมาชิก กราฟจอห์นสันJ ( n , 2)คือกราฟส่วนเติมเต็มของกราฟเนเซอร์K ( n , 2)กราฟจอห์นสันมีความสัมพันธ์อย่างใกล้ชิดกับโครงร่างจอห์นสันซึ่งทั้งสองอย่างตั้งชื่อตามเซลเมอร์ เอ็ม. จอห์นสัน

กราฟKneser ทั่วไปK ( n , k , s )มีเซตจุดยอดเดียวกันกับกราฟ Kneser K ( n , k )แต่เชื่อมต่อจุดยอดสองจุดเมื่อใดก็ตามที่จุดยอดเหล่านั้นสอดคล้องกับเซตที่ตัดกันในs รายการหรือน้อยกว่า^{[ 11 ]}ดังนั้นK ( n , k , 0) = K ( n , k )

กราฟKneser แบบสองส่วนH ( n , k )มีจุดยอดเป็นเซตของkและn − kรายการที่ดึงมาจากคอลเลกชันของ องค์ประกอบ nจุดยอดสองจุดจะเชื่อมต่อกันด้วยขอบเมื่อใดก็ตามที่เซตหนึ่งเป็นเซตย่อยของอีกเซตหนึ่ง เช่นเดียวกับกราฟ Kneser มันเป็นกราฟที่ถ่ายทอดจุดยอดได้โดยมีดีกรีกราฟ Kneser แบบสองส่วนสามารถสร้างขึ้นได้จากการปกคลุมสองชั้นแบบสองส่วนของK ( n , k )โดยที่หนึ่งสร้างสำเนาสองชุดของแต่ละจุดยอดและแทนที่ขอบแต่ละขอบด้วยคู่ของขอบที่เชื่อมต่อคู่ของจุดยอดที่สอดคล้องกัน^{[ 16 ]}กราฟ Kneser แบบสองส่วนH (5, 2)คือกราฟ Desarguesและกราฟ Kneser แบบสองส่วนH ( n , 1)คือกราฟ มงกุฎ${\displaystyle {\tbinom {nk}{k}}.}$

• ไวส์สไตน์, เอริก ดับเบิลยู. "Kneser Graph" . แมทเวิลด์ .
• ไวส์สไตน์, เอริค ดับเบิลยู. "กราฟคี่" . แมธเวิลด์ .