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
