Séminaires 2009 - 2010

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en salle Jaeger. Les responsables sont Louis Esperet et Andras Sebö, n'hésitez pas à les contacter.

• Jeudi 8 juillet 2010 (à 14h30): Andras Sebo (CNRS, G-SCOP) :
  
  How big can the difference between the chromatic number and clique num- ber be in a graph on at most n vertices? Can the extremal graphs be explored? While computational problems related to this chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for the maximum of this difference in terms of Ramsey numbers. As a consequence, the Ramsey graphs for R(3; :) have high matchability and connectivity properties.
  
  Joint work with Nicolas Trotignon and Andras Gyarfas
  
  
• Jeudi 24 juin 2010 (à 10h30): Marco Montalva et Eric Fanchon (TIMC-IMAG) : Problèmes combinatoires liés à des questions de modélisation de réseaux discrets
  
  Les réseaux discrets déterministes sont utilisés comme modèles de différents types de réseaux biologiques (par exemple réseaux génétiques ou neuronaux). La dynamique de ces réseaux est définie par une fonction F de composition d'influences sur les noeuds, et une fonction de mise à jour des noeuds s (update function) spécifiant la séquence de mise à jour de ceux-ci. Cette fonction associe à chaque noeud i un entier k, et est un élément clé dans ces modèles.
  Un digraphe, appelé graphe d'interaction, est défini à partir de F : il existe un arc x -> y si la loi de mise à jour de y dépend de l'état de x. D'autre part, au lieu de spécifier complètement la séquence de mise à jour s, on peut se limiter à spécifier une relation d'ordre partiel entre les noeuds. L'arc x -> y est étiqueté par un signe - si x est mis à jour strictement avant y, par un signe + sinon. Parmi les digraphes signés, on appelle digraphes 'update' ceux qui sont associés à une fonction s. Aracena et al (BioSystems, 2009) ont montré que plusieurs schémas de mise à jour s peuvent donner la même dynamique. Plus précisément, deux fonctions s1 et s2 correspondant au même étiquetage +/- du graphe d'interaction génèrent la même dynamique (représentée par des chemins dans un graphe d'états). Dans un contexte de modélisation, où l'objectif est de construire un modèle de réseau à partir de données sur la dynamique, ceci montre que seuls les digraphes étiquetés sont inférables. Il s'agit donc d'objets importants d'un point de vue pratique.
  Nous présentons des résultats combinatoires concernant les objets mathématiques introduits dans le cadre de cette problématique : nombre d'étiquetages 'update' pour un digraphe donné, énumération des étiquetages update, etc.
  
  (travail en commun avec J. Aracena et M. Noual)
  
  
• Jeudi 3 juin 2010 (à 14h30): Zoltan Füredi (University of Illinois at Urbana-Champaign et Renyi Institute of Mathematics, Budapest) : Graph representations: intersections and differences
  
  A hypergraph H={H_1, ... , H_n} is called a k-representation of the graph G if V(G)={1, 2, ..., n} and (i,j) is an edge if and only if max { |H_i - H_j|, |H_j - H_i| } is at least k. Let k(G):=min k. Improving a result of Boros, Gurvich and Meshulam (2004) it is shown that for most n-vertex graphs $k(G)$ is asymptopic to n /log n. We overview many other versions, generalizations when the vertices of graphs are represented by sets.
  
  
• Mardi 27 avril 2010 (à 14h30): Rico Zenklusen (EPFL, Lausanne) : A Flow Model Based on Linking Systems with Applications in Network Coding
  
  The Gaussian relay channel network, is a natural candidate to model wireless networks. Unfortunately, it is not known how to determine the capacity of this model, except for simple networks. For this reason, Avestimehr, Diggavi and Tse introduced in 2007 a purely deterministic network model (the ADT model), which captures two key properties of wireless channels, namely broadcast and superposition. Furthermore, the capacity of an ADT model can be determined efficiently and approximates the capacity of Gaussian relay channels. In 2009, Amaudruz and Fragouli presented the first polynomial time algorithm to determine a relay encoding strategy that achieves the min-cut value of an ADT network.
  
  In this talk, I will present a flow model which shares many properties with classical network flows (as introduced by Ford and Fulkerson) and includes the ADT model as a special case. The introduced flow model is based on linking systems, a structure closely related to matroids. Exploiting results from matroid theory, many interesting properties can readily be derived, as for example a max-flow min-cut result. Furthermore, classical matroid algorithms can be used to obtain efficient algorithms for finding maximum flows, minimum cost flows and minimum cuts.
  
  This is based on joint work with Michel Goemans and Satoru Iwata.
  
  
• 1er avril 2010 (à 14h30): Christelle Molle-Caillouet (LIG, Grenoble) : Modèles d'optimisation de la capacité des réseaux radio maillés
  
  Nous nous intéressons aux problématiques d'optimisation de la capacité des réseaux radio maillés. Nous définissons la capacité d'un réseau comme la quantité de flot que peut répartir équitablement une topologie aux utilisateurs qu'elle sert. Nous étudions plus précisément le problème joint du routage et de l'ordonnancement relié au Round Weighting Problem. Nous développons, pour la relaxation linéaire de ce problème, une méthode de résolution efficace utilisant la génération de colonnes. Nous dérivons ensuite une formulation qui élimine le routage pour se concentrer sur la capacité de transport disponible sur les coupes du réseau. L'équivalence des solutions optimales avec les formulations existantes est démontrée, et le processus de résolution combine une génération de lignes et de colonnes. Ces études mettent en évidence la présence d'une zone de contention autour de chaque point d'accès qui contraint la capacité du réseau.
  
  
• 18 mars 2010 (à 14h30): Tom McCormick (University of British Columbia, Canada) : A Polynomial Algorithm for Weighted Abstract Flow
  
  Ford and Fulkerson's original 1956 max flow/min cut paper formulated max flow in terms of flows on paths, rather than the more familiar flows on arcs. In 1974 Hoffman pointed out that Ford and Fulkerson's original proof was quite abstract, and applied to a wide range of flow problems. In this abstract model we have capacitated elements, and linearly ordered subsets of elements called paths. When two paths share an element ("cross"), then there must be a path that is a subset of the first path up to the cross and the second path after the cross. Hoffman's generalization of Ford and Fulkerson's proof showed that integral optimal primal and dual solutions still exist under this weak assumption. However, his proof is non-constructive.
  
  Hoffman's paper considers a sort of supermodular objective on the path flows, which allows him to include transportation problems and thus min-cost flow in his framework. We develop the first combinatorial polynomial algorithm that solves this problem, thereby also give a constructive proof of Hoffman's theorem. Our algorithm accesses the network only through a dual feasibility oracle, and resembles the successive shortest path algorithm for ordinary min-cost flow. It uses some of the same techniques used to solve the max flow/min cut version of Hoffman's model, plus a method to re-optimize when capacities change inside capacity scaling.
  
  This is joint work with Maren Martens (Zuse Institute Berlin).
  
  
• 12 février 2010 (à 14h): Benjamin Lévêque (LIRMM, Montpellier) : Triangle contact representations and duality
  
  A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix et al. proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual.
  A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intesertection between the triangles corresponding to u and v is the same point as the intesertection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, it can be required that the interiors of the triangles form a tiling of the triangle corresponding to the outer face and that each contact point is a node of exactly three triangles. Then, these representations are in one-to-one correspondance with generalized Schnyder woods defined by Felsner for 3-connected planar maps.
  
  
• 21 janvier 2010 (à 14h): Gautier Stauffer (Université Bordeaux 1) : The Hidden Matching-Structure of the Composition of Strips
  
  Composition of strips was introduced by Chudnovsky and Seymour as a key tool for decomposing claw-free graphs. In this talk we are going to reveal the close connection between the stable set problem in composed graphs and the matching theory. We will basically show that anything we can do for the strips, we can extend to composition of strips i.e. polytime algorithm (resp. separation, polyhedral description) for the strip extends to polytime algorithm (resp. separation, polyhedral description) for the composed graph.
  
  We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph $G$, we show an integral extended formulation for STAB(G) and a procedure to separate in polynomial time over STAB(G); moreover, we provide a complete characterization of STAB(G) when G is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins.
  
  (joint work with Yuri Faenza and Gianpaolo Oriolo)
  
  
• 14 janvier 2010 : Florian Huc (Université de Genève) : Mixing digraphs
  
  Extremal graph theory studies the question of the maximum number of edges a graph G can have while avoiding another graph H as a subgraph. In the setting of oriented graphs this question is not always interesting. So instead we consider a completely different parameter, namely, bias(D)=max{e(A,B) : A,B\subset V, such that e(B,A)\le e(A,B)/2}. We prove that every oriented graph with bias(D)< e²/32n²}$ contains an oriented four-cycle, and show that, up to the choice of constant, this result is best possible. We prove also a result for oriented six-cycles and a result which applies in the case D is dense. Most importantly we make conjectures and ask questions that we hope will stimulate further work on these questions.
  
  
• 17 décembre 2009 : Anna de Mier (Universitat Politecnica de Catalunya) : On the maximum number of cycles in outerplanar and series-parallel graphs
  
  Let c(n) be the maximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)^{1/n} exists and equals b=1.502837..., where b is a constant related to the recurrence x_{n+1}=1+x_n^2, x_0=1. The same result holds for the larger class of series-parallel graphs.
  
  
• 10 décembre 2009 : Thomas Rothvoss (EPFL, Lausanne) : An Improved LP-based Approximation for Steiner Tree
  
  The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph G=(V,E) and a subset of terminal nodes, find a minimum weight tree spanning the terminals. In this talk, we introduce a new directed LP relaxation and describe an approximation algorithm based on iterative randomized rounding of a fractional solution. We prove an approximation guarantee of 1.5+epsilon for the algorithm (improving over the previously best known factor of 1.55) and show that the mentioned LP has an integrality gap of at most 1.694 (improving over the previously best known factor of 2).
  
  This is joint work with Jaroslaw Byrka, Fabrizio Grandoni and Laura Sanita.
  
  
• 3 décembre 2009 : Alexandre Laugier (France Telecom, Sophia-Antipolis) : Hilbert bases and feasible RHS for flow problems
  
  In order to solve network design and multicommodity flow problems we want to be able to decompose them. The decomposition must be done in such a way that any solution of the original problem can be expressed as the sum of solutions of smaller problems, repetition been allowed. Conversely the sum of solutions of smaller problems arising in the decomposition is a solution of the original problem. Moreover any optimal solution with respect to a given objective function is the sum of optimal solutions over domains arising in the decomposition with respect to the objective function. For this approach we consider that the topology of the network is given. It is represented by vertex-arc incidence matrix of the supply graph. We characterize all the demand-capacity vectors that we need in order to be able to decompose over the domains involved by these vectors any routing or network design problem.
  
  The approach that we propose is based on the notion of extended fibers, we call extended fiber of a given matrix $A$ in $b$ the following discrete set $Q^{I}_{b}=\{x\in \Z,\;Ax=b\}$. A fiber $Q^{I}_{b}$ is said decomposable if there exist $b_{1}$ and $b_{2}$ such that $b=b_{1}+b_{2}$ and $Q^{I}_{b}=Q^{I}_{b_{1}}+Q^{I}_{b_{2}}$, otherwise it is said atomic. We show that the atomic extended fibers are in bijection with the vector of an Hilbert basis of the cone generated by the columns of $A$. Then we define truncated fibers of a matrix $A$ with respect to a set $M$. The elements of a truncated fiber can't be expressed as the sum of an element of the fiber and an element of $M$. We show that any truncated fiber can be expressed as the sum of truncated atomic fibers.
  
  In order to apply this material to flow problem we define an appropriate truncating set. We show that the Hilbert basis of the cone generated by the columns of vertex-arc incidence matrix of a graph is reduced to a subset of its columns. This implies that this Hilbert is rather small. Then starting from this point we show how this Hilbert can be easily extended to the Hilbert basis of the cone generated by the columns of the constraint matrix of a capacited flow problem. In fact we prove that we have a linear time, in the size of the output, in order to compute such a basis. At last we show how the result related to the flow problem can be directly extended to the multicommodity flow problem.
  
  
• 1er décembre 2009 : Celina de Figueiredo (Universidade Federal do Rio de Janeiro) : The P vs. NP-complete dichotomy of some challenging problems in graph theory
  
  The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. Among them is the central problem in theoretical computer science: the P vs. NP problem, which aims to classify the possible existence of efficient solutions to combinatorial and optimization problems. The main goal is to determine whether there are questions whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. In this context, it is important to determine precisely what facet of a problem makes it NP-complete. We shall discuss our contribution to the P vs. NP-complete dichotomy through the classification of some long-standing problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes. More precisely, we have shown that Chvatal's SKEW PARTITION is polynomial and that Roberts-Spencer's CLIQUE GRAPH is NP-complete. We have also solved the dichotomy for Golumbic-Kaplan-Shamir's SANDWICH problem. We shall describe two examples where we can determine the full dichotomy: The edge-coloring problem for graphs with no cycle with a unique chord, and the three nonempty part sandwich problem. Open problems are discussed: the stubborn problem for list partition; the chromatic index of chordal graphs; the recognition of split clique graphs.
  
  
• 18 septembre 2009 : Michael Tarsi (Université de Tel-Aviv) : Strong list coloring, Group connectivity and the Polynomial method
  
  Associated with an nxm matrix A=(a_ij) is its polynomial, P_A=P₁ⁿS₁^m a_ijx_j. If A is the |E|x|V| edges to vertices {-1,0,1} incidence matrix of a digraph G=(V,E), then a proper vertex coloring of G is an assignment of a "Color's vector" X=(x₁,x₂,…,x_|V|), for which P_A(X)≠0. This observation is at the core of the 'Polynomial method' for graph coloring.  I will show how other matrices and their polynomials, are similarly related to other combinatorial entities, such as: Strong list colorings, Nowhere zero flows and group connectivity.
  
  
  I will then show how the theorem relates to factor-critical graphs, t-stable hypergraphs and tau-critical hypergraphs. Finally, I will discuss graphs which achieve equality in Gallai's theorem.
  
  
• 18 septembre 2009 : Matej Stehlik (Visiteur CNRS, G-SCOP) : Gallai's theorem on colour-critical graphs and related results
  
  In 1963 Gallai published two seminal papers on colour-critical graphs: Kritische Graphen I and II. In the second of these papers Gallai proved that a k-critical graph with a connected complement has at least 2k-1 vertices. So any k-critical graph with less than 2k-1 vertices is the complete join of two smaller critical graphs. Gallai's original proof was quite long and involved the Edmonds-Gallai decomposition. I will show a different proof of Gallai's theorem which is much shorter.
  
  I will then show how the theorem relates to factor-critical graphs, t-stable hypergraphs and tau-critical hypergraphs. Finally, I will discuss graphs which achieve equality in Gallai's theorem.
  
  
• 18 septembre 2009 : Nathann Cohen (INRIA Sophia Antipolis) : Arête-coloration acyclique
  
  Une arête-coloration est acyclique si elle est propre et il n'y a pas de cycle bicolore. Une conjecture d'Alon, Sudakov et Zaks affirme que tout graphe admet une arete-coloration acyclique avec Delta + 2 couleurs. Nous montrons que les graphes planaires admettent une arête-coloration acyclique avec Delta + 25 couleurs.
  
  
• 18 septembre 2009 : Nicolas Trotignon (CNRS, LIAFA, Paris) : Combinatorial optimization with 2-joins
  
  The 2-Join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. We construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a minimum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.
  
  We also give a simple class a graph decomposable by 2-joins into bipartite graphs and line-graphs, and for which finding a maximum stable set is NP-hard. This shows that being Berge or even-hole-free gives properties essential to the use of 2-joins. (joint work with Kristina Vuskovic)
  
  
• 17 septembre 2009 : Benjamin Lévêque (CNRS, LIRMM, Montpellier) : Paths, trees and asteroids
  
  A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. We give an analogous characterisation of directed path graphs which are the intersection graphs of directed paths in a directed tree.
  
  
• 17 septembre 2009 : Louis Esperet (CNRS, G-SCOP) : Equivalence covering of line graphs
  
  An equivalence graph is a disjoint union of cliques, and the equivalence number eq(G) of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: 1/3 log log chi(G) < eq(L(G)) \le 2 log log chi(G) + 2, where chi(G) is the chromatic number of G This disproves a recent conjecture that eq(L(G)) is at most three for triangle-free G; indeed it can be arbitrarily large (joint work with John Gimbel and Andrew King).
  
  
• 17 septembre 2009 : Danny Hefetz (ETH Zürich) : Weighted colorings and Alon-Tarsi choosability
  
  Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs; the upper bound on the choice number of G obtained via their method, was later coined the Alon-Tarsi number of G. In the talk I will relate this parameter to a certain weighted sum of the proper colorings of $G$. Other than the appealing notion of obtaining upper bounds on the choice number of a graph via its proper colorings (in some sense), this result has several applications. Some of them are known; for these we give unified, and often also simpler and shorter proofs; and some are new. In the first part of the talk I will introduce chromatic, choice, and Alon-Tarsi numbers of graphs. In the second part I will state the main result and some of its applications.
  
  
• 17 septembre 2009 : Frédéric Havet (CNRS, INRIA Sophia-Antipolis) : Spanning galaxy problem
  
  Dans un digraphe, une galaxie est une union disjointe d'étoiles (un centre domine les feuilles). Le problème est de décider si un graphe admet une galaxie couvrante. On montre notamment que ce problème est NP-complet mais  polynomial dans les arbres et les digraphes fortement connexes. Le côté paramètre est également étudié.