Discrete Mathematics

Spectral stability for the partition function and the number of biased independent sets.

Event Date: May 06, 2015 in Discrete Mathematics, Seminars

Abstract: In this talk we shall discuss two problems concerning the number of independent sets in regular graphs. The results of Kahn and Zhao show that among all d-regular graphs on n vertices, the graph consisting of disjoint copies of complete bipartite graphs maximizes the number of independent sets. In the first part we discuss a spectral stability phenomenon for this result. Further, we are interested in counting “biased” independent sets in regular bipartite graphs, i.e. independent sets which are essentially contained in one of the partition classes. This problem is related to the...

Read More

Lines, betweenness and metric spaces

Event Date: Apr 17, 2015 in Discrete Mathematics, Seminars

  Abstract:   A celebrated Theorem of de Bruijn and Erdos states that every noncollinear set of n points in the plane determines at least n distinct lines. Line uv in the plane consists of all points p such that:   – dist(p,u) + dist(u,v) = dist(p,v) (i.e. u is between p and v) or – dist(u,p) + dist(p,v) = dist(u,v) (i.e. p is between u and v) or – dist(u,v) + dist(v,p) = dist(u p) (i.e. v is between u and p).   With this definition of line uv in an arbitrary metric space (V, dist), Chen and Chvatal conjectured that every metric space on n points, where n is...

Read More

A polyhedral study of the diameter constrained minimum spanning tree problem

Event Date: Mar 06, 2015 in Discrete Mathematics, Seminars

Abstract:   The diameter constrained minimum spanning tree problem (DMSTP) is defined as follows: Given an edge-weighted graph G, and a diameter limit D, the goal is to identify a minimum cost spanning tree of G whose diameter does not exceed D. The question on how to provide a strong formulation for the DMSTP in the natural space of edge variables (using only one variable associated to each edge) remained open for some time and up to now, only extended formulations for the DMSTP are considered in the literature. Despite providing very tight linear programming (LP) bounds, these...

Read More

Macro Connections

Event Date: Dec 18, 2014 in Discrete Mathematics, Seminars

Abstract The rise of computational methods has generated a new natural resource. That new natural resource is data. While it is not clear if Big Data will open up trillion dollar markets, what it is clear is that making sense of visualizations are essential meaning out of. The capacity to create data visualizations, however, is not widespread. To help develop this capacity I have been working on the creation of Data Vizualization Engines, which are tools that allow people quickly visualize any portion of a large dataset and construct visual narratives from which they can draw insight. In...

Read More

Fair Linking Mechanisms for Resource Allocation with Correlated Player Types

Event Date: Dec 05, 2014 in Discrete Mathematics, Seminars

  Abstract: Resource allocation is one of the most relevant problems in the area of Mechanism Design for computing systems. Devising algo- rithms capable of providing efficient and fair allocation is the objective of many previous research efforts. Usually, the mechanisms they propose use payments in order to deal with selfishness. Since using payments is undesirable in some contexts, a family of mechanisms without pay- ments is proposed in this paper. These mechanisms extend the Linking Mechanism of Jackson and Sonnenschein introducing a generic concept of fairness with correlated...

Read More

On the diameter of minimal separators in a graph

Event Date: Nov 28, 2014 in Discrete Mathematics, Seminars

  Abstract: The so-called topological and metric tree-likeness invariants are two distinct approaches to measure “how close” a graph is from a tree. They are related with tree-decompositions of the graph. In this work, we focus on the relations between topological and metric graph parameters, and especially between treewidth and treelength. Our main contribution is a general upper-bound on the diameter of minimal separators in a graph that depends on the properties of its cycle basis. This allows us to show the treelength is upper-bounded by an O(l(G).tw(G)), with tw(G) the...

Read More