Long Cycles in Euclidean 2-Factors

From himtp
Revision as of 17:13, 27 September 2015 by Himuser (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(suggested by William Cook)

Given a set S of points in the plane, a minimum 2-factor is a collection of circuits such that every point in S is a member of exactly one circuit in the collection and the sum of the Euclidean lengths of the edges in the circuits is as small as possible. An example of a minimum 2-factor is shown in the figure below, where the 10,000 points were selected uniformly at random in the unit square.


Notice that one of the circuits, colored red, contains a large fraction of the point set (2,264 of the 10,000 points). The problem is to show that this happens with high probability. That is, given a collection of n points in the unit square, selected uniformly at random, and a minimum 2-factor F, does F have with high probability a circuit of length at least cn for some positive constant c?