DOI: https://doi.org/10.1090/tran/9694
تاريخ النشر: 2026-01-15
المؤلف: Zhenyun Du
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية
نظرة عامة
في عام 1975، طرح إردوش وساور سؤالاً يتعلق بالحد الأقصى لعدد الحواف في رسم بياني يحتوي على \( n \) رأسًا ولا يحتوي على رسم فرعي \( r \)-منتظم. وقد أثبتت التطورات الأخيرة التي قام بها جانزر وسوداكوف أن مثل هذا الرسم البياني يمكن أن يحتوي على أقصى حد من الحواف يبلغ \( C r n \log \log n \)، مما يتماشى مع حد أدنى سابق قدمه بايبر، رودل، وسيميريدي. يوسع هذا البحث نتائجهم من خلال إثبات أن كل رسم بياني يحتوي على \( n \) رأسًا ولا يحتوي على رسم فرعي \( r \)-منتظم يمكن أن يحتوي على أقصى حد من الحواف يبلغ \( C r^2 n \log \log n \)، وبالتالي يحل مشكلة إردوش-ساور حتى ثابت مطلق لـ \( n \) كبير بما فيه الكفاية.
بالإضافة إلى ذلك، يقدم المؤلفون حدودًا دقيقة لمجموعة أوسع من قيم \( r \)، مع حدوث انتقال ملحوظ بالقرب من \( r \approx \log n \). على وجه التحديد، يوضحون أن أي رسم بياني يحتوي على \( n \) رأسًا بمتوسط درجة لا تقل عن \( \min(C r \log(n/r), C r^2 \log \log n) \) يجب أن يحتوي على رسم فرعي \( r \)-منتظم. الحد \( C r \log(n/r) \) دقيق لـ \( r \geq \log n \)، بينما \( C r^2 \log \log n \) ينطبق لـ \( r < (\log n)^{1 - \Omega(1)} \). تعالج هذه النتائج مشكلة طرحها رودل وويزوك في عام 1997 لمعظم قيم \( r \). كما يعزز المؤلفون إطار جانزر-سوداكوف من خلال استخدام تقنيات جبرية متنوعة وتقديم عملية عشوائية جديدة تحدد بكفاءة الرسوم الفرعية شبه المنتظمة في الرسوم البيانية شبه المنتظمة، مما يساهم بشكل كبير في هذا المجال.
مقدمة
تتناول مقدمة الورقة البحثية المشكلة المهمة المتمثلة في العثور على الرسوم الفرعية المنتظمة بدرجة محددة في نظرية الرسوم البيانية، مما يبرز أهميتها للعديد من النظريات والتطبيقات في التركيب. يشير المؤلفون إلى سؤال محوري طرحه إردوش وساور في عام 1975 حول الحد الأقصى للدرجة المتوسطة لرسم بياني يحتوي على \( n \) رأسًا ولا يحتوي على رسم فرعي \( r \)-منتظم. لقد حظيت هذه الاستفسارات باهتمام كبير، خاصة عندما يتم التعامل مع \( r \) كعدد ثابت، وقد تم مناقشتها في أعمال بارزة مثل نصوص بولوباس وبوندي ومورتي.
توضح المقدمة أيضًا تطوير تقنيات جبرية مؤثرة في أوائل الثمانينيات من قبل ألون، فريدلاند، وكالاي، والتي أثبتت أن الرسوم البيانية ذات الدرجات المتوسطة القريبة من درجتها القصوى من المحتمل أن تحتوي على رسوم فرعية منتظمة بدرجة كبيرة. قدمت نتيجة بايبر في عام 1985 حدودًا قوية لشرط الدرجة المتوسطة الدنيا اللازمة لوجود رسم بياني \( r \)-منتظم، مشيرة إلى أن أي رسم بياني يحتوي على \( n \) رأسًا بمتوسط درجة يتجاوز \( 32r^2 \log n \) يجب أن يحتوي على مثل هذا الرسم الفرعي. ومع ذلك، تشير الورقة إلى أنه بينما تكون هذه النظرية دقيقة لـ \( r \) الثابت، فإنها تصبح أقل كفاءة مع زيادة \( r \). بالإضافة إلى ذلك، تذكر فرضية شفاتال بشأن شروط الدرجة المتوسطة للرسوم البيانية \( r \)-منتظمة، والتي تم دحضها في النهاية من خلال أمثلة من بايبر، رودل، وسيميريدي في عام 1995، مما يوضح أن الرسم البياني يمكن أن يحتوي على \( \Omega(n \log \log n) \) حواف دون احتواء رسم فرعي \( r \)-منتظم.
نقاش
في هذا القسم، يناقش المؤلفون التقدمات المهمة في دراسة الرسوم الفرعية المنتظمة داخل الرسوم البيانية الكثيفة، بناءً على النتائج السابقة التي قدمها رودل وويزوك وآخرون. يثبت النظرية 1.2 أنه لأي عدد صحيح $n$، يوجد رسم بياني يحتوي على $n$ رأسًا ومتوسط درجة لا تقل عن $c \log \log n$ يفتقر إلى رسم فرعي \( r \)-منتظم لـ \( r \geq 3 \). حددت أعمال رودل وويزوك اللاحقة عتبة للدرجة المتوسطة، موضحة أنه إذا تجاوزت $\gamma n$، فإن رسمًا فرعيًا \( r \)-منتظمًا موجود لبعض \( r \geq C\gamma^3 n \). يقوم المؤلفون بتحسين هذه الحدود، موضحين أنه لـ \( r < (\log n)^{1 - \Omega(1)} \)، فإن أدنى درجة \( d(r, n) \) المطلوبة لضمان وجود رسم فرعي \( r \)-منتظم هي \( \Theta(r^2 \log \log n) \)، بينما لـ \( r \geq \log n \)، هي \( \Theta(r \log(n/r)) \). تقدم الورقة أيضًا مفهوم الرسوم البيانية شبه المنتظمة، والتي تُعرف بأنها الرسوم البيانية التي تكون فيها الدرجة القصوى لا تزيد عن \( K \) مرات الدرجة الدنيا. يستفيد المؤلفون من ليمّا التنظيم لإردوش وسيمونوفيتس لإظهار أن أي رسم بياني يحتوي على حواف كافية يحتوي على رسم فرعي شبه منتظم \( K \). كما يوسعون هذا لإظهار أن الرسوم البيانية شبه المنتظمة يمكن أن تنتج رسومًا فرعية منتظمة بدرجات مشابهة، مما يعزز النتائج الحالية بشكل كبير. توفر النظريتان 1.13 و1.15 رؤى جديدة حول وجود الرسوم الفرعية المنتظمة في الرسوم البيانية ذات الدرجات المتوسطة والقصوى المضبوطة، مما يساهم في فهم بنية الرسوم البيانية الكثيفة ورسومها الفرعية المنتظمة.
DOI: https://doi.org/10.1090/tran/9694
Publication Date: 2026-01-15
Author(s): Zhenyun Du
Primary Topic: Limits and Structures in Graph Theory
Overview
In 1975, Erdős and Sauer posed a question regarding the maximum number of edges in an \( n \)-vertex graph that does not contain an \( r \)-regular subgraph. Recent advancements by Janzer and Sudakov established that such a graph can have at most \( C r n \log \log n \) edges, aligning with a previous lower bound by Pyber, Rödl, and Szemerédi. This paper extends their findings by proving that every \( n \)-vertex graph devoid of an \( r \)-regular subgraph can have at most \( C r^2 n \log \log n \) edges, thereby resolving the Erdős-Sauer problem up to an absolute constant for sufficiently large \( n \).
Additionally, the authors present tight bounds for a broader range of \( r \) values, with a notable transition occurring near \( r \approx \log n \). Specifically, they demonstrate that any \( n \)-vertex graph with an average degree of at least \( \min(C r \log(n/r), C r^2 \log \log n) \) must contain an \( r \)-regular subgraph. The bound \( C r \log(n/r) \) is tight for \( r \geq \log n \), while \( C r^2 \log \log n \) holds for \( r < (\log n)^{1 - \Omega(1)} \). These results address a problem posed by Rödl and Wysocka in 1997 for nearly all values of \( r \). The authors also enhance the Janzer-Sudakov framework by employing various algebraic techniques and introducing a novel random process that efficiently identifies nearly regular subgraphs in almost-regular graphs, contributing significantly to the field.
Introduction
The introduction of the paper addresses the significant problem of finding regular subgraphs with a specified degree in Graph Theory, highlighting its relevance to various theorems and applications in Combinatorics. The authors reference a pivotal question posed by Erdős and Sauer in 1975 regarding the maximum average degree of an \( n \)-vertex graph that does not contain an \( r \)-regular subgraph. This inquiry has garnered considerable attention, particularly when \( r \) is treated as a constant, and has been discussed in notable works such as Bollobás’s and Bondy and Murty’s texts.
The introduction further outlines the development of influential algebraic techniques in the early 1980s by Alon, Friedland, and Kalai, which established that graphs with average degrees close to their maximum degree are likely to contain regular subgraphs of significant degree. Pyber’s 1985 result provided strong bounds for the minimum average degree condition necessary for the existence of an \( r \)-regular graph, stating that any \( n \)-vertex graph with an average degree exceeding \( 32r^2 \log n \) must contain such a subgraph. However, the paper notes that while this theorem is tight for constant \( r \), it becomes less optimal as \( r \) increases. Additionally, it mentions Chvátal’s conjecture regarding average degree conditions for \( r \)-regular graphs, which was ultimately disproven by examples from Pyber, Rödl, and Szemerédi in 1995, illustrating that a graph can possess \( \Omega(n \log \log n) \) edges without containing an \( r \)-regular subgraph.
Discussion
In this section, the authors discuss significant advancements in the study of regular subgraphs within dense graphs, building on previous results by Rödl and Wysocka, and others. Theorem 1.2 establishes that for any integer $n$, there exists a graph with $n$ vertices and an average degree of at least $c \log \log n$ that lacks an $r$-regular subgraph for $r \geq 3$. Rödl and Wysocka’s subsequent work identified a threshold for the average degree, showing that if it exceeds $\gamma n$, then an $r$-regular subgraph exists for some $r \geq C\gamma^3 n$. The authors improve these bounds, demonstrating that for $r < (\log n)^{1 - \Omega(1)}$, the smallest degree $d(r, n)$ required to guarantee an $r$-regular subgraph is $\Theta(r^2 \log \log n)$, while for $r \geq \log n$, it is $\Theta(r \log(n/r))$. The paper also introduces the concept of almost-regular graphs, defined as graphs where the maximum degree is at most $K$ times the minimum degree. The authors leverage Erdős and Simonovits' regularization lemma to show that any graph with sufficient edges contains a $K$-almost-regular subgraph. They further extend this to demonstrate that almost-regular graphs can yield regular subgraphs with similar degrees, significantly enhancing existing results. Theorems 1.13 and 1.15 provide new insights into the existence of regular subgraphs in graphs with controlled average and maximum degrees, thereby contributing to the understanding of the structure of dense graphs and their regular subgraphs.