2025-11-23T15:40:17.357223

Lollipops, dense cycles and chords

DvoÅÃ¡k, Martins, ThomassÃ© et al.

In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\geq 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). In this work, we go further by showing that some of its edges can be contracted to obtain a graph with high minimum degree (we call such a minor of $C$ a \emph{cyclic minor}). We then investigate further cycles having cliques as cyclic minors, and show that minimum degree at least $O(k^2)$ guarantees a cyclic $K_k$-minor.

academic

ললিপপ, ঘন চক্র এবং জ্যা

মৌলিক তথ্য

পত্রিকা ID: 2502.04726
শিরোনাম: Lollipops, dense cycles and chords
লেখক: Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon
শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৩ তারিখ
পত্রিকা লিঙ্ক: https://arxiv.org/abs/2502.04726

সারসংক্ষেপ

১৯৮০ সালে, গুপ্তা, কান এবং রবার্টসন প্রমাণ করেছিলেন যে প্রতিটি গ্রাফ $G$ যার ন্যূনতম ডিগ্রি কমপক্ষে $k \geq 2$ একটি চক্র $C$ ধারণ করে যা কমপক্ষে $k+1$ টি শীর্ষবিন্দু সহ, প্রতিটি শীর্ষবিন্দু $C$ -তে কমপক্ষে $k$ টি প্রতিবেশী রয়েছে (তাই $C$ কমপক্ষে $\frac{(k+1)(k-2)}{2}$ টি জ্যা রয়েছে)। এই পত্রিকা আরও প্রমাণ করে যে নির্দিষ্ট প্রান্ত সংকোচনের মাধ্যমে উচ্চ ন্যূনতম ডিগ্রি সহ গ্রাফ পাওয়া যায় (যাকে চক্র মাইনর বলা হয়)। পরবর্তীতে দলীয় চক্র মাইনর সহ চক্র অধ্যয়ন করা হয়েছে এবং প্রমাণ করা হয়েছে যে ন্যূনতম ডিগ্রি কমপক্ষে $O(k^2)$ চক্র $K_k$ -মাইনরের অস্তিত্ব নিশ্চিত করে।

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

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

১. ক্লাসিক সমস্যার ধারাবাহিকতা: গ্রাফ তত্ত্বে একটি ক্লাসিক সমস্যা হল ন্যূনতম ডিগ্রি এবং গ্রাফের ঘন উপ-কাঠামোর মধ্যে সম্পর্ক অধ্যয়ন করা। অনেক উপপাদ্য দেখায় যে গ্রাফে যথেষ্ট উচ্চ ন্যূনতম ডিগ্রি কোনো ঘন, জটিল বা সুসংযুক্ত উপ-কাঠামোর অস্তিত্ব নিশ্চিত করে।

२. বিদ্যমান ফলাফলের সীমাবদ্ধতা: গুপ্তা-কান-রবার্টসন উপপাদ্য যদিও অনেক জ্যা সহ চক্রের অস্তিত্ব নিশ্চিত করে, তবে এই চক্রগুলির কাঠামোগত বৈশিষ্ট্য, বিশেষত প্রান্ত সংকোচন অপারেশনের মাধ্যমে কী ধরনের ঘন কাঠামো পাওয়া যায় তা আরও অধ্যয়ন করে না।

३. ললিপপ পদ্ধতির প্রয়োগ: ললিপপ পদ্ধতি থমাসন দ্বারা ১৯৭৮ সালে প্রথম প্রস্তাব করা হয়েছিল, প্রধানত হ্যামিলটোনীয় চক্রের অস্তিত্ব প্রমাণের জন্য ব্যবহৃত হয়েছিল, এই পত্রিকা এটিকে ঘন সংকোচিত চক্র নির্মাণের জন্য সাধারণীকরণ করে।

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

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

মূল অবদান

१. GKR উপপাদ্য সম্প্রসারণ: শুধুমাত্র ঘন চক্রের অস্তিত্ব প্রমাণ করা হয়নি, বরং সংকোচন অপারেশনের মাধ্যমে উচ্চ ন্যূনতম ডিগ্রি বা উচ্চ গড় ডিগ্রি সহ গ্রাফ পাওয়া যায় তাও প্রমাণ করা হয়েছে।

२. চক্র মাইনর ধারণা প্রবর্তন: চক্র মাইনরের ধারণা সংজ্ঞায়িত করা হয়েছে, অর্থাৎ গ্রাফের হ্যামিলটোনীয় উপ-গ্রাফ থেকে হ্যামিলটোনীয় চক্রের নির্দিষ্ট প্রান্ত সংকোচনের মাধ্যমে পাওয়া গ্রাফ।

३. ডিগ্রি এবং চক্র মাইনরের মধ্যে সম্পর্ক স্থাপন: প্রমাণ করা হয়েছে যে $f(\ell) = O(\ell^2)$ , যেখানে $f(\ell)$ হল $K_\ell$ কে চক্র মাইনর হিসাবে নিশ্চিত করার জন্য ন্যূনতম ডিগ্রির নিম্ন সীমা।

४. অ্যালগরিদম কাঠামো প্রদান: সংজ্ঞায়িত চক্র এবং সংশ্লিষ্ট প্রান্ত সংকোচন সেট নির্মাণের জন্য বহুপদী সময় অ্যালগরিদম প্রদান করা হয়েছে।

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

কাজের সংজ্ঞা

ন্যূনতম ডিগ্রি $k$ সহ গ্রাফ $G$ দেওয়া হলে, একটি চক্র $C$ এবং এর প্রান্ত উপসেট $X_1, X_2$ নির্মাণ করুন যাতে $X_i$ -তে প্রান্ত সংকোচনের মাধ্যমে উচ্চ ন্যূনতম ডিগ্রি বা উচ্চ গড় ডিগ্রি সহ গ্রাফ পাওয়া যায়।

মূল ধারণা

ললিপপ কাঠামো

সংজ্ঞা: গ্রাফ $G$ -তে ললিপপ $L$ হল একটি জোড় $(P,C)$ , যেখানে:

$P = p_1...p_s$ একটি পথ
$C = c_1...c_tc_1$ একটি চক্র
$p_s = c_1$ এবং $V(P) \cap V(C) = \{c_1\}$

সর্বোত্তমতা: ললিপপ $L = (P,C)$ সর্বোত্তম যখন এবং শুধুমাত্র যখন:

$L$ শীর্ষবিন্দু অন্তর্ভুক্তির অর্থে সর্বাধিক
$V(L)$ -তে সংজ্ঞায়িত সমস্ত ললিপপের মধ্যে, $L$ -এর চক্র দৈর্ঘ্য সর্বাধিক

সক্রিয় পথ ব্যবস্থা

সক্রিয় পথ সেট $S_1, S_2, ...$ নির্মাণ করা হয় পুনরাবৃত্তিমূলক সংজ্ঞা দ্বারা:

$S_1 = \{c_1c_2...c_t, c_1c_tc_{t-1}...c_2\}$
$i \geq 1$ -এর জন্য, $S_i$ থেকে $S_{i+1}$ নির্মাণ করুন: $Q = c_1...u \in S_i$ এবং জ্যা $uv$ -এর জন্য, যদি $vw$ হয় $C$ -এর একটি প্রান্ত ( $w$ হল $v$ -এর প্রতিবেশী $vQu$ -তে), তাহলে পথ $c_1QvuQw$ কে $S_{i+1}$ -তে যোগ করুন।

প্রধান উপপাদ্য

উপপাদ্য ১.१ (প্রধান ফলাফল)

যদি $G$ -এর ন্যূনতম ডিগ্রি কমপক্ষে $k \geq 2$ হয়, তাহলে $G$ একটি চক্র $C$ ধারণ করে যা সন্তুষ্ট করে: १. $C$ কমপক্ষে $k+1$ টি শীর্ষবিন্দু ধারণ করে, প্রতিটি $C$ -তে কমপক্ষে $k$ টি প্রতিবেশী রয়েছে २. $X_1, X_2 \subseteq E(C)$ বিদ্যমান যাতে:

$X_1$ -তে প্রান্ত সংকোচন করলে ন্যূনতম ডিগ্রি কমপক্ষে $\lceil\frac{k+2}{2}\rceil$ সহ গ্রাফ পাওয়া যায়
$X_2$ -তে প্রান্ত সংকোচন করলে গড় ডিগ্রি কমপক্ষে $\frac{2}{3}(k+1)$ সহ গ্রাফ পাওয়া যায়

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

१. সূক্ষ্ম বিশ্লেষণ: শুধুমাত্র জ্যার সংখ্যা গণনা করা হয় না, বরং জ্যার বিতরণ প্যাটার্ন বিশ্লেষণ করা হয়, কার্যকর প্রান্ত সংকোচনকে সমর্থন করার জন্য যথেষ্ট "ক্রস জ্যা" নিশ্চিত করতে।

२. সক্রিয় শীর্ষবিন্দু তত্ত্ব: সক্রিয় পথের ধারণার মাধ্যমে, উচ্চ ডিগ্রি সহ শীর্ষবিন্দু পদ্ধতিগতভাবে চিহ্নিত করা হয় এবং সংকোচন অপারেশনে তাদের আচরণ বিশ্লেষণ করা হয়।

३. মার্কাস-টার্ডস উপপাদ্যের প্রয়োগ: এই উপপাদ্য ব্যবহার করে উচ্চ গড় ডিগ্রি সহ চক্র মাইনরকে বড় সম্পূর্ণ দ্বিপক্ষীয় গ্রাফে আরও সংকুচিত করা হয়।

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

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

এই পত্রিকা প্রধানত তাত্ত্বিক কাজ, কঠোর গাণিতিক প্রমাণের মাধ্যমে ফলাফল যাচাই করা হয়:

१. ছোট স্কেল যাচাইকরণ:

$f(3) = 2$ , $f(4) = 3$ , $6 \leq f(5) \leq 8$
নির্দিষ্ট নির্মাণের মাধ্যমে ছোট দলের চক্র মাইনর অস্তিত্ব যাচাই করা হয়েছে

२. চরম উদাহরণ:

সম্পূর্ণ গ্রাফ $K_t$ কঠোরতা উদাহরণ হিসাবে, নির্দিষ্ট সিদ্ধান্ত সর্বোত্তম তা দেখায়
আইকোসাহেড্রন দেখায় $f(5) \geq 6$

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

বহুপদী সময় অ্যালগরিদম প্রদান করা হয়েছে:

প্রাথমিক ললিপপ খুঁজতে DFS: $O(n+m)$
ললিপপ উন্নত করার পুনরাবৃত্তি: সর্বাধিক $n^2$ বার কল
মোট জটিলতা: বহুপদী সময়

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

প্রধান ফলাফল

চক্র মাইনরের অস্তিত্ব

উপপাদ্য ३.२: প্রতিটি পূর্ণসংখ্যা $\ell$ -এর জন্য, একটি পূর্ণসংখ্যা $k$ বিদ্যমান যাতে ন্যূনতম ডিগ্রি কমপক্ষে $k$ সহ গ্রাফ $K'_{\ell,\ell}$ কে চক্র মাইনর হিসাবে ধারণ করে
লেম্মা ३.४: $f(k) = O(k^2)$ , অর্থাৎ $K_k$ চক্র মাইনর অস্তিত্বের জন্য $O(k^2)$ ন্যূনতম ডিগ্রি প্রয়োজন

নির্দিষ্ট সংখ্যাগত ফলাফল

$f(3) = 2$ : ন্যূনতম ডিগ্রি २ $K_3$ চক্র মাইনর নিশ্চিত করে
$f(4) = 3$ : ন্যূনতম ডিগ্রি ३ $K_4$ চক্র মাইনর নিশ্চিত করে
$f(5) \leq 8$ : ন্যূনতম ডিগ্রি ८ $K_5$ চক্র মাইনর নিশ্চিত করে

নির্মাণমূলক প্রমাণ

ললিপপ পদ্ধতির মাধ্যমে স্পষ্ট নির্মাণ প্রদান করা হয়েছে: १. সর্বোত্তম ললিপপ $(P,C)$ খুঁজুন २. সক্রিয় শীর্ষবিন্দু চিহ্নিত করুন (কমপক্ষে $k$ টি) ३. সংকোচন প্রান্ত সেট $X_1, X_2$ নির্মাণ করুন ४. সংকোচিত গ্রাফের ডিগ্রি বৈশিষ্ট্য যাচাই করুন

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

অ্যালগরিদমের সঠিকতা এবং বহুপদী সময় জটিলতা প্রমাণ করা হয়েছে:

প্রতিটি পুনরাবৃত্তি হয় একটি ভাল ললিপপ খুঁজে পায় বা প্রয়োজনীয় চক্র পায়
সর্বাধিক $n^2$ পুনরাবৃত্তি প্রয়োজন
প্রতিটি পুনরাবৃত্তি বহুপদী সময়ে সম্পন্ন করা যায়

१. উচ্চ ন্যূনতম ডিগ্রি শুধুমাত্র ঘন চক্রের অস্তিত্ব নিশ্চিত করে না, বরং সংকোচনের মাধ্যমে আরও ঘন কাঠামো পাওয়া যায় २. চক্র মাইনর ধারণা গ্রাফ কাঠামো অধ্যয়নের জন্য নতুন সরঞ্জাম প্রদান করে ३. $O(k^2)$ ডিগ্রি সীমা $K_k$ চক্র মাইনর পাওয়ার জন্য যথেষ্ট শর্ত

সীমাবদ্ধতা

१. দ্বিঘাত সীমার সর্বোত্তমতা: এটি স্পষ্ট নয় যে $f(k) = O(k^2)$ সর্বোত্তম, লেখক অনুমান করেন $O(k\sqrt{\log k})$ সীমা থাকতে পারে २. অ্যালগরিদম জটিলতা: যদিও বহুপদী সময়, তবে $O(n^2)$ পুনরাবৃত্তি ব্যবহারিক প্রয়োগে ধীর হতে পারে ३. বিশেষ কাঠামো সীমাবদ্ধতা: নির্দিষ্ট কাঠামো (যেমন দ্বিপক্ষীয় কনফিগারেশন) সম্ভাব্য চক্র মাইনর সীমাবদ্ধ করে

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

१. প্রশ্ন १.२: $f(\ell) = O(\ell\sqrt{\log \ell})$ কি? २. প্রশ্ন ४.१-४.२: সক্রিয় পথের সহজ নির্ধারণ মানদণ্ড সম্পর্কে ३. প্রশ্ন ४.३-४.४: ন্যূনতম ডিগ্রি ३ গ্রাফে চক্র জ্যা সংখ্যার রৈখিক সীমা

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

সুবিধা

१. তাত্ত্বিক গভীরতা: ক্লাসিক ফলাফল নতুন উচ্চতায় সাধারণীকরণ করা, মূল্যবান নতুন ধারণা প্রবর্তন করা २. প্রযুক্তিগত উদ্ভাবন: ললিপপ পদ্ধতির সূক্ষ্ম প্রয়োগ, সক্রিয় পথ তত্ত্বের প্রতিষ্ঠা ३. সম্পূর্ণতা: অস্তিত্ব প্রমাণ থেকে অ্যালগরিদম বাস্তবায়ন, ছোট স্কেল যাচাইকরণ থেকে অ্যাসিম্পটোটিক বিশ্লেষণ ४. লেখার স্পষ্টতা: ধারণা সংজ্ঞা স্পষ্ট, প্রমাণ কাঠামো যুক্তিসঙ্গত

অসুবিধা

१. ব্যবহারিক সীমিততা: প্রধানত তাত্ত্বিক ফলাফল, বাস্তব প্রয়োগ দৃশ্যকল্প যথেষ্ট স্পষ্ট নয় २. প্রযুক্তিগত জটিলতা: প্রমাণ কৌশল অত্যন্ত জটিল, ফলাফলের সাধারণীকরণ সীমাবদ্ধ করতে পারে ३. অনেক খোলা প্রশ্ন: একাধিক অমীমাংসিত সমস্যা উত্থাপন করা হয়েছে, তত্ত্ব এখনও নিখুঁত নয় তা নির্দেশ করে

প্রভাব

१. একাডেমিক মূল্য: গ্রাফ তত্ত্বে ডিগ্রি এবং কাঠামো সম্পর্ক গবেষণায় নতুন দৃষ্টিভঙ্গি প্রদান করে २. পদ্ধতিগত অবদান: চক্র মাইনর ধারণা অন্যান্য সমস্যায় প্রয়োগ থাকতে পারে ३. পরবর্তী গবেষণা: সম্পর্কিত সমস্যা গবেষণার জন্য ভিত্তি স্থাপন করে

প্রযোজ্য দৃশ্যকল্প

१. তাত্ত্বিক গ্রাফ তত্ত্ব গবেষণা: গ্রাফের ঘন উপ-কাঠামো অধ্যয়নের জন্য সরঞ্জাম প্রদান করে २. অ্যালগরিদম ডিজাইন: ঘন উপ-গ্রাফ খুঁজে পাওয়ার প্রয়োজনীয় অ্যালগরিদমে সম্ভাব্য প্রয়োগ ३. নেটওয়ার্ক বিশ্লেষণ: বড় নেটওয়ার্কের স্থানীয় ঘনত্ব বিশ্লেষণে সম্ভাব্য ব্যবহার

সংদর্ভ

এই পত্রিকা १८টি গুরুত্বপূর্ণ সংদর্ভ উদ্ধৃত করে, যার মধ্যে রয়েছে:

GKR80 গুপ্তা, কান, রবার্টসনের মূল কাজ
MT04 মার্কাস-টার্ডস উপপাদ্য
Tho78 থমাসনের ললিপপ পদ্ধতির যুগান্তকারী কাজ
TW05 থমাস-ওলান k-linked গ্রাফ সম্পর্কিত ফলাফল

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