Noticias en español
Well-quasi-ordering digraphs by the strong immersion relation.
Abstract: A well-quasi-ordering is a reflexive and transitive binary relation such that every infinite sequence has a non-trivial increasing subsequence. The study of well-quasi-ordering was stimulated by two conjectures of Vazsonyi in 1940s: trees and subcubic graphs are well-quasi-ordered by the topological minor relation. It is known that the topological minor relation does not well-quasi-order all graphs. Nash-Williams in 1960s introduced the notion of strong immersion and conjectured that the strong immersion relation well-quasi-orders all graphs, which is a common generalization of...
Read MoreCounting integer partitions with the method of maximum entropy.
Abstract: The problem of asymptotically counting integer partitions has a long and storied history, beginning with the pioneering work of Hardy and Ramanujan in 1918. In the work presented here, we give a probabilistic perspective on this problem, and use this approach to prove an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer...
Read MoreMatroids, polymatroids and submodular functions: algebra or optimization?
Abstract: Matroids, polymatroids and submodular functions are beautiful objects that have appeared in many areas of mathematics including algebra, geometry, topology and optimization. Consequently, they have been studied from multiple points of view. This oftentimes has the consequence that the same results are proven from different points of view and by very different communities. A notable example being their study in optimization and algebraic combinatorics. The goal of this talk is to tell this story, show how a small mixture of ideas from different communities lead to powerful algebraic...
Read MoreAn optimal algorithm for strict circular seriation.
Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities...
Read MoreApportionment Mechanisms under Parity Constraints and the case of Chile and a new Political Constitution.
Abstract: How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level, we also have to find an allocation which is paritary for the types. We consider two different approaches: one of them, with a greedy/local search paradigm, corresponds to a mechanism recently approved in the chilean...
Read MoreOn the two-dimensional knapsack problem for convex polygons.
Abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles. In this talk we will first present: – a quasi-poly time O(1)-approximation – a poly time O(1)-approximation algorithm if all input polygons are triangles. We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the...
Read More