Event № 214
The talk will concern the distance between two polytopes defined for every hypergraph: CP, the covering polytope, which is the convex hull of the characteristic vectors of the covers, and FCP, the fractional covering polytope, which is the set of all fractional covers. Clearly, the first is contained in the second. Given a direction u in space, we can measure the distance between CP and FCP in two ways. One is the ratio t/t*, where t (resp. t*) is smallest such that t u \in CP (resp. FCP). The (better known) second distance measure is the ratio s/s*, where s (resp. s*) is smallest such that a hyperplane perpendicular to u of distance s/|u| (resp. s*/|u|) from the origin meets CP (resp. FCP).
Partially joint work with Ron Aharoni and Ron Holzman