Colin de Verdière graph invariant
কলিন ডি ভার্ডিয়েরের অপরিবর্তনীয় হল যে কোনও গ্রাফ জি-এর জন্য একটি গ্রাফ পরামিতি, যা 1990 সালে ইভস কলিন ডি ভার্ডিয়ের দ্বারা প্রবর্তিত হয়েছিল। এটি নির্দিষ্ট শ্রোডিঙ্গার অপারেটরদের দ্বিতীয় আইগেনভ্যালু সর্বাধিক বহুগুণের অধ্যয়নের দ্বারা অনুপ্রাণিত হয়েছিল। সংজ্ঞা ধরা যাক ভার্টেক্স সেট সহ একটি লুপহীন সহজ গ্রাফ। তারপর যে কোনও প্রতিসম ম্যাট্রিক্সের বৃহত্তম কোর্যাঙ্কটি এমন যেঃ (এম1) সহ সকলের জন্যঃ যদি, এবং যদি; (এম2)-এর গুণিতক 1-এর ঠিক একটি ঋণাত্মক আইগেনভ্যালু রয়েছে; (এম3) এমন কোনও শূন্যেতর ম্যাট্রিক্স নেই যা এবং যদি হয় বা ধরে রাখে। পরিচিত গ্রাফ পরিবারের বৈশিষ্ট্য গ্রাফের বেশ কয়েকটি সুপরিচিত পরিবারকে তাদের কলিন ডি ভার্ডিয়ের অপরিবর্তনীয়তার পরিপ্রেক্ষিতে চিহ্নিত করা যেতে পারেঃ যদি এবং শুধুমাত্র যদি জি-এর কোনও প্রান্ত না থাকে; যদি এবং শুধুমাত্র যদি জি একটি রৈখিক বন (পথের একটি বিচ্ছিন্ন মিলন) হয়; যদি এবং শুধুমাত্র যদি জি বাইরের সমতলীয় হয়; যদি এবং শুধুমাত্র যদি জি সমতল হয়; যদি এবং শুধুমাত্র যদি জি আর 3-এ সংযোগহীনভাবে এম্বেডযোগ্য হয়। গ্রাফের এই একই পরিবারগুলি একটি গ্রাফের কলিন ডি ভার্ডিয়ের অপরিবর্তনীয় এবং তার পরিপূরক কাঠামোর মধ্যে সংযোগেও প্রদর্শিত হয়ঃ যদি একটি এন-ভার্টেক্স গ্রাফের পরিপূরক একটি রৈখিক বন হয়, তাহলে; যদি একটি এন-ভার্টেক্স গ্রাফের পরিপূরক বাইরের সমতলীয় হয়, তাহলে; যদি একটি এন-ভার্টেক্স গ্রাফের পরিপূরক সমতলীয় হয়, তাহলে। গ্রাফ মাইনর একটি গ্রাফের মাইনর হল প্রান্তগুলি সঙ্কুচিত করে এবং প্রান্ত এবং শীর্ষগুলি মুছে দিয়ে এটি থেকে গঠিত আরেকটি গ্রাফ। কলিন ডি ভার্ডিয়ের অপরিবর্তনীয় হল মাইনর-মনোটোন, যার অর্থ একটি গ্রাফের একটি মাইনর নেওয়া কেবল তার অপরিবর্তনীয়কে হ্রাস করতে বা অপরিবর্তিত রাখতে পারেঃ যদি এইচ জি-এর মাইনর হয়। রবার্টসন-সেমুর উপপাদ্য অনুসারে, প্রতিটি কে-এর জন্য গ্রাফের একটি সীমাবদ্ধ সেট এইচ রয়েছে যাতে সর্বাধিক কে-তে অপরিবর্তনীয় গ্রাফগুলি সেই গ্রাফগুলির মতোই হয় যেখানে এইচ-এর কোনও সদস্য মাইনর হিসাবে থাকে না। নিষিদ্ধ অপ্রাপ্তবয়স্কদের এই সেটগুলি কে ≤ 3-এর জন্য তালিকাভুক্ত করে; কে = 4-এর জন্য নিষিদ্ধ অপ্রাপ্তবয়স্কদের সেটটি পিটারসেন পরিবারের সাতটি গ্রাফ নিয়ে গঠিত, লিঙ্কহীনভাবে এম্বেডযোগ্য গ্রাফগুলির দুটি বৈশিষ্ট্যের কারণে যা মাইক্রো ≤ 4 সহ গ্রাফ হিসাবে এবং পিটারসেন পরিবার মাইনর ছাড়া গ্রাফ হিসাবে। কে = 5 এর জন্য নিষিদ্ধ অপ্রাপ্তবয়স্কদের সেটটিতে হিউড পরিবারের 78 টি গ্রাফ অন্তর্ভুক্ত রয়েছে এবং এটি অনুমান করা হয় যে আর নেই। ক্রোমাটিক সংখ্যা অনুমান করে যে কলিন ডি ভার্ডিয়ের অপরিবর্তনীয় মাইক্রো সহ যে কোনও গ্রাফ সর্বাধিক মাইক্রো + 1 রঙে রঙিন হতে পারে। উদাহরণস্বরূপ, রৈখিক বনগুলির অপরিবর্তনীয় 1 রয়েছে এবং 2-রঙের হতে পারে; বাইরের সমতলীয় গ্রাফগুলির অপরিবর্তনীয় দুটি রয়েছে এবং 3-রঙের হতে পারে; সমতলীয় গ্রাফগুলির অপরিবর্তনীয় 3 রয়েছে এবং (চার রঙের উপপাদ্য অনুসারে) 4-রঙের হতে পারে। সর্বাধিক চারটি অপরিবর্তনীয় কলিন ডি ভার্ডিয়ের গ্রাফের জন্য, অনুমানটি সত্য থাকে; এগুলি লিঙ্কহীনভাবে এম্বেডযোগ্য গ্রাফ এবং তাদের সর্বাধিক পাঁচটি ক্রোমাটিক সংখ্যা থাকার বিষয়টি কে6-মাইনর-মুক্ত গ্রাফের জন্য হ্যাডউইগার অনুমানের প্রমাণের ফল। অন্যান্য বৈশিষ্ট্য যদি একটি গ্রাফের ক্রসিং নম্বর থাকে, তবে এটিতে সর্বাধিক কলিন ডি ভার্ডিয়ের অপরিবর্তনীয় থাকে। উদাহরণস্বরূপ, দুটি কুরাটোভস্কি গ্রাফ এবং উভয়ই একটি একক ক্রসিং দিয়ে আঁকা যেতে পারে এবং কলিন ডি ভার্ডিয়ের সর্বাধিক চারটি অপরিবর্তনীয় রয়েছে। প্রভাব কলিন ডি ভার্ডিয়ের অপরিবর্তনীয়কে শুধুমাত্র একটি ম্যাট্রিক্সের পরিবর্তে গ্রাফের সাথে সম্পর্কিত ম্যাট্রিক্সের একটি শ্রেণীর মাধ্যমে সংজ্ঞায়িত করা হয়। একই লাইনে অন্যান্য গ্রাফ প্যারামিটারগুলি একই লাইনে সংজ্ঞায়িত এবং অধ্যয়ন করা যেতে পারে, যেমন ন্যূনতম র্যাঙ্ক, ন্যূনতম সেমিডিফাইনাইট র্যাঙ্ক এবং ন্যূনতম স্ক্যু র্যাঙ্ক। উল্লেখগুলি উল্লেখ করুন। অনুবাদ করেছেন নিল জে কালকিন। । । । গ্রাফ অপরিবর্তনীয় গ্রাফ ক্ষুদ্র তত্ত্ব