اثبات یک هوش مصنوعی، از نو کشیده برای انسان‌ها
چند نقطه بکشید و برخی را با خط به هم وصل کنید. ریاضی‌دانان به این گراف می‌گویند؛ نقطه‌ها رأس‌اند، خط‌ها یال، و شمار خط‌هایی که به یک نقطه می‌رسند درجهٔ آن است. درخت گرافی بی‌حلقه است که یکپارچه به هم پیوسته است، مانند شاخه‌ای شاخه‌شاخه؛ درختی با t نقطه همیشه t − 1 خط دارد.
در اوایل دههٔ 1960، پال اردوش و ورا ت. شوش پرسشی ساده مطرح کردند: چند خط گرافی را وادار می‌کند که هر درختی با اندازه‌ای معین را در خود داشته باشد؟ پاسخ آن‌ها، حدس اردوش–شوش، این است:
اگر میانگین درجهٔ یک گراف بیشتر از t − 2 باشد، آن گراف هر درخت با t رأس را در خود دارد.
این آستانه دقیق است. نسخه‌های جدایی از گراف کامل با t − 1 نقطه بردارید که در آن هر جفت به هم وصل است: هر نقطه دقیقاً t − 2 همسایه دارد، اما هیچ تکه‌ای به قدر کافی بزرگ نیست که درختی با t نقطه را جای دهد. دشواری در واژهٔ میانگین است. اگر تک‌تک نقطه‌ها دست‌کم t − 1 همسایه داشتند، می‌شد درخت را شاخه به شاخه بی‌دردسر جا داد. اما میانگین چیزی دربارهٔ هیچ نقطهٔ منفردی نمی‌گوید: برخی ممکن است صدها همسایه داشته باشند و برخی تقریباً هیچ.
شصت سال پاسخ‌های جزئی
بر پایهٔ تاریخچه‌ای که مقاله روایت می‌کند، این مسئله به 1962–1964 بازمی‌گردد و در کانون شاخه‌ای از ریاضیات قرار گرفت که بررسی می‌کند چند یال الگویی معین را ناگزیر می‌کند. حالت‌های خاص یکی‌یکی حل شدند: ستاره‌ها، مسیرها، ستاره‌های دوگانه، درخت‌هایی با شاخه‌های اندک. در اوایل دههٔ 1990، چهار ریاضی‌دان — آیتای، کوملوش، شیمونوویچ و سمرهدی — اثباتی برای درخت‌های بسیار بزرگ اعلام کردند، اما مقاله‌های اخیر یادآور می‌شوند که هیچ دست‌نوشتهٔ کاملی هرگز منتشر نشد. نتایج جزئی دیگری در 2021، 2024 و 2026 از راه رسید. در 4 سپتامبر 2026، رید و استاین اثباتی برای گراف‌های بزرگ و چگال منتشر کردند که به گفتهٔ خودشان بدون هوش مصنوعی پرورده شده بود.
سپس گزارشی از راه رسید. در سپتامبر 2026، تام آدامچفسکی و توماس بلوم، در سندی به نام FrontierMath Erdős، اثباتی از کل حدس را به نسخه‌ای پیش از انتشار از یک مدل هوش مصنوعی، GPT-6 Astra، نسبت دادند. استدلال شمارشی اصلی عمومی است، و مخزنی همراه، جست‌وجوی خودمختار هوش مصنوعی برای اثبات و یک وارسی صوری به زبان وارسی اثبات Lean را ثبت کرده است. نویسندگان گزارش همچنین از کارشناسان انسانی خواستند شرح‌های کامل‌تر و سنتی بنویسند.
آشکار کردن گراف، نقطه به نقطه
جی کامینگز، از دانشگاه ایالتی کالیفرنیا در ساکرامنتو، به این فراخوان پاسخ می‌دهد. مقالهٔ 27 صفحه‌ای او استدلال شمارشی محوری هوش مصنوعی را نگه می‌دارد اما شیوهٔ روایتش را تغییر می‌دهد:
- گراف را کم‌کم آشکار کن. رأس‌ها را به ترتیبی فهرست کن و یکی‌یکی، همراه با یال‌های میان رأس‌هایی که پیش‌تر نشان داده شده‌اند، آشکارشان کن.
- بیشتر بخواه. به جای هر نسخه‌ای از درخت، به دنبال نسخه‌ای بگرد که «ریشهٔ» برگزیده‌اش درست روی نخستین رأس باشد. بیشتر خواستن اثبات را آسان‌تر می‌کند.
- همسایه‌های زودرس را بشمار. این‌ها همسایه‌های رأس نخست‌اند که پیش از پدیدار شدن چنین نسخه‌ای ظاهر می‌شوند. آن‌ها را روی همهٔ ترتیب‌های ممکن جمع بزن.
- مجموع را کران‌دار کن. کامینگز با جابه‌جا کردن رأس‌ها یا بلوک‌های کامل ترتیب — حرکت‌هایی که همیشه می‌توان آن‌ها را برگرداند — نشان می‌دهد که به‌طور میانگین روی همهٔ ترتیب‌ها، حداکثر t − 2 همسایهٔ زودرس وجود دارد.
گام پایانی کوتاه است. اگر گراف هیچ نسخه‌ای از درخت نداشت، هر همسایهٔ رأس نخست در هر ترتیبی زودرس می‌بود. میانگین آن روی همهٔ ترتیب‌ها دقیقاً همان میانگین درجه است — که بنا به فرض از t − 2 بیشتر است. تناقض: درخت باید آنجا باشد.
این اثبات تنها از مجموع درجه‌ها استفاده می‌کند، نه از چگونگی پخش شدنشان. کامینگز نسخه‌ای احتمالاتی نیز ارائه می‌دهد و درخت‌هایی با چهار و پنج رأس را روی گراف‌های مشخص گام‌به‌گام بررسی می‌کند.
اثباتی به سبک کتاب مصور
مقاله 32 شکل دارد. با پیامدی کلاسیک به پایان می‌رسد: همهٔ خط‌های یک گراف کامل را با q رنگ رنگ‌آمیزی کنید؛ وقتی گراف q(t − 2) + 2 رأس داشته باشد، یک رنگ همیشه درخت داده‌شده را در خود خواهد داشت. کامینگز در بیانیه‌ای پایانی توضیح می‌دهد که متن را در گفت‌وگویی طولانی با ChatGPT پرورانده، که ایده‌های تازهٔ ارائه — همسایه‌های زودرس، افرازهای صریح، طرح‌ها — از آنِ خود اوست، و همه چیز را وارسی کرده و مسئولیت کامل آن را می‌پذیرد.
او شرح خود را با شرح‌های اخیر دیگر از ریوردن و اسکات، وود و فردریکسون مقایسه می‌کند و یادآور می‌شود که این روش هم‌اکنون به شبکه‌های جهت‌دار و به «اَبَرگراف‌ها» گسترش یافته است، و برخی از این گسترش‌ها نیز به GPT-6 Astra نسبت داده شده‌اند. او می‌نویسد سهم او «شرحی دیداری و خواننده‌محور از استدلال است، نه حلی تازه برای حدس».