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
