7ème Rencontre STINT

La 7ème rencontre STINT aura lieu du lundi 4 au mercredi 6 décembre 2017 à Sophia Antipolis.

 

Programme

Lundi 4 décembre:

12-14h : Accueil et déjeuner.

14h : Alantha Newman, Partitioning small induced subgraphs for graph coloring.

P_t-free graphs contain no induced k-cycles for k >= t+1. Therefore, one approach to color a P_t-free graph is to divide the vertices into (few) sets such that all the odd cycles (of length at most t) are partitioned, i.e. each set is bipartite. We present an approach to partition short induced cycles in 3-colorable graphs. Our approach is based on semidefinite programming, which is a useful algorithmic tool for graph partitioning. We focus on partitioning the 5-cycles and 3-cycles in 3-colorable, P_6-free graphs. It is already known how to 3-color 3-colorable P_6-free graphs, but we hope that these methods can be extended.

Joint work with Vladan Jovicic.

15h : Frédéric Havet, On the minimum size of an identifying code over all orientations of a graph.    Slides

For a graph or digraph G, let id(G) be the minimum size of an identifying code of G if one exists, and id(G) = +∞ otherwise. For a graph G, let idor(G) be the minimum of id(D) over all orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G) ≤ 3id(G)/2 for every graph G. We also show that computing idor(G) is NP-hard, while deciding whether idor(G) ≤ |V (G)| − k is polynomial-time solvable for every fixed integer k.

Joint work with Nathann Cohen.

16h : Session de problèmes     Report

 

Mardi 5 décembre:

9h30-10h30 : Matej Stehlik,  Generalised Mycielski graphs and the Borsuk-Ulam theorem.    Slides

Stiebitz determined the chromatic number of generalised Mycielski graphs using the topological method of Lovasz, which invokes the Borsuk–Ulam theorem. Van Ngoc and Tuza used elementary combinatorial arguments to prove Stiebitz’s theorem for 4-chromatic generalised Mycielski graphs, and asked if there is also an elementary combinatorial proof for higher chromatic number. We answer their question by showing that Stiebitz’s theorem can be deduced from a version of Fan’s combinatorial lemma. Our proof uses topological terminology, but is otherwise completely discrete and could be rewritten to avoid topology altogether. However, doing so would be somewhat artificial, because we also show that Stiebitz’s theorem is equivalent to the Borsuk-Ulam theorem.
Joint work with Tobias Müller.
 

11h-12h : Jean-Claude Bermond, Dynamique de formations de groupes dans les réseaux sociaux.    Slides

Cet exposé reprend des résultats de A. Chaintreau, G. Ducoffe et D. Mazauric. Nous considérons le modèle simplifié suivant introduit par Kleinberg et Ligett. Deux personnes sont soit amies soit ennemies. Un groupe est formé de personnes amies (2 personnes ennemies ne peuvent pas être dans le même groupe). On considère les partitions des n personnes en groupes. L’utilité d’une personne est le nombre d’amies
dans son groupe (c’est à dire la taille du groupe moins 1). La partition initiale est formée de n groupes de 1 personne.  On autorise les mouvements suivants appelés k-déviations. Dans une k-déviation
d’une partition vers une autre au plus k personnes quittent leur groupes respectifs pour rejoindre un autre groupe ou en créer un sous réserve que leur utilité augmente.  Ainsi dans une 1- déviation une
personne quitte son groupe pour un groupe de taille supérieure ou égale.  Une partition est k-stable s’il n’existe pas de k-déviation de cette partition vers une autre. Dans le cas où il n’y pas d’ennemies la partition stable est formé d’un unique groupe des n personnes.
Dans l’exposé on se limitera au cas des 1-déviations. On s’intéressera à la dynamique de convergence mesurée par le nombre de 1-déviations utilisées pour  atteindre à partir de  la partition initiale une partition stable. En particulier on montre que dans le cas où il n’y a pas d’ennemies, une séquence de 1-deviations correspond à une chaîne dans le treillis des partitions d’entiers. Utilisant un résultat de Greene
et Kleitman on détermine ainsi exactement la taille de plus longue séquence de 1-déviations menant de la partition initiale en n groupes de une personne à la partition formé d’un seul groupe de n personnes
(elle contient $ 0(n^{3/2}$ 1-déviations). Dans le cas d’un graphe de conflit de nombre de stabilité $\alpha$ au vu du résultat ci-dessus Guillaume conjecturait que la plus longue séquence était en $O(n
\sqrt{\alpha})$. On donne un contre exemple en montrant qu’il existe des  graphes de conflit  avec  $\alpha = \Omega (\sqrt {n})$ pour lesquels  la plus longue séquence est en $0(n \alpha)$.
 

12-14h: Déjeuner.

14h : Maria Macekova, 3-colorability of (claw,H)-free graphs.    Slides

The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs in general. In the talk we focus on the computational complexity of the problem in subclasses of claw-free graphs defined by forbidding additional subgraphs. We give a necessary condition for the polynomial-time solvability of the problem in such classes and present some new result.

15h : William Lochet, Immersion of transitive tournaments in digraphs with large minimum outdegree.

We prove the existence of a function g(k) such that every simple digraph with minimum outdegree greater than g(k) contains an immersion of the transitive tournament on k vertices.
This solves a conjecture of Devos, McDonald, Mohar and Scheide.

 

Mercredi 6 décembre:

9h30-10h30 : Patrice Ossona de Mendez, Sparsity and Beyond.

We review some recent progress in the study of structural properties of sparse graphs and sketch recent exciting developments on “structural sparsity”, allowing to generalize tools used for sparse graphs to dense low complexity graphs

 

11h-12h : Pierre Aboulker, A tigth Erdös-Posá function for wheel minors.        Slides

Let W_t denote the wheel on t+1 vertices. We prove that for every integer t > 2 there is a constant c=c(t) such that for every integer k> 0 and every graph G, either G contains k vertex-disjoint subgraphs each containing W_t as minor, or there is a subset X of at most c k log k vertices such that G-X has no W_t minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace W_t with any fixed planar graph H.

Joint work with Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond and Ignasi Sau.

 

12-14h: Déjeuner.

 

Liste des participants.

EHESS (Paris)

Patrice Ossona de Mendez

 

G-SCOP (Grenoble)

Pierre Aboulker
Maria Macekova
Frédéric Maffray
Alantha Newman
Matej Stehlik

LIP

Khang Le

Nam Le

William Lochet

Stéphan Thomassé

 

Coati

Julien Bensmail

Jean-Claude Bermond

Frédéric Havet

Fionn Mc Inerney

Nicolas Nisse

Stéphane Pérennes

Comments are closed