Recherche · Théorie extrémale des graphes · ex(50 ; C4)

ex(50 ; C4) : un graphe à 50 sommets et 181 arêtes sans 4-cycle

Cette page présente un travail de recherche en théorie extrémale des graphes : un graphe à 50 sommets et 181 arêtes qui ne contient aucun cycle de longueur 4, donc ex(50 ; C4) ≥ 181. Elle montre l’énoncé exact, le paysage des valeurs publiques avec leurs sources, puis le graphe en entier, avec un programme court que chacun exécute pour le revérifier.

1. Le problème

Un graphe est sans 4-cycle (« C4-free ») s’il ne contient aucun cycle de longueur quatre. De façon équivalente, et c’est la forme que le contrôle du tableau utilise, deux sommets distincts n’ont jamais deux voisins communs ou plus. Le nombre ex(n ; C4) est le plus grand nombre d’arêtes d’un graphe sans 4-cycle à n sommets.

L’énoncé du tableau, en anglais : « Find a C4-free graph on exactly 50 vertices with more than 179 edges. » Soit : un graphe sur exactement 50 sommets, numérotés de 0 à 49, sans 4-cycle, avec plus de 179 arêtes, sans boucle ni arête répétée. Source : github.com/math-market/c4-free-50, fichier TASK.md, lu le 13/10/2026 ; le contrôle (check.py) est publié dans le même dépôt, sous licence Apache-2.0.

Un graphe sans 4-cycle peut contenir des triangles. Le schéma montre à gauche un graphe de 7 sommets et 9 arêtes (trois triangles qui partagent un sommet) : il n’a aucun 4-cycle, et 9 est le maximum possible à 7 sommets (ex(7 ; C4) = 9, OEIS A006855). À droite, une arête de plus ferme un 4-cycle : le sommet c et le sommet 2 ont alors deux voisins communs.

2. Le paysage public

Le tableau réunit les nombres publics autour de n = 50, avec leur source et leur date de lecture. Ce sont les repères du problème : ils situent les valeurs connues et ne disent rien de la façon dont un graphe est atteint.

Lectures du 13/10/2026 : tableau math-market/c4-free-50 (README, TASK.md, baseline.json), OEIS A006855, page de B. McKay et N. Afzaly. Les majorants de l’OEIS pour n = 48 et n = 49 (176 et 182) sont égaux à la borne de Reiman recalculée à ces valeurs de n.

L’OEIS (suite A006855) donne ex(n ; C4) pour n de 1 à 40, avec a(40) = 127 ; pour n de 41 à 49 il ne donne que des encadrements, par exemple 174 ≤ a(49) ≤ 182 ; pour n = 50 il ne donne ni valeur ni borne. La page de B. McKay et N. Afzaly liste des graphes jusqu’à n = 49. Le tableau fixe le seuil à 179 et le plafond à 187, et note que le maximum n’est, à sa connaissance, pas publié.

Aux lectures du 13/10/2026, 181 est la plus grande valeur publiée pour n = 50 dans les sources citées ci-dessus (l’OEIS ne donne aucune valeur ni borne pour n = 50). Ce n’est pas la valeur exacte de ex(50 ; C4) : avec la borne de Reiman, elle est comprise entre 181 et 187.

3. Le résultat

Le graphe a 50 sommets, numérotés de 0 à 49, et 181 arêtes. Ses degrés valent 7 ou 8 : 38 sommets de degré 7 et 12 sommets de degré 8 (somme des degrés 362 = 2 × 181). Il ne contient aucun 4-cycle, donc ex(50 ; C4) ≥ 181.

Les 181 arêtes sont publiées en entier. Le fichier au format du tableau est c4free_n50_181.json ; le même graphe est donné ci-dessous en liste d’adjacence, intégrée au programme de revérification.

Les vérifications

Quatre contrôles, rejoués le 13/10/2026 sur le fichier du graphe :

Sortie du juge du tableau sur le graphe :

valid: C4-free graph on 50 vertices with 181 edges
ACCEPTED: 181 > 179 — this improves on the published baseline

Sortie du juge sur le graphe auquel l’arête (0, 4) est ajoutée :

REJECTED: vertices 0 and 3 have common neighbours 4 and 10 — that is a 4-cycle 0-4-3-10-0

Revérifier soi-même

Le programme ci-dessous contient le graphe. Il suffit de l’enregistrer dans un fichier verifier_c4.py et de lancer python verifier_c4.py : Python 3 suffit, sans aucune bibliothèque à installer. Chaque ligne de la liste commence par un sommet, suivi des voisins de numéro supérieur. Le programme recalcule le nombre d’arêtes et les degrés, applique deux contrôles de natures différentes, rejoue un canari (une arête qui crée un 4-cycle, que les deux contrôles doivent rejeter) et affiche l’empreinte du fichier JSON reconstruit, à comparer à celle de la section 3. Version enregistrable : verifier_c4_fr.py.

# verifier_c4.py : bibliothèque standard seule ; python verifier_c4.py
import hashlib, itertools, json
from collections import Counter

# le graphe : une ligne par sommet u, suivie des voisins de numéro supérieur à u (chaque arête figure une seule fois)
LISTE = """
0: 1 2 3 10 20 23 37
1: 2 6 8 25 29 45
2: 7 12 19 27 43
3: 4 5 10 24 31 44
4: 5 6 12 16 36 41 46
5: 7 9 22 29 47
6: 8 11 16 21 32
7: 9 11 27 30 42
8: 9 14 15 38 44 48
9: 18 20 33 34 38
10: 11 15 17 33 40 49
11: 13 21 35 40 42
12: 13 14 19 33 39 46
13: 14 18 25 31 35
14: 15 23 26 47
15: 17 28 30 36
16: 17 18 26 27 37
17: 18 19 22 45
18: 20 25 43
19: 21 22 24 38
20: 21 23 28 46
21: 24 28 47
22: 23 29 32 35 48
23: 26 32 41 42
24: 25 26 30 34 44
25: 29 30 41 49
26: 27 34 40
27: 28 31 48 49
28: 29 31 36 39
29: 39 40
30: 32 37 46
31: 32 38 45
32: 33 43
33: 34 39 49
34: 35 36 45
35: 36 37 48
36: 41 43
37: 38 39 47
38: 40 41
39: 42 44
40: 43 46
41: 42 49
42: 44 45
43: 44 47
44: 48
45: 46 47
46: 48
47: 49
48: 49
49:
"""
N = 50
E = [(int(l.split(":")[0]), int(w)) for l in LISTE.strip().splitlines() for w in l.split(":")[1].split()]
assert len(set(E)) == len(E) and all(0 <= u < v < N for u, v in E)
adj = [set() for _ in range(N)]
for u, v in E:
    adj[u].add(v); adj[v].add(u)

# contrôle 1 : aucun couple de sommets distincts n'a deux voisins communs ou plus
def sans_c4_paires(adj):
    return all(len(adj[u] & adj[v]) <= 1 for u, v in itertools.combinations(range(N), 2))

# contrôle 2, sans rapport avec le contrôle 1 : aucun des 3 cycles possibles sur chacun des 230 300 quadruplets de sommets n'est présent
def sans_c4_quadruplets(adj):
    for a, b, c, d in itertools.combinations(range(N), 4):
        for p, q, r, s in ((a, b, c, d), (a, b, d, c), (a, c, b, d)):
            if q in adj[p] and r in adj[q] and s in adj[r] and p in adj[s]:
                return False
    return True

# canari : une arête qui ferme un chemin de longueur 3 crée un 4-cycle ; les deux contrôles doivent la rejeter
def canari(adj):
    for u, v in itertools.combinations(range(N), 2):
        if v not in adj[u] and any(y in adj[x] for x in adj[u] for y in adj[v]):
            c = [set(a) for a in adj]; c[u].add(v); c[v].add(u)
            return (u, v), c

ok = lambda b: "aucun 4-cycle" if b else "4-CYCLE TROUVÉ"
deg = dict(sorted(Counter(len(a) for a in adj).items()))
print("sommets : %d ; arêtes : %d ; degrés (degré : nombre de sommets) : %s" % (N, len(E), deg))
r1, r2 = sans_c4_paires(adj), sans_c4_quadruplets(adj)
print("contrôle 1 (paires de sommets)  : %s" % ok(r1)); print("contrôle 2 (quadruplets de sommets) : %s" % ok(r2))
e, c = canari(adj)
k1, k2 = sans_c4_paires(c), sans_c4_quadruplets(c)
print("canari : arête ajoutée %s -> contrôle 1 : %s ; contrôle 2 : %s" % (e, "rejetée" if not k1 else "ACCEPTÉE (anormal)", "rejetée" if not k2 else "ACCEPTÉE (anormal)"))
print("empreinte sha256 du fichier JSON du graphe : %s" % hashlib.sha256(json.dumps({"n": N, "edges": [list(x) for x in E]}).encode()).hexdigest())
bon = len(E) == 181 and r1 and r2 and not k1 and not k2
print("VÉRIFIÉ : 50 sommets, 181 arêtes, sans 4-cycle ; le canari est rejeté par les deux contrôles" if bon else "ÉCHEC")
raise SystemExit(0 if bon else 1)

Ce programme a été exécuté le 13/10/2026 (Python 3.11.0rc2, python -I) sur le graphe publié. Sortie obtenue :

sommets : 50 ; arêtes : 181 ; degrés (degré : nombre de sommets) : {7: 38, 8: 12}
contrôle 1 (paires de sommets)  : aucun 4-cycle
contrôle 2 (quadruplets de sommets) : aucun 4-cycle
canari : arête ajoutée (0, 4) -> contrôle 1 : rejetée ; contrôle 2 : rejetée
empreinte sha256 du fichier JSON du graphe : 47e08a82f8af0a73d81eeb4e06c726a7495711b45d0cebef8bc10f6b05a6902d
VÉRIFIÉ : 50 sommets, 181 arêtes, sans 4-cycle ; le canari est rejeté par les deux contrôles

Les deux contrôles s’accordent avec le juge du tableau et avec networkx. L’empreinte reconstruite par le programme est celle du fichier de la pull request n° 6.

Empreintes sha256

Dépôt public

Le graphe est déposé sur le dépôt public du tableau : pull request n° 6 de math-market/c4-free-50, ouverte le 01/10/2026. Son fichier my_graph.json a la même empreinte sha256 que le fichier de cette page. État lu le 13/10/2026 : ouverte, non fusionnée, sans commentaire ni relecture. Le graphe est publié sous licence Apache-2.0, comme l’exige le tableau pour les soumissions. Le graphe de départ provient d’une page dont la licence n’est pas indiquée.

4. Ce que modélise cette question

Cette question relève de la théorie extrémale des graphes : combien d’arêtes un graphe à n sommets peut-il avoir sans contenir un sous-graphe donné, ici le cycle à quatre sommets ? Pour n grand, ex(n ; C4) est de l’ordre de n^3/2/2 : la borne de Reiman, (n/4)(1 + √(4n − 3)), est asymptotiquement exacte (Aigner et Ziegler, d’après l’OEIS).

Les graphes qui atteignent cet ordre viennent des géométries finies. Dans un plan projectif fini d’ordre q, qui compte q² + q + 1 points, on relie deux points lorsque l’un appartient à la droite polaire de l’autre : le graphe de polarité d’Erdős–Rényi n’a aucun 4-cycle, et pour q = 7 il a 57 sommets et 224 arêtes ; le tableau en tire son seuil de 179 en retirant 7 sommets. Füredi montre que, pour q > 13, ex(q² + q + 1 ; C4) ≤ q(q + 1)²/2, avec égalité exactement pour les graphes de polarité orthogonaux d’un plan d’ordre q (J. Combin. Theory B 68, 1996 ; énoncé repris dans l’introduction d’arXiv:1201.4912, lue le 13/10/2026), et Firke, Kosek, Nash et Williford démontrent une majoration de ex(q² + q ; C4) pour q pair (arXiv:1201.4912, lu le 13/10/2026). Pour une valeur de n comme 50, qui n’est pas de la forme q² + q + 1, la valeur exacte reste à établir : le paysage de la section 2 montre ce qui est connu.

Sources : github.com/math-market/c4-free-50 (README, TASK.md, check.py, baseline.json, pull request n° 6), oeis.org/A006855, users.cecs.anu.edu.au/~bdm/data/extremal.html, arXiv:1201.4912, lus le 13/10/2026.

Un programme de recherche, une épreuve extérieure

Ces résultats couvrent des domaines sans rapport entre eux : la géométrie des empilements (Packomania, Friedman Packing Center), la mécanique spatiale (ESA SpOC 4), la théorie des nombres (IBM Ponder This) et les graphes (FlyWire Codex). Dans chacun, le résultat est inscrit sur la page d’un tiers, table, classement ou liste, et se revérifie par calcul : l’ESA évalue chaque solution avec son simulateur, Packomania publie les entrées qu’il retient, IBM publie une liste de noms, Friedman tient une page qui crédite les auteurs. Ces résultats relèvent d’un même programme de recherche : ne retenir que ce qu’un certificat prouve.

Cette page applique le même principe à un problème de graphes : un résultat dont la liste complète est publiée, un programme court que chacun exécute, et le juge d’un tableau extérieur qui accepte le graphe. Ici, le lecteur revérifie lui-même.

Le principe est public : chaque hypothèse est testée par le calcul et n’est retenue que si un certificat la prouve. Des IA génératives me servent d’assistants, interchangeables : elles proposent, mon IA décide, le certificat tranche. Le fonctionnement interne reste confidentiel. Les résultats, eux, sont publics.

Le certificat change la nature de la preuve. Un résultat se vérifie sans faire confiance à celui qui l’a produit, comme une démonstration se vérifie sans connaître son auteur. C’est ce qui rend cette page possible : vous n’avez pas à me croire, vous revérifiez. Le résultat est figé par son empreinte, publiée.

Tout le travail tourne sur du matériel accessible : un PC de bureau, un Raspberry Pi 5 et un Raspberry Pi Pico, qui servent aussi à vérifier que le calcul reste identique d’une machine à l’autre ; ponctuellement, une instance de 32 processeurs virtuels. Le programme vise une IA embarquée certifiable, jusque sur des machines modestes.

Un résultat vérifiable sans confiance, figé, revérifiable : ces propriétés ouvrent sur les usages visés :

• l’IA embarquée certifiable, jusque sur des machines modestes ;
• le pilotage des IA génératives, dont on ne retient que ce qui est prouvé ;
• l’identité vérifiable des agents d’IA ;
• l’audit après incident : rejouer exactement une décision passée ;
• la science reproductible ;
• la carte ouverte des calculs certifiés : chaque résultat avec son certificat, pour ne pas recalculer ce qui est prouvé.

Le programme de recherche détaille ce cadre. Tous les résultats, avec leurs sources et leurs dates, sont réunis sur la page Résultats.