DOI: https://doi.org/10.1002/jgt.70022
تاريخ النشر: 2026-03-19
المؤلف: Zilong Yan وآخرون
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية
نظرة عامة
في دراستهم لعام 2015، أثبت فريد وغاندرسون أن الدالة القصوى \( ex(n, C_{2k+1}) \) تتحقق حصريًا على الرسم البياني الثنائي \( K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil} \) عندما يكون \( n \geq 4k – 2 \). هذه النتيجة تدفع إلى التحقيق في قرب الرسوم البيانية الخالية من \( C_{2k+1} \) من الثنائية. العمل الأخير الذي قام به رين، وانغ، وانغ، ويانغ (2024) يستكشف المزيد من الخصائص الهيكلية لمثل هذه الرسوم البيانية، خاصة عندما تشترك رسمان \( G \) و \( H \) في أقصى حد من رأس واحد وتفتقر إلى الحواف بينهما.
يقدم المؤلفون نظرة هيكلية مهمة حول الرسوم البيانية الخالية من \( C_{2k+1} \)، مع التركيز على الشرط الذي ينص على أن \( ex(n, C_{2k+1}) – e(G) = O(n^k) \) عندما يكون \( k = O(n^{1/3}) \). يقدمون مفهوم النواة القوية \( 2k \)، والتي تعتبر عنصرًا محوريًا في اشتقاق نتيجة استقرار هيكلي قوية، مما يسهل إثباتًا أبسط مقارنة بالمنهجيات السابقة. تعزز هذه التقدمات الفهم لخصائص الرسوم البيانية الخالية من \( C_{2k+1} \) فيما يتعلق بالثنائية.
مقدمة
في هذه المقدمة، يناقش المؤلفون المفاهيم الأساسية في نظرية الرسوم البيانية القصوى، مع التركيز بشكل خاص على خصائص الرسوم البيانية التي تخلو من بعض الرسوم الفرعية المحددة، والتي تُعرف بالرسوم البيانية الخالية من $F$. يعرفون المصطلحات الرئيسية مثل مجموعة الرؤوس $V(G)$، مجموعة الحواف $E(G)$، وعدد توران $ex(n, F)$، الذي يمثل الحد الأقصى لعدد الحواف في رسم بياني خالٍ من $F$ يحتوي على $n$ رأسًا. يشير المؤلفون إلى نظرية توران، التي تثبت أنه بالنسبة لرسم بياني كامل $K_{r+1}$، فإن عدد الحواف في رسم بياني خالٍ من $K_{r+1}$ مقيد بحواف رسم بياني كامل \( r \)-جزئي \( T_r(n) \). كما يبرزون التوسعات المهمة لهذه النظرية، وخاصة النتائج التي توصل إليها إردوش، ستون، وسيمونوفيتس بشأن الرسوم البيانية ذات العدد اللوني $\chi(F) = r + 1$.
تهدف الورقة إلى استكشاف الخصائص الهيكلية للرسوم البيانية الخالية من $C_{2k+1}$، بناءً على النتائج السابقة التي تصف الرسوم البيانية القصوى وقربها من الهياكل الثنائية. يقدم المؤلفون مفهومًا جديدًا، وهو النواة القوية \( 2k \)، التي تسهل إثباتًا أكثر وضوحًا لنتائجهم الرئيسية. يؤكدون أنه إذا كان الرسم البياني الخالي من \( C_{2k+1} \) \( G \) يفي بشروط حواف معينة، يمكن بناؤه عن طريق إضافة تعليقات على رسم بياني ثنائي، مع عدد محدد من الرؤوس خارج هذه البنية الثنائية. لا تعزز هذه العمل النتائج الحالية فحسب، بل توفر أيضًا رؤى أعمق حول الخصائص الهيكلية للرسوم البيانية الخالية من \( C_{2k+1} \).
نقاش
في هذا القسم، يقدم المؤلفون إثباتًا مفصلًا لنظرية 1.3، التي تتناول هيكل الرسوم البيانية الخالية من الدورات الفردية ذات الطول \(2k+1\). يستخدمون اللمحة 2.1 لإثبات أن الرسم البياني \(G\) الذي يحتوي على \(m\) حواف و\(n\) رؤوس يحتوي على رسم فرعي \(H\) بدرجة دنيا \(\delta(H) \geq \frac{m}{n}\). يتضمن الإثبات سلسلة من المتباينات والتناقضات التي تظهر في النهاية وجود نواة قوية \(2k\) في \(G\) والقيود المفروضة على حجم هذه النواة. يقدم المؤلفون أيضًا عدة ادعاءات تعزز حجتهم، بما في ذلك التأكيد على أن الحد الأقصى لحجم النواة \(H\) لا يمكن أن يتجاوز \(r\)، مما يؤدي إلى مزيد من التناقضات إذا تم انتهاك هذا الشرط.
تشير الملاحظات الختامية إلى طرق البحث المستقبلية، خاصة في توسيع نطاق الدالة القصوى \(ex(n, C_{2k+1}) – e(G)\). يشيرون إلى فرضية من كوراندي، روبرتس، وسكوت، التي تفترض أنه بالنسبة لقيم \(n\) الكبيرة بما فيه الكفاية و\(\delta\) الصغيرة بما فيه الكفاية، فإن أي رسم بياني خالٍ من \(C_{2k-1}\) \(G\) مع كثافة حواف معينة سيكون له توسع \(G^*\) يحتفظ أو يتجاوز بعض خصائص \(G\). يبرز المؤلفون أهمية هذه الفرضية في التحقيقات الجارية حول هيكل الرسوم البيانية الخالية من \(K_{r+1}\) وقربها من التكوينات الثنائية، مشيرين إلى أنه بينما تم حل بعض الحالات، لا يزال العديد منها مفتوحًا لمزيد من الاستكشاف.
DOI: https://doi.org/10.1002/jgt.70022
Publication Date: 2026-03-19
Author(s): Zilong Yan et al.
Primary Topic: Limits and Structures in Graph Theory
Overview
In their 2015 study, Füredi and Gunderson established that the extremal function \( ex(n, C_{2k+1}) \) is attained exclusively on the bipartite graph \( K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil} \) for \( n \geq 4k – 2 \). This finding prompts an investigation into the proximity of \( C_{2k+1} \)-free graphs to bipartiteness. Recent work by Ren, Wang, Wang, and Yang (2024) further explores the structural properties of such graphs, particularly when two graphs \( G \) and \( H \) share at most one vertex and lack edges between them.
The authors provide a significant structural insight into \( C_{2k+1} \)-free graphs, focusing on the condition where \( ex(n, C_{2k+1}) – e(G) = O(n^k) \) for \( k = O(n^{1/3}) \). They introduce the concept of a strong \( 2k \)-core, which serves as a pivotal element in deriving a robust structural stability result, facilitating a simpler proof compared to previous methodologies. This advancement enhances the understanding of the characteristics of \( C_{2k+1} \)-free graphs in relation to bipartiteness.
Introduction
In this introduction, the authors discuss fundamental concepts in extremal graph theory, particularly focusing on the properties of graphs that are free of specific subgraphs, denoted as $F$-free graphs. They define key terms such as the vertex set $V(G)$, edge set $E(G)$, and the Turán number $ex(n, F)$, which represents the maximum number of edges in an $n$-vertex $F$-free graph. The authors reference Turán’s theorem, which establishes that for a complete graph $K_{r+1}$, the number of edges in a $K_{r+1}$-free graph is bounded by the edges of a complete $r$-partite graph $T_r(n)$. They also highlight significant extensions of this theorem, particularly results by Erdős, Stone, and Simonovits regarding graphs with chromatic number $\chi(F) = r + 1$.
The paper aims to explore the structural properties of $C_{2k+1}$-free graphs, building on previous findings that characterize extremal graphs and their proximity to bipartite structures. The authors introduce a new concept, the strong $2k$-core, which facilitates a more straightforward proof of their main results. They assert that if a $C_{2k+1}$-free graph $G$ meets certain edge conditions, it can be constructed by adding suspensions to a bipartite graph, with a controlled number of vertices outside this bipartite structure. This work not only strengthens existing results but also provides deeper insights into the structural characteristics of $C_{2k+1}$-free graphs.
Discussion
In this section, the authors provide a detailed proof of Theorem 1.3, which addresses the structure of graphs that are free of odd cycles of length \(2k+1\). They utilize Lemma 2.1 to establish that a graph \(G\) with \(m\) edges and \(n\) vertices contains a subgraph \(H\) with a minimum degree \(\delta(H) \geq \frac{m}{n}\). The proof involves a series of inequalities and contradictions that ultimately demonstrate the existence of a strong \(2k\)-core in \(G\) and the limitations on the size of this core. The authors also introduce several claims that reinforce their argument, including the assertion that the maximum size of the core \(H\) cannot exceed \(r\), leading to further contradictions if this condition is violated.
The concluding remarks suggest avenues for future research, particularly in extending the range of the extremal function \(ex(n, C_{2k+1}) – e(G)\). They reference a conjecture by Korándi, Roberts, and Scott, which posits that for sufficiently large \(n\) and a small enough \(\delta\), any \(C_{2k-1}\)-free graph \(G\) with a specific edge density will have a blowup \(G^*\) that retains or exceeds certain properties of \(G\). The authors highlight the relevance of this conjecture to ongoing investigations into the structure of \(K_{r+1}\)-free graphs and their proximity to bipartite configurations, noting that while some cases have been resolved, many remain open for further exploration.