Evènement pour le groupe Algorithmique Distribuée

Date 2016-10-03  14:00-15:00
TitreAn overview of discharging methods 
RésuméDischarging methods are used in order to obtain structural lemmas in graph theory. In general, the point is to prove by contradiction that a graph with some properties (planarity, bounded density...) must contain an element of a given list as a subgraph. The idea of this proof technique is as follows: (1) weights are assigned to some elements of the graph (vertices, edges, faces...), (2) a discharging phase allows to redistribute the weights over the graph, (3) using the hypothesis that some subgraphs do not appear in the graph, a weight assessment shows that the total weight is in contradiction with the density/planarity assumptions. In short, it is a counting argument that takes strong advantage of the graph structure. Though the proofs are easier to handle as such for humans, they can be straightforwardly translated into linear programs for the sake of computers. The existence of a subgraph from this given list can then be used for example for coloring purpose. In particular, this proof technique is decisive for the Four Colour Theorem. During step (2), the weight redistribution is typically local (the weight travels to close elements only). In 2005, Borodin made this technique evolve by introducing global discharging rules (the weight can travel arbitrarily far away). To this day, global discharging methods are still under-developed, but look promising. This talk is meant as an overview of different discharging techniques, through coloring problems they helped answer to. We will also mention their algorithmic appeal, as efficient coloring algorithms as well as tools toward more refined bounds of Fixed Parameter Tractability kernels.  
OrateurMarthe Bonamy 

Aucun document lié à cet événement.

Retour à l'index