{"id":36,"date":"2022-07-19T16:19:42","date_gmt":"2022-07-19T16:19:42","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/?page_id=36"},"modified":"2025-01-27T11:15:08","modified_gmt":"2025-01-27T14:15:08","slug":"cursos","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/cursos\/","title":{"rendered":"Cursos"},"content":{"rendered":"

Todos los cursos ser\u00e1n en ingl\u00e9s \u2013 All courses will be given in English.<\/em><\/p>\n

Course 1: Packing and Covering Problems in Matroids<\/strong><\/h2>\n

Lecturer: Krist\u00f3f B\u00e9rczi<\/strong><\/em>
\nTeaching Assistant: Lydia Mirabel Mendoza<\/p>\n

Abstract:<\/strong>
\nMotivated 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.<\/p>\n

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.<\/div>\n
<\/div>\n
Ir arriba<\/a><\/div>\n

Course 2: Straight Line Complexity of Linear Programs<\/strong><\/h2>\n

Lecturer: Daniel Dadush<\/strong><\/em>
\nTeaching Assistants: Svenja Griesbach, Benjam\u00edn J\u00e1uregui<\/p>\n

Abstract:
\n<\/strong>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 \u00abfar away\u00bb 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.<\/p>\n

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):<\/p>\n

1. Nearly tight upper and lower bounds on the iteration complexity of IPMs which follow a piecewise linear trajectory using SLC.
\n2. 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).
\n3. Construction of linear programs with exponential SLC using tools from tropical geometry.
\n4. Polynomial upper bounds on SLC for combinatorial classes of linear programs.<\/p>\n

Ir arriba<\/a><\/div>\n

Course 3: Algebraic Methods for Combinatorics<\/strong><\/h2>\n

Lecturer: Natasha Morrison<\/strong><\/em>
\nTeaching Assistants: Taruni Sai Sridhar, Mauricio Y\u00e9pez<\/p>\n

Abstract:<\/strong>
\nAlgebraic 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.<\/p>\n

Ir arriba<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"

Todos los cursos ser\u00e1n en ingl\u00e9s \u2013 All courses will be given in English. Course 1: Packing and Covering Problems in Matroids Lecturer: Krist\u00f3f B\u00e9rczi 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 … Seguir leyendo Cursos<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":55,"featured_media":0,"parent":0,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-36","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/pages\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/users\/55"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/comments?post=36"}],"version-history":[{"count":26,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/pages\/36\/revisions"}],"predecessor-version":[{"id":474,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/pages\/36\/revisions\/474"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2025\/wp-json\/wp\/v2\/media?parent=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}