Nouveaux petits graphes réguliers de circonférence donnée : le problème des cages et au-delà

Informations de base

• ID de l'article : 2511.07247
• Titre : New small regular graphs of given girth: the cage problem and beyond
• Auteurs : Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• Classification : math.CO (Mathématiques combinatoires), cs.DM (Mathématiques discrètes)
• Date de publication : 11 novembre 2025
• Lien de l'article : https://arxiv.org/abs/2511.07247

Résumé

Le problème des cages (cage problem) s'intéresse à la recherche de graphes $(k,g)$ possédant le nombre minimum de sommets, c'est-à-dire des graphes $k$-réguliers ayant une circonférence (girth) égale à $g$. L'objectif principal est de déterminer $n(k,g)$ (l'ordre minimal de tels graphes) et d'identifier les graphes extrémaux correspondants. Cet article étudie le problème des cages et plusieurs de ses variantes d'un point de vue computationnel, en développant quatre algorithmes de génération de graphes complémentaires : génération exhaustive basée sur les relèvements (lifts), recherche tabou heuristique, recherche ascendante heuristique et technique de suppression. En utilisant ces méthodes, les auteurs établissent onze nouvelles bornes supérieures pour le problème classique des cages : $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$, $n(14,7) \leq 4716$. Ces résultats améliorent plusieurs bornes meilleures connues qui n'avaient pas changé depuis 22 ans, en particulier $n(4,10)$ qui passe de 384 à 320, constituant une amélioration substantielle.

Contexte et motivation de la recherche

Définition du problème

1. Problème fondamental : Le problème des cages cherche une $(k,g)$-cage (cage), c'est-à-dire un graphe $k$-régulier ayant le nombre minimum de sommets $n(k,g)$ et une circonférence égale à $g$. La circonférence est la longueur du plus court cycle du graphe.
2. Importance du problème :
   • Signification théorique : Les cages sont des objets centraux de la théorie extrémale des graphes, étroitement liés à des théories classiques comme la borne de Moore
   • Applications pratiques : Les structures creuses et hautement symétriques trouvent des applications dans la conception de réseaux de communication, les codes correcteurs d'erreurs, la cryptographie et autres domaines
   • Conception de réseaux : Fournissent des topologies supportant une propagation efficace et uniforme de l'information, évitant la surcharge des nœuds centraux, et présentant une robustesse aux défaillances
3. Limitations des méthodes existantes :
   • Pour la plupart des paires de paramètres $(k,g)$, la valeur exacte $n(k,g)$ est inconnue
   • Les bornes existantes n'ont pas été améliorées pendant de nombreuses années (certaines bornes remontent à 22 ans)
   • Les graphes de Moore n'existent que pour $g \in \{3,4,5,6,8,12\}$
   • La complexité computationnelle augmente drastiquement avec $k$ et $g$
4. Motivation de la recherche :
   • Exploiter la puissance de calcul moderne et les algorithmes d'optimisation pour améliorer les bornes de longue date
   • Développer des méthodes computationnelles systématisées pour traiter le problème des cages et ses variantes
   • Fournir des preuves empiriques pour la recherche théorique par la construction d'instances de graphes concrètes (comme la conjecture de bipartition pour les cages de circonférence paire)

Contributions principales

1. Cadre algorithmique : Développement de quatre algorithmes de génération de graphes complémentaires
   • Algorithme de retour arrière basé sur les relèvements de graphes de tension (BTA)
   • Recherche tabou heuristique (TS)
   • Recherche ascendante heuristique
   • Technique de suppression
2. Percées dans le problème classique des cages : Établissement de 11 nouvelles bornes supérieures, notamment :
   • $n(4,10) \leq 320$ (réduction significative de 384)
   • $n(3,16) \leq 936$ (amélioration de 960)
   • $n(3,17) \leq 2048$ (amélioration de 2176)
   • Premières bornes non triviales pour $n(4,11)$ et $n(6,11)$
3. Progrès sur les problèmes variantes :
   • Graphes réguliers de circonférence d'arête (egr) : 21 nouvelles bornes (2 bornes serrées)
   • Graphes réguliers de circonférence de sommet (vgr) : 29 nouvelles bornes (7 bornes serrées)
   • Graphes $(k,g,g+1)$ : 6 nouvelles bornes
   • Spectre $(k,g)$ : Détermination de 34 ordres précédemment non résolus
4. Ressources computationnelles et reproductibilité :
   • Environ 5 années-CPU de travail computationnel
   • Tous les codes et données disponibles publiquement sur GitHub
   • Vérification complète et contrôles de cohérence fournis

Détails des méthodes

Définition de la tâche

Entrée : Degré régulier $k$, circonférence $g$, contraintes supplémentaires optionnelles (comme la régularité de circonférence de sommet/arête)

Sortie : Graphe d'ordre minimal satisfaisant les conditions, ou borne supérieure améliorée $n(k,g)$

Contraintes : Le graphe doit être $k$-régulier (chaque sommet ayant un degré $k$) et avoir une circonférence d'au moins $g$ (longueur du plus court cycle $\geq g$)

Technique fondamentale : Relèvements de graphes de tension (Voltage Graph Lifts)

Principes de base

Étant donné un graphe de base $G=(V,E)$, un groupe $\Gamma$ et une assignation de tension $\alpha: A \rightarrow \Gamma$ (où $A$ est l'ensemble des arcs orientés), le graphe relevé $G_\alpha$ a pour ensemble de sommets : $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

Pour chaque arc $(u,v) \in A$ et chaque $s \in \Gamma$, il existe un arc $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$.

Propriétés clés

1. Préservation de la régularité (Observation 1) : $G$ est $k$-régulier si et seulement si $G_\alpha$ est $k$-régulier
2. Condition nécessaire de connexité (Observation 2) : Si $G$ n'est pas connexe, alors $G_\alpha$ n'est pas connexe
3. Calcul de la circonférence (Proposition 1) : La circonférence de $G_\alpha$ égale la longueur du plus court chemin fermé non-réversé dans le graphe orienté de $G$ (avec tension nette égale à $0_\Gamma$)
4. Simplification par arbre couvrant (Proposition 2) : On peut assigner la tension $0_\Gamma$ à tous les arcs d'un arbre couvrant sans modifier la classe d'isomorphisme du graphe relevé

Algorithme 1 : Algorithme de retour arrière (BTA)

Règles d'exclusion structurées

Exclusion basée sur la structure (indépendante de l'assignation de tension) :

1. Contrainte de demi-arête : Les arcs correspondant aux demi-arêtes ne peuvent être assignés qu'à des éléments de groupe d'ordre 2
2. Optimisation par arbre couvrant : Sélectionner un arbre couvrant $T$ et assigner la tension $0_\Gamma$ à ses arcs
3. Exclusion basée sur les cycles : Pour les arcs non-arborescents, si l'assignation de tension $a$ produit un cycle de longueur $(q+1)s$ (où $a^s=0_\Gamma$) inférieure à la circonférence cible, exclure cette tension

Exclusion basée sur l'assignation (dépendant de l'assignation partielle de tension) :

1. Vérification de canonicité (Algorithme 1) :
   • Utiliser les automorphismes de groupe $\phi_\Gamma$ et les automorphismes d'arête $\phi_G$
   • Conserver uniquement le représentant lexicographiquement minimal
   • Si une assignation partielle n'est pas canonique, tous ses complétions peuvent être exclus
2. Vérification incrémentale de circonférence (Algorithme 2) :
   • Vérifier uniquement les chemins fermés non-réversés utilisant les arcs nouvellement assignés
   • Exploiter la nature incrémentale pour améliorer l'efficacité

Flux de l'algorithme (Algorithme 3)

BTA(G, Γ, g_min):
  1. Effectuer les vérifications structurelles, déterminer les ensembles de tensions viables N
  2. Assignation récursive de tensions :
     - Pour chaque arc utile d, essayer chaque tension dans N(d)
     - Appliquer les vérifications de circonférence et de canonicité
     - Si approuvé, traiter récursivement l'arc suivant
     - Restaurer l'état lors du retour arrière
  3. Après assignation complète, construire le graphe relevé et filtrer

Algorithme 2 : Recherche tabou (TS)

Motivation

Le BTA a un coût computationnel élevé pour les instances de grande taille. La TS explore heuristiquement les assignations de tension prometteuses par échantillonnage.

Composants clés

Définition du voisinage : Toutes les assignations alternatives qui modifient exactement l'élément de groupe correspondant à une arête

Fonction de coût :

1. Basée sur la circonférence ($c_{girth}$) : $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{si } \text{Ord}(a) \neq 1 \\ C & \text{sinon} \end{cases}$ où $C$ est une grande constante de pénalité et $m$ est le nombre de chemins échantillonnés
2. Basée sur la régularité ($c_{reg}$) : $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ où $f_V$ et $f_D$ sont respectivement les fréquences d'apparition des sommets et des arcs dans les cycles de circonférence

Liste tabou : Stocke les modifications récentes pour éviter un retour immédiat, de longueur $3|\Gamma|$

Mécanisme de perturbation : Appliquer des modifications aléatoires pour s'échapper des optima locaux

Configuration des hyperparamètres (Tableau 1)

• Limite du nombre d'automorphismes d'arête/groupe : 200/2000
• Limite de temps BTA et TS : 20 secondes chacun par instance
• Circonférence minimale du voisinage : $g_{nbr} = g_{min} - 2$ (problème de circonférence) ou $g_{nbr} = g_{min}$ (problème de régularité)

Algorithme 3 : Recherche ascendante heuristique

Différence avec les méthodes précédentes : Recherche simultanée du graphe de base et de l'assignation de tension

Processus :

1. Commencer avec $n$ sommets isolés
2. À chaque itération :
   • Considérer toutes les paires d'arcs pouvant être ajoutées et les assignations de tension $t \in T(G)$
   • Sélectionner la modification maximisant $|T(G_t)|$ (stratégie gloutonne)
3. Vérifier si le graphe relevé améliore le record

Algorithme 4 : Technique de suppression

Idée fondamentale : Supprimer des sommets d'un graphe $(k,g+1)$ connu de petite taille, puis ajouter des arêtes pour compléter en graphe $k$-régulier

Stratégies spécifiques :

1. Circonférence 7, degré pair $8 \leq k \leq 14$ :
   • Supprimer deux sommets $u,v$ à distance 4 d'une $(k,8)$-cage
   • Supprimer $N_1(u), N_1(v), N_2(u,v)$
   • Taille de l'ensemble de suppression : $3k$ (amélioration par rapport à $3k-1$ de de Ruiter et Biggs)
2. Circonférence 11 :
   • Depuis une $(4,12)$-cage : supprimer $u,v$ à distance 6, $N_1(u), N_1(v), N_3(u,v)$ et un sommet de $N_2(u) \cap N_4(v)$, suppression de $3k+3$ sommets
   • Depuis une $(6,12)$-cage : stratégie similaire, suppression de $5k-1$ sommets

Configuration expérimentale

Ressources computationnelles

• Volume total : Environ 5 années-CPU
• Infrastructure : Flemish Supercomputer Center (VSC)
• Langage d'implémentation : Basé sur C++ (présumé, non explicitement mentionné)

Génération de graphes de base et de groupes

1. Groupes : Utiliser le système GAP pour générer tous les groupes non-isomorphes d'ordre $n < 1024$
2. Graphes de base :
   • Générateur multigraph étendu (multigraph+)
   • Générer des graphes réguliers connexes contenant des arêtes parallèles, des boucles et des demi-arêtes
   • Utiliser Nauty pour éliminer les graphes isomorphes

Stratégie de vérification

1. Vérification des entrées :
   • Groupes : Obtenus directement de GAP
   • Graphes de base : Comparaison avec le générateur pregraph (jusqu'à l'ordre 13)
2. Correction des optimisations :
   • Désactiver individuellement chaque optimisation (automorphismes de graphe, automorphismes de groupe, borne de circonférence)
   • Vérifier que le nombre de graphes relevés non-isomorphes générés reste cohérent
3. Vérification d'exhaustivité :
   • Comparer avec trois implémentations indépendantes :
     • Construction basée sur $K_{1,3}$
     • Relèvements de graphes Gray et Theta
     • Générateur de graphes cycliques par blocs (équivalent aux relèvements de groupe cyclique)
   • Tous les cas produisent des résultats identiques

Processus de filtrage

1. Vérification de connexité
2. Filtrage d'isomorphisme : Utiliser Nauty pour construire la représentation canonique
3. Vérification de circonférence et régularité : Utiliser l'algorithme de 29

Résultats expérimentaux

Résultats principaux : Problème classique des cages (Tableau 2)

Améliorations significatives

Résultats de la technique de suppression

• $(8,7) \leq 774$ (amélioration de 3 sommets par rapport à 777)
• $(10,7) \leq 1608$ (amélioration de 3 sommets par rapport à 1611)
• $(12,7) \leq 2890$ (amélioration de 3 sommets par rapport à 2893)
• $(14,7) \leq 4716$ (amélioration de 3 sommets par rapport à 4719)

Découvertes clés

1. Percée pour $(4,10)$ : Réduction de 384 à 320, réduction de 16,7%, l'amélioration la plus remarquable
2. Preuves de bipartition : Les nouveaux graphes $(3,16)$ et $(4,10)$ sont tous deux bipartis, soutenant la conjecture "les cages de circonférence paire sont bipartites"
3. Détails de construction (Figure 4) :
   • $(3,16)$ : Utilisant le groupe $C_{13} \rtimes C_9$ (ordre 117), graphe de base de 8 sommets
   • $(4,10)$ : Utilisant le groupe $C_5 \times D_4$ (ordre 40), graphe de base de 8 sommets

Résultats sur les problèmes variantes

Graphes réguliers de circonférence d'arête (Tableau 3)

• 21 nouvelles bornes, dont 2 bornes serrées (bornes supérieure et inférieure égales) :
  • $n(4,5,4) = 30$ (nouvellement déterminé)
  • Plusieurs cas $(6,5,\lambda_e)$ obtiennent pour la première fois une borne supérieure

Graphes réguliers de circonférence de sommet (Tableau 4)

• 29 nouvelles bornes, dont 7 bornes serrées :
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • Amélioration substantielle de plusieurs cas $(4,6,\lambda_v)$

Spectre $(k,g)$ (Tableau 5)

• Détermination de 34 ordres précédemment non résolus
• Principalement concentrés sur :
  • $(3,11)$ et $(3,12)$ : 7 nouveaux ordres
  • $(4,7)$ et $(4,8)$ : 12 nouveaux ordres
  • $(5,7)$ : 24 nouveaux ordres (de 184 à 256)

Graphes sans cycles $(g+1)$ (Tableau 6)

• 6 nouvelles bornes :
  • $n(3,11,12) \leq 228$ (amélioration de 272)
  • $n(3,13,14) \leq 600$ (amélioration de 800)
  • $n(3,15,16) \leq 1760$ (amélioration de 2162)

Analyse d'efficacité algorithmique

Stratégie d'allocation de temps

• Par combinaison graphe de base-groupe : BTA 20 secondes, TS 20 secondes
• Recherche de solution initiale TS : 2 secondes
• Recherche d'automorphisme de graphe : 2 secondes

Complémentarité algorithmique

1. BTA : Énumération exhaustive pour petites instances, garantit complétude
2. TS : Échantillonnage heuristique pour grandes instances, bonne scalabilité
3. Recherche ascendante : Optimisation simultanée du graphe de base et de l'assignation, flexibilité élevée
4. Suppression : Exploitation de graphes connus de grande taille, approche ciblée

Travaux connexes

Recherche sur le problème classique des cages

1. Bornes théoriques :
   • Borne de Moore (1963) : Borne inférieure fondamentale
   • Sauer (1967) : Inégalité $n(k,g) < n(k,g+1)$
   • Wong (1982) : Synthèse sur les cages
2. Méthodes de construction :
   • Balaban (1972-1973) : Cages $(3,10)$ et $(3,11)$
   • Benson (1966) : Cages $(k,12)$
   • Série de travaux de Biggs : Plusieurs petits graphes de circonférence
3. Méthodes computationnelles :
   • McKay et al. (1998) : Retour arrière rapide pour les cages
   • Exoo (2002-2020) : Techniques de graphes de tension
   • de Ruiter & Biggs (2015) : Programmation entière et suppression

Théorie des relèvements

• Gross & Tucker (1987) : Fondations de la théorie topologique des graphes
• Exoo & Jajcay (2011) : Théorie de la circonférence pour les relèvements de graphes de tension
• Cet article : Extension avec optimisations systématisées et méthodes heuristiques

Problèmes variantes

1. Graphes réguliers de circonférence :
   • Jajcay et al. (2018) : Graphes réguliers de circonférence d'arête
   • Jajcay et al. (2024) : Graphes réguliers de circonférence de sommet
   • Goedgebeur & Jooken (2025) : Génération exhaustive
2. Problème de spectre :
   • Eze et al. (2025) : Théorie et méthodes computationnelles du spectre $(k,g)$
3. Graphes sans cycles courts :
   • Eze et al. (2026) : Graphes $(k,g,g+1)$ et leur lien avec le problème des cages

Avantages de cet article

1. Cadre systématisé : Traitement unifié du problème des cages et de plusieurs variantes
2. Algorithmes complémentaires : Quatre méthodes couvrant différentes échelles et caractéristiques
3. Améliorations substantielles : Rupture de plusieurs records de longue date
4. Ressources ouvertes : Code et données complètement publics

Conclusions et discussion

Conclusions principales

1. Percées dans le problème classique des cages :
   • 11 nouvelles bornes supérieures, avec $(4,10)$ montrant l'amélioration la plus remarquable (384→320)
   • Premières améliorations de certaines bornes après 22 ans
   • Premières bornes non triviales pour $(4,11)$ et $(6,11)$
2. Progrès sur les problèmes variantes :
   • Graphes réguliers de circonférence d'arête/sommet : 50 nouvelles bornes (9 bornes serrées)
   • Spectre $(k,g)$ : 34 ordres nouvellement déterminés
   • Graphes sans cycles $(g+1)$ : 6 bornes améliorées
3. Contributions méthodologiques :
   • Cadre algorithmique systématisé basé sur les relèvements
   • Règles d'exclusion structurées et basées sur l'assignation
   • Combinaison efficace de méthodes heuristiques et exhaustives

Limitations

1. Complexité computationnelle :
   • Paramètres $(k,g)$ plus grands restent difficiles à traiter
   • Nécessite d'importantes ressources computationnelles (5 années-CPU)
   • Les méthodes heuristiques ne garantissent pas la solution optimale
2. Portée des méthodes :
   • Les méthodes de relèvement dépendent de l'existence de graphes de base et groupes appropriés
   • La technique de suppression nécessite des graphes connus de grande taille comme point de départ
   • Certaines paires de paramètres n'ont pas d'amélioration (comme les cages connues $(3,9)$, $(4,7)$, etc.)
3. Lacunes théoriques :
   • L'écart entre bornes inférieure et supérieure reste important dans la plupart des cas
   • Aucune amélioration de borne inférieure n'est fournie
   • Pour certains paramètres, la borne supérieure reste marquée "?" (inconnue)
4. Sensibilité aux hyperparamètres :
   • Les limites de temps, la taille de la liste tabou, etc. nécessitent un ajustement empirique
   • Aucune étude systématique d'optimisation des hyperparamètres n'est menée

Directions futures

1. Directions théoriques :
   • Dériver des familles infinies à partir des nouvelles constructions
   • Améliorer la borne de Moore et ses variantes
   • Prouver ou réfuter la conjecture de bipartition pour les cages de circonférence paire
2. Améliorations algorithmiques :
   • Développer des algorithmes plus efficaces pour le calcul de circonférence
   • Explorer la conception heuristique assistée par apprentissage automatique
   • Paralléliser les algorithmes pour exploiter les architectures multi-cœurs modernes
3. Généralisation de la technique de suppression :
   • Systématiser la stratégie de sélection des ensembles de suppression
   • Généraliser à plus de paires de paramètres $(k,g)$
   • Analyse théorique de l'efficacité de la méthode de suppression
4. Exploration d'applications :
   • Appliquer les graphes nouvellement découverts à la conception de réseaux
   • Explorer les applications dans les codes correcteurs d'erreurs
   • Étudier les propriétés cryptographiques connexes

Évaluation approfondie

Points forts

1. Contributions empiriques majeures :
   • Rupture de plusieurs records maintenus pendant 22 ans, en particulier l'amélioration significative de $(4,10)$
   • Fourniture de nombreuses constructions concrètes, servant de matériel pour la recherche théorique
   • Premières bornes non triviales pour certains paramètres
2. Innovations méthodologiques :
   • Règles d'exclusion systématisées : Les exclusions structurées et basées sur l'assignation réduisent significativement l'espace de recherche
   • Complémentarité algorithmique : BTA, TS, recherche ascendante et suppression couvrent différents scénarios
   • Vérification incrémentale : La vérification incrémentale de circonférence de l'Algorithme 2 améliore l'efficacité
   • Vérification de canonicité : Utilisation de la symétrie pour éviter les calculs redondants
3. Conception expérimentale rigoureuse :
   • Stratégie de vérification multi-niveaux (entrée, optimisation, exhaustivité)
   • Comparaison avec trois implémentations indépendantes
   • Description détaillée des configurations d'hyperparamètres
   • Support complet de la reproductibilité
4. Largeur de la recherche :
   • Non seulement focus sur le problème classique, mais étude systématique de quatre variantes
   • Établissement des premières bornes pour plusieurs variantes
   • Cadre unifié traitant différents problèmes
5. Pratiques de science ouverte :
   • Code et données complètement publics (GitHub)
   • Graphes archivés dans la base de données House of Graphs
   • Certificats vérifiables fournis (graphes construits)

Insuffisances

1. Profondeur théorique limitée :
   • Principalement un travail computationnel/empirique, manquant d'insights théoriques profonds
   • Aucune amélioration de borne inférieure ou analyse théorique fournie
   • Manque d'explication théorique sur pourquoi certains paramètres montrent des améliorations significatives
2. Complétude des méthodes :
   • Les méthodes heuristiques (TS, recherche ascendante) n'offrent aucune garantie de complétude
   • La sélection des hyperparamètres repose sur l'expérience, manquant d'étude systématique
   • Aucune analyse des garanties théoriques ou convergence des différents algorithmes
3. Détails du rapport expérimental :
   • Aucun rapport sur la contribution spécifique de chaque algorithme aux différentes améliorations
   • Manque d'analyse détaillée des temps d'exécution
   • Absence de discussion sur les cas d'échec ou instances difficiles
4. Problèmes de scalabilité :
   • La faisabilité des méthodes pour $k$ et $g$ plus grands n'est pas claire
   • La loi de croissance des besoins en ressources computationnels en fonction des paramètres n'est pas analysée
   • Certains résultats marqués "≥100" indiquent une exploration incomplète
5. Organisation de la rédaction :
   • Détails techniques denses, lisibilité difficile pour les non-spécialistes
   • Certaines descriptions d'algorithmes (comme le pseudocode de l'Algorithme 4 manquant) sont incomplètes
   • Nombreux tableaux de résultats mais manque d'analyse synthétique unifiée

Impact

1. Impact académique :
   • Élevé : Le problème des cages est un problème classique de la théorie extrémale des graphes, l'amélioration de records de longue date a une importance significative
   • Fournit des voies de recherche indirectes pour des problèmes ouverts célèbres comme le graphe de Moore 57
   • Les méthodes peuvent être généralisées à d'autres problèmes de graphes extrémaux
2. Valeur pratique :
   • Modérée : Les nouveaux graphes peuvent être utilisés dans la conception de topologies de réseau, codes correcteurs d'erreurs
   • Les outils open-source peuvent être utilisés par d'autres chercheurs
   • Le cadre algorithmique s'applique à d'autres problèmes d'optimisation combinatoire connexes
3. Reproductibilité :
   • Excellente : Code et données complets publiquement disponibles
   • Les stratégies de vérification détaillées renforcent la crédibilité
   • Les constructions concrètes peuvent être vérifiées indépendamment
4. Potentiel de recherche ultérieure :
   • Les nouvelles constructions peuvent inspirer la découverte de familles infinies
   • Le cadre algorithmique peut s'appliquer à d'autres problèmes de génération de graphes
   • Les premiers résultats sur les problèmes variantes ouvrent de nouvelles directions de recherche

Scénarios d'application

1. Applications directes :
   • Conception de réseaux nécessitant des petits graphes réguliers de haute circonférence
   • Construction de codes LDPC et autres codes correcteurs d'erreurs
   • Applications cryptographiques comme le partage de clés
2. Outils de recherche :
   • Expériences computationnelles en théorie extrémale des graphes
   • Tests pour les algorithmes d'isomorphisme de graphes et de canonicalisation
   • Tests de référence pour les heuristiques d'optimisation combinatoire
3. Ressources pédagogiques :
   • Démonstration de l'application des méthodes computationnelles aux mathématiques pures
   • Étude de cas en conception et optimisation d'algorithmes
   • Exemple de pratiques de science ouverte et de recherche reproductible
4. Domaines d'extension :
   • Autres problèmes de graphes extrémaux (nombres de Ramsey, problèmes de Turán, etc.)
   • Problèmes de satisfaction de contraintes
   • Théorie du design combinatoire et théorie du codage

Références (sélection)

1. Théorie fondamentale :
   • 45 Sachs (1963) : Preuve de l'existence de graphes $(k,g)$ pour tous $k \geq 2, g \geq 3$
   • 31 Gross & Tucker (1987) : Théorie topologique des graphes et théorie des relèvements
   • 47 Wong (1982) : Synthèse complète sur les cages
2. Méthodes computationnelles :
   • 24 Exoo et al. (2011) : Détermination computationnelle des cages $(3,11)$ et $(4,7)$
   • 38 McKay et al. (1998) : Principes du retour arrière rapide
   • 15 de Ruiter & Biggs (2015) : Méthodes de programmation entière
3. Progrès récents :
   • 22 Exoo & Jajcay (2011) : Théorie de la circonférence pour les relèvements de graphes de tension
   • 29 Goedgebeur & Jooken (2025) : Génération exhaustive de graphes réguliers de circonférence d'arête
   • 34 Jajcay et al. (2024) : Graphes réguliers de circonférence de sommet
4. Outils :
   • 37 McKay & Piperno (2014) : Logiciel d'isomorphisme de graphes Nauty
   • 27 Système GAP : Calcul en théorie des groupes
   • 12 House of Graphs : Base de données de graphes

Évaluation globale : Ceci est un article de haute qualité en mathématiques combinatoires computationnelles qui, par le développement systématique d'algorithmes et des expériences computationnelles à grande échelle, réalise des progrès empiriques significatifs sur le problème classique des cages et ses variantes. Les innovations méthodologiques (en particulier les règles d'exclusion structurées et la complémentarité algorithmique) et la stratégie de vérification rigoureuse constituent les points forts majeurs. Bien que la profondeur théorique soit limitée, les contributions empiriques, les pratiques de science ouverte et l'impact sur le domaine en font une contribution importante. Pour les chercheurs travaillant en théorie extrémale des graphes, algorithmes de graphes ou optimisation combinatoire, cet article fournit des méthodes et des ressources précieuses.