Réunion Mardi 29 Avril 2014

Mardi 29 avril à Jussieu
salle B202, bâtiment de la pédagogie

- 10h30 F. Peschanski (LIP6)
“Parallélisme et Combinatoire”

11h45  Discussion autour des tâches du projet

12h30  Buffet –

13h45  Andrea Sportiello (LIPN) TBA

15h Olivier Bodini (LIPN) TBA

Posted in Accueil | Leave a comment

Réunion Jeudi 16 janvier 2014

Réunion de l’ANR MAGNUM

Jeudi 16 janvier 2014

LIPN – Salle B107
Institut Galilée  Université Paris 13

Comment venir ? http://www-lipn.univ-paris13.fr/planfac/?lang=fr

10h30 Elie de Panafieu (LIAFA)
“Transition de phase dans les hypergraphes aléatoires”

11h45  Discussion autour des  modèles combinatoires complexes
(Non-uniformité, objets combinatoires contraints ou corrélés,
propriétés structurelles, génération aléatoires)

12h15  Buffet — salle A201

13h45  Julien Salez (LPMA)
“La convergence locale faible : un cadre pour l’étude des grands graphes.”

15h Robert Cori (LaBRI)
“Calcul des rangs de configurations sur le graphe complet”

16h15 Discussion et goûter

Posted in Accueil | Leave a comment

Réunion du 7 Novembre 2013 (LIAFA)

La première réunion Magnum de la saison 2013-2014 aura lieu le

Jeudi 7 novembre au LIAFA autour du thème:

“Systèmes dynamiques discrets, simulation, génération aléatoire”

Matin : Amphi Turing (sous-sol du bâtiment Sophie Germain).
Après-midi : Amphi Turing .

Programme:
^^^^^^^^

10.00 – 10.30 : accueil croissant
10-30 -11.30 : Thomas Fernique – Chaîne de Markov sur les pavages : du chaos à l’ordre
11.30 – 12.00 : infos Magnum et discussion
———–
12.00-14.00 : déjeuner a la “cantine”
———–
14.00 – 15.00 : Inès Klimann – Génération aléatoire de groupes: une piste du côté des automates?
15.00 -15.30 : pause
15.30 -16.00 : Sébastien Labbe et Thierry Monteil – Simulation d’orbites generiques pour l’application de Gauss
16.00 – 16.30 : Valérie Berthe – Dynamique Pisot S-adique

Posted in Accueil | Leave a comment

Réunion du du 13 Juin au LIPN

Jeudi 13 Juin aura lieu une rencontre de l’ANR Magnum à Villetaneuse au LIPN salle B107. Au programme, 4 exposés :

  • 10H30 : Aline Parreau (LIFL) : Une preuve combinatoire du Lemme local de Lovasz
  • 11h45 Julien David (LIPN) & Yann Ponty (LIX) (slides)
    présentation de RDos — Random Discrete Objects Suite –
    un ensemble d’outils pour la génération aléatoire d’objets combinatoires
  • 14h Mathieu Raffinot (LIAFA)
    Nouvelles avancées dans la recherche de motifs uniques ou consécutifs dans des permutations
    travail en commun avec D.l Belazzougui (Univ. of Helsinki), A. Pierrot (LIAFA) et S. Vialette (LIGM)
  • 15h15 Axel Bacher (LIPN)
    Génération aléatoire d’arbres en taille exacte et linéaire en temps et en espace
    - version revue, corrigée et clarifiée -

Pour en savoir plus, rendez vous sur la page des exposés.

Posted in Accueil | Leave a comment

Réunion du 24 Janvier 2013

Jeudi 24 Janvier 2013
à Jussieu, Salle 211 (55-65)

———————————————-
Programme

10h30 Xavier Goaoc (Loria)
“Simplifying inclusion-exclusion formulas”

The classical inclusion-exclusion formula expresses the measure of
the union of a family of $n$ sets using the measures of the
intersections of subfamilies. The number of terms in this formula is
exponential in $n$, and a significant amount of research, originating
in applied areas, has been devoted to constructing simpler formulas
for particular families (e.g. sets of balls or halfspaces).

We provide the apparently first upper bound valid for an arbitrary
family: we show that every system of $n$ sets with $m$ nonempty fields
in the Venn diagram admits an inclusion-exclusion formula with
$m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a
formula can be computed in $m^{O(\log^2n)}$ expected time.

This is joint work with J. Matousek, Pavel Patak, Zuzana Safernova and
Martin Tancer.

http://arxiv.org/abs/1207.2591

11h45 Buffet

14h — 18h Discussions et Groupes de travail

Posted in Accueil | Leave a comment

Réunion du 29 Novembre 2012

10h30 Brigitte Vallée (GREYC)
Analyse des arbres digitaux de recherche (DST) sous le modèle d’une source générale.

11h45 Discussion

12h30 Buffet — en commun avec l’ANR COMPLICE — salle A201

14h Alice Jacquot (LIPN)
Génération aléatoire d’arbres de Motzkin en taille exacte et temps linéaire via générateur de Boltzmann et spécification holonome.

15h30 Nick Beaton – post-doc MAGNUM au LIPN
Three approaches to polymer adsorption

————–
16h30 Discussion (suite et fin)

Posted in Accueil | Leave a comment

Réunion ANR Magnum Jeudi 4 Octobre 2012

- 10h exposé Julien David
- 11h discussion sur la plate forme logicielle et des journées sage et programme à venir
- 12h30 buffet
-14h30 exposé Anne Micheli
- 15h30 session ouverte de questions et discussions
—————
“Une étude en moyenne des hypergraphes et de leur transversaux minimaux”
J. David (en collaboration avec L. Lhote, A. Mary, F. Rioult)

Résumé:
“Dans cet exposé, on s’intéressera à certaines propriétés des hypergraphes
et à la complexité moyenne d’algorithmes appliqués aux hypergraphes sous
plusieurs modèles de probabilité.
Notre approche est à la fois théorique et expérimentale puisque notre objectif
est d’obtenir un modèle aléatoire capable de capturer la complexité de données
réelles.

Partant d’un modèle généralisant celui d’Erdös-Renyi, nous avons obtenus
des estimations asymptotiques sur le nombres de transversaux, de minimaux
et de transversaux minimaux d’un hypergraphe aléatoire.
On utilise ces résultats pour obtenir la complexité moyenne des algorithmes
de génération des transversaux minimaux d’un hypergraphe.

Dans un deuxième temps, on complexifie notre modèle aléatoire afin
de s’approcher de données réelles.
Les résultats obtenus sont moins précis mais nous avons pu identifier
des cas où le nombre de transversaux minimaux est au plus polynomial,
quasi-polynomial ou exponentiel.

L’exposé se terminera par des réflexions personnelles et encore
inachevées sur les questions de génération aléatoire et d’analyse
pour des modèles non-uniformes.”

————

Minimiser les tresses à 4 brins
Anne Micheli – LIAFA

Une tresse à n brins correspond à l’idée intuitive que l’on se fait d’une tresse, c’est-à-dire n brins dont les extrémités sont fixes et qui se croisent entre
eux. Les tresses forment un groupe, noté Bn, engendré par n-1 générateurs vérifiant des relations. Une tresse peut être représentée par un diagramme de
tresse, c’est-à-dire une suite de croisements entre les brins de la tresse, chaque générateur correspondant à un croisement de deux brins. Ainsi un
représentant de longueur minimale d’une tresse est un diagramme parmi les diagrammes représentant la tresse, dont le nombre de croisements est minimal. Le
problème de minimisation d’une tresse consiste à exhiber un tel représentant de la tresse ou au moins à calculer sa longueur. Lorsque les tresses sont
positives, on connait leur série génératrice qui est rationnelle. Dans B3, il existe des algorithmes polynomiaux pour résoudre le problème de
minimisation. Mais pour n>3, aucun algorithme polynomial n’est connu à ce jour. On sait par contre que le problème est NP-complet pour n quelconque. Je
présenterai un algorithme polynomial pour résoudre le problème dans B4 dont la correction est prouvée moyennant une conjecture très simplement énonçable.
Ce travail a été effectué en collaboration avec Jean Mairesse (LIAFA) et Dominique Poulalhon (LIX).

Posted in Accueil, Conférences | Leave a comment

Réunion ANR Magnum 11 Juillet

mercredi 11 juillet 2012 au LIP6, Jussieu, salle 101, 25-26

  • 10h30 : Nicolas Schabanel (LIAFA)
    Universality in Stochastic Cellular Automata
  • 14h00 : Axel Bacher (LIX)
    TBA
Posted in Accueil, Conférences | Leave a comment

Réunion ANR Magnum du 10 Mai

Réunion du Jeudi 10 Mai 2012

  • 10H 30 : Ana Busic : Autour de la simulation parfaite
  • 14h Jeremie Lumbroso : Autour des machines de Buffon
Posted in Accueil, Conférences | Leave a comment

Réunion ANR Magnum 15 Mars 2012

Chevaleret, salle 1D06, LIAFA

10H30 : Guglielmo Paoletti
“Strings and Patches in the Abelian Sandpile Model”
Abstract:

The Abelian Sandpile Model is a simple cellular automaton describing the dynamics of a pile of sand under particle’s addition, which has also been studied under the name of Chip-Firing Game; it presents Self Organized Criticality and seems to display allometry. Here I will show the emergence of 2-dimensional periodic patterns (patches) and 1-dimensional periodic defects (strings). I will present the classification of these objects and the relation between their densities and respective periodicity vector, momentum, reminiscent of a dispersion relation. Strings interact, they can merge and split. In the understanding of the whole structure SL(2,Z) plays a key role, finally bringing to the full determination of particular self-similar Structures.

13H30 : Markus Nebel : Generation Aléatoire Non Uniforme
Abstract:

The random generation of combinatorial objects is useful in many places in
computer science, e.g. in the random testing of programs or for the
estimation of the average case runtime of algorithms that elude a
mathematical analysis. In the Bioinformatics area, random sequences are a
topic of great interest e.g. in genome analysis, since according to a
powerful paradigm, they represent the background noise from which the actual
biological information must differentiate.
However, in many applications the random generation should follow the native
distribution of the objects considered.
In this talk we will show how stochastic context-free grammars can be used
for the random generation of combinatorial objects according to non-uniform
distributions derived from sample data. We will see that both, a fixed size
sampling as well as the more efficient Boltzmann sampling can be performed
on basis of those grammars.

Posted in Accueil, Conférences | Leave a comment