Container method
(হাইপারগ্রাফ) ধারকগুলির পদ্ধতি একটি শক্তিশালী সরঞ্জাম যা সাধারণ কাঠামোকে চিহ্নিত করতে এবং/অথবা স্থানীয় সীমাবদ্ধতার একটি নির্ধারিত সেট সহ বিচ্ছিন্ন বস্তুর পরিবার সম্পর্কে চরম প্রশ্নের উত্তর দিতে সহায়তা করতে পারে। এই ধরনের প্রশ্নগুলি স্বাভাবিকভাবেই চরম গ্রাফ তত্ত্ব, অ্যাডিটিভ কম্বিনেটরিক্স, বিচ্ছিন্ন জ্যামিতি, কোডিং তত্ত্ব এবং রামসে তত্ত্বে উত্থাপিত হয়; এগুলির মধ্যে সম্পর্কিত ক্ষেত্রগুলির কয়েকটি ধ্রুপদী সমস্যা অন্তর্ভুক্ত রয়েছে। এই সমস্যাগুলি নিম্নলিখিত রূপের প্রশ্ন হিসাবে প্রকাশ করা যেতে পারেঃ প্রান্ত সেট সহ সীমাবদ্ধ শীর্ষে একটি হাইপারগ্রাফ দেওয়া হয়েছে (অর্থাৎ। কিছু আকারের সীমাবদ্ধতা সহ উপসেটগুলির একটি সংগ্রহ), এর স্বাধীন সেটগুলি সম্পর্কে আমরা কী বলতে পারি (অর্থাৎ। এর সেই উপসেটগুলিতে কোন উপাদান নেই)? হাইপারগ্রাফ ধারক লেম্মা এই ধরনের প্রশ্ন মোকাবেলার জন্য একটি পদ্ধতি প্রদান করে। ইতিহাস চরম গ্রাফ তত্ত্বের অন্যতম মৌলিক সমস্যা, যা 1907 সালে ম্যান্টেল এবং 1940-এর দশকের তুরানের কাজের সাথে সম্পর্কিত, সেই গ্রাফগুলিকে চিহ্নিত করতে বলে যা একটি উপগ্রাফ হিসাবে নিষিদ্ধ কিছু নির্দিষ্ট অনুলিপি ধারণ করে না। একটি ভিন্ন ডোমেনে, অ্যাডিটিভ কম্বিনেটরিক্সের একটি অনুপ্রেরণামূলক প্রশ্ন হল-টার্ম গাণিতিক অগ্রগতি ছাড়াই পূর্ণসংখ্যার একটি সেট কতটা বড় হতে পারে তা বোঝা, রথ () এবং স্জেমেরডি (সাধারণ) দ্বারা প্রদত্ত এই আকারের উপরের সীমা সহ। ধারক পদ্ধতি (আলেখ্যে) প্রাথমিকভাবে 1980 সালে ক্লেইটম্যান এবং উইনস্টন দ্বারা প্রবর্তিত হয়েছিল, যারা 4-চক্র ছাড়াই জাল এবং গ্রাফের সংখ্যা সীমাবদ্ধ করেছিল। কনটেইনার-শৈলীর লেম্মা বিভিন্ন প্রসঙ্গে একাধিক গণিতবিদ দ্বারা স্বাধীনভাবে বিকশিত হয়েছিল, বিশেষত সাপোঝেঙ্কো সহ, যিনি প্রাথমিকভাবে নিয়মিত গ্রাফে স্বাধীন সেট গণনা করতে, আবেলিয়ান গোষ্ঠীতে সমষ্টি-মুক্ত সেট গণনা করতে এবং অন্যান্য বিভিন্ন গণনা সমস্যা অধ্যয়ন করতে 2002-2003 এ এই পদ্ধতিটি ব্যবহার করেছিলেন। এই ধারণাগুলির একটি হাইপারগ্রাফ ধারক লেম্মায় সাধারণীকরণ স্যাক্সটন এবং থমসন এবং বালোগ, মরিস এবং সামোটিজ দ্বারা 2015 সালে স্বাধীনভাবে তৈরি করা হয়েছিল, যা পূর্ববর্তী সম্পর্কিত বিভিন্ন কাজের দ্বারা অনুপ্রাণিত হয়েছিল। মূল ধারণা এবং অনানুষ্ঠানিক বিবৃতি সংমিশ্রণে অনেক সমস্যা গ্রাফ এবং হাইপারগ্রাফগুলিতে স্বাধীন সেট সম্পর্কে প্রশ্ন হিসাবে পুনর্বিন্যাস করা যেতে পারে। উদাহরণস্বরূপ, ধরুন আমরা পূর্ণসংখ্যার উপসেটগুলি বুঝতে চাই, যা আমরা একটি-টার্ম গাণিতিক অগ্রগতির অভাব দ্বারা নির্দেশ করি। এই সেটগুলি-ইউনিফর্ম হাইপারগ্রাফের ঠিক স্বাধীন সেট, যেখানে সমস্ত-টার্ম গাণিতিক অগ্রগতির সংগ্রহ রয়েছে। উপরের (এবং অন্যান্য অনেক) ক্ষেত্রে, একটি হাইপারগ্রাফ সম্পর্কে সাধারণত দুটি প্রাকৃতিক শ্রেণীর সমস্যা দেখা দেয়ঃ একটি সর্বাধিক স্বাধীন সেটের আকার কত? সর্বাধিক আকারের স্বাধীন সেটের সংগ্রহ দেখতে কেমন? কিভাবে স্বাধীন সেট থাকতে পারে? একটি "সাধারণ" স্বাধীন সেট দেখতে কেমন? এই সমস্যাগুলি একটি সহজ পর্যবেক্ষণের দ্বারা সংযুক্ত। ধরা যাক একটি বৃহত্তম স্বাধীন সেটের আকার এবং ধরুন এর স্বাধীন সেট রয়েছে। তারপর, যেখানে নিম্ন সীমা একটি সর্বাধিক স্বাধীন সেটের সমস্ত উপসেট নিয়ে অনুসরণ করে। এই সীমানাগুলি একে অপরের থেকে তুলনামূলকভাবে অনেক দূরে থাকে যদি না তা খুব বড় হয়, হাইপারগ্রাফের শীর্ষগুলির সংখ্যার কাছাকাছি হয়। যাইহোক, অনেক হাইপারগ্রাফে যা স্বাভাবিকভাবেই সমন্বিত সমস্যায় উদ্ভূত হয়, আমাদের বিশ্বাস করার কারণ রয়েছে যে নিম্ন সীমাটি প্রকৃত মানের কাছাকাছি; সুতরাং প্রাথমিক লক্ষ্য হল উপরের সীমার উন্নতি করা। হাইপারগ্রাফ ধারক লেম্মা একটি হাইপারগ্রাফ-এ স্বাধীন সেটের পরিবারের কাঠামো এবং আকার বোঝার জন্য একটি শক্তিশালী পদ্ধতি প্রদান করে। এর মূলে, হাইপারগ্রাফ ধারক পদ্ধতি আমাদের একটি হাইপারগ্রাফ থেকে বের করতে সক্ষম করে, ধারকগুলির একটি সংগ্রহ, শীর্ষগুলির উপসেট যা নিম্নলিখিত বৈশিষ্ট্যগুলিকে সন্তুষ্ট করেঃ খুব বেশি ধারক নেই। প্রতিটি ধারক বৃহত্তম স্বাধীন সেটের চেয়ে খুব বেশি বড় নয়। প্রতিটি পাত্রে কয়েকটি করে প্রান্ত থাকে। হাইপারগ্রাফের প্রতিটি স্বাধীন সেট সম্পূর্ণরূপে কোনও না কোনও পাত্রে অন্তর্ভুক্ত থাকে। নাম ধারকটি এই শেষ শর্তটিকে নির্দেশ করে। এই ধরনের ধারকগুলি প্রায়শই স্বাধীন সেটগুলির (ধারকগুলির উপসেট) পরিবারকে চিহ্নিত করতে এবং হাইপারগ্রাফের স্বাধীন সেটগুলি গণনা করার জন্য (কেবল একটি ধারকের সমস্ত সম্ভাব্য উপসেট বিবেচনা করে) একটি কার্যকর পদ্ধতি প্রদান করে। হাইপারগ্রাফ ধারকটির লেমা উপরের ধারকটির পচনকে দুটি অংশে পরিণত করে। এটি একটি নির্ধারক ফাংশন তৈরি করে। তারপরে, এটি একটি অ্যালগরিদম সরবরাহ করে যা হাইপারগ্রাফের প্রতিটি স্বাধীন সেট থেকে বের করে, যা তুলনামূলকভাবে ছোট শীর্ষগুলির সংগ্রহ, যাকে ফিঙ্গারপ্রিন্ট বলা হয়। তারপরে, পাত্রেগুলি হল উপরের প্রক্রিয়াতে উদ্ভূত সেটগুলির সংগ্রহ, এবং আঙুলের ছাপের ছোট আকার এই ধরনের পাত্রে সেটগুলির সংখ্যার উপর ভাল নিয়ন্ত্রণ প্রদান করে। গ্রাফ ধারক অ্যালগরিদম আমরা প্রথমে একটি গ্রাফে স্বাধীন সেটের সংখ্যার উপর শক্তিশালী উপরের সীমা দেখানোর জন্য একটি পদ্ধতি বর্ণনা করি; এই প্রদর্শনীটি গ্রাফ ধারক পদ্ধতি সম্পর্কে সামোটিজের একটি সমীক্ষা থেকে অভিযোজিত হয়েছে, যা মূলত ক্লেইটম্যান-উইনস্টন এবং সাপোজেঙ্কো দ্বারা নিযুক্ত। স্বরলিপি আমরা নীচের বিভাগে নিম্নলিখিত স্বরলিপিটি ব্যবহার করি। এটি উল্লম্বের উপর একটি গ্রাফ, যেখানে ভার্টেক্স সেটটি (নির্বিচারে) ক্রম দিয়ে সজ্জিত। আকারের সাথে স্বাধীন সেটগুলির সংগ্রহ হতে দিন। আকারের স্বাধীন সেটের সংখ্যা ধরা যাক। একটি ভার্টেক্স উপসেটের সর্বোচ্চ-ডিগ্রি ক্রম হল ইনডিউসড সাবগ্রাফে তাদের ডিগ্রি দ্বারা শীর্ষগুলির ক্রম। ক্লেইটম্যান-উইনস্টন অ্যালগরিদম নিম্নলিখিত অ্যালগরিদমটি একটি গ্রাফের প্রতিটি স্বাধীন সেটের জন্য একটি ছোট "ফিঙ্গারপ্রিন্ট" এবং ফিঙ্গারপ্রিন্টের একটি নির্ধারক ফাংশন দেয় যাতে একটি খুব বড় উপসেট তৈরি করা যায় যা সম্পূর্ণ স্বাধীন সেট ফিক্স গ্রাফ, স্বাধীন সেট এবং ধনাত্মক পূর্ণসংখ্যা ধারণ করে। শুরু করুনঃ যাক। এর জন্য পুনরাবৃত্তি করুনঃ ফাইন্ড দ্য মিনিমাল ইনডেক্সের সর্বোচ্চ-ডিগ্রি ক্রমটি এমনভাবে তৈরি করুন যাতে (অর্থাৎ। ইনডিউসড সাবগ্রাফ-এ সবচেয়ে বড় মাত্রার শীর্ষ) ধরা যাক, শীর্ষের প্রতিবেশী কোথায়। ভেক্টর এবং ভার্টেক্স সেট আউটপুট করুন। বিশ্লেষণ নির্মাণ দ্বারা, উপরের অ্যালগরিদমের আউটপুটের বৈশিষ্ট্য রয়েছে যে, এটি একটি ভার্টেক্স উপসেট যা সম্পূর্ণরূপে দ্বারা নির্ধারিত হয় এবং অন্যথায় এর একটি ফাংশন নয়। এর উপর জোর দেওয়ার জন্য আমরা লিখবো। আমরা আরও লক্ষ্য করেছি যে আমরা কেবল ভেক্টর থেকে উপরের অ্যালগরিদমে সেটটি পুনর্গঠন করতে পারি। এটি ইঙ্গিত দেয় যে এটি একটি ফিঙ্গারপ্রিন্টের একটি ভাল পছন্দ এবং একটি ধারকের জন্য একটি ভাল পছন্দ হতে পারে। আরও সুনির্দিষ্টভাবে, আমরা আউটপুট সিকোয়েন্সের সমষ্টি হিসাবে কিছু আকারের স্বাধীন সেটের সংখ্যাকে আবদ্ধ করতে পারি, যেখানে আমরা গ্রাফের স্বাধীন সেটের মোট সংখ্যার উপর একটি সীমা পেতে পারিঃ এই উপরের সীমাটি হ্রাস করার চেষ্টা করার সময়, আমরা সেই ভারসাম্যটি বেছে নিতে চাই/এই দুটি পদকে ন্যূনতম করতে চাই। এই ফলাফলটি সর্বোচ্চ ডিগ্রি দ্বারা শীর্ষগুলি ক্রমবদ্ধ করার মানকে চিত্রিত করে (হ্রাস করতে)। লেম্মাস উপরের বৈষম্য এবং পর্যবেক্ষণগুলি আরও সাধারণ পরিবেশে বলা যেতে পারে, যা ভেক্টরের উপর একটি স্পষ্ট যোগফল থেকে বিচ্ছিন্ন। লেম্মা 1: একটি গ্রাফ দেওয়া হয়েছে এবং ধরে নেওয়া হয়েছে যে পূর্ণসংখ্যা এবং বাস্তব সংখ্যা সন্তুষ্ট করে। ধরুন, অন্ততপক্ষে শীর্ষে প্রতিটি প্রবর্তিত উপ-গ্রাফের অন্তত প্রান্ত ঘনত্ব রয়েছে। তারপর প্রতিটি পূর্ণসংখ্যার জন্য, লেম্মা 2: শীর্ষে একটি গ্রাফ হতে দিন এবং ধরে নিন যে একটি পূর্ণসংখ্যা এবং বাস্তবগুলি এমনভাবে বেছে নেওয়া হয়েছে। যদি কমপক্ষে শীর্ষগুলির সমস্ত উপসেটগুলির কমপক্ষে প্রান্ত থাকে, তবে শীর্ষগুলির উপসেট ("আঙুলের ছাপ") এবং একটি নির্ধারক ফাংশন রয়েছে, যাতে প্রতিটি স্বাধীন সেটের জন্য এমন কিছু থাকে। হাইপারগ্রাফ ধারক লেম্মা অনানুষ্ঠানিকভাবে, হাইপারগ্রাফ ধারক লেম্মা আমাদের বলে যে আমরা প্রতিটি স্বাধীন সেটের জন্য একটি ছোট ফিঙ্গারপ্রিন্ট বরাদ্দ করতে পারি, যাতে একই ফিঙ্গারপ্রিন্ট সহ সমস্ত স্বাধীন সেট একই বড় সেটের অন্তর্গত হয়, সংশ্লিষ্ট ধারক, যার আকার হাইপারগ্রাফের শীর্ষের সংখ্যা থেকে দূরে সীমাবদ্ধ। উপরন্তু, এই আঙুলের ছাপগুলি ছোট (এবং এইভাবে কয়েকটি ধারক রয়েছে), এবং আমরা হাইপারগ্রাফের কিছু সহজ বৈশিষ্ট্য ব্যবহার করে মূলত সর্বোত্তম উপায়ে তাদের আকারকে উপরের দিকে বেঁধে রাখতে পারি। আমরা ইউনিফর্ম হাইপারগ্রাফের সাথে সম্পর্কিত নিম্নলিখিত স্বরলিপিটি স্মরণ করি। ধনাত্মক পূর্ণসংখ্যার সংজ্ঞা দিন, যেখানে। এর স্বাধীন সেটগুলির সংগ্রহ হতে দিন। এই ধরনের কিছু স্বাধীন সেটকে নির্দেশ করবে। বিবৃতি আমরা বালোগ, মরিস, সামোটিজ এবং স্যাক্সটনের একটি রচনায় পাওয়া এই লেম্মার সংস্করণটি উল্লেখ করি এবং ধরে নিই যে প্রত্যেকের জন্য আমাদের কাছে এটি রয়েছে। তারপর, একটি সংগ্রহ এবং একটি ফাংশন রয়েছে যা প্রত্যেকের জন্য এবং এর সাথে বিদ্যমান। প্রত্যেকের জন্য। উদাহরণ অ্যাপ্লিকেশন নিয়মিত গ্রাফ স্বাধীন সেটের সংখ্যার উপর উচ্চ সীমাবদ্ধতা আমরা দেখাব যে একটি পরম ধ্রুবক রয়েছে যা প্রতিটি-ভার্টেক্স-নিয়মিত গ্রাফকে সন্তুষ্ট করে। আমরা ট্রিভিয়াল বাউন্ড ব্যবহার করে প্রতিটি আকারের স্বাধীন সেটের সংখ্যা বেঁধে রাখতে পারি। এই প্যারামিটারগুলির সাথে,-নিয়মিত গ্রাফ লেমা 1-এর শর্তগুলি সন্তুষ্ট করে এবং এইভাবে, সমস্ত কিছুর উপর যোগফল দেয়, যা আমরা যখন সাম-মুক্ত সেটগুলি প্লাগ ইন করি তখন কাঙ্ক্ষিত ফলাফল দেয় একটি আবেলিয়ান গোষ্ঠীর উপাদানগুলির একটি সেটকে যোগফল-মুক্ত বলা হয় যদি কোনও সন্তোষজনক না থাকে। আমরা দেখাব যে এর সর্বাধিক সমষ্টি-মুক্ত উপসেট রয়েছে। এটি একটি নিয়মিত গ্রাফে স্বাধীন সেটের সংখ্যার উপর আমাদের উপরের সীমা থেকে অনুসরণ করবে। এটি দেখার জন্য, আমাদের একটি সহায়ক গ্রাফ তৈরি করতে হবে। আমরা প্রথমে লক্ষ্য করি যে নিম্ন ক্রমের শর্তাবলী পর্যন্ত, আমরা আমাদের ফোকাসকে কমপক্ষে ছোট উপাদানগুলির সমষ্টি-মুক্ত সেটগুলিতে সীমাবদ্ধ করতে পারি (যেহেতু এর পরিপূরকে উপসেটগুলির সংখ্যা সর্বাধিক)। কিছু উপসেট দেওয়া হলে, আমরা ভার্টেক্স সেট এবং এজ সেট সহ একটি অক্জিলিয়ারি গ্রাফ সংজ্ঞায়িত করি এবং লক্ষ্য করি যে আমাদের অক্জিলিয়ারি গ্রাফ নিয়মিত কারণ এর প্রতিটি উপাদান এর চেয়ে ছোট। তারপর যদি উপসেটের ক্ষুদ্রতম উপাদানগুলি হয়, তবে সেটটি গ্রাফের একটি স্বাধীন সেট। তারপরে, আমাদের পূর্ববর্তী সীমা দ্বারা, আমরা দেখতে পাই যে সর্বাধিক ত্রিভুজ-মুক্ত গ্রাফের সমষ্টি-মুক্ত উপসেটগুলির সংখ্যা আমরা হাইপারগ্রাফ ধারক লেম্মা ব্যবহার করে একটি সংখ্যাসূচক প্রশ্নের উত্তর দেওয়ার জন্য একটি দৃষ্টান্ত দিই যা শীর্ষস্থান সহ ত্রিভুজ-মুক্ত গ্রাফের সংখ্যার উপর একটি অ্যাসিম্পটোটিকভাবে টাইট আপার বাউন্ড দেয়। অনানুষ্ঠানিক বিবৃতি যেহেতু দ্বিদলীয় গ্রাফগুলি ত্রিভুজ-মুক্ত, তাই শীর্ষ সহ ত্রিভুজ মুক্ত গ্রাফের সংখ্যা কমপক্ষে সুষম সম্পূর্ণ দ্বিদলীয় গ্রাফের সমস্ত সম্ভাব্য উপগ্রাফ গণনা করে প্রাপ্ত হয়। আমরা ভার্টেক্স সেট এবং এজ সেট সহ একটি অক্জিলিয়ারি-ইউনিফর্ম হাইপারগ্রাফ তৈরি করতে পারি। এই হাইপারগ্রাফ ত্রিভুজকে এই অর্থে "এনকোড" করে যে শীর্ষে ত্রিভুজ-মুক্ত গ্রাফের পরিবারটি ঠিক এই হাইপারগ্রাফের স্বাধীন সেটগুলির সংগ্রহ। উপরের হাইপারগ্রাফটির একটি সুন্দর ডিগ্রি ডিস্ট্রিবিউশন রয়েছেঃ এর প্রতিটি প্রান্ত এবং এইভাবে শীর্ষটি ঠিক ত্রিভুজে রয়েছে এবং প্রতিটি জোড়া উপাদান সর্বাধিক 1টি ত্রিভুজে রয়েছে। অতএব, হাইপারগ্রাফ ধারক লেম্মা (পুনরাবৃত্তিমূলকভাবে) প্রয়োগ করে আমরা দেখাতে পারি যে ধারকগুলির একটি পরিবার রয়েছে যার প্রত্যেকটিতে কয়েকটি ত্রিভুজ রয়েছে যা প্রতিটি ত্রিভুজ-মুক্ত গ্রাফ/হাইপারগ্রাফের স্বাধীন সেট ধারণ করে। ত্রিভুজ-মুক্ত গ্রাফের সংখ্যার উপরের সীমা আমরা প্রথমে জেনেরিক হাইপারগ্রাফ ধারক লেম্মাকে 3-ইউনিফর্ম হাইপারগ্রাফ হিসাবে নিম্নরূপ বিশেষজ্ঞ করিঃ লেমাঃ প্রত্যেকের জন্য, এমন কিছু রয়েছে যা নিম্নলিখিত ধারণ করে। ধরা যাক গড় ডিগ্রি সহ একটি 3-ইউনিফর্ম হাইপারগ্রাফ এবং মনে করুন। তারপরে বেশিরভাগ ধারকগুলির একটি সংগ্রহ রয়েছে যাতে প্রত্যেকের জন্য, সকলের জন্য বিদ্যমান থাকে এই লেম্মাটি পুনরাবৃত্তভাবে প্রয়োগ করলে নিম্নলিখিত উপপাদ্যটি পাওয়া যাবে (নীচে প্রমাণিত হিসাবে): উপপাদ্যঃ সকলের জন্য, এমন কিছু রয়েছে যা নিম্নলিখিত ধারণ করে। প্রতিটি ধনাত্মক পূর্ণসংখ্যার জন্য, শীর্ষে এমন গ্রাফের একটি সংগ্রহ রয়েছে যার প্রত্যেকটিতে ত্রিভুজের চেয়ে কম থাকে, শীর্ষে প্রতিটি ত্রিভুজ-মুক্ত গ্রাফ কিছু কিছুতে থাকে। প্রমাণঃ উপরে বর্ণিত হাইপারগ্রাফটি বিবেচনা করুন। আগে অনানুষ্ঠানিকভাবে যেমন দেখা গেছে, হাইপারগ্রাফ প্রত্যেকের জন্য সন্তোষজনক। অতএব, আমরা (অর্থাৎ) এর উপসেটগুলির কিছু সংগ্রহ খুঁজে পেতে উপরের লেমমা প্রয়োগ করতে পারি। শীর্ষে গ্রাফ) এমন যে প্রতিটি ত্রিভুজ মুক্ত গ্রাফ কয়েকটির একটি উপগ্রাফ, প্রত্যেকটির সর্বাধিক প্রান্ত থাকে। এটি আমরা যে ফলাফলটি দেখাতে চাই তার মতো যথেষ্ট শক্তিশালী নয়, তাই আমরা পুনরাবৃত্তিমূলকভাবে ধারক লেম্মা প্রয়োগ করব। ধরুন আমাদের কাছে অন্তত ত্রিভুজ সহ কিছু ধারক রয়েছে। আমরা ইনডিউসড সাব-হাইপারগ্রাফ-এ ধারক লেম্মা প্রয়োগ করতে পারি। এর গড় ডিগ্রি কমপক্ষে, যেহেতু প্রতিটি ত্রিভুজের একটি প্রান্ত থাকে এবং এই প্ররোচিত উপ-গ্রাফের সর্বাধিক শীর্ষ থাকে। সুতরাং, আমরা পরামিতি সহ লেম্মা প্রয়োগ করতে পারি, আমাদের পাত্রে সেট থেকে সরাতে পারি, এই পাত্রে সেট দ্বারা প্রতিস্থাপন করতে পারি, পাত্রে আবরণ। আমরা পুনরাবৃত্তি করতে পারি যতক্ষণ না আমাদের ধারকগুলির একটি চূড়ান্ত সংগ্রহ থাকে যার প্রত্যেকটিতে ত্রিভুজের চেয়ে কম থাকে। আমরা লক্ষ্য করেছি যে এই সংগ্রহটি খুব বড় হতে পারে না; আমাদের সমস্ত প্ররোচিত সাবগ্রাফগুলির সর্বাধিক শীর্ষ এবং কমপক্ষে গড় ডিগ্রি রয়েছে, যার অর্থ প্রতিটি পুনরাবৃত্তির ফলস্বরূপ বেশিরভাগ নতুন ধারক থাকে। উপরন্তু, পাত্রের আকার প্রতিবার একটি ফ্যাক্টর দ্বারা সঙ্কুচিত হয়, তাই পুনরাবৃত্তির একটি সীমাবদ্ধ (নির্ভরশীল) সংখ্যার পরে, পুনরাবৃত্তিমূলক প্রক্রিয়াটি শেষ হয়ে যাবে। আরও দেখুন স্বাধীন সেট (গ্রাফ তত্ত্ব) স্জেমেরডির উপপাদ্য স্জেমেরডি নিয়মিততা লেম্মা রেফারেন্স এক্সট্রিমাল গ্রাফ তত্ত্ব হাইপারগ্রাফস অ্যাডিটিভ কম্বিনেটরিক্স