পলিং এর নিয়মিত গ্রাফে ক্রমবর্ধমান ডিগ্রি সহ অবশিষ্ট এন্ট্রপি অনুমান সম্পর্কে

মৌলিক তথ্য

• পেপার আইডি: 2509.20671
• শিরোনাম: On Pauling's residual entropy estimate for regular graphs with growing degree
• লেখক: Mahdieh Hasheminezhad (Yazd University), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Australian National University), Rui-Ray Zhang
• শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
• প্রকাশনার সময়: ২০২৫ সালের নভেম্বর ৫ তারিখ (arXiv v2)
• পেপার লিঙ্ক: https://arxiv.org/abs/2509.20671

সারসংক্ষেপ

১৯৩৫ সালে, পলিং জল বরফের তাত্ত্বিক আচরণ অধ্যয়ন করার সময় গ্রাফের অয়লারীয় অভিমুখীকরণের সংখ্যা সম্পর্কে একটি অনুমান প্রস্তাব করেছিলেন। অয়লারীয় অভিমুখীকরণের সংখ্যার লগারিদমকে শীর্ষবিন্দুর সংখ্যা দ্বারা ভাগ করা হয় অবশিষ্ট এন্ট্রপি। একটি প্রাথমিক পেপারে, লেখকরা অনুমান করেছিলেন যে ডিগ্রি ক্রমবর্ধমান নিয়মিত গ্রাফ ক্রমের অবশিষ্ট এন্ট্রপি অ্যাসিম্পটোটিকভাবে পলিং অনুমানের সমান। এই পেপারটি স্বল্প চক্র সংখ্যার সীমাবদ্ধতার অধীনে এই অনুমানটি প্রমাণ করে। এই সীমাবদ্ধতাগুলি দুর্বল বৈশিষ্ট্যমূল্য শর্তের অধীনে বৈধ এবং ক্রমবর্ধমান পরিধি সহ গ্রাফ ক্রম এবং পুনরাবৃত্ত কার্টেসিয়ান পণ্যগুলিতে প্রযোজ্য (যেমন হাইপারকিউব)।

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

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

এই পেপারটি গ্রাফের অয়লারীয় অভিমুখীকরণ (Eulerian orientations) গণনা সমস্যা অধ্যয়ন করে। একটি d-নিয়মিত গ্রাফ G এর জন্য (d সমান), অয়লারীয় অভিমুখীকরণ হল প্রান্তের এমন একটি অভিমুখীকরণ যাতে প্রতিটি শীর্ষবিন্দুর অন্তর্গামী ডিগ্রি বহির্গামী ডিগ্রির সমান। অবশিষ্ট এন্ট্রপি সংজ্ঞায়িত করা হয়: $\rho(G) := \frac{1}{n}\log EO(G)$ যেখানে EO(G) হল অয়লারীয় অভিমুখীকরণের সংখ্যা এবং n হল শীর্ষবিন্দুর সংখ্যা।

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

• পদার্থবিজ্ঞানের পটভূমি: অবশিষ্ট এন্ট্রপি পরিসংখ্যানগত পদার্থবিজ্ঞানের বরফ মডেলে (ice-type models) গুরুত্বপূর্ণ এবং জল বরফ স্ফটিকের মাইক্রোস্কোপিক অবস্থার সংখ্যার সাথে সম্পর্কিত
• গাণিতিক তাৎপর্য: নির্দিষ্ট জালকার জন্য (বর্গ জালক, ত্রিভুজাকার জালক, ষড়ভুজ বরফ একক স্তর), অবশিষ্ট এন্ট্রপির সঠিক মান পরিচিত, কিন্তু সাধারণ গ্রাফের অ্যাসিম্পটোটিক আচরণ এখনও একটি খোলা সমস্যা
• তাত্ত্বিক মূল্য: সমন্বয়বিদ্যা, পরিসংখ্যানগত পদার্থবিজ্ঞান এবং সম্ভাব্যতা তত্ত্বকে সংযুক্ত করে

৩. পলিং অনুমান

পলিং ১৯৩৫ সালে একটি অনুমানমূলক অনুমান প্রস্তাব করেছিলেন: প্রতিটি প্রান্ত স্বাধীনভাবে এলোমেলোভাবে অভিমুখী হয় বলে ধরে নিন, শীর্ষবিন্দু i এর অন্তর্গামী ডিগ্রি বহির্গামী ডিগ্রির সমান হওয়ার সম্ভাবনা $2^{-d}\binom{d}{d/2}$। যদি n শীর্ষবিন্দুর ঘটনাগুলি স্বাধীন হয়, তাহলে আমরা পাই: $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

লিব এবং উ প্রমাণ করেছেন যে যেকোনো গ্রাফের জন্য: $\rho(G) \geq \hat{\rho}(G)$

৪. বিদ্যমান গবেষণার সীমাবদ্ধতা

• পূর্ববর্তী ফলাফল (Isaev, McKay, Zhang 5) শুধুমাত্র ভাল সম্প্রসারণ বৈশিষ্ট্য এবং $d \geq \log^8 n$ সহ গ্রাফের জন্য প্রযোজ্য
• এলোমেলো গ্রাফের ফলাফল (6) উচ্চ সম্ভাবনার বৈশিষ্ট্যের উপর নির্ভর করে
• Las Vergnas 7 এর ফলাফল পরিধি দ্রুত $\log d$ এর চেয়ে বৃদ্ধি পাওয়ার প্রয়োজন

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

অনুমান ১.১: d-নিয়মিত গ্রাফ ক্রম G(n) এর জন্য, যদি সমান $d = d(n) \to \infty$, তাহলে $\rho(G) = \hat{\rho}(G) + o(1)$

এই পেপারের লক্ষ্য আরও দুর্বল শর্তের অধীনে এই অনুমানটি প্রমাণ করা।

মূল অবদান

১. প্রধান উপপাদ্য (Theorem 2.1): স্বল্প বন্ধ পথের সংখ্যার সীমাবদ্ধতার অধীনে অনুমান ১.১ প্রমাণ করে, শর্ত হল:

• $\ell_{max} = \omega(\log d)$ এবং ধ্রুবক C > 0 বিদ্যমান
• সমস্ত $3 \leq \ell \leq \ell_{max}$ এর জন্য: $c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$

२. বৈশিষ্ট্যমূল্য শর্তের উপসংহার (Corollary 2.2): যদি সর্বাধিক $nd^{-\omega(1)}$ বৈশিষ্ট্যমূল্য $[-d^{1-\delta}, d^{1-\delta}]$ এর বাইরে থাকে (কিছু ধ্রুবক δ > 0), তাহলে অনুমান সত্য

३. পরিধি শর্তের উপসংহার (Corollary 2.3): পরিধি $g \to \infty$ সহ d-নিয়মিত গ্রাফ ক্রমের জন্য, অনুমান সত্য ($d \to \infty$ প্রয়োজন নেই)

४. কার্টেসিয়ান পণ্যের উপসংহার (Corollary 2.4): কার্টেসিয়ান পণ্য $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$ এর জন্য, যখন ডিগ্রি বর্গের যোগফল $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$ সন্তুষ্ট করে অনুমান সত্য, বিশেষত হাইপারকিউব $Q_d$ এর জন্য প্রযোজ্য

५. প্রযুক্তিগত উদ্ভাবন: সমস্যাটিকে এলোমেলো অয়লারীয় বিভাজন দ্বারা প্ররোচিত বন্ধ পথের সংখ্যার মুহূর্ত উৎপাদক ফাংশন বিশ্লেষণে রূপান্তরিত করে

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

কাজের সংজ্ঞা

d-নিয়মিত গ্রাফ G (d সমান) দেওয়া হয়েছে, অবশিষ্ট এন্ট্রপি $\rho(G) = \frac{1}{n}\log EO(G)$ গণনা করুন এবং প্রমাণ করুন যে এটি অ্যাসিম্পটোটিকভাবে পলিং অনুমান $\hat{\rho}(G)$ এর সমান।

মূল পদ্ধতির কাঠামো

১. অয়লারীয় বিভাজন প্রতিনিধিত্ব

সংজ্ঞা: অয়লারীয় বিভাজন P হল গ্রাফের প্রান্তগুলিকে বেশ কয়েকটি বন্ধ পথে বিভক্ত করা। প্রতিটি শীর্ষবিন্দুর প্রান্ত জোড়া (pairing) অনন্যভাবে একটি অয়লারীয় বিভাজন নির্ধারণ করে।

মূল সূত্র: $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ যেখানে P হল সমানভাবে এলোমেলো অয়লারীয় বিভাজন এবং T(P) হল P দ্বারা প্ররোচিত বন্ধ পথের সেট।

সমতা: অনুমান $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$ প্রমাণ করার সমতুল্য

२. বন্ধ পথ বিয়োজন কৌশল

$k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$ সংজ্ঞায়িত করুন, বন্ধ পথগুলিকে বিভক্ত করুন:

• দীর্ঘ বন্ধ পথ $L_k(P)$: k এর চেয়ে বেশি বিভিন্ন শীর্ষবিন্দু সহ বন্ধ পথের সংখ্যা
• স্বল্প বন্ধ পথ $S_k(P)$: সর্বাধিক k বিভিন্ন শীর্ষবিন্দু সহ বন্ধ পথের সংখ্যা

Hölder অসমতা ব্যবহার করুন: $\mathbb{E} 2^{|T(P)|} = \mathbb{E} 2^{L_k(P)+S_k(P)} \leq \left(\mathbb{E} 2^{\frac{7}{2}L_k(P)}\right)^{2/7}\left(\mathbb{E} 2^{\frac{7}{5}S_k(P)}\right)^{5/7}$

প্রযুক্তিগত উপাদান

३. দীর্ঘ বন্ধ পথ নিয়ন্ত্রণ (Lemma 3.4)

মূল লেম্মা (Lemma 3.1): সমান m এবং λ ≥ 0 এর জন্য, $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ যেখানে $X(m)$ হল স্বাধীন বার্নুলি এলোমেলো চলক $1/(2j-1)$ (j=1,...,m/2) প্যারামিটার সহ এর যোগফল।

জোড়া স্বাধীনতা (Lemma 3.2): এলোমেলো জোড়ায়, শীর্ষবিন্দু v এর মাধ্যমে বিভিন্ন বন্ধ পথের সংখ্যা বিতরণ X(m) অনুসরণ করে এবং অন্যান্য শীর্ষবিন্দুর জোড়া থেকে স্বাধীন।

মুহূর্ত উৎপাদক ফাংশন সীমা (Lemma 3.3): শীর্ষবিন্দু উপসেট U এর জন্য, $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

চূড়ান্ত সীমা: $|U| = \lfloor n/k\rfloor$ এর এলোমেলো উপসেট নির্বাচন করুন, $L_k \leq 2Y(U)$ এর সম্ভাবনা কমপক্ষে 1/2 ব্যবহার করে, পান: $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

४. স্বল্প বন্ধ পথ নিয়ন্ত্রণ (Lemma 4.5)

স্যুইচিং পদ্ধতি ব্যবহার করুন (Theorem 4.1) — এটি একটি শক্তিশালী সমন্বয়বিদ্যা গণনা সরঞ্জাম।

স্যুইচিং সংজ্ঞা: অয়লারীয় বিভাজন P এবং বন্ধ পথ T দেওয়া হয়েছে, T-স্যুইচিং T দ্বারা অতিক্রম করা প্রতিটি শীর্ষবিন্দুতে জোড়া সংশোধন করে:

• শীর্ষবিন্দু v কে T দ্বারা t বার পরিদর্শন করা হয়, প্রান্ত জোড়া $(e_1,e_1'),\ldots,(e_t,e_t')$ এর সাথে সামঞ্জস্যপূর্ণ
• t অতিরিক্ত প্রান্ত জোড়া নির্বাচন করুন $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$
• নতুন জোড়া দিয়ে প্রতিস্থাপন করুন $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$ এবং $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$

স্যুইচিং গ্রাফ: নির্দেশিত মাল্টিগ্রাফ Γ তৈরি করুন:

• শীর্ষবিন্দু: $\mathbf{m} = (m_3,\ldots,m_L)$, ঠিক $m_\ell$ দৈর্ঘ্যের স্বল্প বন্ধ পথ সহ অয়লারীয় বিভাজন শ্রেণীর প্রতিনিধিত্ব করে
• প্রান্ত: রঙ ℓ এর নির্দেশিত প্রান্ত $(\mathbf{m},\mathbf{m}')$ C(m) থেকে C(m') এ ℓ-স্যুইচিং বিদ্যমান নির্দেশ করে

মূল অনুমান (Lemma 4.3):

• P ∈ C(m) থেকে শুরু করা ℓ-স্যুইচিং সংখ্যা: $\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• P' ∈ C(m') এ পৌঁছানো ℓ-স্যুইচিং সংখ্যা: $\leq c_{k,\ell}$

ওজন ফাংশন: $\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}$

Theorem 4.1 প্রয়োগ: সংজ্ঞায়িত করুন $M_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m$

যেহেতু $\hat{\alpha}(e) < 1/2$ সমস্ত $\|\mathbf{m}\|_1 > M_0$ এর প্রান্তের জন্য, পান: $|Y| \leq 2e^{-M+M_0}|Z|$

লেজ সম্ভাবনা সীমা: $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

মুহূর্ত সীমা: অবিচ্ছেদ্য প্রতিনিধিত্বের মাধ্যমে, $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ যেখানে $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$।

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

१. বিয়োজন কৌশলের সূক্ষ্মতা: k মানের নির্বাচনের মাধ্যমে দীর্ঘ এবং স্বল্প বন্ধ পথের অবদান ভারসাম্য রাখুন, Hölder অসমতার সূচক নির্বাচন (7/2 এবং 7/5) সাবধানে ডিজাইন করা হয়েছে

२. স্যুইচিং পদ্ধতির উদ্ভাবনী প্রয়োগ:

• অয়লারীয় বিভাজনের গণনা সমস্যাকে নির্দেশিত গ্রাফে প্রবাহ সমস্যায় রূপান্তরিত করুন
• স্যুইচিং ওজন নিয়ন্ত্রণ করতে স্বল্প বন্ধ পথ সংখ্যা অনুমান ব্যবহার করুন
• Theorem 4.1 এর মাধ্যমে লেজ সম্ভাবনার সূচক হ্রাস পান

३. শর্তের দুর্বলকরণ:

• $d \geq \log^8 n$ থেকে $d \to \infty$ এ দুর্বল করুন
• শক্তিশালী সম্প্রসারণ থেকে স্বল্প বন্ধ পথ সংখ্যা সীমাবদ্ধতায় দুর্বল করুন
• বৈশিষ্ট্যমূল্য শর্ত শুধুমাত্র $nd^{-\omega(1)}$ বহিরাগত প্রয়োজন

४. একীভূত কাঠামো: একটি একক কাঠামোতে পরিধি বৃদ্ধি, বৈশিষ্ট্যমূল্য সীমাবদ্ধতা, কার্টেসিয়ান পণ্য ইত্যাদি একাধিক পরিস্থিতি পরিচালনা করুন

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

তাত্ত্বিক প্রমাণ বৈশিষ্ট্য

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

প্রয়োগের উদাহরণ

পেপারটি নিম্নলিখিত গ্রাফ শ্রেণীতে অনুমানটি যাচাই করে উপসংহারের মাধ্যমে:

१. পরিধি বৃদ্ধি গ্রাফ (Corollary 2.3) २. বর্ণালী সীমাবদ্ধ গ্রাফ (Corollary 2.2) ३. হাইপারকিউব $Q_d$ (d সমান) ४. চক্রীয় কার্টেসিয়ান পণ্য: স্থানীয়ভাবে উচ্চ মাত্রার বর্গ জালকে রূপান্তরিত করুন ५. এলোমেলো নিয়মিত গ্রাফ (6 এর ফলাফল উদ্ধৃত করুন)

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

প্রধান ফলাফল

Theorem 2.1 এর শর্ত যাচাইকরণ:

१. পরিধি g → ∞ এর গ্রাফ:

• দৈর্ঘ্য ℓ < g এর বন্ধ পথের সংখ্যা 0, স্বয়ংক্রিয়ভাবে শর্ত সন্তুষ্ট করে
• এমনকি d = O(1) এও সত্য

२. বৈশিষ্ট্যমূল্য সীমাবদ্ধ গ্রাফ:

• বন্ধ হাঁটার সংখ্যা $\leq \sum_i \lambda_i^\ell$
• যদি সর্বাধিক $nd^{-f(n)}$ বৈশিষ্ট্যমূল্য $[-d^{1-\delta}, d^{1-\delta}]$ এর বাইরে থাকে
• $\ell_{max} = \frac{1}{2}f(n)\log d$ নিন, শর্ত সন্তুষ্ট হয়

३. কার্টেসিয়ান পণ্য:

• বৈশিষ্ট্যমূল্য বিতরণ নিয়ন্ত্রণ করতে Hoeffding অসমতা ব্যবহার করুন
• $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$ এর জন্য, শর্ত সন্তুষ্ট হয়
• হাইপারকিউব: $h_i = 1$, $\sum h_i^2 = t = o(d_t^2)$ সন্তুষ্ট করে

প্রযুক্তিগত ফলাফল

দীর্ঘ বন্ধ পথ সীমা (Lemma 3.4): $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

স্বল্প বন্ধ পথ সীমা (Lemma 4.5): $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

মূল অসমতা শৃঙ্খল