बड़े क्लिक्स ग्राफ़ में निषिद्ध अर्ध-प्रेरित संरचनाओं के साथ

मूल जानकारी

• पेपर ID: 2511.13073
• शीर्षक: Large cliques in graphs with forbidden semi-induced structures
• लेखक: Nannan Chen (शेडोंग विश्वविद्यालय & IBS), Yulai Ma (नानकाई विश्वविद्यालय), Fan Yang (शेडोंग विश्वविद्यालय & IBS)
• वर्गीकरण: math.CO (संयोजन विज्ञान)
• प्रस्तुति समय: 17 नवंबर 2025
• पेपर लिंक: https://arxiv.org/abs/2511.13073

सारांश

यह पेपर निषिद्ध अर्ध-प्रेरित उप-संरचनाओं वाले ग्राफ़ में बड़े क्लिक्स के अस्तित्व की समस्या का अध्ययन करता है। होल्मसेन ने 2022 में सिद्ध किया कि कम से कम $c\binom{n}{r}$ $r$-क्लिक्स युक्त कोई भी ग्राफ़ जिसमें प्रेरित पूर्ण $r$-भाग ग्राफ़ $K_{2,\ldots,2}$ नहीं है, आवश्यक रूप से $Ω(c^{2^{r-1}}n)$ क्रम का एक क्लिक रखता है। यह पेपर $K_{2,\ldots,2}$ से संबंधित अर्ध-प्रेरित उप-संरचनाओं को निषिद्ध करके, सिद्ध करता है कि कम से कम $c\binom{n}{r}$ $K_r$ प्रतियों वाला प्रत्येक $n$ शीर्ष ग्राफ़ $G$ आवश्यक रूप से $Ω(cn)$ क्रम का एक क्लिक रखता है। यह परिणाम होल्मसेन सीमा में $c$ की निर्भरता को $c^{2^{r-1}}$ से $c$ के संबंध में रैखिक तक सुधारता है, और केवल सीमित संख्या में संरचनाओं को निषिद्ध करने की आवश्यकता है। इसके अतिरिक्त, यह विधि स्वाभाविक रूप से VC आयाम की अवधारणा से जुड़ी है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

1. शास्त्रीय तुरान सिद्धांत: तुरान प्रमेय और इसके सामान्यीकरण (एर्डोस-स्टोन-सिमोनोविट्स प्रमेय) गैर-प्रेरित उप-ग्राफ़ को निषिद्ध करने की चरम समस्याओं का अध्ययन करते हैं। रंग संख्या $χ(H) ≥ 3$ वाले ग्राफ़ $H$ के लिए, $H$ को उप-ग्राफ़ के रूप में निषिद्ध करने से चरम ग्राफ़ स्पर्शोन्मुख रूप से $(χ(H)-1)$-भाग ग्राफ़ बन जाता है, जिससे क्लिक संख्या स्थिरांक द्वारा सीमित होती है।
2. प्रेरित उप-ग्राफ़ का मामला: जब प्रेरित उप-ग्राफ़ को निषिद्ध किया जाता है, तो स्थिति पूरी तरह से भिन्न होती है। ग्यारफास, हुबेंको और सोलिमोसी (2002) ने सिद्ध किया कि यदि $n$ शीर्ष ग्राफ़ $G$ में कम से कम $c\binom{n}{2}$ किनारे हैं और प्रेरित $K_{2,2}$ नहीं है, तो $ω(G) ≥ \frac{c^2}{10}n$।
3. कॉर्डल ग्राफ़ की सटीक सीमा: कॉर्डल ग्राफ़ (लंबाई कम से कम 4 के प्रेरित चक्र को निषिद्ध करते हैं) बेहतर सीमा प्राप्त करते हैं: $ω(G) ≥ (1-\sqrt{1-c})n$, जब $c$ छोटा हो तो $Ω(cn)$।
4. होल्मसेन का सामान्यीकरण: होल्मसेन (2020) ने $K_{2,2}$ मामले को बहु-भाग संस्करण तक सामान्यीकृत किया, सिद्ध किया कि प्रेरित $K_r[2]$ ($K_r$ का 2-विस्तार) को निषिद्ध करने वाले ग्राफ़ में $Ω(c^{2^{r-1}}n)$ क्रम का क्लिक है।

अनुसंधान प्रेरणा

यद्यपि होल्मसेन का परिणाम $n$ के संबंध में रैखिक है, लेकिन इसकी $c$ की सीमा $r$ के साथ बढ़ने पर तेजी से बिगड़ जाती है। इस पेपर का मूल प्रश्न है: क्या प्रमेय 1.1 से प्रमेय 1.2 तक के सुधार के समान, अधिक (लेकिन सीमित संख्या में) संरचनाओं को निषिद्ध करके होल्मसेन सीमा में सुधार किया जा सकता है?

महत्व

• यह समस्या चरम ग्राफ़ सिद्धांत को अमूर्त हेली प्रमेय से जोड़ती है
• प्रेरित उप-ग्राफ़ निषेध शर्तों और क्लिक संख्या के संबंध को समझने के लिए मौलिक है
• ग्राफ़ संरचना में VC आयाम की भूमिका को प्रकट करता है

मुख्य योगदान

1. मुख्य प्रमेय: सिद्ध किया कि कम से कम $c\binom{n}{r}$ $K_r$ प्रतियों वाले प्रेरित $K_r^{[2]}$-मुक्त ग्राफ़ $G$ के लिए, $ω(G) ≥ \frac{c}{18r}n$ (प्रमेय 1.5)
2. सीमा में सुधार: होल्मसेन की $Ω(c^{2^{r-1}}n)$ सीमा को $Ω(cn)$ तक सुधारा, $c$ में रैखिक निर्भरता प्राप्त की
3. सीमित निषिद्ध संरचनाएं: केवल अधिकतम $2^{\binom{r}{2}}$ प्रेरित उप-संरचनाओं को निषिद्ध करने की आवश्यकता है (कॉर्डल ग्राफ़ के अनंत के विपरीत)
4. VC आयाम विधि: अर्ध-प्रेरित उप-ग्राफ़ और VC आयाम के बीच स्वाभाविक संबंध स्थापित किया, मौजूदा द्वि-प्रेरित उप-ग्राफ़ सिद्धांत को सामान्यीकृत किया
5. संरचनात्मक अंतर्दृष्टि: प्रकट किया कि कॉर्डल ग्राफ़ की तुलना में कहीं कम संरचनाओं को निषिद्ध करने के बावजूद, रैखिक आकार के क्लिक की गारंटी दी जा सकती है

विधि विस्तार

कार्य परिभाषा

इनपुट: $n$ शीर्ष ग्राफ़ $G$, संतुष्ट करता है:

• कम से कम $c\binom{n}{r}$ $K_r$ प्रतियां रखता है ($c > 0$ स्थिरांक है)
• प्रेरित $K_r^{[2]}$-मुक्त (प्रेरित उप-ग्राफ़ के रूप में $K_r^{[2]}$ में कोई भी ग्राफ़ नहीं है)

आउटपुट: सिद्ध करें कि $G$ कम से कम $\frac{c}{18r}n$ क्रम का क्लिक रखता है

मुख्य परिभाषाएं:

• $K_r[2]$: $K_r$ का 2-विस्तार, प्रत्येक शीर्ष को आकार 2 के स्वतंत्र समुच्चय से प्रतिस्थापित करता है
• $K_r^{[2]}$: $K_r[2]$ के उप-ग्राफ़ का परिवार, जिसके किनारे समुच्चय $(E(K_r[2])\backslash E(K_{U'})) \cup E'$ के रूप में हैं, जहां $U' = \{u'_1, \ldots, u'_r\}$ प्रत्येक भाग का दूसरा शीर्ष समुच्चय है, $E' \subseteq E(K_{U'})$

मुख्य आर्किटेक्चर

यह पेपर तीन मुख्य चरणों में विभाजित है:

1. VC आयाम सीमा (दावा 2.3)

मुख्य लेम्मा: प्रेरित $K_r^{[2]}$-मुक्त ग्राफ़ के अधिकतम क्लिक समुच्चय $MC(G)$ का VC आयाम अधिकतम $r-1$ है।

प्रमाण विचार:

• मान लीजिए कि आकार $r$ का समुच्चय $S = \{u_1, \ldots, u_r\}$ $MC(G)$ द्वारा विखंडित है
• प्रत्येक $i \in [r]$ के लिए, एक अधिकतम क्लिक $K_i$ मौजूद है जैसे कि $K_i \cap S = S \backslash \{u_i\}$
• अधिकतमता से, $u'_i \in K_i \backslash S$ मौजूद है जैसे कि $u_i u'_i \notin E(G)$
• तब $\{u_1, u'_1, \ldots, u_r, u'_r\}$ $K_r^{[2]}$ में किसी ग्राफ़ को प्रेरित करता है, विरोधाभास

2. सॉयर-शेलाह लेम्मा का अनुप्रयोग

VC आयाम $k$ वाले समुच्चय प्रणाली $\mathcal{F}$ के लिए, आकार $m$ के किसी भी समुच्चय $S$ को संतुष्ट करता है: $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

इस पेपर के मामले के लिए, $k = r-1$, $m = \lfloor\frac{9r}{c}\rfloor$ चुनते हैं, प्राप्त करते हैं: $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. संभाव्यता तर्क

विरोधाभास द्वारा: मान लीजिए $ω(G) < c'n$, जहां $c' = \frac{c}{18r}$

यादृच्छिक चयन: $V(G)$ में से $S_r \subseteq S_m$ यादृच्छिक रूप से चुनें, जहां $|S_r| = r$, $|S_m| = m$

संभाव्यता विश्लेषण:

• $S_r$ क्लिक को प्रेरित करने की संभावना कम से कम $c$ है
• यदि $S_r$ क्लिक को प्रेरित करता है और आकार $< c'n$ के अधिकतम क्लिक $K$ में समाहित है, तो $S_m$ में $S_r$ है लेकिन $S_m \backslash S_r$ में $K$ के किसी भी शीर्ष को नहीं रखने की संभावना कम से कम है: $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• इसलिए $S_r = S_m \cap K$ की संभावना कम से कम $\frac{1}{4}c$ है
• शर्त को संतुष्ट करने वाले $S_r$ की अपेक्षित संख्या कम से कम $\frac{1}{4}c\binom{m}{r}$ है

विरोधाभास: यह सॉयर-शेलाह लेम्मा द्वारा दी गई ऊपरी सीमा के साथ विरोधाभास है।

तकनीकी नवाचार बिंदु

1. अर्ध-प्रेरित संरचनाओं का परिचय: $K_r^{[2]}$ परिवार संरचना सीमा की शक्ति और संख्या को कुशलतापूर्वक संतुलित करता है, पर्याप्त बाधा सुनिश्चित करते हुए सीमित निषिद्ध संरचनाओं को बनाए रखता है
2. VC आयाम का स्वाभाविक संबंध: अधिकतम क्लिक प्रणाली के VC आयाम को ग्राफ़ की प्रेरित उप-संरचनाओं से सीधे जोड़ता है, विश्लेषण के लिए नया दृष्टिकोण प्रदान करता है
3. सूक्ष्म संभाव्यता अनुमान: यादृच्छिक चयन ढांचे में, सावधानीपूर्वक संभाव्यता गणना के माध्यम से क्लिक घनत्व और क्लिक आकार के बीच मात्रात्मक संबंध स्थापित करता है
4. पैरामीटर अनुकूलन: $m = \lfloor\frac{9r}{c}\rfloor$ चुनता है ताकि सॉयर-शेलाह सीमा और संभाव्यता निचली सीमा विरोधाभास उत्पन्न करें

प्रायोगिक सेटअप

यह पेपर शुद्ध सैद्धांतिक गणित पेपर है, प्रायोगिक सत्यापन में शामिल नहीं है। सभी परिणाम कठोर गणितीय प्रमाण के माध्यम से प्राप्त होते हैं।

सैद्धांतिक सत्यापन

• चरम उदाहरण: $r=2$ मामले के लिए, पेपर इंगित करता है कि प्रेरित $K_2^{[2]}$-मुक्त ग्राफ़ (प्रेरित $P_4$ और $K_{2,2}$ को निषिद्ध करते हैं) कॉर्डल ग्राफ़ का उप-वर्ग बनाते हैं
• कसापन विश्लेषण: यद्यपि सटीक चरम ग्राफ़ निर्माण नहीं दिया गया है, लेकिन सीमा की मात्रा को उचित साबित किया गया है

प्रायोगिक परिणाम

मुख्य सैद्धांतिक परिणाम

प्रमेय 1.5 (मुख्य परिणाम): $r ≥ 2$, $0 < c < 1$ को सेट करें, $G$ कम से कम $c\binom{n}{r}$ $K_r$ प्रतियों वाला $n$ शीर्ष ग्राफ़ है। यदि $G$ प्रेरित $K_r^{[2]}$-मुक्त है, तो पर्याप्त बड़े $n$ के लिए, $ω(G) ≥ \frac{c}{18r}n$

मौजूदा परिणामों के साथ तुलना

मुख्य सुधार

1. घातांक से रैखिक: $c$ की निर्भरता $c^{2^{r-1}}$ से $c/r$ तक सुधारी गई
   • जब $r=3$, $c^4$ से $c/3$ तक सुधार
   • जब $r=5$, $c^{16}$ से $c/5$ तक सुधार
2. सीमित संरचना संख्या: केवल $2^{\binom{r}{2}}$ संरचनाओं को निषिद्ध करने की आवश्यकता है
   • $r=2$: 2 संरचनाएं
   • $r=3$: 8 संरचनाएं
   • $r=4$: 64 संरचनाएं
3. इष्टतमता: $r=2$ के लिए, यह पेपर परिणाम कॉर्डल ग्राफ़ सीमा के साथ मात्रा में सुसंगत है (दोनों $Ω(cn)$ हैं), लेकिन कम संरचनाओं को निषिद्ध करता है

संबंधित कार्य

शास्त्रीय चरम ग्राफ़ सिद्धांत

1. तुरान प्रमेय (1941): $ex(n, K_k)$ के सटीक मान और चरम ग्राफ़ निर्धारित करता है
2. एर्डोस-स्टोन-सिमोनोविट्स प्रमेय (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • गैर-द्विभाजक ग्राफ़ $H$ के लिए, स्पर्शोन्मुख व्यवहार पूरी तरह से हल करता है
   • द्विभाजक ग्राफ़ के लिए, केवल $ex(n,H) = o(n^2)$ देता है

प्रेरित उप-ग्राफ़ का चरम सिद्धांत

3. ग्यारफास-हुबेंको-सोलिमोसी (2002):
   • प्रेरित $K_{2,2}$-मुक्त ग्राफ़: $ω(G) ≥ \frac{c^2}{10}n$
   • $C_4$-मुक्त ग्राफ़ (कॉर्डल ग्राफ़): $ω(G) ≥ (1-\sqrt{1-c})n$
4. एबॉट-कैचलस्की (1979): कॉर्डल ग्राफ़ की सटीक सीमा स्वतंत्र रूप से सिद्ध करते हैं
5. लोह एट अल. (2018): प्रेरित $K_{2,t}$-मुक्त ग्राफ़ तक परिणाम सामान्यीकृत करते हैं
6. होल्मसेन (2020):
   • अतिग्राफ़ और बहु-भाग संस्करण तक सामान्यीकृत करता है
   • सिद्ध करता है कि अमूर्त रंगीन हेली अमूर्त आंशिक हेली को निहित करता है
   • यह पेपर होल्मसेन के ग्राफ़ सिद्धांत परिणाम को सीधे सुधारता है

ग्राफ़ सिद्धांत में VC आयाम का अनुप्रयोग

7. न्गुयेन-स्कॉट-सेमोर (2025): द्वि-प्रेरित उप-ग्राफ़ घनत्व और VC आयाम के बीच संबंध स्थापित करते हैं
8. सॉयर (1972), शेलाह (1972): स्वतंत्र रूप से VC आयाम की मौलिक सीमा सिद्ध करते हैं (सॉयर-शेलाह लेम्मा)

इस पेपर की स्थिति

यह पेपर होल्मसेन के कार्य के आधार पर, अर्ध-प्रेरित उप-संरचनाओं और VC आयाम विधि को पेश करके, मात्रात्मक सुधार प्राप्त करता है। कॉर्डल ग्राफ़ सिद्धांत के साथ संबंध $r=2$ मामले के लिए स्वाभाविक व्याख्या प्रदान करता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. मात्रात्मक सुधार: $K_r^{[2]}$ परिवार को निषिद्ध करके (अधिकतम $2^{\binom{r}{2}}$ संरचनाएं), क्लिक संख्या निचली सीमा को $Ω(c^{2^{r-1}}n)$ से $Ω(cn)$ तक सुधारता है
2. पद्धति संबंधी योगदान: अर्ध-प्रेरित उप-ग्राफ़ और VC आयाम के बीच स्वाभाविक संबंध स्थापित करता है, मौजूदा सैद्धांतिक ढांचे को सामान्यीकृत करता है
3. संरचनात्मक अंतर्दृष्टि: प्रकट करता है कि सीमित संरचना निषेध शर्तें रैखिक आकार के क्लिक की गारंटी देने के लिए पर्याप्त हैं, कॉर्डल ग्राफ़ की तरह अनंत संरचनाओं को निषिद्ध किए बिना

सीमाएं

1. स्थिरांक कारक: सीमा में स्थिरांक $\frac{1}{18r}$ इष्टतम नहीं हो सकता है, पेपर इसकी कसापन पर चर्चा नहीं करता है
2. निषिद्ध संरचना संख्या: यद्यपि सीमित है, लेकिन $2^{\binom{r}{2}}$ $r$ के साथ घातीय रूप से बढ़ता है, जब $r$ बड़ा हो तो अभी भी बहुत है
3. चरम निर्माण की कमी: पेपर निचली सीमा तक पहुंचने वाले चरम ग्राफ़ निर्माण प्रदान नहीं करता है
4. स्पर्शोन्मुख गुण: परिणाम के लिए $n$ पर्याप्त बड़ा होना आवश्यक है, विशिष्ट सीमा स्पष्ट नहीं है

भविष्य की दिशाएं

पेपर निष्कर्ष भाग में स्पष्ट रूप से खुली समस्याएं प्रस्तुत करता है:

मुख्य प्रश्न: $c^{2^{r-1}}$ से $c$ की रैखिक निर्भरता में परिवर्तन कब होता है? अधिक सटीक रूप से, $c$ में रैखिक सीमा को बाध्य करने के लिए आवश्यक न्यूनतम निषिद्ध संरचना संख्या क्या है?

संभावित अनुसंधान दिशाएं:

1. रैखिक सीमा प्राप्त करने के लिए न्यूनतम निषिद्ध संरचना परिवार निर्धारित करना
2. स्थिरांक कारक $\frac{1}{18r}$ में सुधार करना
3. चरम उदाहरण निर्माण या सीमा की कसापन सिद्ध करना
4. अतिग्राफ़ मामले तक सामान्यीकरण
5. अन्य अर्ध-प्रेरित संरचनाओं के निषेध शर्तों की खोज

गहन मूल्यांकन

लाभ

1. महत्वपूर्ण मात्रात्मक सुधार:
   • घातीय निर्भरता को रैखिक में सुधारना वास्तविक प्रगति है
   • अनुप्रयोगों के लिए (जैसे अमूर्त हेली प्रमेय) महत्वपूर्ण है
2. सुरुचिपूर्ण प्रमाण तकनीक:
   • VC आयाम विधि एकीकृत विश्लेषण ढांचा प्रदान करती है
   • संभाव्यता तर्क सरल और शक्तिशाली है
   • प्रमाण पूरी तरह से आत्मनिर्भर है, केवल मौलिक उपकरणों पर निर्भर है
3. अवधारणात्मक नवाचार:
   • $K_r^{[2]}$ परिवार की परिभाषा बाधा शक्ति और संख्या को कुशलतापूर्वक संतुलित करती है
   • अर्ध-प्रेरित संरचनाओं का परिचय स्वाभाविक सामान्यीकरण है
4. स्पष्ट लेखन:
   • प्रेरणा पूरी तरह से समझाई गई है
   • तकनीकी विवरण पूर्ण है
   • मौजूदा कार्य के साथ संबंध स्पष्ट है
5. सैद्धांतिक गहराई:
   • प्रेरित उप-ग्राफ़ सिद्धांत की गहरी संरचना प्रकट करता है
   • कई गणितीय शाखाओं को जोड़ता है (चरम ग्राफ़ सिद्धांत, VC आयाम सिद्धांत, संयोजक ज्यामिति)

कमियां

1. स्थिरांक अनुकूलन:
   • $\frac{1}{18r}$ स्थिरांक पर्याप्त सूक्ष्म नहीं हो सकता है
   • सीमा की कसापन पर चर्चा नहीं की गई है या मेल खाने वाली ऊपरी सीमा निर्माण प्रदान नहीं किया गया है
2. संरचना संख्या की निर्भरता:
   • $2^{\binom{r}{2}}$ अभी भी $r$ के साथ तेजी से बढ़ता है
   • यह अन्वेषण नहीं किया गया है कि क्या कम निषिद्ध संरचनाओं के साथ समान परिणाम प्राप्त किए जा सकते हैं
3. विशिष्ट सीमा की कमी:
   • "पर्याप्त बड़ा $n$" परिमाणित नहीं है
   • व्यावहारिक अनुप्रयोगों को प्रभावित कर सकता है
4. सामान्यीकरण चर्चा अपर्याप्त:
   • विधि अन्य निषिद्ध संरचनाओं पर लागू हो सकती है या नहीं, यह चर्चा नहीं की गई है
   • अतिग्राफ़ मामले के साथ संबंध केवल परिचय में उल्लेख किया गया है
5. खुली समस्याओं की विशिष्टता:
   • यद्यपि महत्वपूर्ण समस्याएं प्रस्तुत की गई हैं, लेकिन अनुमान या आंशिक परिणाम नहीं दिए गए हैं

प्रभाव मूल्यांकन

सैद्धांतिक प्रभाव:

• प्रेरित उप-ग्राफ़ चरम सिद्धांत के लिए नए उपकरण प्रदान करता है
• VC आयाम विधि अधिक अनुप्रयोग को प्रेरित कर सकती है
• अमूर्त हेली प्रमेय अनुसंधान में सीधा योगदान

व्यावहारिक मूल्य:

• मुख्य रूप से सैद्धांतिक प्रकृति का है
• एल्गोरिथ्मिक ग्राफ़ सिद्धांत और कम्प्यूटेशनल ज्यामिति में अनुप्रयोग मिल सकते हैं

पुनरुत्पादनीयता:

• प्रमाण पूरी तरह से सत्यापन योग्य है
• कम्प्यूटेशनल प्रयोग शामिल नहीं है

संभावित उद्धरण मूल्य:

• चरम संयोजन विज्ञान क्षेत्र में उच्च उद्धरण की अपेक्षा है
• इस दिशा का मानक संदर्भ बन सकता है

लागू परिदृश्य

1. सैद्धांतिक अनुसंधान:
   • प्रेरित उप-ग्राफ़ निषेध की चरम समस्याएं
   • संयोजक संरचनाओं में VC आयाम का अनुप्रयोग
   • अमूर्त हेली प्रमेय और इसके सामान्यीकरण
2. संबंधित समस्याएं:
   • अन्य अर्ध-प्रेरित संरचनाओं का अनुसंधान
   • क्लिक संख्या और अन्य ग्राफ़ पैरामीटर के बीच संबंध
   • यादृच्छिक ग्राफ़ में क्लिक संरचना
3. संभावित अनुप्रयोग:
   • एल्गोरिथ्म डिजाइन (संरचनात्मक गुणों का उपयोग करके)
   • कम्प्यूटेशनल जटिलता सिद्धांत
   • संयोजक अनुकूलन समस्याएं

संदर्भ

पेपर निम्नलिखित मुख्य साहित्य का उद्धरण देता है:

1. एबॉट और कैचलस्की (1979): अंतराल ग्राफ़ की तुरान-प्रकार समस्याएं
2. एर्डोस और सिमोनोविट्स (1966), एर्डोस और स्टोन (1946): ESS प्रमेय
3. ग्यारफास, हुबेंको और सोलिमोसी (2002): $C_4$-मुक्त ग्राफ़ में बड़े क्लिक्स
4. होल्मसेन (2020): अतिग्राफ़ में निषिद्ध उप-संरचनाओं के साथ बड़े क्लिक्स (यह पेपर सीधे सुधारता है)
5. लोह एट अल. (2018): प्रेरित तुरान संख्याएं
6. न्गुयेन, स्कॉट और सेमोर (2025): प्रेरित उप-ग्राफ़ घनत्व और VC आयाम
7. सॉयर (1972), शेलाह (1972): VC आयाम की मौलिक सीमा
8. तुरान (1941): शास्त्रीय तुरान प्रमेय

समग्र मूल्यांकन: यह चरम ग्राफ़ सिद्धांत की महत्वपूर्ण समस्या पर वास्तविक प्रगति प्राप्त करने वाला उच्च गुणवत्ता का संयोजन गणित पेपर है। अर्ध-प्रेरित संरचनाओं और VC आयाम विधि को पेश करके, लेखकों ने होल्मसेन की घातीय सीमा को रैखिक सीमा तक सफलतापूर्वक सुधारा है, जबकि निषिद्ध संरचना संख्या की सीमितता बनाए रखी है। प्रमाण तकनीक सुरुचिपूर्ण है और अंतर्दृष्टि से भरपूर है, इस क्षेत्र के लिए नए अनुसंधान उपकरण और दिशाएं प्रदान करता है। पेपर का मुख्य योगदान सैद्धांतिक स्तर पर है, लेकिन इसकी विधि और विचार संबंधित क्षेत्रों पर व्यापक प्रभाव डाल सकते हैं।