Cursos

Todos los cursos serán en inglés – All courses will be given in English.

Course 1: Packing and Covering Problems in Matroids

Lecturer: Kristóf Bérczi
Teaching Assistant: Lydia Mirabel Mendoza

Abstract:
Motivated by the shared behaviors of vector spaces and graphs, matroids were introduced by Whitney and independently by Nakasawa as a combinatorial abstraction of the recurring theme of linear independence. Informally, a matroid is a hereditary set system whose maximal members, called bases, satisfy a certain exchange property. Over the past century, matroid theory has proven to be an efficient tool for combinatorial optimization, thanks to the pioneering work of Edmonds and Fulkerson. Edmonds’ matroid intersection theorem provides a min-max formula for the maximum cardinality of a common independent set of two matroids, which can also be extended to the weighted setting. Additionally, Edmonds and Fulkerson addressed the closely related problem of packing bases in a matroid, or more generally, packing bases of k matroids in a pairwise disjoint manner.

This leads naturally to the following question: What can we say about the common generalization of these two problems, i.e., when one seeks to find disjoint common bases in the intersection of two matroids? This problem generalizes a wide range of fundamental questions, including Woodall’s conjecture on the maximum number of pairwise disjoint dijoins in directed graphs, as well as Rota’s beautiful conjecture on the existence of transversal bases. Unfortunately, it has been shown that the problem is oracle-hard, meaning there is no algorithm that can decide whether the ground set of two matroids admits a partition into common bases using a polynomial number of independence queries. Nevertheless, the hardness of the abstract problem does not necessarily imply complexity for its special cases; thus, finding necessary or sufficient conditions for the existence of the required packing is of particular interest. In this minicourse, starting from the basics, we will discuss recent advances in this topic.
Ir arriba

Course 2: Straight Line Complexity of Linear Programs

Lecturer: Daniel Dadush
Teaching Assistants: Svenja Griesbach, Benjamín Jáuregui

Abstract:
Interior point methods (IPMs) are some of the most efficient methods for solving linear programs, i.e., programs of the form min c^T x, Ax = b, x >= 0. These methods follow a so-called central path which stays «far away» from the boundary and ends at an optimal solution. While worst-case per iteration converge rates of IPMs are now quite well understood, a more global understanding of the iteration complexity of IPMs has remained elusive until recently.

In this course, we will show how to characterize the complexity of path following via straight line complexity (SLC), which corresponds to the minimum number of pieces of any piecewise linear curve which suitably approximates the central path. The course will cover (to varying degrees of detail):

1. Nearly tight upper and lower bounds on the iteration complexity of IPMs which follow a piecewise linear trajectory using SLC.
2. The relation between SLC to the shape of simplex paths as well as the shape of minimal linear dependences of the constraint matrix A (also known as circuits).
3. Construction of linear programs with exponential SLC using tools from tropical geometry.
4. Polynomial upper bounds on SLC for combinatorial classes of linear programs.

Ir arriba

Course 3: Algebraic Methods for Combinatorics

Lecturer: Natasha Morrison
Teaching Assistants: Taruni Sai Sridhar, Mauricio Yépez

Abstract:
Algebraic methods are some of the most beautiful and powerful techniques in combinatorics. In this course, I will present some of the most appealing applications of these techniques. The course aims to cover topics related to graph theory, intersection theorems, and the Combinatorial Nullstellensatz and applications.

Ir arriba