*   Domaine de compétence Optimisation Combinatoire   *

logo Leibniz logo Imag logo GDR Alp

FONCTIONS BOOLÉENNES, GRAPHES ET HYPERGRAPHES, SYSTÈMES FORMELS : JOURNÉE SCIENTIFIQUE ET AMICALE EN L'HONNEUR DE CLAUDE BENZAKEN

Grenoble, vendredi 6 septembre 2002

à l'INPG, Institut National Polytechnique de Grenoble
Amphithéâtre Gosse
46 avenue Félix Viallet, 38031 Grenoble


Objectifs de la journée - Programme
Quelques photos de la journée
Texte biographique sur Claude Benzaken présenté par Pierre Jullien


 

Objectifs de la journée

Ce colloque d'une journée sera centré sur les thèmes mentionnés dans le titre, thèmes chers à notre collègue Claude Benzaken. Nous proposons ainsi de marquer d'une pierre blanche la carrière de Claude grâce à la tenue d'une réunion scientifique en son honneur. La journée se terminera par une réception ouverte également à tous les amis et anciens collègues de Claude.

Photo de Claude

Claude Benzaken fait partie des pionniers de l'IMAG. Sous sa direction bienveillante, les mathématiques discrètes et l'informatique fondamentale se sont développées à Grenoble pendant la période cruciale des trente dernières années. Bien que retraité officiellement depuis quelques années, après avoir obtenu le titre de Professeur Émérite de l'Université Joseph Fourier, Claude continue son activité de recherche dans l'Institut IMAG. Nous souhaitons lui rendre hommage en lui dédiant cette journée.

Programme de la journée

9h25: Accueil des participants et introduction

9h30-10h: Odile Favaron
"Domination totale dans les graphes"
Dans un graphe simple G, un sous-ensemble D de sommets est un ensemble dominant total si tout élément de G a au moins un voisin dans D. Nous nous intéressons aux cardinalités minimum et maximum des ensembles dominants totaux minimaux. Nous donnons des propriétés relatives à ces paramètres, valables pour tous les graphes ou dans des classes particulières comme celles des graphes planaires ou des graphes sans griffe. Les résultats principaux sont des majorations faisant intervenir les degrés minimum ou maximum de G ou son diamètre.

10h-10h30: Jean Fonlupt
"Une nouvelle preuve d'un théorème de Boros et Gurvich sur les noyaux dans les graphes parfaits"
En 1995 Aharoni et Holzman ont donné une preuve très courte d'une conjecture de Berge et Duchet démontrée peu de temps avant par Boros et Gurvich : toute orientation "clique-acyclique" d'un graphe parfait a un noyau. Cette preuve est une application directe d'un théorème de Scarf apparu en 1967 dans la revue Econometrica. Dans la démonstration de ce théorème Scarf n'utilise aucune notion de théorie des graphes. Nous donnons ici une nouvelle preuve de ce résultat en raisonnant plus directement sur les structures des graphes parfaits.

10h30-11h: Pause

11h-11h45: Dominique de Werra
"Contraintes de parité dans les partitions eulériennes de graphes orientés"
Considering a variation of a transportation scheduling model, we start from a combinatorial extension of the Birkhoff-von Neumann theorem which consists in decomposing an integral matrix (with entries unrestricted in sign) into generalized permutation matrices. This corresponds to finding a Eulerian partition of the arc set of an oriented bipartite multigraph together with an appropriate coloring of its chains; we introduce some requirements on the parity of the chains and we show how to optimise the number of odd chains in the decomposition. This generalises the classical case of nonnegative integral matrices where all chains have length 1. Complexity of some balanced variations will be studied.

11h45-12h15: Maurice Pouzet
"Belordre et dénombrement de graphes"
Un belordre est un ordre - ou un préordre - sur un ensemble tel que toute suite infinie d'éléments de l'ensemble contienne forcément une sous-suite infinie croissante. A partir de l'article fondateur de Higman (1952) et de travaux indépendants, cette notion a diffusé, fournissant un paradigme à des questions d'algèbre, d'algorithmique, de logique et de combinatoire. D'importants résultats concernant la structure et les exemples d'ensembles belordonnés jalonnent ce développement. Dans le même temps, la notion de meilleurordre, renforcement de celle de belordre, introduite par Nash-Williams, permettait d'étendre à des structures infinies les propriétés de belordre de la comparaison des structures finies. Dans ce bref exposé, je présenterai l'intervention du belordre dans l'étude asymptotique du profil des relations. Le profil d'une structure relationnelle R est la fonction qui à chaque entier n associe le nombre de sous-structures de R ayant n éléments, celles-ci étant comptées à l'isomorphie près.
Le texte complet de ce résumé est disponible en format .ps ou .pdf.

12h15: Claude Benzaken

Déjeuner

14h-15h: Peter Hammer
"Analyse logique de données"
Un problème très fréquent en analyse de données admet une interprétation simple en termes de fonctions booléennes partiellement définies. Ces problèmes consistent essentiellement à rechercher une extension d'une fonction booléenne partiellement définie, satisfaisant certaines conditions. Dans cet exposé nous allons présenter certains des problèmes théoriques et algorithmiques apparaissant dans ce contexte, ainsi qu'une série d'applications à des problèmes concrets, en particulier concernant certaines études biomédicales récentes.

15h-15h15: Pause

15h15-16h: Yves Crama
"Fonctions booléennes : Morceaux choisis"
Cette présentation consistera en un bref survol de l'état de l'art concernant l'étude des fonctions booléennes, dans le but de mettre en évidence certains des progrès les plus remarquables obtenus dans les 20 dernières années et d'identifier d'intéressantes questions ouvertes. On y passera notamment en revue des questions liées à la complexité de la dualisation des fonctions monotones, à l'orthogonalisation des formes disjonctives normales et à la reconnaissance des fonctions booléennes à seuil.

16h-16h20: Nadia Brauner et Charles Payan
Présentation et exemple d'application du logiciel booléen créé par Claude Benzaken

16h20-16h40: Pierre Jullien
"Trous de serrure"
En écoutant Claude Benzaken, on ne s'ennuie jamais ; ne serait-ce que le spectacle ! Il n'en va pas de même avec tous les orateurs. Qui, honnêtement, parmi vous ne s'est jamais ennuyé en écoutant un exposé de mathématiques ?
Toujours est-il qu'il m'est arrivé de m'ennuyer. Que faire alors si on n'a pas pris la précaution de se mettre près de la sortie pour s'éclipser en douce, ou si la sortie est juste derrière le conférencier ? Personnellement je gribouille et gamberge. J'élucubre (toujours discrètement, ça va de soi !). Voici un résultat de mes élucubrations...
Le texte complet de ce résumé est disponible en format .ps ou .pdf.

Pierre Jullien fera ensuite un petit exposé biographique sur Claude Benzaken.

16h45: Réception et clôture


Organisateurs :
  • Myriam Preissmann,
  • Frédéric Maffray,
Laboratoire Leibniz-IMAG, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France