چهار رنگ برای هر نقشه، یافته‌شده در زمان خطی
هر نقشه‌ای که روی صفحه‌ای تخت کشیده شود، می‌تواند با چهار رنگ طوری رنگ‌آمیزی شود که کشورهای همسایه هرگز یک رنگ نداشته باشند. Francis Guthrie این را در 1852 حدس زد؛ Appel و Haken آن را در 1976 اثبات کردند. اما قضیه تنها می‌گوید چهار رنگ وجود دارد. برای یک نقشهٔ مشخص چگونه آن‌ها را پیدا کنیم؟ Yuta Inoue از دانشگاه توکیو و پنج همکارش از ژاپن، کانادا، اسلوونی و دانمارک می‌نویسند: «پاسخ آسانی وجود ندارد.» این مسئله چنان پیچیده بوده که به پیشنهاد مثال‌های نقض بسیاری انجامیده است.
نقطه‌ها، خط‌ها و مثلث‌ها
هر کشور به یک نقطه، یا رأس (vertex)، و هر مرز مشترک به یک خط، یا یال (edge)، تبدیل می‌شود: نقشه به یک گراف مسطح (planar graph) بدل می‌شود که بدون خط‌های متقاطع کشیده شده است. رنگ‌آمیزی آن یعنی دادن یکی از چهار رنگ به هر رأس، طوری که دو سر هر یال رنگ متفاوت داشته باشند. تعداد رأس‌ها را n بنامید. کافی است به مثلث‌بندی‌ها (triangulations) بپردازیم، که در آن‌ها هر وجه یک مثلث است: یال‌های بیشتر فقط رنگ‌آمیزی را دشوارتر می‌کنند.
جابه‌جایی کمپه
حرکت پایه به مقاله‌ای از A. B. Kempe در 1879 بازمی‌گردد. چهار رنگ را جفت کنید، مثلاً قرمز با آبی و سبز با زرد. یک زنجیرهٔ کمپه (Kempe chain) گروهی همبند از رأس‌هاست که دو رنگ یک جفت را دارند. جابه‌جا کردن این دو رنگ در سراسر یک زنجیره، رنگ‌آمیزی را معتبر نگه می‌دارد.
رأس v را با چهار همسایه در نظر بگیرید، v0 تا v3 به ترتیب گرداگردش، و ابتدا بقیه را رنگ کنید. اگر همسایه‌ها سه رنگ یا کمتر به کار ببرند، v رنگ آزاد را می‌گیرد. اگر هر چهار رنگ را به کار ببرند، زنجیره‌ای را دنبال کنید که از v0 با رنگ‌های v0 و v2 آغاز می‌شود. اگر به v2 نرسد، آن را جابه‌جا کنید: v0 رنگ v2 را می‌گیرد و رنگی برای v آزاد می‌شود. اگر به v2 برسد، به جای آن زنجیرهٔ v1 را با رنگ‌های v1 و v3 جابه‌جا کنید تا v1 رنگ v3 را بگیرد.
تکه‌هایی که همیشه می‌توان ترمیمشان کرد
اثبات‌های قضیه بر پیکربندی‌های کاهش‌پذیر (reducible configurations) استوارند: الگوهای کوچکی که می‌توان آن‌ها را برید و پس از رنگ‌آمیزی بقیه دوباره سر جایشان گذاشت. اگر رنگ‌های حلقهٔ (ring) آن‌ها — رأس‌هایی که درست دورشان هستند — جور درنیاید، تعداد محدودی تغییر کمپهٔ بهبوددهنده که بیرون از آن‌ها انجام شود همیشه درستشان می‌کند: حداکثر 25 برای الگوهای به‌کاررفته در اینجا، که حلقه‌هایشان حداکثر 18 رأس دارند.
یک پیکربندی کاهش‌پذیر (چپ؛ هر عدد نشان می‌دهد آن رأس در نقشهٔ کامل باید چند همسایه داشته باشد) و همان الگو که با حلقه‌اش R کامل شده است (راست). — شکل 1، Inoue و همکاران (2026)، arXiv:2610.39753.
Robertson، Sanders، Seymour و Thomas در 1997 نشان دادند چگونه می‌توان به این روش، هر بار یک الگو، رنگ‌آمیزی کرد. هر دور گراف را چند رأس کوچک‌تر می‌کند و به بهای یک پیمایش کامل آن تمام می‌شود، پس زمان درجه‌دوم (quadratic) است: برای نقشه‌ای دو برابر بزرگ‌تر، چهار برابر طولانی‌تر.
در مقاله‌ای پیشین (FOCS’26)، همین شش نویسنده اثبات کردند که هر مثلث‌بندی، به تعدادی متناسب با n، پیکربندی کاهش‌پذیرِ نامتماس دارد که از فهرستی 8,202تایی گرفته شده‌اند — یا به همان تعداد حلقهٔ کوتاه با رأس‌هایی در هر دو سو، که آن‌ها هم کمک می‌کنند. آن‌ها همهٔ الگوها را یکجا برمی‌دارند، بقیه را رنگ می‌کنند و سپس همهٔ حلقه‌ها را با هم ترمیم می‌کنند. یک تغییر کمپهٔ تصادفی به یک حلقهٔ مشخص کمک می‌کند اگر جفت‌بندی درست رنگ‌ها را برگزیند (یک شانس از سه) و شیر یا خط درست را روی هر زنجیره‌ای که با حلقه تماس دارد (هر کدام یک شانس از دو). با حداکثر 18 زنجیره از این دست، این دست‌کم یک شانس از 3 × 2¹⁸، یعنی 786,432، است: کوچک، اما ثابت. پس تعداد دورها تنها مانند log n رشد می‌کند، تقریباً تعداد دفعاتی که می‌توان n را نصف کرد. اما یک تغییر می‌تواند کسر ثابتی از گراف را در بر بگیرد: هر کدام به بهای یک پیمایش کامل، در مجموع n log n.
جدولی به جای پیمایش
مقالهٔ جدید log n تغییر را نگه می‌دارد اما هر یک را ارزان‌تر می‌کند. پس از آماده‌سازی‌ای که زمانی متناسب با n می‌برد، هر تغییر به‌طور میانگین در حدود n / log n گام یافته و اجرا می‌شود. در این صورت log n تغییر روی هم زمانی متناسب با n — زمان خطی (linear time) — می‌برند، کرانی که نویسندگان آن را بهینه می‌نامند.
ترفند، «روش چهار روس» (Method of Four Russians) است. زیرمسئله‌ای که در کدی ½ log n بیتی — نیمی از رقم‌های دودویی لازم برای نوشتن n — جا شود، حداکثر √n نسخهٔ ممکن دارد، پس همهٔ پاسخ‌هایشان را می‌توان از پیش محاسبه و در جدولی ذخیره کرد. رایانهٔ فرضی، با واژه‌های حافظه‌ای حدود log n بیتی، هر پاسخ ذخیره‌شده را در یک گام می‌خواند.
گراف بارها و بارها به ناحیه‌های تودرتو با مرزهای کوتاه بریده می‌شود. کوچک‌ترین‌ها حدود log n رأس دارند و همراه رنگ‌ها در یک کد جا می‌شوند. برای هر ناحیه، یک گراف خلاصهٔ کوچک ثبت می‌کند کدام رأس‌های مرزی در یک زنجیرهٔ کمپه شریک‌اند. آنگاه یک تغییر به شکل رشته‌هایی از بیت‌های «جابه‌جا کن» یا «نگه دار» به پایین می‌رود و در هر ناحیهٔ کوچک یک بار رجوع به جدول، همهٔ رنگ‌ها را به‌روز می‌کند.
بخشی از گرافی که با چهار رنگ رنگ‌آمیزی شده است. ناحیهٔ خاکستری یک ناحیهٔ R است؛ یال‌های سیاه پررنگ به زنجیره‌های کمپهٔ جفت‌های قرمز-آبی و سبز-زرد تعلق دارند. — شکل 2، Inoue و همکاران (2026)، arXiv:2610.39753.
خلاصهٔ همان ناحیه: هر لکهٔ آبی نمایندهٔ تکه‌ای از یک زنجیرهٔ کمپه است و خط‌هایش نشان می‌دهند کدام رأس‌های مرزی را به هم وصل می‌کند. — شکل 3، Inoue و همکاران (2026)، arXiv:2610.39753.
انتخاب بدون تاس
با انتخاب‌های تصادفی، این روش هم‌اکنون نقشه را به‌طور میانگین در زمان خطی رنگ می‌کند. حذف تاس بدون از دست دادن سرعت «به‌مراتب دشوارترین بخش» بود. حلقه‌ای را زنده بنامید تا وقتی که هر تصمیمِ تاکنون به سود آن بوده است. اگر u زنجیرهٔ تصمیم‌نگرفته‌ای که با آن تماس دارند به شیر یا خط سپرده می‌شدند، حلقه با احتمال 1/2^u جان به در می‌برد؛ جمع این عددها روی همهٔ حلقه‌های زنده، تعداد مورد انتظار بازماندگان را می‌دهد. تصمیم دربارهٔ یک زنجیره، جملهٔ هر حلقه‌ای را که آن انتخاب را می‌خواست دو برابر و جملهٔ بقیه را صفر می‌کند. الگوریتم گزینه‌ای را برمی‌گزیند که نمی‌گذارد مجموع کاهش یابد، تا در پایان دست‌کم به همان تعداد حلقه کمک شود که شانس به‌طور میانگین کمک می‌کرد.
یک کران، نه یک زمان‌سنج
مقاله هیچ پیاده‌سازی (implementation) و زمان اجرایی گزارش نمی‌کند و ثابت‌های پنهان در «متناسب با n» داده نشده‌اند. این ثابت‌ها بزرگ‌اند: برای هر یک از 8,202 الگو، الگوریتم ذخیره می‌کند که هر رنگ‌آمیزی حلقه‌اش به چند تغییر بهبوددهنده نیاز دارد — «مقدار ثابتِ عظیمی از اطلاعات». نویسندگان در یک پیوست «اشتباه کوچکی» را هم در ساختار ناحیه‌های تودرتوی 2013 که بر آن بنا کرده‌اند اصلاح می‌کنند. حدسی از 1852 اکنون همراه با روشی برای رنگ‌آمیزی می‌آید که هزینه‌اش سریع‌تر از نقشه‌ای که رنگ می‌کند رشد نمی‌کند.