2025-11-12T20:34:10.839402

New small regular graphs of given girth: the cage problem and beyond

Exoo, Goedgebeur, Jooken et al.

The cage problem concerns finding $(k,g)$-graphs, which are $k$-regular graphs with girth $g$, of the smallest possible number of vertices. The central goal is to determine $n(k,g)$, the minimum order of such a graph, and to identify corresponding extremal graphs. In this paper, we study the cage problem and several of its variants from a computational perspective. Four complementary graph generation algorithms are developed based on exhaustive generation of lifts, a tabu search heuristic, a hill climbing heuristic and excision techniques. Using these methods, we establish new upper bounds for eleven cases of the classical cage problem: $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$ and $n(14,7) \leq 4716$. Notably, our results improve upon several of the best-known bounds, some of which have stood unchanged for 22 years. Moreover, the improvement for $n(4,10)$, from the longstanding upper bound of 384 down to 320, is surprising and constitutes a substantial improvement. While the main focus is on the cage problem, we also adapted our algorithms for variants of the cage problem that received attention in the literature. For these variants, additional improvements are obtained, further narrowing the gaps between known lower and upper bounds.

academic

প্রদত্ত পরিধি সহ নতুন ছোট নিয়মিত গ্রাফ: খাঁচা সমস্যা এবং তার বাইরে

মৌলিক তথ্য

পেপার আইডি: 2511.07247
শিরোনাম: New small regular graphs of given girth: the cage problem and beyond
লেখক: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
শ্রেণীবিভাগ: math.CO (সমন্বয়মূলক গণিত), cs.DM (বিচ্ছিন্ন গণিত)
প্রকাশনার সময়: ২০২৫ সালের ১১ নভেম্বর
পেপার লিঙ্ক: https://arxiv.org/abs/2511.07247

সারসংক্ষেপ

খাঁচা সমস্যা (cage problem) সর্বনিম্ন শীর্ষবিন্দু সংখ্যা সহ $(k,g)$ -গ্রাফ খুঁজে পাওয়ার সাথে সম্পর্কিত, যেখানে এটি $k$ -নিয়মিত গ্রাফ এবং পরিধি (girth) $g$ । মূল লক্ষ্য হল $n(k,g)$ (এই ধরনের গ্রাফের সর্বনিম্ন ক্রম) নির্ধারণ করা এবং সংশ্লিষ্ট চরম গ্রাফ চিহ্নিত করা। এই পেপারটি গণনামূলক দৃষ্টিকোণ থেকে খাঁচা সমস্যা এবং এর একাধিক রূপভেদ অধ্যয়ন করে, চারটি পরিপূরক গ্রাফ উৎপাদন অ্যালগরিদম বিকাশ করে: উত্তোলন (lifts) ভিত্তিক নিঃশেষ উৎপাদন, নিষিদ্ধ অনুসন্ধান অনুমানিক, পর্বতারোহণ অনুমানিক এবং ছেদন কৌশল। এই পদ্ধতিগুলি ব্যবহার করে, ক্লাসিক্যাল খাঁচা সমস্যার ১১টি ক্ষেত্রে নতুন উপরের সীমা প্রতিষ্ঠা করা হয়েছে: $n(3,16) \leq 936$ , $n(3,17) \leq 2048$ , $n(4,9) \leq 270$ , $n(4,10) \leq 320$ , $n(4,11) \leq 713$ , $n(5,9) \leq 1116$ , $n(6,11) \leq 7783$ , $n(8,7) \leq 774$ , $n(10,7) \leq 1608$ , $n(12,7) \leq 2890$ , $n(14,7) \leq 4716$ । এই ফলাফলগুলি ২২ বছর ধরে অপরিবর্তিত থাকা একাধিক সেরা পরিচিত সীমা উন্নত করে, বিশেষত $n(4,10)$ দীর্ঘমেয়াদী ৩৮৪ থেকে ৩২০-এ হ্রাস পেয়েছে, যা একটি উল্লেখযোগ্য উন্নতি গঠন করে।

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

সমস্যার সংজ্ঞা

১. মূল সমস্যা: খাঁচা সমস্যা $(k,g)$ -খাঁচা খুঁজে পায় (cage), যা সর্বনিম্ন শীর্ষবিন্দু সংখ্যা $n(k,g)$ সহ $k$ -নিয়মিত গ্রাফ এবং পরিধি $g$ । পরিধি হল গ্রাফে সবচেয়ে ছোট চক্রের দৈর্ঘ্য।

२. সমস্যার গুরুত্ব:

তাত্ত্বিক তাৎপর্য: খাঁচা হল চরম গ্রাফ তত্ত্বের কেন্দ্রীয় গবেষণা বিষয়, মূর সীমা (Moore bound) এর মতো ক্লাসিক্যাল তত্ত্বের সাথে ঘনিষ্ঠভাবে সম্পর্কিত
ব্যবহারিক প্রয়োগ: বিরল এবং উচ্চ মাত্রায় প্রতিসম কাঠামো যোগাযোগ নেটওয়ার্ক ডিজাইন, ত্রুটি সংশোধনকারী কোড, ক্রিপ্টোগ্রাফি ইত্যাদি ক্ষেত্রে প্রয়োগ মূল্য রাখে
নেটওয়ার্ক ডিজাইন: দক্ষ সমান তথ্য প্রচার সমর্থন করে এমন টোপোলজি প্রদান করে, কেন্দ্রীয় নোড অতিরিক্ত লোড এড়ায়, ব্যর্থতার প্রতি শক্তিশালী

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

অধিকাংশ পরামিতি জোড়ার জন্য $(k,g)$ , সঠিক মূল্য $n(k,g)$ অজানা
বিদ্যমান সীমা অনেক বছর ধরে উন্নত হয়নি (কিছু সীমা ২২ বছর অপরিবর্তিত)
মূর গ্রাফ শুধুমাত্র $g \in \{3,4,5,6,8,12\}$ এর জন্য সম্ভব
গণনামূলক জটিলতা $k$ এবং $g$ বৃদ্ধির সাথে তীব্রভাবে বৃদ্ধি পায়

४. গবেষণার প্রেরণা:

আধুনিক গণনামূলক ক্ষমতা এবং অপ্টিমাইজেশন অ্যালগরিদম ব্যবহার করে দীর্ঘমেয়াদী অপরিবর্তিত সীমা উন্নত করা
খাঁচা সমস্যা এবং এর রূপভেদ পরিচালনার জন্য সিস্টেমেটিক গণনামূলক পদ্ধতি বিকাশ করা
নির্দিষ্ট গ্রাফ উদাহরণ নির্মাণের মাধ্যমে তাত্ত্বিক গবেষণার জন্য প্রমাণ প্রদান করা (যেমন সমান পরিধি খাঁচার দ্বিপক্ষীয়তা অনুমান)

মূল অবদান

१. অ্যালগরিদম কাঠামো: চারটি পরিপূরক গ্রাফ উৎপাদন অ্যালগরিদম বিকাশ করা হয়েছে

বৈদ্যুতিক গ্রাফ উত্তোলন ভিত্তিক ব্যাকট্র্যাকিং অ্যালগরিদম (BTA)
নিষিদ্ধ অনুসন্ধান অনুমানিক (TS)
পর্বতারোহণ অনুমানিক
ছেদন কৌশল

२. ক্লাসিক্যাল খাঁচা সমস্যার অগ্রগতি: ১১টি নতুন উপরের সীমা প্রতিষ্ঠা করা হয়েছে, যার মধ্যে রয়েছে:

$n(4,10) \leq 320$ (৩৮৪ থেকে উল্লেখযোগ্যভাবে হ্রাস)
$n(3,16) \leq 936$ (৯৬০ থেকে উন্নত)
$n(3,17) \leq 2048$ (২১৭৬ থেকে উন্নত)
প্রথমবারের জন্য $n(4,11)$ এবং $n(6,11)$ এর জন্য অ-তুচ্ছ উপরের সীমা প্রদান করা

३. রূপভেদ সমস্যার অগ্রগতি:

প্রান্ত পরিধি নিয়মিত (egr) গ্রাফ: ২১টি নতুন সীমা (২টি কঠোর সীমা)
শীর্ষবিন্দু পরিধি নিয়মিত (vgr) গ্রাফ: ২৯টি নতুন সীমা (৭টি কঠোর সীমা)
$(k,g,g+1)$ -গ্রাফ: ৬টি নতুন সীমা
$(k,g)$ -বর্ণালী: ৩৪টি পূর্বে অমীমাংসিত ক্রম নির্ধারণ করা

४. গণনামূলক সম্পদ এবং পুনরুৎপাদনযোগ্যতা:

প্রায় ৫ বছরের CPU কাজ
সমস্ত কোড এবং ডেটা GitHub-এ প্রকাশ্য
সম্পূর্ণ যাচাইকরণ এবং সুস্থতা পরীক্ষা প্রদান করা

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

কাজের সংজ্ঞা

ইনপুট: নিয়মিত ডিগ্রি $k$ , পরিধি $g$ , ঐচ্ছিক অতিরিক্ত সীমাবদ্ধতা (যেমন শীর্ষবিন্দু/প্রান্ত পরিধি নিয়মিততা)

আউটপুট: শর্তসাপেক্ষ সর্বনিম্ন ক্রম গ্রাফ, বা উন্নত উপরের সীমা $n(k,g)$

সীমাবদ্ধতা: গ্রাফ অবশ্যই $k$ -নিয়মিত হতে হবে (প্রতিটি শীর্ষবিন্দুর ডিগ্রি $k$ ) এবং পরিধি কমপক্ষে $g$ হতে হবে (সবচেয়ে ছোট চক্র দৈর্ঘ্য $\geq g$ )

মূল কৌশল: বৈদ্যুতিক গ্রাফ উত্তোলন (Voltage Graph Lifts)

মৌলিক নীতি

প্রদত্ত ভিত্তি গ্রাফ $G=(V,E)$ , গ্রুপ $\Gamma$ এবং বৈদ্যুতিক বরাদ্দ $\alpha: A \rightarrow \Gamma$ ( $A$ হল নির্দেশিত প্রান্ত সেট), উত্তোলিত গ্রাফ $G_\alpha$ এর শীর্ষবিন্দু সেট হল: $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

প্রতিটি চাপ $(u,v) \in A$ এবং প্রতিটি $s \in \Gamma$ এর জন্য, একটি চাপ $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$ বিদ্যমান।

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

१. নিয়মিততা সংরক্ষণ (পর্যবেক্ষণ ১): $G$ হল $k$ -নিয়মিত যদি এবং শুধুমাত্র যদি $G_\alpha$ হল $k$ -নিয়মিত २. সংযোগযোগ্যতা প্রয়োজনীয় শর্ত (পর্যবেক্ষণ २): যদি $G$ সংযুক্ত না হয়, তাহলে $G_\alpha$ সংযুক্ত নয় ३. পরিধি গণনা (প্রস্তাব १): $G_\alpha$ এর পরিধি $G$ এর নির্দেশিত গ্রাফে সবচেয়ে ছোট বন্ধ অ-বিপরীত পথের দৈর্ঘ্যের সমান (নেট বৈদ্যুতিক $0_\Gamma$ ) ४. উৎপাদক গাছ সরলীকরণ (প্রস্তাব २): উৎপাদক গাছে সমস্ত বৈদ্যুতিক $0_\Gamma$ এ সেট করা যায় উত্তোলিত গ্রাফের সমরূপ শ্রেণী পরিবর্তন না করে

অ্যালগরিদম १: ব্যাকট্র্যাকিং অ্যালগরিদম (BTA)

কাঠামোগত বর্জন নিয়ম

কাঠামো ভিত্তিক বর্জন (বৈদ্যুতিক বরাদ্দ থেকে স্বাধীন): १. অর্ধ-প্রান্ত সীমাবদ্ধতা: অর্ধ-প্রান্তের সাথে সংশ্লিষ্ট চাপ শুধুমাত্র ক্রম २ এর গ্রুপ উপাদান বরাদ্দ করা যায় २. উৎপাদক গাছ অপ্টিমাইজেশন: উৎপাদক গাছ $T$ নির্বাচন করুন, এর প্রান্তের বৈদ্যুতিক $0_\Gamma$ এ সেট করুন ३. চক্র ভিত্তিক বর্জন: অ-গাছ প্রান্তের জন্য, যদি বৈদ্যুতিক বরাদ্দ $a$ দৈর্ঘ্য $(q+1)s$ এর চক্র তৈরি করে (যেখানে $a^s=0_\Gamma$ ) এবং লক্ষ্য পরিধির চেয়ে ছোট, তাহলে সেই বৈদ্যুতিক বর্জন করুন

বরাদ্দ ভিত্তিক বর্জন (আংশিক বৈদ্যুতিক বরাদ্দের উপর নির্ভরশীল): १. নিয়মিততা পরীক্ষা (অ্যালগরিদম १):

গ্রুপ স্বয়ংরূপতা $\phi_\Gamma$ এবং প্রান্ত স্বয়ংরূপতা $\phi_G$ ব্যবহার করুন
শুধুমাত্র অভিধানক্রমে সর্বনিম্ন প্রতিনিধি রাখুন
যদি আংশিক বরাদ্দ নিয়মিত না হয়, তাহলে এর সমস্ত সমাপ্তি বর্জন করা যায়

२. বৃদ্ধিমান পরিধি যাচাইকরণ (অ্যালগরিদম २):

শুধুমাত্র নতুন বরাদ্দ প্রান্ত ব্যবহার করে বন্ধ অ-বিপরীত পথ পরীক্ষা করুন
দক্ষতা উন্নত করতে বৃদ্ধিমান সম্পত্তি ব্যবহার করুন

অ্যালগরিদম প্রবাহ (অ্যালগরিদম ३)

BTA(G, Γ, g_min):
  १. কাঠামোগত পরীক্ষা সম্পাদন করুন, সম্ভাব্য বৈদ্যুতিক সেট N নির্ধারণ করুন
  २. পুনরাবৃত্তিমূলক বৈদ্যুতিক বরাদ্দ:
     - প্রতিটি দরকারী চাপ d এর জন্য, N(d) এ প্রতিটি বৈদ্যুতিক চেষ্টা করুন
     - পরিধি পরীক্ষা এবং নিয়মিততা পরীক্ষা প্রয়োগ করুন
     - যদি পাস হয়, পরবর্তী চাপ পরিচালনা করতে পুনরাবৃত্তি করুন
     - ব্যাকট্র্যাক করার সময় অবস্থা পুনরুদ্ধার করুন
  ३. সম্পূর্ণ বরাদ্দের পরে, উত্তোলিত গ্রাফ নির্মাণ এবং ফিল্টার করুন

অ্যালগরিদম २: নিষিদ্ধ অনুসন্ধান (TS)

প্রেরণা

বড় স্কেল উদাহরণের জন্য BTA গণনামূলক খরচ বেশি, TS আশাব্যঞ্জক বৈদ্যুতিক বরাদ্দ অন্বেষণ করতে অনুমানিক নমুনা করে।

মূল উপাদান

প্রতিবেশী সংজ্ঞা: ঠিক একটি প্রান্তের সাথে সংশ্লিষ্ট গ্রুপ উপাদান পরিবর্তন করে এমন সমস্ত বিকল্প বরাদ্দ

খরচ ফাংশন: १. পরিধি ভিত্তিক ( $c_{girth}$ ): $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{যদি } \text{Ord}(a) \neq 1 \\ C & \text{অন্যথায়} \end{cases}$ যেখানে $C$ হল বড় শাস্তি ধ্রুবক, $m$ হল নমুনা পথের সংখ্যা

२. নিয়মিততা ভিত্তিক ( $c_{reg}$ ): $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ যেখানে $f_V$ এবং $f_D$ যথাক্রমে শীর্ষবিন্দু এবং চাপ পরিধি চক্রে উপস্থিতির ফ্রিকোয়েন্সি

নিষিদ্ধ তালিকা: সাম্প্রতিক পরিবর্তন অপারেশন সংরক্ষণ করে, তাৎক্ষণিক রিটার্ন প্রতিরোধ করে, দৈর্ঘ্য $3|\Gamma|$

বিঘ্ন প্রক্রিয়া: স্থানীয় সর্বোত্তমে আটকে গেলে, র্যান্ডম পরিবর্তন প্রয়োগ করে বেরিয়ে আসুন

হাইপারপ্যারামিটার সেটিং (সারণী १)

প্রান্ত/গ্রুপ স্বয়ংরূপতা সংখ্যা সীমা: २००/२०००
BTA এবং TS সময় সীমা: প্রতিটি २० সেকেন্ড/উদাহরণ
প্রতিবেশী ন্যূনতম পরিধি: $g_{nbr} = g_{min} - 2$ (পরিধি সমস্যা) বা $g_{nbr} = g_{min}$ (নিয়মিততা সমস্যা)

অ্যালগরিদম ३: পর্বতারোহণ অনুমানিক

পূর্ববর্তী পদ্ধতির পার্থক্য: ভিত্তি গ্রাফ এবং বৈদ্যুতিক বরাদ্দ একসাথে অনুসন্ধান করুন

প্রবাহ: १. $n$ টি বিচ্ছিন্ন শীর্ষবিন্দু থেকে শুরু করুন २. প্রতিটি পুনরাবৃত্তিতে:

যোগ করা যায় এমন সমস্ত চাপ জোড়া এবং বৈদ্যুতিক বরাদ্দ $t \in T(G)$ বিবেচনা করুন
$|T(G_t)|$ সর্বাধিক করে এমন পরিবর্তন নির্বাচন করুন (লোভী কৌশল) ३. উত্তোলিত গ্রাফ রেকর্ড ভাঙে কিনা তা পরীক্ষা করুন

অ্যালগরিদম ४: ছেদন কৌশল

মৌলিক ধারণা: পরিচিত ছোট $(k,g+1)$ -গ্রাফ থেকে শীর্ষবিন্দু মুছুন, তারপর $k$ -নিয়মিত সম্পূর্ণ করতে প্রান্ত যোগ করুন

নির্দিষ্ট কৌশল: १. পরিধি ७, সমান ডিগ্রি $8 \leq k \leq 14$ :

$(k,8)$ -খাঁচা থেকে দূরত্ব ४ এর দুটি শীর্ষবিন্দু $u,v$ মুছুন
$N_1(u), N_1(v), N_2(u,v)$ মুছুন
ছেদন সেট আকার: $3k$ (de Ruiter এবং Biggs এর $3k-1$ থেকে উন্নত)

२. পরিধি११:

$(4,12)$ -খাঁচা থেকে: দূরত্ব ६ এর $u,v$ মুছুন, $N_1(u), N_1(v), N_3(u,v)$ এবং $N_2(u) \cap N_4(v)$ এ একটি শীর্ষবিন্দু মুছুন, $3k+3$ শীর্ষবিন্দু ছেদন করুন
$(6,12)$ -খাঁচা থেকে: অনুরূপ কৌশল, $5k-1$ শীর্ষবিন্দু ছেদন করুন

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

গণনামূলক সম্পদ

মোট গণনা: প্রায় ५ বছরের CPU
অবকাঠামো: Flemish Supercomputer Center (VSC)
বাস্তবায়ন ভাষা: C++ ভিত্তিক (অনুমান, স্পষ্টভাবে বলা হয়নি)

ভিত্তি গ্রাফ এবং গ্রুপ উৎপাদন

१. গ্রুপ: GAP সিস্টেম ব্যবহার করে সমস্ত ক্রম $n < 1024$ এর অ-সমরূপ গ্রুপ উৎপাদন করুন २. ভিত্তি গ্রাফ:

মাল্টিগ্রাফ জেনারেটর সম্প্রসারণ (multigraph+)
সমান্তরাল প্রান্ত, লুপ এবং অর্ধ-প্রান্ত সহ সংযুক্ত নিয়মিত গ্রাফ উৎপাদন করুন
Nauty ব্যবহার করে সমরূপ গ্রাফ সরান

যাচাইকরণ কৌশল

१. ইনপুট যাচাইকরণ:

গ্রুপ: সরাসরি GAP থেকে পান
ভিত্তি গ্রাফ: pregraph জেনারেটরের সাথে তুলনা করুন (ক্রম १३ পর্যন্ত)

२. অপ্টিমাইজেশন সঠিকতা:

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

३. নিঃশেষতা যাচাইকরণ:

তিনটি স্বাধীন বাস্তবায়নের সাথে তুলনা করুন:
- $K_{1,3}$ ভিত্তি নির্মাণ
- Gray এবং Theta গ্রাফ উত্তোলন
- ব্লক সাইক্লিক গ্রাফ জেনারেটর (চক্রীয় গ্রুপ উত্তোলনের সমতুল্য)
সমস্ত ক্ষেত্রে আউটপুট সম্পূর্ণভাবে সামঞ্জস্যপূর্ণ

ফিল্টার প্রক্রিয়া

१. সংযোগযোগ্যতা পরীক্ষা २. সমরূপতা ফিল্টারিং: Nauty ব্যবহার করে নিয়মিত প্রতিনিধিত্ব নির্মাণ করুন ३. পরিধি এবং নিয়মিততা যাচাইকরণ: २९ এ অ্যালগরিদম ব্যবহার করুন

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

প্রধান ফলাফল: ক্লাসিক্যাল খাঁচা সমস্যা (সারণী २)

উল্লেখযোগ্য উন্নতি

$(k,g)$	পুরানো সীমা	নতুন সীমা	উন্নতি	বছর
$(3,16)$	960	936	24	22 বছর
$(3,17)$	2176	2048	128	-
$(4,9)$	275	270	5	22 বছর
$(4,10)$	384	320	64	22 বছর
$(4,11)$	$n(4,12)-1$	713	প্রথম অ-তুচ্ছ সীমা	-
$(5,9)$	1152	1116	36	-
$(6,11)$	$n(6,12)-1$	7783	প্রথম অ-তুচ্ছ সীমা	-

ছেদন কৌশল ফলাফল

$(8,7) \leq 774$ (७७७ থেকে ३ শীর্ষবিন্দু উন্নত)
$(10,7) \leq 1608$ (१६११ থেকে ३ শীর্ষবিন্দু উন্নত)
$(12,7) \leq 2890$ (२८९३ থেকে ३ শীর্ষবিন্দু উন্নত)
$(14,7) \leq 4716$ (४७१९ থেকে ३ শীর্ষবিন্দু উন্নত)

মূল আবিষ্কার

१. $(4,10)$ এর অগ্রগতি: ३८४ থেকে ३२० এ হ্রাস, ১६.७% হ্রাস, সবচেয়ে আশ্চর্যজনক উন্নতি २. দ্বিপক্ষীয়তা প্রমাণ: নতুন $(3,16)$ এবং $(4,10)$ গ্রাফ উভয়ই দ্বিপক্ষীয়, "সমান পরিধি খাঁচা অবশ্যই দ্বিপক্ষীয়" অনুমান সমর্থন করে ३. নির্মাণ বিবরণ (চিত্র ४):

$(3,16)$ : গ্রুপ $C_{13} \rtimes C_9$ (ক্রম ११७) ব্যবহার করুন, ভিত্তি গ্রাফ ८ শীর্ষবিন্দু
$(4,10)$ : গ্রুপ $C_5 \times D_4$ (ক্রম ४०) ব্যবহার করুন, ভিত্তি গ্রাফ ८ শীর্ষবিন্দু

রূপভেদ সমস্যা ফলাফল

প্রান্ত পরিধি নিয়মিত গ্রাফ (সারণী ३)

२१টি নতুন সীমা, যার মধ্যে २টি কঠোর সীমা (উপরের এবং নিচের সীমা সমান):
- $n(4,5,4) = 30$ (নতুন নির্ধারিত)
- একাধিক $(6,5,\lambda_e)$ ক্ষেত্রে প্রথম উপরের সীমা

শীর্ষবিন্দু পরিধি নিয়মিত গ্রাফ (সারণী ४)

२९টি নতুন সীমা, যার মধ্যে ७টি কঠোর সীমা:
- $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
- $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
- একাধিক $(4,6,\lambda_v)$ ক্ষেত্রে উল্লেখযোগ্য উন্নতি

$(k,g)$ -বর্ণালী (সারণী ५)

३४টি পূর্বে অমীমাংসিত ক্রম নির্ধারণ করুন
প্রধানত কেন্দ্রীভূত:
- $(3,11)$ এবং $(3,12)$ : ७টি নতুন ক্রম
- $(4,7)$ এবং $(4,8)$ : १२টি নতুন ক্রম
- $(5,7)$ : २४টি নতুন ক্রম (१८४ থেকে २५६)

$(g+1)$ -চক্র ছাড়াই গ্রাফ (সারণী ६)

६টি নতুন সীমা:
- $n(3,11,12) \leq 228$ (२७२ থেকে উন্নত)
- $n(3,13,14) \leq 600$ (८०० থেকে উন্নত)
- $n(3,15,16) \leq 1760$ (२१६२ থেকে উন্নত)

অ্যালগরিদম দক্ষতা বিশ্লেষণ

সময় বরাদ্দ কৌশল

প্রতিটি ভিত্তি গ্রাফ-গ্রুপ সমন্বয়: BTA २० সেকেন্ড, TS २० সেকেন্ড
TS প্রাথমিক সমাধান অনুসন্ধান: २ সেকেন্ড
গ্রাফ স্বয়ংরূপতা অনুসন্ধান: २ সেকেন্ড

অ্যালগরিদম পরিপূরকতা

१. BTA: ছোট উদাহরণ সম্পূর্ণ নিঃশেষ, সম্পূর্ণতা নিশ্চিত করে २. TS: বড় উদাহরণ অনুমানিক নমুনা, স্কেলেবিলিটি ভাল ३. পর্বতারোহণ: ভিত্তি গ্রাফ এবং বরাদ্দ একসাথে অপ্টিমাইজ করুন, নমনীয়তা উচ্চ ४. ছেদন: পরিচিত বড় গ্রাফ ব্যবহার করুন, লক্ষ্যভিত্তিক শক্তিশালী

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

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

१. ক্লাসিক্যাল খাঁচা সমস্যা অগ্রগতি:

११টি নতুন উপরের সীমা, যার মধ্যে $(4,10)$ সবচেয়ে উল্লেখযোগ্য (३८४→३२०)
কিছু সীমা २२ বছর প্রথম উন্নতি
প্রথমবারের জন্য $(4,11)$ এবং $(6,11)$ এর জন্য অ-তুচ্ছ উপরের সীমা

२. রূপভেদ সমস্যা অগ্রগতি:

প্রান্ত/শীর্ষবিন্দু পরিধি নিয়মিত গ্রাফ: ५० নতুন সীমা (९টি কঠোর সীমা)
$(k,g)$ -বর্ণালী: ३४টি নতুন নির্ধারিত ক্রম
$(g+1)$ -চক্র ছাড়াই গ্রাফ: ६টি উন্নত সীমা

३. পদ্ধতিগত অবদান:

উত্তোলন ভিত্তিক সিস্টেমেটিক অ্যালগরিদম কাঠামো
কাঠামোগত এবং বরাদ্দ-ভিত্তিক বর্জন নিয়ম
অনুমানিক এবং নিঃশেষ পদ্ধতির কার্যকর সমন্বয়

সীমাবদ্ধতা

१. গণনামূলক জটিলতা:

বড় $(k,g)$ পরামিতি এখনও পরিচালনা করা কঠিন
বিশাল গণনামূলক সম্পদ প্রয়োজন (५ CPU বছর)
অনুমানিক পদ্ধতি সর্বোত্তম সমাধান খুঁজে পাওয়ার নিশ্চয়তা দেয় না

२. পদ্ধতি প্রয়োগযোগ্যতা সীমা:

উত্তোলন পদ্ধতি উপযুক্ত ভিত্তি গ্রাফ এবং গ্রুপ অস্তিত্বের উপর নির্ভর করে
ছেদন কৌশল পরিচিত বড় গ্রাফ প্রয়োজন
কিছু পরামিতি সমন্বয় উন্নতি পায়নি (যেমন $(3,9)$ , $(4,7)$ ইত্যাদি পরিচিত খাঁচা)

३. তাত্ত্বিক ফাঁক:

বেশিরভাগ ক্ষেত্রে নিচের এবং উপরের সীমার মধ্যে ব্যবধান এখনও বড়
নতুন নিচের সীমা উন্নতি প্রদান করা হয়নি
কিছু পরামিতির জন্য, উপরের সীমা এখনও "?" চিহ্নিত (অজানা)

४. হাইপারপ্যারামিটার সংবেদনশীলতা:

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

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

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

নতুন নির্মাণ থেকে অসীম পরিবার অনুমান করুন
মূর সীমা এবং এর রূপভেদ উন্নত করুন
সমান পরিধি খাঁচার দ্বিপক্ষীয়তা অনুমান প্রমাণ বা খণ্ডন করুন

२. অ্যালগরিদম উন্নতি:

আরও দক্ষ পরিধি গণনা অ্যালগরিদম বিকাশ করুন
মেশিন লার্নিং সহায়ক অনুমানিক ডিজাইন অন্বেষণ করুন
আধুনিক মাল্টি-কোর আর্কিটেকচার ব্যবহার করতে অ্যালগরিদম সমান্তরালকরণ করুন

३. ছেদন কৌশল সাধারণীকরণ:

ছেদন সেট নির্বাচন কৌশল সিস্টেমেটিক করুন
আরও বেশি $(k,g)$ পরামিতি জোড়ায় সাধারণীকরণ করুন
ছেদন পদ্ধতির কার্যকারিতা তাত্ত্বিক বিশ্লেষণ করুন

४. প্রয়োগ অন্বেষণ:

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

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

শক্তি

१. বড় অভিজ্ঞতামূলক অবদান:

२२ বছর ধরে অপরিবর্তিত একাধিক রেকর্ড ভাঙুন, বিশেষত $(4,10)$ এর বড় উন্নতি
বিভিন্ন নির্দিষ্ট নির্মাণ প্রদান করুন, তাত্ত্বিক গবেষণার জন্য উপাদান প্রদান করুন
কিছু পরামিতির জন্য প্রথমবারের জন্য অ-তুচ্ছ সীমা প্রদান করুন

२. পদ্ধতিগত উদ্ভাবন:

সিস্টেমেটিক বর্জন নিয়ম: কাঠামো-ভিত্তিক এবং বরাদ্দ-ভিত্তিক বর্জন অনুসন্ধান স্থান উল্লেখযোগ্যভাবে হ্রাস করে
অ্যালগরিদম পরিপূরকতা: BTA, TS, পর্বতারোহণ এবং ছেদন বিভিন্ন পরিস্থিতি কভার করে
বৃদ্ধিমান যাচাইকরণ: অ্যালগরিদম २ এর বৃদ্ধিমান পরিধি পরীক্ষা দক্ষতা উন্নত করে
নিয়মিততা পরীক্ষা: প্রতিসাম্য ব্যবহার করে অপ্রয়োজনীয় গণনা এড়ান

३. পরীক্ষামূলক ডিজাইন কঠোর:

বহু-স্তরীয় যাচাইকরণ কৌশল (ইনপুট, অপ্টিমাইজেশন, নিঃশেষতা)
তিনটি স্বাধীন বাস্তবায়নের সাথে তুলনা করুন
বিস্তারিত হাইপারপ্যারামিটার সেটিং ব্যাখ্যা
সম্পূর্ণ পুনরুৎপাদনযোগ্যতা সমর্থন

४. গবেষণা বিস্তৃতি:

শুধুমাত্র ক্লাসিক্যাল সমস্যা নয়, চারটি রূপভেদ সিস্টেমেটিক অধ্যয়ন করুন
একাধিক রূপভেদের জন্য প্রথম ব্যাচ উপরের সীমা প্রতিষ্ঠা করুন
বিভিন্ন সমস্যা একীভূত কাঠামো পরিচালনা করুন

५. খোলা বিজ্ঞান অনুশীলন:

কোড এবং ডেটা সম্পূর্ণ প্রকাশ্য (GitHub)
গ্রাফ House of Graphs ডাটাবেসে অন্তর্ভুক্ত
যাচাইযোগ্য শংসাপত্র প্রদান করুন (নির্মিত গ্রাফ)

অপূর্ণতা

१. সীমিত তাত্ত্বিক গভীরতা:

প্রধানত গণনামূলক/অভিজ্ঞতামূলক কাজ, গভীর তাত্ত্বিক অন্তর্দৃষ্টি অভাব
নতুন নিচের সীমা বা তাত্ত্বিক বিশ্লেষণ প্রদান করা হয়নি
কেন কিছু পরামিতি উল্লেখযোগ্য উন্নতি দেখায় তার তাত্ত্বিক ব্যাখ্যা অভাব

२. পদ্ধতি সম্পূর্ণতা:

অনুমানিক পদ্ধতি (TS, পর্বতারোহণ) সম্পূর্ণতা নিশ্চয়তা নেই
হাইপারপ্যারামিটার নির্বাচন অভিজ্ঞতা-নির্ভর, সিস্টেমেটিক গবেষণা অভাব
বিভিন্ন অ্যালগরিদমের তাত্ত্বিক গ্যারান্টি বা সংবেদনশীলতা বিশ্লেষণ অভাব

३. পরীক্ষামূলক রিপোর্ট বিবরণ:

বিভিন্ন অ্যালগরিদমের নির্দিষ্ট অবদান রিপোর্ট করা হয়নি
চালু সময়ের বিস্তারিত বিশ্লেষণ অভাব
ব্যর্থতার ক্ষেত্রে বা কঠিন উদাহরণের আলোচনা অভাব

४. স্কেলেবিলিটি সমস্যা:

বৃহত্তর $k$ এবং $g$ এর জন্য পদ্ধতির সম্ভাব্যতা অস্পষ্ট
পরামিতি বৃদ্ধির সাথে গণনামূলক সম্পদ প্রয়োজনের নিয়ম বিশ্লেষণ করা হয়নি
কিছু ফলাফল "≥१००" চিহ্নিত সম্পূর্ণ অন্বেষণ নির্দেশ করে

५. লেখার সংগঠন:

প্রযুক্তিগত বিবরণ ঘনীভূত, অ-বিশেষজ্ঞদের জন্য পাঠযোগ্যতা চ্যালেঞ্জ
কিছু অ্যালগরিদম বর্ণনা অসম্পূর্ণ (যেমন অ্যালগরিদম ४ সিউডোকোড অভাব)
ফলাফল সারণী অনেক কিন্তু একীভূত সারসংক্ষেপ বিশ্লেষণ অভাব

প্রভাব

१. একাডেমিক প্রভাব:

উচ্চ: খাঁচা সমস্যা ক্লাসিক্যাল চরম গ্রাফ তত্ত্ব সমস্যা, দীর্ঘমেয়াদী রেকর্ড ভাঙা গুরুত্বপূর্ণ
५७-মূর গ্রাফ ইত্যাদি বিখ্যাত খোলা সমস্যার জন্য পরোক্ষ গবেষণা পথ প্রদান করুন
পদ্ধতি অন্যান্য চরম গ্রাফ সমস্যায় সাধারণীকরণ করা যায়

२. ব্যবহারিক মূল্য:

মধ্যম: নতুন গ্রাফ নেটওয়ার্ক টোপোলজি ডিজাইন, ত্রুটি সংশোধনকারী কোডে ব্যবহার করা যায়
খোলা উৎস সরঞ্জাম অন্যান্য গবেষকদের জন্য ব্যবহারযোগ্য
অ্যালগরিদম কাঠামো সম্পর্কিত সমন্বয় অপ্টিমাইজেশন সমস্যায় প্রয়োগযোগ্য

३. পুনরুৎপাদনযোগ্যতা:

চমৎকার: সম্পূর্ণ কোড এবং ডেটা প্রকাশ্য
বিস্তারিত যাচাইকরণ কৌশল বিশ্বাসযোগ্যতা বৃদ্ধি করে
নির্দিষ্ট নির্মাণ স্বাধীনভাবে যাচাই করা যায়

४. অনুসরণ গবেষণা সম্ভাবনা:

নতুন নির্মাণ অসীম পরিবার আবিষ্কার অনুপ্রাণিত করতে পারে
অ্যালগরিদম কাঠামো অন্যান্য গ্রাফ উৎপাদন সমস্যায় প্রয়োগযোগ্য
রূপভেদ সমস্যার প্রথম ব্যাচ ফলাফল নতুন গবেষণা দিক খোলে

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

१. সরাসরি প্রয়োগ:

ছোট উচ্চ পরিধি নিয়মিত গ্রাফ প্রয়োজন এমন নেটওয়ার্ক ডিজাইন
LDPC কোড ইত্যাদি ত্রুটি সংশোধনকারী কোড নির্মাণ
মূল শেয়ারিং ইত্যাদি ক্রিপ্টোগ্রাফি প্রয়োগ

२. গবেষণা সরঞ্জাম:

চরম গ্রাফ তত্ত্বের গণনামূলক পরীক্ষা
গ্রাফ সমরূপতা এবং নিয়মিতকরণ অ্যালগরিদম পরীক্ষা
সমন্বয় অপ্টিমাইজেশন অনুমানিক বেঞ্চমার্ক পরীক্ষা

३. শিক্ষা সম্পদ:

বিশুদ্ধ গণিতে গণনামূলক পদ্ধতি প্রয়োগ প্রদর্শন করুন
অ্যালগরিদম ডিজাইন এবং অপ্টিমাইজেশন কেস স্টাডি
খোলা বিজ্ঞান এবং পুনরুৎপাদনযোগ্য গবেষণার উদাহরণ

४. প্রসারিত ক্ষেত্র:

অন্যান্য চরম গ্রাফ সমস্যা (Ramsey সংখ্যা, Turán সমস্যা ইত্যাদি)
সীমাবদ্ধতা সন্তুষ্টি সমস্যা
সমন্বয় ডিজাইন এবং কোডিং তত্ত্ব

রেফারেন্স (নির্বাচিত)

१. ভিত্তি তত্ত্ব:

४५ Sachs (१९६३): প্রমাণ করুন $(k,g)$ -গ্রাফ সমস্ত $k \geq 2, g \geq 3$ এর জন্য বিদ্যমান
३१ Gross & Tucker (१९८७): টোপোলজিক্যাল গ্রাফ তত্ত্ব এবং উত্তোলন তত্ত্ব
४७ Wong (१९८२): খাঁচা ব্যাপক সমীক্ষা

२. গণনামূলক পদ্ধতি:

२४ Exoo ইত্যাদি (२०११): $(3,11)$ এবং $(4,7)$ খাঁচার গণনামূলক নির্ধারণ
३८ McKay ইত্যাদি (१९९८): দ্রুত ব্যাকট্র্যাকিং নীতি
१५ de Ruiter & Biggs (२०१५): পূর্ণসংখ্যা প্রোগ্রামিং পদ্ধতি

३. সর্বশেষ অগ্রগতি:

२२ Exoo & Jajcay (२०११): বৈদ্যুতিক গ্রাফ উত্তোলনের পরিধি তত্ত্ব
२९ Goedgebeur & Jooken (२०२५): প্রান্ত পরিধি নিয়মিত গ্রাফের নিঃশেষ উৎপাদন
३४ Jajcay ইত্যাদি (२०२४): শীর্ষবিন্দু পরিধি নিয়মিত গ্রাফ

४. সরঞ্জাম:

३७ McKay & Piperno (२०१४): Nauty গ্রাফ সমরূপতা সফটওয়্যার
२७ GAP সিস্টেম: গ্রুপ তত্ত্ব গণনা
१२ House of Graphs: গ্রাফ ডাটাবেস

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