Lévy family of graphs
ग्राफ सिद्धांत में, गणित की एक शाखा, ग्राफ का एक लेवी परिवार ग्राफ Gn, n = 1,2,3, का एक परिवार है, जिसमें एक निश्चित प्रकार की "सघनता" या "उलझन" होती है। ग्राफ के कई प्राकृतिक रूप से पाए जाने वाले परिवार लेवी परिवार हैं। कई गणितविदों ने इस तथ्य को नोट किया है और आश्चर्य व्यक्त किया है कि ऐसा प्रतीत होता है कि इसकी कोई तैयार व्याख्या नहीं है। औपचारिक रूप से, ग्राफ का एक परिवार Gn, n = 1,2,3,., एक लेवी परिवार है यदि, किसी भी जगह के लिए यहाँ D, G का ग्राफ व्यास है, और A (n), A का n-ग्राफ पड़ोस है। ध्यान दें कि अधिकतमकरण जी के उपसमुच्चय ए पर होता है, ए के जी के आधे आकार से अधिक होने के अधीन शब्दों में, इसका मतलब है कि कोई जी के कम से कम आधे आकार का उपसमुच्चय ले सकता है, और इसे केवल ग्राफ व्यास से उड़ा सकता है, और लगभग सभी सेट के साथ समाप्त हो सकता है। लंबा "कठोर" (अर्थात। "कॉम्पैक्ट" नहीं) ग्राफ के परिवारों जैसे कि क्रम n के चक्र ग्राफ में स्पष्ट रूप से ऐसा कोई गुण नहीं हैः कोई भी एक उपसमुच्चय पर विचार कर सकता है जिसमें एक बिंदु का n/2 पड़ोस (मध्यरात्रि से छह बजे तक, मान लीजिए) शामिल हो। ग्राफ का व्यास डी लगभग एन/2 है। तो सबसेट का-पड़ोसी केवल आकार का है लगभग n/2। एक लेवी परिवार के पास लगभग पूरे सेट को कवर करने वाला यह पड़ोस होगा। यह स्पष्ट होना चाहिए कि एक लेवी परिवार में एक बहुत ही विशेष प्रकार की सघन संरचना होनी चाहिए। एन क्रम के हाइपरक्यूब ग्राफ को लेवी परिवार के रूप में जाना जाता है। यदि एस. एन. वह ग्राफ है जिसमें ऐसे बिंदु हैं जो एन तत्वों के क्रमपरिवर्तन समूह के तत्व हैं, जिनके किनारे उन बिंदुओं को जोड़ते हैं जो एक स्थानांतरण से भिन्न होते हैं, तो श्रृंखला सी, आई = 1,2, एक लेवी परिवार है। संदर्भ बोलोबास (संपादक)। संभावित संयोजन और इसके अनुप्रयोग। अमेरिकन मैथमेटिकल सोसाइटी, 1991 (पी63) ग्राफ परिवार