3

I am working in convex geometry for the summer with little experience beforehand. It's a lot of fun but it does mean I don't know some of the basic things.

I know that it is not generally true that the union of convex sets is convex, but I think I've stumbled across a bunch of convex sets with convex union. Now I have no idea how I would prove this is actually true. Are there any strategies you have seen / can imagine, or any well-known examples of this phenomenon that I might look at for inspiration?

If it makes any difference, my sets are convex hulls of finite sets in $\Bbb R^n$, and each have the same combinatorial symmetries, but probably not any geometric symmetries (I mean, arising from an isometry). So they look like "squished" versions of highly regular polytopes. There are uncountably many of them, and no two are disjoint. The set that I believe they union to, also has these properties, although the symmetries it has are different.

Any pointers or references are appreciated!

Eric Stucky
  • 12,758
  • 3
  • 38
  • 69
  • 1
    One fairly simple case is if your family is such that the union of any finite subset is contained in a single member of the family. – Harald Hanche-Olsen Jun 10 '14 at 20:49
  • Could you give a more precise definition of your sets? It is difficult to imagine what is a "combinatorial but not geometric symmetry".

    I know what a combinatorial polytope is, but the fact that the union of a family of realizations of combinatorial polytopes is convex or not will strongly depend on the exact realizations.

     – Taladris Jun 16 '14 at 18:19

1 Answers1

2

If you can parameterize the sets as sublevel sets of a convex function, then you can show their union is convex.

That is, suppose the function $f(x,y)$ is convex (jointly in both $x$ and $y$), and define the sets:

$$ S_y := \{ x \ | \ f(x,y) \le 0 \} $$

Then each $S_y$ is convex. Further, the union of $S_y$, where $y$ ranges over some convex set $C$, is convex:

$$ S_C := \bigcup_{y \ \in \ C} S_y $$

This is related to fact that if you minimize over one variable of a convex function, the resulting function is convex. (See Sec. 3.2.5 of Boyd Vandenberghe). That is, the following function is convex.

$$ g_C(x) := \inf_{y \ \in \ C} f(x,y) $$

So (assuming $g_C > -\infty)$, the set $S_C$ is a sublevel set of a convex function: $$ S_C = \{ x \ | \ g_C(x) \le 0 \} $$ Therefore, $S_C$ is convex.

For example, if $f(x,y) = \|x-y\|_2 - 1$, then each $S_y$ is a ball of radius $1$ centered at $y$. In that case, $S_C$ is the set of points distance $1$ or less from $C$.

Granted, due to the combinatorial nature of your problem, this kind of parameterization might not be possible, but I figured I'd throw it out there anyway.

p.s.
  • 6,401