OpenAI'nin Cycle Double Cover Conjecture'ının Kanıtı Görselleştirmesi

İki gün önce, OpenAI Döngü Çift Örtü varsayımının bir kanıtını kullanıma sundu: Köprüsü olmayan her kübik grafik, her kenarı tam olarak iki kez içeren bir döngüler kümesine sahiptir. Bu grafiklerde var olduğu bilinen, hiçbir yerde sıfır olmayan bir $\mathbb{Z__2^3$-flow $f$ ile başlarlar ve bunu, her bir kenarı tam olarak iki kez içeren 8 döngü birliğine dönüştürürler. Hiçbir yerde sıfır olmayan $\mathbb{Z__2^3$-akış, her köşedeki toplam 000 olacak şekilde 001, 010, 011, 100, 101, 110, 111'den bir sayının her kenara atanmasıdır. Burada $+$ XOR'dur çünkü taşıma olmadan bitsel toplamadır. Sadece her bir kenarın hangi iki döngüye ait olduğunu söylememiz ve ardından her köşenin her döngünün 0 veya 2 kenarına bitişik olması yerel koşulunu kontrol etmemiz gerekiyor. O zaman bu otomatik olarak onu bir döngüler birliği haline getirir. Her biri 000, 001, 010, 011, 100, 101, 110, 111 ile etiketlenen 8 döngü birliği olacaktır. Açıkçası $\mathbb{Z__2^3$ akışına bağlı olarak döngü üyeliğini bir şekilde seçmek istiyoruz. Her köşe için, daha sonra belirlenmek üzere bir $t_v \in \mathbb{Z__2^3$ seçeceğiz. Bu köşe daha sonra kenarlarının her birinin hangi döngüye ait olduğunu "söyleyecektir". Bu yapının bir açıklamasıdır ve daha sonra neden işe yaradığını göreceğiz. Her köşede hangi kenarın "üçüncü kenar" olduğunu nasıl seçeriz? Keyfi olarak. We can always make it work in the end. Ancak her $v$ için $t_v$'nin dikkatlice seçilmesi gerekir. Now we did something strange. Her bir kenarın hangi döngüye ait olduğunu söylememiz gerekiyor ama artık her köşenin söz hakkı var.

Ve bir kenarın iki ucu aynı fikirde olmayabilir. Ne zaman anlaşıyorlar? Bir tarafın veya diğer tarafın üçüncü kenar olmasına bağlı olarak özel durumlarımız var gibi görünüyor. Öyleyse $e$'ın her iki ucun üçüncü kenarı olmadığı duruma bakalım. Sonunda, üçüncü kenarlara sahip olmanın yalnızca $f$'ye bağlı bir sabit eklediğini göreceğiz. $f(e) + f(e) = 0$ olduğundan, iki koşul gereksizdir ve yalnızca birine ihtiyacımız var.