Sitting closer to friends than enemies, revisited

Abstract:

The Sitting Closer to Friends than Enemies problem is to find an embedding in a metric space for the vertices of a given signed graph so that, for every pair of incident edges with different sign, the positive edge has to be shorter (in the metric of the space) than the negative edge. In this talk, I will give a gentle introduction and will present a collection of results regarding this problem. In particular, I will show a characterization for the sets of signed graphs for which there exist such an embedding in \mathbb{R}, in the circle, and in trees. Moreover, I will show an upper and lower bound on the number of vertices of a signed graph such that there exists such an embedding in \mathbb{R}^n. Finally, I will present interesting questions that are still open about this problem.

Posted on Aug 1, 2018 in ACGO, Seminars