2025-11-10T03:02:02.480547

Tight bounds towards Zarankiewicz problem in hypergraph

Gao, Hou, Huang et al.
The classical Zarankiewicz problem, which concerns the maximum number of edges in a bipartite graph without a forbidden complete bipartite subgraph, motivates a direct analogue for hypergraphs. Let $K_{s_1,\ldots, s_r}$ be the complete $r$-partite $r$-graph such that the $i$-th part has $s_i$ vertices. We say an $r$-partite $r$-graph $H=H(V_1,\ldots,V_r)$ contains an ordered $K_{s_1,\ldots, s_r}$ if $K_{s_1,\ldots, s_r}$ is a subgraph of $H$ and the set of size $s_i$ vertices is embedded in $V_i$. The Zarankiewicz number for $r$-graph, denoted by $z(m_1, \ldots, m_{r}; s_1,, \ldots,s_{r})$, is the maximum number of edges of the $r$-partite $r$-graph whose $i$-th part has $m_i$ vertices and does not contain an ordered $K_{s_1,\ldots, s_r}$. In this paper, we show that $$z(m_1,m_2, \cdots, m_{r-1},n ; s_1,s_2, \cdots,s_{r-1}, t)=Θ\left(m_1m_2\cdots m_{r-1} n^{1-1 / s_1s_2\cdots s_{r-1}}\right)$$ for a range of parameters. This extends a result of Conlon [Math. Proc. Camb. Philos. Soc. (2022)].
academic

حدود محكمة تجاه مسألة زارانكيفيتش في الرسوم البيانية الفائقة

المعلومات الأساسية

  • معرّف الورقة: 2510.14869
  • العنوان: حدود محكمة تجاه مسألة زارانكيفيتش في الرسوم البيانية الفائقة
  • المؤلفون: Guorong Gao, Jianfeng Hou, Shuping Huang, Hezhi Wang
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 16 أكتوبر 2025 (نسخة أولية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.14869

الملخص

تدرس مسألة زارانكيفيتش الكلاسيكية الحد الأقصى لعدد الأضلاع في الرسوم البيانية الثنائية التي لا تحتوي على رسم بياني ثنائي كامل محظور. تعمم هذه الورقة المسألة إلى الرسوم البيانية الفائقة. بالنسبة للرسم البياني الفائق r-جزئي الكامل Ks1,…,srK_{s_1,\ldots,s_r} حيث يحتوي الجزء i على sis_i رأس، تعرّف الورقة رقم زارانكيفيتش للرسم البياني الفائق r-جزئي z(m1,…,mr;s1,…,sr)z(m_1,\ldots,m_r; s_1,\ldots,s_r) كالحد الأقصى لعدد الأضلاع في رسم بياني فائق r-جزئي حيث يحتوي الجزء i على mim_i رأس ولا يحتوي على Ks1,…,srK_{s_1,\ldots,s_r} مرتب. تثبت النتائج الرئيسية أنه ضمن نطاق معين من المعاملات:

z(m1,m2,⋯ ,mr−1,n;s1,s2,⋯ ,sr−1,t)=Θ(m1m2⋯mr−1n1−1/s1s2⋯sr−1)z(m_1,m_2,\cdots,m_{r-1},n; s_1,s_2,\cdots,s_{r-1},t) = \Theta\left(m_1m_2\cdots m_{r-1} n^{1-1/s_1s_2\cdots s_{r-1}}\right)

تعمم هذه النتيجة عمل Conlon من عام 2022.

الخلفية البحثية والدافع

خلفية المشكلة

  1. مسألة زارانكيفيتش الكلاسيكية: دراسة الحد الأقصى لعدد الأضلاع z(m,n;s,t)z(m,n;s,t) في الرسوم البيانية الثنائية G(m,n)G(m,n) التي لا تحتوي على رسم بياني ثنائي كامل محدد Ks,tK_{s,t}
  2. نظرية توران: تعطي نظرية Erdős-Stone-Simonovits الكلاسيكية تقديرات للحد الأقصى لعدد الأضلاع في الرسوم البيانية التي لا تحتوي على رسم بياني فرعي معين
  3. التعميم إلى الرسوم البيانية الفائقة: تعميم طبيعي لمسألة زارانكيفيتش من الرسوم البيانية الثنائية إلى الرسوم البيانية الفائقة r-موحدة

دافع البحث

  1. إكمال النظرية: مسألة زارانكيفيتش للرسوم البيانية الفائقة هي مسألة أساسية في الرياضيات التوافقية وتتطلب إطار نظري شامل
  2. التحديات التقنية: التعميم من الرسوم البيانية إلى الرسوم البيانية الفائقة يشكل تحديات تقنية ويتطلب تقنيات إثبات جديدة
  3. القيمة التطبيقية: للرسوم البيانية الفائقة تطبيقات مهمة في علوم الحاسوب ونظرية المعلومات

حدود الطرق الموجودة

  1. تعطي نظرية Kővári-Sós-Turán فقط حد أعلى: z(m,n;s,t)=O(mn1−1/s)z(m,n;s,t) = O(mn^{1-1/s})
  2. نتائج Conlon تنطبق فقط على حالة الرسوم البيانية الثنائية
  3. نقص النتائج ذات الحدود المحكمة في حالة الرسوم البيانية الفائقة

المساهمات الأساسية

  1. إنشاء إطار نظري لمسألة زارانكيفيتش للرسوم البيانية الفائقة: إعطاء تعريف دقيق للرسوم البيانية الفرعية الكاملة المرتبة في الرسوم البيانية الفائقة r-جزئية
  2. إثبات نظرية فوق التشبع: تعميم نظرية Erdős الفوق تشبع الكلاسيكية إلى الرسوم البيانية الفائقة (النظرية 1.1)
  3. إعطاء حد أعلى: تعميم نظرية Kővári-Sós-Turán إلى الرسوم البيانية الفائقة (النتيجة 1.2)
  4. إنشاء حد أدنى: استخدام الطريقة الجبرية العشوائية لإثبات حد أدنى متطابق (النظرية 1.3)
  5. الحصول على حدود محكمة: إنشاء حدود متقاربة بشكل مقارب ضمن نطاق معين من المعاملات (النتيجة 1.4)

شرح الطريقة

تعريف المهمة

الإدخال: المعاملات m1,…,mrm_1,\ldots,m_r (أحجام الأجزاء) و s1,…,srs_1,\ldots,s_r (أحجام الرسوم البيانية الفرعية المحظورة) الإخراج: تقدير مقارب لرقم زارانكيفيتش z(m1,…,mr;s1,…,sr)z(m_1,\ldots,m_r; s_1,\ldots,s_r)القيود: عدم احتواء Ks1,…,srK_{s_1,\ldots,s_r} المرتب كرسم بياني فائق فرعي

التعاريف الأساسية

  • الرسم البياني الفائق r-موحد: رسم بياني فائق حيث تكون مجموعة الأضلاع مكونة من r-عناصر
  • Ks1,…,srK_{s_1,\ldots,s_r} المرتب: رسم بياني فائق r-جزئي كامل حيث يتم تضمين sis_i رؤوس من الجزء i في ViV_i
  • رقم زارانكيفيتش: z(m1,…,mr;s1,…,sr)z(m_1,\ldots,m_r; s_1,\ldots,s_r) هو الحد الأقصى لعدد الأضلاع الذي يستوفي الشروط

طرق التقنية الرئيسية

1. نظرية فوق التشبع (النظرية 1.1)

استخدام الاستقراء وتقنيات العد المزدوج:

  • الحالة الأساسية (r=2): عد مزدوج معياري، استخدام عدم المساواة في Jensen
  • خطوة الاستقراء: اختزال مسألة r-رسم بياني فائق إلى مسألة (r-1)-رسم بياني فائق من خلال تقنية link-hypergraph

عدم المساواة الرئيسية: ts1,1=∑v∈V2(d(v)s1)≥m2(e/m2s1)t_{s_1,1} = \sum_{v \in V_2} \binom{d(v)}{s_1} \geq m_2 \binom{e/m_2}{s_1}

2. الطريقة الجبرية العشوائية (النظرية 1.3)

تعميم طريقة Bukh الجبرية العشوائية إلى الرسوم البيانية الفائقة:

عملية البناء:

  1. ربط فئات الرؤوس (up11,…,upr−1r−1)(u^1_{p_1}, \ldots, u^{r-1}_{p_{r-1}}) بكثيرات حدود من درجة (s1s2⋯sr−1−1)(s_1s_2\cdots s_{r-1}-1) وهي fp1,…,pr−1f_{p_1,\ldots,p_{r-1}}
  2. يتصل كل فئة رؤوس بمجموعة النقاط: Sp1,…,pr−1={(x1,…,xs−1,fp1,…,pr−1(x1,…,xs−1)):xi∈Fq}S_{p_1,\ldots,p_{r-1}} = \{(x_1,\ldots,x_{s-1}, f_{p_1,\ldots,p_{r-1}}(x_1,\ldots,x_{s-1})) : x_i \in \mathbb{F}_q\}

اللمة الرئيسية 2.5: يوجد اختيار كثيرات حدود بحيث يكون البعد الجبري للتقاطع Ta1,a2∩⋯∩Ta1,ajT_{a_1,a_2} \cap \cdots \cap T_{a_1,a_j} على الأكثر s−js-j

نقاط الابتكار التقني

  1. التحكم في البعد: استخدام نظرية البعد من الهندسة الجبرية للتحكم في حجم التقاطع
  2. البناء الاستقرائي: اختيار تدريجي لكثيرات الحدود مع ضمان شروط البعد
  3. التحليل الاحتمالي: استخدام اللمة 2.1 لتقدير احتمالية مرور كثيرة حدود عشوائية عبر نقاط محددة

النتائج النظرية

النظريات الرئيسية

النظرية 1.1 (نظرية فوق التشبع): إذا كان عدد الأضلاع في رسم بياني فائق r-جزئي H يستوفي ∣E(H)∣≥c1⋅(∏i=1r−1mi)⋅mr1−1/(s1s2⋯sr−1)|E(H)| \geq c_1 \cdot (\prod_{i=1}^{r-1} m_i) \cdot m_r^{1-1/(s_1s_2\cdots s_{r-1})}، فإن H يحتوي على الأقل c2⋅∏i=1r(misi)⋅p∏i=1rsic_2 \cdot \prod_{i=1}^r \binom{m_i}{s_i} \cdot p^{\prod_{i=1}^r s_i} نسخة من Ks1,…,srK_{s_1,\ldots,s_r} المرتب.

النتيجة 1.2 (الحد الأعلى): z(m1,…,mr;s1,…,sr)=O(m1⋯mr−1mr1−1/(s1⋯sr−1))z(m_1,\ldots,m_r; s_1,\ldots,s_r) = O(m_1\cdots m_{r-1} m_r^{1-1/(s_1\cdots s_{r-1})})

النظرية 1.3 (الحد الأدنى): تحت الشروط s≤ts \leq t و m≤nt1/s−1/s(s−1)m \leq n^{t^{1/s-1}/s(s-1)}، z(m1,…,mr−1,n;s1,…,sr−1,t)=Ω(m1⋯mr−1n1−1/(s1⋯sr−1))z(m_1,\ldots,m_{r-1},n; s_1,\ldots,s_{r-1},t) = \Omega(m_1\cdots m_{r-1} n^{1-1/(s_1\cdots s_{r-1})})

النتيجة 1.4 (الحدود المحكمة): تحت الشروط المناسبة، يتطابق الحد الأعلى والأدنى، مما يعطي: z(m1,…,mr−1,n;s1,…,sr−1,t)=Θ(m1⋯mr−1n1−1/(s1⋯sr−1))z(m_1,\ldots,m_{r-1},n; s_1,\ldots,s_{r-1},t) = \Theta(m_1\cdots m_{r-1} n^{1-1/(s_1\cdots s_{r-1})})

تقنيات الإثبات

إثبات الحد الأعلى (الطريقة الاستقرائية)

  1. الخطوة الأساسية: عند r=2 استخدام العد المزدوج المعياري
  2. الفرضية الاستقرائية: افترض أن النظرية صحيحة لـ r-1
  3. خطوة الاستقراء:
    • إزالة الرؤوس منخفضة الدرجة
    • لكل رأس متبقي v، اعتبر رسم البياني الفائق link-hypergraph HvH_v
    • تطبيق الفرضية الاستقرائية وعدم المساواة في Jensen

إثبات الحد الأدنى (الطريقة الجبرية العشوائية)

  1. البناء الجبري: استخدام كثيرات الحدود على الحقول المحدودة لبناء رسم بياني فائق
  2. تحليل البعد: إثبات البعد الجبري للتقاطعات الرئيسية
  3. التقدير الاحتمالي: استخدام اللمة 2.1 للتحكم في احتمالية الأحداث "السيئة"

الأعمال ذات الصلة

النتائج الكلاسيكية

  1. نظرية Kővári-Sós-Turán: تعطي الحد الأعلى في حالة الرسوم البيانية الثنائية
  2. نظرية Erdős-Stone-Simonovits: صيغة مقاربة لأرقام توران للرسوم البيانية العامة
  3. نتائج Brown-Erdős-Rényi: الحدود المثلى لـ K2,tK_{2,t} و K3,tK_{3,t}

التطورات الحديثة

  1. Kollár-Rónyai-Szabó و Alon-Rónyai-Szabó: استخدام الطرق الجبرية
  2. الطريقة الجبرية العشوائية لـ Bukh: تقنية اختراق، أساس هذه الورقة
  3. عمل Conlon: حدود محكمة لمسألة زارانكيفيتش للرسوم البيانية الثنائية

الأعمال المتعلقة بالرسوم البيانية الفائقة

  1. Ma-Yuan-Zhang: حدود دنيا لأرقام توران للرسوم البيانية الفائقة
  2. Pohoata-Zakharov: شروط معاملات محسّنة
  3. Mubayi: تحسينات أسية ونتائج ذات صلة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

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

  1. إنشاء إطار نظري شامل
  2. إثبات حدود عليا ودنيا متطابقة
  3. تعميم النتائج الكلاسيكية المهمة

القيود

  1. قيود المعاملات: الحدود المحكمة تنطبق فقط ضمن نطاق معين من المعاملات m≤nt1/s−1/s(s−1)m \leq n^{t^{1/s-1}/s(s-1)}
  2. العوامل الثابتة: النتائج مقاربة، والعوامل الثابتة لم تُحدد
  3. الشروط التقنية: تتطلب شروط تقنية مثل mi≥nm_i \geq n

الاتجاهات المستقبلية

  1. توسيع نطاق المعاملات: البحث عن حدود محكمة تحت شروط أكثر عمومية
  2. العوامل الثابتة الدقيقة: تحديد العوامل الثابتة الدقيقة في الصيغة المقاربة
  3. التطبيقات الخوارزمية: تطبيق النتائج النظرية على مسائل خوارزمية

التقييم المتعمق

المميزات

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

أوجه القصور

  1. قيود معاملات قوية: نطاق تطبيق الحدود المحكمة محدود نسبياً
  2. تعقيد تقني: الطريقة الجبرية العشوائية لها عتبة تقنية عالية
  3. التطبيقات العملية: الحاجة إلى استكشاف المزيد من الروابط بين النتائج النظرية والتطبيقات العملية

التأثير

  1. القيمة الأكاديمية: توفير أدوات ونتائج مهمة لنظرية القيم الطرفية للرسوم البيانية الفائقة
  2. التأثير التقني: قد تكون الطريقة الجبرية العشوائية المعممة قابلة للتطبيق على نطاق أوسع
  3. البحث اللاحق: توفير اتجاهات وطرق جديدة لأبحاث المسائل ذات الصلة

السيناريوهات المناسبة

  1. البحث النظري: أبحاث الرياضيات التوافقية ونظرية الرسوم البيانية الطرفية
  2. تصميم الخوارزميات: مسائل خوارزمية تتطلب تجنب هياكل فرعية محددة
  3. نظرية الترميز: بناء وتحليل أكواد تصحيح الأخطاء

المراجع

تستشهد الورقة بالأدبيات المهمة في هذا المجال، بما في ذلك:

  • الأعمال الكلاسيكية لـ Kővári و Sós و Turán
  • الطريقة الجبرية العشوائية لـ Bukh
  • نتائج الرسوم البيانية الثنائية لـ Conlon
  • والتطورات الحديثة لـ Mubayi و Pohoata-Zakharov وآخرين

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