2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

ব্রাউন-এরডোস-সোস সমস্যার দ্বিঘাত ৮-প্রান্ত ক্ষেত্র সম্পর্কে

মৌলিক তথ্য

  • পেপার আইডি: 2506.01739
  • শিরোনাম: ব্রাউন-এরডোস-সোস সমস্যার দ্বিঘাত ৮-প্রান্ত ক্ষেত্র সম্পর্কে
  • লেখক: ওলেগ পিখুর্কো, শুমিন সান (ওয়ারউইক বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
  • প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৬ (arXiv সংস্করণ ২)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2506.01739

সারসংক্ষেপ

এই পেপারটি ব্রাউন-এরডোস-সোস সমস্যার দ্বিঘাত ৮-প্রান্ত ক্ষেত্র অধ্যয়ন করে। f(r)(n;s,k)f^{(r)}(n;s,k) কে nn টি শীর্ষবিন্দুর rr-সমরূপ হাইপারগ্রাফে সর্বোচ্চ প্রান্ত সংখ্যা হিসাবে সংজ্ঞায়িত করা হয় যা kk টি প্রান্ত ধারণ করে না এবং এই প্রান্তগুলি সর্বাধিক ss টি শীর্ষবিন্দু জুড়ে বিস্তৃত। ব্রাউন, এরডোস এবং সোস ১৯৭৩ সালে অনুমান করেছিলেন যে সমস্ত kk এর জন্য, সীমা lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k) বিদ্যমান। সম্প্রতি ডেলকোর্ট এবং পোস্টেল এই অনুমানটি সমাধান করেছেন, শাংগুয়ান এটি সমস্ত সমরূপতা r≥4r\ge 4 এ সাধারণীকরণ করেছেন। এই পেপারটি k=8k=8 এর ক্ষেত্রে বিবেচনা করে, প্রতিটি r≥4r\ge 4 এর জন্য সীমার মান নির্ধারণ করে এবং r=3r=3 এর জন্য একটি নিম্ন সীমা প্রদান করে।

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

  1. মূল সমস্যা: ব্রাউন-এরডোস-সোস সমস্যা rr-সমরূপ হাইপারগ্রাফের টুরান সংখ্যা অধ্যয়ন করে, অর্থাৎ নির্দিষ্ট নিষিদ্ধ উপগ্রাফ এড়ানোর শর্তে, nn টি শীর্ষবিন্দুর হাইপারগ্রাফ কতটি প্রান্ত ধারণ করতে পারে।
  2. সমস্যার গুরুত্ব: এটি চরম সমন্বয়বিদ্যার একটি মৌলিক সমস্যা, যা রামসে তত্ত্ব, টুরান তত্ত্ব এবং অন্যান্য মূল ক্ষেত্রের সাথে ঘনিষ্ঠভাবে সম্পর্কিত। এই সমস্যার সমাধান হাইপারগ্রাফের কাঠামোগত বৈশিষ্ট্য বোঝার জন্য গুরুত্বপূর্ণ।
  3. বিদ্যমান অগ্রগতি:
    • ব্রাউন, এরডোস এবং সোস প্রমাণ করেছেন যে f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t), যেখানে t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • যখন t=2t=2 (অর্থাৎ s=rk−2k+2s = rk-2k+2), সীমা π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k) এর অস্তিত্ব প্রমাণিত হয়েছে
    • k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\} এর জন্য, সীমার মান পরিচিত
  4. গবেষণার প্রেরণা: k=8k=8 হল পরবর্তী প্রাকৃতিক গবেষণা লক্ষ্য, এবং এই ক্ষেত্রটি নতুন জটিলতা প্রদর্শন করে, বিশেষ করে r=3r=3 এবং r≥4r\ge 4 এর সময় ভিন্ন আচরণ।

মূল অবদান

  1. প্রধান উপপাদ্য: সমস্ত r≥4r \geq 4 এর জন্য, π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r} নির্ধারণ করা হয়েছে
  2. নিম্ন সীমা ফলাফল: π(3,8)≥316\pi(3,8) \geq \frac{3}{16} প্রমাণ করা হয়েছে এবং এই নিম্ন সীমা কঠোর বলে অনুমান করা হয়েছে
  3. নির্মাণ পদ্ধতি: নিম্ন সীমা অর্জনকারী স্পষ্ট নির্মাণ প্রদান করা হয়েছে, যা প্রজেক্টিভ প্লেনের ঘটনা গ্রাফের উপর ভিত্তি করে
  4. কাঠামো বিশ্লেষণ: G8(r)G^{(r)}_8-মুক্ত হাইপারগ্রাফের কাঠামোর গভীর বিশ্লেষণ, বিশেষ করে ২-ক্লাস্টারের শ্রেণীবিভাগ
  5. প্রয়োগ: সাধারণীকৃত রামসে সংখ্যার সাথে সংযোগ স্থাপন করা হয়েছে, lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12} পাওয়া গেছে

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

কাজের সংজ্ঞা

k=8k=8 এর সময় ফাংশন f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) এর অ্যাসিম্পটোটিক আচরণ অধ্যয়ন করা, অর্থাৎ সীমা π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8) এর মান নির্ধারণ করা।

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

মৌলিক নির্মাণ ইউনিট

  • R-গ্রাফ: ৫ শীর্ষবিন্দু এবং ৩ প্রান্তের ৩-গ্রাফ সংজ্ঞায়িত করা হয়েছে, একটি প্রান্ত abcabc এবং একটি হীরা {buv,cuv}\{buv, cuv\} নিয়ে গঠিত
  • পথ পরিবার: ডেসার্গুয়েসিয়ান প্রজেক্টিভ প্লেন ব্যবহার করে ২-পথ পরিবার PP নির্মাণ করা হয়েছে, নির্দিষ্ট বিরলতা এবং সংযোগযোগ্যতা শর্ত সন্তুষ্ট করে

সম্ভাব্য মুছে ফেলার পদ্ধতি

  1. প্রজেক্টিভ প্লেনের ঘটনা গ্রাফ থেকে শুরু করে, দ্বিপক্ষীয় গ্রাফ G′G' নির্মাণ করা হয়েছে
  2. ২-পথ সম্ভাব্যতা (logm)/m1/2(log m)/m^{1/2} সহ নির্বাচন করা হয়েছে
  3. ঘন কনফিগারেশন গঠনকারী পথগুলি সরানোর জন্য সম্ভাব্য মুছে ফেলার পদ্ধতি ব্যবহার করা হয়েছে
  4. প্রতিটি ২-পথে RR-গ্রাফের অনুলিপি স্থাপন করা হয়েছে

মূল লেম্মা

লেম্মা ৩.২: যথেষ্ট বড় প্রাইম পাওয়ার qq এর জন্য, ২-পথ পরিবার PP বিদ্যমান যা সন্তুষ্ট করে:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • সংযোজন গ্রাফ ⋃P∈PP\bigcup_{P\in P} P এ O(m3/2)O(m^{3/2}) প্রান্ত রয়েছে
  • সংযোজন গ্রাফ ত্রিভুজ-মুক্ত, ৪-চক্র-মুক্ত এবং ৫-চক্র-মুক্ত
  • যেকোনো i∈[8]i \in [8] এর জন্য, প্রতিটি ii-উপসেটের শীর্ষবিন্দু সংখ্যা কমপক্ষে i+2i+2

উপরের সীমা প্রমাণ পদ্ধতি

একীকরণ কৌশল

  1. ১-একীকরণ: প্রান্ত সেটকে সংযুক্ত ১-ক্লাস্টারে (প্রকৃতপক্ষে গাছ) বিভক্ত করা হয়েছে
  2. २-একীকরণ: ২-ক্লাস্টার পেতে আরও একীকরণ করা হয়েছে, {1}∣{2}\{1\}|\{2\}-একীকরণযোগ্য শর্তের মাধ্যমে

কাঠামো বিশ্লেষণ

লেম্মা ৪.७: যেকোনো ∣F∣≥9|F| \geq 9 সহ २-ক্লাস্টার FF এর জন্য, FF নিম্নলিখিত পরিবারগুলির মধ্যে একটিতে অন্তর্গত:

  • AA: (5,2,2)(5,2,2) সমন্বয়ের ९-প্রান্ত २-ক্লাস্টার
  • BB: (1,2,4,2)(1,2,4,2) সমন্বয়ের ९-প্রান্ত २-ক্লাস্টার
  • C1,C2C_1, C_2: বিভিন্ন সমন্বয়ের २-ক্লাস্টার
  • E,FE, F: বিশেষ কাঠামোর २-ক্লাস্টার
  • SiS_i: १টি १-গাছ এবং ii টি হীরা নিয়ে গঠিত (2i+1)(2i+1)-প্রান্ত २-ক্লাস্টার

ওজন বরাদ্দ

r≥5r \geq 5 এবং r=4r = 4 এর জন্য বিভিন্ন ওজন ফাংশন ব্যবহার করা হয়েছে:

r≥5r \geq 5 এর সময়:

1 & \text{যদি } 1 \in C_F(uv) \\ 1/3 & \text{যদি } 2 \in C_F(uv) \text{ এবং } 1 \notin C_F(uv) \\ 0 & \text{অন্যথায়} \end{cases}$$ **$r = 4$ এর সময়**: ৫টি সহায়ক ফাংশন $h_i^F$ এর সর্বোচ্চ মান ওজন হিসাবে ব্যবহার করা হয়েছে। ## পরীক্ষামূলক সেটআপ এই পেপারটি বিশুদ্ধ তাত্ত্বিক গবেষণা, যা কোনো গণনামূলক পরীক্ষা জড়িত নয়। সমস্ত ফলাফল কঠোর গাণিতিক প্রমাণের মাধ্যমে প্রাপ্ত হয়েছে। ### প্রমাণ যাচাইকরণ - নিম্ন সীমা স্পষ্ট নির্মাণের মাধ্যমে যাচাই করা হয়েছে - উপরের সীমা বিস্তৃত কেস বিশ্লেষণ এবং ওজন বরাদ্দ পদ্ধতির মাধ্যমে প্রমাণিত হয়েছে - সমস্ত মূল লেম্মার সম্পূর্ণ গাণিতিক প্রমাণ রয়েছে ## পরীক্ষামূলক ফলাফল ### প্রধান ফলাফল **উপপাদ্য ১.१**: প্রতিটি $r \geq 4$ এর জন্য, $\pi(r,8) = \frac{1}{r^2-r}$ রয়েছে। **উপপাদ্য १.२**: $\pi(3,8) \geq \frac{3}{16}$। **অনুমান १.३**: $\pi(3,8) = \frac{3}{16}$। ### পরিচিত ফলাফলের সাথে তুলনা - $\pi(r,2) = \frac{1}{r^2-r}$ (রডল) - $\pi(r,4) = \frac{1}{r^2-r}$ (গ্লক ইত্যাদি) - $\pi(r,6) = \frac{1}{r^2-r}$ $r \geq 4$ এর জন্য (গ্লক ইত্যাদি) - $\pi(3,6) = \frac{61}{330}$ (বিশেষ ক্ষেত্র) ### নতুন আবিষ্কার 1. **থ্রেশহোল্ড ঘটনা**: $r=4$ হল সর্বনিম্ন সমরূপতা যার জন্য $\pi(r,8) = \frac{1}{r^2-r}$ সত্য 2. **কাঠামো জটিলতা**: $k=8$ এর ক্ষেত্রটি পূর্ববর্তী অধ্যয়নকৃত $k$ মানের তুলনায় আরও জটিল २-ক্লাস্টার কাঠামো প্রদর্শন করে 3. **রামসে সংযোগ**: সাধারণীকৃত রামসে সংখ্যার সাথে নতুন সংযোগ স্থাপিত হয়েছে ## সম্পর্কিত কাজ ### ঐতিহাসিক উন্নয়ন 1. **ব্রাউন-এরডোস-সোস (१९७३)**: মূল অনুমান এবং মৌলিক সীমা প্রস্তাব করেছেন 2. **রডল (१९८५)**: $k=2$ এর ক্ষেত্র সমাধান করেছেন 3. **গ্লক (२०१९)**: $k=3$ এর ক্ষেত্র সমাধান করেছেন 4. **ডেলকোর্ট-পোস্টেল (२०२४)**: সীমার অস্তিত্ব প্রমাণ করেছেন 5. **শাংগুয়ান (२०२३)**: সমস্ত সমরূপতায় সাধারণীকরণ করেছেন ### প্রযুক্তিগত উন্নয়ন - **দ্বন্দ্ব-অপ্রাসঙ্গিক ম্যাচিং তত্ত্ব**: ডেলকোর্ট-পোস্টেল এবং গ্লক ইত্যাদি দ্বারা উন্নত মূল প্রযুক্তি - **ওজন বরাদ্দ পদ্ধতি**: গ্লক ইত্যাদির কাজের ভিত্তিতে উন্নত উপরের সীমা প্রযুক্তি - **সম্ভাব্য নির্মাণ**: বীজগণিত জ্যামিতি কাঠামোর উপর ভিত্তি করে সম্ভাব্য পদ্ধতি ## উপসংহার এবং আলোচনা ### প্রধান উপসংহার 1. $r \geq 4$ এর সময় $\pi(r,8)$ এর মান সম্পূর্ণভাবে নির্ধারণ করা হয়েছে 2. $r=3$ এর ক্ষেত্রে সম্ভবত সর্বোত্তম সীমা প্রদান করা হয়েছে 3. সাধারণীকৃত রামসে সংখ্যার সাথে নতুন সংযোগ স্থাপিত হয়েছে ### সীমাবদ্ধতা 1. **$r=3$ এর ক্ষেত্র**: শুধুমাত্র নিম্ন সীমা পাওয়া গেছে, উপরের সীমা মিলান এখনও খোলা সমস্যা 2. **নির্মাণ জটিলতা**: নিম্ন সীমা নির্মাণ অত্যন্ত প্রযুক্তিগত, আরও সহজ নির্মাণ বিদ্যমান হতে পারে 3. **সাধারণীকরণ**: বড় $k$ মানের জন্য পদ্ধতির প্রযোজ্যতা অস্পষ্ট ### ভবিষ্যত দিকনির্দেশনা 1. $\pi(3,8) = \frac{3}{16}$ অনুমান প্রমাণ করা 2. $k \geq 9$ এর ক্ষেত্র অধ্যয়ন করা 3. আরও সাধারণ নির্মাণ এবং উপরের সীমা প্রযুক্তি খুঁজে বের করা 4. অন্যান্য চরম সমস্যার সাথে সংযোগ অন্বেষণ করা ## গভীর মূল্যায়ন ### শক্তি 1. **প্রযুক্তিগত উদ্ভাবন**: নতুন २-ক্লাস্টার শ্রেণীবিভাগ এবং ওজন বরাদ্দ প্রযুক্তি উন্নত করা হয়েছে 2. **পরিশীলিত নির্মাণ**: প্রজেক্টিভ প্লেনের উপর ভিত্তি করে নির্মাণ গভীর জ্যামিতিক অন্তর্দৃষ্টি প্রদর্শন করে 3. **সম্পূর্ণতা**: $r \geq 4$ এর জন্য সম্পূর্ণ সমাধান প্রদান করা হয়েছে 4. **স্পষ্ট লেখা**: প্রযুক্তিগত বিবরণ ভালভাবে সংগঠিত এবং বোঝা সহজ ### অপূর্ণতা 1. **$r=3$ অসম্পূর্ণ**: প্রধান খোলা সমস্যা এখনও সমাধান করা হয়নি 2. **পদ্ধতির বিশেষত্ব**: প্রযুক্তি $k=8$ এর জন্য অত্যন্ত লক্ষ্যবস্তু, সাধারণীকরণ সীমিত 3. **গণনামূলক জটিলতা**: কিছু প্রমাণ প্রক্রিয়া অত্যন্ত দীর্ঘ এবং প্রযুক্তিগত ### প্রভাব 1. **তাত্ত্বিক অবদান**: ব্রাউন-এরডোস-সোস সমস্যার গবেষণা এগিয়ে নিয়ে যায় 2. **পদ্ধতিবিদ্যা**: অনুরূপ সমস্যার জন্য নতুন প্রযুক্তিগত সরঞ্জাম প্রদান করে 3. **প্রয়োগ মূল্য**: রামসে তত্ত্বের সাথে সংযোগ নতুন গবেষণা দিকনির্দেশনা খোলে ### প্রযোজ্য পরিস্থিতি এই পদ্ধতি নিম্নলিখিত ক্ষেত্রে প্রযোজ্য: 1. হাইপারগ্রাফ চরম সমস্যার গবেষণা 2. নিষিদ্ধ উপগ্রাফের টুরান-ধরনের সমস্যা 3. সমন্বয়বিদ্যা অপ্টিমাইজেশনে কাঠামো বিশ্লেষণ 4. বীজগণিত সমন্বয়বিদ্যার প্রয়োগ ## সংদর্ভ পেপারটি এই ক্ষেত্রের মূল সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে: - ব্রাউন, এরডোস, সোসের মূল কাজ - ডেলকোর্ট-পোস্টেলের যুগান্তকারী ফলাফল - গ্লক ইত্যাদির সিরিজ কাজ - শাংগুয়ানের সাধারণীকরণ ফলাফল - বেনেট ইত্যাদির সাধারণীকৃত রামসে সংখ্যা সম্পর্কিত কাজ --- **সামগ্রিক মূল্যায়ন**: এটি তাত্ত্বিক সমন্বয়বিদ্যার একটি উচ্চ মানের পেপার, যা ব্রাউন-এরডোস-সোস সমস্যার গবেষণায় গুরুত্বপূর্ণ অগ্রগতি অর্জন করেছে। যদিও প্রধান খোলা সমস্যা ($r=3$ এর ক্ষেত্র) এখনও সম্পূর্ণভাবে সমাধান করা হয়নি, পেপারের প্রযুক্তিগত অবদান এবং পদ্ধতিগত উদ্ভাবন এই ক্ষেত্রের পরবর্তী গবেষণার জন্য একটি দৃঢ় ভিত্তি স্থাপন করে।