RAMSEY THÉORÈME DE

COMBINATOIRE ANALYSE

  • Écrit par 
  • Dominique FOATA
  •  • 5 830 mots
  •  • 2 médias

Dans le chapitre « Théorèmes d'existence »  : […] Le théorème de Ramsey et celui de Hall-König, dont nous donnons les énoncés maintenant, jouent un rôle spécial en combinatoire. Ils assurent l'existence de certaines configurations dans des conditions très générales et ont ainsi trouvé de nombreuses applications. Supposons que l'on ait un graphe de six sommets, dans lequel deux sommets distincts sont joints par une arête « coloriée » en bleu ou en […] Lire la suite

ERDÖS PAUL (1913-1996)

  • Écrit par 
  • Jean-Louis NICOLAS
  •  • 966 mots

Mathématicien brillant et hors du commun, lauréat du prix Wolf en 1983. Né le 26 mars 1913 à Budapest et décédé le 20 septembre 1996 à Varsovie, Paul Erdös fut un enfant prodige et, à l'âge de quatre ans, il savait déjà compter avec des nombres de trois chiffres et avait redécouvert les nombres négatifs. Il fut élevé par ses parents, professeurs de mathématiques, comme un fils unique, ses deux sœu […] Lire la suite

MODÈLES THÉORIE DES

  • Écrit par 
  • Daniel ANDLER, 
  • Daniel LASCAR, 
  • Gabriel SABBAGH
  •  • 7 958 mots

Dans le chapitre « Indiscernables »  : […] Ehrenfeucht et Mostowski ont dégagé la notion centrale d' ensemble ordonné indiscernable  I dans une structure  a  : I est une partie totalement ordonnée de A (l'ordre n'étant pas nécessairement définissable dans a ) dont, pour chaque n , tous les n -uples strictement croissants ont le même n -type ; autrement dit, si i 1  <   ...  <   i n et i ′ 1   <  ...  […] Lire la suite

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Complexité »  : […] Un programme de calcul x d'une semi-fonction récursive f  = ϕ( x ) étant donné, où ϕ : N  → *F R (1) est l'énumération universelle définie dans le chapitre précédent, on peut effectuer deux types de mesures. La première consiste, par exemple, à mesurer le nombre d'instructions d'un certain type de ce programme  x . On définit ainsi une application m  : N  →  N en désignant par m ( x ) le nombre […] Lire la suite