معضلة إزالة الرسم البياني الفائق

في نظرية المخططات ، تنصّ مبرهنة إزالة المخطط الفائق على أنه عندما يحتوي مخطط فائق على عدد قليل من نسخ مخطط فائق فرعي مُعطى، فإنه يُمكن إزالة جميع النسخ بإزالة عدد قليل من الحواف الفائقة. وهي تعميم لمبرهنة إزالة المخطط . تُعرف الحالة الخاصة التي يكون فيها المخطط رباعي الأوجه باسم مبرهنة إزالة رباعي الأوجه. وقد أثبتها لأول مرة كلٌّ من ناغل، ورودل، وشاخت، وسكوكان ^{[ 1 ]} ، وبشكل مستقل، غاورز ^{[ 2 ] .}

يمكن استخدام مبرهنة إزالة الرسم البياني الفائق لإثبات نتائج مثل مبرهنة سيميريدي ^{[ 1 ]} ومبرهنة سيميريدي متعددة الأبعاد. ^{[ 1 ]}

يترك${\displaystyle H}$كن${\displaystyle r}$- رسم بياني فائق منتظم (كل حافة تربط بالضبط r رأسًا) مع${\displaystyle h}$الرؤوس. تنصّ نظرية إزالة الرسم البياني الفائق على أنه لأي${\displaystyle \varepsilon >0}$يوجد${\displaystyle \delta =\delta (r,m,\varepsilon )>0}$بحيث يكون لأي ${\displaystyle r}$-زي مُوحد،${\displaystyle n}$الرسم البياني الفائق ذو الرؤوس${\displaystyle G}$بأقل من${\displaystyle \delta n^{h}}$الرسوم البيانية الفرعية المتماثلة مع${\displaystyle H}$من الممكن إزالة جميع نسخ${\displaystyle H}$عن طريق إزالة ما لا يزيد عن${\displaystyle \varepsilon n^{r}}$الحواف.

ويمكن صياغة ذلك بشكل مكافئ على النحو التالي، لأي رسم بياني فائق${\displaystyle G}$مع${\displaystyle o(n^{h})}$نسخ من${\displaystyle H}$يمكننا حذف جميع نسخ${\displaystyle H}$من${\displaystyle G}$عن طريق الإزالة${\displaystyle o(n^{r})}$الحواف الفائقة.

تُعتبر معضلة إزالة الرسم البياني حالة خاصة مع${\displaystyle r=2}$.

الفكرة العامة للبرهان مشابهة لفكرة مبرهنة إزالة الرسوم البيانية . نُبرهن على نسخة من مبرهنة سيميريدي للانتظام (تقسيم الرسوم البيانية الفائقة إلى كتل شبه عشوائية) ومبرهنة عد (تقدير عدد الرسوم البيانية الفائقة في كتلة شبه عشوائية مناسبة). تكمن الصعوبة الرئيسية في البرهان في تعريف المفهوم الصحيح لانتظام الرسوم البيانية الفائقة. وقد بُذلت محاولات عديدة ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ]} لتعريف "التقسيم" و"الكتل شبه العشوائية (المنتظمة)" في الرسم البياني الفائق، لكن لم تتمكن أي منها من تقديم مبرهنة عد قوية. أول تعريف صحيح لمبرهنة سيميريدي للانتظام للرسوم البيانية الفائقة العامة قدمه رودل وآخرون ^{[ 1 ] .}

في مبرهنة سيميريدي للانتظام ، تُجرى عمليات التقسيم على الرؤوس (الحافة الفائقة 1) لتنظيم الحواف (الحافة الفائقة 2). ومع ذلك، بالنسبة لـ${\displaystyle k>2}$إذا قمنا ببساطة بتنظيم${\displaystyle k}$باستخدام حافة فائقة واحدة فقط، سنفقد معلومات جميع الحواف الفائقة.${\displaystyle j}$- حواف فائقة في المنتصف حيث${\displaystyle 1<j<k}$ويفشلون في إيجاد مبرهنة عدّ. ^{[ 13 ]} يجب أن تقسم النسخة الصحيحة${\displaystyle (k-1)}$- الحواف الفائقة من أجل تنظيم${\displaystyle k}$- الحواف الفائقة. للحصول على مزيد من التحكم في${\displaystyle (k-1)}$-الحواف الفائقة، يمكننا التعمق أكثر وتقسيمها على${\displaystyle (k-2)}$-الحواف الفائقة لتنظيمها، إلخ. في النهاية، سنصل إلى بنية معقدة لتنظيم الحواف الفائقة.

على سبيل المثال، نعرض نسخة غير رسمية من معضلة انتظام سيميريدي، التي قدمها فرانكل ورودل لأول مرة، باستخدام رسم بياني فائق ثلاثي الأبعاد. ^{[ 14 ]} لنفترض تجزئة للحواف${\displaystyle E(K_{n})=G_{1}^{(2)}\cup \dots \cup G_{l}^{(2)}}$بحيث يكون ذلك بالنسبة لمعظم الثلاثيات${\displaystyle (i,j,k),}$يوجد الكثير من المثلثات في الأعلى${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right).}$نقول ذلك${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)}$هي "شبه عشوائية" بمعنى أنه بالنسبة لجميع الرسوم البيانية الفرعية${\displaystyle A_{i}^{(2)}\subset G_{i}^{(2)}}$مع وجود عدد ليس بقليل من المثلثات في الأعلى${\displaystyle \left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right),}$لدينا

${\displaystyle \left|d\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)-d\left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right)\right|\leq \varepsilon ,}$

أين${\displaystyle d(X,Y,Z)}$يشير إلى نسبة${\displaystyle 3}$- حافة فائقة منتظمة في${\displaystyle G^{(3)}}$من بين جميع المثلثات الموجودة أعلى${\displaystyle (X,Y,Z)}$.

ثم نُعرّف التقسيم المنتظم بأنه تقسيم تكون فيه ثلاثيات الأجزاء غير المنتظمة على الأكثر${\displaystyle \varepsilon }$جزء من جميع ثلاثيات الأجزاء في التقسيم.

إضافة إلى ذلك، نحتاج إلى مزيد من التنظيم${\displaystyle G_{1}^{(2)},\dots ,G_{l}^{(2)}}$عن طريق تقسيم مجموعة الرؤوس. ونتيجة لذلك، لدينا البيانات الكاملة لانتظام الرسم البياني الفائق كما يلي:

1. قسم من${\displaystyle E(K_{n})}$إلى رسوم بيانية بحيث${\displaystyle G^{(3)}}$يجلس بشكل عشوائي ظاهرياً في الأعلى؛
2. قسم من${\displaystyle V(G)}$بحيث تكون الرسوم البيانية في (1) عشوائية زائفة للغاية (بطريقة تشبه معضلة الانتظام لسزيميريدي ).

بعد إثبات معضلة انتظام الرسم البياني الفائق، يمكننا إثبات معضلة عدّ الرسم البياني الفائق. ويستمر باقي البرهان على غرار برهان معضلة إزالة الرسم البياني .

يترك${\displaystyle r_{k}(N)}$ليكن حجم أكبر مجموعة فرعية من${\displaystyle \{1,\ldots ,N\}}$الذي لا يحتوي على طول${\displaystyle k}$التقدم الحسابي. تنص نظرية سمريدي على أن،${\displaystyle r_{k}(N)=o(N)}$لأي ثابت${\displaystyle k}$الفكرة الأساسية للبرهان هي أننا نبني مخططًا فائقًا من مجموعة جزئية بدون أي طول.${\displaystyle k}$ثم استخدم مبرهنة إزالة الرسم البياني لإظهار أن هذا الرسم البياني لا يمكن أن يحتوي على عدد كبير جدًا من الحواف الفائقة، مما يدل بدوره على أن المجموعة الفرعية الأصلية لا يمكن أن تكون كبيرة جدًا.

يترك${\displaystyle A\subset \{1,\ldots ,N\}}$ليكن مجموعة جزئية لا تحتوي على أي طول${\displaystyle k}$متتابعة حسابية. ليكن${\displaystyle M=k^{2}N+1}$ليكن عددًا صحيحًا كبيرًا بما يكفي . يمكننا التفكير في${\displaystyle A}$كجزء من${\displaystyle \mathbb {Z} /M\mathbb {Z} }$من الواضح، إذا${\displaystyle A}$ليس له طول${\displaystyle k}$المتتابعة الحسابية في${\displaystyle \mathbb {Z} }$كما أنه ليس له طول${\displaystyle k}$المتتابعة الحسابية في${\displaystyle \mathbb {Z} /M\mathbb {Z} }$.

سنقوم ببناء${\displaystyle k}$-partite${\displaystyle (k-1)}$- رسم بياني فائق منتظم${\displaystyle G}$من${\displaystyle A}$مع أجزاء${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$وكلها${\displaystyle M}$مجموعات رؤوس العناصر المفهرسة بواسطة${\displaystyle \mathbb {Z} /M\mathbb {Z} }$لكل${\displaystyle 1\leq i\leq k}$نضيف حافة فائقة بين الرؤوس${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$إذا وفقط إذا${\displaystyle \sum _{j\neq i}(j-i)v_{j}\in A.}$يترك${\displaystyle H}$كن كاملاً${\displaystyle k}$-partite${\displaystyle (k-1)}$- رسم بياني فائق منتظم. إذا${\displaystyle G}$يحتوي على نسخة متماثلة من${\displaystyle H}$مع رؤوس${\displaystyle v_{1},\ldots ,v_{k}}$، ثم${\displaystyle \alpha _{i}=\sum _{j\neq i}(j-i)v_{j}\in A}$لأي${\displaystyle 1\leq i\leq j}$ومع ذلك، لاحظ أن${\displaystyle \alpha _{i}}$هو طول${\displaystyle k}$المتتابعة الحسابية ذات الفرق المشترك${\displaystyle \alpha _{i+1}-\alpha _{i}=-\sum _{j}v_{j}}$. منذ${\displaystyle A}$ليس له طول${\displaystyle k}$فيما يتعلق بالمتتابعة الحسابية، لا بد أن يكون الأمر كذلك.${\displaystyle \alpha _{1}=\cdots =\alpha _{k}}$، لذا${\displaystyle \sum _{j}v_{j}=0}$.

وبالتالي، لكل حافة فائقة${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$، يمكننا العثور على نسخة فريدة من${\displaystyle H}$أن هذه الحافة تقع في إيجاد${\displaystyle v_{i}=-\sum _{j\neq i}v_{j}}$عدد نسخ${\displaystyle H}$في${\displaystyle G}$يساوي${\displaystyle {\frac {1}{k}}e(G)=O(N^{k-1})=o(N^{k})}$لذلك، وبحسب مبرهنة إزالة الرسم البياني الفائق، يمكننا إزالة${\displaystyle o(N^{k-1})}$حواف لإزالة جميع نسخ${\displaystyle H}$في${\displaystyle G}$بما أن كل حافة فائقة من${\displaystyle G}$موجود في نسخة فريدة من${\displaystyle H}$، لإزالة جميع نسخ${\displaystyle H}$في${\displaystyle G}$، نحتاج إلى إزالة على الأقل${\displaystyle e(G)/k}$الحواف. وبالتالي،${\displaystyle e(G)=o(N^{k-1})}$.

عدد الحواف الفائقة في${\displaystyle G}$يكون${\displaystyle kM^{k-2}|A|=o(N^{k-1})}$، وهو ما يخلص إلى أن${\displaystyle |A|=o(N)}$.

لا تُعطي هذه الطريقة عادةً حدًا كميًا جيدًا، لأن الثوابت الخفية في مبرهنة إزالة الرسم البياني الفائق تتضمن دالة أكرمان العكسية . وللحصول على حد كمي أفضل، أثبت لينغ وساه وسوهني أن${\displaystyle |A|\leq {\frac {N}{\exp(-(\log \log N)^{c_{k}})}}}$لبعض الثوابت${\displaystyle c_{k}}$.اعتمادا علي${\displaystyle k}$[ ^{15 ]} إنه أفضل خيار ^لـ${\displaystyle k\geq 5}$حتى الآن.

• استُخدمت مبرهنة إزالة المخطط الفائق لإثبات نظرية سيميريدي متعددة الأبعاد بواسطة ج. سوليموسي. ^{[ 16 ]} تنص المبرهنة على أنه لأي مجموعة جزئية منتهية${\displaystyle S}$ل${\displaystyle \mathbb {Z} ^{r}}$، أي${\displaystyle \delta >0}$وأي${\displaystyle n}$كبيرة بما يكفي، أي مجموعة فرعية من${\displaystyle [n]^{r}}$بحجم لا يقل عن${\displaystyle \delta n^{r}}$يحتوي على مجموعة فرعية من الشكل${\displaystyle a\cdot S+d}$أي نسخة موسعة ومترجمة من${\displaystyle S}$تُعتبر نظرية الزوايا حالة خاصة عندما${\displaystyle S=\{(0,0),(0,1),(1,0)\}}$.
• كما أنها تستخدم لإثبات نظرية سيميريدي متعددة الحدود، ونظرية سيميريدي للمجال المحدود ، ونظرية سيميريدي للمجموعة الأبيلية المحدودة. ^{[ 17 ] [ 18 ]}

• معضلة إزالة الرسم البياني
• نظرية سيميريدي
• مسائل تتضمن متتابعات حسابية