ในเรขาคณิตเชิงเส้นตรงเซตแคปคือเซตย่อยของปริภูมิเชิงเส้นตรง( ปริภูมิเชิงเส้นตรงมิติเหนือฟิลด์สามองค์ประกอบ ) โดยที่ไม่มีองค์ประกอบสามตัวใดรวมกันได้เป็นเวกเตอร์ศูนย์ปัญหาเซตแคปคือปัญหาของการหาขนาดของเซตแคปที่ใหญ่ที่สุดที่เป็นไปได้ โดยเป็นฟังก์ชันของ[ ^{1 ] ขนาด}ของเซตแคปแรกๆ ได้แก่ 1, 2, 4, 9, 20, 45, 112, ... (ลำดับA090245ในOEIS ) ${\displaystyle \mathbb {Z} _{3}^{n}}$${\displaystyle n}$${\displaystyle n}$

โดยทั่วไปแล้ว Capsจะถูกนิยามว่าเป็นเซตย่อยของปริภูมิแอฟฟินหรือปริภูมิโปรเจคทีฟ จำกัด ที่ไม่มีสามตัวเรียงกัน^{[ 2 ]}

คำศัพท์ "cap set" ควรแยกออกจากวัตถุทางคณิตศาสตร์อื่นที่ไม่เกี่ยวข้องซึ่งมีชื่อเดียวกัน และโดยเฉพาะอย่างยิ่งจากเซตที่มีคุณสมบัติการดูดซับแบบกะทัดรัดในปริภูมิฟังก์ชัน^{[ 3 ]}เช่นเดียวกับจากเซตย่อยนูนร่วมแบบกะทัดรัดของ เซต แบบนูน^{[ 4 ]}

ตัวอย่างของชุดแคปมาจากเกมไพ่Setซึ่งเป็นเกมไพ่ที่ไพ่แต่ละใบมีคุณสมบัติสี่อย่าง (หมายเลข สัญลักษณ์ การแรเงา และสี) โดยแต่ละคุณสมบัติสามารถมีค่าได้หนึ่งในสามค่า ไพ่ในเกมนี้สามารถตีความได้ว่าแทนจุดในปริภูมิเชิงเส้นสี่มิติโดยที่พิกัดแต่ละจุดจะระบุค่าของคุณสมบัติอย่างใดอย่างหนึ่ง เส้นในปริภูมินี้คือไพ่สามใบที่ในแต่ละคุณสมบัติจะเหมือนกันทั้งหมดหรือแตกต่างกันทั้งหมด การเล่นเกมประกอบด้วยการค้นหาและรวบรวมเส้นจากไพ่ที่หงายหน้าอยู่ และชุดแคปอธิบายถึงอาร์เรย์ของไพ่ที่หงายหน้าอยู่ซึ่งไม่สามารถรวบรวมเส้นได้^{[ 1 ] [ 5 ] [ 6 ]}${\displaystyle \mathbb {Z} _{3}^{4}}$

วิธีหนึ่งในการสร้างชุดหมวกขนาดใหญ่ในเกม Set คือการเลือกค่าสองค่าจากสามค่าสำหรับแต่ละคุณลักษณะ และวางไพ่แต่ละใบที่ใช้เพียงหนึ่งในสองค่านั้นในแต่ละคุณลักษณะหงายขึ้น ผลลัพธ์ที่ได้จะเป็นชุดหมวกที่มีไพ่ 16 ใบ โดยทั่วไปแล้ว กลยุทธ์เดียวกันนี้จะนำไปสู่ชุดหมวกที่มีขนาดอย่างไรก็ตาม ในปี 1970 Giuseppe Pellegrino ได้พิสูจน์ว่าชุดหมวกสี่มิติมีขนาดสูงสุด 20 ^{[ 7 ]}ในแง่ของเกม Set ผลลัพธ์นี้หมายความว่ารูปแบบการจัดวางไพ่ 20 ใบบางรูปแบบไม่มีเส้นให้เก็บ แต่รูปแบบการจัดวางไพ่ 21 ใบทุกรูปแบบจะมีอย่างน้อยหนึ่งเส้น (วันที่ไม่ได้พิมพ์ผิด: ผลลัพธ์ชุดหมวกของ Pellegrino จากปี 1970 เกิดขึ้นก่อนการตีพิมพ์เกม Set ครั้งแรกในปี 1974 จริงๆ) ^{[ 8 ]}${\displaystyle \mathbb {Z} _{3}^{n}}$${\displaystyle 2^{n}}$

นับตั้งแต่ผลงานของ Pellegrino ในปี 1971 และของTom Brownและ Joe Buhler ซึ่งในปี 1984 ได้พิสูจน์ว่าชุดหมวกไม่สามารถประกอบเป็นสัดส่วนคงที่ของพื้นที่ทั้งหมดได้^{[ 9 ]}ก็มีการวิจัยที่สำคัญเกี่ยวกับขนาดที่เป็นไปได้ของชุดหมวกเหล่า นี้

วิธีแก้ปัญหาของ Pellegrino สำหรับปัญหา cap-set สี่มิติยังนำไปสู่ขอบเขตล่างที่ใหญ่กว่าสำหรับมิติที่สูงกว่าใดๆ ซึ่งได้รับการปรับปรุงเพิ่มเติมโดยEdel (2004) ^{[ 2 ]} และจากนั้นโดยTyrrell (2022) [ ^{10 ] ใน}เดือนธันวาคม 2023 ทีมวิจัยจาก DeepMind ของ Google ได้ตีพิมพ์บทความที่พวกเขาจับคู่โมเดลภาษาขนาดใหญ่ (LLM) กับตัวประเมินผลและสามารถปรับปรุงขอบเขตเป็น^{[ 11 ]}${\displaystyle 2^{n}}$${\displaystyle 2.2173^{n}}$${\displaystyle 2.2180^{n}}$${\displaystyle 2.2202^{n}}$

ในปี พ.ศ. 2527 Tom Brownและ Joe Buhler ^{[ 9 ]}พิสูจน์ว่าขนาดที่ใหญ่ที่สุดที่เป็นไปได้ของเซตหมวกในคือเมื่อเติบโตขึ้น กล่าวโดยคร่าวๆ หมายความว่าเซตหมวกมีความหนาแน่นเป็นศูนย์Péter Frankl , Ronald GrahamและVojtěch Rödlได้แสดง^{[ 12 ]}ในปี พ.ศ. 2530 ว่าผลลัพธ์ของ Brown และ Buhler เป็นไปตามทฤษฎีบทการลบสามเหลี่ยมของ Ruzsa - Szemerédi ได้อย่างง่ายดาย และตั้งคำถามว่ามีค่าคงที่ อยู่หรือไม่ เช่นนั้น สำหรับค่า ที่มีขนาดใหญ่เพียงพอทั้งหมด เซตหมวกใดๆ ในจะมีขนาดไม่เกิน; นั่นคือ เซตใดๆ ในที่มีขนาดเกินจะมีเส้นตรงเชิงเส้นหรือไม่ คำถามนี้ยังปรากฏในบทความ^{[ 13 ]}ที่ตีพิมพ์โดยNoga Alonและ Moshe Dubiner ในปี พ.ศ. 2538 ในปีเดียวกัน Roy Meshulam พิสูจน์^{[ 14 ]}ว่าขนาดของเซตหมวกไม่ เกิน Michael Bateman และNets Katz ^{[ 15 ]}ปรับปรุงขอบเขตด้วยค่าคงที่บวก ${\displaystyle \mathbb {Z} _{3}^{n}}$${\displaystyle o(3^{n})}$${\displaystyle n}$${\displaystyle c<3}$${\displaystyle n}$${\displaystyle \mathbb {Z} _{3}^{n}}$${\displaystyle c^{n}}$${\displaystyle \mathbb {Z} _{3}^{n}}$${\displaystyle c^{n}}$${\displaystyle 2\cdot 3^{n}/n}$${\displaystyle O(3^{n}/n^{1+\varepsilon })}$${\displaystyle \varepsilon }$

การพิจารณาว่าขอบเขตของ Meshulam สามารถปรับปรุงให้ดีขึ้นได้หรือ ไม่นั้น ถือเป็นหนึ่งในปัญหาเปิดที่น่าสนใจที่สุดในคณิตศาสตร์เชิงผสมแบบบวกและทฤษฎี Ramseyมานานกว่า 20 ปี โดยได้รับการเน้นย้ำ เช่น จากบทความในบล็อกเกี่ยวกับปัญหานี้จากผู้ได้รับรางวัล Fields อย่างTimothy Gowers ^{[ 16 ]}และTerence Tao [ ^{17 ] ใน}บทความในบล็อกของเขา Tao กล่าวถึงปัญหานี้ว่าเป็น "บางที ปัญหาเปิดที่ฉันชอบที่สุด" และให้การพิสูจน์แบบง่ายของขอบเขตเลขชี้กำลังบนเซต cap กล่าวคือ สำหรับกำลังของจำนวนเฉพาะใดๆเซตย่อยที่ไม่มีลำดับเลขคณิตที่มีความยาวจะมีขนาดไม่เกินสำหรับบางค่า^{[ 17 ]}${\displaystyle c^{n}}$${\displaystyle c<3}$${\displaystyle p}$${\displaystyle S\subset F_{p}^{n}}$${\displaystyle 3}$${\displaystyle c_{p}^{n}}$${\displaystyle c_{p}<p}$

ข้อสันนิษฐานของเซตแคปได้รับการแก้ไขในปี 2016 เนื่องจากความก้าวหน้าหลายประการในวิธีการพหุนามErnie Croot , Vsevolod Lev และ Péter Pál Pach ได้เผยแพร่เอกสารก่อนตีพิมพ์เกี่ยวกับปัญหาที่เกี่ยวข้องของเซตย่อยที่ปราศจากความก้าวหน้าของและวิธีการนี้ถูกใช้โดยJordan EllenbergและDion Gijswijtเพื่อพิสูจน์ขอบเขตบนของในปัญหาเซตแคป^{[ 5 ] [ 6 ] [ 18 ] [ 19 ] [ 20 ]}ในปี 2019 Sander Dahmen, Johannes Hölzl และ Rob Lewis ได้ทำให้การพิสูจน์ขอบเขตบนนี้เป็นทางการใน ตัวพิสูจน์ ทฤษฎีบทLean ^{[ 21 ]}${\displaystyle \mathbb {Z} _{4}^{n}}$${\displaystyle 2.756^{n}}$

ณ เดือนมีนาคม พ.ศ. 2566 ยังไม่มีการปรับปรุงแบบเลขชี้กำลังสำหรับขอบเขตบนของ Ellenberg และ Gijswijt Jiang แสดงให้เห็นว่าโดยการตรวจสอบสัมประสิทธิ์พหุนามที่ได้จากการพิสูจน์ของ Ellenberg และ Gijswijt อย่างแม่นยำ จะสามารถประหยัดปัจจัยได้[ ^{22 ] การ}ประหยัดนี้เกิดขึ้นด้วยเหตุผลเดียวกันกับที่มีปัจจัยใน สัมประสิทธิ์ ทวิ นามกลาง${\displaystyle {\sqrt {n}}}$${\displaystyle {1/{\sqrt {n}}}}$

ในปี 2013 นักวิจัย 5 คนได้ร่วมกันตีพิมพ์บทวิเคราะห์เกี่ยวกับวิธีการแบ่งพื้นที่ที่มีขนาดไม่เกิน ออกเป็นเซตปิดที่ไม่ซ้ำกัน^{[ 23 ]}พวกเขารายงานว่าสามารถใช้เซตปิดที่แตกต่างกัน 4 เซตที่มีขนาด 20 ซึ่งครอบคลุมเซลล์ที่แตกต่างกัน 80 เซลล์ เซลล์เดียวที่ไม่ได้ถูกครอบคลุมเรียกว่าจุดยึดของแต่ละเซตปิดทั้ง 4 เซต ซึ่งเป็นจุดเดียวที่เมื่อบวกกับ 20 จุดของเซตปิดแล้ว ผลรวมทั้งหมดจะเป็น 0 (mod 3) เซตปิดทั้งหมดในชุดที่ไม่ซ้ำกันดังกล่าวจะใช้จุดยึดเดียวกัน ผลลัพธ์สำหรับขนาดที่ใหญ่กว่ายังคงเปิดอยู่ ณ ปี 2021 ${\displaystyle \mathbb {Z} _{3}^{4}}$${\displaystyle \mathbb {Z} _{3}^{4}}$

วิธีแก้ปัญหาชุดหมวกยังสามารถใช้เพื่อพิสูจน์รูปแบบบางส่วนของการคาดการณ์ดอกทานตะวันได้ กล่าวคือ ถ้าตระกูลของเซตย่อยของเซตที่มีสมาชิก - ตัวไม่มีเซตย่อยสามเซตใดที่จุดตัดกันเป็นคู่ๆ เท่ากันทั้งหมด จำนวนเซตย่อยในตระกูลจะมีค่าสูงสุดเพียงค่าคงที่^{[ 5 ] [ 24 ] [ 6 ] [ 25 ]}${\displaystyle n}$${\displaystyle c^{n}}$${\displaystyle c<2}$

ขอบเขตบนของชุดแคปหมายถึงขอบเขตล่างของอัลกอริธึมบางประเภทสำหรับการคูณเมทริกซ์^{[ 26 ]}

กราฟเกมส์เป็นกราฟปกติอย่างเข้มแข็งที่มีจุดยอด 729 จุด ขอบทุกเส้นเป็นของสามเหลี่ยมที่ไม่ซ้ำกัน ดังนั้นจึงเป็นกราฟเชิงเส้นเฉพาะที่ ซึ่งเป็นกราฟปกติอย่างเข้มแข็งเชิงเส้นเฉพาะที่ที่ใหญ่ที่สุดเท่าที่รู้จัก การสร้างกราฟนี้ขึ้นอยู่กับเซตแคป 56 จุดที่ไม่ซ้ำกันในปริภูมิเชิง ฉายไตรภาคห้ามิติ (แทนที่จะเป็นปริภูมิเชิงเส้นที่เซตแคปมักถูกกำหนดไว้) ^{[ 27 ]}

• ปัญหาห้ามมีสามสิ่งเรียงกันในแนวเดียวกัน (No-three-in-line problem)คือปัญหาในการหลีกเลี่ยงองค์ประกอบสามชิ้นที่เรียงกันในแนวเดียวกันบนตารางสองมิติ
• ปัญหา Ruzsa–Szemerédi