Blow-up lemma
1997 সালে জানোস কমলোস, গাবোর এন সার্কোজি এবং এন্ড্রে স্জেমেরডি দ্বারা প্রমাণিত ব্লো-আপ লেম্মা চরম গ্রাফ তত্ত্বের একটি গুরুত্বপূর্ণ ফলাফল, বিশেষ করে নিয়মিততা পদ্ধতির প্রেক্ষাপটে। এতে বলা হয়েছে যে স্জেমেরেডির নিয়মিত লেম্মার বিবৃতির নিয়মিত জোড়াগুলি সীমাবদ্ধ মাত্রার বিস্তৃত গ্রাফগুলি এম্বেড করার প্রসঙ্গে সম্পূর্ণ দ্বিদলীয় গ্রাফের মতো আচরণ করে। সংজ্ঞা এবং বিবৃতি ব্লো-আপ লেম্মাকে আনুষ্ঠানিকভাবে বর্ণনা করার জন্য, আমাদের প্রথমে একটি অতি-নিয়মিত জুটির ধারণাটি সংজ্ঞায়িত করতে হবে। অতি-নিয়মিত জোড়া ভার্টেক্স সেটের এক জোড়া উপসেটকে বলা হয়-অতি-নিয়মিত যদি প্রতিটি এবং সন্তোষজনক এবং আমাদের আছে এবং উপরন্তু, সকলের জন্য এবং সকলের জন্য। এখানে জোড়ার সংখ্যা বোঝানো হয়েছে এবং এটি একটি প্রান্ত। ব্লো-আপ লেম্মার বিবৃতি ক্রম এবং ইতিবাচক পরামিতিগুলির একটি গ্রাফ দেওয়া হলে, একটি ইতিবাচক রয়েছে যা নিম্নলিখিত ধারণ করে। আসুন নির্বিচারে ধনাত্মক পূর্ণসংখ্যা হতে দিন এবং আসুন আমরা এর শীর্ষগুলিকে জোড়ার দিক থেকে বিচ্ছিন্ন আকারের সেট দিয়ে প্রতিস্থাপন করি। আমরা একই ভার্টেক্স সেটের উপর দুটি গ্রাফ তৈরি করি। প্রথম গ্রাফটি সংশ্লিষ্ট ভার্টেক্স সেট এবং এর মধ্যে সম্পূর্ণ দ্বিদলীয় গ্রাফ দিয়ে প্রতিটি প্রান্ত প্রতিস্থাপন করে প্রাপ্ত হয়। একটি বিচ্ছুরক গ্রাফ জি প্রতিটি প্রান্তকে এবং এর মধ্যে একটি-সুপার-নিয়মিত জোড়া দিয়ে প্রতিস্থাপন করে তৈরি করা হয়। যদি একটি গ্রাফ সহ এম্বেড করা যায় তবে এটি ইতিমধ্যে জি প্রুফ স্কেচে এম্বেড করা যায় ব্লো-আপ লেমার প্রমাণ ক্রমানুসারে শীর্ষগুলি এম্বেড করার জন্য একটি র্যান্ডমাইজড লোভী অ্যালগরিদম (আরজিএ) ব্যবহারের উপর ভিত্তি করে। যুক্তিটি তখন অ্যালগরিদমের ব্যর্থতার হারকে এমনভাবে সীমাবদ্ধ করে এগিয়ে যায় যে এটি পরামিতিগুলির উপযুক্ত পছন্দের জন্য 1 (এবং প্রকৃতপক্ষে) এর চেয়ে কম। এর মানে হল যে অ্যালগরিদম সফল হওয়ার জন্য একটি অ-শূন্য সম্ভাবনা রয়েছে, তাই একটি এম্বেডিং অবশ্যই বিদ্যমান থাকতে হবে। এই পদ্ধতিতে সমস্ত শীর্ষগুলি সরাসরি এম্বেড করার চেষ্টা কাজ করে না কারণ অল্প সংখ্যক শীর্ষগুলি অবশিষ্ট থাকলে অ্যালগরিদম আটকে যেতে পারে। পরিবর্তে, আমরা ভার্টেক্স সেটের একটি ছোট ভগ্নাংশ আলাদা করে রাখি, যাকে বাফার ভার্টিসেস বলা হয় এবং বাকি ভার্টিসগুলি এম্বেড করার চেষ্টা করি। বাফার শীর্ষগুলি পরবর্তীকালে হলের বিবাহ উপপাদ্য ব্যবহার করে সংযুক্ত করা হয় যাতে বাফার শীর্ষগুলি এবং এর অবশিষ্ট শীর্ষগুলির মধ্যে একটি নিখুঁত মিল খুঁজে পাওয়া যায়। স্বরলিপি আমরা পূর্ববর্তী বিভাগে প্রবর্তিত সমস্ত স্বরলিপি ধার করি। যাক। যেহেতু এটি অন্তর্ভুক্ত করা যেতে পারে, তাই আমরা সবার জন্য লিখতে পারি। একটি শীর্ষের জন্য, ধরা যাক। এর জন্য, এর সংশ্লিষ্ট ভার্টেক্স সেটগুলির মধ্যে প্রান্তের ঘনত্ব নির্দেশ করে। এটি হল এম্বেডিং যা আমরা নির্মাণ করতে চাই। এটি চূড়ান্ত সময় যার পরে অ্যালগরিদম শেষ হয়। অ্যালগরিদম ফেজ 0-এর রূপরেখাঃ ইনিশিয়ালাইজেশন লোভের সাথে শীর্ষগুলি থেকে বাফার শীর্ষগুলির সেটটি কমপক্ষে একে অপরের থেকে দূরত্বের সর্বোচ্চ সেট হিসাবে বেছে নিন একটি তালিকার অবশিষ্ট শীর্ষগুলি (মধ্যে থাকা) অর্ডার করুন, প্রথমটির প্রতিবেশীদের স্থাপন করুন। বর্তমানে অগ্রাধিকারপ্রাপ্ত শীর্ষগুলির একটি সারি ঘোষণা করুন, যা প্রাথমিকভাবে খালি। শীর্ষগুলি দ্বারা সূচিবদ্ধ সেটগুলির একটি অ্যারে ঘোষণা করুন, যা সমস্ত "মুক্ত দাগ"-এর সেটকে উপস্থাপন করে, অর্থাৎ, শীর্ষে অব্যবহৃত শীর্ষগুলির সেটটি ইতিমধ্যে এম্বেড করা প্রতিবেশীদের কাছ থেকে কোনও সংলগ্ন শর্ত লঙ্ঘন না করে ম্যাপ করা যেতে পারে। শুরু করা হয়। পর্যায় 1: এলোমেলোভাবে লোভী এম্বেডিং অবশিষ্ট শীর্ষগুলির সেট থেকে নিম্নরূপ একটি শীর্ষ নির্বাচন করুনঃ যদি অগ্রাধিকারপ্রাপ্ত শীর্ষগুলির সারি খালি না হয়, তবে থেকে শীর্ষটি বেছে নিন অন্যথায়, অবশিষ্ট শীর্ষগুলির তালিকা থেকে একটি শীর্ষ বেছে নিন "ভাল" পছন্দগুলির সেট থেকে এলোমেলোভাবে শীর্ষের জন্য চিত্রটি বেছে নিন, যেখানে একটি পছন্দ ভাল যদি নতুন ফ্রি-সেটগুলির কোনওটিই প্রত্যাশিত মান থেকে আকারে খুব বেশি আলাদা না হয়। মুক্ত সেটগুলি হালনাগাদ করুন এবং এমন শীর্ষগুলি রাখুন যার মুক্ত সেটগুলি অগ্রাধিকারপ্রাপ্ত শীর্ষগুলির সেটের শেষ আপডেটে তাদের আকারের তুলনায় খুব ছোট হয়ে গেছে যদি সারিতে কোনও সেটের যথেষ্ট বড় ভগ্নাংশ থাকে তবে বাতিল করুন যদি বাফারবিহীন শীর্ষগুলি এমবেড করার জন্য বাকি থাকে বা, সময় আপডেট করুন এবং ধাপ 1-এ ফিরে যান; অন্যথায় দ্বিতীয় পর্যায়ে যান। পর্যায় 2: অবশিষ্ট শীর্ষগুলির জন্য কনিগ-হল ম্যাচিং এম্বেড করার জন্য অবশিষ্ট শীর্ষগুলির সেট বিবেচনা করুন, যা সঠিকভাবে, এবং মুক্ত দাগগুলির সেট। এই দুটি সেটের মধ্যে একটি দ্বিদলীয় গ্রাফ তৈরি করুন, একে অপরের সাথে যুক্ত করুন এবং এই দ্বিদলীয় গ্রাফে একটি নিখুঁত মিল খুঁজে বের করুন। এই মিল অনুসারে এমবেড করুন। সঠিকতার প্রমাণ সঠিকতার প্রমাণ প্রযুক্তিগত এবং বেশ জড়িত, তাই আমরা বিশদটি বাদ দিই। মূল যুক্তিটি নিম্নরূপঃ ধাপ 1: বেশিরভাগ শীর্ষগুলি ভাল, এবং পর্যাপ্ত শীর্ষগুলি মুক্ত, একই সাথে প্রবর্তন দ্বারা প্রমাণ করুন যে যদি শীর্ষটি সময়ে এম্বেড করা থাকে, তবে পছন্দগুলির একটি ছোট ভগ্নাংশই খারাপ হয় সমস্ত মুক্ত সেটগুলি অনিবন্ধিত শীর্ষগুলির জন্য মোটামুটি বড় ধাপ 2: "প্রধান লেম্মা" বিবেচনা করুন, এবং যা খুব ছোট নয়। সেই ঘটনাটির কথা বিবেচনা করুন যেখানে প্রথম পর্যায়ে কোনও শীর্ষ সংযুক্ত করা হয় না, প্রত্যেকটির জন্য এমন একটি সময় থাকে যে সেই সময়ে মুক্ত শীর্ষগুলির ভগ্নাংশ ছোট ছিল। তারপর, আমরা প্রমাণ করি যে ঘটার সম্ভাবনা কম। ধাপ 3: প্রথম পর্যায়টি উচ্চ সম্ভাবনার সাথে সফল হয় প্রথম পর্যায়টি ব্যর্থ হওয়ার একমাত্র উপায় হল যদি এটি বাতিল হয়ে যায়, কারণ প্রথম ধাপের মাধ্যমে আমরা জানি যে সর্বদা ভাল শীর্ষগুলির একটি পর্যাপ্ত পছন্দ রয়েছে। যখন সারিটি খুব দীর্ঘ হয় তখনই প্রোগ্রামটি বন্ধ হয়ে যায়। তারপরে যুক্তিটি ব্যর্থতার সমস্ত পদ্ধতির উপর ইউনিয়ন-বাউন্ডিং দ্বারা এগিয়ে যায়, উল্লেখ করে যে কোনও নির্দিষ্ট পছন্দের জন্য, এবং ব্যর্থ সারির একটি উপসেট প্রতিনিধিত্ব করার সাথে, ট্রিপল "প্রধান লেমা"-র শর্তগুলি সন্তুষ্ট করে এবং এইভাবে ঘটার সম্ভাবনা কম থাকে। পদক্ষেপ 4: প্রাথমিক পর্যায়ে কোনও সারি নেই মনে রাখবেন যে তালিকাটি সেট আপ করা হয়েছিল যাতে বাফারের শীর্ষগুলির প্রতিবেশীরা প্রথমে এম্বেড করা যায়। এই সমস্ত শীর্ষগুলি এম্বেড না হওয়া পর্যন্ত সময়কে প্রাথমিক পর্যায় বলা হয়। প্রবর্তন দ্বারা প্রমাণ করুন যে প্রাথমিক পর্যায়ে সারিতে কোনও শীর্ষ যোগ করা হয় না। এটি অনুসরণ করে যে বাফার শীর্ষগুলির সমস্ত প্রতিবেশী বাকি শীর্ষগুলির আগে যোগ করা হয়। পদক্ষেপ 5: বাফার শীর্ষে যথেষ্ট মুক্ত দাগ রয়েছে যে কোনওটির জন্য এবং, আমরা সম্ভাবনার উপর যথেষ্ট বড় নিম্ন সীমা খুঁজে পেতে পারি যে, যে কোনও শীর্ষে এম্বেড করার আগে যে অনুমানটি মুক্ত ছিল তার উপর শর্তযুক্ত। ধাপ 6: পর্যায় 2 উচ্চ সম্ভাবনার সাথে সফল হয় হলের বিবাহ উপপাদ্য অনুসারে, পর্যায় 2 ব্যর্থ হয় যদি এবং শুধুমাত্র হলের শর্ত লঙ্ঘন করা হয়। এটি হওয়ার জন্য, এমন কিছু এবং এরকম অবশ্যই থাকতে হবে। মুক্ত সেটের বিশালতা দ্বারা খুব ছোট হতে পারে না (ধাপ 1)। যদি খুব বড় হয়, তবে উচ্চ সম্ভাবনার সাথে, তাই এই জাতীয় ক্ষেত্রে ব্যর্থতার সম্ভাবনা কম হবে। যদি খুব ছোট বা খুব বড় না হয়, তবে এটি অব্যবহৃত শীর্ষগুলির একটি বড় সেট উল্লেখ করে, আমরা প্রধান লেম্মা এবং ইউনিয়ন-আবদ্ধ ব্যর্থতার সম্ভাবনা ব্যবহার করতে পারি। অ্যাপ্লিকেশন ঘন গ্রাফ এম্বেড করার ক্ষেত্রে ব্লো-আপ লেম্মার বেশ কয়েকটি অ্যাপ্লিকেশন রয়েছে। 1962 সালে, লাজোস পোসা অনুমান করেছিলেন যে ন্যূনতম ডিগ্রি সহ প্রতিটি-ভার্টেক্স গ্রাফে কমপক্ষে একটি হ্যামিল্টনিয়ান চক্রের বর্গ রয়েছে, যা ডিরাকের উপপাদ্যকে সাধারণীকরণ করে। 1974 সালে পল সেমুর এই অনুমানটি আরও প্রসারিত করেছিলেনঃ সর্বনিম্ন ডিগ্রি সহ শীর্ষে প্রতিটি গ্রাফ কমপক্ষে হ্যামিল্টনিয়ান চক্রের-তম শক্তি ধারণ করে। 1998 সালে (একটি স্থিরের জন্য) সমস্ত পর্যাপ্ত বড় মানের অনুমান প্রমাণ করতে কমলোস, সার্কোজি এবং স্জেমেরাদি ব্লো-আপ লেম্মা ব্যবহার করেছিলেন। অ্যালন-ইউস্টার অনুমান 1995 সালে, নোগা অ্যালন এবং রাফায়েল ইউস্টার সুপরিচিত হাজনাল-জিমেরিডি উপপাদ্যের সাধারণীকরণকে নির্বিচারে-ফ্যাক্টর (সম্পূর্ণ গ্রাফের পরিবর্তে) হিসাবে বিবেচনা করেছিলেন এবং নিম্নলিখিত বিবৃতিটি প্রমাণ করেছিলেনঃ শীর্ষ সহ প্রতিটি স্থির গ্রাফের জন্য, n শীর্ষ সহ এবং ন্যূনতম ডিগ্রি সহ যে কোনও গ্রাফ জি-তে এইচ-এর শীর্ষ বিচ্ছিন্ন অনুলিপি থাকে। তারা আরও অনুমান করেছিলেন যে ফলাফলটি কেবল একটি ধ্রুবক (রৈখিকের পরিবর্তে) ত্রুটির সাথে ধারণ করেঃ প্রতিটি পূর্ণসংখ্যার জন্য এমন একটি ধ্রুবক বিদ্যমান যাতে শীর্ষ সহ প্রতিটি গ্রাফের জন্য, শীর্ষ সহ এবং ন্যূনতম ডিগ্রি সহ যে কোনও গ্রাফ কমপক্ষে শীর্ষের বিচ্ছিন্ন অনুলিপি ধারণ করে। এই অনুমানটি 2001 সালে ব্লো-আপ লেম্মা ব্যবহার করে কমলোস, সার্কোজি এবং স্জেমেরডি দ্বারা প্রমাণিত হয়েছিল। ইতিহাস এবং বৈচিত্র্য 1997 সালে কমলোস, সার্কোজি এবং স্জেমেরডি দ্বারা প্রথম প্রকাশিত ব্লো-আপ লেম্মা, বিস্তৃত গ্রাফগুলি এম্বেড করার জন্য নিয়মিততা পদ্ধতি ব্যবহার করে বিদ্যমান প্রমাণ কৌশলগুলির একটি পরিমার্জন হিসাবে আবির্ভূত হয়েছিল, যেমন বিস্তৃত গাছের উপর বোলোবাস অনুমানের প্রমাণ হিসাবে, হ্যামিল্টনিয়ান চক্রের কে-তম গ্রাফ শক্তি ধারণ করার জন্য প্রয়োজনীয় ন্যূনতম ডিগ্রি সম্পর্কে পোসা-সেমুর অনুমানের উপর কাজ করে এবং একটি গ্রাফের জন্য নিখুঁত এইচ-ফ্যাক্টর থাকার জন্য প্রয়োজনীয় ন্যূনতম ডিগ্রির উপর অ্যালন-ইউস্টার অনুমানের প্রমাণ। এই সমস্ত উপপাদ্যের প্রমাণগুলি বেশিরভাগ শীর্ষগুলি এম্বেড করার জন্য একটি র্যান্ডমাইজড লোভী অ্যালগরিদম ব্যবহার করার উপর নির্ভর করে এবং তারপরে অবশিষ্ট শীর্ষগুলির জন্য একটি এম্বেডিং খুঁজে পেতে কনিগ-হলের মতো যুক্তি ব্যবহার করে। ব্লো-আপ লেম্মার প্রথম প্রমাণটিও অনুরূপ যুক্তি ব্যবহার করেছিল। যাইহোক, পরে 1997 সালে, একই লেখকরা আরেকটি গবেষণাপত্র প্রকাশ করেন যা র্যান্ডমাইজড অ্যালগরিদমকে নির্ধারণমূলক করার জন্য একটি উন্নতি খুঁজে পায়। পিটার কিভাশ 2010 সালে হাইপারগ্রাফগুলিতে ব্লো-আপ লেমার একটি সাধারণীকরণ খুঁজে পেয়েছিলেন। স্টেফান গ্লক এবং ফেলিক্স জুস 2018 সালে রামধনু গ্রাফের জন্য ব্লো-আপ লেমার একটি রূপ আবিষ্কার করেন। 2019 সালে, পিটার অ্যালেন, জুলিয়া বটচার, হাইপ হান, ইয়োশিহারু কোহায়াকাওয়া এবং ইউরি পার্সন, এলোমেলো এবং ছদ্মবেশী গ্রাফগুলিতে সীমাবদ্ধ ডিগ্রি গ্রাফ এম্বেড করার জন্য ব্লো-আপ লেম্মার বিরল সাদৃশ্য খুঁজে পেয়েছেন।