2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

حول حالة الحافة الثمانية التربيعية لمسألة براون-إيردوس-سوس

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

  • معرّف الورقة: 2506.01739
  • العنوان: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • المؤلفون: أوليج بيخوركو، شومين صن (جامعة وارويك)
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 16 أكتوبر 2025 (الإصدار الثاني من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2506.01739

الملخص

تدرس هذه الورقة حالة الحافة الثمانية التربيعية لمسألة براون-إيردوس-سوس. لتكن f(r)(n;s,k)f^{(r)}(n;s,k) أقصى عدد حواف في فوق-رسم بياني rr-منتظم على nn رأس لا يحتوي على kk حافة تغطي على الأكثر ss رأس. خمّن براون وإيردوس وسوس عام 1973 أنه لجميع kk، يوجد الحد lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k). حل هذا التخمين مؤخراً ديلكور وبوستل، وعممه شانغوان على جميع الانتظامات r≥4r\ge 4. تدرس هذه الورقة حالة k=8k=8، وتحدد قيمة الحد لكل r≥4r\ge 4، وتعطي حداً أدنى عندما r=3r=3.

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

  1. المسألة الأساسية: تدرس مسألة براون-إيردوس-سوس أعداد توران للفوق-رسوم البيانية rr-المنتظمة، أي أقصى عدد حواف في فوق-رسم بياني على nn رأس مع تجنب فوق-رسم بياني محظور معين.
  2. أهمية المسألة: هذه مسألة أساسية في الرياضيات التوافقية القصوى، وترتبط ارتباطاً وثيقاً بنظرية رامسي ونظرية توران والمجالات الأساسية الأخرى. يحمل حل هذه المسألة أهمية كبيرة لفهم الخصائص الهيكلية للفوق-رسوم البيانية.
  3. التقدم الحالي:
    • أثبت براون وإيردوس وسوس أن f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t)، حيث t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • عندما t=2t=2 (أي s=rk−2k+2s = rk-2k+2)، تم إثبات وجود الحد π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k)
    • بالنسبة لـ k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\}، قيم الحد معروفة
  4. الدافع البحثي: k=8k=8 هو الهدف الطبيعي التالي للدراسة، وتظهر هذه الحالة تعقيداً جديداً، خاصة في السلوك المختلف بين r=3r=3 و r≥4r\ge 4.

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

  1. النظرية الرئيسية: لجميع r≥4r \geq 4، يتم تحديد π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}
  2. نتائج الحد الأدنى: إثبات أن π(3,8)≥316\pi(3,8) \geq \frac{3}{16}، مع التخمين بأن هذا الحد ضيق
  3. طرق البناء: توفير بناء صريح يحقق الحد الأدنى، بناءً على رسوم البيانية الحادثة للمستويات الإسقاطية
  4. التحليل الهيكلي: تحليل عميق لهيكل فوق-رسوم البيانية الخالية من G8(r)G^{(r)}_8، خاصة تصنيف العناقيد الثنائية
  5. التطبيقات: إنشاء ارتباطات مع أعداد رامسي المعممة، الحصول على lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}

شرح الطرق

تعريف المهمة

دراسة السلوك التقاربي للدالة f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) عندما k=8k=8، أي تحديد قيمة الحد π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8).

طرق بناء الحد الأدنى

وحدات البناء الأساسية

  • رسم البياني R: تعريف فوق-رسم بياني 3-منتظم بـ 5 رؤوس و 3 حواف، يتكون من حافة abcabc وماسة {buv,cuv}\{buv, cuv\}
  • عائلات المسارات: استخدام المستويات الإسقاطية الديزارغية لبناء عائلة مسارات ثنائية PP تحقق شروط الندرة والاتصال المحددة

طريقة الحذف الاحتمالي

  1. البدء من رسم البياني الحادث للمستوى الإسقاطي، بناء رسم بياني ثنائي الجزء G′G'
  2. اختيار مسارات ثنائية عشوائياً باحتمالية (logm)/m1/2(log m)/m^{1/2}
  3. استخدام طريقة الحذف الاحتمالي لإزالة المسارات التي تشكل تكوينات كثيفة
  4. وضع نسخ من رسم البياني RR على كل مسار ثنائي

اللمة الرئيسية

اللمة 3.2: لقوة أولية كافية qq، توجد عائلة مسارات ثنائية PP تحقق:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • الاتحاد ⋃P∈PP\bigcup_{P\in P} P يحتوي على O(m3/2)O(m^{3/2}) حافة
  • الاتحاد خالٍ من المثلثات والدورات الرباعية والخماسية
  • لأي i∈[8]i \in [8]، كل مجموعة فرعية من ii رأس لها على الأقل i+2i+2 رأس

طرق إثبات الحد الأعلى

استراتيجية الدمج

  1. الدمج الأحادي: تقسيم مجموعة الحواف إلى عناقيد أحادية متصلة (في الواقع أشجار)
  2. الدمج الثنائي: دمج إضافي للحصول على عناقيد ثنائية، من خلال شرط الدمج {1}∣{2}\{1\}|\{2\}

التحليل الهيكلي

اللمة 4.7: لأي عنقود ثنائي FF بـ ∣F∣≥9|F| \geq 9، ينتمي FF إلى إحدى العائلات التالية:

  • AA: عنقود ثنائي بـ 9 حواف بتركيب (5,2,2)(5,2,2)
  • BB: عنقود ثنائي بـ 9 حواف بتركيب (1,2,4,2)(1,2,4,2)
  • C1,C2C_1, C_2: عناقيد ثنائية بتركيبات مختلفة
  • E,FE, F: عناقيد ثنائية بهيكل خاص
  • SiS_i: عناقيد ثنائية تتكون من شجرة أحادية واحدة و ii ماسة بـ (2i+1)(2i+1) حافة

تخصيص الأوزان

لـ r≥5r \geq 5 و r=4r = 4 يتم استخدام دوال وزن مختلفة:

عندما r≥5r \geq 5: wF(uv)={1إذا كان 1∈CF(uv)1/3إذا كان 2∈CF(uv) و 1∉CF(uv)0خلاف ذلكw_F(uv) = \begin{cases} 1 & \text{إذا كان } 1 \in C_F(uv) \\ 1/3 & \text{إذا كان } 2 \in C_F(uv) \text{ و } 1 \notin C_F(uv) \\ 0 & \text{خلاف ذلك} \end{cases}

عندما r=4r = 4: استخدام القيمة العظمى لخمس دوال مساعدة hiFh_i^F كوزن.

الإعداد التجريبي

هذه الورقة بحث نظري بحت، لا تتضمن تجارب حسابية. يتم الحصول على جميع النتائج من خلال إثبات رياضي صارم.

التحقق من الإثبات

  • يتم التحقق من الحد الأدنى من خلال البناء الصريح
  • يتم إثبات الحد الأعلى من خلال تحليل شامل للحالات وطريقة تخصيص الأوزان
  • جميع اللمات الرئيسية لها إثبات رياضي كامل

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

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

النظرية 1.1: لكل r≥4r \geq 4، لدينا π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}.

النظرية 1.2: π(3,8)≥316\pi(3,8) \geq \frac{3}{16}.

التخمين 1.3: π(3,8)=316\pi(3,8) = \frac{3}{16}.

المقارنة مع النتائج المعروفة

  • π(r,2)=1r2−r\pi(r,2) = \frac{1}{r^2-r} (رودل)
  • π(r,4)=1r2−r\pi(r,4) = \frac{1}{r^2-r} (جلوك وآخرون)
  • π(r,6)=1r2−r\pi(r,6) = \frac{1}{r^2-r} لـ r≥4r \geq 4 (جلوك وآخرون)
  • π(3,6)=61330\pi(3,6) = \frac{61}{330} (حالة خاصة)

الاكتشافات الجديدة

  1. ظاهرة العتبة: r=4r=4 هو الحد الأدنى للانتظامية حيث يكون π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}
  2. تعقيد الهيكل: حالة k=8k=8 تظهر هيكل عنقود ثنائي أكثر تعقيداً من قيم kk المدروسة سابقاً
  3. ارتباط رامسي: إنشاء ارتباطات جديدة مع أعداد رامسي المعممة

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

التطور التاريخي

  1. براون-إيردوس-سوس (1973): تقديم التخمين الأصلي والحدود الأساسية
  2. رودل (1985): حل حالة k=2k=2
  3. جلوك (2019): حل حالة k=3k=3
  4. ديلكور-بوستل (2024): إثبات وجود الحد
  5. شانغوان (2023): التعميم على جميع الانتظامات

التطور التقني

  • نظرية المطابقة غير المتضاربة: تقنية رئيسية طورها ديلكور-بوستل وجلوك وآخرون
  • طريقة تخصيص الأوزان: تقنية حد أعلى مطورة بناءً على عمل جلوك وآخرين
  • البناء الاحتمالي: طريقة احتمالية بناءً على الهياكل الهندسية الجبرية

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

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

  1. تحديد كامل لقيمة π(r,8)\pi(r,8) عندما r≥4r \geq 4
  2. توفير حد ممكن أن يكون أمثل لحالة r=3r=3
  3. إنشاء ارتباطات جديدة مع أعداد رامسي المعممة

القيود

  1. حالة r=3r=3: الحصول على حد أدنى فقط، مطابقة الحد الأعلى لا تزال مسألة مفتوحة
  2. تعقيد البناء: بناء الحد الأدنى معقد تقنياً جداً، قد توجد بناءات أبسط
  3. التعميم: وضوح تطبيق الطريقة على قيم kk أكبر غير واضح

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

  1. إثبات التخمين π(3,8)=316\pi(3,8) = \frac{3}{16}
  2. دراسة حالات k≥9k \geq 9
  3. البحث عن تقنيات بناء وحد أعلى أكثر عمومية
  4. استكشاف الارتباطات مع مسائل قصوى أخرى

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

المميزات

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

أوجه القصور

  1. عدم الاكتمال في r=3r=3: المسألة المفتوحة الرئيسية لم تُحل بعد
  2. خصوصية الطريقة: التقنيات موجهة بشكل كبير نحو k=8k=8، القابلية للتعميم محدودة
  3. التعقيد الحسابي: بعض خطوات الإثبات طويلة جداً وتقنية

القيمة التأثيرية

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

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

تنطبق هذه الطريقة على:

  1. دراسة مسائل قصوى للفوق-رسوم البيانية
  2. مسائل نوع توران مع فوق-رسوم بيانية محظورة
  3. تحليل الهيكل في التحسين التوافقي
  4. تطبيقات الرياضيات التوافقية الجبرية

المراجع

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

  • الأعمال الأصلية لبراون وإيردوس وسوس
  • النتائج الاختراقية لديلكور وبوستل
  • سلسلة أعمال جلوك وآخرين
  • نتائج التعميم لشانغوان
  • أعمال بينيت وآخرين حول أعداد رامسي المعممة

التقييم الإجمالي: هذه ورقة عالية الجودة في الرياضيات التوافقية النظرية، حققت تقدماً مهماً في دراسة مسألة براون-إيردوس-سوس. على الرغم من أن المسألة المفتوحة الرئيسية (حالة r=3r=3) لم تُحل بالكامل، فإن المساهمات التقنية والابتكارات المنهجية في الورقة توفر أساساً متيناً للبحث اللاحق في هذا المجال.