Sös Vera T.

Imaginez deux rangées de points : une rangée de personnes et une rangée de lieux. Les traits relient seulement un point de la première rangée à un point de la seconde. Un graphe biparti de ce type devient très dense si beaucoup de traits sont présents. Le théorème de Kővári-Sós-Turán indique que, pour des tailles de parties et une configuration K_s,t fixées, l'absence de cette configuration impose une borne sur le nombre d'arêtes : elle dépend de la taille des deux parties et des paramètres s et t, et ne constitue pas un plafond universel. Cette idée relie une forme visible du réseau à une propriété générale de sa structure.

Le théorème de Kővári-Sós-Turán concerne un graphe biparti, c'est-à-dire un graphe dont les sommets sont répartis en deux parties et dont chaque arête relie un sommet d'une partie à un sommet de l'autre. Il étudie le nombre d'arêtes possible lorsque le graphe ne contient pas un sous-graphe complet biparti K_s,t. Ici, s et t désignent les nombres de sommets dans les deux parties de cette configuration complète : chacun des s sommets serait relié à chacun des t autres sommets. Le théorème fournit alors une borne supérieure sur le nombre total d'arêtes du graphe. Ainsi, l'absence d'une configuration locale impose une contrainte globale sur la densité du réseau.

La configuration interdite dépend du choix de s et de t. Modifier ces deux paramètres modifie donc la borne et la question combinatoire étudiée. Le résultat ne s'applique pas à un graphe quelconque sans préciser une séparation en deux parties ni la configuration complète recherchée. Née en 1930, Vera T. Sós a travaillé en théorie des nombres et en théorie des graphes ; le théorème de Kővári-Sós-Turán est une contribution particulière de son parcours dans ce second domaine.

Considérons deux parties de sommets, A = {a, b} et B = {1, 2}. On cherche à reconnaître la configuration complète bipartie correspondant à s = 2 et t = 2.

Les données sont les suivantes : A contient a et b ; B contient 1 et 2 ; les arêtes possibles vont de A vers B.

On vérifie l'arête a–1.
On vérifie l'arête a–2.
On vérifie l'arête b–1.
On vérifie l'arête b–2.

Les quatre liaisons entre les deux parties sont présentes. Le sous-graphe obtenu est donc un K_2,2, car chaque sommet de A est relié à chaque sommet de B. Un graphe qui interdit cette configuration ne peut pas contenir simultanément ces quatre arêtes dans deux parties de deux sommets. La figure associée rend visibles les deux parties et les quatre liaisons à contrôler.

En théorie des graphes, le résultat sert à estimer combien d'arêtes un réseau biparti peut posséder lorsqu'une configuration complète donnée doit être absente. Le geste consiste à fixer les deux tailles s et t, puis à rechercher les sous-graphes K_s,t.

Pour étudier un réseau réel séparé en deux catégories, cette approche fournit un point de comparaison structurel. Si le réseau contient la configuration recherchée, il faut abandonner l'hypothèse d'absence et employer une analyse qui l'autorise. Si elle est absente, la borne du théorème aide à repérer si le nombre d'arêtes reste compatible avec cette contrainte.

Un graphe biparti n'est pas nécessairement un graphe complet biparti. Le premier impose seulement que les arêtes relient les deux parties ; le second exige que toutes les liaisons entre ces parties soient présentes. Le cas A = {a, b}, B = {1, 2} tranche immédiatement : avec une seule arête manquante, le graphe reste biparti mais ne contient plus ce K_2,2 complet.

Le théorème de Kővári-Sós-Turán ne dit pas que tout graphe biparti possède peu d'arêtes. Il donne une borne sous l'hypothèse testable qu'une configuration complète K_s,t est absente. Sans cette hypothèse, la conclusion ne peut pas être appliquée.

Le choix de s et de t n'est pas un détail de notation. Il fixe la configuration complète interdite et donc la borne obtenue. Un raisonnement qui change K_2,2 en K_2,3 en cours de route ne porte plus sur le même cas. Il faut conserver les deux paramètres pendant toute l'analyse.

Le mot « biparti » impose aussi une partition précise. Une arête reliant deux sommets de la même partie signale que le modèle retenu n'est pas celui du théorème. Il faut alors redéfinir les parties ou utiliser un résultat adapté à un graphe non biparti.

Enfin, une borne sur le nombre d'arêtes ne décrit pas à elle seule la forme du graphe. Deux graphes peuvent avoir autant d'arêtes tout en répartissant ces arêtes très différemment. La conclusion porte sur une quantité globale sous une contrainte de sous-graphe, pas sur l'unicité du réseau.

Le théorème s'inscrit dans la théorie des graphes extrémaux : cette branche cherche jusqu'où une structure peut être dense tout en évitant une configuration donnée. Le cas biparti permet d'observer clairement le passage d'une interdiction locale, l'absence d'un K_s,t, à une borne globale sur les arêtes. Cette perspective prépare l'étude d'autres problèmes où l'on compare densité et sous-structures interdites.