2025-11-12T07:25:09.921673

Bipartite Turán number of paths and other trees

Bonamy, Leclere, Picavet
We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as a subgraph and of the number of vertices in each side of the bipartition. This was previously known only in the case where both sides of the bipartition have equal size and the longest path has size at most $5$. We also discuss possible generalizations replacing "path" with some specific types of trees.
academic

দ্বিপক্ষীয় পথ এবং অন্যান্য গাছের টুরান সংখ্যা

মৌলিক তথ্য

  • পত্রের আইডি: 2511.07374
  • শিরোনাম: দ্বিপক্ষীয় টুরান সংখ্যা পথ এবং অন্যান্য গাছের
  • লেখক: মার্থে বোনামি, থিওটাইম লেক্লার্ক, টিমোথে পিকাভেট
  • প্রতিষ্ঠান: CNRS, LaBRI, বোর্দো বিশ্ববিদ্যালয়; ENS প্যারিস-স্যাকলে
  • শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত), cs.DM (বিচ্ছিন্ন গণিত)
  • প্রকাশনার সময়: ২০২৫ সালের নভেম্বর ১১ তারিখ
  • পত্রের লিঙ্ক: https://arxiv.org/abs/2511.07374

সারসংক্ষেপ

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

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

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

১. ক্লাসিক্যাল টুরান সমস্যা: টুরান উপপাদ্য নির্ধারণ করে যে প্রদত্ত ক্রমের সম্পূর্ণ উপগ্রাফ ধারণ করে না এমন n শীর্ষবিন্দু গ্রাফের সর্বাধিক প্রান্ত সংখ্যা, যা নিষিদ্ধ উপগ্রাফ চরম সমস্যার পদ্ধতিগত অধ্যয়ন শুরু করেছে।

२. Erdős-Stone উপপাদ্যের সীমাবদ্ধতা: এই উপপাদ্য সমস্ত অ-দ্বিপক্ষীয় নিষিদ্ধ গ্রাফের টুরান সংখ্যা渐近ভাবে প্রদান করে, কিন্তু দ্বিপক্ষীয় গ্রাফের ক্ষেত্রে কোনো তথ্য প্রদান করে না।

३. দ্বিপক্ষীয় গ্রাফের বিশেষত্ব: দ্বিপক্ষীয় গ্রাফের টুরান সমস্যা এখনও খোলা থাকে, যা একাধিক মূল অনুমান তৈরি করেছে, সবচেয়ে বিখ্যাত হল Erdős-Sós অনুমান: k শীর্ষবিন্দুর গাছ বাদ দেওয়া n শীর্ষবিন্দু গ্রাফের সর্বাধিক (k-2)n/2 প্রান্ত রয়েছে।

४. সংযুক্ত দ্বিপক্ষীয় গ্রাফের গবেষণা: কারো, পাটকোস এবং টুজা CPT25 সম্প্রতি এমন ক্ষেত্রে মনোনিবেশ করেছেন যেখানে হোস্ট গ্রাফ দ্বিপক্ষীয় এবং সংযুক্ত উভয়ই, exb,c(a,b,H) চিহ্ন প্রবর্তন করেছেন যা a এবং b আকারের অংশ সহ, H কে উপগ্রাফ হিসাবে ধারণ করে না এমন সংযুক্ত দ্বিপক্ষীয় গ্রাফের সর্বাধিক প্রান্ত সংখ্যা প্রতিনিধিত্ব করে।

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

  • পরিচিত ফলাফলের সীমাবদ্ধতা: CPT25 শুধুমাত্র ৬ বা তার কম শীর্ষবিন্দু সহ সমস্ত গাছ, দ্বিতারকা এবং নির্দিষ্ট মাকড়সা গ্রাফের ক্ষেত্রে সমাধান করেছে, বিশেষত শুধুমাত্র exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1 জানা যায়
  • খোলা সমস্যা: যেকোনো পথ Pₖ এর জন্য exb,c(n,n,Pₖ) নির্ধারণ করা প্রয়োজন, কমপক্ষে渐近মান প্রদান করা
  • সাধারণীকরণের প্রয়োজন: নির্দিষ্ট গাছ পরিবারের exb,c মান অধ্যয়ন করা প্রয়োজন

মূল অবদান

१. পথ সমস্যার সম্পূর্ণ সমাধান: সমস্ত পথ Pₖ এর জন্য, exb,c(a,b,Pₖ) এর সঠিক মান প্রদান করা হয়েছে, শুধুমাত্র渐近মান নয়, বরং অসম দ্বিপক্ষীয় গ্রাফের জন্যও প্রযোজ্য (প্রধান উপপাদ্য 1.5)

२. ব্রুম গ্রাফে সম্প্রসারণ: ব্রুম গ্রাফ Sp,d* (পথের দৈর্ঘ্য p এবং d শাখা সহ তারকার সমন্বয়) এর জন্য, যখন তারকা পথের চেয়ে বড় হয় তখন সঠিক মান প্রদান করা হয়েছে (উপপাদ্য 1.6)

३. উপরের সীমা ফলাফল: যখন তারকা পথের আকারের সর্বাধিক অর্ধেক হয় তখন উপরের সীমা প্রদান করা হয়েছে (উপপাদ্য 1.7)

४. প্রযুক্তিগত উদ্ভাবন: সংযুক্ত দ্বিপক্ষীয় গ্রাফ পরিচালনার জন্য নতুন কৌশল বিকশিত করা হয়েছে, যার মধ্যে রয়েছে মূল শীর্ষবিন্দুর অস্তিত্ব লেম্মা এবং আবর্তক কাঠামো

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

কাজের সংজ্ঞা

সংজ্ঞা 1.1: নির্দিষ্ট পূর্ণসংখ্যা a, b এবং গ্রাফ H এর জন্য, exb,c(a,b,H) হল a এবং b আকারের অংশ সহ, H কে উপগ্রাফ হিসাবে ধারণ করে না এমন সংযুক্ত দ্বিপক্ষীয় গ্রাফের সর্বাধিক প্রান্ত সংখ্যা।

এই পত্রটি প্রধানত অধ্যয়ন করে:

  • ইনপুট: পথের দৈর্ঘ্য k, দ্বিপক্ষীয় বিভাজনের আকার a, b
  • আউটপুট: exb,c(a,b,Pₖ) এর সঠিক মান
  • সীমাবদ্ধতা: গ্রাফ অবশ্যই সংযুক্ত, দ্বিপক্ষীয় এবং Pₖ কে উপগ্রাফ হিসাবে ধারণ করে না

মূল উপপাদ্য

উপপাদ্য 1.5 (প্রধান ফলাফল): সমস্ত k ≥ 3 এবং b ≥ a ≥ k এর জন্য, exb,c(a,b,P2k)=exb,c(a,b,P2k−1)=(k−2)(b−1)+a\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a

এই সূত্রটি নির্দেশ করে:

  • বিজোড় এবং জোড় দৈর্ঘ্যের পথের একই টুরান সংখ্যা রয়েছে
  • প্রান্ত সংখ্যা বৃহত্তর অংশ b এর সাথে রৈখিকভাবে বৃদ্ধি পায়, সহগ (k-2)
  • একটি সংযোজনীয় সংশোধন পদ a বিদ্যমান

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

१. নিম্ন সীমা নির্মাণ (অংশ 2)

প্রস্তাব 2.1 নির্মাণমূলক প্রমাণ প্রদান করে:

একটি গ্রাফ G নির্মাণ করুন, যার দ্বিপক্ষীয় বিভাজন A = {u₁,...,uₐ} এবং B = {v₁,...,vᵦ}:

  • A তে প্রথম k-2 শীর্ষবিন্দু B তে সমস্ত শীর্ষবিন্দুর সাথে সম্পূর্ণভাবে সংযুক্ত (Kₖ₋₂,ᵦ গঠন করে)
  • A তে অবশিষ্ট a-(k-2) শীর্ষবিন্দু পাতা হিসাবে কাজ করে, সবই B তে একটি নির্দিষ্ট শীর্ষবিন্দুর সাথে সংযুক্ত

প্রান্ত সংখ্যা গণনা: ∣E(G)∣=b(k−2)+(a−(k−2))=(k−2)(b−1)+a|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a

P₂ₖ₋₁-মুক্ত সম্পত্তি প্রমাণ:

  • সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ Kₖ₋₂,ᵦ এর দীর্ঘতম পথে 2k-3 শীর্ষবিন্দু রয়েছে
  • যোগ করা পাতাগুলি পথকে প্রসারিত করতে পারে না, কারণ তারা সবই ডিগ্রি 1 এর শীর্ষবিন্দু

२. উপরের সীমা প্রমাণ (অংশ 3)

আবর্তক পদ্ধতি ব্যবহার করা হয়, মূল বিষয় তিনটি লেম্মা:

লেম্মা 3.2 (ছোট ডিগ্রি শীর্ষবিন্দুর অস্তিত্ব): বৃহত্তর অংশ B তে ডিগ্রি ≤ k-2 সহ এবং মুছে ফেলার পরে সংযুক্ত থাকে এমন একটি শীর্ষবিন্দু x বিদ্যমান।

প্রমাণের চিন্তাধারা:

  • B তে একটি পাতা b খুঁজে পেতে DFS গাছ ব্যবহার করুন
  • যদি d(b) ≤ k-2 হয়, x = b নিন
  • যদি d(b) = k-1 হয়, তাহলে পথের দৈর্ঘ্য অবশ্যই 2k-2 হবে, একটি চক্র গঠন করবে
  • এই সময়ে, অন্য একটি ডিগ্রি ≤ k-2 সহ শীর্ষবিন্দু b' খুঁজে পাওয়া যায়

লেম্মা 3.3 (ভারসাম্যপূর্ণ গ্রাফের মুছে ফেলার যোগ্য শীর্ষবিন্দু জোড়া): ভারসাম্যপূর্ণ দ্বিপক্ষীয় গ্রাফের জন্য, দুটি শীর্ষবিন্দু x, y বিদ্যমান যাতে d(x) + d(y) ≤ k-1 এবং মুছে ফেলার পরে সংযুক্ত এবং ভারসাম্যপূর্ণ থাকে।

প্রমাণ দীর্ঘতম পথ P এর শেষ বিন্দুর বিশ্লেষণ ব্যবহার করে:

  • যদি শেষ বিন্দুগুলি বিভিন্ন অংশে থাকে, সরাসরি ব্যবহার করা যেতে পারে
  • অন্যথায়, উপযুক্ত পাতার জোড়া খুঁজে পেতে DFS গাছ ব্যবহার করুন

লেম্মা 3.4 (ভিত্তি ক্ষেত্র): যখন a = b = k হয়, |E(G)| ≤ (k-1)² + 1।

প্রমাণ আবর্তক পদ্ধতি ব্যবহার করে, মূল পর্যবেক্ষণ:

  • অ-কাটা বিন্দুর ন্যূনতম ডিগ্রি শীর্ষবিন্দু x খুঁজুন
  • x মুছে ফেলার পরে অবশিষ্ট গ্রাফ বিশ্লেষণ করুন
  • P₂ₖ-মুক্ত সম্পত্তি ব্যবহার করে ডিগ্রি এবং কাঠামো সীমাবদ্ধ করুন

প্রধান উপপাদ্য প্রমাণ:

  • যদি b > a: লেম্মা 3.2 ব্যবহার করে একটি শীর্ষবিন্দু মুছুন, আবর্তন করুন
  • যদি a = b > k: লেম্মা 3.3 ব্যবহার করে দুটি শীর্ষবিন্দু মুছুন, আবর্তন করুন
  • যদি a = b = k: লেম্মা 3.4 ব্যবহার করুন

ব্রুম গ্রাফের ফলাফল

উপপাদ্য 1.6: k, d ≥ 2 এর জন্য, যখন n ≥ d²/2 এবং d > 2k হয়, exb,c(n,n,S2k,d)=exb,c(n,n,S2k+1,d)=nd\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd

মূল প্রযুক্তিগত লেম্মা:

লেম্মা 4.1: যদি গ্রাফে এমন একটি শীর্ষবিন্দু থাকে যা 2k দৈর্ঘ্যের পথের শেষ বিন্দু নয়, তাহলে |E(G)| ≤ (k-1)(b+a)

লেম্মা 4.2: যদি |E(G)| ≥ k(b+a)+1 হয়, তাহলে প্রতিটি শীর্ষবিন্দুর ডিগ্রি সর্বাধিক k+d-1

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

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

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

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

প্রধান ফলাফল যাচাইকরণ

পথের সঠিক সূত্র:

  • P₅ এবং P₆ এর জন্য: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
    • সূত্র ব্যবহার করে: k=3 সময়, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
  • সাধারণ Pₖ এর জন্য: সূত্রটি অসম দ্বিপক্ষীয় গ্রাফ সহ সমস্ত ক্ষেত্রের সঠিক মান প্রদান করে

ব্রুম গ্রাফ ফলাফল:

  • যখন তারকা অংশ প্রভাবশালী হয় (d > 2k) তখন, টুরান সংখ্যা nd
  • এটি সর্বাধিক ডিগ্রি সীমাবদ্ধতার সাথে সামঞ্জস্যপূর্ণ

পরিচিত ফলাফলের সাথে তুলনা

१. প্রস্তাব 1.2 এর সাধারণীকরণ: এই পত্রের ফলাফল সম্পূর্ণভাবে CPT25 থেকে exb,c(n,n,P₅) = 2n-1 অন্তর্ভুক্ত এবং সাধারণীকরণ করে

२. সাধারণতার উন্নতি:

  • ভারসাম্যপূর্ণ গ্রাফ থেকে অসম গ্রাফে সম্প্রসারণ
  • নির্দিষ্ট ছোট পথ থেকে যেকোনো পথে সম্প্রসারণ -渐近ফলাফল থেকে সঠিক সূত্রে সম্প্রসারণ

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

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

१. টুরান উপপাদ্য Tur45: সম্পূর্ণ গ্রাফের চরম সমস্যা २. Erdős-Stone উপপাদ্য ES46: অ-দ্বিপক্ষীয় গ্রাফের渐近টুরান সংখ্যা ३. Gallai-Erdős GE59: নির্দিষ্ট আকারের পথ বাদ দেওয়া সংযুক্ত গ্রাফের渐近ফলাফল ४. Gyárfás-Rousseau-Schelp GRS84: নির্দিষ্ট আকারের পথ বাদ দেওয়া দ্বিপক্ষীয় গ্রাফের সঠিক টুরান সংখ্যা

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

Caro-Patkós-Tuza CPT25:

  • exb,c চিহ্ন প্রবর্তন করেছেন
  • ছোট গাছের ক্ষেত্রে সমাধান করেছেন (≤6 শীর্ষবিন্দু)
  • দ্বিতারকা এবং নির্দিষ্ট মাকড়সা গ্রাফ সমাধান করেছেন
  • এই পত্রে সমাধানকৃত সমস্যা প্রস্তাব করেছেন

স্বাধীন কাজ

He-Salia-Zhu HSZ25: লেখক উল্লেখ করেছেন যে একই দিনে অনুরূপ অগ্রগতির স্বাধীন কাজ জমা দেওয়া হয়েছিল

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

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

१. প্রশ্ন 1.3 এর সম্পূর্ণ উত্তর: সমস্ত পথ Pₖ এর জন্য exb,c(n,n,Pₖ) এর সঠিক মান প্রদান করা হয়েছে, প্রশ্নের দ্বারা প্রয়োজনীয়渐近মান অতিক্রম করে

२. প্রশ্ন 1.4 এর আংশিক উত্তর: ব্রুম গ্রাফ পরিবারের জন্য, নির্দিষ্ট পরামিতি পরিসরে সঠিক মান বা উপরের সীমা প্রদান করা হয়েছে

३. পদ্ধতিগত অবদান: সংযুক্ত দ্বিপক্ষীয় গ্রাফ চরম সমস্যা পরিচালনার জন্য নতুন প্রযুক্তিগত কাঠামো বিকশিত করা হয়েছে

সীমাবদ্ধতা

१. ব্রুম গ্রাফের সীমাবদ্ধতা:

  • উপপাদ্য 1.6 এর জন্য d > 2k এবং n ≥ d²/2 প্রয়োজন
  • উপপাদ্য 1.7 শুধুমাত্র উপরের সীমা প্রদান করে, সঠিক মান নয়
  • মধ্যবর্তী ক্ষেত্র (d ≈ k) সম্পূর্ণভাবে সমাধান করা হয়নি

२. গাছের সাধারণ ক্ষেত্র: শুধুমাত্র পথ এবং ব্রুম গ্রাফ পরিচালনা করা হয়েছে, আরও সাধারণ গাছ পরিবার এখনও খোলা

३. প্রযুক্তিগত সীমাবদ্ধতা: কিছু প্রমাণ পদক্ষেপ নির্দিষ্ট কাঠামোগত সম্পত্তির উপর নির্ভর করে, যা আরও জটিল নিষিদ্ধ উপগ্রাফে সাধারণীকরণ করা কঠিন হতে পারে

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

१. ব্রুম গ্রাফ ফলাফল উন্নত করা: সমস্ত পরামিতি পরিসরের সঠিক মান নির্ধারণ করা

२. অন্যান্য গাছ পরিবারে সম্প্রসারণ:

  • মাকড়সা গ্রাফের সম্পূর্ণ বর্ণনা
  • অন্যান্য বিশেষ গাছ কাঠামো

३. অসম ক্ষেত্রের গভীর গবেষণা: যদিও এই পত্রটি a ≠ b এর ক্ষেত্রে পরিচালনা করে, আরও সূক্ষ্ম ফলাফল থাকতে পারে

४. গণনামূলক জটিলতা: প্রদত্ত গ্রাফ টুরান সীমা অর্জন করে কিনা তা নির্ধারণের অ্যালগরিদমিক সমস্যা অধ্যয়ন করা

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

সুবিধা

१. খোলা সমস্যার সম্পূর্ণ সমাধান:

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

२. প্রমাণ প্রযুক্তি মার্জিত:

  • নিম্ন সীমা নির্মাণ সহজ এবং স্পষ্ট
  • উপরের সীমা প্রমাণের আবর্তক কাঠামো পরিষ্কার
  • মূল লেম্মা (3.2, 3.3, 3.4) এর বিবৃতি এবং প্রমাণ সংক্ষিপ্ত

३. ফলাফলের সম্পূর্ণতা:

  • পথের জন্য, সমস্ত পরামিতির সঠিক সূত্র প্রদান করা হয়েছে
  • সূত্র রূপ সহজ: (k-2)(b-1)+a
  • বিজোড় এবং জোড় দৈর্ঘ্যের পথ একীভূতভাবে পরিচালনা করা হয়েছে

४. লেখার গুণমান:

  • পত্রের কাঠামো পরিষ্কার, যুক্তি কঠোর
  • মূল পদক্ষেপগুলি বিস্তারিত উপ-প্রস্তাব দ্বারা সমর্থিত
  • চিত্র (যেমন চিত্র 1) নির্মাণ বোঝার সাহায্য করে

५. প্রযুক্তিগত উদ্ভাবন:

  • লেম্মা 3.2 ছোট ডিগ্রি অ-কাটা বিন্দুর অস্তিত্ব সম্পর্কে মূল অন্তর্দৃষ্টি
  • ভারসাম্যপূর্ণ গ্রাফে মুছে ফেলার যোগ্য শীর্ষবিন্দু জোড়ার বর্ণনা (লেম্মা 3.3) স্বাধীন মূল্য রাখে
  • DFS গাছের ব্যবহার প্রমাণ জুড়ে বিস্তৃত, ক্লাসিক্যাল সরঞ্জামের কার্যকর প্রয়োগ প্রদর্শন করে

অপূর্ণতা

१. ব্রুম গ্রাফ ফলাফল অসম্পূর্ণ:

  • উপপাদ্য 1.6 এবং 1.7 এর মধ্যে পরামিতি ফাঁক বিদ্যমান
  • উপপাদ্য 1.7 শুধুমাত্র উপরের সীমা 2nk+1 প্রদান করে, সম্ভাব্য সঠিক মানের সাথে ব্যবধান অজানা
  • শর্ত n ≥ d²/2 প্রযুক্তিগতভাবে শক্তিশালী মনে হয়, সম্ভবত সর্বোত্তম নয়

२. ভিত্তি ক্ষেত্র প্রমাণ জটিল:

  • লেম্মা 3.4 (a=b=k এর ক্ষেত্র) এর প্রমাণ উল্লেখযোগ্য স্থান দখল করে
  • একাধিক উপ-প্রস্তাব (দাবি 3.11-3.13) প্রয়োজন
  • আরও সরাসরি যুক্তি থাকতে পারে

३. সাধারণীকরণ সীমিত:

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

४. স্বাধীন কাজের সাথে সম্পর্ক:

  • HSZ25 এর স্বাধীন কাজ উল্লেখ করা হয়েছে কিন্তু বিস্তারিত তুলনা করা হয়নি
  • দুটি পত্রের প্রযুক্তিগত পদ্ধতি একই কিনা তা স্পষ্ট নয়

প্রভাব

१. তাত্ত্বিক অবদান:

  • একটি স্পষ্টভাবে উত্থাপিত খোলা সমস্যা সম্পূর্ণভাবে সমাধান করে
  • সংযুক্ত দ্বিপক্ষীয় টুরান সমস্যার জন্য নতুন প্রযুক্তিগত সরঞ্জাম প্রদান করে
  • ফলাফলের নির্ভুলতা এটিকে এই ক্ষেত্রের মানদণ্ড করে তোলে

२. পদ্ধতিগত মূল্য:

  • আবর্তক কাঠামো অন্যান্য নিষিদ্ধ উপগ্রাফ সমস্যায় প্রযোজ্য হতে পারে
  • মূল লেম্মা অন্যান্য প্রসঙ্গে উপযোগী হতে পারে

३. পরবর্তী গবেষণা:

  • স্বাভাবিকভাবে ব্রুম গ্রাফের সম্পূর্ণ বর্ণনার প্রশ্ন উত্থাপন করে
  • অন্যান্য গাছ পরিবারের exb,c মান অধ্যয়ন করতে অনুপ্রাণিত করে
  • অ-সংযুক্ত ক্ষেত্রের গবেষণা অনুপ্রাণিত করতে পারে

४. যাচাইযোগ্যতা:

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

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

१. তাত্ত্বিক গবেষণা:

  • চরম গ্রাফ তত্ত্ব গবেষক দের জন্য রেফারেন্স ফলাফল
  • টুরান ধরনের সমস্যার প্রযুক্তিগত উৎস
  • সংযোগ সীমাবদ্ধতার অধীনে চরম সমস্যার কেস স্টাডি

२. সম্পর্কিত সমস্যা:

  • Erdős-Sós অনুমানের গবেষণায় অনুপ্রেরণা দিতে পারে
  • অন্যান্য গাছের টুরান সংখ্যার জন্য তুলনা প্রদান করে
  • সংযুক্ত দ্বিপক্ষীয় গ্রাফের কাঠামোগত সম্পত্তি গবেষণা

३. শিক্ষামূলক মূল্য:

  • চরম সমন্বয়ে আবর্তক পদ্ধতির প্রয়োগ প্রদর্শন করে
  • DFS গাছ এবং পথ বিশ্লেষণের উদাহরণ
  • উপরের এবং নিম্ন সীমা মিলানোর সম্পূর্ণ কেস

রেফারেন্স (মূল সাহিত্য)

१. CPT25 Caro, Patkós, Tuza: দ্বিপক্ষীয় টুরান সংখ্যা গাছের - এই পত্রে সমাধানকৃত সমস্যা প্রস্তাব করেছেন

२. Tur45 Turán: গ্রাফ তত্ত্বে একটি চরম সমস্যা সম্পর্কে - টুরান সমস্যার ভিত্তি স্থাপন করেছেন

३. ES46 Erdős, Stone: রৈখিক গ্রাফের কাঠামো সম্পর্কে - Erdős-Stone উপপাদ্য

४. GRS84 Gyárfás, Rousseau, Schelp: দ্বিপক্ষীয় গ্রাফে পথের জন্য একটি চরম সমস্যা - দ্বিপক্ষীয় গ্রাফে পথের নির্ভুল টুরান সংখ্যা (সংযোগ প্রয়োজন ছাড়াই)

५. HSZ25 He, Salia, Zhu: দীর্ঘ চক্র এবং পথের জন্য সংযুক্ত দ্বিপক্ষীয় টুরান সমস্যা - স্বাধীন সম্পর্কিত কাজ

সামগ্রিক মূল্যায়ন

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