DOI: https://doi.org/10.1016/j.ejc.2026.104373
تاريخ النشر: 2026-03-19
المؤلف: Jian Zheng وآخرون
الموضوع الرئيسي: نظرية الطيف في الفيزياء الرياضية
نظرة عامة
في هذا القسم، يبني المؤلفون على النتائج الأساسية في نظرية الرسوم البيانية، حيث يمددون بشكل خاص عمل بولوباس وإردوش، وكذلك نيكيفوروف، بشأن وجود المجموعات في الرسوم البيانية بناءً على الخصائص الطيفية. يثبتون أنه بالنسبة لرسم بياني \( G \) يحتوي على \( n \) رأسًا ونصف قطر طيفي لا يحمل علامة \( q(G) \) يفي بعوامل معينة، يحتوي \( G \) على عدد كبير من نسخ المجموعة \( K_{k+1} \) وتضخيم \( K_{k+1}[t] \) بحجم \( t = \Omega_{k,\epsilon}(\log n) \). تعمم هذه النتيجة النتائج السابقة وتقدم نتائج استقرار جديدة تتعلق بالعدد اللوني للرسوم البيانية.
بالإضافة إلى ذلك، يوضح المؤلفون أنه إذا كان \( G \) خاليًا من \( F \) ويحقق شروطًا معينة على نصف قطره الطيفي، يمكن تقريبه بشكل وثيق بواسطة هيكل معين، \( T_{n,k} \)، مع عدد محدود فقط من تعديلات الحواف. كما يستخدمون طرقًا احتمالية لتأكيد مثالية حدودهم، مما يؤدي إلى تطبيقات تمتد إلى نظرية بولوباس-إردوش الكلاسيكية وتثبت نتائج طيفية قصوى للرسوم البيانية الفائقة. تسهم هذه النتائج في فهم أعمق للتفاعل بين هيكل الرسم البياني والخصائص الطيفية.
مقدمة
في مقدمة هذه الورقة، يحدد المؤلفون الرموز والتعريفات الأساسية اللازمة لتحليل السلوك اللانهائي لمتغيرات الرسم البياني. يعرفون العلاقات بين الدوال باستخدام الرموز اللانهائية: \( f(n) = \Omega(g(n)) \)، \( f(n) = O(g(n)) \)، و \( f(n) = o(g(n)) \)، والتي تصف الحدود الدنيا، الحدود العليا، والنمو الضئيل بالنسبة لدالة أخرى، على التوالي. يتم وضع هذه التعريفات في إطار نظرية الرسوم البيانية، حيث \( |V| = n \) و \( |E| = m \) تشير إلى عدد الرؤوس والحواف في رسم بياني \( G \).
يقدم المؤلفون مفاهيم رئيسية مثل الرسوم البيانية الكاملة \( K_{k+1} \) والرسوم البيانية الثنائية الكاملة \( K_{t,t} \)، بالإضافة إلى التضخيم \( t \) لرسم بياني \( H \)، المشار إليه بـ \( H[t] \). كما يعرفون الرسوم البيانية الخالية من \( F \)، والتي لا تحتوي على رسم فرعي متشابه مع رسم بياني معين \( F \)، ويقدمون عدد توران \( ex(n, F) \)، الذي يمثل الحد الأقصى لعدد الحواف في رسم بياني خالي من \( F \) يحتوي على \( n \) رأسًا. تشمل مجموعة \( Ex(n, F) \) جميع هذه الرسوم البيانية مع الحد الأقصى لعدد الحواف. تضع هذه التعريفات الأساس لاستكشاف الورقة لمتغيرات الرسم البياني وخصائصها اللانهائية.
النتائج
يناقش القسم نتائج هامة في نظرية الرسوم البيانية القصوى، مع التركيز بشكل خاص على نظرية توران وتوسعاتها. طرح توران مشكلة تحديد الحد الأقصى لعدد الحواف في رسم بياني لا يحتوي على رسم فرعي كامل $K_{k+1}$، مما أدى إلى تعريف رسم توران $T_{n,k}$، وهو الرسم البياني الكامل ذو \( k \) أجزاء على \( n \) رأسًا. تم إثبات أنه بالنسبة لأي رسم بياني خالي من \( K_{k+1} \) \( G \) يحتوي على \( n \) رأسًا، فإن عدد الحواف يحقق \( e(G) \leq e(T_{n,k}) \)، مع المساواة إذا وفقط إذا كان \( G \) متشابهًا مع \( T_{n,k} \). يتم إعطاء عدد توران الدقيق بواسطة \( ex(n, K_{k+1}) = e(T_{n,k}) = \left(1 – \frac{1}{k}\right) \frac{n^2}{2} \).
علاوة على ذلك، يبرز القسم نتائج الاستقرار التي قدمها إردوش وسيمونوفيتس، والتي تشير إلى أنه إذا كان الرسم البياني \( G \) قريبًا من عدد الحواف لـ \( T_{n,k} \)، يمكن تحويله إلى \( T_{n,k} \) عن طريق تعديل عدد محدود من الحواف. قام نيكيفوروف بتوسيع هذه النتائج باستخدام نصف القطر الطيفي للجوار، موضحًا أنه إذا كان \( G \) رسمًا بيانيًا خاليًا من \( F \) مع نصف قطر طيفي مرتفع بما فيه الكفاية، يمكن أيضًا تقريبه بواسطة \( T_{n,k} \) تحت قيود مشابهة لتعديل الحواف. يختتم القسم بمناقشة النتائج المعروفة للرسوم البيانية الكثيفة، بما في ذلك ليمّا إردوش-سيمونوفيتس للزيادة الفائقة، التي تؤكد أن الرسوم البيانية الكثيفة تحتوي على عدد كبير من نسخ \( K_{k+1} \)، وليمات أخرى تقدم أدوات أساسية لإثبات نظريات مختلفة في سياق نظرية الرسوم البيانية القصوى.
مناقشة
تتناول قسم المناقشة في الورقة توسيعات وتعميمات مختلفة لنظرية توران، مع التركيز بشكل خاص على نظرية الرسوم البيانية القصوى. يتم تسليط الضوء على نظرية إردوش-ستون-سيمونوفيتس كنتيجة أساسية، حيث تقدم تقديرات لانهائية لأعداد توران للرسوم البيانية غير الثنائية. بشكل محدد، تنص على أنه بالنسبة لرسم بياني \( F \) مع عدد لوني \( \chi(F) = k + 1 \geq 2 \)، يمكن تقريب الدالة القصوى \( ex(n, F) \) كـ \( ex(n, F) = \left(1 – \frac{1}{k}\right) \frac{n^2}{2} + o(n^2) \). ومع ذلك، بالنسبة للرسوم البيانية الثنائية، تعطي النظرية فقط \( ex(n, F) = o(n^2) \)، مما يدفع إلى مزيد من البحث لتحسين الحدود لمختلف الرسوم البيانية الثنائية.
كما يقدم القسم نصف القطر الطيفي للجوار \( \lambda(G) \) وآثاره في مشاكل توران الطيفية. بشكل ملحوظ، يناقش النتائج التي توصل إليها ويلف ونيكيفوروف وغيدولي، والتي توسع نظرية توران الكلاسيكية إلى سياقات طيفية، مما يثبت حدودًا لـ \( \lambda(G) \) في الرسوم البيانية الخالية من \( K_{k+1} \). تؤكد الورقة على أهمية نصف القطر الطيفي غير الحامل للعلامة \( q(G) \)، مع نتائج جديدة تشير إلى أنه إذا كان \( G \) رسمًا بيانيًا يحتوي على \( n \) رأسًا مع \( q(G) \geq \left(1 – \frac{1}{k} + \epsilon\right)2n \)، فإن \( G \) يحتوي على عدد كبير من نسخ \( K_{k+1} \). تسلط النتائج الضوء على التفاعل بين الخصائص الطيفية ونظرية الرسوم البيانية القصوى، مما يمهد الطريق للبحث المستقبلي في هذا المجال.
DOI: https://doi.org/10.1016/j.ejc.2026.104373
Publication Date: 2026-03-19
Author(s): Jian Zheng et al.
Primary Topic: Spectral Theory in Mathematical Physics
Overview
In this section, the authors build upon foundational results in graph theory, specifically extending the work of Bollobás and Erdős, as well as Nikiforov, regarding the presence of cliques in graphs based on spectral properties. They establish that for a graph \( G \) with \( n \) vertices and a signless Laplacian spectral radius \( q(G) \) meeting certain thresholds, \( G \) contains a significant number of copies of the clique \( K_{k+1} \) and a blowup \( K_{k+1}[t] \) of size \( t = \Omega_{k,\epsilon}(\log n) \). This result generalizes previous findings and introduces new stability results related to the chromatic number of graphs.
Additionally, the authors demonstrate that if \( G \) is \( F \)-free and meets specific conditions on its spectral radius, it can be closely approximated by a particular structure, \( T_{n,k} \), with only a limited number of edge modifications. They also employ probabilistic methods to assert the optimality of their bounds, leading to applications that extend the classical Bollobás-Erdős theorem and establish spectral extremal results for hypergraphs. These findings contribute to a deeper understanding of the interplay between graph structure and spectral properties.
Introduction
In the introduction of this paper, the authors establish foundational notation and definitions essential for analyzing the asymptotic behavior of graph parameters. They define the relationships between functions using asymptotic notations: \( f(n) = \Omega(g(n)) \), \( f(n) = O(g(n)) \), and \( f(n) = o(g(n)) \), which describe lower bounds, upper bounds, and negligible growth relative to another function, respectively. These definitions are contextualized within the framework of graph theory, where \( |V| = n \) and \( |E| = m \) denote the number of vertices and edges in a graph \( G \).
The authors introduce key concepts such as complete graphs \( K_{k+1} \) and complete bipartite graphs \( K_{t,t} \), as well as the \( t \)-blowup of a graph \( H \), denoted as \( H[t] \). They also define \( F \)-free graphs, which do not contain a subgraph isomorphic to a given graph \( F \), and introduce the Turán number \( ex(n, F) \), representing the maximum number of edges in an \( n \)-vertex \( F \)-free graph. The set \( Ex(n, F) \) encompasses all such graphs with the maximum edge count. These definitions set the stage for the paper’s exploration of graph parameters and their asymptotic properties.
Results
The section discusses significant results in extremal graph theory, particularly focusing on Turán’s theorem and its extensions. Turán posed the problem of determining the maximum number of edges in a graph that does not contain a complete subgraph $K_{k+1}$, leading to the definition of the Turán graph $T_{n,k}$, which is the complete $k$-partite graph on $n$ vertices. It was established that for any $K_{k+1}$-free graph $G$ with $n$ vertices, the number of edges satisfies $e(G) \leq e(T_{n,k})$, with equality if and only if $G$ is isomorphic to $T_{n,k}$. The exact Turán number is given by $ex(n, K_{k+1}) = e(T_{n,k}) = \left(1 – \frac{1}{k}\right) \frac{n^2}{2}$.
Further, the section highlights stability results introduced by Erdős and Simonovits, which indicate that if a graph $G$ is close to the edge count of $T_{n,k}$, it can be transformed into $T_{n,k}$ by modifying a limited number of edges. Nikiforov extended these results using the adjacency spectral radius, demonstrating that if $G$ is an $F$-free graph with a sufficiently high spectral radius, it can also be approximated by $T_{n,k}$ under similar edge modification constraints. The section concludes with a discussion of known results for dense graphs, including the Erdős-Simonovits supersaturation lemma, which asserts that dense graphs contain a significant number of copies of $K_{k+1}$, and other lemmas that provide foundational tools for proving various theorems in the context of extremal graph theory.
Discussion
The discussion section of the paper elaborates on various extensions and generalizations of Turán’s theorem, particularly focusing on extremal graph theory. The Erdős-Stone-Simonovits theorem is highlighted as a cornerstone result, providing asymptotic estimates for Turán numbers of non-bipartite graphs. Specifically, it states that for a graph \( F \) with chromatic number \( \chi(F) = k + 1 \geq 2 \), the extremal function \( ex(n, F) \) can be approximated as \( ex(n, F) = \left(1 – \frac{1}{k}\right) \frac{n^2}{2} + o(n^2) \). However, for bipartite graphs, the theorem yields only \( ex(n, F) = o(n^2) \), prompting further research to refine bounds for various bipartite graphs.
The section also introduces the adjacency spectral radius \( \lambda(G) \) and its implications in spectral Turán-type problems. Notably, it discusses results by Wilf, Nikiforov, and Guiduli, which extend the classical Turán theorem to spectral contexts, establishing bounds for \( \lambda(G) \) in \( K_{k+1} \)-free graphs. The paper emphasizes the significance of the signless Laplacian spectral radius \( q(G) \), with new results indicating that if \( G \) is an \( n \)-vertex graph with \( q(G) \geq \left(1 – \frac{1}{k} + \epsilon\right)2n \), then \( G \) contains a substantial number of copies of \( K_{k+1} \). The findings underscore the interplay between spectral properties and extremal graph theory, paving the way for future research in this domain.