🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

Cet article présente une preuve assistée par ordinateur combinée et certifiée établissant les nombres de Zarankiewicz exacts pour des tranches finies spécifiques et une frontière voisine du problème Z(m,n,3,3), utilisant des certificats d'orbite, des lemmes de suppression et une vérification arithmétique rigoureuse pour confirmer des valeurs telles que Z(12,n,3,3)=6n pour 18≤n≤22 et Z(13,22,3,3)=137.

Auteurs originaux : Koyar Afrasyab

Publié 2026-08-11

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Koyar Afrasyab

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un urbaniste essayant de construire le réseau routier le plus efficace possible. Vous avez deux groupes de lieux : un ensemble de « Hubs » d'un côté et un ensemble de « Destinations » de l'autre. Votre objectif est de tracer autant de routes (connexions) que possible entre eux pour maintenir la fluidité du trafic. Cependant, une loi de zonage stricte vous interdit de construire un motif d'intersection spécifique et désordonné. En langage mathématique, ce motif interdit est un « sous-graphe biparti complet », ou simplement, vous ne pouvez pas avoir une situation où trois Hubs sont tous connectés aux mêmes trois Destinations. Si vous faites cela, vous avez enfreint la règle.

Ce puzzle est connu sous le nom de problème de Zarankiewicz. C'est un casse-tête classique dans le domaine de la combinatoire, qui est la branche des mathématiques dédiée au comptage, à l'arrangement et à l'organisation des choses. Bien que les mathématiciens aient trouvé des moyens de résoudre cela pour des villes théoriques massives, le véritable défi réside dans les villes de « taille moyenne ». Pour ces tailles spécifiques, le nombre de cartes routières possibles est si immense que vous ne pouvez pas toutes les vérifier à la main, mais elles sont aussi trop complexes pour de simples formules. C'est une zone de difficulté « Goldilocks » : trop grande pour une preuve papier-crayon, mais trop petite pour les raccourcis « asymptotiques » qui fonctionnent pour les villes infinies. Résoudre ces nombres exacts est important car ils révèlent les limites cachées de l'efficacité dans les réseaux, des puces informatiques aux connexions des réseaux sociaux.

Entrez Koyar Afrasyab, un chercheur qui vient de percer un ensemble particulièrement tenace de ces puzzles de taille moyenne. Voyez ce problème comme une tentative de trouver le nombre absolu maximum de routes que vous pouvez tracer sur une grille sans créer ce « bouchon » de trafic interdit de « trois par trois ». Le papier se concentre sur deux « tranches » spécifiques de ce problème : des grilles de 12 lignes et des grilles de 13 lignes, associées à différents nombres de colonnes.

La découverte principale est une liste de « limites de vitesse » exactes pour ces grilles. Pour une grille de 12 lignes et n'importe quel nombre de colonnes allant de 18 à 22, le nombre maximum de routes (arêtes) que vous pouvez avoir sans enfreindre la règle est exactement $6n$ (où $n$ est le nombre de colonnes). Par exemple, une grille de 12 par 18 peut contenir exactement 108 routes, et une grille de 12 par 22 peut en contenir exactement 132. Le papier prouve cela en montrant que si vous essayez d'ajouter juste une route de plus à ces grilles, vous créez inévitablement le bouchon de trafic interdit.

La partie la plus spectaculaire de l'histoire concerne une grille de 13 par 22. Des suppositions antérieures suggéraient que la limite pourrait être aussi haute que 140 routes. La preuve assistée par ordinateur d'Afrasyab agit comme un tamis, filtrant chaque arrangement impossible. Ils ont commencé en supposant que quelqu'un pouvait construire une grille avec 138 routes sans enfreindre les règles. Grâce à un processus d'élimination ingénieux — en vérifiant les « profils » de la manière dont les routes se connectent à chaque point — ils ont prouvé que 138 est impossible. Ils ont réduit l'écart jusqu'à trouver le véritable plafond : 137 routes. Ils ont même fourni une carte spécifique et vérifiée de 137 routes qui fonctionne, prouvant que vous pouvez atteindre ce nombre mais pas aller au-delà.

Le papier fixe également la carte pour plusieurs grilles voisines, déterminant les limites exactes pour des tailles comme 13-par-18, 14-par-17 et 15-par-18. Pour un cas délicat, une grille de 16-par-17, la preuve confirme que vous pouvez certainement construire 132 routes, mais la limite supérieure reste une plage serrée entre 132 et 133.

Ce qui rend ce travail spécial, c'est la manière dont il a été réalisé. L'auteur n'a pas seulement exécuté un programme informatique « boîte noire » qui disait « aucune solution trouvée ». Au lieu de cela, il a créé une preuve « basée sur des certificats ». Imaginez un détective laissant une trace de miettes de pain : pour chaque scénario impossible qu'il a éliminé, il a laissé un « reçu » mathématique (un certificat) que n'importe qui peut vérifier avec une simple calculatrice pour vérifier l'erreur. Le papier inclut un package numérique où vous pouvez exécuter une seule commande pour rejouer toute l'enquête, vérifiant des millions de ces reçus pour s'assurer qu'aucune erreur n'a été commise. C'est une victoire rigoureuse, transparente et entièrement reproductible pour la communauté mathématique, transformant un ensemble de réponses « peut-être » en un ensemble de faits « certainement ».

Résumé Technique : Valeurs Exactes de Zarankiewicz sur Deux Frontières Finies

Énoncé du Problème
L'article traite du problème de Zarankiewicz, qui cherche le nombre maximal d'arêtes, noté $Z(m, n, s, t)$ , dans un graphe biparti dont les parties sont de tailles $m$ et $n$ et qui ne contient pas de sous-graphe biparti complet $K_{s,t}$ . L'auteur se concentre spécifiquement sur le cas $s=t=3$ (évitant $K_{3,3}$ ) pour des paramètres finis modérés. Bien que la théorie asymptotique soit bien développée, les valeurs exactes pour des dimensions finies spécifiques restent difficiles à déterminer en raison d'une symétrie sévère et du coût élevé de la certification de preuve. L'article cible une « frontière finie » de valeurs précédemment non résolues ou partiellement résolues, incluant la bande $Z(12, n, 3, 3)$ pour $18 \le n \le 22$ , le cas spécifique $Z(13, 22, 3, 3)$ , ainsi qu'un groupe de valeurs voisines autour de $13 \times 18$ et $16 \times 17$ .

Méthodologie
La preuve est assistée par ordinateur mais strictement basée sur des certificats, ce qui la distingue des méthodes reposant uniquement sur des solveurs de programmation linéaire en nombres entiers mixtes (MILP) renvoyant « infaisable » ou des solveurs SAT sans témoins explicites. La vérification repose sur l'arithmétique exacte d'entiers et de rationnels (utilisant la classe Fraction de Python et des bibliothèques standards), l'optimisation en virgule flottante n'étant utilisée que pour la découverte initiale des certificats.

La méthodologie emploie une stratégie de réduction multicouche :

Relaxation Globale et Profils de Degrés : Pour le cas $13 \times 22$ , l'auteur suppose l'existence d'une matrice hypothétique possédant 138 arêtes. En analysant la fonction de « pénalité » $p(d) = \binom{d}{3} - 15d + 70$ associée aux degrés des colonnes, l'espace de recherche est réduit de l'ensemble des matrices possibles à seulement 83 profils de degrés distincts (histogrammes des degrés de colonnes).
Certificats de Farkas : Pour 77 de ces 83 profils, l'auteur construit des certificats de Farkas rationnels exacts. Ces certificats prouvent l'infaisabilité en démontrant que les contraintes linéaires imposées par la condition de non-contenant de $K_{3,3}$ (spécifiquement, que chaque triplet de lignes apparaît dans au plus 2 colonnes) ne peuvent être satisfaites par aucune solution d'entiers non négatifs pour ce profil.
Énumération de Lignes Marquées et de Restes : Les six profils restants sont exclus à l'aide de techniques plus granulaires. L'auteur fixe une « ligne marquée », la supprime, et analyse le « multigraphe de reste » résultant sur les 12 points restants. Cela implique :
- Arguments de Congruence : Utilisation de l'arithmétique modulaire sur les déficits de lignes pour exclure des configurations spécifiques (par exemple, le profil 6187391).
- Contraintes de la Matrice de Gram : Vérification des conditions de rang et de déterminant de la matrice d'incidence des blocs résiduels.
- Énumération Exacte : Énumération exhaustive des plans de blocs résiduels et application de certificats de Farks à échelle entière aux systèmes de factorisation restants.
Lemmes de Suppression et Témoins : Pour la bande $12 \times n$ et la fermeture de la frontière, l'auteur utilise des « lemmes de suppression » (reliant $Z(m, n)$ à $Z(m, n-1)$ ) combinés à des témoins constructifs explicites (matrices atteignant les bornes inférieures) pour établir des égalités exactes.

Contributions Clés et Résultats
L'article fournit une preuve combinée, basée sur des certificats, pour les valeurs et bornes exactes suivantes :

La Bande $12 \times n$ : Prouve que $Z(12, n, 3, 3) = 6n$ pour $18 \le n \le 22$ . Ceci est établi par un certificat exact pour $Z(12, 18, 3, 3) = 108$ et des arguments de suppression ultérieurs soutenus par des témoins explicites pour $n=19, 20, 21, 22$ .
Le Cas $13 \times 22$ : Prouve que $Z(13, 22, 3, 3) = 137$ . La borne supérieure de 138 est éliminée par l'analyse de profil exhaustive décrite ci-dessus. Une borne inférieure de 137 est confirmée via une construction explicite (une matrice binaire $13 \times 22$ avec 137 uns et aucun $K_{3,3}$ ).
Fermeture de la Frontière : Établit des valeurs exactes pour quatre cellules voisines :
- $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'Intervalle $16 \times 17$ : Rapporte l'intervalle $132 \le Z(16, 17, 3, 3) \le 133$ . La borne inférieure est soutenue par un nouveau témoin de 132 arêtes ; la borne supérieure de 133 est tirée de la littérature antérieure (Collins et al.). L'article note explicitement que la valeur exacte pour cette cellule spécifique n'est pas déterminée dans ce travail.

Signification et Revendications
L'auteur affirme que ce travail fournit une preuve complète, reproductible et basée sur des certificats pour ces valeurs spécifiques de Zarankiewicz. La signification réside dans la séparation rigoureuse entre la découverte (où des heuristiques en virgule flottante peuvent être utilisées) et la vérification (qui utilise uniquement l'arithmétique exacte).

Reproductibilité : L'article inclut une « porte de vérification en une commande » qui rejoue les 5,7 millions de vérifications de non-négativité exactes, incluant la régénération des profils de degrés, le rejeu des certificats de Farkas et l'énumération exhaustive des plans de blocs résiduels.
Modestie : L'auteur stipule explicitement que ces résultats doivent être considérés comme des « nouvelles preuves assistées par ordinateur en attente de reproduction indépendante et d'examen par les pairs ». L'article ne prétend pas résoudre le problème général de Zarankiewicz ni fournir un algorithme universel, mais démontre une division du travail pour les problèmes extrémaux finis : utiliser des relaxations globales grossières pour éliminer la plupart des cas et réserver l'énumération exacte, coûteuse en calcul, pour les quelques profils résiduels « difficiles ».
Antériorité : L'auteur note que bien que la construction à 137 arêtes pour $13 \times 22$ ait été rapportée précédemment, la borne supérieure exacte est une nouvelle contribution. De même, les valeurs spécifiques pour la bande $12 \times n$ ( $n=18$ à $21$) et les valeurs de fermeture de la frontière sont rapportées comme de nouveaux résultats exacts non trouvés dans la littérature indexée à la date de l'article (août 2026).

L'article conclut en soulignant qu'aucune revendication DRAT non vérifiée, aucun dépassement de délai SAT ou statut de solveur en virgule flottante n'est utilisé comme prémisse pour les théorèmes, garantissant que les affirmations mathématiques reposent entièrement sur des données finies explicites et l'arithmétique exacte.

Articles similaires