| Christine Bachoc | 7/12/2012 | Le nombre theta de Lovász : applications, généralisations, et
problèmes ouverts (I)
Nous ferons un petit tour d'horizon des applications en théorie des codes et en géométrie euclidienne du nombre theta de Lovász, une introduction à la hiérarchie de Lasserre des programmes SDP pour le nombre d'indépendance d'un graphe dont theta est le premier niveau, et nous présenterons quelques questions ouvertes. |
Salle 76, Labri, 14h15-15h15 |
| Christine Bachoc | 14/12/2012 | Le nombre theta de Lovász : applications, généralisations, et
problèmes ouverts (II)
Suite du précédent |
Salle 76, Labri, 15h15-16h15 |
| Philippe Jaming | 08/01/2013 | Problème de la phase dans le cadre discret
Nous étudirons le problème de reconstruire une fonction à partir du module de sa transformée de Fourier (discrète) et d'informations à priori sur la fonction. Par exemple, dans le cas où la fonction est la fonction caractéristique d'un ensemble A, on veut reconstruire A à partir de l'ensemble des différences A-A. |
Salle 385, IMB, 10h-11h |
| Paul Dorbec | 05/03/2013 | A propos de domination dans les graphes
Au cours de cet exposé, nous verrons les bases de la domination dans les graphes et quelques pistes de recherches actuelles. Nous parlerons en particulier de la conjecture de Vizing, de dominants parfaits (codes couvrants), et de différentes autre variantes de la domination. |
Salle 385, IMB, 10h-11h |
| Guillem Perarnau | 25/03/2013 | A probabilistic approach to consecutive pattern avoiding in permutations
We present a new approach based on the probabilistic method, for the problem of enumerating permutations of length n that avoid a fixed consecutive pattern of length m. We use this approach to give alternative and shorter proofs for some known results as well as to provide new results that have not been shown using other techniques. |
Salle 76, Labri, 11h-12h (dans le cadre du GT Proba-Info) |
| Florent Foucaud | 29/03/2013 | The complexity of signed graph homomorphisms
Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring (in relation with graph minors) or in the theory of flows. Recently, the notion of homomorphisms of signed graphs has been introduced by Bertrand Guenin and further developed by Reza Naserasr, Edita Rollova and Eric Sopena. It naturally extends the notion of homomorphisms for classical graphs to the case of signed graphs. We study the computational complexity of the H-signed colouring problem, i.e. the question of deciding whether a given signed graph admits a homomorphism to a fixed signed graph H. We settle all cases where H is a cycle, and discuss the restriction where the input graph is planar. We relate these questions to the state of the art for classical graph homomorphisms. This is joint work with Reza Naserasr. |
Salle 178, Labri, 15h15-16h15 |
| Gilles Zémor | 5/04/2013 | Une version dimensionnelle du théorème de Vosper
Notre résultat principal est le suivant: dans une extension séparable de degré premier d'un corps k, les paires de k-sous-espaces vectoriels A, B, tels que la dimension de l'espace engendré par le produit AB égale dim(A)+dim(B)-1 sont à l'exception de cas dégénérés simples, des translatés multiplicatifs des espaces de polynômes de degrés strictement inférieur à dim(A) pour l'un, à dim(B) pour l'autres, et évalués en un élément z de l'extension. Nous utilisons la méthode isopérimétrique, ou atomique, d'Hamidoune dont la motivation originelle est l'étude de la connexité dans les graphes mais qui s'est avérée également très utile en combinatoire additive. Travail commun avec Oriol Serra. |
Salle 178, Labri, 15h15-16h15 |
| Ralf Klasing | 16/04/2013 | Identifying coDes in Evolving grAphs (IDEA)
In this talk, we will give an overview of the ANR project "Identifying coDes in Evolving grAphs (IDEA)". In particular, we will present some of the results obtained in the project, and we will outline some potential directions of future research. |
Salle 385, IMB, 10h-11h |
| Sandi Klavzar | 26/04/2013 | Bad words arising from generalized Fibonacci cubes
|
Salle 178, Labri, 15h15-16h15 |
| Achill Schurmann | 28/05/2013 | Exploiting Symmetries in Polyhedral Computations
Many important problems in mathematics and its applications are modeled using linear constraints respectively polyhedra. Standard modeling often yields polyhedra having many symmetries. However, standard algorithms do not take advantage of them, and even worse, they often work particularly poorly on symmetric problems. In this talk we give an overview about ongoing work on new symmetry exploiting techniques for three fundamental task in polyhedral computations: the representation conversion problem, integer linear programming, and lattice point counting. Initial proof-of-concept results show that affine symmetries can be exploited quite well in certain situations. In order to apply these new techniques on a broader scale new theoretical grounds have to be broken. |
Salle 385, IMB, 10h-11h |