2025-11-14T23:55:11.549557

Turán densities of stars in uniformly dense hypergraphs

Lin, Zhou
A $3$-uniform hypergraph (or $3$-graph) $H=(V,E)$ is $(d,μ, \text{dot})$-dense if for any subsets $X, Y, Z\subseteq V$, the number of triples $(x,y,z)\in X\times Y\times Y$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||Y||Z|-μ|V|^3$. Similarly, we say that $H$ is $(d,μ, \text{dot-edge})$-dense if for any subset $X\subseteq V$ and every pair set $P\subseteq V\times V$, the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||P|-μ|V|^3$. Restricting to $\text{dot}$-dense $3$-graphs and $\text{dot-edge}$-dense $3$-graphs, determining the $\text{dot}$-uniform Turán density $π_{\text{dot}}(S_k)$ and the $\text{dot-edge}$-uniform Turán density $π_{\text{dot-edge}}(S_k)$ of the $k$-star $S_k$ for $k\ge 4$ was proposed by Schacht in ICM 2022. In particular, Reiher, Rödl and Schacht presented that $π_{\text{dot}}(S_k)\ge π_{\text{dot-edge}}(S_k)\ge \frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 3$ and $π_{\text{dot}}(S_3)= π_{\text{dot-edge}}(S_3)=1/4$. Last year, Lamaison and Wu shown that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 48$. In this paper, we show that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 11$. Moreover, we determine the $\text{dot-edge}$-uniform Turán density for all $S_k$ except for $k=4$.
academic

كثافات توران للنجوم في الرسوم البيانية الفائقة الموحدة الكثافة

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

  • معرف الورقة: 2510.12576
  • العنوان: كثافات توران للنجوم في الرسوم البيانية الفائقة الموحدة الكثافة
  • المؤلفون: Hao Lin, Wenling Zhou
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 14 أكتوبر 2025 (نسخة arXiv التمهيدية)
  • رابط الورقة: https://arxiv.org/abs/2510.12576

الملخص

تدرس هذه الورقة مشكلة كثافة توران لهياكل النجوم في الرسوم البيانية الفائقة الموحدة الكثافة. بالنسبة للرسوم البيانية الفائقة ثلاثية الاتساق، يعرّف المؤلفون مفهومي كثافة: (d,μ,⋅)(d,\mu,\cdot)-كثيفة و(d,μ,⋆)(d,\mu,\star)-كثيفة. تحت هذه القيود، تحديد كثافة توران ⋅\cdot-الاتساق π⋅(Sk)\pi_{\cdot}(S_k) وكثافة توران ⋆\star-الاتساق π⋆(Sk)\pi_{\star}(S_k) للنجم kk-SkS_k هي مشكلة مهمة طرحها Schacht في المؤتمر الدولي للرياضيين عام 2022. المساهمات الرئيسية للورقة هي: إثبات أن π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع k≥11k \geq 11، وتحديد كثافة توران ⋆\star-الاتساق لجميع SkS_k باستثناء k=4k=4.

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

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

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

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

  1. مشكلة توران الكلاسيكية: نظراً لصعوبة مشاكل توران للرسوم البيانية الفائقة، اقترح Erdős و Sós في الثمانينيات متغيراً يقصر الاهتمام على الرسوم البيانية الفائقة ثلاثية الاتساق الخالية من FF التي تكون موحدة الكثافة على مجموعات فرعية كبيرة من الرؤوس.
  2. التقدم المحدد:
    • Rödl (1986) اقترح الحدس π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2، والذي لم يُحل حتى الآن
    • Glebov و Král' و Volec (2016) وكذلك Reiher و Rödl و Schacht (2015) أثبتوا بشكل مستقل أن π⋅(K4(3)−)=1/4\pi_{\cdot}(K_4^{(3)-}) = 1/4
    • الأخيرون أيضاً أسسوا حدوداً عامة للنجوم kk-: k2−5k+7(k−1)2≤π⋅(Sk)≤(k−2k−1)2\frac{k^2-5k+7}{(k-1)^2} \leq \pi_{\cdot}(S_k) \leq \left(\frac{k-2}{k-1}\right)^2

دافع البحث

طرح Schacht رسمياً مشكلة تحديد π⋅(Sk)\pi_{\cdot}(S_k) و π⋆(Sk)\pi_{\star}(S_k) في المؤتمر الدولي للرياضيين عام 2022. أثبت Lamaison و Wu (2024) أن الحد الأدنى محكم لـ k≥48k \geq 48، وتهدف هذه الورقة إلى تعميم هذه النتيجة على قيم kk أصغر.

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

  1. النتيجة النظرية الرئيسية: إثبات أن π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع k≥11k \geq 11
  2. النتائج الموسعة: تحديد π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع k≥5k \geq 5
  3. الابتكار المنهجي: استخدام إطار عمل البناء بلوحة الألوان من Lamaison، مما يتجنب استخدام قاعدة الانتظام التقليدية للرسوم البيانية الفائقة
  4. الاختراق التقني: من خلال تحليل البنية الرسومية الموجهة المساعدة، إنشاء تقديرات الحد الأعلى الحاسمة

شرح الطريقة

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

تعريف النجم kk-: النجم kk-SkS_k هو رسم بياني فائق ثلاثي الاتساق بـ (k+1)(k+1) رأس، يحتوي على الرؤوس u,v1,…,vku, v_1, \ldots, v_k، بحيث uvivj∈E(Sk)uv_iv_j \in E(S_k) لجميع 1≤i<j≤k1 \leq i < j \leq k.

مفاهيم الكثافة:

  • ⋅\cdot-كثيفة: الرسم البياني الفائق ثلاثي الاتساق H=(V,E)H=(V,E) هو (d,μ,⋅)(d,\mu,\cdot)-كثيف إذا كان لأي مجموعات فرعية X,Y,Z⊆VX,Y,Z \subseteq V، عدد الثلاثيات (x,y,z)∈X×Y×Z(x,y,z) \in X \times Y \times Z بحيث {x,y,z}∈E\{x,y,z\} \in E على الأقل d∣X∣∣Y∣∣Z∣−μ∣V∣3d|X||Y||Z| - \mu|V|^3
  • ⋆\star-كثيفة: لأي مجموعة فرعية X⊆VX \subseteq V ومجموعة أزواج P⊆V×VP \subseteq V \times V، تحقيق الشروط المقابلة

طريقة لوحة الألوان

تعريف لوحة الألوان: لوحة الألوان P=(C,A)P = (C,A) تتضمن مجموعة ألوان محدودة CC ومجموعة ثلاثيات مرتبة A⊆C×C×CA \subseteq C \times C \times C.

الخصائص الرئيسية:

  • الكثافة: d(P):=∣A∣/∣C∣3d(P) := |A|/|C|^3
  • الحد الأدنى للدرجة: δ(P):=min⁡i∈[3],a∈C∣Aai∣/∣C∣2\delta(P) := \min_{i \in [3], a \in C} |A_a^i|/|C|^2

النظرية الأساسية:

  • π⋅(F)=πpal⋅(F)\pi_{\cdot}(F) = \pi_{pal}^{\cdot}(F) (النظرية 2.2)
  • π⋆(F)=πpal⋆(F)\pi_{\star}(F) = \pi_{pal}^{\star}(F) (النظرية 2.3)

بناء الرسم البياني الموجه المساعد

بالنسبة للوحة الألوان P=(C,A)P = (C,A)، يتم بناء الرسم البياني الموجه المساعد DP=(V,E)D_P = (V,E):

  • مجموعة الرؤوس: V=C1∪C2V = C_1 \cup C_2 (نسختان منفصلتان من CC)
  • قاعدة الحافة: إضافة أقواس وفقاً لقابلية القبول (i,j)(i,j) لأزواج الألوان (a,b)(a,b)

اللمة الرئيسية: إذا كانت لوحة الألوان PP سيئة بالنسبة لـ SkS_k، فإن DPD_P خالية من الدورات وTkT_k-free (اللمة 2.4).

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

إطار التحليل النظري

تستخدم هذه الورقة طريقة تحليل نظري بحتة، لا تتضمن بيانات تجريبية. تتم بشكل أساسي من خلال الخطوات التالية:

  1. استراتيجية الاختزال: اختزال النظرية الرئيسية إلى اللمة الحاسمة (اللمة 2.6)
  2. التحليل الهيكلي: تحليل خصائص الرسوم البيانية الموجهة TkT_k-free
  3. تقدير الحد الأعلى: إنشاء حد أعلى من خلال متغير من نظرية Caro-Wei

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

  • نظرية Brown-Harary: تحديد الحد الأقصى لعدد الأقواس في الرسوم البيانية الموجهة TkT_k-free
  • تقنيات عدم المساواة: استخدام عدم المساواة الأساسية مثل xy≤(x+y2)2xy \leq \left(\frac{x+y}{2}\right)^2
  • تحليل الحالات: مناقشة الحالات المختلفة بناءً على حجم الحد الأدنى min⁡{e2,1(a),e2,3(a)}\min\{e_{2,1}(a), e_{2,3}(a)\}

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

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

النظرية 1.2: π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع k≥11k \geq 11.

النظرية 1.4: π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع k≥5k \geq 5.

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

اللمة 2.6: لنفترض k≥5k \geq 5، بالنسبة لأي لوحة ألوان SkS_k-سيئة PP تحقق δ(P)≥14\delta(P) \geq \frac{1}{4}، لدينا d(P)≤k2−5k+7(k−1)2d(P) \leq \frac{k^2-5k+7}{(k-1)^2}.

النتائج التقنية

اللمة 3.2: بالنظر إلى k≥4k \geq 4، لنفترض DD رسم بياني موجه TkT_k-free بـ nn رأس، لكل رأس vv، دع m(v)=max⁡{dD+(v)/n,dD−(v)/n}m(v) = \max\{d_D^+(v)/n, d_D^-(v)/n\}، دع V′={v∈V(D):m(v)≥2k−1}V' = \{v \in V(D) : m(v) \geq \frac{2}{k-1}\}، إذن ∑v∈V′(m(v)−12)2≤(k−3)24(k−1)2n\sum_{v \in V'} \left(m(v) - \frac{1}{2}\right)^2 \leq \frac{(k-3)^2}{4(k-1)^2}n

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

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

  1. مشكلة Erdős-Sós: طُرحت عام 1982 لمشاكل توران المقيدة بالرسوم البيانية الفائقة الموحدة الكثافة
  2. بناء Rödl: طُرح عام 1986، يقترح الحدس π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2
  3. طريقة جبر الأعلام: قدمها Razborov (2007)، استخدمها Glebov وآخرون لحل مشكلة K4(3)−K_4^{(3)-}
  4. طريقة انتظام الرسوم البيانية الفائقة: سلسلة أعمال Reiher و Rödl و Schacht

التقدم الأخير

  • إطار عمل Lamaison: قُدم عام 2024، يقدم طريقة لوحة الألوان، يوحد دراسة π⋅\pi_{\cdot} و π⋆\pi_{\star}
  • نتيجة Lamaison-Wu: أثبتت القيمة الدقيقة لـ k≥48k \geq 48
  • المساعدة الحسابية: تشير إلى أن الحد الأدنى قد يكون محكماً بالفعل لـ k≥40k \geq 40

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

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

تحسن هذه الورقة بشكل كبير نتيجة Lamaison و Wu، وتوسع نطاق التحديد الدقيق لـ π⋅(Sk)\pi_{\cdot}(S_k) من k≥48k \geq 48 إلى k≥11k \geq 11، وتحل بالكامل مشكلة π⋆(Sk)\pi_{\star}(S_k) (باستثناء k=4k=4).

المشاكل المفتوحة

يقترح المؤلفون حدسين:

  1. الحدس 5.1: π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} لجميع 4≤k≤104 \leq k \leq 10
  2. الحدس 5.2: π⋆(S4)=13\pi_{\star}(S_4) = \frac{1}{3}

القيود التقنية

  • بالنسبة لحالة k=4k=4، يتطلب شرط m(v)≥2/3m(v) \geq 2/3، لكن من الصعب ضمان ذلك في الإطار الحالي
  • عتبة m(v)≥2/(k−1)m(v) \geq 2/(k-1) في اللمة 3.2 هي الأمثل لـ k=4k=4، وتتطلب اختراقات تقنية جديدة

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

المميزات

  1. الابتكار التقني: تطبيق ناجح لطريقة لوحة الألوان، يتجنب قاعدة الانتظام المعقدة للرسوم البيانية الفائقة
  2. النتائج المهمة: توسيع كبير لنطاق تطبيق النتائج المعروفة
  3. توحيد الطريقة: معالجة متزامنة لمشكلتي π⋅\pi_{\cdot} و π⋆\pi_{\star}
  4. الإثبات الواضح: استراتيجية اختزال منظمة تجعل خط الإثبات واضحاً

أوجه القصور

  1. التغطية غير الكاملة: لا تزال حالات 4≤k≤104 \leq k \leq 10 غير محلولة
  2. قيود الطريقة: الحالة الخاصة لـ k=4k=4 تتطلب تقنيات جديدة
  3. التعقيد الحسابي: يتضمن الإثبات تقديرات عدم مساواة معقدة وتحليل حالات

التأثير

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

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

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

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

المراجع

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

  • Erdős-Sós (1982): طرح المشكلة الأصلية
  • Razborov (2007): طريقة جبر الأعلام
  • سلسلة أعمال Reiher و Rödl و Schacht: إنشاء الحدود الأساسية
  • Lamaison (2024): إطار عمل لوحة الألوان
  • Brown-Harary (1970): أرقام توران للرسوم البيانية الموجهة