প্রদত্ত ক্রোমেটিক সংখ্যা সহ ন্যূনতম অ-রঙ-নির্বাচনযোগ্য গ্রাফ

মৌলিক তথ্য

• পেপার আইডি: 2201.02060
• শিরোনাম: প্রদত্ত ক্রোমেটিক সংখ্যা সহ ন্যূনতম অ-রঙ-নির্বাচনযোগ্য গ্রাফ
• লেখক: জিয়ালু ঝু, জুডিং ঝু
• শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
• প্রকাশনার সময়: ২০২৪ সালের ১৩ সেপ্টেম্বর
• পেপার লিঙ্ক: https://arxiv.org/abs/2201.02060

সারসংক্ষেপ

গ্রাফ $G$ কে রঙ-নির্বাচনযোগ্য (chromatic-choosable) বলা হয় যদি $\chi(G) = ch(G)$ হয়। একটি প্রাকৃতিক প্রশ্ন হল প্রদত্ত ক্রোমেটিক সংখ্যা $k$ সহ অ-$k$-নির্বাচনযোগ্য গ্রাফে শীর্ষবিন্দুর সংখ্যার ন্যূনতম মান নির্ধারণ করা। ওহবা অনুমান এবং নোয়েল, রিড এবং উ দ্বারা প্রমাণিত: শীর্ষবিন্দু সংখ্যা $|V(G)| \leq 2k+1$ সহ $k$-রঙের গ্রাফ $G$ সবই $k$-নির্বাচনযোগ্য। এই উপরের সীমা কঠোর। যখন $k$ সমান হয় তখন জানা যায়, $G=K_{3*(k/2+1),1*(k/2-1)}$ এবং $G=K_{4,2*(k-1)}$ হল শীর্ষবিন্দু সংখ্যা $2k+2$ সহ অ-$k$-নির্বাচনযোগ্য $k$-রঙের গ্রাফ। এই পেপারের প্রধান ফলাফল হল: অন্যান্য সমস্ত শীর্ষবিন্দু সংখ্যা $2k+2$ সহ $k$-রঙের গ্রাফ $k$-নির্বাচনযোগ্য। বিশেষত, যদি $\chi(G)$ বিজোড় হয় এবং $|V(G)| \leq 2\chi(G)+2$, তাহলে $G$ রঙ-নির্বাচনযোগ্য, যা নোয়েলের অনুমানকে প্রমাণ করে।

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

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

1. তালিকা রঙ সমস্যা: তালিকা রঙ হল ক্লাসিক্যাল গ্রাফ রঙের প্রাকৃতিক সম্প্রসারণ, যা এরডোস-রুবিন-টেইলর এবং ভিজিং দ্বারা ১৯৭০ এর দশকে স্বাধীনভাবে প্রবর্তিত হয়েছিল। গ্রাফ $G$ এর তালিকা বরাদ্দ $L$ এর জন্য, যদি একটি উপযুক্ত রঙ বিদ্যমান থাকে যেখানে প্রতিটি শীর্ষবিন্দু $v$ $L(v)$ থেকে একটি রঙ পায়, তাহলে $G$ কে $L$-রঙযোগ্য বলা হয়।
2. রঙ-নির্বাচনযোগ্য গ্রাফ: গ্রাফ $G$ কে রঙ-নির্বাচনযোগ্য বলা হয় যদি এর ক্রোমেটিক সংখ্যা $\chi(G)$ নির্বাচন সংখ্যা $ch(G)$ এর সমান হয়। এই ধরনের গ্রাফ গ্রাফ তত্ত্বে গুরুত্বপূর্ণ স্থান রাখে এবং অনেক কঠিন সমস্যার সাথে সম্পর্কিত।
3. ওহবা অনুমান: ওহবা অনুমান বলে যে যেকোনো ধনাত্মক পূর্ণসংখ্যা $k$ এর জন্য, সর্বাধিক $2k+1$ শীর্ষবিন্দু সহ $k$-রঙের গ্রাফ সবই $k$-নির্বাচনযোগ্য। এই অনুমান অবশেষে ২০১৫ সালে নোয়েল, রিড এবং উ দ্বারা প্রমাণিত হয়েছিল।

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

1. কঠোরতা বিশ্লেষণ: যদিও ওহবা অনুমান প্রমাণিত হয়েছে, এর কঠোরতা সমস্যা এখনও গভীর গবেষণার প্রয়োজন। পরিচিত প্রতিউদাহরণ শুধুমাত্র সমান $k$ এর ক্ষেত্রে সীমাবদ্ধ।
2. নোয়েল অনুমান: নোয়েল অনুমান বলে যে বিজোড় $k$ এর জন্য, শীর্ষবিন্দু সংখ্যা $2k+2$ সহ সমস্ত $k$-রঙের গ্রাফ $k$-নির্বাচনযোগ্য।
3. চরম গ্রাফ তত্ত্ব: প্রদত্ত ক্রোমেটিক সংখ্যার অধীনে অ-রঙ-নির্বাচনযোগ্য গ্রাফের ন্যূনতম শীর্ষবিন্দু সংখ্যা নির্ধারণ করা চরম গ্রাফ তত্ত্বের একটি মৌলিক সমস্যা।

মূল অবদান

1. সম্পূর্ণ বৈশিষ্ট্য: শীর্ষবিন্দু সংখ্যা $2k+2$ সহ অ-$k$-নির্বাচনযোগ্য সম্পূর্ণ $k$-অংশীয় গ্রাফের সম্পূর্ণ বৈশিষ্ট্য, প্রমাণ করে যে শুধুমাত্র $K_{4,2*(k-1)}$ এবং $K_{3*(k/2+1),1*(k/2-1)}$ (যখন $k$ সমান হয়) অ-$k$-নির্বাচনযোগ্য।
2. নোয়েল অনুমান প্রমাণ: প্রমাণ করেছে যে যখন $k$ বিজোড় হয়, প্রতিটি সর্বাধিক $2k+2$ শীর্ষবিন্দু সহ $k$-রঙের গ্রাফ রঙ-নির্বাচনযোগ্য।
3. ফাংশন $\beta(k)$ নির্ভুলভাবে নির্ধারণ: ফাংশন $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ এর জন্য, প্রমাণ করেছে যে2k + 2, & \text{যদি } k \text{ সমান হয়} \\ 2k + 3, & \text{যদি } k \text{ বিজোড় হয়} \end{cases}$$
4. প্রযুক্তিগত উদ্ভাবন: "প্রায় গ্রহণযোগ্য $L$-রঙ" এবং "ছদ্ম $L$-রঙ" এর মতো নতুন ধারণা প্রবর্তন করেছে এবং নতুন প্রমাণ কৌশল বিকশিত করেছে।

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

কাজের সংজ্ঞা

ধরুন $G$ একটি সম্পূর্ণ $k$-অংশীয় গ্রাফ, $L$ হল $G$ এর $k$-তালিকা বরাদ্দ। কাজ হল নির্ধারণ করা কোন শর্তে $G$ $L$-রঙযোগ্য, বিশেষত যখন $|V(G)| = 2k+2$ এবং $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$ (যখন $k$ সমান হয়)।

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

১. দ্বিপক্ষীয় গ্রাফ ম্যাচিং পদ্ধতি

• মৌলিক ধারণা: $V(G)$ কে স্বাধীন সেট পরিবার $\mathcal{S}$ তে বিভক্ত করুন, ভাগফল গ্রাফ $G/\mathcal{S}$ তৈরি করুন
• দ্বিপক্ষীয় গ্রাফ নির্মাণ: দ্বিপক্ষীয় গ্রাফ $B_\mathcal{S}$ তৈরি করুন, শীর্ষবিন্দু সেট $V(G/\mathcal{S})$ এবং $C_L$, প্রান্ত $\{v_S, c\}$ বিদ্যমান যদি এবং শুধুমাত্র যদি $c \in L_S(v_S)$
• হল উপপাদ্য প্রয়োগ: যদি $B_\mathcal{S}$ এ $V(G/\mathcal{S})$ কভার করার ম্যাচিং থাকে, তাহলে $L$-রঙ পান; অন্যথায় হল উপপাদ্য দ্বারা $X_\mathcal{S} \subseteq V(G/\mathcal{S})$ বিদ্যমান যেখানে $|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|$

২. ছদ্ম $L$-রঙ ধারণা

সংজ্ঞা: $G$ এর ছদ্ম $L$-রঙ হল উপযুক্ত রঙ $f$, যা সন্তুষ্ট করে:

• $f(v) \in C_L$ সমস্ত শীর্ষবিন্দু $v$ এর জন্য
• যদি $f(v) = c \notin L(v)$, তাহলে $f^{-1}(c) = \{v\}$ একক বিন্দু $f$-শ্রেণী

মূল বৈশিষ্ট্য:

• যদি $v$ ভুলভাবে রঙিত হয় ($f(v) \notin L(v)$), তাহলে $\{v\}$ অবশ্যই একক রঙ শ্রেণী হতে হবে
• এটি আংশিক রঙের জন্য নমনীয়তা প্রদান করে

৩. প্রায় গ্রহণযোগ্য রঙ

ঘন ঘন রঙ সংজ্ঞা: রঙ $c$ ঘন ঘন হয়, যদি নিম্নলিখিত শর্তগুলির মধ্যে একটি পূরণ করে:

1. $|L^{-1}(c)| \geq k + 2$
2. $|L^{-1}(c) \cap T| \geq \lambda$ (যেখানে $T$ একক বিন্দু অংশের সেট)
3. $|T| = \lambda - 1 \geq 1$ এবং $T \subseteq L^{-1}(c)$

প্রায় গ্রহণযোগ্য রঙ: ছদ্ম $L$-রঙ $f$ প্রায় গ্রহণযোগ্য, যদি প্রতিটি ভুলভাবে রঙিত শীর্ষবিন্দু ঘন ঘন রঙ দিয়ে রঙিত হয়।

প্রমাণ কৌশল

প্রথম পদক্ষেপ: বিশেষ ক্ষেত্র বাদ দেওয়া

লেমা ২.১ এর মাধ্যমে সমস্ত অংশ আকার সর্বাধিক ৩ সহ সম্পূর্ণ বহু-অংশীয় গ্রাফ পরিচালনা করুন, এই ধরনের গ্রাফ $g$-নির্বাচনযোগ্য করার জন্য পর্যাপ্ত শর্ত প্রতিষ্ঠা করুন।

দ্বিতীয় পদক্ষেপ: প্রতিফলন প্রমাণ কাঠামো

ধরুন $(G,L)$ উপপাদ্য ১.২ এর ন্যূনতম প্রতিউদাহরণ, অর্থাৎ:

• $|V(G)|$ ন্যূনতম
• শর্ত ১ এর অধীনে, $|C_L|$ ন্যূনতম

তৃতীয় পদক্ষেপ: ঘন ঘন রঙ বিশ্লেষণ

• প্রমাণ করুন সর্বাধিক $k-1$ ঘন ঘন রঙ আছে (লেমা ৭.১)
• আরও প্রমাণ করুন সর্বাধিক $k-p_1-1$ ঘন ঘন রঙ আছে (লেমা ৮.৩)
• যেখানে $p_1$ একক বিন্দু অংশের সংখ্যা

চতুর্থ পদক্ষেপ: চূড়ান্ত বিরোধ

$k-p_1$ ঘন ঘন রঙ সহ পরিস্থিতি তৈরি করে, বিরোধ উদ্ভব করুন, প্রমাণ সম্পূর্ণ করুন।

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

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

এই পেপার বিশুদ্ধ তাত্ত্বিক গবেষণা, প্রধানত গাণিতিক প্রমাণের মাধ্যমে ফলাফল যাচাই করে:

1. ছোট স্কেল যাচাইকরণ: $k \leq 7$ এর জন্য, সরাসরি যাচাই করুন সম্পর্কিত গ্রাফ শ্রেণী $k$-নির্বাচনযোগ্য
2. গঠনমূলক প্রমাণ: নির্দিষ্ট নির্মাণের মাধ্যমে প্রমাণ করুন কিছু গ্রাফ সত্যিই অ-$k$-নির্বাচনযোগ্য
3. আবেগপূর্ণ যাচাইকরণ: গাণিতিক আবেগ ব্যবহার করে লেমা ২.১ এর শর্ত যাচাই করুন

মূল লেমা যাচাইকরণ

• লেমা ৩.২: যদি $P$ $G$ এর $2^+$-অংশ হয়, তাহলে $\bigcap_{v \in P} L(v) = \emptyset$
• লেমা ৫.১: ছদ্ম রঙে একক বিন্দু সংখ্যার উপরের সীমা সম্পর্কে
• লেমা ৬.১: $G$ এর কোনো প্রায় গ্রহণযোগ্য $L$-রঙ নেই

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

প্রধান উপপাদ্য যাচাইকরণ

উপপাদ্য ১.२: ধরুন $G$ একটি সম্পূর্ণ $k$-অংশীয় গ্রাফ, $|V(G)| \leq 2k+2$, এবং যখন $k$ সমান হয় $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$, $L$ হল $G$ এর $k$-তালিকা বরাদ্দ, তাহলে $G$ $L$-রঙযোগ্য।

অনুসিদ্ধান্ত ১.३: যদি $k$ বিজোড় হয়, তাহলে প্রতিটি সর্বাধিক $2k+2$ শীর্ষবিন্দু সহ $k$-রঙের গ্রাফ রঙ-নির্বাচনযোগ্য।

অনুসিদ্ধান্ত १.४: ফাংশন $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ সন্তুষ্ট করে: