Attacco Sistematico di un Agente AI al Problema del Grafo 99 di Conway
Un recente preprint su arXiv (2608.11211) descrive un attacco completo e riproducibile al problema del grafo 99 di Conway, che chiede se esista un grafo fortemente regolare con parametri srg(99,14,1,2). Questa ricerca è stata condotta da un agente AI autonomo e valutata utilizzando una metrica a punteggio parziale. I contributi chiave dell'articolo includono: (1) una prova completa che dimostra che nessun grafo circolante su Z/99 soddisfa più di 3366/4950 = 68.0% dei requisiti (33 su 49 classi di differenza), il che vale anche per l'altro gruppo abeliano di ordine 99; (2) una riduzione a struttura forzata che porta a un grafo 12-regolare su 84 vertici; (3) un quadro validato per l'esistenza di orbite con automorfismi prescritti. Questo lavoro rappresenta un passo significativo nell'applicazione dell'AI a un problema di lunga data nella teoria dei grafi, sebbene sia ancora preliminare e non sia stato sottoposto a revisione paritaria. L'articolo è accessibile all'indirizzo https://arxiv.org/abs/2608.11211.
Fatti principali
- L'articolo affronta il problema del grafo 99 di Conway, chiedendo se esista un grafo fortemente regolare srg(99,14,1,2).
- Un agente di ricerca AI autonomo ha condotto l'attacco, valutato con una metrica a punteggio parziale.
- Prova esaustiva: nessun grafo circolante su Z/99 soddisfa più del 68.0% dei vincoli (33 su 49 classi di differenza).
- Lo stesso limite si applica all'altro gruppo abeliano di ordine 99.
- Riduzione a struttura forzata: λ=1 rende ogni intorno un accoppiamento perfetto; μ=2 mette i vertici esterni in biiezione con le coppie di vicini non accoppiati.
- La riduzione riconduce l'esistenza a un grafo 12-regolare su 84 vertici, codificato per CP-SAT.
- La riduzione è stata validata recuperando l'unico srg(9,4,1,2).
- È stato sviluppato un quadro validato per l'esistenza di orbite con automorfismi prescritti, inclusi azioni senza punti fissi e con un singolo punto fisso, verificato su grafi noti.
- L'articolo è un nuovo preprint arXiv (2608.11211), non ancora sottoposto a revisione paritaria.
Entità
Istituzioni
- arXiv