গ্রাফ বুটস্ট্র্যাপ পার্কোলেশনে তীক্ষ্ণ ফাস-ক্যাটালান থ্রেশহোল্ড

মৌলিক তথ্য

• পেপার আইডি: 2510.26724
• শিরোনাম: গ্রাফ বুটস্ট্র্যাপ পার্কোলেশনে তীক্ষ্ণ ফাস-ক্যাটালান থ্রেশহোল্ড
• লেখক: জোল্ট বার্থা, ব্রেট কোলেসনিক, গ্যাল ক্রোনেনবার্গ, ইউভাল পেলেড
• শ্রেণীবিভাগ: math.PR (সম্ভাব্যতা তত্ত্ব), math.CO (সমন্বয়বিদ্যা)
• প্রকাশনার সময়: ২০২৫ সালের ৩০ অক্টোবর arXiv-এ জমা দেওয়া
• পেপার লিঙ্ক: https://arxiv.org/abs/2510.26724

সারসংক্ষেপ

এই পেপারটি Erdős-Rényi র্যান্ডম গ্রাফ $G_{n,p}$-এ গ্রাফ বুটস্ট্র্যাপ পার্কোলেশন অধ্যয়ন করে। সমস্ত $r \geq 5$-এর জন্য, লেখকরা $K_r$-পার্কোলেশনের তীক্ষ্ণ থ্রেশহোল্ড $p_c \sim (\gamma n)^{-1/\lambda}$ সঠিকভাবে নির্ধারণ করেছেন, যা Balogh, Bollobás এবং Morris দ্বারা উত্থাপিত একটি উন্মুক্ত সমস্যার সমাধান করে। $r=3$ হলে এটি ক্লাসিক্যাল গ্রাফ সংযোগযোগ্যতা থ্রেশহোল্ডের সাথে সামঞ্জস্যপূর্ণ, এবং $r=4$-এর থ্রেশহোল্ড পরিসংখ্যানগত পদার্থবিজ্ঞানে ২-প্রতিবেশী গতিশীলতার সাথে সংযোগের মাধ্যমে সমাধান করা হয়েছে। কিন্তু $r \geq 5$-এর জন্য, এই সংযোগ আর বিদ্যমান থাকে না, এবং প্রক্রিয়াটি আরও সমৃদ্ধ আচরণ প্রদর্শন করে। থ্রেশহোল্ড $p_c$-এর ধ্রুবক $\lambda=\lambda(r)$ এবং $\gamma=\gamma(r)$ একটি শ্রেণীর $\binom{r}{2}-1$ মাত্রার বৃক্ষ-সদৃশ গ্রাফ দ্বারা নির্ধারিত হয়, যা লেখকরা $K_r$-বৃক্ষ সাক্ষী গ্রাফ (tree witness graphs) নাম দেন। এই গ্রাফগুলি $K_r$-গতিশীলতায় নতুন প্রান্ত যোগ করার সবচেয়ে কার্যকর উপায়ের সাথে সামঞ্জস্যপূর্ণ এবং ফাস-ক্যাটালান সংখ্যা দ্বারা গণনা করা যায়। অতিরিক্তভাবে, উপ-সংকটকালীন সেটিংয়ে, লেখকরা $G_{n,p}$-এ যোগ করা প্রান্তের সংখ্যার অ্যাসিম্পটোটিক আচরণ নির্ধারণ করেছেন, প্রমাণ করেছেন যে প্রান্ত ঘনত্ব শুধুমাত্র একটি চিহ্নিতযোগ্য ধ্রুবক ফ্যাক্টর দ্বারা বৃদ্ধি পায়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. গ্রাফ বুটস্ট্র্যাপ পার্কোলেশনের মূল সমস্যা: টেমপ্লেট গ্রাফ $H$ এবং প্রাথমিক গ্রাফ $G \subseteq K_n$ দেওয়া হলে, $H$-বুটস্ট্র্যাপ পার্কোলেশন প্রক্রিয়া প্রতিটি পদক্ষেপে একটি নতুন প্রান্ত $e$ যোগ করে, শর্ত সাপেক্ষে যে $K_n$-এ $H$-এর একটি অনুলিপি বিদ্যমান থাকে যেখানে $e$ হল একমাত্র এখনও $G$-এ যোগ করা হয়নি এমন প্রান্ত। যদি $G$ চূড়ান্তভাবে সম্পূর্ণ গ্রাফ $K_n$-এ বিকশিত হয়, তবে $G$-কে দুর্বল $H$-সম্পৃক্ত বা $H$-পার্কোলিত বলা হয়।

२. থ্রেশহোল্ড সম্ভাব্যতার গুরুত্ব: Erdős-Rényi র্যান্ডম গ্রাফ $G_{n,p}$-এর জন্য, সংকটকালীন থ্রেশহোল্ড $p_c(n,H)$ হল $P(\langle G_{n,p}\rangle_H = K_n) \geq 1/2$ করার ন্যূনতম $p$ মান। এটি র্যান্ডম গ্রাফ তত্ত্বের একটি মূল সমস্যা, যা ক্লাসিক্যাল গ্রাফ সংযোগযোগ্যতা থ্রেশহোল্ডকে সাধারণীকরণ করে।

३. পরিচিত ফলাফলের সীমাবদ্ধতা:

• $r=3$: ক্লাসিক্যাল ফলাফল $p_c(n,K_3) \sim \log n/n$ (গ্রাফ সংযোগযোগ্যতা)
• $r=4$: $p_c(n,K_4) \sim (3n\log n)^{-1/2}$, ২-প্রতিবেশী গতিশীলতার সাথে সংযোগের মাধ্যমে প্রাপ্ত
• $r \geq 5$: Balogh এবং অন্যরা 8 শুধুমাত্র $p_c(n,K_r) = n^{-1/\lambda + o(1)}$ নির্ধারণ করেছেন, যেখানে $\lambda = \frac{\binom{r}{2}-2}{r-2}$, বহু-লগারিদমিক ফ্যাক্টর পর্যন্ত নির্ভুল

গবেষণার প্রেরণা

१. উন্মুক্ত সমস্যার সমাধান: Balogh এবং অন্যরা 8-এ তিনটি সমস্যা উত্থাপন করেছেন, এই পেপারটি শক্তিশালী আকারে তাদের দুটি সমাধান করে:

• সমস্যা 2: কোন $H$ তীক্ষ্ণ থ্রেশহোল্ড রাখে তা নির্ধারণ করা
• সমস্যা 3: $p_c(n,K_r)$ ধ্রুবক গুণক পর্যন্ত নির্ধারণ করা

२. $r \geq 5$-এর গুণগত পরিবর্তন: যখন $r \geq 5$, $K_r$ কঠোরভাবে ভারসাম্যপূর্ণ গ্রাফ (strictly balanced graph) হয়ে ওঠে, $(r-2)$-প্রতিবেশী গতিশীলতার সাথে সংযোগ ভেঙে যায়, এবং প্রক্রিয়াটি আর "নিউক্লিয়েশন" (nucleation)-এর মাধ্যমে প্রসারিত হয় না, বরং সম্পূর্ণ নতুন আচরণ প্যাটার্ন প্রদর্শন করে।

३. তাত্ত্বিক চ্যালেঞ্জ: সাক্ষী গ্রাফের কাঠামো বিশ্লেষণ করার জন্য নতুন সমন্বয়গত কৌশল বিকাশ করতে হবে, বিশেষত "শূন্য খরচ" প্রান্তের প্রসার নিয়ন্ত্রণ করা, যা এই পেপারের মূল প্রযুক্তিগত উদ্ভাবন।

মূল অবদান

१. তীক্ষ্ণ থ্রেশহোল্ড উপপাদ্য (উপপাদ্য 1.1): সমস্ত $r \geq 5$-এর জন্য, প্রমাণ করা হয়েছে $p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$ যেখানে $\gamma$ ফাস-ক্যাটালান সংখ্যার অ্যাসিম্পটোটিক বৃদ্ধির হার $\alpha_{\binom{r}{2}-2}$ দ্বারা অনন্যভাবে নির্ধারিত হয়: $(r-2)!\gamma^{r-2} = \alpha_{\binom{r}{2}-2} = \frac{(\binom{r}{2}-1)^{\binom{r}{2}-1}}{(\binom{r}{2}-2)^{\binom{r}{2}-2}}$

२. উপ-সংকটকালীন প্রান্ত সম্প্রসারণ উপপাদ্য (উপপাদ্য 1.2): উপ-সংকটকালীন অঞ্চল $p = (\bar{\gamma}n)^{-1/\lambda}$ ($\bar{\gamma} > \gamma$)-এ, প্রমাণ করা হয়েছে $|E(\langle G_{n,p}\rangle_{K_r})| \sim \rho \cdot p\binom{n}{2}$ যেখানে $\rho > 1$ হল সমীকরণ $\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$-এর ন্যূনতম মূল।

३. বৃক্ষ বিয়োজন পদ্ধতি: সাক্ষী গ্রাফের বৃক্ষ বিয়োজন কৌশল প্রবর্তন করা হয়েছে, যা যেকোনো সাক্ষী গ্রাফকে "খারাপ অংশ" (bad part) এবং একাধিক "বৃক্ষ অংশ" (tree parts)-এ বিয়োজিত করে, প্রমাণ করে যে বৃক্ষ অংশের সংখ্যা $O(\kappa)$, যেখানে $\kappa$ হল মোট খরচ।

४. $(r-2)^*$-বুটস্ট্র্যাপ পার্কোলেশন প্রক্রিয়া: পরিবর্তিত $(r-2)$-প্রতিবেশী গতিশীলতা প্রবর্তন করা হয়েছে, বৃক্ষ অংশের মধ্যে শূন্য খরচ প্রান্তের প্রসার নিয়ন্ত্রণ করার জন্য, যা তীক্ষ্ণ নিম্ন সীমা প্রমাণের মূল হাতিয়ার।

५. সমন্বয়গত গণনার নির্ভুলতা: সাক্ষী গ্রাফের গণনা $A^\sigma\sigma!$ থেকে $\gamma^\sigma\sigma!\sigma^{O(\kappa^2)}$-এ পরিমার্জিত করা হয়েছে, যা তীক্ষ্ণ ধ্রুবক প্রাপ্তির মূল চাবিকাঠি।

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

ইনপুট: Erdős-Rényi র্যান্ডম গ্রাফ $G_{n,p}$, টেমপ্লেট গ্রাফ $H = K_r$ ($r$-ক্লিক)
আউটপুট: সংকটকালীন থ্রেশহোল্ড $p_c(n,K_r)$ যেমন $P(\langle G_{n,p}\rangle_{K_r} = K_n)$ শূন্যের কাছাকাছি থেকে এক-এর কাছাকাছিতে লাফিয়ে যায়
সীমাবদ্ধতা: ধ্রুবক গুণক পর্যন্ত নির্ভুল হতে হবে, অর্থাৎ $p_c \sim (\gamma n)^{-1/\lambda}$-এ ধ্রুবক $\gamma$ নির্ধারণ করা

মূল ধারণা ব্যবস্থা

१. সাক্ষী গ্রাফ (Witness Graph)

$K_r$-গতিশীলতায় যোগ করা প্রতিটি প্রান্ত $e$-এর জন্য, একটি সাক্ষী গ্রাফ $W(e) \subseteq G$ বিদ্যমান থাকে যেমন $e \in E(\langle W(e)\rangle_{K_r})$। সাক্ষী গ্রাফ সাক্ষী গ্রাফ অ্যালগরিদম (WGA) দ্বারা পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত হয়:

• যদি $e \in E_0$ (প্রাথমিক প্রান্ত), তবে $W(e) = e$
• অন্যথায়, $K_r$-এর একটি অনুলিপি $H(e)$ নির্বাচন করুন যেমন $E(H(e)\setminus e) \subset \bigcup_{s<t}E_s$, এবং $W(e) = \bigcup_{f \in E(H(e)\setminus e)}W(f)$ সেট করুন

२. $K_r$-বৃক্ষ সাক্ষী গ্রাফ (Tree Witness Graph, TWG)

TWG হল প্রান্ত সংখ্যায় ন্যূনতম সাক্ষী গ্রাফ, পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত:

• ভিত্তি ক্ষেত্র: একক প্রান্ত $e$ হল ০-TWG
• পুনরাবৃত্তিমূলক নির্মাণ: $k$-TWG নিম্নলিখিত উপায়ে প্রাপ্ত হয়:
  • একটি $(k-1)$-TWG $T'$ নিন
  • এর মধ্যে একটি প্রান্ত $e'$ সরান
  • $e'$ সম্বলিত $K_r$ অনুলিপি $H'$ ($e'$ সরানো অবস্থায়) দিয়ে প্রতিস্থাপন করুন

মূল বৈশিষ্ট্য (লেম্মা 3.6):

• শীর্ষবিন্দু সংখ্যা: $v(T) = (r-2)k + 2$
• প্রান্ত সংখ্যা: $e(T) = \lambda(r-2)k + 1$, যেখানে $\lambda = \frac{\binom{r}{2}-2}{r-2}$
• বৃক্ষ কাঠামো: $\binom{r}{2}-1$ মাত্রার বৃক্ষ দ্বারা প্রতিনিধিত্ব করা যায়

३. ফাস-ক্যাটালান সংখ্যার সংযোগ

$k$-TWG-এর সংখ্যা (লেম্মা 3.8): $t(k) = \frac{((r-2)k)!}{(r-2)!^k} \text{FC}_{\binom{r}{2}-2}(k)$ যেখানে ফাস-ক্যাটালান সংখ্যা $\text{FC}_d(k) = \frac{1}{dk+1}\binom{(d+1)k}{k}$, অ্যাসিম্পটোটিক বৃদ্ধির হার $\alpha_d = \frac{(d+1)^{d+1}}{d^d}$।

উপরের সীমা প্রমাণ কৌশল (তৃতীয় অংশ)

মূল ধারণা

অতি-সংকটকালীন অঞ্চল $p = ((1+\epsilon)\gamma n)^{-1/\lambda}$-এ, প্রমাণ করা হয় যে উচ্চ সম্ভাবনায় সমস্ত প্রান্ত লগারিদমিক ক্রম TWG-এর মাধ্যমে যোগ করা যায়।

প্রযুক্তিগত পদক্ষেপ

१. ভারসাম্যপূর্ণ TWG-এর প্রত্যাশিত গণনা (লেম্মা 3.12): একটি নির্দিষ্ট প্রান্ত $e$-এর জন্য, ভারসাম্যপূর্ণ $k$-TWG (সমস্ত প্রধান শাখার ক্রম সমান) এর সংখ্যা $B_k^{(e)}$ সন্তুষ্ট করে: $\mathbb{E}(B_k^{(e)}) \sim \phi' \frac{(1+\epsilon)^{(r-2)k}}{k^{3((\binom{r}{2}-1)/2)}}p$ যখন $k = \beta\log n$ ($\beta$ যথেষ্ট বড়), প্রত্যাশিত মান $\gg n^c$।

२. আংশিক TWG-এর কাঠামো লেম্মা (লেম্মা 3.16): TWG $T$-এর সত্য উপগ্রাফ $S$-এর জন্য, তিনটি মূল পরামিতি সংজ্ঞায়িত করুন:

• প্রান্ত দক্ষতা: $\mathcal{E}(S) = \lambda\sigma(S) - e(S) \geq 0$
• বৃক্ষের মধ্যে ত্রুটি: $\mathcal{D}(S,T) = |P| \leq c\mathcal{E}(S) + 2$
• বৃক্ষ সম্প্রসারণযোগ্যতা: $\mathcal{T}(S) \leq c\mathcal{E}(S)$

যেখানে $\sigma(S) = |V(S)\setminus e|$ হল লক্ষ্য-অ-প্রান্ত শীর্ষবিন্দুর সংখ্যা।

३. Janson অসমতা প্রয়োগ: ভেরিয়েন্স পদ $\Delta = \sum_{T_1 \sim T_2}P(T_1,T_2 \subset G_{n,p})$ গণনা করুন, মূল বিষয় হল:

• যদি $S = T_1 \cap T_2$ এ $\mathcal{E}(S) > 0$, তবে $p^{\mathcal{E}(S)}$ পদ যথেষ্ট ক্ষয় প্রদান করে
• যদি $\mathcal{E}(S) = 0$, তবে $S$ শাখা সরানোর মাধ্যমে প্রাপ্ত হয়, ভারসাম্য ব্যবহার করে $\sigma(S) \geq ck$ পান

উপসংহার: $\Delta/\mu^2 \ll (k/n)^c$, Janson অসমতা $P(B_k^{(e)} = 0) \ll n^{-2}$ দেয়, যৌথ সীমা সম্পূর্ণ পার্কোলেশন প্রমাণ করে।

নিম্ন সীমা প্রমাণ কৌশল (৫-৬ অংশ)

প্রথম পর্যায়: মোটামুটি নিম্ন সীমা (৫ অংশ)

$p_c = \Omega(n^{-1/\lambda})$ প্রমাণ করুন।

१. বৃক্ষ বিয়োজন নির্মাণ: যেকোনো সাক্ষী গ্রাফ $W$-এর জন্য, লাল প্রান্ত অ্যালগরিদম (REA)-এর প্রতিটি পদক্ষেপে উপাদান $C$ বিয়োজিত করুন:

• খারাপ অংশ $B$ (সম্ভবত খালি)
• বৃক্ষ অংশ $T_1,\ldots,T_k$ (প্রতিটি $K_r$-বৃক্ষ)

সন্তুষ্ট করে:

• যদি $B = \emptyset$, তবে $k=1$ এবং $C$ বৃক্ষ উপাদান
• যদি $B \neq \emptyset$, প্রতিটি $T_i$ $B$-এর সাথে একক প্রান্তে ছেদ করে (ভিত্তি প্রান্ত বলা হয়), বৃক্ষ অংশ দুই-দুই প্রান্ত-বিচ্ছিন্ন

२. জটিলতা সীমা (লেম্মা 5.7): বৃক্ষ সংখ্যা $\tau(C)$ সংজ্ঞায়িত করুন REA-তে "আপস করা" (খারাপ অংশে যোগ করা) বৃক্ষ অংশের সংখ্যা হিসাবে, প্রমাণ করুন: $\tau(C) = O(\kappa(C))$ যেখানে $\kappa(C)$ হল খরচ (ব্যয়বহুল পদক্ষেপে জড়িত শীর্ষবিন্দু সংখ্যা)।

३. সমন্বয়গত গণনা (লেম্মা 5.10): আকার $\sigma$, খরচ $\kappa$ সাক্ষী গ্রাফের সংখ্যা সর্বাধিক: $A^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa)}$ যেখানে $A > \gamma$ কিছু ধ্রুবক।

४. প্রত্যাশা গণনা: লেম্মা 4.9 ($\chi(W) \geq \xi\kappa(W)$) এবং উপরোক্ত গণনা একত্রিত করে, $p = (\epsilon/n)^{1/\lambda}$ ($\epsilon < 1/\gamma$)-এর জন্য, সাক্ষী গ্রাফের প্রত্যাশিত সংখ্যা: $\sum_{\sigma,\kappa}\binom{n}{\sigma}A^\sigma\sigma!\sigma^{O(\kappa)}p^{\lambda\sigma+1+\xi\kappa} \leq (\log n)^{O(\log\log n)}p\sum_\sigma(\epsilon A)^\sigma \to 0$

দ্বিতীয় পর্যায়: তীক্ষ্ণ নিম্ন সীমা (৬ অংশ)

$p_c \sim (\gamma n)^{-1/\lambda}$ প্রমাণ করুন।

মূল চ্যালেঞ্জ: গণনা $A^\sigma$ থেকে $\gamma^\sigma$-এ উন্নত করতে হবে, পার্থক্য অ-TWG বৃক্ষ উপাদানের অবদানে।

মূল উদ্ভাবন १: $(r-2)^*$-বুটস্ট্র্যাপ পার্কোলেশন (সংজ্ঞা 6.2): $K_r$-বৃক্ষ $T$-এ পরিবর্তিত $(r-2)$-প্রতিবেশী প্রক্রিয়া সংজ্ঞায়িত করুন, বিশেষ পদক্ষেপ অনুমতি দিন:

• সাধারণ পদক্ষেপ: $\geq r-2$ সংক্রমিত প্রতিবেশী সহ শীর্ষবিন্দু সংক্রমিত হয়
• বিশেষ পদক্ষেপ: অভ্যন্তরীণ প্রান্ত $e$-এর জন্য, যদি $e$ সম্বলিত দুটি $K_r$ অনুলিপি $H_i,H_j$ এ, $H_i$ এ $r-4$ সংক্রমিত শীর্ষবিন্দু থাকে, $H_j$ এ 1 সংক্রমিত শীর্ষবিন্দু থাকে (উভয়ই $e$-তে নয়), তবে $e$-এর একটি শীর্ষবিন্দু সংক্রমিত করুন

মূল উদ্ভাবন २: তুলনা লেম্মা (লেম্মা 6.3): $T$ একটি $K_r$-বৃক্ষ, $G$ একটি গ্রাফ, $S = V(G)\cap V(T)$ সেট করুন। তবে: $\langle G \cup T\rangle_{K_r} \subset Q \cup T$ যেখানে $Q$ হল $V(G) \cup \langle S;T\rangle^*$-এর একটি ক্লিক, $\langle S;T\rangle^*$ হল $(r-2)^*$-BP-এর চূড়ান্ত সংক্রমিত সেট।

মূল উদ্ভাবন ३: সম্প্রসারণ লেম্মা (লেম্মা 6.5): $(r-2)^*$-BP প্রক্রিয়া সর্বাধিক রৈখিক সম্প্রসারণ: $|\langle S;T\rangle^*| = O(|S|)$।

প্রমাণ কৌশল:

• সংক্রমণের সময় প্রতিবেশী সংখ্যা ট্র্যাক করুন, $k$-পদক্ষেপ সংজ্ঞায়িত করুন (ঠিক $k$ প্রান্ত সংক্রমিত শীর্ষবিন্দুতে সংযুক্ত)
• অন্বেষণ প্রক্রিয়া (ক্রমান্বয়ে $K_r$ অনুলিপি প্রকাশ) দ্বারা অসমতা সিস্টেম প্রতিষ্ঠা করুন
• $r \geq 5$-এর কঠোর ভারসাম্য বৈশিষ্ট্য নিশ্চিত করতে ব্যবহার করুন যে বিশেষ পদক্ষেপ পরবর্তী সাধারণ পদক্ষেপ দ্বারা "ক্ষতিপূরণ" করা হয়

প্রসার লেম্মা (লেম্মা 6.7): যদি $|V(T)\cap V(G)| = x$, তবে $K_r$-গতিশীলতা $G\cup T$-এ $T$-এ সর্বাধিক $O(x)$ প্রান্ত ব্যবহার করে।

উন্নত সমন্বয়গত গণনা (লেম্মা 6.10): লেম্মা 6.8 (প্রতিটি সর্বাধিক বৃক্ষ অংশ সর্বাধিক $O(\kappa)$ লক্ষ্য প্রান্ত রাখে) ব্যবহার করে, প্রমাণ করুন: $\text{সাক্ষী গ্রাফ সংখ্যা} \leq \gamma^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa^2)}$

চূড়ান্ত যুক্তি: $p = ((1-\epsilon)\gamma n)^{-1/\lambda}$-এর জন্য, প্রত্যাশিত সংখ্যা: $\sum_{\sigma,\kappa}\binom{n}{\sigma}\gamma^\sigma\sigma!\sigma^{O(\kappa^2)}p^{\lambda\sigma+1+\xi\kappa} \leq (\log n)^{O((\log\log n)^2)}p\sum_\sigma(1-\epsilon)^\sigma \to 0$

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. বৃক্ষ বিয়োজনের উদ্ভাবনী ডিজাইন

• গতিশীল রক্ষণাবেক্ষণ বৈশিষ্ট্য: REA-এর প্রতিটি পদক্ষেপে গতিশীলভাবে বিয়োজন আপডেট করুন, তিনটি মূল বৈশিষ্ট্য বজায় রাখুন
• খারাপ বৃক্ষ পদক্ষেপের পরিচালনা: সহায়ক বৃক্ষ $T$ খারাপ অংশে যোগ করুন বৃক্ষ অংশ হিসাবে নয়, এটি বৃক্ষ অংশের সংখ্যা নিয়ন্ত্রণের মূল চাবিকাঠি
• খরচের সাথে ঘনিষ্ঠ সম্পর্ক: প্রমাণ করুন $\omega(W) = O(\kappa(W))$ এবং $\sum|V(T_i)| = \sigma + O(\kappa)$

२. $(r-2)^*$-BP-এর চতুর ডিজাইন

• অগ্রাধিকার প্রক্রিয়া: সাধারণ পদক্ষেপ অগ্রাধিকার দিন, শুধুমাত্র প্রয়োজনে বিশেষ পদক্ষেপ ব্যবহার করুন
• $K_r$-গতিশীলতার সাথে সামঞ্জস্য: বিশেষ পদক্ষেপ সঠিকভাবে প্রান্ত প্রসার "হিঞ্জ" (hinge)-এর মাধ্যমে শর্ত ক্যাপচার করে
• রৈখিক সম্প্রসারণের প্রমাণ: সূক্ষ্ম গণনা যুক্তির মাধ্যমে, $r \geq 5$ ব্যবহার করে নিশ্চিত করুন যে বিশেষ পদক্ষেপের খরচ পরবর্তী পদক্ষেপ দ্বারা শোষিত হয়

३. কঠোর ভারসাম্যের গভীর প্রয়োগ

সংজ্ঞা (সংজ্ঞা 3.17): গ্রাফ $H$ কঠোরভাবে ভারসাম্যপূর্ণ যদি সমস্ত $3 \leq v(F) < v(H)$ উপগ্রাফ $F$-এর জন্য: $\frac{e(F)-1}{v(F)-2} < \lambda(H) = \frac{e(H)-2}{v(H)-2}$

মূল প্রয়োগ:

• লেম্মা 3.20: আংশিক TWG-এর মধ্যে পাতার প্রান্ত দক্ষতা নিয়ন্ত্রণ করুন
• বিবৃতি 5.3: IntR পদক্ষেপ বৃক্ষ অংশ জুড়ে প্রসারিত হবে না প্রমাণ করুন
• লেম্মা 6.3-এর প্রমাণ: নিশ্চিত করুন যে বিরোধী ক্ষেত্র ঘটবে না

४. বহু-স্কেল বিশ্লেষণ

• লগারিদমিক স্কেল: TWG-এর ক্রম $k = O(\log n)$
• দ্বি-লগারিদমিক স্কেল: খরচ $\kappa = O(\log\log n)$
• ধ্রুবক স্কেল: বৃক্ষ অংশের লক্ষ্য প্রান্ত সংখ্যা $O(\kappa)$

পরীক্ষামূলক সেটআপ

সিমুলেশন অধ্যয়ন (অংশ 8.2)

পরামিতি সেটিং:

• শীর্ষবিন্দু সংখ্যা: $n = 2000$
• টেমপ্লেট গ্রাফ: $K_5$ ($r=5$)
• তিনটি পর্যায়: উপ-সংকটকালীন, সংকটকালীন কাছাকাছি, অতি-সংকটকালীন

ভিজ্যুয়ালাইজেশন পদ্ধতি:

• ম্যাট্রিক্স প্রতিনিধিত্ব: বিন্দু $(i,j)$ প্রান্ত $\{v_i,v_j\}$ প্রতিনিধিত্ব করে
• রঙ এনকোডিং: গভীর নীল (প্রাথমিক প্রান্ত) → হলুদ (শেষে যোগ করা), সাদা (যোগ করা হয়নি)
• শীর্ষবিন্দু সাজানো: প্রাথমিক যোগ করা প্রান্তের শীর্ষবিন্দুর দিকে পক্ষপাতী

পর্যবেক্ষণ ফলাফল: १. উপ-সংকটকালীন: প্রান্ত ঘনত্ব শুধুমাত্র ধ্রুবক ফ্যাক্টর দ্বারা বৃদ্ধি, 100 শীর্ষবিন্দুতে স্থানীয়করণ २. অতি-সংকটকালীন: প্রাথমিক পর্যায়ে ধীর বৃদ্ধি, তারপর "বিস্ফোরণ" সম্পূর্ণ পার্কোলেশন ३. রাউন্ড সংখ্যা: উপ-সংকটকালীন 4 রাউন্ড, অতি-সংকটকালীন 15 রাউন্ড

সীমাবদ্ধতা আলোচনা:

• $L = (np^{r-2})^{-1/(r-3)} \approx 1.6$ $n=2000,r=5$-এর জন্য খুব ছোট
• প্রকৃত পর্যবেক্ষণ 3-প্রতিবেশী গতিশীলতা-প্রভাবিত আচরণ
• সত্যিকারের $r \geq 5$ আচরণ পর্যবেক্ষণ করতে $n$ অত্যন্ত বড় প্রয়োজন ("ধীর বার্ধক্য" ঘটনা)

পরীক্ষামূলক ফলাফল

তাত্ত্বিক ফলাফল যাচাইকরণ

উপপাদ্য 1.1-এর নির্দিষ্ট ফর্ম ($r=5$): $p_c(n,K_5) \sim (\gamma n)^{-1/3}, \quad \gamma = \left(\frac{\alpha_8}{6}\right)^{1/3} = \left(\frac{9^9}{8^8 \cdot 6}\right)^{1/3} \approx 1.107$

উপপাদ্য 1.2-এর নির্দিষ্ট ফর্ম ($r=5$, $\bar{\gamma} = 1.2$):

• $\bar{\alpha} = 6 \times 1.2^3 \approx 10.368$
• $\rho$ সন্তুষ্ট করে $\rho^9 = 10.368(\rho-1)$, সংখ্যাগত সমাধান $\rho \approx 1.52$
• প্রান্ত ঘনত্ব বৃদ্ধি প্রায় 52%

সংখ্যাগত যাচাইকরণ (চিত্র 1)

উপ-সংকটকালীন ক্ষেত্র (চিত্র 1a):

• প্রাথমিক প্রান্ত সংখ্যা: $\approx p\binom{n}{2} \approx 1000$
• চূড়ান্ত প্রান্ত সংখ্যা: $\approx 1.5 \times 1000 = 1500$
• তাত্ত্বিক পূর্বাভাস $\rho \approx 1.52$ সাথে সামঞ্জস্যপূর্ণ

অতি-সংকটকালীন ক্ষেত্র (চিত্র 1c):

• সমস্ত $\binom{2000}{2} \approx 2\times 10^6$ প্রান্ত চূড়ান্তভাবে যোগ করা হয়
• দুই-পর্যায় উপস্থাপন: ধীর বৃদ্ধি (গভীর নীল থেকে সবুজ) + বিস্ফোরণ সম্পূর্ণতা (কমলা থেকে হলুদ)

মূল আবিষ্কার

१. থ্রেশহোল্ডের তীক্ষ্ণতা: উপ-সংকটকালীন থেকে অতি-সংকটকালীনে, পার্কোলেশন সম্ভাবনা শূন্যের কাছাকাছি থেকে এক-এর কাছাকাছিতে লাফিয়ে যায়, উইন্ডো প্রস্থ $o(p_c)$

२. TWG-এর আধিপত্য:

• অতি-সংকটকালীন: প্রায় সমস্ত প্রান্ত লগারিদমিক ক্রম TWG-এর মাধ্যমে যোগ করা হয়
• উপ-সংকটকালীন: $\rho$ ফ্যাক্টর সম্পূর্ণভাবে TWG অবদান দ্বারা নির্ধারিত

३. খরচের ভূমিকা:

• অ-TWG সাক্ষী গ্রাফের খরচ $\kappa \geq 1$ অতিরিক্ত ফ্যাক্টর $p^{\xi\kappa}$ প্রদান করে
• এটি তাদের সংখ্যা বৃদ্ধি ($\gamma^\sigma$ থেকে $\gamma^\sigma\sigma^{O(\kappa^2)}$) প্রতিহত করার জন্য যথেষ্ট

४. $r \geq 5$-এর গুণগত পরিবর্তন:

• মধ্যবর্তী স্কেলের পার্কোলেশন উপগ্রাফ বিদ্যমান নেই ($1 \ll k \ll L$)
• $r=4$-এর নিউক্লিয়েশন প্রক্রিয়া থেকে মৌলিকভাবে আলাদা

সম্পর্কিত কাজ

বুটস্ট্র্যাপ পার্কোলেশনের ঐতিহাসিক প্রসঙ্গ

१. ক্লাসিক্যাল শীর্ষবিন্দু বুটস্ট্র্যাপ পার্কোলেশন:

• Chalupa এবং অন্যরা 18: পরিসংখ্যানগত পদার্থবিজ্ঞানে উৎপত্তি
• Aizenman-Lebowitz 1: $\mathbb{Z}^d$-এ মেটাস্টেবিলিটি বৈশিষ্ট্য
• Holroyd 30: দ্বিমাত্রিক তীক্ষ্ণ মেটাস্টেবিলিটি থ্রেশহোল্ড
• Balogh এবং অন্যরা 7: সমস্ত মাত্রায় তীক্ষ্ণ থ্রেশহোল্ড
• Balister এবং অন্যরা 6: একঘেয়ে সেলুলার অটোমেটার সর্বজনীনতা অনুমান

२. র্যান্ডম গ্রাফে $r$-প্রতিবেশী গতিশীলতা:

• Janson এবং অন্যরা 31: $G_{n,p}$-এ বিস্তারিত গবেষণা
• মূল পার্থক্য: শীর্ষবিন্দু সংক্রমণ বনাম প্রান্ত সংক্রমণ

३. গ্রাফ বুটস্ট্র্যাপ পার্কোলেশন:

• Bollobás 15: দুর্বল সম্পৃক্ততার প্রবর্তন, $r \leq 6$-এর ন্যূনতম প্রান্ত সংখ্যা নির্ধারণ
• Alon 2, Frankl 23, Kalai 32,33, Lovász 36: সমস্ত $r$-এ সাধারণীকরণ
• Balogh এবং অন্যরা 9: হাইপারগ্রাফ সাধারণীকরণ
• Balogh এবং অন্যরা 8: র্যান্ডম গ্রাফে থ্রেশহোল্ড, এই পেপারের সরাসরি পূর্বসূরী

এই পেপারের অবস্থান

8-এর তুলনায় অগ্রগতি:

• 8-এর ফলাফল: $p_c(n,K_r) = n^{-1/\lambda+o(1)}$ (বহু-লগারিদমিক নির্ভুলতা)
• এই পেপার: $p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$ (ধ্রুবক নির্ভুলতা)
• সমস্যা 2 (তীক্ষ্ণতা) এবং সমস্যা 3 (ধ্রুবক ফ্যাক্টর) সমাধান করুন

প্রযুক্তিগত তুলনা:

• 8: $K_r$-সিঁড়ি গ্রাফ + Aizenman-Lebowitz বৈশিষ্ট্য ব্যবহার করুন
• এই পেপার: বৃক্ষ বিয়োজন + $(r-2)^*$-BP + ফাস-ক্যাটালান গণনা

অন্যান্য টেমপ্লেট গ্রাফ $H$-এর সাথে সম্পর্ক:

• Korándi-Sudakov 35 এবং অন্যরা: $G_{n,p}$-এ সম্পৃক্ততা সমস্যা
• Bayraktar-Chakraborty 12, Bidgoli এবং অন্যরা 13: $K_{r,s}$-পার্কোলেশন
• সাধারণ $H$-এর বোঝাপড়া ব্যাপকভাবে উন্মুক্ত (সমস্যা 1 8-এ)

ক্রস-ডিসিপ্লিনারি সংযোগ

হাইপারগ্রাফ বুটস্ট্র্যাপ পার্কোলেশন:

• Lubetzky-Peled 37: স্ট্যাকড ত্রিভুজকরণের ফাস-ক্যাটালান-টাইপ থ্রেশহোল্ড
• বাহ্যিক বীজগণিত শিফট ব্যবহার করুন, এই পেপারের সমন্বয়গত পদ্ধতির পরিপূরক

কঠোরতা তত্ত্ব:

• Kalai 32: দুর্বল সম্পৃক্ততা এবং $(r-2)$-কঠোরতার সংযোগ
• এই পেপার চেষ্টা করে কিন্তু কঠোরতা তত্ত্ব প্রয়োগ করতে ব্যর্থ (অংশ 8.4)
• উন্মুক্ত সমস্যা: প্রসার লেম্মা শক্তিশালী করতে কঠোরতা তত্ত্ব ব্যবহার করা যায়?

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. $r \geq 5$-এর থ্রেশহোল্ড সমস্যা সম্পূর্ণভাবে সমাধান করুন: $p_c(n,K_r) = \frac{1}{\gamma n^{1/\lambda}}(1+o(1))$ যেখানে $\gamma,\lambda$ ফাস-ক্যাটালান সংখ্যার অ্যাসিম্পটোটিক বৈশিষ্ট্য দ্বারা অনন্যভাবে নির্ধারিত।

२. উপ-সংকটকালীন প্রান্ত সম্প্রসারণের নির্ভুল চিত্রকল্প: প্রান্ত ঘনত্ব বৃদ্ধি ফ্যাক্টর $\rho$ জেনারেটিং ফাংশন সমীকরণ $\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$ দ্বারা নির্ধারিত।

३. $r \geq 5$-এর নতুন প্রক্রিয়া প্রকাশ করুন:

• নিউক্লিয়েশনের মাধ্যমে প্রসার নয়
• TWG প্রভাবশালী পার্কোলেশন প্রক্রিয়া
• কঠোর ভারসাম্য মূল চাবিকাঠি

সীমাবদ্ধতা

१. সংকটকালীন উইন্ডো অনির্ধারিত:

• দ্বিতীয় ক্রম পদ অজানা
• সংকটকালীন উইন্ডো প্রস্থ $\omega(n)$ অনির্ধারিত
• সংকটকালীন আচরণের সূক্ষ্ম কাঠামো অস্পষ্ট

२. "সংকটকালীন ফোঁটা" চিহ্নিত করা হয়নি:

• তাত্ত্বিক পূর্বাভাস স্কেল $L = n^{(r-4)/(r^2-r-4)+o(1)}$
• কিন্তু প্রমাণ এই ধরনের উপগ্রাফ সরাসরি নির্মাণ করে না
• নিউক্লিয়েশন প্রক্রিয়ার সাথে সম্পর্ক অস্পষ্ট

३. সিমুলেশনের সীমাবদ্ধতা:

• সত্যিকারের আচরণ পর্যবেক্ষণ করতে অত্যন্ত বড় $n$ প্রয়োজন ("ধীর বার্ধক্য")
• বর্তমান সিমুলেশন প্রধানত $(r-2)$-প্রতিবেশী গতিশীলতা প্রদর্শন করে

४. পদ্ধতির প্রয়োগযোগ্যতার পরিসীমা:

• কঠোরভাবে $r \geq 5$ (কঠোর ভারসাম্য)-এর উপর নির্ভরশীল
• সাধারণ $H$-এ সাধারণীকরণ নতুন চিন্তাভাবনা প্রয়োজন
• কঠোরতা তত্ত্ব পদ্ধতি সফল হয়নি

ভবিষ্যত দিকনির্দেশনা

१. সংকটকালীন ঘটনার সূক্ষ্ম বোঝাপড়া (অংশ 8.1):

• সংকটকালীন উইন্ডো প্রস্থ নির্ধারণ করুন
• $G(n,m)$ বিবর্তনে "বিস্ফোরণ" পদক্ষেপ চিত্রকল্প করুন
• স্কেল $L$-এর সংকটকালীন ফোঁটা চিহ্নিত করুন

२. কঠোরভাবে ভারসাম্যপূর্ণ গ্রাফে সাধারণীকরণ (অংশ 8.3):

• অনুমান: সমস্ত কঠোরভাবে ভারসাম্যপূর্ণ $H$ $p_c = \Theta(n^{-1/\lambda})$ সন্তুষ্ট করে
• উপরের সীমা ইতিমধ্যে 10 দ্বারা প্রমাণিত
• নিম্ন সীমা বৃক্ষ বিয়োজন এবং প্রসার লেম্মা সাধারণীকরণ প্রয়োজন
• মূল চাবিকাঠি: অতিরিক্ত ফ্যাক্টর $p^{\xi\kappa}$ ($\xi > 0$) ব্যবহার করুন

३. সাধারণ টেমপ্লেট গ্রাফ $H$ (8-এ সমস্যা 1):

• সমস্ত $H$-এর জন্য $p_c(n,H)$ নির্ধারণ করুন
• তীক্ষ্ণতা শর্ত নির্ধারণ করুন
• ভারসাম্যপূর্ণ কিন্তু কঠোরভাবে ভারসাম্যপূর্ণ নয় এমন গ্রাফের আচরণ

४. কঠোরতা তত্ত্বের প্রয়োগ (অংশ 8.4):

• উন্মুক্ত সমস্যা: প্রসার লেম্মা শক্তিশালী করতে $(r-2)$-কঠোরতা ব্যবহার করা যায়?
• অনুমান: $G\cup T$-এর $(r-2)$-কঠোরতা ম্যাট্রয়েডে বন্ধ $C$ সর্বাধিক $T$-এ $O(x)$ শীর্ষবিন্দু নতুন প্রতিবেশী পায়

५. সমন্বয়গত প্রমাণের সাধারণীকরণ:

• এই পেপারের পদ্ধতি হাইপারগ্রাফ বুটস্ট্র্যাপ পার্কোলেশনে 37 প্রয়োগযোগ্য হতে পারে
• বীজগণিত পদ্ধতির সমন্বয়গত বিকল্প প্রদান করুন

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক গভীরতা:

• দীর্ঘমেয়াদী উন্মুক্ত সমস্যা সম্পূর্ণভাবে সমাধান করুন, ধ্রুবক ফ্যাক্টর পর্যন্ত নির্ভুল
• $r \geq 5$-এর সারমর্ম নতুন ঘটনা প্রকাশ করুন (অ-নিউক্লিয়েশন প্রক্রিয়া)
• ফাস-ক্যাটালান সংখ্যার সাথে গভীর সংযোগ প্রতিষ্ঠা করুন

२. প্রযুক্তিগত উদ্ভাবন:

• বৃক্ষ বিয়োজন: জটিল সাক্ষী গ্রাফকে নিয়ন্ত্রণযোগ্য কাঠামোতে সুন্দরভাবে বিয়োজিত করুন
• $(r-2)^*$-BP: প্রান্ত গতিশীলতা এবং শীর্ষবিন্দু গতিশীলতা চতুরভাবে সেতু করুন
• বহু-স্কেল বিশ্লেষণ: তিনটি স্কেলে সূক্ষ্ম নিয়ন্ত্রণ $O(\log n)$, $O(\log\log n)$, $O(1)$

३. প্রমাণের শক্তিশালীতা:

• অংশ 5-এর মোটামুটি নিম্ন সীমা ইতিমধ্যে সমস্যা 3 উত্তর দেয়
• অংশ 6-এর সূক্ষ্মতা মডুলার উন্নতি
• পদ্ধতিবিদ্যা অন্যান্য সমস্যায় সম্ভাব্য প্রয়োগযোগ্যতা

४. লেখার গুণমান:

• অংশ 2-এর সংক্ষিপ্ত বিবরণ চ্যালেঞ্জ এবং ধারণা স্পষ্টভাবে বর্ণনা করে
• প্রযুক্তিগত বিবরণ ভালভাবে সংগঠিত (তিন অংশ: প্রস্তুতি, মোটামুটি, তীক্ষ্ণ)
• চিত্র এবং সিমুলেশন বোঝাপড়া বৃদ্ধি করে

অসুবিধা

१. প্রযুক্তিগত জটিলতা:

• প্রমাণ অত্যন্ত প্রযুক্তিগত, বিশেষত অংশ 6
• একাধিক সহায়ক লেম্মা এবং সূক্ষ্ম অনুমান প্রয়োজন
• কিছু যুক্তি (যেমন লেম্মা 6.5-এর প্রমাণ) অত্যন্ত দীর্ঘ

२. কঠোরতা পদ্ধতির ব্যর্থতা:

• লেখকরা চেষ্টা করেন কিন্তু কঠোরতা তত্ত্ব প্রয়োগ করতে ব্যর্থ হন
• ব্যর্থতার কারণ পর্যাপ্তভাবে ব্যাখ্যা করা হয়নি
• পদ্ধতির সাধারণীকরণ সীমাবদ্ধ করতে পারে

३. সিমুলেশনের সীমাবদ্ধতা:

• স্বীকার করুন যে $n=2000$ সত্যিকারের আচরণ পর্যবেক্ষণ করতে অপর্যাপ্ত
• বৃহত্তর স্কেলের সংখ্যাগত পরীক্ষা প্রদান করা হয়নি
• সংকটকালীন উইন্ডোর সংখ্যাগত অন্বেষণ অনুপস্থিত

४. সাধারণীকরণের বাধা:

• $K_r$-এর বিশেষ বৈশিষ্ট্যের উপর গুরুতরভাবে নির্ভরশীল (ক্লিক কাঠামো)
• সাধারণ কঠোরভাবে ভারসাম্যপূর্ণ গ্রাফে সাধারণীকরণের পথ অস্পষ্ট
• কঠোরভাবে ভারসাম্যপূর্ণ নয় এমন ক্ষেত্র সম্পূর্ণ উন্মুক্ত

প্রভাব

१. তাত্ত্বিক অবদান:

• Balogh-Bollobás-Morris-এর দুটি উন্মুক্ত সমস্যা সমাধান করুন
• গ্রাফ বুটস্ট্র্যাপ পার্কোলেশন এবং ফাস-ক্যাটালান সংখ্যার নতুন সংযোগ প্রতিষ্ঠা করুন
• $r \geq 5$-এর জন্য সম্পূর্ণ তাত্ত্বিক চিত্র প্রদান করুন

२. পদ্ধতিবিদ্যা অবদান:

• বৃক্ষ বিয়োজন কৌশল অন্যান্য বুটস্ট্র্যাপ প্রক্রিয়ায় প্রয়োগযোগ্য হতে পারে
• $(r-2)^*$-BP নতুন বিশ্লেষণ হাতিয়ার প্রদান করে
• সমন্বয়গত গণনার সূক্ষ্মতা কৌশল সর্বজনীন মূল্য রাখে

३. ব্যবহারিক মূল্য:

• তাত্ত্বিক শক্তিশালী, সরাসরি প্রয়োগ সীমিত
• কিন্তু নেটওয়ার্ক প্রসার, ক্যাসকেড ব্যর্থতার জন্য গাণিতিক ভিত্তি প্রদান করে
• সেলুলার অটোমেটা ডিজাইনের তাত্ত্বিক নির্দেশনা

४. পুনরুৎপাদনযোগ্যতা:

• প্রমাণ সম্পূর্ণ স্ব-নিহিত
• সিমুলেশন কোড প্রকাশিত নয় কিন্তু পদ্ধতি স্পষ্টভাবে বর্ণিত
• তাত্ত্বিক ফলাফল পাঠক দ্বারা যাচাই করা যায়

প্রয়োগযোগ্য দৃশ্যকল্প

१. সরাসরি প্রয়োগ:

• র্যান্ডম গ্রাফে $K_r$-পার্কোলেশন বিশ্লেষণ ($r \geq 5$)
• নির্ভুল থ্রেশহোল্ড ধ্রুবক প্রয়োজন এমন প্রয়োগ
• উপ-সংকটকালীন প্রান্ত সম্প্রসারণের পূর্বাভাস

२. পদ্ধতি প্রয়োগ:

• অন্যান্য কঠোরভাবে ভারসাম্যপূর্ণ গ্রাফের পার্কোলেশন
• হাইপারগ্রাফ বুটস্ট্র্যাপ পার্কোলেশন (37 এর মতো)
• বৃক্ষ-সদৃশ সাক্ষী কাঠামো সহ প্রসার প্রক্রিয়া

३. তাত্ত্বিক অনুপ্রেরণা:

• তীক্ষ্ণ থ্রেশহোল্ডের সমন্বয়গত প্রক্রিয়া বোঝা
• বহু-স্কেল বিশ্লেষণ কৌশল
• বিশ্লেষণ হাতিয়ার হিসাবে পরিবর্তিত বুটস্ট্র্যাপ প্রক্রিয়া

রেফারেন্স (মূল উদ্ধৃতি)

१. 1 Aizenman & Lebowitz (1988): প্রথমবার বুটস্ট্র্যাপ পার্কোলেশনের Aizenman-Lebowitz বৈশিষ্ট্য পর্যবেক্ষণ করুন २. 8 Balogh, Bollobás & Morris (2012): এই পেপার সমাধান করে এমন উন্মুক্ত সমস্যার উৎস ३. 15 Bollobás (1968): দুর্বল সম্পৃক্ততা ধারণার উৎপত্তি ४. 32,33 Kalai (1984,1985): দুর্বল সম্পৃক্ততা এবং কঠোরতা তত্ত্বের সংযোগ ५. 31 Janson এবং অন্যরা (2012): র্যান্ডম গ্রাফে $r$-প্রতিবেশী গতিশীলতার বিস্তারিত গবেষণা ६. 37 Lubetzky & Peled (2023): হাইপারগ্রাফে ফাস-ক্যাটালান থ্রেশহোল্ড, বীজগণিত পদ্ধতি ব্যবহার করুন ७. 40 Riedl (2012): বৃক্ষে বুটস্ট্র্যাপ পার্কোলেশন বিশ্লেষণ, এই পেপারের লেম্মা 6.5-এর প্রমাণ অনুপ্রাণিত করে

সংক্ষিপ্তসার

এই পেপারটি গ্রাফ বুটস্ট্র্যাপ পার্কোলেশন তত্ত্বে একটি বড় অগ্রগতি, যা $r \geq 5$ ক্ষেত্রে $K_r$-পার্কোলেশনের তীক্ষ্ণ থ্রেশহোল্ড সমস্যা সম্পূর্ণভাবে সমাধান করে। মূল উদ্ভাবন হল: (१) বৃক্ষ বিয়োজন কৌশল সাক্ষী গ্রাফের জটিলতা সিস্টেমেটিকভাবে নিয়ন্ত্রণ করে, (२) $(r-2)^*$-বুটস্ট্র্যাপ পার্কোলেশন প্রক্রিয়া শূন্য খরচ প্রান্তের প্রসার চতুরভাবে বিশ্লেষণ করে, (३) ফাস-ক্যাটালান সংখ্যার সাথে গভীর সংযোগ থ্রেশহোল্ড ধ্রুবকের সমন্বয়গত সারমর্ম প্রকাশ করে। প্রমাণ $r \geq 5$ সময় $K_r$-এর কঠোর ভারসাম্য বৈশিষ্ট্য সম্পূর্ণভাবে ব্যবহার করে, যা $r=4$ ক্ষেত্রের সাথে মৌলিক পার্থক্য। যদিও প্রযুক্তিগত জটিলতা উচ্চ এবং সাধারণীকরণের পথ সম্পূর্ণ স্পষ্ট নয়, এই পেপারের পদ্ধতিবিদ্যা অবদান এবং তাত্ত্বিক গভীরতা এটিকে এই ক্ষেত্রে একটি মাইলফলক কাজ করে তোলে, আরও সাধারণ গ্রাফ বুটস্ট্র্যাপ পার্কোলেশন এবং সম্পর্কিত প্রসার প্রক্রিয়া বোঝার জন্য একটি দৃঢ় ভিত্তি স্থাপন করে।