ในทางคณิตศาสตร์ปัญหาเพื่อนบ้านที่สองเป็นปัญหาที่ยังแก้ไม่ตกเกี่ยวกับกราฟแบบมีทิศทาง ที่ Paul Seymourตั้งขึ้น ตามสัญชาตญาณแล้ว ปัญหานี้ชี้ให้เห็นว่าในเครือข่ายสังคมที่อธิบายโดยกราฟดังกล่าว บุคคลหนึ่งจะมีเพื่อนของเพื่อนอย่างน้อยเท่ากับจำนวนเพื่อน^{[ 1 ] [ 2 ]}

ปัญหาดังกล่าวเป็นที่รู้จักกันในชื่อสมมติฐานย่านใกล้เคียงลำดับที่สองหรือสมมติฐานระยะทางสองของเซย์มัวร์

กราฟเชิงทิศทาง (Oriented graph ) คือ กราฟระบุทิศทางจำกัดที่ได้มาจากกราฟไม่ระบุทิศทางแบบง่าย (Simple undirected graph)โดยการกำหนดทิศทางให้กับแต่ละขอบ กล่าวอีกนัยหนึ่งคือ เป็นกราฟระบุทิศทางที่ไม่มีวงวนในตัวเอง ไม่มีขอบขนาน และไม่มีวงจรสองขอบ บริเวณใกล้เคียงแรกของจุดยอด(เรียกอีกอย่างว่าบริเวณใกล้เคียงแบบเปิด ) ประกอบด้วยจุดยอดทั้งหมดที่อยู่ห่างจากจุดยอดแรกเป็นระยะทางหนึ่งและบริเวณใกล้เคียงที่สองของจุดยอดแรกประกอบด้วยจุดยอดทั้งหมดที่อยู่ห่างจากจุดยอดแรกเป็นระยะทางสองบริเวณใกล้เคียงทั้งสองนี้เป็นเซตที่ไม่ซ้ำกันโดยที่เซตใดเซตหนึ่งไม่มีตัวมันเอง อยู่ภายใน${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

ในปี 1990 Paul Seymourตั้งข้อสันนิษฐานว่า ในกราฟแบบมีทิศทางทุกกราฟ จะมีจุดยอดอย่างน้อยหนึ่งจุดที่มีบริเวณใกล้เคียงที่สองอย่างน้อยเท่ากับบริเวณใกล้เคียงแรก หรือกล่าวอีกนัยหนึ่งคือ ในรูปสี่เหลี่ยมจัตุรัสของกราฟ ดีกรีของ จะ มีค่าอย่างน้อยสองเท่า ปัญหาดังกล่าวได้รับการตีพิมพ์ครั้งแรกโดยNathaniel Deanและ Brenda J. Latka ในปี 1995 ในบทความที่ศึกษาปัญหาดังกล่าวในกลุ่มกราฟแบบมีทิศทางที่จำกัด คือ ทัวร์นาเมนต์(การวางแนวของกราฟสมบูรณ์) ก่อนหน้านี้ Dean ได้ตั้งข้อสันนิษฐานว่า ทัวร์นาเมนต์ทุกอันเป็นไปตามข้อสันนิษฐานของบริเวณใกล้เคียงที่สอง และกรณีพิเศษนี้จึงกลายเป็นที่รู้จักในชื่อข้อสันนิษฐานของ Dean ^{[ 3 ]}${\displaystyle v}$${\displaystyle v}$

จุดยอดในกราฟทิศทางที่มีบริเวณใกล้เคียงที่สองมีขนาดใหญ่กว่าบริเวณใกล้เคียงแรกอย่างน้อยเรียกว่า จุด ยอดSeymour ^{[ 4 ]}

ในการคาดการณ์เกี่ยวกับย่านใกล้เคียงลำดับที่สอง เงื่อนไขที่ว่ากราฟต้องไม่มีวงจรสองขอบเป็นสิ่งจำเป็น เพราะในกราฟที่มีวงจรดังกล่าว (เช่น กราฟเชิงทิศทางสมบูรณ์) ย่านใกล้เคียงลำดับที่สองทั้งหมดอาจว่างเปล่าหรือมีขนาดเล็ก

ฟิชเชอร์ (1996)พิสูจน์สมมติฐานของดีน ซึ่งเป็นกรณีพิเศษของปัญหาเพื่อนบ้านลำดับที่สองสำหรับทัวร์นาเมนต์^{[ 5 ]}

สำหรับกราฟบางกราฟ จุดยอดที่มีดีกรีขาออกต่ำสุดจะเป็นจุดยอด Seymour ตัวอย่างเช่น หากกราฟแบบมีทิศทางมีจุดปลายทาง ซึ่งเป็นจุดยอดที่มีดีกรีขาออกเป็นศูนย์ จุดปลายทางนั้นจะเป็นจุดยอด Seymour โดยอัตโนมัติ เนื่องจากบริเวณใกล้เคียงแรกและบริเวณใกล้เคียงที่สองมีขนาดเป็นศูนย์ทั้งคู่ ในกราฟที่ไม่มีจุดปลายทาง จุดยอดที่มีดีกรีขาออกเป็นหนึ่งจะเป็นจุดยอด Seymour เสมอ ในการวางแนวของกราฟที่ไม่มีสามเหลี่ยมจุดยอดใดๆ ที่มีดีกรีขาออกต่ำสุดจะเป็นจุดยอด Seymour อีกครั้ง เนื่องจากสำหรับขอบใดๆ จากไปยังจุดยอดอื่นเพื่อนบ้านขาออกทั้งหมดของ จะอยู่ในบริเวณใกล้เคียงที่สองของ^{[ 6 ]}${\displaystyle v}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle v}$

สำหรับกราฟใดๆ ที่มีดีกรีของจุดยอดสูงกว่า จุดยอดที่มีดีกรีต่ำสุดอาจไม่ใช่จุดยอด Seymour แต่การมีอยู่ของจุดยอดที่มีดีกรีต่ำยังคงนำไปสู่การมีอยู่ของจุดยอด Seymour ที่อยู่ใกล้เคียงได้ โดยใช้เหตุผลแบบนี้ ข้อสันนิษฐานเรื่องย่านใกล้เคียงข้อที่สองได้รับการพิสูจน์แล้วว่าเป็นจริงสำหรับกราฟแบบมีทิศทางใดๆ ที่มีจุดยอดอย่างน้อยหนึ่งจุดที่มีดีกรีขาออก ≤ 6 ^{[ 7 ]}ตามนี้ ข้อสันนิษฐานจะเป็นจริงสำหรับกราฟทั้งหมดที่มีจำนวนจุดยอด ≤ 14 เนื่องจากกราฟเหล่านี้ต้องมีจุดยอดอย่างน้อยหนึ่งจุดที่มีดีกรีขาออก ≤ 6 สิ่งนี้สามารถปรับปรุงได้สำหรับกราฟที่มีจำนวนจุดยอด ≤ 15 เนื่องจากกราฟเดียวที่มี 15 จุดยอดและไม่มีจุดยอดใดที่มีดีกรีขาออก ≤ 6 คือกราฟทัวร์นาเมนต์

กราฟสองส่วนแบบมีทิศทางทุกกราฟเป็นไปตามสมมติฐานนี้ เช่นเดียวกับกราฟแบบมีทิศทางทั้งหมดที่มีเซตจุดยอดที่สามารถแบ่งออกเป็นเซตอิสระและกราฟเสื่อมสภาพ 2 เซตได้^{[ 8 ]}

ทัวร์นาเมนต์แบบสุ่มและกราฟทิศทางแบบสุ่มบางกราฟมีจุดยอด Seymour จำนวนมากที่มีความน่าจะเป็นสูง^{[ 4 ]} กราฟแบบมีทิศทางทุกกราฟมีจุดยอดที่มีย่านใกล้เคียงที่สองมีขนาดใหญ่กว่าย่านใกล้เคียงแรก อย่างน้อยเท่า${\displaystyle \gamma }$

${\displaystyle \gamma ={\frac {1}{6}}\left(-1+{\sqrt[{3}]{53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\approx 0.657}$

เป็นรากจริงของพหุนาม^{[ 9 ]}${\displaystyle 2x^{3}+x^{2}-1}$

• ความขัดแย้งของมิตรภาพ

• บทความเรื่อง "Seymour's 2nd Neighborhood Conjecture"ในWayback Machine (เก็บถาวรเมื่อวันที่ 11 มิถุนายน 2023) ในหนังสือ "Open Problems in Graph Theory and Combinatorics" โดยDouglas B. West