La conjecture de partitionnement des chemins

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.

Construction des problèmes publics, controverse et action publique : santé publique et jeux de hasard et d'argent au Québec

Depuis la fin des années 1990, les jeux de hasard et d’argent (JHA) sèment régulièrement la controverse dans l’espace public québécois. En effet, au cours des dernières années, la question du management et de la régulation des JHA a pris une place de plus en plus importante dans les débats publics. Dans le cadre de cette thèse, qui prend la forme d’une thèse par articles, nous nous intéresserons au processus de construction du problème public que représente maintenant le jeu excessif au Québec. Pour ce faire, nous tracerons, dans un premier temps, la genèse de ce problème public en remontant à ses origines. Ce détour historique nous permettra de mettre en relief les diverses constructions par lesquelles l’action de s’adonner aux JHA et ce, de manière excessive ou non, est passée au cours du dernier siècle, soit de vice, à crime, à loisir en passant par maladie et problème de santé publique. Cette genèse nous permettra d’apporter un nouvel éclairage sur la présente controverse relative aux JHA au Québec. Nous tenterons, dans un premier temps, de mettre en relief comment la santé publique a réussi à construire ce « nouveau risque » que représente maintenant l’action de s’adonner aux JHA. Par la suite, nous tenterons de tirer des leçons pour la compréhension, l’analyse et le management des politiques publiques et ce, via une analyse de la controverse portant sur les JHA (article 1), un travail de reconceptualisation théorique (article 2) ainsi qu’une réflexion épistémologique sur des fondements de l’analyse et du management des politiques publiques (article 3).