Todos los cursos serán en Ingles.
All the courses will be given in English.
“Edge colouring multigraphs”
Penny Haxell
Abstract:
An edge colouring of a multigraph \( G \) is a function that assigns a colour to each edge of \(G\) such that no two edges sharing a vertex get the same colour. The chromatic index \( \chi'(G) \) is the smallest \( k \) for which there exists an edge colouring of \( G \) using \( k \) colours. It is clear that the maximum degree \( \Delta(G) \)$ is a lower bound for \( \chi'(G) \) for every loopless multigraph \( G \). The classical upper bounds for \( \chi'(G) \) are \( \chi'(G) \leq 3\Delta(G)/2 \) (Shannon’s Theorem, 1949) and \( \chi'(G)\leq\Delta(G)+\mu(G) \) (Vizing’s Theorem, 1964), where \( \mu(G) \) denotes the maximum edge multiplicity of \( G \). Thus for simple graphs (i.e. those satisfying \(\mu(G)=1\) ) there are only two possible values for \( \chi'(G) \), namely \( \Delta(G) \) and \( \Delta(G)+1\), and by Holyer’s classical theorem it is NP-hard to distinguish between them.
In this course we will study edge colouring of multigraphs, with a particular focus on a famous open problem posed by Goldberg and (independently) Seymour in the 1970’s. It states that if a loopless multigraph \( G \) does not have an edge colouring with \( \Delta(G)+1 \) colours, then it contains a natural obstruction consisting of a vertex subset that induces too many edges to be coloured with \(\Delta(G)+1 \) colours. We will see some relatively recent partial results related to this conjecture. One of the principal tools is an important method due to Tashkinov, called the method of Tashkinov trees, which is a sophisticated generalization of the method of alternating paths.
“Two Topics in Discrete Algorithms: Certifying Algorithms and Slime Mold Computations.”
Kurt Mehlhorn.
Abstract:
A certifying algorithm for a function \( f \) on input \( x \) does not only compute a result \( y \), but also a witness \( w \) that proves that \(y = f(x)\). Certifying algorithms are a design principle of LEDA. The witness can be checked by a checker program. We review certifying algorithms and report on the formal verification of checker programs.
The slime mold Physarum Polycephalum can apparently compute shortest path and design cost-effective and fault-resilient networks. We report on wet-lab experiments, modeling, analysis, and a surprising connection to linear programming.
“CONGEST Algorithms and Lower Bounds.”
Rotem Oshman.
Abstract:
The CONGEST model of distributed computing models a network with congestion constraints: each edge may only carry a small number of bits per round of communication. In this model it can be challenging to perform network-global tasks such as finding a minimum spanning tree of the network, computing the network diameter, or finding approximately-shortest paths between all pairs of nodes; we will present algorithms for the tasks above and other tasks. In addition, it is sometimes possible to prove that no faster algorithm exists, and we will see several examples of such lower bounds, using reductions from two-party communication complexity.