2025-11-19T08:19:14.801176

Skeletons and Spectra: Bernoulli graphings are relatively Ramanujan

Jardón--Sánchez, Tóth
The aim of this paper is to investigate the spectral theory of unimodular random graphs and graphings representing them. We prove that Bernoulli graphings are relatively Ramanujan with respect to their skeleton Markov chain. That is, the part of their spectrum that comes from the random labels falls within the appropriate Alon-Boppana bound. This result complements an example due to Frączyk of an ergodic unimodular random graph with almost sure spectral gap but non-expanding Bernoulli graphing. We also highlight connections of our work with the theory of finite random graphs. Exploiting the result of Bordenave and Collins on random lifts being relatively almost Ramanujan, we prove a strengthening of our main theorem for unimodular quasi-transitive quasi-trees.
academic

কঙ্কাল এবং বর্ণালী: বার্নুলি গ্রাফিং্স সম্পর্কিতভাবে রামানুজন

মৌলিক তথ্য

  • পত্র ID: 2510.13323
  • শিরোনাম: Skeletons and Spectra: Bernoulli graphings are relatively Ramanujan
  • লেখক: Héctor Jardón-Sánchez, László Márton Tóth
  • শ্রেণীবিভাগ: math.PR (সম্ভাবনা তত্ত্ব), math.CO (সমন্বয় গণিত)
  • প্রকাশনার সময়: ২০২৫ সালের ১৭ অক্টোবর
  • পত্র লিঙ্ক: https://arxiv.org/abs/2510.13323

সারাংশ

এই পত্রটি একমডুলার র‍্যান্ডম গ্রাফ (unimodular random graphs) এবং তাদের প্রতিনিধিত্বকারী গ্রাফিং্সের বর্ণালী তত্ত্ব অধ্যয়নের লক্ষ্যে নিবেদিত। লেখকরা প্রমাণ করেছেন যে বার্নুলি গ্রাফিং্স তাদের কঙ্কাল মার্কভ শৃঙ্খলের সাপেক্ষে সম্পর্কিতভাবে রামানুজন, অর্থাৎ র‍্যান্ডম লেবেল থেকে আসা বর্ণালী অংশ উপযুক্ত অ্যালন-বোপ্পানা সীমানার মধ্যে পড়ে। এই ফলাফল ফ্র্যাচিকের একটি উদাহরণকে পরিপূরক করে: প্রায় নিশ্চিত বর্ণালী ব্যবধান সহ কিন্তু সম্প্রসারক নয় এমন বার্নুলি গ্রাফিং্স সহ এরগোডিক একমডুলার র‍্যান্ডম গ্রাফ বিদ্যমান। পত্রটি সীমিত র‍্যান্ডম গ্রাফ তত্ত্বের সাথে সংযোগও তুলে ধরে, বোর্ডেনাভ এবং কলিন্সের র‍্যান্ডম উত্তোলন সম্পর্কিতভাবে প্রায় রামানুজন সম্পর্কিত ফলাফল ব্যবহার করে, একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রিজের জন্য প্রধান উপপাদ্যের একটি শক্তিশালী সংস্করণ প্রমাণ করে।

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

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

এই পত্রের গবেষণার মূল সমস্যা হল একমডুলার র‍্যান্ডম গ্রাফের স্থানীয় বর্ণালী ব্যাসার্ধ ρ(G,o) এবং এর বার্নুলি গ্রাফিং্সের বৈশ্বিক বর্ণালী ব্যাসার্ধ ρ(B) এর মধ্যে সম্পর্ক। গ্রাফ তত্ত্বে, রামানুজন সম্পত্তি একটি গুরুত্বপূর্ণ ধারণা, যা গ্রাফের বর্ণালী ব্যাসার্ধ অ্যালন-বোপ্পানা উপপাদ্য দ্বারা প্রদত্ত তাত্ত্বিক নিম্নসীমা অর্জনের দাবি করে।

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

১. তাত্ত্বিক সম্পূর্ণতা: যদিও কেলি গ্রাফ এবং নিয়মিত গাছের জন্য বার্নুলি গ্রাফিং্সে রামানুজন সম্পত্তি রয়েছে (ρ(G,o) = ρ(B)), সাধারণ একমডুলার র‍্যান্ডম গ্রাফের জন্য এই সম্পত্তি সত্য কিনা তা অস্পষ্ট।

२. প্রতিপক্ষ উদাহরণের অস্তিত্ব: ফ্র্যাচিক এমন একটি প্রতিপক্ষ নির্মাণ করেছেন যা ρ(G,o) < 1 কিন্তু ρ(B) = 1 এমন ক্ষেত্র প্রদর্শন করে, এটি নির্দেশ করে যে সাধারণ রামানুজন সম্পত্তি সর্বদা সত্য নয়।

३. সীমিত এবং অসীমের সংযোগ: পত্রটি সীমিত র‍্যান্ডম গ্রাফ তত্ত্ব (যেমন ফ্রিডম্যান উপপাদ্য) এবং অসীম গ্রাফিং্স তত্ত্বের মধ্যে সেতু স্থাপনের লক্ষ্য রাখে।

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

  • বিদ্যমান ফলাফল প্রধানত বিশেষ ক্ষেত্রে সীমাবদ্ধ (যেমন কেলি গ্রাফ, নিয়মিত গাছ)
  • সাধারণ একমডুলার র‍্যান্ডম গ্রাফের বর্ণালী কাঠামোর গভীর বোঝাপড়ার অভাব
  • সীমিত এবং অসীম গ্রাফ তত্ত্বের মধ্যে সংযোগ যথেষ্ট স্পষ্ট নয়

মূল অবদান

१. প্রধান উপপাদ্য: প্রমাণ করেছেন যে বার্নুলি গ্রাফিং্স তার কঙ্কালের সাপেক্ষে রামানুজন, অর্থাৎ σR(B) ⊆ -ρ(G,o), ρ(G,o)

२. বর্ণালী অন্তর্ভুক্তি সম্পর্ক: স্থানীয় এবং বৈশ্বিক বর্ণালীর মধ্যে অন্তর্ভুক্তি সম্পর্ক স্থাপন করেছেন σ(G,o) ⊆ σR(B)

३. প্রতিপক্ষ বিশ্লেষণ: ফ্র্যাচিকের প্রতিপক্ষ প্রদান এবং বিশ্লেষণ করেছেন, সম্পর্কিত রামানুজন সম্পত্তির প্রয়োজনীয়তা ব্যাখ্যা করেছেন

४. সীমিত-অসীম সংযোগ: বোর্ডেনাভ-কলিন্সের ফলাফল ব্যবহার করে, একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রিজের জন্য উপপাদ্যের একটি শক্তিশালী সংস্করণ প্রমাণ করেছেন

५. গ্রাফ তত্ত্বগত বৈশিষ্ট্য: একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রিজের সম্পূর্ণ বৈশিষ্ট্য প্রদান করেছেন (উপপাদ্য 1.7)

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

মূল ধারণা সংজ্ঞা

একমডুলার র‍্যান্ডম গ্রাফ: ভর স্থানান্তর নীতি সন্তুষ্ট করে এমন র‍্যান্ডম মূল গ্রাফ (G,o), অর্থাৎ যেকোনো বোরেল ফাংশন f এর জন্য: ∫∑f(G,o',o)d(G,o) = ∫∑f(G,o,o')d(G,o)

বার্নুলি গ্রাফিং্স: G+• এ সংজ্ঞায়িত বোরেল গ্রাফ B, যেখানে শীর্ষবিন্দুগুলি স্বাধীন সমানভাবে বিতরণকৃত 0,1 লেবেল সহ মূল গ্রাফ

বর্ণালী বিয়োজন: L²(G+•,μ*) কে কাঠামোগত উপ-স্থান S এবং র‍্যান্ডম উপ-স্থান R এ বিয়োজন করা:

  • S: শুধুমাত্র গ্রাফ কাঠামোর উপর নির্ভরশীল ফাংশন
  • R = S⊥: র‍্যান্ডম লেবেলের উপর নির্ভরশীল ফাংশন

প্রযুক্তিগত কাঠামো

१. বর্ণালী বিয়োজন পদ্ধতি

পত্রের মূল কৌশল হল বার্নুলি গ্রাফিং্সের বর্ণালী σ(B) বিয়োজন করা:

  • কাঠামোগত বর্ণালী: σS(B) = σ(M|S)
  • র‍্যান্ডম বর্ণালী: σR(B) = σ(M|R)

যেখানে M হল মার্কভ অপারেটর।

२. কঙ্কাল মার্কভ শৃঙ্খল

কঙ্কাল মার্কভ শৃঙ্খল S সংজ্ঞায়িত করা G• এ: pS((G,u),(H,v)) = |{w ∈ NG(u) : (G,w) ≅ (H,v)}|/degG(u)

প্রমাণ করেছেন যে σS(B) = σ(N), যেখানে N হল কঙ্কালের মার্কভ অপারেটর।

३. ব্লক ফ্যাক্টর অনুমান

ব্লক ফ্যাক্টর (block factors) ব্যবহার করে র‍্যান্ডম উপ-স্থানে ফাংশন অনুমান করা, যেগুলির মান শুধুমাত্র মূলের চারপাশে সীমিত ব্যাসার্ধের মধ্যে লেবেল দ্বারা নির্ধারিত।

মূল প্রমাণ কৌশল

উপপাদ্য 1.1 এর প্রমাণ কৌশল:

१. বিউর্লিং বর্ণালী ব্যাসার্ধ সূত্র ব্যবহার করে, শুধুমাত্র প্রমাণ করতে হবে যে যেকোনো স্বাভাবিক ব্লক ফ্যাক্টর f ∈ R এর জন্য: n√⟨Mnf,f⟩ ≤ (1+o(1))ρ(G,o)

२. অভ্যন্তরীণ গুণফল মূল থেকে দূরত্ব 2r এর মধ্যে এবং বাইরে অবদানে বিয়োজন করা

३. দূরত্ব 2r এর বাইরে শীর্ষবিন্দুর জন্য, ব্লক ফ্যাক্টর সম্পত্তি এবং র‍্যান্ডম উপ-স্থানের বৈশিষ্ট্যের কারণে, অবদান শূন্য

४. কচি-শোয়ার্জ অসমতা এবং অবসর বর্ণালী ব্যাসার্ধ ফলাফল ব্যবহার করে প্রমাণ সম্পন্ন করা

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

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

ফ্র্যাচিক প্রতিপক্ষ নির্মাণ

  • ভিত্তি গ্রুপ: মুক্ত গ্রুপ F₂ = ⟨a,b⟩
  • সমরূপতা ম্যাপিং: φ: F₂ → Z, φ(a) = φ(b) = 1
  • গ্রাফ নির্মাণ: 4-নিয়মিত গাছ T থেকে শুরু করে, সমরূপতা φ এর মাধ্যমে লেবেল নির্মাণ করা, তারপর ফ্যাক্টর হিসাবে (G,o) পাওয়া
  • মূল সম্পত্তি: ρ(G,o) < 1 কিন্তু ρ(B) = 1

প্রধান ফলাফল

মূল উপপাদ্য

উপপাদ্য 1.1: বার্নুলি গ্রাফিং্স B তার কঙ্কালের সাপেক্ষে রামানুজন: σR(B) ⊆ -ρ(G,o), ρ(G,o)

উপপাদ্য 1.2: সমস্ত অ-পর্যায়ক্রমিক গ্রাফিং্সের জন্য, ρ(G,o) ≤ ρ(G)

উপপাদ্য 1.4: এরগোডিক একমডুলার র‍্যান্ডম গ্রাফের জন্য, ρ(G,o) = ρR(B)

শক্তিশালী ফলাফল

উপপাদ্য 1.6: একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রি G এর জন্য, σR(B) = σ(G)

এটি উপপাদ্য 1.1 এর একটি কঠোর শক্তিশালীকরণ, নির্দেশ করে যে এই বিশেষ গ্রাফ শ্রেণীর জন্য, র‍্যান্ডম বর্ণালী ঠিক গ্রাফের বর্ণালীর সমান।

গ্রাফ তত্ত্বগত বৈশিষ্ট্য

উপপাদ্য 1.7: স্থানীয়ভাবে সীমিত সংযুক্ত গ্রাফ G এর জন্য, নিম্নলিখিত সমতুল্য: १. G একটি একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রি २. একটি মুক্ত কোয়াসি-ট্রানজিটিভ ক্রিয়া Fd ↷ G বিদ্যমান ३. একটি সীমিত গ্রাফ H এবং ম্যাপিং φ বিদ্যমান যেমন G ≅ H̃/ker(φ)

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

সীমিত গ্রাফ তত্ত্ব

  • অ্যালন-বোপ্পানা উপপাদ্য: d-নিয়মিত গ্রাফের বর্ণালী ব্যাসার্ধের নিম্নসীমা প্রদান করে
  • ফ্রিডম্যান উপপাদ্য: র‍্যান্ডম d-নিয়মিত গ্রাফ প্রায় নিশ্চিতভাবে রামানুজন
  • বোর্ডেনাভ-কলিন্স ফলাফল: র‍্যান্ডম উত্তোলনের নতুন বৈশিষ্ট্যমূল্য সংগ্রহ

অসীম গ্রাফ তত্ত্ব

  • কেস্টেন উপপাদ্য: বর্ণালী ব্যাসার্ধকে পৌঁছানোর সাথে সংযুক্ত করে
  • ব্যাকহাউজ-সেজেডি-ভিরাগ ফলাফল: নিয়মিত গাছের বার্নুলি গ্রাফিং্স রামানুজন
  • গ্রাফিং্স তত্ত্ব: লোভাজ এবং অন্যদের দ্বারা বিকশিত সীমা তত্ত্ব

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

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

१. সম্পর্কিত রামানুজন সম্পত্তি: যদিও বার্নুলি গ্রাফিং্স সর্বদা রামানুজন নয়, তবে এর র‍্যান্ডম অংশের বর্ণালী সর্বদা রামানুজন সীমানা সন্তুষ্ট করে २. কাঠামো এবং র‍্যান্ডমের বিভাজন: বর্ণালীর কাঠামোগত অংশ এবং র‍্যান্ডম অংশের মধ্যে স্পষ্ট বিভাজন রয়েছে, প্রথমটি কঙ্কাল দ্বারা নির্ধারিত ३. সীমিত অসীম সংযোগ: সীমিত র‍্যান্ডম গ্রাফ ফলাফল এবং অসীম গ্রাফিং্স ফলাফলের মধ্যে গভীর সংযোগ স্থাপন করেছেন

সীমাবদ্ধতা

१. বিশেষ ক্ষেত্র: সম্পূর্ণ বৈশিষ্ট্য শুধুমাত্র একমডুলার কোয়াসি-ট্রানজিটিভ কোয়াসি-ট্রিজের জন্য প্রযোজ্য २. গঠনমূলক: কিছু প্রমাণ অস্তিত্বমূলক, স্পষ্ট নির্মাণের অভাব ३. গণনাগত জটিলতা: বর্ণালী প্রকৃত গণনার পদ্ধতি এখনও কঠিন

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

পত্রটি ষষ্ঠ বিভাগে বেশ কয়েকটি গুরুত্বপূর্ণ খোলা প্রশ্ন উত্থাপন করেছে:

१. কনফিগারেশন মডেল: অ-নিয়মিত র‍্যান্ডম গ্রাফ কি প্রায় রামানুজন? २. গ্যালটন-ওয়াটসন গাছ: এর বার্নুলি গ্রাফিং্স কি রামানুজন? ३. সাধারণ ক্ষেত্র: কি সর্বদা σR(G) = σ(G,o)? ४. শক্তিশালী সংগ্রহ: র‍্যান্ডম প্রতিনিধিত্বের শক্তিশালী সংগ্রহ কি আরও বর্ণালী তথ্য প্রদান করে?

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

সুবিধা

१. তাত্ত্বিক গভীরতা: একমডুলার র‍্যান্ডম গ্রাফ বর্ণালী তত্ত্বের গুরুত্বপূর্ণ ফলাফল স্থাপন করেছেন, তাত্ত্বিক ফাঁক পূরণ করেছেন २. প্রযুক্তিগত উদ্ভাবন: বর্ণালী বিয়োজন পদ্ধতি এবং সম্পর্কিত রামানুজন ধারণা মৌলিক ३. ব্যাপক সংযোগ: সীমিত গ্রাফ, অসীম গ্রাফ, সম্ভাবনা তত্ত্ব এবং সমন্বয় গণিত কার্যকরভাবে সংযুক্ত করেছেন ४. স্পষ্ট কাঠামো: পত্রটি ভালভাবে সংগঠিত, প্রেরণা থেকে প্রযুক্তিগত বিবরণ পর্যন্ত স্পষ্ট

অপূর্ণতা

१. সীমিত প্রয়োগ: প্রধানত তাত্ত্বিক ফলাফল, ব্যবহারিক প্রয়োগের পরিস্থিতি যথেষ্ট স্পষ্ট নয় २. গণনাগত কঠিনতা: যদিও তাত্ত্বিক কাঠামো স্থাপন করেছেন, প্রকৃত গণনা এখনও কঠিন ३. বিশেষত্ব: সবচেয়ে শক্তিশালী ফলাফল শুধুমাত্র বিশেষ গ্রাফ শ্রেণীতে প্রযোজ্য

প্রভাব

१. তাত্ত্বিক অবদান: একমডুলার র‍্যান্ডম গ্রাফ বর্ণালী তত্ত্বের জন্য ভিত্তিগত ফলাফল প্রদান করেছেন २. পদ্ধতিগত মূল্য: বর্ণালী বিয়োজন পদ্ধতি অন্যান্য সমস্যায় প্রয়োগযোগ্য হতে পারে ३. আন্তঃশাখা প্রভাব: একাধিক গাণিতিক শাখা সংযুক্ত করেছেন, অন্যান্য গবেষণা অনুপ্রাণিত করতে পারে

প্রযোজ্য পরিস্থিতি

१. তাত্ত্বিক গবেষণা: গ্রাফ বর্ণালী তত্ত্ব, র‍্যান্ডম গ্রাফ তত্ত্ব, এরগোডিক তত্ত্ব २. নেটওয়ার্ক বিশ্লেষণ: বৃহৎ-স্কেল নেটওয়ার্কের বর্ণালী সম্পত্তি বিশ্লেষণ ३. অ্যালগরিদম ডিজাইন: বর্ণালী সম্পত্তির উপর ভিত্তি করে গ্রাফ অ্যালগরিদম ডিজাইন

প্রযুক্তিগত বিবরণ সম্পূরক

মূল অসমতা

পত্রের মূল প্রযুক্তিগত ফলাফল হল যেকোনো স্বাভাবিক ব্লক ফ্যাক্টর f ∈ R এর জন্য:

n√⟨Mnf,f⟩ ≤ K^(2/n) * n√E_ν*[p_n(o,o)] ≤ (1+o(1))ρ(G,o)

ভর স্থানান্তর নীতির প্রয়োগ

ভর স্থানান্তর নীতি একাধিক স্থানে মূল ভূমিকা পালন করে:

  • কঙ্কাল মার্কভ শৃঙ্খলের স্থিরতা প্রমাণ করা
  • স্থানীয় এবং বৈশ্বিক মেট্রিকের মধ্যে সম্পর্ক স্থাপন করা
  • ব্লক ফ্যাক্টরের নর্ম নিয়ন্ত্রণ করা

এই সিস্টেমেটিক ব্যবহার লেখকদের এই সরঞ্জামের গভীর বোঝাপড়া প্রদর্শন করে।