2025-11-20T08:49:14.495176

Measurable domatic partitions

Hou

Let $Î$ be a compact Polish group of finite topological dimension. For a countably infinite subset $S\subseteq Î$, a domatic $\aleph_0$-partition (for its Schreier graph on $Î$) is a partial function $f:Î\rightharpoonup\mathbb{N}$ such that for every $x\in Î$, one has $f[S\cdot x]=\mathbb{N}$. We show that a continuous domatic $\aleph_0$-partition exists, if and only if a Baire measurable domatic $\aleph_0$-partition exists, if and only if the topological closure of $S$ is uncountable. A Haar measurable domatic $\aleph_0$-partition exists for all choices of $S$. We also investigate domatic partitions in the general descriptive graph combinatorial setting.

academic

পরিমাপযোগ্য ডোমেটিক বিভাজন

মৌলিক তথ্য

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

সারসংক্ষেপ

এই নিবন্ধটি সীমিত টপোলজিক্যাল মাত্রার সংক্ষিপ্ত পোলিশ গ্রুপগুলিতে পরিমাপযোগ্য আধিপত্য বিভাজনের সমস্যা অধ্যয়ন করে। সংক্ষিপ্ত পোলিশ গ্রুপ Γ এবং এর গণনাযোগ্য অসীম উপসেট S⊆Γ এর জন্য, আধিপত্য ℵ₀-বিভাজন হল একটি আংশিক ফাংশন f:Γ⇀ℕ যেমন প্রতিটি x∈Γ এর জন্য fS·x=ℕ। লেখক প্রমাণ করেছেন যে ক্রমাগত আধিপত্য ℵ₀-বিভাজন বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি বেয়ার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন বিদ্যমান থাকে, যদি এবং শুধুমাত্র যদি S এর টপোলজিক্যাল বন্ধন অগণনীয় হয়। S এর সমস্ত পছন্দের জন্য, হার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন বিদ্যমান। নিবন্ধটি সাধারণ বর্ণনামূলক গ্রাফ সমন্বয় সেটিংয়ে আধিপত্য বিভাজনও অধ্যয়ন করে।

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

সমস্যার উৎস

এই গবেষণা অসীম গ্রাফে ক্লাসিক্যাল গ্রাফ তত্ত্বের আধিপত্য বিভাজন সমস্যার সম্প্রসারণ থেকে উদ্ভূত। আধিপত্য বিভাজন সমস্যা গ্রাফের শীর্ষবিন্দুগুলিকে রঙ করার দাবি করে যাতে প্রতিটি শীর্ষবিন্দুর প্রতিবেশী সমস্ত রঙ ধারণ করে। এই ধারণাটি প্রাথমিকভাবে জেলিংকা দ্বারা সীমিত হাইপারকিউব গ্রাফে অধ্যয়ন করা হয়েছিল, তিনি প্রমাণ করেছেন যে n-নিয়মিত হাইপারকিউব গ্রাফ Qₙ একটি আধিপত্য n-বিভাজন স্বীকার করে যদি এবং শুধুমাত্র যদি n হল 2 এর শক্তি।

গবেষণার তাৎপর্য

তাত্ত্বিক তাৎপর্য: ক্লাসিক্যাল সীমিত গ্রাফ আধিপত্য বিভাজন তত্ত্বকে অসীম ক্ষেত্রে সম্প্রসারিত করা, বিশেষত বর্ণনামূলক সেট তত্ত্ব কাঠামোতে পরিমাপযোগ্যতা সমস্যা অধ্যয়ন করা
আন্তঃশৃঙ্খলাবদ্ধ মূল্য: গ্রাফ তত্ত্ব, টপোলজিক্যাল গ্রুপ তত্ত্ব, বর্ণনামূলক সেট তত্ত্ব এবং পরিমাপ তত্ত্বের মতো একাধিক গাণিতিক শাখাকে সংযুক্ত করা
প্রযুক্তিগত উদ্ভাবন: বিভিন্ন পরিমাপযোগ্যতা শর্তের অধীনে আধিপত্য বিভাজনের অস্তিত্বের প্রথম সিস্টেমেটিক অধ্যয়ন

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

ক্লাসিক্যাল সীমিত গ্রাফ আধিপত্য বিভাজন তত্ত্ব সরাসরি অসীম ক্ষেত্রে সম্প্রসারিত করা যায় না
বিভিন্ন পরিমাপযোগ্যতা প্রয়োজনীয়তা পরিচালনার জন্য একীভূত কাঠামোর অভাব
শ্রেয়ার গ্রাফে আধিপত্য বিভাজনের বোঝাপড়া যথেষ্ট গভীর নয়

মূল অবদান

আধিপত্য ℵ₀-বিভাজনের অস্তিত্বের সম্পূর্ণ বৈশিষ্ট্য প্রতিষ্ঠা: সীমিত মাত্রার সংক্ষিপ্ত পোলিশ গ্রুপের জন্য, প্রমাণ করা হয়েছে যে ক্রমাগত এবং বেয়ার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজনের অস্তিত্বের প্রয়োজনীয় এবং যথেষ্ট শর্ত হল উৎপাদক সেট S এর টপোলজিক্যাল বন্ধন অগণনীয়
পরিমাপ তাত্ত্বিক আধিপত্য বিভাজনের সার্বজনীন অস্তিত্ব প্রমাণ: যেকোনো পোলিশ গ্রুপ এবং বোরেল সম্ভাব্যতা পরিমাপের জন্য, প্রমাণ করা হয়েছে যে μ-পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন সর্বদা বিদ্যমান
খোলা সেট আধিপত্য বিভাজন নির্মাণের প্রযুক্তি বিকাশ: মাত্রা তত্ত্ব এবং লোভাজ স্থানীয় লেম্মার মাধ্যমে, খোলা সেট আধিপত্য সীমিত বিভাজন নির্মাণের একটি সাধারণ পদ্ধতি প্রদান করা
যোগ সেট তত্ত্বের প্রয়োগ প্রদান: এরডোস-কুনেন-মৌলডিন সম্পর্কে যোগ সেটের ক্লাসিক্যাল ফলাফল সাধারণীকরণ করা
প্রান্ত রঙ আধিপত্য বিভাজন তত্ত্ব প্রতিষ্ঠা: আধিপত্য বিভাজনের প্রান্ত রঙ সংস্করণ অধ্যয়ন করা, অস্তিত্ব এবং অ-অস্তিত্ব ফলাফল প্রদান করা

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

কাজের সংজ্ঞা

G যদি শীর্ষবিন্দু সেট V এর উপর একটি নির্দেশিত গ্রাফ হয়, তাহলে আধিপত্য k-বিভাজন হল k টি পারস্পরিক বিচ্ছিন্ন আধিপত্য সেটের একটি ক্রম, যেখানে আধিপত্য সেট D সন্তুষ্ট করে যে প্রতিটি শীর্ষবিন্দু v∈V এর জন্য D∩N_G(v)≠∅। সমতুল্যভাবে, আধিপত্য আংশিক ফাংশন f:V⇀k সন্তুষ্ট করে যে প্রতিটি শীর্ষবিন্দু v এর জন্য fN_G(v)=k।

শ্রেয়ার গ্রাফ Sch(Γ,S,Γ) এর জন্য, যেখানে Γ একটি পোলিশ গ্রুপ, S⊆Γ একটি উপসেট, গ্রাফের প্রান্ত সেট হল {(γ,s·γ):γ∈Γ,s∈S}।

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

1. বিরোধী আধিপত্য ফলাফল (Anti-domaticity)

উপপাদ্য 2.1: পোলিশ গ্রুপ Γ যদি পোলিশ স্থান X এ ক্রমাগত কাজ করে, S⊆Γ যদি গণনাযোগ্য সংক্ষিপ্ত সেট হয়। যেকোনো বেয়ার পরিমাপযোগ্য ফাংশন f:X→ω এর জন্য, একটি অবশিষ্ট সেট বিদ্যমান যাতে f এই বিন্দুগুলিতে আধিপত্যশীল নয়।

প্রমাণের কৌশল: বেয়ার বিভাগ উপপাদ্য এবং সংক্ষিপ্ততা ব্যবহার করে, প্রমাণ করা হয় যে সংক্ষিপ্ত সেটে ক্রমাগত ফাংশনের চিত্র সীমাবদ্ধ হতে হবে।

2. খোলা সেট আধিপত্য বিভাজন নির্মাণ

উপপাদ্য 2.12 (প্রধান প্রযুক্তিগত লেম্মা): Γ যদি দ্বিপক্ষীয় অপরিবর্তনীয় মেট্রিক এবং সীমিত টপোলজিক্যাল মাত্রা সহ স্থানীয়ভাবে সংক্ষিপ্ত পোলিশ গ্রুপ হয়। প্রতিটি k,n∈ℕ এর জন্য, একটি N=N(k,n) বিদ্যমান যাতে F₀,...,Fₙ₋₁⊆Γ আকারের যেকোনো সেটের জন্য, পারস্পরিক বিচ্ছিন্ন খোলা সেটের একটি ক্রম D₀,...,Dₖ₋₁ বিদ্যমান, প্রতিটি Fᵢ·γ প্রতিটি Dⱼ এর সাথে ছেদ করে।

প্রমাণের কৌশল:

গ্লিসন-ইয়ামাবে উপপাদ্য ব্যবহার করে স্থানীয়ভাবে সংক্ষিপ্ত পোলিশ গ্রুপের মাত্রা বৈশিষ্ট্য নির্ধারণ করা
খোলা সেটের প্যাকিং নির্মাণ, মাত্রা বৃদ্ধি নিয়ন্ত্রণ করা
র্যান্ডম রঙ পরিচালনার জন্য লোভাজ স্থানীয় লেম্মা প্রয়োগ করা

3. খোলা জোড়া সম্পত্তি (Open Pair Property)

সংজ্ঞা 2.13: অসীম সংক্ষিপ্ত পোলিশ গ্রুপ Γ খোলা জোড়া সম্পত্তি রাখে, যদি প্রতিটি সীমিত সম্পূর্ণ সেট পরিবার P₀,...,Pₙ₋₁ এর জন্য, দুটি বিচ্ছিন্ন খোলা সেট A₀,A₁ বিদ্যমান যা সমস্ত Pᵢ কে আধিপত্য করে।

লেম্মা 2.14: সীমিত মাত্রার অসীম সংক্ষিপ্ত পোলিশ গ্রুপ খোলা জোড়া সম্পত্তি রাখে।

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

মাত্রা তত্ত্বের প্রয়োগ: প্রথমবারের মতো টপোলজিক্যাল মাত্রা তত্ত্বকে সিস্টেমেটিকভাবে আধিপত্য বিভাজন সমস্যায় প্রয়োগ করা, সীমানা মাত্রা নিয়ন্ত্রণের মাধ্যমে খোলা সেট বিভাজন বাস্তবায়ন করা
পরিমাপ এবং বিভাগের একীভূত পরিচালনা: পরিমাপ তাত্ত্বিক এবং বেয়ার বিভাগ সংস্করণ একযোগে পরিচালনার প্রযুক্তি বিকাশ করা
শ্রেয়ার গ্রাফের বিশেষ কাঠামো: গ্রুপ ক্রিয়াকলাপের বিশেষ সম্পত্তি ব্যবহার করে, বিমূর্ত গ্রাফ সমস্যাকে গ্রুপ তাত্ত্বিক সমস্যায় রূপান্তরিত করা

প্রধান ফলাফল

মূল উপপাদ্য

উপপাদ্য 1.1 (অনুসিদ্ধান্ত 2.18): Γ যদি সীমিত মাত্রার সংক্ষিপ্ত পোলিশ গ্রুপ হয়, S⊆Γ যদি উপসেট হয়। তাহলে Sch(Γ,S,Γ) খোলা সেট আধিপত্য ℵ₀-বিভাজন স্বীকার করে যদি এবং শুধুমাত্র যদি বেয়ার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন স্বীকার করে যদি এবং শুধুমাত্র যদি S⊆Γ অগণনীয় হয়।

উপপাদ্য 1.2 (অনুসিদ্ধান্ত 2.19): S⊆ℝⁿ যদি হয়। তাহলে Sch(ℝⁿ,S,ℝⁿ) খোলা সেট বা বেয়ার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন স্বীকার করে যদি এবং শুধুমাত্র যদি S অগণনীয় বা S অসীম হয়।

উপপাদ্য 1.3 (অনুসিদ্ধান্ত 3.6): Γ যদি পোলিশ গ্রুপ হয়, μ যদি Γ এর উপর বোরেল সম্ভাব্যতা পরিমাপ হয়, S⊆Γ যদি গণনাযোগ্য অসীম উপসেট হয়। তাহলে Sch(Γ,S,Γ) μ-পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজন স্বীকার করে।

প্রয়োগ ফলাফল

উপপাদ্য 1.5 (অনুসিদ্ধান্ত 2.29): P⊆ℝⁿ যদি অ-খালি বন্ধ নিখুঁত উপসেট হয়। তাহলে 2^ℵ₀ টি পারস্পরিক বিচ্ছিন্ন বন্ধ উপসেট পরিবার {Cᵢ:i<2^ℵ₀} বিদ্যমান, যাতে P+Cᵢ=ℝⁿ এবং Cᵢ+Cⱼ=ℝⁿ সমস্ত i,j<2^ℵ₀ এর জন্য।

নেতিবাচক ফলাফল

উপপাদ্য 4.3: সম্পূর্ণ চক্রাকার অনির্দেশিত ℵ₀-নিয়মিত চক্র-মুক্ত বোরেল গ্রাফ G পোলিশ স্থানে বিদ্যমান, যা বেয়ার পরিমাপযোগ্য আধিপত্য 3-বিভাজন স্বীকার করে না।

উপপাদ্য 4.5 (ওয়েইলাচার): চক্র-মুক্ত সরল অনির্দেশিত ℵ₀-নিয়মিত চক্র-মুক্ত বোরেল গ্রাফ G বিদ্যমান, যা প্রতিসম বোরেল আধিপত্য প্রান্ত 2-বিভাজন স্বীকার করে না।

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

মাত্রা নিয়ন্ত্রণ প্রযুক্তি

লেম্মা 2.8 এর পুনরাবৃত্তিমূলক নির্মাণের মাধ্যমে, পোলিশ স্থান X এবং বন্ধ উপসেট M₀,...,Mᵣ₋₁ এর জন্য, একটি খোলা সেট U নির্মাণ করা যায় যাতে ∂U∩Mᵢ এর মাত্রা Mᵢ এর মাত্রার চেয়ে কঠোরভাবে ছোট। এটি সম্পূর্ণ তত্ত্বের প্রযুক্তিগত কেন্দ্রবিন্দু।

লোভী অ্যালগরিদম

মসৃণ বোরেল গ্রাফের জন্য, বোরেল আধিপত্য ℵ₀-বিভাজন নির্মাণের জন্য লোভী অ্যালগরিদম ব্যবহার করা যায়। অ্যালগরিদম প্রতিটি পদক্ষেপে বর্তমান শীর্ষবিন্দুর জন্য প্রথম অরঙ্গিত প্রতিবেশী নির্বাচন করে রঙ করে।

র্যান্ডম পদ্ধতি

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

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

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

সীমিত মাত্রার সংক্ষিপ্ত পোলিশ গ্রুপের জন্য, ক্রমাগত এবং বেয়ার পরিমাপযোগ্য আধিপত্য ℵ₀-বিভাজনের অস্তিত্ব সম্পূর্ণভাবে উৎপাদক সেটের টপোলজিক্যাল সম্পত্তি দ্বারা নির্ধারিত
পরিমাপ তাত্ত্বিক আধিপত্য ℵ₀-বিভাজন সর্বজনীন অস্তিত্ব রাখে
মাত্রা তত্ত্ব আধিপত্য বিভাজন সমস্যা পরিচালনার জন্য একটি কার্যকর সরঞ্জাম

সীমাবদ্ধতা

অসীম মাত্রার ক্ষেত্র এখনও খোলা (সমস্যা 2.20)
স্থানীয়ভাবে সীমিত গ্রাফে ফলাফল তুলনামূলকভাবে সীমিত
বোরেল আধিপত্য সীমিত বিভাজনের অস্তিত্ব সমস্যা জটিল

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

অসীম মাত্রার সংক্ষিপ্ত পোলিশ গ্রুপে আধিপত্য বিভাজন অধ্যয়ন করা
আরও সাধারণ মাত্রা নিয়ন্ত্রণ প্রযুক্তি বিকাশ করা
অন্যান্য সমন্বয় অপ্টিমাইজেশন সমস্যার সাথে সংযোগ অন্বেষণ করা

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

সুবিধা

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

অপূর্ণতা

প্রযুক্তিগত জটিলতা: প্রমাণ প্রযুক্তি অত্যন্ত জটিল, যা ফলাফলের অ্যাক্সেসযোগ্যতা সীমিত করতে পারে
খোলা সমস্যা: অসীম মাত্রার ক্ষেত্র সহ গুরুত্বপূর্ণ সমস্যা এখনও অমীমাংসিত
গণনামূলক জটিলতা: নির্মাণ অ্যালগরিদমের জটিলতা আলোচনা করা হয়নি

প্রভাব

এই নিবন্ধটি বর্ণনামূলক গ্রাফ সমন্বয় ক্ষেত্রে গুরুত্বপূর্ণ প্রভাব রাখে, এই ক্ষেত্রে নতুন প্রযুক্তিগত সরঞ্জাম এবং গবেষণা দিকনির্দেশনা প্রদান করে। মাত্রা তত্ত্ব পদ্ধতি অন্যান্য গ্রাফ তাত্ত্বিক সমস্যায় প্রয়োগ খুঁজে পেতে পারে।

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

এই পদ্ধতি নিম্নলিখিত ক্ষেত্রে প্রযোজ্য:

গ্রুপ কাঠামো সহ গ্রাফে সমন্বয় সমস্যা
পরিমাপযোগ্যতা বিবেচনা করা প্রয়োজন এমন অসীম সমন্বয় অপ্টিমাইজেশন সমস্যা
টপোলজিক্যাল গ্রুপে জ্যামিতিক সমস্যা

সংদর্ভ সূত্র

নিবন্ধটি 35 টি গুরুত্বপূর্ণ সংদর্ভ উদ্ধৃত করে, যা বর্ণনামূলক সেট তত্ত্ব, টপোলজিক্যাল গ্রুপ তত্ত্ব, গ্রাফ তত্ত্ব এবং সমন্বয়বিদ্যার একাধিক ক্ষেত্রের ক্লাসিক্যাল এবং অগ্রগামী কাজ অন্তর্ভুক্ত করে।