กลับไปหน้าบทความ

อ่าน 9 นาที

การบรรจุในไฮเปอร์กราฟ

ไฮเปอร์กราฟ

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

การบรรจุในไฮเปอร์กราฟ

การแบ่งขอบออกเป็นสองเซตย่อยนี้เรียกว่าการจัดเรียง (packing ) เนื่องจากขอบแต่ละขอบในแต่ละเซตย่อยจะมีจุดยอดที่ไม่ซ้ำกันในขอบอื่น ๆ ภายในเซตย่อยเดียวกัน การจัดเรียงนี้ถือว่าเหมาะสมที่สุดแล้วเนื่องจากมี 2 เซตย่อย และไม่มีทางที่จะจัดเรียงได้โดยใช้เพียง 1 เซตย่อย เนื่องจากขอบบางขอบอาจทับซ้อนกับจุดยอดเดียวกัน

ในทางคณิตศาสตร์การบรรจุ (packing) ในไฮเปอร์กราฟคือการแบ่งเซตของขอบของไฮเปอร์กราฟออกเป็นเซตย่อยที่ไม่ซ้ำกันจำนวนหนึ่ง โดยที่ไม่มีขอบคู่ใดในแต่ละเซตย่อยใช้จุดยอดร่วมกัน มีอัลกอริทึมที่มีชื่อเสียงสองแบบที่ใช้ในการบรรจุให้ได้ผลลัพธ์ที่ดีที่สุดใน เชิงอะซิมโทติกในไฮเปอร์กราฟแบบ k -uniform อัลกอริทึมหนึ่งคืออัลกอริทึมแบบสุ่ม โลภ (random greedy algorithm)ซึ่งเสนอโดยJoel Spencerเขาใช้กระบวนการแตกแขนงเพื่อพิสูจน์ขอบเขตที่เหมาะสมที่สุดภายใต้เงื่อนไขบางประการ อีกอัลกอริทึมหนึ่งเรียกว่า Rödl nibble ซึ่งเสนอโดยVojtěch Rödlและคณะ พวกเขาแสดงให้เห็นว่าการบรรจุที่ทำได้โดย Rödl nibble นั้นใกล้เคียงกับการบรรจุที่ได้จากอัลกอริทึมแบบสุ่มโลภในบางแง่

ประวัติศาสตร์

ปัญหาการหาจำนวนของเซตย่อยดังกล่าวในไฮเปอร์กราฟแบบ k -uniform นั้น มีที่มาจากการคาดการณ์ของPaul ErdősและHaim Hananiในปี 1963 Vojtěch Rödlได้พิสูจน์การคาดการณ์ของพวกเขาในเชิงอะซิมโทติกภายใต้เงื่อนไขบางประการในปี 1985 Pippenger และJoel Spencerได้ขยายผลลัพธ์ของ Rödl โดยใช้อัลกอริทึมแบบโลภ แบบสุ่ม ในปี 1989

คำจำกัดความและศัพท์เฉพาะ

ในคำจำกัดความต่อไปนี้ไฮเปอร์กราฟจะถูกแทนด้วยH = ( V , E ) Hเรียกว่าไฮเปอร์กราฟk- ยูนิฟอร์ม ถ้าขอบทุกขอบในEประกอบด้วย จุดยอด kจุด พอดี

พี{\displaystyle P}H คือ เซต ย่อยของขอบใน H ที่ไม่มีขอบที่แตกต่างกันสองคู่ใดที่มีจุดยอดร่วมกัน

ชม{\displaystyle H}คือ(ดี0{\displaystyle D_{0}},ϵ{\displaystyle \epsilon }ไฮเปอร์กราฟที่ดีถ้ามีอยู่จริงดี0{\displaystyle D_{0}}โดยที่สำหรับทั้งหมดx,yวี{\displaystyle x,y\in V}และดีดี0{\displaystyle D\geq D_{0}}และเงื่อนไขต่อไปนี้ทั้งสองข้อต้องเป็นจริง

ดี(1ϵ)องศา(x)ดี(1+ϵ){\displaystyle D(1-\epsilon )\leq {\text{deg}}(x)\leq D(1+\epsilon )}
โค้ด(x,y)ϵดี{\displaystyle {\text{codeg}}(x,y)\leq \epsilon D}

ปริญญาองศา(x){\displaystyle {\text{deg}}(x)}ของจุดยอดx{\displaystyle x}คือจำนวนขอบที่บรรจุx{\displaystyle x}และปริญญาร่วมโค้ด(x,y){\displaystyle {\text{codeg}}(x,y)}ประกอบด้วยจุดยอดสองจุดที่แตกต่างกันx{\displaystyle x}และy{\displaystyle y}คือจำนวนขอบที่ประกอบด้วยจุดยอดทั้งสองจุด

ทฤษฎีบท

มีการบรรจุเชิงอะซิมโทติกPที่มีขนาดอย่างน้อยnเค+1(1โอ(1)){\displaystyle {\frac {n}{K+1}}(1-o(1))}สำหรับ(เค+1){\displaystyle (K+1)}-ไฮเปอร์กราฟแบบเอกรูปภายใต้เงื่อนไขสองประการต่อไปนี้

  1. จุดยอดทั้งหมดมีดีกรีเท่ากับดี(1+โอ(1)){\displaystyle D(1+o(1))}ซึ่งดี{\displaystyle D}มีแนวโน้มเข้าสู่ค่าอนันต์
  2. สำหรับทุกคู่ของจุดยอด จะมีเพียงส่วนที่ใช้ร่วมกันเท่านั้นโอ(ดี){\displaystyle o(D)}ขอบร่วม

ที่ไหนn{\displaystyle n}คือจำนวนจุดยอดทั้งหมด ผลลัพธ์นี้แสดงให้เห็นโดย Pippenger และต่อมาได้รับการพิสูจน์โดย Joel Spencer เพื่อแก้ปัญหาการบรรจุไฮเปอร์กราฟเชิงอะซิมโทติก Joel Spencer ได้เสนออัลกอริทึมโลภแบบสุ่ม ในอัลกอริทึมนี้ กระบวนการแตกแขนงถูกใช้เป็นพื้นฐาน และแสดงให้เห็นว่าเกือบจะบรรลุการบรรจุที่เหมาะสมที่สุดในเชิงอะซิมโทติกภายใต้เงื่อนไขข้างต้นเสมอ

อัลกอริทึมการบรรจุแบบเชิงอะซิมโทติก

มีอัลกอริทึมที่มีชื่อเสียงสองแบบสำหรับการจัดเรียงไฮเปอร์กราฟ k-uniform ในเชิงอะซิมโทติก ได้แก่ อัลกอริทึมโลภแบบสุ่มผ่านกระบวนการแตกแขนง และนิบเบิลของ Rödl

อัลกอริทึมโลภแบบสุ่มผ่านกระบวนการแตกแขนง

ทุกขอบอีชม{\displaystyle E\in H}ได้รับการกำหนด "เวลาเกิด" ที่แท้จริงที่แตกต่างกันอย่างเป็นอิสระและสม่ำเสมอทีอี[0,ดี]{\displaystyle t_{E}\in [0,D]}ขอบจะถูกเลือกทีละขอบตามลำดับเวลาเกิด ขอบอี{\displaystyle E}ได้รับการยอมรับและรวมอยู่ในพี{\displaystyle P}หากมันไม่ทับซ้อนกับขอบที่ยอมรับไว้ก่อนหน้านี้ เห็นได้ชัดว่าเซตย่อยนั้นพี{\displaystyle P}เป็นบรรจุภัณฑ์ และสามารถแสดงให้เห็นได้ว่าขนาดของมันคือ|พี|=nเค+1{\displaystyle |P|={\frac {n}{K+1}}}เกือบจะแน่นอนเพื่อแสดงให้เห็นเช่นนั้น ให้หยุดกระบวนการเพิ่มขอบใหม่ ณ เวลา{\displaystyle c}สำหรับค่าใดๆ ก็ตามγ>0{\displaystyle \gamma >0}, เลือก,ดี0,ϵ{\displaystyle c,D_{0},\เอปไซลอน }โดยที่สำหรับใดๆ(ดี0,ϵ){\displaystyle (D_{0},\เอปไซลอน )}-ไฮเปอร์กราฟที่ดีเอฟx,ชม()<γ2{\displaystyle f_{x,H}(c)<\gamma ^{2}}ที่ไหนเอฟx,ชม(){\displaystyle f_{x,H}(c)}แสดงถึงความน่าจะเป็นของจุดยอดx{\displaystyle x}การอยู่รอด (จุดยอดจะอยู่รอดหากไม่อยู่ในขอบใด ๆ ในพี{\displaystyle P}) จนถึงเวลา{\displaystyle c}เห็นได้ชัดว่า ในสถานการณ์เช่นนี้ จำนวนที่คาดหวังของx{\displaystyle x}รอดชีวิตมาได้ ณ เวลานั้น{\displaystyle c}น้อยกว่าγ2n{\displaystyle \gamma ^{2}n}ดังนั้น ความน่าจะเป็นของx{\displaystyle x}การเอาชีวิตรอดจากการที่ด้อยกว่าγn{\displaystyle \gamma n}สูงกว่า1γ{\displaystyle 1-\gamma }กล่าวอีกนัยหนึ่งคือพี{\displaystyle P_{c}}ต้องรวมอย่างน้อย(1γ)n{\displaystyle (1-\gamma )n}จุดยอด ซึ่งหมายความว่า|พี|(1γ)nเค+1{\displaystyle |P|\geq (1-\gamma ){\frac {n}{K+1}}}.

เพื่อให้การพิสูจน์เสร็จสมบูรณ์ จะต้องแสดงให้เห็นว่าลิมลิมx,ชมเอฟx,ชม()=0{\displaystyle \lim _{c\rightarrow \infty }\lim _{x,H}f_{x,H}(c)=0}ด้วยเหตุนี้ พฤติกรรมเชิงอะซิมโทติกของx{\displaystyle x}การอยู่รอดนั้นจำลองโดยกระบวนการแตกแขนงอย่างต่อเนื่อง แก้ไข>0{\displaystyle c>0}และเริ่มต้นด้วยอีฟ โดยมีวันเกิดคือ{\displaystyle c}สมมติว่าเวลาเดินถอยหลัง ดังนั้นอีฟจึงให้กำเนิดบุตรในช่วงเวลาดังกล่าว[0,){\displaystyle [0,c)}ด้วย การแจกแจงปัวซงที่มีความหนาแน่นหนึ่งหน่วยความน่าจะเป็นที่อีฟจะมีเค{\displaystyle k}การเกิดคืออีเคเค!{\displaystyle {\frac {e^{-c}c^{k}}{k!}}}โดยการปรับเงื่อนไขตามเค{\displaystyle k}เวลาเกิดx1,...,xเค{\displaystyle x_{1},...,x_{k}}มีการกระจายอย่างอิสระและสม่ำเสมอบน[0,){\displaystyle [0,c)}การเกิดทุกครั้งที่อีฟให้กำเนิดนั้นประกอบด้วย...คิว{\displaystyle Q}ลูกหลานที่เกิดเวลาเดียวกันทั้งหมดเอ{\displaystyle a}กระบวนการนี้จะทำซ้ำสำหรับลูกหลานแต่ละตัว สามารถแสดงได้ว่าสำหรับทุกๆϵ>0{\displaystyle \epsilon >0}มีอยู่เค{\displaystyle K}ดังนั้นจึงมีความน่าจะเป็นสูงกว่า(1ϵ){\displaystyle (1-\epsilon )}อีฟมีเวลาอย่างมากที่สุดเค{\displaystyle K}ลูกหลาน

ต้นไม้ที่มีรากซึ่งมีแนวคิดเกี่ยวกับพ่อแม่ ลูก ราก ลำดับการเกิด และพี่น้องร่วมครรภ์ จะเรียกว่าต้นไม้สายวิวัฒนาการ โดยกำหนดให้ต้นไม้สายวิวัฒนาการมีจำนวนจำกัดที{\displaystyle T}เรากล่าวสำหรับแต่ละจุดยอดว่ามันจะอยู่รอดหรือตาย จุดยอดที่ไม่มีลูกหลานจะอยู่รอด จุดยอดจะตายก็ต่อเมื่อมันมีลูกหลานอย่างน้อยหนึ่งกลุ่มและทุกกลุ่มรอดชีวิต ให้เอฟ(){\displaystyle f(c)}แสดงถึงความน่าจะเป็นที่อีฟจะรอดชีวิตในต้นไม้แห่งสายเลือดที{\displaystyle T}โดยกำหนดตามกระบวนการข้างต้น วัตถุประสงค์คือเพื่อแสดงให้เห็นลิมเอฟ()=0{\displaystyle \lim _{c\rightarrow \infty }f(c)=0}แล้วสำหรับค่าคงที่ใดๆ{\displaystyle c}สามารถแสดงให้เห็นได้ว่าลิม*เอฟx,ชม()=เอฟ(){\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}ความสัมพันธ์ทั้งสองนี้ทำให้ข้อโต้แย้งของเราสมบูรณ์

เพื่อแสดงเอฟ()=0{\displaystyle f(c)=0}, อนุญาต0,Δ>0{\displaystyle c\geq 0,\Delta c>0}. สำหรับΔ{\displaystyle \Delta c}เล็ก,เอฟ(+Δ)เอฟ()(Δ)เอฟ()คิว+1{\displaystyle f(c+\Delta c)-f(c)\approx -(\Delta c)f(c)^{Q+1}}โดยประมาณแล้วก็คืออีฟที่เริ่มต้น ณ เวลา+Δ{\displaystyle c+\Delta c}อาจมีการเกิดในช่วงเวลาที่กำหนด[,+Δ){\displaystyle [c,c+\Delta c)}ลูกๆ ของพวกเขาทุกคนมีชีวิตรอด ในขณะที่อีฟไม่มีลูกเลย[0,){\displaystyle [0,c)}ซึ่งลูก ๆ ของพวกเขาทั้งหมดรอดชีวิต ปล่อยให้Δ0{\displaystyle \Delta c\rightarrow 0}ส่งผลให้ได้สมการเชิงอนุพันธ์เอฟ()=เอฟ()คิว+1{\displaystyle f'(c)=-f(c)^{Q+1}}ค่าเริ่มต้นเอฟ(0)=1{\displaystyle f(0)=1}นำเสนอวิธีแก้ปัญหาที่ไม่เหมือนใครเอฟ()=(1+คิว)1/คิว{\displaystyle f(c)=(1+Qc)^{-1/Q}}โปรดทราบว่าแท้จริงแล้วลิมเอฟ()=0{\displaystyle \lim _{c\rightarrow \infty }f(c)=0}.

เพื่อพิสูจน์ลิม*เอฟx,ชม()=เอฟ(){\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}ลองพิจารณาขั้นตอนที่เราเรียกว่า History ซึ่งจะยกเลิกหรือสร้างสายวิวัฒนาการ History ประกอบด้วยเซตที{\displaystyle T}ของจุดยอด ในตอนเริ่มต้นที={x}{\displaystyle T=\{x\}}.ที{\displaystyle T}จะมีโครงสร้างต้นไม้ผสมพันธุ์ที่มีx{\displaystyle x}ราก.yที{\displaystyle y\in T}เป็นได้ทั้งแบบแปรรูปแล้วและยังไม่แปรรูปx{\displaystyle x}ในขั้นต้นยังไม่ผ่านกระบวนการใดๆ สำหรับแต่ละyที{\displaystyle y\in T}ได้รับการกำหนดเวลาเกิดทีy{\displaystyle t_{y}}เราเริ่มต้นทีx={\displaystyle t_{x}=c}ประวัติศาสตร์คือการนำเอาสิ่งที่ไม่ผ่านกระบวนการมาประมวลผลyที{\displaystyle y\in T}และดำเนินการดังต่อไปนี้ สำหรับค่าทั้งหมดทีอี{\displaystyle t_{E}}กับyอี{\displaystyle y\in E}แต่ไม่มีxอี{\displaystyle x\in E}ที่ได้รับการประมวลผลไปแล้ว หากอย่างใดอย่างหนึ่งอี{\displaystyle E}มีทีอี<ทีy{\displaystyle t_{E}<t_{y}}และy,zอี{\displaystyle y,z\in E}กับzที{\displaystyle z\in T}หรือบางส่วนอี,อี{\displaystyle E,E'}มีทีอี,ทีอี<ทีy{\displaystyle t_{E},t_{E'}<t_{y}}กับyอี,อี{\displaystyle y\in E,E'}และ|อีอี|>1{\displaystyle |E\cup E'|>1}จากนั้นกระบวนการประวัติศาสตร์จะถูกยกเลิก มิฉะนั้นสำหรับแต่ละอี{\displaystyle E}กับทีอี<ทีy{\displaystyle t_{E}<t_{y}}เพิ่มทั้งหมดzอี{y}{\displaystyle z\in E-\{y\}}ถึงที{\displaystyle T}ในฐานะเพื่อนร่วมครรภ์กับพ่อแม่y{\displaystyle y}และวันเกิดทั่วไปทีอี{\displaystyle t_{E}}. ตอนนี้y{\displaystyle y}ถือว่าดำเนินการเสร็จสิ้นแล้ว ประวัติการทำงานจะหยุดลง หากไม่ถูกยกเลิก เมื่อทุกอย่างเสร็จสิ้นyที{\displaystyle y\in T}จะถูกประมวลผล หากประวัติไม่ยกเลิก ให้ดำเนินการกับ rootx{\displaystyle x}รอดชีวิตจากต้นพันธุ์ที{\displaystyle T}ก็ต่อเมื่อx{\displaystyle x}อยู่รอดมาได้จนถึงเวลา{\displaystyle c}สำหรับต้นพันธุ์ที่กำหนดไว้ ให้เอฟ(ที,){\displaystyle f(T,c)}แสดงถึงความน่าจะเป็นที่กระบวนการแตกกิ่งจะให้ต้นพันธุ์ที{\displaystyle T}ดังนั้น ความน่าจะเป็นที่ประวัติศาสตร์จะไม่ยุติลงคือเอฟ(ที,){\displaystyle f(T,c)}เนื่องจากกระบวนการแตกแขนงมีขอบเขตจำกัดเอฟ(ที,)=1{\displaystyle \sum f(T,c)=1}ผลรวมของต้นไม้พ่อแม่พันธุ์ทั้งหมดที{\displaystyle T}และประวัติศาสตร์ก็ไม่ยุติลงฉัน*{\displaystyle lim^{*}}การกระจายตัวของต้นพันธุ์เข้าใกล้การกระจายตัวของกระบวนการแตกแขนง ดังนั้นลิม*เอฟx,ชม()=เอฟ(){\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}.

การกัดของ Rödl

ในปี 1985 โรดล์ได้พิสูจน์ข้อสันนิษฐานของพอล เออร์ดอส โดยใช้วิธีที่เรียกว่า โรดล์นิบเบิล ผลลัพธ์ของโรดล์สามารถกำหนดได้ในรูปแบบของปัญหาการบรรจุหรือปัญหาการครอบคลุม สำหรับ2<เค<n{\displaystyle 2\leq l<k<n}หมายเลขการครอบคลุมที่ระบุโดยเอ็ม(n,เค,){\displaystyle M(n,k,l)}แสดงขนาดครอบครัวขั้นต่ำκ{\displaystyle \kappa }ของเค{\displaystyle k}-เซตย่อยขององค์ประกอบ{1,...,n}{\displaystyle \{1,...,n\}}ซึ่งมีคุณสมบัติที่ทุกๆ{\displaystyle l}-ชุดองค์ประกอบมีอยู่ในอย่างน้อยหนึ่งรายการเอκ{\displaystyle A\in \kappa }. พอล เออร์โดสและคณะ การคาดเดาคือ

ลิมnเอ็ม(n,เค,)(n)/(เค)=1{\displaystyle \lim _{n\rightarrow \infty }{\frac {M(n,k,l)}{{n \choose l}/{k \choose l}}}=1}.

ที่ไหน2<เค{\displaystyle 2\leq l<k}ข้อสันนิษฐานนี้หมายความโดยคร่าวๆ ว่าการจัดเรียงเชิงยุทธวิธีนั้นสามารถบรรลุได้ในเชิงอะซิมโทติก เราอาจกำหนดจำนวนการบรรจุในทำนองเดียวกันได้(n,เค,){\displaystyle m(n,k,l)}ขนาดสูงสุดของครอบครัวκ{\displaystyle \kappa }ของเค{\displaystyle k}-เซตย่อยขององค์ประกอบ{1,...,n}{\displaystyle \{1,...,n\}}มีคุณสมบัติที่ทุกคน{\displaystyle l}-ชุดองค์ประกอบมีอยู่ในอย่างมากที่สุดหนึ่งชุดเอκ{\displaystyle A\in \kappa }.

การบรรจุภายใต้เงื่อนไขที่เข้มงวดกว่า

ในปี 1997 โนกา อาลอน , จอง ฮัน คิมและโจเอล สเปนเซอร์ก็ได้จัดหาขอบเขตที่ดีให้กับγ{\displaystyle \gamma }ภายใต้เงื่อนไขโคดีกรีที่เข้มงวดกว่าซึ่งแต่ละคู่ที่แตกต่างกันวี,วีวี{\displaystyle v,v'\in V}มีขอบร่วมกันอย่างมากที่สุดเพียงหนึ่งขอบ

สำหรับ ไฮ เปอร์กราฟk- เอกรูป D-ปกติ บน จุดยอด nจุด ถ้าk > 3 จะมีการบรรจุPที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกิน 3 จุดโอ(nดี1/(เค1)){\displaystyle O(nD^{-1/(k-1)})}ถ้าk = 3 จะมีการบรรจุPที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกิน 3 จุดโอ(nดี1/2ln3/2ดี){\displaystyle O(nD^{-1/2}\ln ^{3/2}D)}.

ขอบเขตนี้เป็นที่ต้องการในแอปพลิเคชันต่างๆ เช่นระบบสามเท่าของสไตเนอร์ (Steiner Triple System ) ระบบสามเท่าของสไตเนอร์เป็นไฮเปอร์กราฟแบบง่าย 3-เอกรูป (3-uniform simple hypergraph) ซึ่งทุกคู่ของจุดยอดจะอยู่ในขอบเพียงหนึ่งเดียวเท่านั้น เนื่องจากระบบสามเท่าของสไตเนอร์เป็นแบบปกติd = ( n -1)/2 อย่างชัดเจน ขอบเขตข้างต้นจึงให้การปรับปรุงเชิงอะซิมโทติกดังต่อไปนี้

ระบบสามเหลี่ยมสไตเนอร์ใดๆ บน จุดยอด nจุด จะมีการบรรจุที่ครอบคลุมจุดยอดทั้งหมด แต่ไม่เกินโอ(n1/2ln3/2n){\displaystyle O(n^{1/2}\ln ^{3/2}n)}.

ต่อมาได้มีการปรับปรุงให้ดีขึ้นเป็นn/3โอ(บันทึกnบันทึกบันทึกn){\displaystyle n/3-O({\frac {\log n}{\log \log n}})}[ 1 ]และn43{\displaystyle {\frac {n-4}{3}}}[ 2 ]

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Packing_in_a_hypergraph&oldid=1318691186 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การบรรจุในไฮเปอร์กราฟ

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

ประวัติศาสตร์

ปัญหาการหาจำนวนของเซตย่อยดังกล่าวใน ไฮเปอร์กราฟ แบบ k -uniform นั้น มีที่มาจากการคาดการณ์ของ Paul Erdős และ Haim Hanani ในปี 1963 Vojtěch Rödl ได้พิสูจน์การคาดการณ์ของพวกเขาในเชิงอะซิมโทติกภายใต้เงื่อนไขบางประการในปี 1985 Pippenger และ Joel Spencer...

คำจำกัดความและศัพท์เฉพาะ

ในคำจำกัดความต่อไปนี้ ไฮเปอร์กราฟ จะถูกแทนด้วย H = ( V , E ) H เรียกว่า ไฮเปอร์กราฟ k- ยูนิฟอร์ม ถ้าขอบทุกขอบใน E ประกอบด้วย จุดยอด k จุด พอดี

ทฤษฎีบท

มีการบรรจุเชิงอะซิมโทติก P ที่มีขนาดอย่างน้อย n เค + 1 ( 1 − โอ ( 1 ) ) {\displaystyle {\frac {n}{K+1}}(1-o(1))} สำหรับ ( เค + 1 ) {\displaystyle (K+1)} -ไฮเปอร์กราฟแบบเอกรูปภายใต้เงื่อนไขสองประการต่อไปนี้