عباد الشمس (الرياضيات)

في مجالي نظرية المجموعات والتوافقية المتطرفة في الرياضيات ، تُعتبر زهرة عباد الشمس أو${\displaystyle \Delta }$النظام ^{[ 1 ]} هو مجموعة من المجموعات التي يكون تقاطع أي مجموعتين مختلفتين فيها هو نفسه. يُطلق على هذا التقاطع المشترك اسم نواة زهرة عباد الشمس.

ينشأ هذا الاسم من تشابه بصري مع زهرة عباد الشمس، ويحدث ذلك عند ترتيب مخطط فين لمجموعة عباد الشمس بطريقة بديهية. لنفترض أن العناصر المشتركة لمجموعة عباد الشمس تتجمع في مركز المخطط، وأن العناصر غير المشتركة موزعة بشكل دائري حول العناصر المشتركة. عند اكتمال مخطط فين، تتخذ المجموعات الفرعية ذات الشكل الفصي، التي تحيط بالعناصر المشتركة وعنصر فريد واحد أو أكثر، شكل بتلات الزهرة.

السؤال البحثي الرئيسي الذي يطرح نفسه فيما يتعلق بعباد الشمس هو: ما هي الشروط التي تسمح بوجود زهرة عباد شمس كبيرة (زهرة عباد شمس ذات مجموعات متعددة) ضمن مجموعة معينة من المجموعات؟${\displaystyle \Delta }$تُقدّم كلٌّ من مبرهنة -lemma ، ومبرهنة عباد الشمس ، وتخمين إردوش-رادو لعباد الشمس، شروطًا أضعف تدريجيًا من شأنها أن تُشير إلى وجود عباد شمس كبير في مجموعة مُعطاة، وتُعدّ الأخيرة واحدة من أشهر المسائل المفتوحة في التوافقية المتطرفة. ^{[ 2 ]}

يفترض ${\displaystyle W}$هو نظام مجموعة على${\displaystyle U}$أي مجموعة من المجموعات الجزئية لمجموعة${\displaystyle U}$المجموعة${\displaystyle W}$هي زهرة عباد الشمس (أو${\displaystyle \Delta }$(-النظام ) إذا كانت هناك مجموعة فرعية${\displaystyle S}$ل${\displaystyle U}$بحيث يكون لكل متميز${\displaystyle A}$و${\displaystyle B}$في${\displaystyle W}$لدينا${\displaystyle A\cap B=S}$بمعنى آخر، نظام مجموعات أو مجموعة من المجموعات${\displaystyle W}$هي زهرة عباد الشمس إذا ما حلّ كل شيء${\displaystyle W}$تشترك في نفس المجموعة الفرعية المشتركة من العناصر.

عنصر في${\displaystyle U}$إما أن يتم العثور عليها في المجموعة الفرعية المشتركة${\displaystyle S}$أو يظهر في واحد على الأكثر من${\displaystyle W}$عناصر. لا يوجد عنصر من${\displaystyle U}$يشترك فيها بعض من${\displaystyle W}$مجموعة فرعية، وليس غيرها.

تركز دراسة عباد الشمس بشكل عام على الحالات التي تحتوي فيها الأنظمة المحددة على عباد الشمس، وعلى وجه الخصوص، عندما يكون النظام المحدد كبيرًا بما يكفي ليحتوي بالضرورة على عباد الشمس.

وعلى وجه التحديد، يقوم الباحثون بتحليل الوظيفة${\displaystyle f(k,r)}$للأعداد الصحيحة غير السالبة${\displaystyle k,r}$، والذي يُعرَّف بأنه أصغر عدد صحيح غير سالب${\displaystyle n}$بحيث يكون ذلك، لأي نظام مجموعة${\displaystyle W}$بحيث كل مجموعة${\displaystyle S\in W}$عدد عناصرها على الأكثر${\displaystyle k}$، لو${\displaystyle W}$لديه أكثر من${\displaystyle n}$مجموعات، ثم${\displaystyle W}$يحتوي على زهرة دوار الشمس${\displaystyle r}$مجموعات. على الرغم من أنه ليس من الواضح أن مثل هذا${\displaystyle n}$يجب أن يكون موجودًا، وهي نتيجة أساسية وبسيطة لإردوش ورادو ، وهي نظرية نظام دلتا، تشير إلى أنه موجود.

بديل لـ${\displaystyle f(k,r)}$يُستخدم أحيانًا،${\displaystyle Sun(k,r)}$، أين${\displaystyle f(k,r)=Sun(k,r)-1}$هذا يشبه قول "إذا".${\displaystyle F}$عدد عناصره أكبر من أو يساوي${\displaystyle Sun(k,r)}$، ثم${\displaystyle F}$تحتوي على زهرة دوار الشمس بحجم${\displaystyle r}$.

في الأدبيات،${\displaystyle W}$يُفترض غالبًا أن تكون مجموعة وليست مجرد تجميع، لذا يمكن لأي مجموعة أن تظهر في${\displaystyle W}$مرة واحدة على الأكثر. بإضافة عناصر وهمية، يكفي النظر فقط في أنظمة المجموعات.${\displaystyle W}$بحيث يكون كل مجموعة في${\displaystyle W}$له عددية${\displaystyle k}$لذلك، غالبًا ما تتم صياغة معضلة عباد الشمس بشكل مكافئ على أنها تنطبق على "${\displaystyle k}$أنظمة المجموعات "الموحدة". ^{[ 3 ]}

تتناول نسخة أخرى من المسألة، والتي تُسمى أحيانًا حدسية عباد الشمس الضعيفة أو حدسية عباد الشمس لإردوش-سزيميريدي ، الحالة التي تكون فيها عائلة المجموعات مجموعة جزئية من مجموعة القوى لمجموعة مكونة من n عنصرًا. في هذه النسخة، لا يُقيّد حجم المجموعات الفردية. وتنص الحدسية على أنه إذا${\displaystyle {\mathcal {F}}}$هي عائلة من المجموعات الفرعية من${\displaystyle {1,2,\ldots ,n}}$و${\displaystyle |{\mathcal {F}}|>c^{n}}$لبعض الثوابت${\displaystyle c<2}$، ثم${\displaystyle {\mathcal {F}}}$يجب أن تحتوي على زهرة دوار الشمس بحجم 3 (في الحالة التي${\displaystyle r=3}$).

تم حل هذه الفرضية نتيجةً لاختراق في مسألة مجموعة الأغطية . وكان ألون وشبيلكا وأومانز قد أظهروا سابقًا أن الحد الأعلى الأسي لمسألة مجموعة الأغطية سيؤدي إلى حل لفرضية عباد الشمس الضعيفة لـ${\displaystyle r=3}$^{[ 12 ]} في عام 2016، استخدم إيلنبرغ وجيسويت، بالاستناد إلى عمل كروت وليف وباتش، طرقًا متعددة الحدود لإثبات حد أسي محكم لحجم مجموعات الغطاء . ^{[ 13 ]}

بعد ذلك، قام إريك ناسلوند وويل ساوين بتكييف هذه الأساليب لتقديم برهان صريح لتخمين عباد الشمس الضعيف. وقد أثبتا أن حجم أي عائلة من المجموعات الجزئية من${\displaystyle {1,2,\ldots ,n}}$بدون زهرة عباد الشمس الثالثة، يكون ذلك على الأكثر${\displaystyle 3n\sum _{k\leq n/3}{\tbinom {n}{k}}}$، والتي يحدها${\displaystyle (1.89)^{n}}$للكبير${\displaystyle n}$وقد أكد هذا التخمين بأن حجم هذه العائلات لا يتجاوز 100 فرد.${\displaystyle c^{n}}$لثابت${\displaystyle c<2}$[ ^{14 ]​}

مجموعة من المجموعات${\displaystyle {\mathcal {F}}}$يُطلق عليه اسم نظام عباد الشمس الضعيف (أو نظام دلتا الضعيف ) إذا كانت جميع التقاطعات الثنائية متساوية في الحجم . أي أنه يوجد عدد صحيح${\displaystyle c\geq 0}$بحيث يكون لأي مجموعتين مختلفتين${\displaystyle A,B\in {\mathcal {F}}}$ويرى ذلك أن${\displaystyle |A\cap B|=c}$.

كل زهرة عباد شمس قوية هي، بحكم تعريفها، زهرة عباد شمس ضعيفة. مع ذلك، ليس العكس صحيحًا دائمًا. لكي تُعتبر مجموعة ما زهرة عباد شمس قوية، يجب أن تكون التقاطعات الثنائية هي نفس المجموعة تمامًا ، وليس فقط بنفس الحجم. على سبيل المثال، لننظر إلى المجموعة التالية المكونة من أربع مجموعات منتظمة ثلاثية:

${\displaystyle {\mathcal {F}}=\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\}\}}$

هذه العائلة هي عباد شمس ضعيف لأن كل زوج من المجموعات له تقاطع بحجم 1. ومع ذلك، فهي ليست عباد شمس قوي لأن التقاطعات ليست كلها متطابقة.

إذا كانت زهرة عباد الشمس الضعيفة كبيرة بما يكفي، فإنها تُجبر على أن تصبح زهرة عباد شمس قوية من خلال مبدأ التصنيف . على وجه التحديد، أي${\displaystyle k}$-عباد الشمس الضعيف الموحد مع أكثر من${\displaystyle (r-2){\tbinom {k}{c}}+1}$يجب أن تحتوي المجموعات على زهرة دوار الشمس قوية مع${\displaystyle r}$بتلات. ^{[ 15 ]}

تُستخدم نظرية عباد الشمس في العديد من التطبيقات في علوم الحاسوب النظرية . على سبيل المثال، في عام 1986، استخدم رازبوروف نظرية عباد الشمس لإثبات أن لغة كليك تتطلب${\displaystyle n^{\log(n)}}$الدوائر الرتيبة ذات الحجم (الكبير جدًا)، وهي نتيجة رائدة في نظرية تعقيد الدوائر في ذلك الوقت. استخدمها هاستاد، وجوكنا، وبودلاك لإثبات الحدود الدنيا للعمق-${\displaystyle 3}$${\displaystyle AC_{0}}$الدوائر. كما تم تطبيقها في التعقيد المُعامل لمسألة مجموعة الضرب ، لتصميم خوارزميات قابلة للمعالجة ذات معلمات ثابتة لإيجاد مجموعات صغيرة من العناصر التي تحتوي على عنصر واحد على الأقل من عائلة معينة من المجموعات. ^{[ 16 ]}

نسخة من${\displaystyle \Delta }$-lemma التي تعادل أساسًا Erdős-Rado${\displaystyle \Delta }$تنص نظرية النظام على أن مجموعة قابلة للعد من مجموعات k تحتوي على زهرة عباد شمس لا نهائية قابلة للعد أو${\displaystyle \Delta }$-نظام.

ال${\displaystyle \Delta }$تنصّ المبرهنة - على أن كل مجموعة غير قابلة للعد من المجموعات المنتهية تحتوي على مجموعة غير قابلة للعد${\displaystyle \Delta }$-نظام.

ال${\displaystyle \Delta }$تُعدّ مبرهنة -lemma أداةً من أدوات نظرية المجموعات التوافقية ، تُستخدم في البراهين لفرض حدٍّ أعلى على حجم مجموعة من العناصر غير المتوافقة ثنائياً في مجموعة جزئية مرتبة قسرية . على سبيل المثال، يمكن استخدامها كأحد عناصر البرهان الذي يُبيّن أن عدم صحة فرضية الاستمرارية يتوافق مع نظرية زيرميلو-فرانكل للمجموعات . وقد قدّمها شانين ( 1946 ) . 

لو${\displaystyle W}$هو${\displaystyle \omega _{2}}$مجموعة بحجم n من المجموعات الفرعية القابلة للعد من${\displaystyle \omega _{2}}$وإذا صحت فرضية الاستمرارية، فسيكون هناك${\displaystyle \omega _{2}}$-حجم${\displaystyle \Delta }$-نظام فرعي. دع${\displaystyle \langle A_{\alpha }:\alpha <\omega _{2}\rangle }$تعداد${\displaystyle W}$. ل${\displaystyle \operatorname {cf} (\alpha )=\omega _{1}}$، يترك ${\displaystyle f(\alpha )=\sup(A_{\alpha }\cap \alpha )}$بحسب قاعدة فودور ، ثبت${\displaystyle S}$أدوات مكتبية في${\displaystyle \omega _{2}}$بحيث${\displaystyle f}$يساوي باستمرار${\displaystyle \beta }$على${\displaystyle S}$. يبني${\displaystyle S'\subseteq S}$من حيث العددية${\displaystyle \omega _{2}}$بحيث كلما${\displaystyle i<j}$في${\displaystyle S'}$ثم${\displaystyle A_{i}\subseteq j}$باستخدام فرضية الاستمرارية، لا يوجد سوى${\displaystyle \omega _{1}}$- العديد من المجموعات الفرعية القابلة للعد من${\displaystyle \beta }$لذلك، من خلال المزيد من التخفيف، يمكننا تثبيت النواة.

يمكن استخدام حل مشكلة مجموعة الغطاء لإثبات شكل جزئي من حدسية عباد الشمس، أي أنه إذا كانت عائلة من المجموعات الجزئية من${\displaystyle n}$لا تحتوي مجموعة العناصر على زهرة عباد الشمس الثلاثية (الحالة التي${\displaystyle r=3}$إذا كان عدد المجموعات الفرعية في العائلة على الأكثر${\displaystyle c^{n}}$لثابت${\displaystyle c<2}$[ ^{17 ] [ 18 ] [ 19 ]​}

• ثيمان، رينيه. ليمّة عباد الشمس لإردوش ورادو (تطوير البرهان الرسمي في إيزابيل/هول، أرشيف البراهين الرسمية)
• صفحة Polymath المقابلة
• (التسلسل A332077 في OEIS )