2025-11-25T07:46:18.118060

Triangle Ramsey numbers of complete graphs

Fox, Tidor, Zhang
A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}{3}\] for all sufficiently large $t$. We do so through a result on graph coloring: there exists an absolute constant $K$ such that every $r$-chromatic graph where every edge is contained in at least $K$ triangles must contain at least $\binom{r}{3}$ triangles in total.
academic

সম্পূর্ণ গ্রাফের ত্রিভুজ রামসে সংখ্যা

মৌলিক তথ্য

  • পেপার আইডি: 2312.06895
  • শিরোনাম: Triangle Ramsey numbers of complete graphs
  • লেখক: Jacob Fox (Stanford), Jonathan Tidor (Princeton), Shengtong Zhang (Stanford)
  • শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
  • প্রকাশনার সময়: arXiv:2312.06895v2 math.CO 1 Oct 2025
  • পেপার লিঙ্ক: https://arxiv.org/abs/2312.06895

সারসংক্ষেপ

একটি গ্রাফ GG কে HH-রামসে বলা হয়, যদি এর প্রান্তগুলির যেকোনো দ্বি-রঙায়নে একটি একরঙী HH অনুলিপি থাকে। HH এর FF-রামসে সংখ্যা rF(H)r_F(H) সংজ্ঞায়িত করা হয় সমস্ত HH-রামসে গ্রাফে FF অনুলিপির ন্যূনতম সংখ্যা হিসাবে। এটি গ্রাফের রামসে সংখ্যা এবং আকার রামসে সংখ্যার ধারণাকে সাধারণীকরণ করে। স্পিরো দ্বারা উত্থাপিত প্রশ্নের প্রতিক্রিয়ায়, লেখকরা প্রমাণ করেছেন যে যথেষ্ট বড় tt এর জন্য, rK3(Kt)=(r(Kt)3)r_{K_3}(K_t)=\binom{r(K_t)}{3}। প্রমাণটি গ্রাফ রঙায়নের একটি ফলাফলের উপর ভিত্তি করে: একটি পরম ধ্রুবক KK বিদ্যমান, যাতে প্রতিটি rr-রঙ সংখ্যার গ্রাফ যদি এর প্রতিটি প্রান্ত কমপক্ষে KK টি ত্রিভুজে থাকে, তাহলে গ্রাফটি মোট কমপক্ষে (r3)\binom{r}{3} টি ত্রিভুজ ধারণ করে।

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

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

  1. ক্লাসিক্যাল রামসে তত্ত্বের সম্প্রসারণ: ঐতিহ্যবাহী রামসে তত্ত্ব r(H)r(H) অধ্যয়ন করে (যাতে যেকোনো দ্বি-রঙায়ন একটি একরঙী HH অনুলিপি ধারণ করে), এই পেপারটি আরও সাধারণ FF-রামসে সংখ্যা rF(H)r_F(H) অধ্যয়ন করে (HH-রামসে গ্রাফে FF অনুলিপির সংখ্যা)।
  2. পরিচিত ফলাফল: চভাটাল প্রমাণ করেছেন যে rK2(Kt)=(r(Kt)2)r_{K_2}(K_t) = \binom{r(K_t)}{2}, অর্থাৎ সম্পূর্ণ গ্রাফ Kr(Kt)K_{r(K_t)} সমস্ত KtK_t-রামসে গ্রাফের মধ্যে সবচেয়ে কম প্রান্ত রাখে।
  3. স্পিরোর অনুমান: সমস্ত s≤ts \leq t এর জন্য, কি rKs(Kt)=(r(Kt)s)r_{K_s}(K_t) = \binom{r(K_t)}{s} সত্য?

গবেষণার গুরুত্ব

  • তাত্ত্বিক তাৎপর্য: এটি শীর্ষবিন্দু এবং প্রান্ত ছাড়া অন্যান্য উপগ্রাফ FF এর জন্য FF-রামসে সংখ্যা অধ্যয়নের প্রথম প্রচেষ্টা
  • পদ্ধতিগত উদ্ভাবন: রামসে তত্ত্বকে গ্রাফ রঙায়ন তত্ত্বের সাথে গভীরভাবে সংযুক্ত করে
  • সাধারণীকরণের মূল্য: অ্যালন-শিখেলম্যানের সাধারণীকৃত টুরান ফাংশন ex(n,F,H)ex(n,F,H) এর মতো

মূল অবদান

  1. প্রধান উপপাদ্য: প্রমাণ করেছেন যে যথেষ্ট বড় tt এর জন্য, rK3(Kt)=(r(Kt)3)r_{K_3}(K_t) = \binom{r(K_t)}{3} (উপপাদ্য 1.3)
  2. মূল লেম্মা: গ্রাফ রঙায়ন এবং ত্রিভুজ গণনার মধ্যে সংযোগ স্থাপন করেছেন (উপপাদ্য 1.5)
  3. প্রযুক্তিগত উদ্ভাবন: স্থানীয়ভাবে ঘন গ্রাফ পরিচালনার জন্য রঙায়ন কৌশল বিকশিত করেছেন
  4. পদ্ধতিগত অবদান: সাধারণ rKs(Kt)r_{K_s}(K_t) সমস্যা অধ্যয়নের জন্য একটি কাঠামো প্রদান করেছেন

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

মূল কৌশল

প্রমাণটি দুটি প্রধান পদক্ষেপে বিভক্ত:

পদক্ষেপ 1: রামসে সম্পত্তি এবং রঙ সংখ্যার সংযোগ (প্রস্তাব 1.4)

মূল পর্যবেক্ষণ:

  • যদি GG একটি KtK_t-রামসে গ্রাফ হয়, তাহলে χ(G)≥r(Kt)\chi(G) \geq r(K_t)
  • যদি GG একটি KtK_t-রামসে সংকটপূর্ণ গ্রাফ হয়, তাহলে GG এর প্রতিটি প্রান্ত কোনো KtK_t এ থাকে

প্রমাণের চিন্তাভাবনা: প্রতিফলন দ্বারা, ধরে নিন যে একটি (r(Kt)−1)(r(K_t)-1)-রঙায়ন বিদ্যমান, তাহলে একটি KtK_t-রামসে গ্রাফের একটি একরঙী KtK_t ছাড়া দ্বি-রঙায়ন তৈরি করা যায়।

পদক্ষেপ 2: স্থানীয়ভাবে ঘন গ্রাফের ত্রিভুজ নিম্নসীমা (উপপাদ্য 1.5)

মূল উপপাদ্য: একটি পরম ধ্রুবক KK বিদ্যমান, যাতে প্রতিটি rr-রঙ সংখ্যার গ্রাফ যদি এর প্রতিটি প্রান্ত কমপক্ষে KK টি ত্রিভুজে থাকে, তাহলে গ্রাফটি কমপক্ষে (r3)\binom{r}{3} টি ত্রিভুজ ধারণ করে।

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

মৌলিক টুরান যুক্তি (বিভাগ 2)

উপপাদ্য 2.2: যেকোনো rr-রঙ সংখ্যার গ্রাফ GG এর জন্য, t(G)+12e(G)≥(r3)+12(r2)t(G) + \frac{1}{2}e(G) \geq \binom{r}{3} + \frac{1}{2}\binom{r}{2}

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

  1. গ্রাফ ক্রম তৈরি করুন G⊇G0⊇G0′⊇G1⊇⋯G \supseteq G_0 \supseteq G'_0 \supseteq G_1 \supseteq \cdots
  2. প্রতিটি Gi′G'_i একটি (r−i)(r-i)-সংকটপূর্ণ উপগ্রাফ, IiI_i হল Gi′G'_i এ সর্বাধিক স্বাধীন সেট
  3. প্রতিটি শীর্ষবিন্দুর ত্রিভুজ সংখ্যা অনুমান করতে টুরান উপপাদ্য প্রয়োগ করুন

রঙায়ন তত্ত্বের সরঞ্জাম (বিভাগ 3)

  1. গ্যালাই উপপাদ্য: ছোট সংকটপূর্ণ গ্রাফের কাঠামো
  2. ভু উপপাদ্য: স্থানীয়ভাবে বিরল গ্রাফের তালিকা রঙ সংখ্যার উপরের সীমা
  3. হ্যারিস উপপাদ্য: ত্রিভুজ সংখ্যার উপর ভিত্তি করে রঙ সংখ্যা
  4. নতুন লেম্মা 3.5: অবক্ষয়িত স্থানীয়ভাবে বিরল গ্রাফের রঙায়ন উন্নতি

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

রৈখিক আকারের গ্রাফের প্রক্রিয়াকরণ (বিভাগ 4)

লেম্মা 4.1: শীর্ষবিন্দু সংখ্যা O(r)O(r) এবং ক্লিক সংখ্যা rr এর কাছাকাছি সহ rr-সংকটপূর্ণ গ্রাফের জন্য, ত্রিভুজ সংখ্যা (r3)\binom{r}{3} অতিক্রম করে

প্রস্তাব 4.2: শীর্ষবিন্দু সংখ্যা [2r−1,Cr][2r-1, Cr] পরিসরে থাকা rr-সংকটপূর্ণ গ্রাফের জন্য, ত্রিভুজ সংখ্যা (r3)\binom{r}{3} অতিক্রম করে

সাধারণ ক্ষেত্রের প্রমাণ (বিভাগ 5)

তিনটি ক্ষেত্রে বিভক্ত প্রক্রিয়াকরণ:

  1. ছোট ক্লিক সংখ্যার ক্ষেত্র: রামসে-টুরান উপপাদ্য ব্যবহার করুন
  2. বড় ক্লিক সংখ্যার ক্ষেত্র: পূর্ববর্তী রৈখিক আকারের ফলাফল প্রয়োগ করুন
  3. সমন্বিত যুক্তি: ওজন-সংশোধিত স্বাধীন সেট বিয়োজন মাধ্যমে

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

1. টুরান যুক্তির সূক্ষ্মকরণ

  • ক্লাসিক্যাল টুরান উপপাদ্যের সহজ প্রয়োগ নয়, বরং সংকটপূর্ণ গ্রাফ বিয়োজনের মাধ্যমে সঠিক সীমা অর্জন করা
  • বড় ক্লিক ধারণকারী ক্ষেত্রে পরিচালনার জন্য "সংশোধিত ওজন" ধারণা প্রবর্তন করা

2. স্থানীয় শর্তের বৈশ্বিকীকরণ

  • "প্রতিটি প্রান্ত KK টি ত্রিভুজে থাকে" এর স্থানীয় শর্ত থেকে বৈশ্বিক ত্রিভুজ নিম্নসীমা অনুমান করা
  • সম্ভাব্য পদ্ধতি এবং ঘনীভবন অসমতা (Azuma-Hoeffding, Talagrand অসমতা) সংযুক্ত করা

3. বহু-স্কেল বিশ্লেষণ

  • বিভিন্ন আকারের গ্রাফের জন্য বিভিন্ন কৌশল প্রয়োগ করা: গ্যালাই উপপাদ্য (ছোট গ্রাফ), রামসে-টুরান (মাঝারি গ্রাফ), সম্ভাব্য রঙায়ন (বড় গ্রাফ)

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

এই পেপারটি একটি বিশুদ্ধ তাত্ত্বিক কাজ, যা পরীক্ষামূলক যাচাইকরণ জড়িত নয়, সমস্ত ফলাফল গাণিতিক প্রমাণের মাধ্যমে অর্জিত হয়েছে।

প্রধান ফলাফল

মূল উপপাদ্য

উপপাদ্য 1.3: যথেষ্ট বড় tt এর জন্য, rK3(Kt)=(r(Kt)3)r_{K_3}(K_t) = \binom{r(K_t)}{3}

সহায়ক ফলাফল

  1. উপপাদ্য 1.5: স্থানীয়ভাবে ঘন গ্রাফের ত্রিভুজ নিম্নসীমা
  2. উপপাদ্য 2.2: উন্নত টুরান-ধরনের অসমতা
  3. লেম্মা 3.5: অবক্ষয়িত গ্রাফের রঙায়ন উন্নতি

অ্যাসিম্পটোটিক ফলাফল

অনুসিদ্ধান্ত 2.3: rK3(Kt)≥(1−o(1))(r(Kt)3)r_{K_3}(K_t) \geq (1-o(1))\binom{r(K_t)}{3}

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

ক্লাসিক্যাল ফলাফল

  • চভাটাল উপপাদ্য: rK2(Kt)=(r(Kt)2)r_{K_2}(K_t) = \binom{r(K_t)}{2}
  • রামসে তত্ত্ব: ক্লাসিক্যাল r(Kt)r(K_t) এর গবেষণা
  • আকার রামসে সংখ্যা: r^(H)\hat{r}(H) এর সম্পর্কিত কাজ

আধুনিক উন্নয়ন

  • সাধারণীকৃত টুরান সমস্যা: অ্যালন-শিখেলম্যানের ex(n,F,H)ex(n,F,H)
  • হাইপারগ্রাফ আকার রামসে সংখ্যা: ম্যাকে এবং অন্যদের কাজ
  • সম্ভাব্য পদ্ধতি: রোডল-রুসিনস্কির থ্রেশহোল্ড ফাংশন

প্রযুক্তিগত সরঞ্জাম

  • গ্রাফ রঙায়ন তত্ত্ব: মলয়-রিড এর স্থানীয়ভাবে বিরল গ্রাফ রঙায়ন
  • রামসে-টুরান তত্ত্ব: এরডস-সোস উপপাদ্য
  • সম্ভাব্য ঘনীভবন: আধুনিক সম্ভাব্য অসমতার প্রয়োগ

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

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

  1. স্পিরো অনুমানটি যথেষ্ট বড় tt এর জন্য s=3s=3 ক্ষেত্রে নিশ্চিত করেছেন
  2. রামসে তত্ত্ব এবং গ্রাফ রঙায়ন তত্ত্বের মধ্যে নতুন সংযোগ স্থাপন করেছেন
  3. স্থানীয়ভাবে ঘন গ্রাফ পরিচালনার জন্য নতুন কৌশল বিকশিত করেছেন

সীমাবদ্ধতা

  1. সীমাবদ্ধতা: শুধুমাত্র "যথেষ্ট বড় tt" এর জন্য প্রযোজ্য, ছোট tt ক্ষেত্র সমাধান করা হয়নি
  2. বিশেষ ক্ষেত্র: শুধুমাত্র s=3s=3 ক্ষেত্র সমাধান করেছেন, সাধারণ ss এখনও খোলা
  3. ধ্রুবক নির্ভরতা: প্রমাণে ধ্রুবক KK খুব বড় হতে পারে, ব্যবহারিক প্রয়োগ সীমিত

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

  1. সম্পূর্ণ অনুমান: সাধারণ rKs(Kt)=(r(Kt)s)r_{K_s}(K_t) = \binom{r(K_t)}{s} প্রমাণ করা
  2. সীমাবদ্ধ ক্ষেত্র: ছোট tt মানের ক্ষেত্র পরিচালনা করা
  3. অন্যান্য গ্রাফ জোড়া: (F,H)(F,H) সম্পূর্ণ গ্রাফ নয় এমন ক্ষেত্র অধ্যয়ন করা
  4. গণনামূলক জটিলতা: rF(H)r_F(H) এর গণনামূলক জটিলতা বিশ্লেষণ

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

সুবিধা

  1. তাত্ত্বিক গভীরতা: একাধিক গাণিতিক শাখা (রামসে তত্ত্ব, গ্রাফ রঙায়ন, সম্ভাব্য পদ্ধতি) দক্ষতার সাথে সংযুক্ত করা
  2. প্রযুক্তিগত উদ্ভাবন: স্থানীয় ঘন শর্ত পরিচালনার জন্য নতুন পদ্ধতি বিকশিত করা
  3. কাঠামোগত স্পষ্টতা: প্রমাণ স্তরযুক্ত অগ্রগতি, যুক্তি কঠোর
  4. সাধারণতা: আরও বিস্তৃত FF-রামসে সংখ্যা সমস্যা অধ্যয়নের ভিত্তি স্থাপন করা

প্রযুক্তিগত হাইলাইট

  1. ওজন সংশোধন কৌশল: স্বাধীন সেট নির্বাচনে বড় ক্লিক ক্ষেত্র পরিচালনার জন্য সংশোধিত ওজন প্রবর্তন করা
  2. বহু-স্কেল বিশ্লেষণ: বিভিন্ন আকারের গ্রাফের জন্য সবচেয়ে উপযুক্ত কৌশল প্রয়োগ করা
  3. সম্ভাব্য রঙায়ন: নিশ্চিত সমস্যায় সম্ভাব্য পদ্ধতির দক্ষ প্রয়োগ

অপূর্ণতা

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

প্রভাব মূল্যায়ন

  1. তাত্ত্বিক অবদান: FF-রামসে সংখ্যা তত্ত্বের জন্য গুরুত্বপূর্ণ ভিত্তি স্থাপন করা
  2. পদ্ধতিগত মূল্য: প্রদত্ত প্রযুক্তিগত কাঠামো অন্যান্য সমন্বয় সমস্যায় প্রযোজ্য হতে পারে
  3. পরবর্তী গবেষণা: সম্পূর্ণ স্পিরো অনুমান সমাধানের পথ প্রশস্ত করা

প্রয়োগযোগ্য পরিস্থিতি

  1. তাত্ত্বিক গবেষণা: সমন্বয় গণিত, চরম গ্রাফ তত্ত্ব গবেষণা
  2. পদ্ধতি ধার: অনুরূপ স্থানীয়-বৈশ্বিক সমস্যা বিশ্লেষণ
  3. শিক্ষাগত মূল্য: আধুনিক সমন্বয় গণিতের প্রযুক্তিগত সমন্বিত প্রয়োগ প্রদর্শন করা

তথ্যসূত্র

পেপারটি 23টি গুরুত্বপূর্ণ তথ্যসূত্র উদ্ধৃত করে, যা অন্তর্ভুক্ত করে:

  • ক্লাসিক্যাল রামসে তত্ত্ব (এরডস এবং অন্যরা)
  • আধুনিক গ্রাফ রঙায়ন তত্ত্ব (অ্যালন-ক্রিভেলেভিচ-সুডাকভ, মলয়-রিড)
  • সম্ভাব্য পদ্ধতি (ঘনীভবন অসমতা সম্পর্কিত সাহিত্য)
  • সাধারণীকৃত টুরান সমস্যা (অ্যালন-শিখেলম্যান এবং অন্যরা)

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চমানের তাত্ত্বিক পেপার, যা রামসে তত্ত্বের এই ক্লাসিক্যাল ক্ষেত্রে গুরুত্বপূর্ণ অগ্রগতি অর্জন করেছে। যদিও এটি শুধুমাত্র সাধারণ অনুমানের একটি বিশেষ ক্ষেত্র সমাধান করেছে, বিকশিত প্রযুক্তি এবং চিন্তাভাবনা এই ক্ষেত্রের আরও উন্নয়নের জন্য গুরুত্বপূর্ণ সরঞ্জাম প্রদান করে। পেপারের প্রযুক্তিগত গভীরতা এবং উদ্ভাবনী প্রকৃতি উভয়ই অসাধারণ, এটি সমন্বয় গণিত ক্ষেত্রের একটি গুরুত্বপূর্ণ অবদান।