Lévy family of graphs
গ্রাফ তত্ত্বে, গণিতের একটি শাখা, গ্রাফের একটি লেভি পরিবার হল Gn, n = 1,2,3, গ্রাফের একটি পরিবার, যা একটি নির্দিষ্ট ধরনের "কম্প্যাক্টনেস" বা "ট্যাঙ্গলনেস" ধারণ করে। গ্রাফের অনেক প্রাকৃতিক পরিবার হল লেভি পরিবার। অনেক গণিতবিদ এই সত্যটি লক্ষ্য করেছেন এবং বিস্ময় প্রকাশ করেছেন যে এর কোনও প্রস্তুত ব্যাখ্যা আছে বলে মনে হয় না। আনুষ্ঠানিকভাবে, গ্রাফের একটি পরিবার Gn, n = 1,2,3,., একটি লেভি পরিবার হয় যদি, যে কোনও জায়গার জন্য এখানে D হল G-এর গ্রাফ ব্যাস, এবং A (n) হল A-এর এন-গ্রাফ প্রতিবেশী। লক্ষ্য করুন যে সর্বাধিককরণটি জি-এর উপসেট এ-এর উপর নির্ভর করে, যার সাপেক্ষে এ-এর আকার জি-এর অর্ধেকের বেশি। লম্বা "স্ট্রিং" (অর্থাৎ। "কম্প্যাক্ট" নয়) ক্রম n-এর চক্র গ্রাফের মতো গ্রাফের পরিবারগুলির স্পষ্টভাবে এই ধরনের কোনও বৈশিষ্ট্য নেইঃ একটি বিন্দুর n/2 পার্শ্ববর্তী (মধ্যরাত থেকে ছয়টা পর্যন্ত, ধরুন) সমন্বিত একটি উপসেট বিবেচনা করা যেতে পারে। গ্রাফের ব্যাস D প্রায় n/2। সুতরাং উপসেটটির-প্রতিবেশীত্ব শুধুমাত্র আকারের প্রায় n/2। একটি লেভি পরিবারের প্রায় সমস্ত সেট জুড়ে এই পাড়াটি থাকবে। এটা স্পষ্ট হওয়া উচিত যে একটি লেভি পরিবারের অবশ্যই একটি বিশেষ ধরনের কম্প্যাক্ট কাঠামো থাকতে হবে। অর্ডার এন-এর হাইপারকিউব গ্রাফগুলি একটি লেভি পরিবার হিসাবে পরিচিত। যদি এস. এন হল এমন একটি গ্রাফ যার বিন্দুগুলি এন উপাদানগুলির ক্রমবিকাশ গোষ্ঠীর উপাদান, যার প্রান্তগুলি একটি স্থানান্তর দ্বারা পৃথক বিন্দুতে যোগদান করে, তবে সিরিজ সি, আই = 1,2, একটি লেভি পরিবার। তথ্যসূত্র বোলোবাস (সম্পাদক)। সম্ভাব্য সমন্বয়বিদ্যা এবং এর প্রয়োগ। আমেরিকান ম্যাথমেটিকাল সোসাইটি, 1991 (পৃ. 63) গ্রাফ পরিবার