ফ্রিডম্যানের এসএসসিজি ফাংশন

গণিতে, একটি সরল সাবকিউবিক গ্রাফ (এসএসসিজি) হলো একটি সীমাবদ্ধ সহজ গ্রাফ যেখানে প্রতিটি শীর্ষের সর্বোচ্চ তিনটি ডিগ্রি থাকে। ধরুন, আমাদের কাছে সহজ সাবকিউবিক গ্রাফের একটি ক্রম G1, G2,... আছে যেখানে প্রতিটি গ্রাফের Gi এর সর্বাধিক i + k শীর্ষবিন্দু থাকে (কিছু পূর্ণসংখ্যা k এর জন্য) এবং এবং কোনটি i < j এর জন্য Gi হোমোমরফিকালি এম্বেডেবল নয় (অর্থাৎ এটি একটি গ্রাফ মাইনর)।

রবার্টসন-সেইমোর উপপাদ্য প্রমাণ করে যে সাবকিউবিক গ্রাফগুলি (সরল বা না) হোমোমরফিক এম্বেডেবিলিটি দ্বারা সু-প্রতিষ্ঠিত, যা বোঝায় যে এমন একটি ক্রম অসীম হতে পারে না। তারপর, কোনিগের লেমা প্রয়োগ করে এমন ক্রমগুলির গাছের উপর সম্প্রসারণের অধীনে, প্রতিটি k মানের জন্য একটি সর্বাধিক দৈর্ঘ্যের ক্রম রয়েছে। SSCG(k) ফাংশনটি সরল সাবকিউবিক গ্রাফগুলির জন্য সেই দৈর্ঘ্য নির্দেশ করে। SCG(k) ফাংশনটি (সাধারণ) সাবকিউবিক গ্রাফগুলির জন্য সেই দৈর্ঘ্য নির্দেশ করে।

SCG ক্রমটি শুরু হয় SCG(0) = 6 দিয়ে, তবে তারপর একটি মানে বিস্ফোরিত হয় যা দ্রুত-বর্ধমান শ্রেণিবিন্যাস এ fε2*2 এর সমতুল্য।

SSCG ক্রমটি SCG এর চেয়ে ধীরে শুরু হয়, SSCG(0) = 2, SSCG(1) = 5, তবে তারপর দ্রুত বৃদ্ধি পায়। SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 10. এর প্রথম এবং শেষ ২০টি সংখ্যা হল 32417042291246009846...34057047399148290040। SSCG(3) উভয়ের চেয়ে অনেক বড় TREE(3) এবং TREETREE(3)(3), অর্থাৎ, TREE ফাংশনটি TREE(3) গুণিতক থেকে ৩ দিয়ে নিচে।

অ্যাডাম পি. গৌচারের দাবি SSCG এবং SCG এর অসমাপ্তিক বৃদ্ধির হারের মধ্যে কোনও গুণগত পার্থক্য নেই। তিনি লিখেছেন "এটা স্পষ্ট যে SCG(n) ≥ SSCG(n), তবে আমি SSCG(4n + 3) ≥ SCG(n) প্রমাণ করতে পারি।"

ফাংশনটি হার্ভি ফ্রিডম্যান দ্বারা প্রস্তাবিত এবং অধ্যয়ন করা হয়েছিল।

 আরও দেখুন 
গুডস্টাইনের উপপাদ্য 
প্যারিস-হ্যারিংটন উপপাদ্য
কানামোরি-ম্যাকালুন উপপাদ্য

 তথ্যসূত্র 

বিষয়শ্রেণী:গাণিতিক যুক্তিবিজ্ঞান
বিষয়শ্রেণী:বিছিন্ন গণিতের উপপাদ্য
বিষয়শ্রেণী:ক্রম তত্ত্ব
বিষয়শ্রেণী:যুক্তিসঙ্গতি
বিষয়শ্রেণী:গ্রাফ তত্ত্ব