حدی برای شبکه‌ها، اکنون برای هر اندازه‌ای اثبات‌شده

چند نقطه بردارید و برخی جفت‌هایشان را با خط به هم وصل کنید. ریاضی‌دانان این را گراف (graph) می‌نامند: نقطه‌ها رأس‌های آن‌اند، خط‌ها یال‌هایش، و فاصله میان دو رأس کمترین تعداد یالی است که برای رفتن از یکی به دیگری لازم است. حالا دو قاعده بیفزایید. هر جفت رأس باید حداکثر در فاصلهٔ 2 باشد — مستقیماً وصل، یا از راه یک همسایهٔ مشترک. و هیچ یالی نباید زائد باشد: هر یک را که حذف کنید، جفتی بیش از دو گام از هم دور می‌شود. به چنین گرافی قطر-2-بحرانی (diameter-2-critical) می‌گویند. چند یال می‌تواند داشته باشد؟

سقف مانتل، و حدسی جسورانه‌تر

در 1907، مانتل (Mantel) اثبات کرد گرافی با n رأس و بدون مثلث — بدون سه رأسی که همه به هم وصل باشند — حداکثر ⌊n²/4⌋ یال دارد: مربع n تقسیم بر چهار، گردشده رو به پایین به یک عدد صحیح. تنها یک گراف به این سقف می‌رسد، گراف دوبخشی کامل متوازن (balanced complete bipartite graph): دو گروه با اندازه‌هایی تا حد ممکن برابر، هر رأس یکی به همهٔ رأس‌های دیگری وصل، و هیچ یالی درون یک گروه.

هر گراف بی‌مثلثی که نتواند بدون ساختن مثلث یک یال دیگر بپذیرد، قطر-2-بحرانی است. عکس آن درست نیست: برخی گراف‌های قطر-2-بحرانی مثلث دارند.

گرافی قطر-2-بحرانی با 7 رأس و 9 یال که مثلث v1v3v5 را در بر دارد. حذف v1v3 تنها مسیر دوگامی میان v2 و v3 را از بین می‌برد؛ حذف یالی بیرون از مثلث، دو سر آن را بی هیچ مسیر دوگامی رها می‌کند. — شکل 1، Das و Fox (2026)، arXiv:2610.39032.

حدس این بود که مثلث‌ها چیزی به دست نمی‌دهند: یک گراف قطر-2-بحرانی با n رأس همچنان حداکثر ⌊n²/4⌋ یال دارد و گراف دوبخشی کامل متوازن همچنان تنها گرافی است که به آن می‌رسد. قضیهٔ مانتل به‌عنوان حالتی خاص از آن نتیجه می‌شد. برای 7 رأس شکل، سقف 12 یال است.

برجی از 2ها

به گفتهٔ اردوش (Erdős)، آن‌طور که Zoltán Füredi نقل کرده، این پرسش به کارهای اوره (Ore) در دههٔ 1960 بازمی‌گردد. Ján Plesník کران یال‌ها را در 1975 به‌صورت یک حدس بیان کرد؛ مورتی (Murty) و سایمون (Simon) مستقلاً آن را پیشنهاد کردند و افزودند که گراف دوبخشی کامل متوازن تنها حالت حدی است — از همین رو حدس مورتی–سایمون. در دهه‌های 1970 و 1980، کران‌هایی به شکل c·n² آرام‌آرام پایین آمدند و c هر بار به 1/4 نزدیک‌تر شد.

در 1992، Füredi حدس را برای هر n به اندازهٔ کافی بزرگ با روش‌های منظم‌سازی (regularity methods) — ابزارهایی برگرفته از لم منظم‌سازی سمردی (Szemerédi) — اثبات کرد. بهای آن اندازهٔ آغازین بود: n باید دست‌کم برجی از 2ها با ارتفاع تقریباً 10¹⁴ می‌بود، یعنی 2 به توانِ 2 به توانِ 2…، که از بالا به پایین حساب می‌شود — هر 2 به توانِ همهٔ آنچه بالای آن است — با حدود 10¹⁴ عدد 2 در این پشته. زیر این اندازه، تنها خانواده‌های خاصی از گراف‌ها حل شده بودند.

یال‌ها در برابر یال‌های غایب

اثبات تازه، از Sanjana Das و Jacob Fox در دانشکدهٔ ریاضی دانشگاه استنفورد، برای هر n از 3 به بالا کار می‌کند. این اثبات از یک تطابق بیشینه (maximal matching) استفاده می‌کند: مجموعه‌ای از یال‌ها که هیچ دوتایشان رأس مشترک ندارند و نمی‌توان یال دیگری به آن افزود بی‌آنکه دو یال به هم برسند. یک تطابق روی n رأس حداکثر ⌊n/2⌋ یال دارد.

لم کلیدی: در یک گراف قطر-2-بحرانی، برای هر تطابق بیشینه، یال‌های بیرون از تطابق هرگز بیشتر از نایال‌ها (non-edges) — جفت رأس‌هایی که به هم وصل نیستند — نیستند. باقی‌اش حساب است. دو برابر تعداد یال‌ها حداکثر برابر تعداد جفت‌ها به‌علاوهٔ اندازهٔ تطابق است. با 10 رأس: 45 جفت به‌علاوهٔ حداکثر 5 یال تطابق می‌شود 50، پس حداکثر 25 یال. برای هر n، این مجموع دقیقاً دو برابر سقف مانتل می‌شود.

خود لم یک حساب‌وکتاب دقیق است. یک نایال بحرانی (critical) است اگر تنها یک مسیر دوگامی دو سرش را به هم وصل کند، مانند همهٔ دوازده نایال شکل 1. نویسندگان هر نایال بحرانی را به دو یال مسیرش می‌چسبانند و شبکهٔ حاصل را به تکه‌های همبند تقسیم می‌کنند. یک تکه حداکثر یک یال بیشتر از نایال‌های بحرانی‌اش دارد، و بهای هر تکه‌ای که این مازاد را دارد باید با یک نایال غیربحرانی پرداخت شود. نویسندگان برای یافتن آن‌ها از خروجی‌های جابه‌جایی (switch exits) استفاده می‌کنند: یک یال یا نایال بحرانی از تکه را بردارید و یکی از دو سرش را با جفت آن سر در تطابق عوض کنید. هر نایال غیربحرانی حداکثر دو بار مطالبه می‌شود، هر تکهٔ مازاددار دست‌کم دو مطالبه دارد، و حساب بسته می‌شود.

چه کسی چه یافت

نویسندگان در بیانیه‌ای کوتاه دربارهٔ هوش مصنوعی می‌نویسند: «این اثبات بیشتر به دست هوش مصنوعی یافته شد، به‌طور مشخص GPT-5.6 Sol در 11 اوت 2026.» مدل اثبات کاملی برای کران ⌊n²/4⌋ یافت که نویسندگان آن را ساده کردند. برای تعداد زوج رأس، مدل همچنین اثبات کرد که گراف دوبخشی کامل متوازن تنها حالت حدی است، با تکیه بر واقعیتی که سامنر (Sumner) دربارهٔ گراف‌هایی اثبات کرده بود که در آن‌ها هر تطابق بیشینه کامل (perfect) است، یعنی همهٔ رأس‌ها را می‌پوشاند.

با تعداد فرد رأس، هیچ تطابقی کامل نیست و در بسیاری از گراف‌ها هر تطابق بیشینه دقیقاً یک رأس را جا می‌اندازد: استدلال مدل قابل تطبیق نبود. نویسندگان اثبات دیگری برای حالت تساوی یافتند که برای هر n معتبر است و مقاله را خودشان نوشتند؛ بازبینی پایانی با GPT-6 Astra به «چند ویرایش جزئی» انجامید. این مقاله یک پیش‌چاپ است، هنوز داوری همتا نشده، و از هیچ نسخهٔ رایانه‌ای‌وارسی‌شده‌ای از استدلال نام نمی‌برد.

بازگشت به 1907

اگر گرافی با سقف برابر شود، نابرابری کلیدی برای هر تطابق بیشینه به تساوی بدل می‌شود. نویسندگان با انتخاب هوشمندانهٔ تطابق‌ها نشان می‌دهند چنین گرافی یا یک ستاره (star) است — یک رأس وصل به همهٔ رأس‌های دیگر، و هیچ چیز دیگر — یا اصلاً نایال بحرانی ندارد. در یک گراف قطر-2-بحرانی، هر یال یک مثلث روی یک مسیر بحرانی قرار دارد، پس نبودِ نایال بحرانی یعنی نبودِ مثلث؛ ستاره هم مثلثی ندارد. بنابراین گرافی که با سقف برابر شود بی‌مثلث است، و گام آخر همان قضیه‌ای است که حدس قصد تقویتش را داشت: نتیجهٔ مانتل در 1907، که گراف دوبخشی کامل متوازن را تنها بر سقف باقی می‌گذارد.