ヘニング ブルーン-藤本
Maître de conférences
Équipe Combinatoire et Optimisation
Université Pierre et Marie Curie, Paris
Barre 1516, 1er étage, bureau 1-18
(+33) 01 44 27 85 39
NM512 Coloration et graphes parfaits
Vendredi 13h-15h, salle 15-16/101
Dates: Janvier 27, Février 3/10/17, Mars 2/9/16/23/30, Avril 6
Examen: 13 Avril
Bibliographie: Graph Theory
(Reinhard Diestel),
Combinatorial Optimization (Alexander Schrijver)
Sujets des exposés
MM063 Optimisation combinatoire
Mercredi 08h30-10h30 (salle 23.24.212) et jeudi 10h45-12h45 (salle 23.24.203)
TD Mardi 17h00-20h00 (salle 23.24.202) et mercredi 13h45-16h45 (salle 23.24.212)
Examen partiel: 29/02 13h45-16h45 (salle 13.14.102)
Bibliographie: Optimisation combinatoire
(Korte et Vygen)
Feuilles d'exercice:
1
2
3
4
5
6
7
8
9
10
Feuilles d'exercice de Dominique Bernardi:
1
correction
2
3
4
5
6
7
8
9
Brightwell, van den Heuvel and Stougie proved that the diameter of an m × n transportation polytope is at most 8(m + n − 2), a factor of eight away from the Hirsch Conjecture. This bound was improved to 3(m + n − 1) by Hurkens. We investigate diameters for certain classes of transportation polytopes.
We prove that every stability two unit disk graph has chromatic number at most 3/2 times its clique number.
We give axiomatic foundations for non-finitary infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. This completes the solution to a problem of Rado of 1966.
We introduce a connectivity function for infinite matroids with properties similar to the connectivity function of a finite matroid, such as submodularity and invariance under duality. As an application we use it to extend Tutte's linking theorem to finitary and to co-finitary matroids.
A graph is called t-perfect, if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We characterise the class of all claw-free t-perfect graphs by forbidden t-minors, and show that they are 3-colourable. Moreover, we determine the chromatic number of claw-free h-perfect graphs and give a polynomial-time algorithm to compute an optimal colouring.
Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y.
In a finite graph, an edge set Z is an element of the cycle space if and only if every vertex has even degree in Z. We extend this basic result to the topological cycle space, which allows infinite circuits, of locally finite graphs. In order to do so, it becomes necessary to attribute a parity to the ends of the graph.
It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals.
In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a suficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question.
Two non-isomorphic graphs are twins if each is isomorphic to a subgraph of the other. We prove that a rayless graph has either infinitely many twins or none.
Motivated by work of Diestel and Kühn on the cycle spaces of infinite graphs we study the ramifications of allowing infinite sums in a module RM. We show that every generating set in this setup contains a basis if the ground set M is countable, but not necessarily otherwise. Given a family N ⊆ RM, we determine when the infinite-sum span <N> of N is closed under infinite sums, i.e. when <N> = <<N>>. We prove that this is the case if R is a field or a finite ring and each element of M lies in the support of only finitely many elements of N. This is, in a sense, best possible. We finally relate closures under infinite sums to topological closures in the product space RM.
We prove that every rayless graph has an unfriendly partition.
A connected graph G is called t-perfect if its stable set polytope is determined by the non-negativity, edge and odd-cycle inequalities. Moreover, G is called strongly t-perfect if this system is totally dual integral. It is an open problem whether t-perfection is equivalent to strong t-perfection. We prove the equivalence for the class of claw-free graphs.
We investigate the end spaces of infinite dual graphs. We show that there exists a natural homeomorphism between the end spaces of a graph and its dual, and that this homeomorphism maps thick ends to thick ends. Along the way, we prove that Tutte-connectivity is invariant under taking (infinite) duals.
We extend three results involving bicycles and left-right tours to infinite, locally finite graphs: Read and Rosenstiehl’s tripartition theorem, Shank’s theorem that the residues of left-right tours generate the bicycle space and the planarity criterion of Archdeacon, Bonnington and Little. In order to achieve this it is necessary to allow infinite cycles as defined by Diestel and Kühn.
Given a closed surface S, we characterise the graphs embeddable in S by an algebraic condition asserting the existence of a sparse generating set for their cycle space. When S is the sphere, the condition defaults to MacLane’s planarity criterion.
Degree constrained orientations are orientations of an (undirected) graph where the in-degree function satisfies given lower and upper bounds. For finite graphs Frank and Gyárfás (1976) gave a necessary and sufficient condition for the existence of such an orientation. We extend their result to countable graphs.
A classical theorem by Tutte assures the existence of a Hamilton cycle in every finite 4-connected planar graph. Extensions of this result to infinite graphs require a suitable concept of an infinite cycle. Such a concept was provided by Diestel and Kühn, who defined circles to be homeomorphic images of the unit circle in the Freudenthal compactification of the (locally finite) graph. With this definition we prove a partial extension of Tutte’s result to locally finite graphs.
For an integer h>0, an elementary h-route flow is a flow along h edge disjoint paths between a source and a sink, each path carrying a unit of flow, and a single commodity h-route flow is a non-negative linear combination of elementary h-route flows. An instance of a single source multicommodity flow problem for a graph G = (V,E) consists of a source vertex s and k sinks t1, . . . , tk corresponding to k commodities; we denote it I =(s;t1, . . . , tk). In the single source multicommodity multiroute flow problem, we are given an instance I = (s;t1, . . . , tk) and an integer h>0, and the objective is to maximize the total amount of flow that is transferred from the source to the sinks so that the capacity constraints are obeyed and, moreover, the flow of each commodity is an h-route flow.
We study the relation between classical and multiroute single source flows on undirected networks with uniform capacities and we provide a tight bound. In particular, we prove the following result. Given an instance I = (s;t1, . . . , tk) such that each s−ti pair is h-connected, the maximum classical flow between s and the ti is at most (2−2/h)-times larger than the maximum h-route flow between s and the ti and this is the best possible bound for h>1. This, as we show, is in contrast to the situation of general multicommodity (i. e., multiple sources or non-uniform capacities) multiroute flows that are up to k(1−1/h)-times smaller than their classical counterparts.
Furthermore, we introduce and investigate duplex flows defined so that the capacity constraints on edges are applied independently for each direction. We show that for networks with uniform capacities and for instances as above the maximum classical flow between s and the ti is the same as the maximum h-route duplex flow between s and the ti. Moreover, the total flow on each edge in the duplex flow can be restricted to (2−2/h)C, where C is the capacity of each edge.
As a corollary, we establish a max-flow min-cut theorem for the single source multicommodity multiroute flow and cut. An h-disconnecting cut for I is a set of edges F such that for each i, the maximum h-route flow between s and ti is zero. We show that the maximum h-route flow is within 2h−2 of the minimum h-disconnecting cut, independently of the number of commodities; we also describe a (2h−2)-approximation algorithm for the minimum h-disconnecting cut problem.
Owari is an old African game that consists of cyclically ordered pits that are filled with pebbles. In a sowing move all the pebbles are taken out of one pit and distributed one by one in subsequent pits. Repeated sowing will give rise to recurrent states of the owari. Bouchet studied such periodical states in an idealised setup, where there are infinitely many pits. We characterise periodical states in owaris with finitely many pits. Our result implies Bouchet’s result.
We introduce a natural extension of the vertex degree to ends. For the cycle space as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in the cycle space if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.
MacLane's planarity criterion states that a finite graph is planar if and only if its cycle space has a basis B such that every edge is contained in at most two members of B. Solving a problem of Wagner (1970), we show that the topological cycle space introduced recently by Diestel and Kühn allows a verbatim generalization of MacLane's criterion to locally finite graphs. This then enables us to extend Tutte's planarity criterion as well. Finally, we shall discuss a generalization of MacLane's criterion to non-locally finite graphs.
The adaption of combinatorial duality to infinite graphs has been hampered by the fact that while cuts (or cocycles) can be infinite, cycles are finite. We show that these obstructions fall away when duality is reinterpreted on the basis of a `singular' approach to graph homology, whose cycles are defined topologically in a space formed by the graph together with its ends and can be infinite. Our approach enables us to complete Thomassen's results about `finitary' duality for infinite graphs to full duality, including his extensions of Whitney's theorem.
A well-known conjecture of Erdös states that, given an infinite graph G and vertex sets A,B there exists a family of disjoint A-B paths P together with an A-B separator X consisting of a choice of one vertex from each path in P. There is a natural extension of this conjecture in which A, B and X may contain ends as well as vertices. We prove this extension by reducing it to the vertex version, which was recently proved by Aharoni and Berger.
By a result of Gallai, every finite graph G has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in G. However we show that, for the adaptation of the cycle space to infinite graphs recently introduced by Diestel and Kühn (which involves infinite cycles as well as finite ones), Gallai's theorem extends to locally finite graphs. Using similar techniques we show that if Seymour's faithful cycle cover conjecture is true for finite graphs then it also holds for locally finite graphs when infinite cyles are allowed in the cover, but not otherwise. We also consider extensions to graphs with infinite degrees.
We extend Tutte's result that in a finite 3-connected graph the cycle space is generated by the peripheral circuits to locally finite graphs. Such a generalization becomes possible by the admission of infinite circuits in the graph compactified by its ends.
Answering a question of Halin, we prove that in a 3-connected graph with at most one end the cycle space is generated by the induced non-separating cycles.
All Hamburg papers concerning the topological cycle space can be found here