هر نقطه را به همهٔ نقطه‌های دیگر وصل کنید: کمترین تعداد تقاطع، اثبات شد

پنج نقطه روی برگه‌ای کاغذ بگذارید و هر جفت را با یک منحنی به هم وصل کنید: روی هم ده منحنی. منحنی‌ها می‌توانند هر طور بخواهید خم شوند، اما هیچ‌کدام نباید از نقطهٔ سومی بگذرد. بکوشید از هر تقاطعی پرهیز کنید، و شکست خواهید خورد. با پنج نقطه، دست‌کم 1 تقاطع گریزناپذیر است؛ با شش نقطه، دست‌کم 3؛ با ده نقطه، دست‌کم 60.

ریاضی‌دانان چنین تصویری را یک رسم از گراف کامل Kₙ می‌نامند — n نقطه که هر جفتشان به هم وصل‌اند — و کمترین تعداد تقاطعی را که هر رسمی می‌تواند به آن برسد عدد تقاطع (crossing number) آن. مارتین بالکو (Martin Balko)، از دانشگاه چارلز در جمهوری چک، این پرسش را «یکی از مشهورترین مسائل نظریهٔ گراف توپولوژیک» می‌نامد.

شمارش یک هنرمند

در اواخر دههٔ 1950، آنتونی هیل (Anthony Hill)، هنرمند بریتانیایی، رسم‌هایی از Kₙ ساخت که دقیقاً

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

تقاطع داشتند، که در آن ⌊ ⌋ به معنای گرد کردن به پایین است. این حدس که هیچ رسمی نمی‌تواند بهتر عمل کند نخستین بار به‌دست گای (Guy) منتشر شد، بعدها هاراری (Harary) و هیل به آن پرداختند، و اردیش (Erdős) و گای آن را رواج دادند. این حدس با نام حدس هاراری–هیل (Harary–Hill conjecture) یا حدس گای شناخته می‌شود.

این فرمول به‌سرعت بالا می‌رود:

4 نقطه یا کمتر: 0 تقاطع
5 نقطه: 1
7 نقطه: 9
10 نقطه: 60
14 نقطه: 315

شش دهه پاسخ‌های نیمه‌کاره

رسم‌هایی با دقیقاً Z(n) تقاطع برای هر تعداد نقطه وجود داشت؛ بخش دشوار نشان دادن این بود که هیچ رسمی بهتر عمل نمی‌کند.

بیش از شصت سال، این تنها برای گونه‌های خاصی از رسم‌ها اثبات شده بود — برای نمونه وقتی همهٔ نقطه‌ها روی یک خط باشند و هر منحنی در یک سوی آن بماند، یا وقتی نقطه‌ها روی یک کره باشند و هر منحنی کوتاه‌ترین مسیر را بپیماید. خود بالکو، همراه با فولک (Fulek) و کینچل (Kynčl)، یکی از این دسته‌ها را حل کرده بود. تا سال 2021، رایانه‌ها فرمول را تا 14 نقطه تأیید کرده بودند. برای تعداد بسیار زیاد نقطه‌ها، بهترین نتایج کلی دست‌کم 98.5%، و سپس 98.99%، از Z(n) را تضمین می‌کردند.

یک اثبات، سپس اثباتی روشن‌تر

در سال 2026، OpenAI اثباتی برای هر تعداد نقطه اعلام کرد، که مقالهٔ بالکو آن را با عنوان «OpenAI Math Release preprint» فهرست می‌کند و قضیه را به آن نسبت می‌دهد. مقاله نمی‌گوید این اثبات چگونه یافته شد. به گفتهٔ بالکو، اثبات اصلی «نسبتاً کوتاه است»، اما «دنبال کردنش بسیار دشوار است». پیش‌چاپ او نسخهٔ ساده‌شده‌ای ارائه می‌دهد که، به نوشتهٔ خودش، «تنها به دانش مقدماتی جبر خطی و نظریهٔ گراف نیاز دارد». ریاضی‌دان دیگری، گلاسیو سالازار (Gelasio Salazar)، در حال آماده کردن شرحی جداگانه و مفصل است.

شمردن ضرایب به جای تقاطع‌ها

از آنجا که رسم‌های شناخته‌شده از پیش به Z(n) می‌رسند، تنها کران پایین نیاز به اثبات دارد. این کار چهار گام دارد.

عددهای فرد کافی‌اند. بهترین رسم را می‌توان چنان از نو کشید که منحنی‌هایی که در یک نقطه مشترک‌اند هرگز یکدیگر را قطع نکنند؛ آنگاه هر تقاطع به 4 نقطهٔ متفاوت مربوط می‌شود. هر یک از 6 نقطه را به نوبت حذف کنید: هر تصویر 5 نقطه‌ای باقی‌مانده دست‌کم 1 تقاطع دارد، و هر تقاطع دقیقاً در 2 حذف از 6 حذف پابرجا می‌ماند (هرگاه یکی از 4 نقطهٔ خودش حذف شود ناپدید می‌شود، و در 2 حذف دیگر باقی می‌ماند). پس دو برابر تعداد تقاطع‌ها دست‌کم 6 است: یعنی دست‌کم 3، که همان Z(6) است. همین شمارش برای هر عدد زوج کار می‌کند.
خانواده‌ای از چندجمله‌ای‌ها. به هر نقطه عدد خودش را بدهید. یک تقاطع به دو منحنی مربوط است، پس به چهار نقطه، پس به چهار عدد. بالکو از چندجمله‌ای‌هایی با چهار متغیر استفاده می‌کند، که چنان برگزیده شده‌اند که وقتی n فرد است خانواده دقیقاً Z(n) ضریب مستقل داشته باشد — برای 7 نقطه، 3 × 3 = 9.
تقاطع‌های بسیار کم جا باز می‌گذارند. اینکه بخواهیم چندجمله‌ای در یک تقاطع صفر شود یک معادله است. وقتی معادله‌ها کمتر از ضرایب آزاد باشند، جبر خطی همیشه یک جواب ناصفر باقی می‌گذارد. پس رسمی با کمتر از Z(n) تقاطع با یک چندجمله‌ای ناصفر همراه خواهد بود که در همهٔ تقاطع‌هایش صفر می‌شود؛ آن را که کمترین درجه را دارد برگزینید.
صفحه پس می‌زند. هندسه از راه یک واقعیت کلاسیک وارد می‌شود: یک حلقهٔ بسته در صفحه، حلقهٔ دیگری را دقیقاً به همان تعداد بار از راست به چپ قطع می‌کند که از چپ به راست. با وزن‌هایی که خوب برگزیده شده‌اند، این به مجموعی از مربع‌های مقادیر چندجمله‌ای می‌انجامد، برخی با علامت مثبت و برخی با علامت منفی، که حاصلش صفر است. جمله‌های مثبت همگی در تقاطع‌ها قرار دارند، جایی که چندجمله‌ای صفر است، پس جمله‌های منفی هم باید صفر شوند. استفادهٔ دوم از واقعیت حلقه، چندجمله‌ای را بر عاملی ثابت بخش‌پذیر می‌کند؛ تقسیم بر آن، چندجمله‌ای ناصفری با درجهٔ کمتر و همان ویژگی به دست می‌دهد، که ناممکن است، چون ما کمترین درجه را برگزیده بودیم.

آن استدلال علامت، تغییر اصلی بالکو است: جایگزین استدلال اصلی می‌شود که «با یک فرم دوخطی ناتباهیده و مکمل‌های متعامد سروکار دارد». او همچنین واقعیت حلقه را به شیوه‌ای دیگر اثبات می‌کند و هر نقطه را مستقیم‌تر جدا می‌کند.

شبکه‌های دیگر، یکجا حل‌شده

اگر به جای تقاطع‌ها، جفت منحنی‌هایی را بشماریم که اصلاً یکدیگر را قطع می‌کنند، یا تعداد فردی بار قطع می‌کنند، پاسخ همچنان Z(n) می‌ماند — به شرط آنکه منحنی‌هایی که در یک نقطه مشترک‌اند هرگز در جای دیگری به هم نرسند. این قضیه، همراه با کاهش‌های پیشین، عدد تقاطع دقیق را برای گراف‌های کاملی که برخی پیوندهایشان حذف شده، برای نسخه‌هایی از یک گراف کامل که در امتداد یک مسیر یا به دور یک دور زوج به هم زنجیر شده‌اند، و برای خانواده‌ای از شبکه‌های برخال‌گونه به نام گراف‌های سرپینسکی توسیع‌یافته (extended Sierpiński graphs) نیز به دست می‌دهد.

تنها یک منحنی را از گراف کامل روی 6 نقطه بردارید، و کمینهٔ آن از 3 تقاطع به 2 می‌رسد؛ روی 8 نقطه، از 18 به 15.