On the additive graph generated by a subset of the natural numbers

by Costain, Gregory

\'{E}tant donn\'{e} un sous-ensemble $S$ de $\{3,4,\ldots,2n-1\}$, le graphe additif engendr\'{e} par $S$ a un ensemble de sommets $V=[n]$ et un ensemble d'arr\^{e}tes $E$, telle que $(i,j) \in E$ si et seulement si $i+j \in S$. L'objectif de cette th\`{e}se est l'\'{e}tude des relations entre l'ensemble $S$ et les propri\'{e}t\'{e}s monotones du graphe additif correspondant. On effectue les premi\`{e}res recherches connue sur le \textit{Traversal By Prime Sum Problem}, probl\`{e}me dans lequel l'ensemble $S$ correspond \`{a} l'ensemble des nombres premiers et la propri\'{e}t\'{e} de graphe recherch\'{e}e est l'existence d'un cycle hamiltonien. De nouveaux r\'{e}sultats sont \'{e}tablis pour ce probl\`{e}me ainsi que dans le cas o\`{u} $S$ est l'ensemble des entiers pratiques.\\

Pour un tel $S$ quelconque, on d\'{e}montre que la $|S|$-fermeture du graphe additif engendr\'{e} par $S$ est un graphe complet. Ainsi, en utilisant les r\'{e}sultats de la th\'{e}orie de la fermeture on parvient \`{a} d\'{e}terminer le seuil pour plusieurs propri\'{e}t\'{e}s monotones des graphes en terme de $|S|$. Ces graphes sont les premiers repr\'{e}sentant connus d'une large sous-classe de graphe $k$-ferm\'{e}s complets. Ils permettent de donner une construction nouvelle et simple de graphe ferm\'{e}s et complets minimaux. Enfin, comme exemple d'interpr\'{e}tation arithm\'{e}tique de ces graphes et de leurs propri\'{e}t\'{e}s, on g\'{e}n\'{e}ralise un th\'{e}or\`{e}me de Cramer sur les nombres premiers \`{a} d'autres suites d'entiers.