2025-11-17T08:22:14.076517

Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

Diskin, Krivelevich
We provide sufficient conditions for a regular graph $G$ of growing degree $d$, guaranteeing a phase transition in its random subgraph $G_p$ similar to that of $G(n,p)$ when $p\cdot d\approx 1$. These conditions capture several well-studied graphs, such as (percolation on) the complete graph $K_n$, the binary hypercube $Q^d$, $d$-regular expanders, and random $d$-regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that $G$ is a $d$-regular graph on $n$ vertices, with $d=ω(1)$. Let $ε>0$ be a small constant, and let $p=\frac{1+ε}{d}$. Let $y(ε)$ be the survival probability of a Galton-Watson tree with offspring distribution Po$(1+ε)$. We show that if $G$ satisfies a (very) mild edge expansion requirement, and if one has fairly good control on the expansion of small sets in $G$, then typically the percolated random subgraph $G_p$ contains a unique giant component of asymptotic order $y(ε)n$, and all the other components in $G_p$ are of order $O(\log n/ε^2)$. We also show that this result is tight, in the sense that if one asks for a slightly weaker control on the expansion of small sets in $G$, then there are $d$-regular graphs $G$ on $n$ vertices, where typically the second largest component is of order $Ω(d\log (n/d))=ω(\log n)$. This is the first of a two-part sequence of papers. In the subsequent work, we consider supercritical percolation on regular graphs of constant degree, and establish similar sufficient (and essentially tight) conditions in that setting.
academic

উপাদান, বড় এবং ছোট, যেমন হওয়া উচিত I: নিয়মিত গ্রাফে ক্রমবর্ধমান ডিগ্রির উপর অতিসংকটপূর্ণ অনুস্যান্দন

মৌলিক তথ্য

  • পত্রের ID: 2408.04597
  • শিরোনাম: উপাদান, বড় এবং ছোট, যেমন হওয়া উচিত I: নিয়মিত গ্রাফে ক্রমবর্ধমান ডিগ্রির উপর অতিসংকটপূর্ণ অনুস্যান্দন
  • লেখক: সাহার ডিসকিন, মাইকেল ক্রিভেলেভিচ (তেল আভিভ বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা), math.PR (সম্ভাব্যতা তত্ত্ব)
  • প্রকাশনার সময়: ২০২৪ সালের আগস্টে জমা দেওয়া, ২০২৫ সালের নভেম্বরে সংশোধিত সংস্করণ
  • পত্রের লিঙ্ক: https://arxiv.org/abs/2408.04597

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

এই পত্রটি ডিগ্রি বৃদ্ধিশীল d-নিয়মিত গ্রাফ G-এর জন্য যথেষ্ট শর্ত প্রদান করে যাতে এর র্যান্ডম সাবগ্রাফ Gp, p·d≈1 এ ক্লাসিক্যাল Erdős-Rényi র্যান্ডম গ্রাফ G(n,p)-এর মতো পর্যায় রূপান্তর প্রদর্শন করে। যখন G হল n শীর্ষবিন্দুর একটি d-নিয়মিত গ্রাফ (d=ω(1)), p=(1+ε)/d, এবং G অত্যন্ত মৃদু প্রান্ত সম্প্রসারণ প্রয়োজনীয়তা এবং ছোট সেটগুলির সম্প্রসারণের ভাল নিয়ন্ত্রণ সন্তুষ্ট করে, তখন সাধারণত Gp একটি অনন্য বিশাল সংযুক্ত উপাদান ধারণ করে যার আকার y(ε)n (যেখানে y(ε) হল পরামিতি Po(1+ε) সহ Galton-Watson গাছের বেঁচে থাকার সম্ভাবনা), যখন অন্যান্য সমস্ত সংযুক্ত উপাদানের আকার O(log n/ε²)। লেখকরা আরও প্রমাণ করেন যে এই ফলাফলটি কঠোর: যদি ছোট সেটগুলির সম্প্রসারণ নিয়ন্ত্রণ সামান্য দুর্বল হয়, তবে d-নিয়মিত গ্রাফ বিদ্যমান যেখানে দ্বিতীয় বৃহত্তম সংযুক্ত উপাদানের আকার Ω(d log(n/d))=ω(log n)।

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

গবেষণা সমস্যা

এই পত্রটি নিয়মিত গ্রাফে অতিসংকটপূর্ণ অনুস্যান্দন (supercritical percolation) সমস্যা অধ্যয়ন করে: একটি হোস্ট গ্রাফ G এবং সম্ভাবনা p∈0,1 দেওয়া হলে, স্বাধীনভাবে সম্ভাবনা p সহ G-এর প্রতিটি প্রান্ত ধরে রেখে অনুস্যান্দন র্যান্ডম সাবগ্রাফ Gp পাওয়া যায়। মূল প্রশ্ন হল: কোন ধরনের নিয়মিত গ্রাফ G Erdős-Rényi সংযুক্ত উপাদান ঘটনা (ERCP) প্রদর্শন করতে পারে, অর্থাৎ অতিসংকটপূর্ণ পর্যায়ে p=(1+ε)/d, একটি অনন্য বিশাল সংযুক্ত উপাদান এবং অন্যান্য সমস্ত সংযুক্ত উপাদান লগারিদমিক আকারের সাথে উপস্থিত হয়?

সমস্যার গুরুত্ব

  1. পর্যায় রূপান্তর ঘটনার একীভূত বোঝাপড়া: Erdős-Rényi ১৯৬০ সালে প্রমাণ করেছিলেন যে ক্লাসিক্যাল র্যান্ডম গ্রাফ G(n,p) p·n≈1 এ পর্যায় রূপান্তর প্রদর্শন করে। এই ঘটনাটি বিভিন্ন বিশেষ গ্রাফে স্বাধীনভাবে প্রমাণিত হয়েছে (সম্পূর্ণ গ্রাফ, হাইপারকিউব, সিউডোর্যান্ডম গ্রাফ ইত্যাদি), কিন্তু প্রমাণ পদ্ধতি বৈচিত্র্যময়। এই পত্রটি একটি একীভূত কাঠামো প্রদান করার লক্ষ্য রাখে।
  2. সর্বজনীন শ্রেণীর বৈশিষ্ট্য: কোন গ্রাফ কাঠামোগত বৈশিষ্ট্যগুলি ERCP-এর উপস্থিতি নির্ধারণ করে তা চিহ্নিত করা অনুস্যান্দন তত্ত্বে সর্বজনীনতা (universality) বোঝার জন্য সহায়তা করে।
  3. তাত্ত্বিক সম্পূর্ণতা: এটি জানা যায় যে কিছু গ্রাফ (যেমন সংযুক্ত নয় এমন ক্লিকের সংমিশ্রণ) ERCP প্রদর্শন করে না, তাই সীমানা শর্তগুলি সঠিকভাবে বৈশিষ্ট্যযুক্ত করার প্রয়োজন।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  • বিশেষ কাঠামো নির্ভরতা: হাইপারকিউবের প্রমাণ এর পণ্য কাঠামো এবং Harper সমপরিধি অসমতার উপর নির্ভর করে; সিউডোর্যান্ডম গ্রাফের প্রমাণ সম্প্রসারণ মিশ্রণ লেম্মার উপর নির্ভর করে
  • প্রমাণ কৌশল বিচ্ছিন্ন: বিভিন্ন গ্রাফ শ্রেণীর জন্য সম্পূর্ণ ভিন্ন প্রমাণ কৌশল প্রয়োজন, একীভূত দৃষ্টিভঙ্গির অভাব
  • শর্তাবলী অস্পষ্ট: সাধারণ নিয়মিত গ্রাফের জন্য, কোন সম্প্রসারণ বৈশিষ্ট্য ERCP নিশ্চিত করার জন্য যথেষ্ট তা এখনও স্পষ্ট নয়
  • কঠোরতা অজানা: বর্তমান যথেষ্ট শর্তগুলি প্রয়োজনীয় কিনা তা নির্ধারিত হয়নি

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

লেখকরা বিশুদ্ধ সম্প্রসারণ বৈশিষ্ট্যের মাধ্যমে (বিশেষ কাঠামোর পরিবর্তে) ERCP বৈশিষ্ট্যযুক্ত করার লক্ষ্য রাখেন, একটি একীভূত প্রমাণ কাঠামো প্রদান করেন, এবং প্রতিরোধমূলক উদাহরণ নির্মাণের মাধ্যমে শর্তগুলির কঠোরতা প্রমাণ করেন।

মূল অবদান

  1. একীভূত যথেষ্ট শর্তের কাঠামো: সম্প্রসারণ বৈশিষ্ট্যের উপর ভিত্তি করে যথেষ্ট শর্তগুলি প্রস্তাব করে (উপপাদ্য 1), ডিগ্রি d≥log^α n এর ক্ষেত্রে অন্তর্ভুক্ত করে, সম্পূর্ণ গ্রাফ, হাইপারকিউব, d-নিয়মিত সম্প্রসারণ গ্রাফ, র্যান্ডম d-নিয়মিত গ্রাফ ইত্যাদি বিভিন্ন গ্রাফ শ্রেণীর ERCP একীভূতভাবে প্রমাণ করে।
  2. তিনটি প্রধান উপপাদ্য:
    • উপপাদ্য 1 (d≥log^α n): বৈশ্বিক মৃদু প্রান্ত সম্প্রসারণ (P1), ছোট সেট শীর্ষবিন্দু সম্প্রসারণ (P2), ছোট সেট প্রায়-সর্বোত্তম প্রান্ত সম্প্রসারণ (P3) প্রয়োজন
    • উপপাদ্য 3 (d≥10log n/ε): (P2) অপসারণ করে, শুধুমাত্র (P1) এবং শক্তিশালী (P2') প্রয়োজন
    • উপপাদ্য 4 (d=ω(1)): (P2) এবং ডিগ্রি নিম্ন সীমা অপসারণ করে, কিন্তু (P3) আরও বড় সেটে শক্তিশালীকরণ প্রয়োজন
  3. কঠোরতা ফলাফল (উপপাদ্য 2): প্রতিরোধমূলক উদাহরণ নির্মাণ করে যা ছোট সেট সম্প্রসারণ শর্ত (P3) ধ্রুবক ফ্যাক্টর অর্থে কঠোর তা প্রমাণ করে—যদি শুধুমাত্র আকার ≤εd log(n/d)/(100c₁) এর সেটগুলির জন্য প্রায়-সর্বোত্তম প্রান্ত সম্প্রসারণ প্রয়োজন হয়, তবে এমন গ্রাফ বিদ্যমান যেখানে দ্বিতীয় বৃহত্তম সংযুক্ত উপাদান Ω(d log(n/d))।
  4. নতুন প্রযুক্তিগত উদ্ভাবন:
    • বড় সংযুক্ত উপাদান "সর্বত্র ঘন" (everywhere dense) প্রমাণ করা
    • দ্বিগুণ এক্সপোজার/ছিটানো (double-exposure/sprinkling) কৌশল
    • সংযুক্ত উপাদান আকারের ফাঁক লেম্মা (gap lemma)
  5. একীভূত প্রমাণ প্যারাডাইম: বিশেষ কাঠামো (যেমন পণ্য কাঠামো বা সিউডোর্যান্ডমতা) উপর নির্ভর না করে বিশুদ্ধ সম্প্রসারণ প্রমাণ প্রদান করে।

পদ্ধতির বিস্তারিত বিবরণ

কাজের সংজ্ঞা

ইনপুট: d-নিয়মিত গ্রাফ G=(V,E), n=|V|, ডিগ্রি d=ω(1), অনুস্যান্দন সম্ভাবনা p=(1+ε)/d (ε>0 ছোট ধ্রুবক)
আউটপুট: Gp উচ্চ সম্ভাবনায় (whp) নিম্নলিখিত বৈশিষ্ট্য রাখে তা প্রমাণ করা:

  • একটি অনন্য বিশাল সংযুক্ত উপাদান L₁ বিদ্যমান, |L₁|=(1+o(1))y(ε)n
  • অন্যান্য সমস্ত সংযুক্ত উপাদানের আকার O(log n/ε²)

যেখানে y(ε)∈(0,1) সমীকরণ y=1-exp{-(1+ε)y}-এর অনন্য সমাধান, অর্থাৎ Po(1+ε) শাখা প্রক্রিয়ার বেঁচে থাকার সম্ভাবনা।

মূল অনুমান শর্তাবলী

উপপাদ্য 1 G-কে নিম্নলিখিত সন্তুষ্ট করতে প্রয়োজন:

(P1) বৈশ্বিক প্রান্ত সম্প্রসারণ: সমস্ত U⊆V, |U|≤n/2 এর জন্য, e(U,U^C)≥c₁|U| (c₁>0 ধ্রুবক)

(P2) ছোট সেট শীর্ষবিন্দু সম্প্রসারণ: সমস্ত U⊆V, |U|≤c₂log n এর জন্য, |N(U)|≥c₃d|U| (c₂,c₃>0 ধ্রুবক)

(P3) ছোট সেট প্রায়-সর্বোত্তম প্রান্ত সম্প্রসারণ: সমস্ত U⊆V, |U|≤Cd log n এর জন্য, e(U,U^C)≥(1-ε³)d|U| (C যথেষ্ট বড় ধ্রুবক)

প্রমাণ স্থাপত্য

সামগ্রিক কৌশল

দ্বিগুণ এক্সপোজার কৌশল ব্যবহার করা: p₂=ε³/d সেট করুন, p₁ এমনভাবে নির্বাচন করুন যাতে (1-p₁)(1-p₂)=1-p, তখন Gp এবং Gp₁∪Gp₂ একই বিতরণ। প্রমাণ চারটি প্রধান পদক্ষেপে বিভক্ত:

পদক্ষেপ 1: বড় সংযুক্ত উপাদান সর্বত্র ঘন (অংশ 3.1)

  • "বড় সংযুক্ত উপাদান" সংজ্ঞায়িত করুন: VL(H)={v: |C_H(v)|≥7log n/ε²}
  • লক্ষ্য: প্রমাণ করুন whp প্রতিটি শীর্ষবিন্দু v দূরত্ব 1+log_d log n এর মধ্যে VL(Gp)-তে Ω(d log n) শীর্ষবিন্দু রাখে

পদক্ষেপ 2: সংযুক্ত উপাদান আকারের ফাঁক (লেম্মা 3.4)

  • প্রমাণ করুন whp 7log n/ε², Cd log n-এ আকারের কোনো সংযুক্ত উপাদান নেই
  • এটি সূক্ষ্ম গণনা এবং সম্ভাব্যতা অনুমান প্রয়োজন

পদক্ষেপ 3: বড় সংযুক্ত উপাদান একত্রিত (অংশ 3.2, লেম্মা 3.5)

  • প্রমাণ করুন whp Gp₁-এর সমস্ত বড় সংযুক্ত উপাদান ছিটানো Gp₂ পরে একটি একক সংযুক্ত উপাদানে একত্রিত হয়
  • চাবিকাঠি: পর্যাপ্ত শীর্ষবিন্দু-বিচ্ছিন্ন পথ নির্মাণ

পদক্ষেপ 4: আয়তন ঘনীভবন (অংশ 3.3, লেম্মা 3.8)

  • প্রমাণ করুন বড় সংযুক্ত উপাদানে শীর্ষবিন্দুর মোট সংখ্যা y(ε)n এর কাছাকাছি ঘনীভূত

প্রযুক্তিগত বিবরণ

লেম্মা 3.1: নির্দিষ্ট সেটের সংযুক্ত উপাদান আচরণ

|S|=c'd log n এর সেটের জন্য (c'=c₂c₃^(1+1/α)), প্রমাণ করুন:

  • (a) কোনো U⊆S নেই যাতে ∪{u∈U}C(u)-এর আকার c'd log n/ε³, 2c'd log n/ε³-এ থাকে
  • (b) কোনো বড় উপসেট U⊆S নেই (|U|≥(1-ε²)c'd log n) যাতে ∪{u∈U}C(u)-এর আকার ≤Cd log n থাকে

প্রমাণ কৌশল:

  • বন গণনা ব্যবহার করুন (লেম্মা 2.3): k শীর্ষবিন্দুর গাছ সর্বাধিক (ed)^(k-1) ধরনের
  • (P3) ব্যবহার করুন: সীমানা কমপক্ষে (1-ε³)kd প্রান্ত রাখে যা Gp-তে থাকতে পারে না
  • সম্ভাব্যতা অনুমান: (edp)^(k-1)(1-p)^((1-ε³)kd) ≤ exp{-ε²k/4}

লেম্মা 3.3: সর্বত্র ঘনত্ব

প্রমাণ করুন whp প্রতিটি v∈V দূরত্ব ≤1+log_d log n এর মধ্যে VL(Gp)-তে ≥ε²c'd log n শীর্ষবিন্দু রাখে।

প্রমাণ পথ:

  1. (P2) দ্বারা, |B_G(v, log_d log n)|≥c₂c₃^(log_d log n) log n≥c₂c₃^(1/α) log n
  2. (P2) পুনরায় প্রয়োগ করুন, |B_G(v, 1+log_d log n)|≥c₃d·c₂c₃^(1/α) log n=c'd log n
  3. Sv⊆B_G(v, 1+log_d log n), |Sv|=c'd log n এর জন্য, অনুসিদ্ধান্ত 3.2 দ্বারা |Sv∩VL(Gp)|≥ε²c'd log n
  4. সমস্ত v-এর উপর সংযুক্ত সীমানা প্রমাণ সম্পূর্ণ করে

লেম্মা 3.5: বড় সংযুক্ত উপাদান একত্রিত

W=VL(Gp₁) সেট করুন, W-এর যেকোনো সংযুক্ত উপাদান-সম্মানিত বিভাজন W=A⊔B এর জন্য, Gp₂-তে A থেকে B-তে পথ খুঁজে পেতে হবে।

নির্মাণ প্রক্রিয়া (ধরুন |A|≤|B|):

  1. A₀=A, B₀=B সংজ্ঞায়িত করুন, পুনরাবৃত্তিমূলকভাবে Ai, Bi নির্মাণ করুন (i=1,...,r, r=1+log_d log n):
    • Ai Ai₋₁-এ ≥ε²c'd/(5r) প্রতিবেশী সহ শীর্ষবিন্দু অন্তর্ভুক্ত করে
    • Bi একইভাবে সংজ্ঞায়িত
  2. দাবি 3.6: V=A'⊔B', যেখানে A'=∪Ai, B'=∪Bi
  3. Gp₂-তে A' থেকে B'-তে প্রান্ত এক্সপোজ করুন, লেম্মা 2.4 দ্বারা ম্যাচিং M পান, |M|≥ε⁶c₁|A|/d
  4. পুনরাবৃত্তিমূলকভাবে M-এর শেষবিন্দু Gp₂-তে পথের মাধ্যমে A₀=A-তে প্রসারিত করুন
  5. একইভাবে B' থেকে B-তে প্রসারিত করুন, অবশেষে A এবং B সংযুক্ত করুন

সম্ভাব্যতা অনুমান:

  • প্রতিটি পদক্ষেপ ব্যর্থতার সম্ভাবনা ≤exp{-ε⁸c'|Mi,A'|/(5r)}
  • চূড়ান্ত পথ সংখ্যা ≥(ε⁸c'c₁/(5r))^(r+1)|A|/d
  • বিভাজন সংখ্যা ≤n^(|A|/(Cd log n))
  • সংযুক্ত সীমানা: ≤2n·exp{-(ε⁸c'c₁/(7r))^(2r+1)C log n}=o(1)

লেম্মা 3.4: ফাঁক লেম্মা

প্রমাণ করুন whp কোনো সংযুক্ত সেট K নেই, |K|∈7log n/ε², Cd log n এবং E_{Gp₁}(K,K^C)=∅।

মূল অনুমান:

  • আকার k এর গাছ T: সর্বাধিক n(ed)^(k-1) ধরনের
  • (P3) দ্বারা: e(V(T), V\V(T))≥(1-ε³)kd
  • Pসমস্ত প্রান্ত Gp-তে এবং সীমানা Gp₁-তে কোনো প্রান্ত নেই≤n(edp)^(k-1)exp{-p₁(1-ε³)dk}
  • ≤n exp{k(1+log(1+ε)-(1+ε-3ε³))}≤n exp{-ε²k/3}=o(1/n)

লেম্মা 3.8: আয়তন ঘনীভবন

W কে Gp-তে আকার ≥14log n/ε²-এর সংযুক্ত উপাদানের শীর্ষবিন্দু সেট করুন।

প্রত্যাশা গণনা:

  • নির্দিষ্ট v এর জন্য, BFS অন্বেষণের মাধ্যমে, Bin(d,p) শাখা প্রক্রিয়া দ্বারা র্যান্ডমভাবে আধিপত্য বিস্তার করা
  • P|C_(v)|≥14log n/ε²≤(1+o(1))y(ε) (উপরের সীমা)
  • BFS √d পদক্ষেপে থামানো পরিবর্তন করুন, Bin(d-√d,p) দ্বারা আধিপত্য বিস্তার করা
  • P|C_(v)|≥√d≥(1-o(1))y(ε) (নিম্ন সীমা)
  • লেম্মা 3.7 দ্বারা, EW=(1+o(1))y(ε)n

ঘনীভবন:

  • প্রান্ত এক্সপোজার মার্টিনগেল, প্রতিটি প্রান্ত |W| পরিবর্তন করে সর্বাধিক 28log n/ε²
  • Azuma-Hoeffding দ্বারা (লেম্মা 2.2): P||W|-EW|≥n^(2/3)≤2exp{-n^(4/3)/(O(ndp·log²n/ε⁴))}=o(1)

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

  1. সর্বত্র ঘনত্বের নতুন প্রমাণ: পণ্য কাঠামোর উপর নির্ভর করে না, বিশুদ্ধভাবে বল বৃদ্ধি এবং শীর্ষবিন্দু সম্প্রসারণের মাধ্যমে প্রতিষ্ঠিত
  2. পথ নির্মাণের পুনরাবৃত্তিমূলক কৌশল: ছিটানো সম্ভাবনা p₂=ε³/d এ, দৈর্ঘ্য r=O(log_d log n)-এর পথ উপস্থিতির সম্ভাবনা p₂^r খুব ছোট হতে পারে, পুনরাবৃত্তিমূলক ম্যাচিং এবং সেট নির্মাণ Ai-এর মাধ্যমে চতুরভাবে সমাধান করা
  3. ফাঁক লেম্মার নির্ভুল ধ্রুবক: 7log n/ε² থেকে Cd log n-এর ফাঁক পরবর্তী যুক্তির জন্য গুরুত্বপূর্ণ, ধ্রুবক নির্বাচন p₂=ε³/d-এর সাথে ঘনিষ্ঠভাবে সম্পর্কিত (log(1+x)-এর টেইলর সম্প্রসারণের সাথে সম্পর্কিত)
  4. কঠোরতা নির্মাণ (উপপাদ্য 2): c'₁-নিয়মিত গ্রাফ H (বৈশ্বিক সম্প্রসারণ সন্তুষ্ট) এবং রঙ শ্রেণীর মধ্যে (n',d',λ')-গ্রাফ যোগ করে নির্মাণ, যাতে রঙ শ্রেণী Gp-তে বিচ্ছিন্ন থাকে

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

এই পত্রটি একটি বিশুদ্ধ তাত্ত্বিক গণিত পত্র, এতে কোনো গণনামূলক পরীক্ষা নেই। সমস্ত ফলাফল কঠোর গাণিতিক প্রমাণ।

প্রয়োগ উদাহরণ ("যাচাইকরণ" হিসাবে)

পত্রটি দেখায় কীভাবে উপপাদ্য 1 এবং এর রূপান্তরগুলি পরিচিত ফলাফল পুনরুদ্ধার করে:

  1. সম্পূর্ণ গ্রাফ Kn: উপপাদ্য 3 দ্বারা Erdős-Rényi ক্লাসিক্যাল ফলাফল পুনরুদ্ধার করা
  2. (n,d,λ)-সিউডোর্যান্ডম গ্রাফ (λ=o(d)): সম্প্রসারণ মিশ্রণ লেম্মা দ্বারা (P3) যাচাই করা, উপপাদ্য 3/4 প্রযোজ্য
  3. র্যান্ডম d-নিয়মিত গ্রাফ: whp হল (n,d,Ω(√d))-গ্রাফ, সমস্ত শর্ত সন্তুষ্ট করে
  4. হাইপারকিউব Qd: Harper সমপরিধি অসমতা e(U,U^C)≥|U|(d-log₂|U|) দেয়, (P1) এবং (P3) সন্তুষ্ট করে; ছোট সেট শীর্ষবিন্দু সম্প্রসারণ Harper ফলাফল দ্বারা দেওয়া
  5. উচ্চ-মাত্রিক পণ্য গ্রাফ: Harper-ধরনের অসমতার মাধ্যমে শর্ত সন্তুষ্ট করে
  6. Duplicube: Harper-ধরনের অসমতা সন্তুষ্ট করে, Benjamini-Zhukovskii প্রশ্নের উত্তর দেয়

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

প্রধান ফলাফল সারসংক্ষেপ

উপপাদ্য 1 (বহু-লগারিদমিক ডিগ্রি): d≥log^α n যখন, (P1)+(P2)+(P3) ⇒ ERCP

উপপাদ্য 3 (উচ্চ ডিগ্রি): d≥10log n/ε যখন, (P1)+(P2') ⇒ ERCP, যেখানে (P2') প্রয়োজন |U|≤min{Cd log n, ε⁵n} যখন e(U,U^C)≥(1-ε³)d|U|

উপপাদ্য 4 (নিম্ন ডিগ্রি): d=ω(1) যখন, (P1)+শক্তিশালী (P3) (|U|≤(d log n)^(5log log n)) ⇒ ERCP

উপপাদ্য 2 (কঠোরতা): d-নিয়মিত গ্রাফ G বিদ্যমান যা:

  • (P1) সন্তুষ্ট করে
  • |U|≤log(n/d)/(40c₁) যখন, |N(U)|≥d|U|
  • |U|≤ε³d log(n/d)/(100c₁) যখন, e(U,U^C)≥(1-ε³)d|U|
  • কিন্তু whp দ্বিতীয় বৃহত্তম সংযুক্ত উপাদান ≥εd log(n/d)/(30c₁)=ω(log n)

শর্তাবলীর প্রয়োজনীয়তা বিশ্লেষণ

  • (P1)-এর প্রয়োজনীয়তা: 17 ইতিমধ্যে প্রমাণ করেছে যে বৈশ্বিক সম্প্রসারণ খুব দুর্বল হলে, বিশাল সংযুক্ত উপাদান o(n) হতে পারে
  • (P3)-এর কঠোরতা: উপপাদ্য 2 ধ্রুবক ফ্যাক্টর অর্থে কঠোরতা প্রমাণ করে
  • (P2)-এর প্রয়োজনীয়তা: খোলা প্রশ্ন (প্রশ্ন 6.1), কিন্তু উপপাদ্য 3 এবং 4 দেখায় কিছু ক্ষেত্রে এটি অপসারণ করা যায়

বিদ্যমান ফলাফলের সাথে তুলনা

গ্রাফ শ্রেণীবিদ্যমান প্রমাণএই পত্রের পদ্ধতিসুবিধা
সম্পূর্ণ গ্রাফErdős-Rényi 1960উপপাদ্য 3একীভূত কাঠামো
(n,d,λ)-গ্রাফFrieze et al. 2004উপপাদ্য 3/4মিশ্রণ লেম্মার উপর নির্ভর করে না
হাইপারকিউব QdAjtai et al. 1982উপপাদ্য 1পণ্য কাঠামোর উপর নির্ভর করে না
র্যান্ডম d-নিয়মিত গ্রাফ31-তে নিহিতউপপাদ্য 1স্পষ্ট শর্ত
Duplicubeঅজানাউপপাদ্য 1নতুন ফলাফল

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

ঐতিহাসিক উন্নয়ন

  1. Erdős-Rényi (1960): G(n,p)-এর পর্যায় রূপান্তর তত্ত্ব প্রতিষ্ঠা করে
  2. Broadbent-Hammersley (1957): অনুস্যান্দন মডেল প্রবর্তন করে
  3. Ajtai-Komlós-Szemerédi (1982): হাইপারকিউবের ERCP প্রমাণ করে, প্রথমবার "সর্বত্র ঘন" কৌশল ব্যবহার করে
  4. Bollobás-Kohayakawa-Łuczak (1992): হাইপারকিউবের অন্য প্রমাণ

ধ্রুবক ডিগ্রি ক্ষেত্রে

  • Alon-Benjamini-Stacey (2004): উচ্চ পরিধি সম্প্রসারণ গ্রাফ বিশাল সংযুক্ত উপাদান রাখে
  • Krivelevich-Lubetzky-Sudakov (2020): বিশাল সংযুক্ত উপাদান আকার y(ε)n, কিন্তু দ্বিতীয় বৃহত্তম |V|^a (যেকোনো a<1) পৌঁছাতে পারে
  • Diskin-Krivelevich (2025, 18): এই পত্রের বোন পত্র, ধ্রুবক ডিগ্রি ক্ষেত্র পরিচালনা করে

ডিগ্রি ক্রম এবং র্যান্ডমতা

  • Van der Hofstad (2023, 32): দেওয়া ডিগ্রি ক্রম যখন বিশাল সংযুক্ত উপাদানের সর্বজনীন সীমানা
  • Lichev-Mitsche-Perarnau (2024): ডিগ্রি ক্রম র্যান্ডম গ্রাফের থ্রেশহোল্ড বৈশিষ্ট্য
  • Alimohammadi-Borgs-Saberi (2023): বড় সেট সম্প্রসারণ যখন স্থানীয় কাঠামো বিশাল সংযুক্ত উপাদান নির্ধারণ করে

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

এই পত্রটি ডিগ্রি বৃদ্ধিশীল নিয়মিত গ্রাফের জন্য বিশুদ্ধ সম্প্রসারণ বৈশিষ্ট্যের একীভূত যথেষ্ট প্রয়োজনীয় শর্ত বৈশিষ্ট্য প্রদান করার প্রথম, এবং শর্ত কঠোরতা প্রমাণ করে।

সিদ্ধান্ত এবং আলোচনা

প্রধান সিদ্ধান্ত

  1. ডিগ্রি বৃদ্ধিশীল d-নিয়মিত গ্রাফের জন্য, মৃদু বৈশ্বিক প্রান্ত সম্প্রসারণ প্লাস ছোট সেটের (আকার O(d log n)) জন্য ভাল সম্প্রসারণ নিয়ন্ত্রণ ERCP নিশ্চিত করার জন্য যথেষ্ট
  2. ছোট সেট সম্প্রসারণ শর্ত ধ্রুবক ফ্যাক্টর অর্থে কঠোর
  3. একীভূত প্রমাণ কাঠামো প্রদান করে, বিশেষ কাঠামোর উপর নির্ভর করে না (পণ্য, সিউডোর্যান্ডমতা ইত্যাদি)

সীমাবদ্ধতা

  1. শীর্ষবিন্দু সম্প্রসারণ (P2)-এর প্রয়োজনীয়তা অসমাধান: প্রশ্ন 6.1 প্রস্তাব করে, (P1) এবং (P3) সন্তুষ্ট কিন্তু ERCP প্রদর্শন না করে এমন গ্রাফ বিদ্যমান?
  2. ধ্রুবক নির্ভরতা: উপপাদ্যের ধ্রুবক ε, c₁, c₂, c₃, α-এর উপর নির্ভর করে, নির্দিষ্ট নির্ভরতা সম্পূর্ণভাবে অপ্টিমাইজ করা হয়নি
  3. পরিমাণগত কঠোরতা: উপপাদ্য 2 গুণগত কঠোরতা দেয়, কিন্তু ধ্রুবক ফ্যাক্টরের নির্ভুল ম্যাচিং এখনও উন্নতির জায়গা রাখে
  4. ডিগ্রি পরিসীমা: d=ω(1) কিন্তু d=o(log n) ক্ষেত্রে উপপাদ্য 4-এর শক্তিশালী অনুমান প্রয়োজন

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

  1. প্রশ্ন 6.1: (P2)-এর প্রয়োজনীয়তা বৈশিষ্ট্য করা
  2. বৈশ্বিক এবং স্থানীয় সম্প্রসারণের পরিমাণগত ভারসাম্য: পত্রটি নির্দেশ করে (P1) শক্তিশালী হলে (P3) দুর্বল হতে পারে, এই ভারসাম্য নির্ভুলভাবে বৈশিষ্ট্য করা
  3. অন্যান্য গ্রাফ শ্রেণী: পারমুটেশন পলিটোপ (permutahedron) 13 কি অনুরূপ কাঠামো ব্যবহার করতে পারে?
  4. অ্যালগরিদমিক প্রয়োগ: সম্প্রসারণ শর্ত কি দক্ষ নমুনা বা আনুমানিক অ্যালগরিদমের জন্য ব্যবহার করা যায়?
  5. অ-নিয়মিত গ্রাফে সম্প্রসারণ: 13,15,30 অ-নিয়মিত গ্রাফ ERCP প্রদর্শন না করতে পারে দেখায়, কিন্তু আরও সূক্ষ্ম শর্ত দেওয়া যায়?

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

শক্তি

  1. তাত্ত্বিক গভীরতা:
    • একীভূত গাণিতিক কাঠামো প্রদান করে, বিশেষ ক্ষেত্র বিশ্লেষণ এড়ায়
    • কঠোরতা ফলাফল (উপপাদ্য 2) শর্ত প্রায় সর্বোত্তম প্রমাণ করে
    • প্রযুক্তিগত উদ্ভাবন (সর্বত্র ঘনত্ব, পুনরাবৃত্তিমূলক পথ নির্মাণ) স্বাধীন মূল্য রাখে
  2. প্রমাণ কৌশল:
    • দ্বিগুণ এক্সপোজার কৌশলের সূক্ষ্ম প্রয়োগ (p₂=ε³/d নির্বাচন টেইলর সম্প্রসারণের সাথে সম্পর্কিত)
    • ফাঁক লেম্মার ধ্রুবক নির্ভুল নিয়ন্ত্রণ
    • সম্ভাব্যতা অনুমানের সূক্ষ্ম পরিচালনা (যেমন লেম্মা 3.1-এর বন গণনা)
  3. প্রয়োগ বিস্তৃততা:
    • একাধিক ক্লাসিক্যাল ফলাফল পুনরুদ্ধার করে (সম্পূর্ণ গ্রাফ, হাইপারকিউব, সিউডোর্যান্ডম গ্রাফ)
    • খোলা প্রশ্ন সমাধান করে (duplicube-এর ERCP)
    • র্যান্ডম d-নিয়মিত গ্রাফের জন্য স্পষ্ট শর্ত প্রদান করে
  4. লেখার স্পষ্টতা:
    • কাঠামো স্পষ্ট: পটভূমি→প্রধান ফলাফল→প্রমাণ→কঠোরতা→প্রয়োগ
    • প্রযুক্তিগত রুট মানচিত্র স্পষ্ট: চার-পদক্ষেপ প্রমাণ কৌশল বোঝা সহজ
    • প্রতীক ব্যবস্থা সম্পূর্ণ

অপূর্ণতা

  1. শর্ত জটিলতা:
    • তিনটি বৈশিষ্ট্য (P1)(P2)(P3)-এর পারস্পরিক ক্রিয়া যথেষ্ট স্বজ্ঞাত নয়
    • ধ্রুবক c₁, c₂, c₃, C-এর মধ্যে নির্ভরতা সম্পর্ক স্পষ্টভাবে দেওয়া হয়নি
    • বাস্তব গ্রাফ শর্ত সন্তুষ্ট করে কিনা যাচাই করা কঠিন হতে পারে
  2. খোলা প্রশ্ন:
    • (P2)-এর প্রয়োজনীয়তা অসমাধান, তাত্ত্বিক চিত্র অসম্পূর্ণ
    • উপপাদ্য 2-এর নির্মাণ কঠোরতা প্রমাণ করে, কিন্তু ধ্রুবক ম্যাচিং নির্ভুল নয়
  3. প্রযুক্তিগত সীমাবদ্ধতা:
    • d=ω(1) কিন্তু d=o(log n) জন্য উপপাদ্য 4-এর শক্তিশালী অনুমান প্রয়োজন (সেট আকার (d log n)^(5log log n) পর্যন্ত)
    • প্রমাণ কৌশল নিয়মিততা অনুমানের উপর অত্যন্ত নির্ভরশীল, অ-নিয়মিত গ্রাফে সম্প্রসারণ কঠিন
  4. প্রয়োগ নির্দেশনা:
    • দেওয়া গ্রাফের জন্য, (P2)(P3) দক্ষতার সাথে যাচাই করতে কীভাবে?
    • অ্যালগরিদম বা গণনামূলক দিক আলোচনা অনুপস্থিত

প্রভাব

  1. ক্ষেত্রে অবদান:
    • অনুস্যান্দন তত্ত্বের জন্য নতুন একীভূত দৃষ্টিভঙ্গি প্রদান করে
    • অন্যান্য র্যান্ডম গ্রাফ মডেলের গবেষণা অনুপ্রাণিত করতে পারে
    • বোন পত্র 18 ধ্রুবক ডিগ্রিতে প্রসারিত, সম্পূর্ণ তত্ত্ব গঠন করে
  2. ব্যবহারিক মূল্য:
    • নেটওয়ার্ক শক্তিশালীতা বিশ্লেষণের জন্য তাত্ত্বিক ভিত্তি প্রদান করে
    • নেটওয়ার্ক ডিজাইনে ভাল অনুস্যান্দন বৈশিষ্ট্য সহ ব্যবহার করা যায়
    • সম্প্রসারণ বৈশিষ্ট্য কম্পিউটার বিজ্ঞানে ব্যাপক প্রয়োগ রাখে
  3. পুনরুৎপাদনযোগ্যতা:
    • বিশুদ্ধ তাত্ত্বিক প্রমাণ, সম্পূর্ণভাবে পুনরুৎপাদনযোগ্য
    • প্রমাণ কৌশল বিস্তারিত, মূল লেম্মা সম্পূর্ণ প্রমাণ রাখে
    • উপপাদ্য 2-এর নির্মাণ বাস্তবে বাস্তবায়ন করা যায়

প্রযোজ্য দৃশ্য

  1. তাত্ত্বিক গবেষণা:
    • র্যান্ডম গ্রাফ তত্ত্ব
    • অনুস্যান্দন তত্ত্ব
    • গ্রাফ সম্প্রসারণ বৈশিষ্ট্য গবেষণা
    • পর্যায় রূপান্তর ঘটনার সর্বজনীনতা শ্রেণী গবেষণা
  2. নেটওয়ার্ক বিজ্ঞান:
    • নেটওয়ার্ক শক্তিশালীতা বিশ্লেষণ (নোড/প্রান্ত ব্যর্থতা)
    • সংক্রামক রোগ প্রসার মডেল (অনুস্যান্দন প্রসার সংশ্লিষ্ট)
    • সামাজিক নেটওয়ার্ক সংযোগযোগ্যতা বিশ্লেষণ
  3. সমন্বয় অপ্টিমাইজেশন:
    • গ্রাফ বিভাজন সমস্যা
    • সম্প্রসারণ গ্রাফ নির্মাণ
    • র্যান্ডম অ্যালগরিদম ডিজাইন

রেফারেন্স (মূল সাহিত্য)

  1. 20 Erdős-Rényi (1960): র্যান্ডম গ্রাফ পর্যায় রূপান্তরের ভিত্তিপ্রস্তর কাজ
  2. 1 Ajtai-Komlós-Szemerédi (1982): হাইপারকিউব অনুস্যান্দন, প্রথমবার "সর্বত্র ঘন" ব্যবহার করে
  3. 22 Frieze-Krivelevich-Martin (2004): সিউডোর্যান্ডম গ্রাফের ERCP
  4. 29 Krivelevich-Lubetzky-Sudakov (2020): ধ্রুবক ডিগ্রি উচ্চ পরিধি সম্প্রসারণ গ্রাফ
  5. 32 Van der Hofstad (2023): বিশাল সংযুক্ত উপাদানের সর্বজনীন সীমানা
  6. 17 Diskin et al. (2024): লেখকদের পূর্ববর্তী সমপরিধি অসমতা এবং অনুস্যান্দন সম্পর্কিত কাজ
  7. 18 Diskin-Krivelevich (2025): এই পত্রের বোন পত্র (ধ্রুবক ডিগ্রি ক্ষেত্র)

সামগ্রিক মূল্যায়ন: এটি অনুস্যান্দন তত্ত্বের জন্য গভীর একীভূত কাঠামো প্রদান করে একটি উচ্চ মানের তাত্ত্বিক গণিত পত্র। প্রযুক্তিগতভাবে কঠোর এবং উদ্ভাবনী, ফলাফল ব্যাপক প্রযোজ্যতা রাখে, কঠোরতা বিশ্লেষণ তাত্ত্বিক চিত্র সম্পূর্ণ করে। প্রধান দুঃখ হল (P2)-এর প্রয়োজনীয়তা সম্পূর্ণভাবে সমাধান করা হয়নি, কিন্তু এটি পরবর্তী গবেষণার জন্য মূল্যবান দিকনির্দেশনা রেখে যায়। এই কাজ সমন্বয় গণিত এবং সম্ভাব্যতা তত্ত্ব ক্ষেত্রে গুরুত্বপূর্ণ প্রভাব রাখে, এবং নেটওয়ার্ক বিজ্ঞানের সাথে সম্ভাব্য সংযোগ রাখে।