🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

Questo articolo presenta una prova assistita dal computer, combinata e basata su certificati, che stabilisce i numeri di Zarankiewicz esatti per specifiche fette finite e una frontiera vicina del problema Z(m,n,3,3), utilizzando certificati di orbita, lemmi di cancellazione e verifica aritmetica rigorosa per confermare valori quali Z(12,n,3,3)=6n per 18≤n≤22 e Z(13,22,3,3)=137.

Autori originali: Koyar Afrasyab

Pubblicato 2026-08-11

📖 4 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Koyar Afrasyab

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere un urbanista che cerca di costruire la rete stradale più efficiente possibile. Hai due gruppi di località: un insieme di "Hub" su un lato e un insieme di "Destinazioni" sull'altro. Il tuo obiettivo è tracciare quante più strade (connessioni) puoi tra di loro per mantenere fluido il traffico. Tuttavia, esiste una rigorosa legge di zonizzazione: ti è proibito costruire un particolare e disordinato schema di incroci. In termini matematici, questo schema proibito è un "sottografo bipartito completo", o semplicemente, non puoi avere una situazione in cui tre Hub siano tutti collegati alle stesse tre Destinazioni. Se lo facessi, avresti infranto la regola.

Questo enigma è noto come problema di Zarankiewicz. È un classico rompicapo nel campo della combinatoria, che è la branca della matematica dedicata al conteggio, all'ordinamento e all'organizzazione delle cose. Mentre i matematici sono riusciti a risolvere questo problema per città enormi e teoriche, la vera sfida risiede nelle città di "medie dimensioni". Per queste dimensioni specifiche, il numero di possibili mappe stradali è così vasto che non puoi controllarle tutte a mano, ma sono anche troppo complesi per le scorciatoie "asintotiche" che funzionano per le città infinite. È una zona di difficoltà perfetta: troppo grande per una dimostrazione con carta e penna, ma troppo piccola per i ripassi "asintotici" che funzionano per le città infinite. Risolvere questi numeri esatti è importante perché rivelano i limiti nascosti di efficienza nelle reti, dalle microchip ai collegamenti dei social media.

Entra in scena Koyar Afrasyab, un ricercatore che ha appena scardinato un set particolarmente ostinato di questi enigmi di medie dimensioni. Pensa al problema come al tentativo di trovare il numero massimo assoluto di strade che puoi tracciare su una griglia senza creare quel proibito ingorgo del traffico "tre per tre". Afrasyab non ha solo tirato a indovinare; ha costruito un'agenzia investigativa digitale per dare la caccia alla risposta. Il documento si concentra su due specifici "fette" di questo problema: griglie con 12 righe e griglie con 13 righe, accoppiate con vari numeri di colonne.

La scoperta principale è un elenco di esatti "limiti di velocità" per queste griglie. Per una griglia con 12 righe e da 18 a 22 colonne, il numero massimo di strade (archi) che puoi avere senza infrangere la regola è esattamente $6n$ (dove $n$ è il numero di colonne). Ad esempio, una griglia 12 per 18 può contenere esattamente 108 strade, e una griglia 12 per 22 può contenerne 132. Il documento prova questo dimostrando che se provi ad aggiungere anche solo una strada in più a queste griglie, crei inevitabilmente il proibito ingorgo del traffico.

La parte più drammatica della storia riguarda una griglia 13 per 22. Le ipotesi precedenti suggerivano che il limite potesse essere così alto come 140 strade. La prova assistita dal computer di Afrasyab agisce come un setaccio, filtrando ogni singolo arrangiamento impossibile. Hanno iniziato assumendo che qualcuno potesse costruire una griglia con 138 strade senza infrangere le regole. Attraverso un processo intelligente di eliminazione — controllando i "profili" di quante strade si collegano a ogni punto — hanno dimostrato che 138 è impossibile. Hanno ristretto il campo finché non hanno trovato il vero soffitto: 137 strade. Hanno persino fornito una mappa specifica e verificata di 137 strade che funziona, provando che puoi raggiungere quel numero ma non andare oltre.

Il documento fissa anche la mappa per diverse griglie vicine, determinando i limiti esatti per dimensioni come 13 per 18, 14 per 17 e 15 per 18. Per un caso particolarmente complicato, una griglia 16 per 17, la prova conferma che puoi sicuramente costruire 132 strade, ma il limite superiore è ancora un intervallo stretto tra 132 e 133.

Ciò che rende speciale questo lavoro è il modo in cui è stato eseguito. L'autore non si è limitato a far girare un programma per computer "black-box" che diceva "Nessuna soluzione trovata". Invece, ha creato una prova "basata su certificati". Immagina un detective che lascia una scia di briciole di pane: per ogni scenario impossibile che ha escluso, ha lasciato una "ricevuta" matematica (un certificato) che chiunque può controllare con una semplice calcolatrice per verificare l'errore. Il documento include un pacchetto digitale dove puoi eseguire un singolo comando per ripercorrere l'intera investigazione, controllando milioni di queste ricevute per assicurarsi che non siano stati commessi errori. È una vittoria rigorosa, trasparente e completamente riproducibile per la comunità matematica, che trasforma un insieme di risposte "forse" in un insieme di fatti "certamente".

Sintesi Tecnica: Valori Esatti di Zarankiewicz su Due Finitiamente Limiti di Frontiera

Enunciato del Problema
Il documento affronta il problema di Zarankiewicz, che cerca il numero massimo di archi, denotato con $Z(m, n, s, t)$ , in un grafo bipartito con parti di dimensione $m$ e $n$ che non contiene un sottografo completo bipartito $K_{s,t}$ . Nello specifico, l'autore si concentra sul caso $s=t=3$ (evitando $K_{3,3}$ ) per parametri finiti moderati. Mentre la teoria asintotica è ben sviluppata, i valori esatti per specifiche dimensioni finite rimangono difficili a causa della severa simmetria e dell'alto costo di certificazione della prova. Il documento mira a una "frontiera finita" di valori precedentemente irrisolti o parzialmente risolti, inclusa la striscia $Z(12, n, 3, 3)$ per $18 \le n \le 22$ , il caso specifico $Z(13, 22, 3, 3)$ e un cluster di valori limitrofi attorno a $13 \times 18$ e $16 \times 17$ .

Metodologia
La prova è assistita dal computer ma rigorosamente basata su certificati, distinguendosi dai metodi che si affidano esclusivamente a solver di programmazione lineare intera mista (MILP) che restituiscono "infattibilità" o a solver SAT senza testimoni espliciti. La verifica si basa sull'aritmetica esatta di interi e razionali (utilizzando Fraction di Python e librerie standard), con l'ottimizzazione a virgola mobile utilizzata solo per la scoperta iniziale dei certificati.

La metodologia impiega una strategia di riduzione multistrato:

Rilassamento Globale e Profili di Grado: Per il caso $13 \times 22$ , l'autore assume un ipotetico matrice con 138 archi. Analizzando la funzione di "penalità" $p(d) = \binom{d}{3} - 15d + 70$ associata ai gradi delle colonne, lo spazio di ricerca viene ridotto da tutte le possibili matrici a soli 83 profili di grado distinti (istogrammi dei gradi delle colonne).
Certificati di Farkas: Per 77 di questi 83 profili, l'autore costruisce esatti certificati razionali di Farkas. Questi certificati provano l'infattibilità dimostrando che i vincoli lineari imposti dalla condizione $K_{3,3}$ -free (specificamente, che ogni terna di righe appare in al massimo 2 colonne) non possono essere soddisfatti da alcuna soluzione intera non negativa per quel profilo.
Enumerazione di Righe Segnate e Residui: I restanti sei profili sono esclusi utilizzando tecniche più granulari. L'autore fissa una "riga segnata", la elimina e analizza il risultante "multigrafo residuo" sulle restanti 12 entità. Ciò comporta:
- Argomenti di Congruenza: Utilizzo dell'aritmetica modulare sui deficit di riga per escludere configurazioni specifiche (ad esempio, il profilo 6187391).
- Vincoli della Matrice di Gram: Verifica delle condizioni di rango e determinante della matrice di incidenza dei blocchi residui.
- Enumerazione Esaustiva: Enumerazione esaustiva dei design di blocchi residui e applicazione di certificati di Farkas con scala intera ai sistemi di fattorizzazione rimanenti.
Lemmi di Delezione e Testimoni: Per la striscia $12 \times n$ e la chiusura della frontiera, l'autore utilizza "lemmi di delezione" (relativi a $Z(m, n)$ rispetto a $Z(m, n-1)$ ) combinati con testimoni costruttivi espliciti (matrici che raggiungono i limiti inferiori) per stabilire uguaglianze esatte.

Contributi Chiave e Risultati
Il documento fornisce una prova combinata, basata su certificati, per i seguenti valori esatti e limiti:

La Striscia $12 \times n$ : Dimostra che $Z(12, n, 3, 3) = 6n$ per $18 \le n \le 22$ . Ciò è stabilito da un certificato esatto per $Z(12, 18, 3, 3) = 108$ e successivi argomenti di delezione supportati da testimoni espliciti per $n=19, 20, 21, 22$ .
Il Caso $13 \times 22$ : Dimostra che $Z(13, 22, 3, 3) = 137$ . Il limite superiore di 138 è eliminato tramite l'analisi dei profili descritta sopra. Un limite inferiore di 137 è confermato tramite una costruzione esplicita (una matrice binaria $13 \times 22$ con 137 uni e nessuna $K_{3,3}$ ).
Chiusura della Frontiera: Stabilisce valori esatti per quattro celle limitrofe:
- $Z(13, 18, 3, 3) = 116$
- $Z(14, 17, 3, 3) = 118$
- $Z(14, 18, 3, 3) = 124$
- $Z(15, 17, 3, 3) = 126$
- $Z(15, 18, 3, 3) = 132$
L'Intervallo $16 \times 17$ : Riporta l'intervallo $132 \le Z(16, 17, 3, 3) \le 133$ . Il limite inferiore è supportato da un nuovo testimone a 132 archi; il limite superiore di 133 è preso dalla letteratura precedente (Collins et al.). Il documento nota esplicitamente che il valore esatto per questa specifica cella non è determinato all'interno di questo lavoro.

Significato e Rivendicazioni
L'autore sostiene che questo lavoro fornisca una prova completa, riproducibile e basata su certificati per questi specifici valori di Zarankiewicz. La significatività risiede nella rigorosa separazione tra la scoperta (dove possono essere usate euristiche a virgola mobile) e la verifica (che utilizza solo aritmetica esatta).

Riproducibilità: Il documento include un "gate di verifica a comando singolo" che riproduce tutti i 5,7 milioni di controlli di non negatività esatti, inclusa la rigenerazione dei profili di grado, la riproduzione dei certificati di Farkas e l'enumerazione esaustiva dei design di blocchi residui.
Modestia: L'autore afferma esplicitamente che questi risultati devono essere considerati come "nuove prove assistite dal computer in attesa di riproduzione indipendente e revisione paritaria". Il documento non pretende di risolvere il problema generale di Zarankiewicz o di fornire un algoritmo universale, ma dimostra una divisione del lavoro per problemi estremi finiti: l'uso di rilassamenti globali grossolani per eliminare la maggior parte dei casi e la riserva dell'enumerazione esatta, computazionalmente intensiva, per i pochi profili residui "difficili".
Stato dell'Arte: L'autore nota che, sebbene la costruzione a 137 archi per $13 \times 22$ sia stata precedentemente riportata, il limite superiore esatto è un nuovo contributo. Allo stesso modo, i valori specifici per la striscia $12 \times n$ ( $n=18$ a $21$) e i valori di chiusura della frontiera sono riportati come nuovi risultati esatti non presenti nella letteratura indicizzata precedente alla data del documento (agosto 2026).

Il documento conclude sottolineando che non vengono utilizzati né affermazioni DRAT non verificate, timeout SAT o stati di solver a virgola mobile come premesse per i teoremi, garantendo che le affermazioni matematiche poggino interamente su dati finiti espliciti e aritmetica esatta.

Articoli simili