Some recent results on the integer linear programming formulation for the Max-Cut problem

-- Hung Nguyen (GALAC, LRI)

Summary: Given an undirected graph G=(V,E) where the edges are weighted by an arbitrary cost vector c, a cut S in G associated with a node subset S is the edge subset of E which contains all the edges having exactly one end-node in S. The Maximum Cut ...

Maximum Independent Set in H-free graphs

-- Edouard BONNET (GALAC, LRI)

Summary: Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1 ...

Comprendre la combinatoire des fonctions “parking" rectangulaire via les espaces de polynômes harmoniques diagonaux (exposé 1)

-- François Bergeron (UQAM)

Dans cette suite d’exposés, j’ai l’intention d’expliquer comment de nouveaux espaces de polynômes multivariés permettent: de rendre compte de la riche combinatoire des généralisations rectangulaires des fonctions parking, des chemins de (m,n)-Catalan, et des treillis de (m,n)-Tamari; de comprendre les familles de ...

Attribution Accessit du prix de thèse 2018 Graphes Charles DELORME

-- George Manoussakis

Nous avons le plaisir de vous annoncer que l'étudiant George Manoussakis encadré par Johanne Cohen et Antoine Deza a reçu l'accessit du prix de thèse 2018 Graphes Charles DELORME. http://gtgraphes.labri.fr/pmwiki/pmwiki.php/PrixTheseDelorme/PrixTheseDelorme Voici le résumé de sa thèse : Nous introduisons d'abord ...

Séminaire ouvert

-- Toute l'équipe (LIX et GALAC)

Lors d'un séminaire ouvert, le thème n'est pas décidé à l'avance. Tous les membres du séminaires sont invités à participer et peuvent proposer le jour même des interventions plus ou moins longues, des démos ou des questions ouvertes au reste de l'équipe.

Binary pattern of length greater than 14 are abelian-2-avoidable

-- Matthieu Rosenfeld (GALAC, LRI)

Summary: Two words u and v are abelian equivalent if they are permutation of each other ("aabc" and "baca" are abelian equivalent). Let w be a word and P= P1...Pn (where the Pi are the letters of P) a pattern (a word over another alphabet), we say that w ...

Cyclic sieving for reduced reflection factorizations of the Coxeter element

-- Theo Douvropoulos (IRIF, Paris 7 Diderot)

Given a factorization \(t_1\cdots t_n=c\) of some element \(c\) in a group, there are various natural cyclic operations we can apply on it; one of them is given by \(\Psi:(t_1,\cdots,t_n)\rightarrow (c\ t_n\ c^{-1},t_1,\cdots, t_{n-1})\). A common question is then to ...

Caractérisation de réseaux égocentrés par l'énumération de leurs sous-graphes induits

-- Raphaël Charbey (GALAC, LRI)

Résumé : La science des réseaux regroupe des méthodes issues de différentes disciplines qui ont néanmoins souvent du mal à percer au delà de celles-ci. Très utilisée en biologie moléculaire, notamment dans le cadre de l'étude des interactions entre protéines, l'énumération de l'ensemble des sous-graphes induits, jusqu'à ...

Convergence of uniform noncrossing partitions toward the Brownian triangulation

-- Jérémie Bettinelli (LIX, équipe Combi)

We give a short proof that a uniform noncrossing partition of the regular \(n\)-gon weakly converges toward Aldous's Brownian triangulation of the disk, in the sense of the Hausdorff topology. This result was first obtained by Curien and Kortchemski, using a more complicated encoding. Thanks to a result ...

Extensions d'ordres cycliques partiels, boustrophédons et polytopes

-- Sanjay Ramassamy (UMPA, ENS Lyon)

Tandis que l'énumeration des extensions linéaires des ensembles partiellement ordonnés a fait l'objet de nombreux travaux, son analogue cyclique (énumération des extensions à des ordres cycliques totaux d'un ordre cyclique partiel donné) a été fort peu étudié. Dans cet exposé, j'introduirai certaines classes d'ordres cycliques ...

Page 1 / 8 »