2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning
Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $δ^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $δ^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $δ^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $δ^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Turán numbers for matching numbers due to Erdős and Gallai.
academic

المثلثات قوس قزح التي تشترك في رأس واحد أو حافة واحدة

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

  • معرّف الورقة: 2302.00851
  • العنوان: المثلثات قوس قزح التي تشترك في رأس واحد أو حافة واحدة
  • المؤلفون: Xiaozheng Chen (جامعة تشنغتشو)، Bo Ning (جامعة نانكاي)
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 2 فبراير 2023 (نسخة أولية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2302.00851

الملخص

تبحث هذه الورقة في مسألة وجود المثلثات قوس قزح في الرسوم البيانية الملونة بالحواف. بالنسبة للرسم البياني الملون بالحواف GG الذي يحتوي على nn رأس، يُعرّف درجة اللون dc(v)d^c(v) للرأس vv بأنها عدد الألوان المختلفة المستخدمة في الحواف المجاورة لـ vv. يُرمز إلى الحد الأدنى لدرجة اللون بـ δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\}. تبين نظرية H. Li أنه عندما يكون δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2}، يحتوي الرسم البياني GG على مثلث قوس قزح. بناءً على هذا الإلهام، يدرس المؤلفون هياكل الكتب (books) والرسوم البيانية للصداقة (friendship graphs) في الرسوم البيانية الملونة بالحواف. تثبت النتائج الرئيسية أنه عندما يكون δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} و n≥3k−2n\geq 3k-2، يحتوي GG على kk مثلثات قوس قزح تشترك في حافة واحدة؛ وعندما يكون δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} و n≥2k+9n\geq 2k+9، يحتوي GG على kk مثلثات قوس قزح تشترك في رأس واحد.

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

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

  1. مسألة المثلث الكلاسيكية: أثبت Mantel (1907) أن الرسم البياني الخالي من المثلثات الذي يحتوي على nn رأس يحتوي على ما لا يزيد عن ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor حافة
  2. المثلثات المنظمة: درس Erdős وآخرون أرقام Turán للكتب BkB_k (مثلثات kk تشترك في حافة واحدة) والرسوم البيانية للصداقة FkF_k (مثلثات kk تشترك في رأس واحد)
  3. الرسوم البيانية الجزئية قوس قزح: ترتبط الرسوم البيانية الجزئية قوس قزح والرسوم البيانية الجزئية الملونة بشكل صحيح ارتباطاً وثيقاً بالعديد من الخصائص النظرية للرسوم البيانية، مثل نتائج الاستقرار الكلاسيكية وحدسية Bermond-Thomassen وحدسية Caccetta-Häggkvist

دافع البحث

  1. تعميم نظرية H. Li: أثبت H. Li (2013) أن شرط الحد الأدنى لدرجة اللون δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} يضمن وجود مثلث قوس قزح
  2. المثلثات قوس قزح المنظمة: من الطبيعي النظر في حالة مثلثات قوس قزح متعددة تشترك في رؤوس أو حواف
  3. الارتباط بنظرية الرسوم البيانية الكلاسيكية: تعميم مفاهيم الكتب والرسوم البيانية للصداقة الكلاسيكية إلى إعدادات الرسوم البيانية الملونة بالحواف

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

يركز البحث الموجود حول المثلثات قوس قزح بشكل أساسي على وجود مثلث واحد، مع وجود بحث أقل عن الترتيبات المنظمة لمثلثات قوس قزح متعددة (مثل المشاركة في الرؤوس أو الحواف).

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

  1. النظرية الرئيسية 3: تثبت أنه عندما يكون δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} و n≥3k−2n\geq 3k-2، يحتوي الرسم البياني GG على kk مثلثات قوس قزح تشترك في حافة واحدة (كتاب ملون بالحواف BkB_k)
  2. النظرية الرئيسية 4: تثبت أنه عندما يكون δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} و n≥2k+9n\geq 2k+9، يحتوي الرسم البياني GG على kk مثلثات قوس قزح تشترك في رأس واحد (رسم بياني صداقة ملون بالحواف FkF_k)
  3. تحسين نظرية H. Li: عندما يكون k=2k=2، تحسّن كلا النتيجتين الرئيسيتين النظرية الأصلية لـ H. Li
  4. الابتكار التقني: يجمع بين تقنية الدورات قوس قزح لـ Czygrinow وآخرين والتقنيات العدية الحديثة
  5. تحليل الشدة: يوفر تحليلاً لشدة النتائج والبنى القصوى

شرح الطريقة

تعريف المهمة

الإدخال: رسم بياني ملون بالحواف G=(V,E)G=(V,E)، حيث ∣V∣=n|V|=n، دالة التلوين C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}الإخراج: تحديد ما إذا كان GG يحتوي على kk مثلثات قوس قزح تشترك في حافة واحدة (أو رأس واحد) قيود: الحد الأدنى لدرجة اللون δc(G)\delta^c(G) يفي بعتبة معينة

المفاهيم والتقنيات الأساسية

1. تعريفات متعلقة بدرجة اللون

  • درجة اللون: dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • الحي α\alpha: Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • درجة اللون الأحادي: dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

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

إدخال مفهوم "تقييد اللون" من Czygrinow وآخرين:

  • بالنسبة للرأس vv و X⊆N(v)X \subseteq N(v)، إذا كان α=C(xy)\alpha = C(xy) بحيث يشكل vxyvxy مسار قوس قزح P3P_3 و α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X)، فإننا نقول أن (v,X)(v,X) يقيد اللون α\alpha لـ yy
  • يُرمز إلى عدد الألوان المقيدة بـ (v,X)(v,X) بـ σv,X(y)\sigma_{v,X}(y)

3. عد مثلثات قوس قزح

  • rt(v)rt(v): عدد مثلثات قوس قزح التي تحتوي على الرأس vv
  • rt(v,x)rt(v,x): عدد مثلثات قوس قزح التي تحتوي على كل من الرأس vv و xx
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

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

اللمة 7 (لمة العد)

بالنسبة للرسم البياني الأدنى GG والرأس vv، لدينا: rt(v,Ni(v))≥∑x∈Ni(v)(dc(x)+dc(v)−n)+di(v)∑1≤j≤s(dj(v)−1)−di(v)(di(v)−1)−∑y∈N!(v)dvyc(y,Ni(v))rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))

حيث N!(v)=⋃α∈C(G){Nα(v):∣Nα(v)∣=1}N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}.

اللمة 9 (تحليل درجة اللون الأحادي)

بالنسبة للرأس vv الذي يحتوي على أقصى درجة لون أحادي، لدينا B(v)≥0B(v) \geq 0، وعندما يكون B(v)=0B(v) = 0 توجد خصائص هيكلية خاصة.

استراتيجية الإثبات

خطوط إثبات النظرية 3

  1. افترض عدم وجود kk مثلثات قوس قزح تشترك في حافة واحدة
  2. اختر الرأس vv الذي يحتوي على أقصى درجة لون أحادي
  3. استخدم عدم المساواة العدية من اللمة 7
  4. أثبت بالتناقض وجود البنية المطلوبة

خطوط إثبات النظرية 4

  1. استخدم نظرية Erdős-Gallai حول أرقام Turán للمطابقات
  2. بناء رسم بياني مساعد G△(v)G^\triangle(v) (يتكون من حواف مثلثات قوس قزح التي تحتوي على vv)
  3. تحليل عدد الغطاء والمطابقة لـ G△(v)G^\triangle(v)
  4. الحصول على تناقض من خلال تحليل دقيق للدرجات

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

البنى القصوى

مثال 1: بناء رسم بياني ثلاثي الأجزاء كامل متوازن G[V1,V2,V3]G[V_1,V_2,V_3]، حيث ∣V(G)∣=3k−3|V(G)|=3k-3، ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1، مع تطبيق تلوين صحيح. يحقق هذا الرسم البياني dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2} لكنه لا يحتوي على BkB_k أو FkF_k، مما يثبت شدة الشرط "n≥3k−2n \geq 3k-2" في النظرية 3.

تحليل المقارنة

تقارن الورقة النتائج بالنتائج الكلاسيكية التالية:

  • نظرية H. Li: δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} يضمن مثلث قوس قزح
  • نتائج Erdős وآخرين: أرقام Turán الكلاسيكية للكتب والرسوم البيانية للصداقة
  • حالة الرسم البياني غير الملون: شروط الحد الأدنى للدرجة المقابلة

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

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

البنيةشرط هذه الورقةمتطلبات الرؤوسشرط H. Liالتحسين
B2B_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥4n \geq 4δc≥n+12\delta^c \geq \frac{n+1}{2}تحسين بنائي
F2F_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥13n \geq 13δc≥n+12\delta^c \geq \frac{n+1}{2}تحسين بنائي
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2-نتيجة جديدة
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9-نتيجة جديدة

تحليل الشدة

  • شدة النظرية 3: يوضح المثال 1 أنه عندما يكون n≤3k−3n \leq 3k-3 يلزم شرط درجة لون أقوى δc≥n+k2\delta^c \geq \frac{n+k}{2}
  • الشدة المقاربة: عندما يكون k=o(n)k = o(n)، تكون النتائج شديدة بشكل مقارب

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

بحث المثلثات قوس قزح

  1. H. Li (2013): أول من أثبت أن شرط درجة اللون δc≥n+12\delta^c \geq \frac{n+1}{2} يضمن مثلث قوس قزح
  2. B. Li وآخرون (2014): أثبتوا أن الشرط الأضعف ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} كافٍ أيضاً
  3. X. Li وآخرون (2022): قدموا نسخة عدية من مثلثات قوس قزح

نتائج نظرية الرسوم البيانية الكلاسيكية

  1. Mantel (1907): الحد الأعلى لعدد الحواف في الرسوم البيانية الخالية من المثلثات
  2. Erdős-Edwards-Khadžiivanov-Nikiforov: أرقام Turán للكتب
  3. Erdős وآخرون (1995): أرقام Turán للرسوم البيانية للصداقة

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

  1. Czygrinow وآخرون (2021): تقنية تقييد اللون المستخدمة في الدورات قوس قزح
  2. Erdős-Gallai (1959): نظرية Turán لأرقام المطابقة

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

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

  1. نجح في تعميم النتيجة الكلاسيكية لـ H. Li حول مثلثات قوس قزح إلى حالة مثلثات متعددة تشترك في هياكل
  2. إنشاء شروط كافية لوجود الكتب والرسوم البيانية للصداقة في الرسوم البيانية الملونة بالحواف
  3. توفير تحليل الشدة والبنى القصوى للنتائج

القيود

  1. متطلبات الرؤوس: يتطلب الشرط في النظرية 4 n≥2k+9n \geq 2k+9 وهو نسبياً قوي
  2. التعقيد التقني: يتضمن الإثبات عدة تقنيات عدية معقدة وتحليل هيكلي
  3. درجة التعميم: تركز النتائج بشكل أساسي على أنماط مشاركة محددة (حافة واحدة أو رأس واحد)

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

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

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

المميزات

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

أوجه القصور

  1. تعقيد الإثبات: التفاصيل التقنية كثيرة، مما قد يؤثر على إمكانية الوصول إلى النتائج
  2. نطاق التطبيق: النتائج نظرية بشكل أساسي، والسيناريوهات التطبيقية العملية غير واضحة بشكل كافٍ
  3. عوامل ثابتة: قد لا تكون بعض العوامل الثابتة في الشروط (مثل 2k+92k+9) مثلى

التأثير

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

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

ينطبق هذا البحث بشكل أساسي على:

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

المراجع

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

  • H. Li (2013): المثلثات قوس قزح C3C_3 و C4C_4 في الرسوم البيانية الملونة بالحواف
  • Erdős, Füredi, Gould, Gunderson (1995): الرسوم البيانية القصوى للمثلثات المتقاطعة
  • Czygrinow, Molla, Nagle, Oursler (2021): حول دورات قوس قزح الفردية في الرسوم البيانية الملونة بالحواف
  • وعديد من المراجع الكلاسيكية الأخرى في مجالات الرياضيات التوافقية ونظرية الرسوم البيانية