9512.net

# On a Convex Operator for Finite Sets

ON A CONVEX OPERATOR FOR FINITE SETS

arXiv:math/0606371v1 [math.MG] 15 Jun 2006

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK Abstract. Let S be a ?nite set with n elements in a real linear space. Let JS be a set of n intervals in R. We introduce a convex operator co(S, JS ) which generalizes the familiar concepts of the convex hull conv S and the a?ne hull a? S of S . We establish basic properties of this operator. It is proved that each homothet of conv S that is contained in a? S can be obtained using this operator. A variety of convex subsets of a? S can also be obtained. For example, this operator assigns a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For JS which consists of bounded intervals, we give the upper bound for the number of vertices of the polytope co(S, JS ).

1. Introduction Let d be a positive integer and let L be a real linear space of dimension d. Let S = {x1 , . . . , xm } be a ?nite set of distinct points in L. The familiar convex sets associated with S are the convex hull of S
m m

(1.1)

conv S =
j =1

ξj xj : xj ∈ S, ξj ≥ 0,

ξj = 1
j =1

and the a?ne hull of S
m m

a? S =
j =1

ξj xj : xj ∈ S, ξj ∈ R,

ξj = 1 .
j =1

The set in (1.1) will not change if the conditions ξj ≥ 0 are replaced by the conditions ξj ∈ [0, 1], j = 1, . . . , m. This leads us to ask the following natural question: How will the set on the right-hand side of (1.1) change when the conditions ξj ≥ 0 are replaced by the conditions ξj ∈ Ij , j = 1, . . . , m, where Ij are arbitrary nonempty intervals in R? An immediate and obvious answer is that the resulting set will always be a subset of a? S . In this article we explore this question further. That is, we study the subsets of L introduced by the following de?nition. De?nition 1.1. Let S = {x1 , . . . , xm } be a ?nite set of distinct points in a linear space L. Let JS = {I1 , . . . , Im } be a family of nonempty intervals in R (some of which can be degenerated to a singleton) such that the interval Ij is associated with the point xj for each j ∈ {1, . . . , m}. Set
m m

co(S, JS ) :=

j =1

ξj xj : xj ∈ S, ξj ∈ Ij ,

ξj = 1 .
j =1

This set we call a convex interval hull of S .
1991 Mathematics Subject Classi?cation. Primary 52A05.
1

2

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

It is clear that the convex interval hull co(S, JS ) coincides with conv S when all the intervals in JS are equal to [0, 1] and co(S, JS ) coincides with a? S when all the intervals in JS are equal to R. In this sense co(S, JS ) generalizes these two well-known concepts. Our primary interest in this article is to explore the family of all convex interval hulls co(S, JS ) which are bounded. Examples in Section 2 show that a variety of convex sets appear in such families even if S is ?xed. It is quite striking that when S is the set of only 4 points: the vertices and the orthocenter of an equilateral triangle, for example √ √ S = ?1, 0 , 0, 1 , 0, 3 , 0, 1/ 3 , and when JS = [0, 1], [0, 1], [0, 1], 1 ? √ √ 3, ?2 + 3 ,

then co(S, JS ) is a regular dodecagon; see Figure 12. An inverse problem in this setting is as follows: For a given convex set K ?nd a ?nite set S with minimal cardinality and a family JS of intervals such that K = co(S, JS ). Examples 2.7 and 2.10 suggest solutions of the inverse problem for K equal to a regular dodecagon and for K equal to a rhombic dodecahedron. This inverse problem and unbounded convex interval hulls will be considered elsewhere. Let m be a positive integer. For a ?xed family J of m nonempty intervals in R our operator S → co(S, J ) is a set-valued function de?ned on ?nite subsets of L with m elements. Recall that many set-valued functions f considered in convexity theory are described in the following way: (1.2) f (X ) = F ∈F : X?F , X ? L,

where F is a prescribed family of subsets of L. The convex hull itself and many well-known generalizations of it are obtained in this way, see for example [2] and [6]. An immediate consequence of de?nition (1.2) is the inclusion X ? f (X ). From examples in Section 2 and our results in Section 6 it is clear that the convex interval hull does not always satisfy the inclusion S ? co(S, JS ). As a matter of fact, for every set S there are families of intervals JS for which S is not a subset of co(S, JS ). In this sense our operator di?ers from operators described by (1.2). De?nitions similar to De?nition 1.1 appeared in [4] and [5]. We recall the following three de?nitions from [5, p. 363]. First, for nonempty sets Λ ? Rm and S ? L denote by Λ · S ? L the set of all m j =1 λj sj , where (λ1 , . . . , λm ) ∈ Λ and sj ∈ S, j = 1 . . . , m. Second, a set S ? L is called endo -Λ if Λ · S ? S . Third, with F being the family of all endo-Λ sets, (1.2) de?nes the Λ-hull operator. A special case of Λ-hull operator with Λ = (ξ, 1 ? ξ ) : ξ ∈ ? ? R2 , where ? is any nonempty subset of [0, 1] containing at least one point interior to [0, 1], was considered in [4]. In [4] endo-Λ sets are called ?-convex sets. (We notice that Motzkin in [5] does not refer to [4].) In this paragraph we point out the di?erences between the de?nitions of Λ · S and co(S, JS ). To this end, let Λ be the intersection of I1 × · · · × Im and the hyperplane m j =1 ξj = 1, where Ij are nonempty intervals in R, and let S = {x1 , . . . , xm }, where x1 , . . . , xm are distinct points in L. Then, in general, Λ · S contains more linear combinations than co(S, JS ). The ?rst reason for this is that, with ξ1 , . . . ξm ∈ Λ, m m j =1 ξj xj ∈ co(S, JS ) it is j =1 ξj sj ∈ Λ · S whenever s1 , . . . , sm ∈ S , while for

CONVEX OPERATOR

3

essential that x1 , . . . , xm are distinct points in S . For example, with s1 = · · · = m sm = s ∈ S , the condition j =1 ξj = 1 implies S ? Λ · S , while S ? co(S, JS ) is not true in general. The second reason is that in the de?nition of co(S, JS ) the point xj ∈ S , for ?xed j ∈ {1, . . . , m}, is scaled only by scalars in Ij , while there is no such restriction in the de?nition of Λ · S . We also remark that the geometry of the sets Λ · S and the properties of the operator S → Λ · S for a ?xed Λ were not considered in [4] and [5]. The article is organized as follows. In Section 2 we give several illustrative examples of convex interval hulls in R2 and R3 for sets S with three, four and ?ve points. A justi?cation for the adjective “convex” in the name of co(S, JS ) begins Section 3. Furthermore, in this section we characterize nonemptyness and boundedness of co(S, JS ). In Section 4 we prove that all bounded convex interval hulls are polytopes. We also give an upper bound for the number of vertices of such polytopes. As we have already noticed, di?erent families of intervals can result in the same convex interval hulls. In Section 5 we study minimality conditions for a family of intervals, where minimality is understood in such a way that any further shrinking of intervals results in a smaller convex interval hull. In Section 6 we prove that a family of bounded convex interval hulls of a ?xed ?nite set S is invariant under homotheties. As a special case of this result we obtain that for each homothet K of conv S there exists a family of intervals JS such that K = co(S, JS ). We use this result to give a detailed description of bounded convex interval hulls of ?nite a?nely independent subsets of a linear space. In this paragraph we introduce the notation. By R we denote the real numbers. The symbol L denotes a real linear space and · is a norm in this space. A speci?c linear space that we will encounter is Rm , where m is a positive integer. The linear operations from L are extended to subsets of L in the following standard way. For subsets K and M of L and α, β ∈ R we put For a mapping T : L → L, T (K ) denotes the set of all T x, x ∈ K . 2. Examples In this section we present several examples of convex interval hulls. All examples here are bounded sets, since our main interest in this article are convex interval hulls which are bounded sets. We will consider unbounded convex interval hulls elsewhere. For completeness we start with the standard example. Example 2.1. Let S = {x1 , . . . , xm } be a ?nite set of points in a linear space L and let JS = {I1 , . . . , Im } with Ij = [0, tj ], where tj ≥ 1, j = 1, . . . , m. Then The examples below are calculated and plotted using Mathematica. In each example the points of the set S are listed starting from the lowest point that is furthermost to the left. Then we proceed counterclockwise, ?nishing with the point inside. In each ?gure the points in S are marked with black dots (?) and the polygon co S, JS is shaded gray with its edges slightly darker. Example 2.2. In Figures 1 and 2, we use S = (0, 0), (1, 0), (0, 1) . In Fig. 1 we use JS = [?1, 1], [0, 1], [0, 1] to get a square and in Fig. 2 we use JS = [0, 1], [0, 2/3], [0, 2/3] to get an irregular pentagon. co(S, JS ) = conv S. αK + βM = αx + βy : x ∈ K, y ∈ M .

4

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

Figure 1. A square

Figure 2. A pentagon

Figure 3. A regular hexagon

Figure 4. A regular pentagon

Figure 5. A regular octagon

Figure 6. A nonagon

CONVEX OPERATOR

5

Example 2.3. In Fig. 3 we use √ S = (?1, 0), (0, 1), (0, 3) to get a regular hexagon. Example 2.4. In Fig. 4 we use

and JS = [0, 2/3], [0, 2/3], [0, 2/3] ,

√ √ √ 0, ?5 ? 2 5 , 10 + 2 5, 5 , 0, 5 , ? √ JS = [0, 3 ? 5], [0, 2], [?1, 1], [0, 2] , S= to get a regular pentagon.

√ √ 10 + 2 5, 5

,

Example 2.5. In Fig. 5 we use S = (0, 0), (1, 0), (1, 1), (0, 1) and JS that consists √ of four copies of the interval 0, 2/2 to get a regular octagon. Example 2.6. In Fig. 6 we use √ √ ?1, 0 , 0, 1 , 0, 3 , 0, 1/ 3 , √ JS = [0, 1], [0, 1], [0, 1], ( 3 ? 3)/2, 1 , S= to get an irregular nonagon with all equal sides. Example 2.7. In Figures 7 through 12 we show six di?erent convex interval hulls corresponding to the same set S that is used in Example 2.6. We start with an equilateral triangle in Fig. 7 and proceed by changing one interval at each step to ?nish with a regular dodecagon in Fig. 12. We use the following families of intervals: Fig. 7 Fig. 8 Fig. 9 Fig. 10 Fig. 11 Fig. 12 JS = [0, 2], [0, 2], [0, 2], [?1, 0] ,

JS = [0, 1], [0, 1], [0, 1], [?1, 0] , √ JS = [0, 1], [0, 1], [0, 1], [1 ? 3, 0] , √ √ JS = [0, 1], [0, 1], [0, 1], [1 ? 3, ?2 + 3 ] . √ √ ?1, 0, 0 , 1, 0, 0 , 0, 3, 0 , 0, 1/ 3, 2

JS = [0, 1], [0, 1], [0, 2], [?1, 0] ,

JS = [0, 1], [0, 2], [0, 2], [?1, 0] ,

Example 2.8. In Fig. 13 we use S= 2/3

and JS that consists of four copies of 0, 2/3 to get a truncated tetrahedron. Notice that the points of S are vertices of a tetrahedron. Example 2.9. In Fig. 14 we use S= JS = to get a cube. 0, 0, 0 , 1, 0, 0 , 0, 1, 0 , 0, 0, 1 ?2, 1 , 0, 1 , 0, 1 , 0, 1

6

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

Figure 7. Step 1

Figure 8. Step 2

Figure 9. Step 3

Figure 10. Step 4

Figure 11. Step 5

Figure 12. A regular dodecagon

CONVEX OPERATOR

7

Figure 13. A truncated tetrahedron

Figure 14. A cube

Figure 15. A rhombic dodecahedron Example 2.10. In Fig. 15 we use S= JS =

Figure 16. Example 2.11

√ 1 ?1, 0, 0 , 1, 0, 0 , 0, 3, 0 , 0, √ , 2 3 0, 1 , 0, 1 , 0, 1 , 0, 1 , ?2, 0

2 3

1 1 , 0, √ , √ 3 6

to get a rhombic dodecahedron. The ?rst four points of S are vertices of a tetrahedron and the ?fth point is its orthocenter. Example 2.11. In Fig. 16 we use the same S as in Example 2.10 and JS = 0, 1 , 0, 1 , 0, 1 , 0, 1 , ?1/2, 0 .

8

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

3. Basic properties of convex interval hulls In this section most proofs are omitted since they are, though sometimes lengthy, straightforward consequences of the de?nitions. The proofs that are included indicate how to construct the omitted proofs. Proposition 3.1. Let S = {x1 , . . . , xm } be a ?nite set of points in a linear space L and let JS = {I1 , . . . , Im }, Ij ? R, j = 1, . . . , m, be a family of nonempty intervals. Then the set co(S, JS ) is convex. Proposition 3.2. Let S = {x1 , . . . , xm } be a ?nite set of points in a linear space L and let JS = {I1 , . . . , Im }, Ij ? R, j = 1, . . . , m, be a family of nonempty intervals. ′ ′ ′ ′ If JS = {I1 , . . . , Im } is a family of nonempty intervals such that Ij ? Ij , j = 1, . . . , m, then
′ ) ? co(S, JS ). co(S, JS

Proposition 3.3. Let S = {x1 , . . . , xm } be a ?nite set of points in a linear space L and let JS = {I1 , . . . , Im }, Ij ? R, j = 1, . . . , m, be a family of nonempty intervals. Put aj = inf Ij and bj = sup Ij , j = 1, . . . , m, allowing for the in?nite values. Let m m α = j =1 aj and β = j =1 bj . Then co(S, JS ) = ? if and only if the following three conditions are satis?ed: (a) (b) (c) α ≤ 1 ≤ β; if α = 1, then aj ∈ Ij , j = 1, . . . , m; and if β = 1, then bj ∈ Ij , j = 1, . . . , m.

Proof. Assume co(S, JS ) = ?. Then there exist ξj ∈ Ij , j = 1, . . . , m, such that m j =1 ξj = 1. Since aj ≤ ξj ≤ bj , j = 1, . . . , m, it follows that α ≤ 1 ≤ β . This proves (a). If α = 1, then aj = ξj , and thus aj ∈ Ij , j = 1, . . . , m. This proves (b) and (c) is proved similarly. To prove the converse assume that (a), (b) and (c) hold. If α = β = 1, then each of the intervals is in fact a point and co(S, JS ) consists of a single point. Now assume α < β . It follows from Proposition 3.2 that without loss of generality we can in addition assume that α and β are ?nite. Set ξj = 1?α β?1 aj + bj , β?α β?α j = 1, . . . , m.
m

It easily follows that ξj ∈ Ij , j = 1, . . . , m, and j =1 ξj = 1. Therefore x = m j =1 ξj xj ∈ co(S, JS ). Thus co(S, JS ) = ? and the proposition is proved. Theorem 3.4. Let S = {x1 , . . . , xm } be a ?nite set of distinct points in a linear space L and let JS = {I1 , . . . , Im }, Ij ? R, j = 1, . . . , m, be a family of nonempty intervals. The set co(S, JS ) is bounded if and only if at least one of the conditions below is satis?ed. (i) All the intervals in JS are bounded below. (ii) All the intervals in JS are bounded above. (iii) At most one interval in JS is unbounded.

If any of the conditions (i)-(iii) is satis?ed, then there exists a family of bounded ′ ′ intervals JS such that co(S, JS ) = co(S, JS ).

CONVEX OPERATOR

9

Proof. We ?rst show that if all the intervals in JS = {I1 , . . . , Im } are bounded, then co(S, JS ) is bounded. Indeed, if for some b > 0 we have Ij ? [?b, b] for all j = 1, . . . , m, then for each x ∈ co(S, JS ) we have
m

x =
j =1

ξj xj

≤ m b max

x1 , . . . , xm

.

Next we assume (i). Let a ∈ R be such that Ij ? (a, +∞) for all j = 1, . . . , m. Since the empty set is bounded, we assume co(S, JS ) = ?. By Proposition 3.3, we have ma < 1. Let x ∈ co(S, JS ). Then there exist ξj ∈ Ij , j = 1, . . . , m, such that m m j =1 ξj xj . Let k ∈ {1, . . . , m} be arbitrary. Then j =1 ξj = 1 and x =
m

ξk = 1 ? Therefore

j =k

ξj < 1 ? (m ? 1)a = 1 ? ma + a.

a < ξk < 1 ? ma + a. ′ ′ ′ ′ Hence, with b′ = min { 1 ? ma + a, bk }, Ik = [ak , b′ k k ] and JS = {I1 , . . . , Im }, we have ′ proved that co(S, JS ) ? co(S, JS ). By Proposition 3.2 the converse inclusion is also ′ ′ true. Consequently co(S, JS ) = co(S, JS ). Since each interval in JS is bounded, ′ the set co(S, JS ) is bounded. Thus co(S, JS ) is bounded, as well. Similarly, (ii) implies that co(S, JS ) is bounded. Assume (iii). We can also assume that (i) and (ii) are not true. Then exactly one of the intervals in JS is unbounded and it equals R. Assume that I1 = R and m Ij = [aj , bj ], aj ≤ bj , aj , bj ∈ R, j = 2, . . . , m. Put α = m j =2 aj and β = j =2 bj . Clearly α ≤ β . Let v ∈ co(S, JS ) be such that
m m

v=
j =1

ξj xj ,
j =1

ξj = 1,

ξj ∈ Ij ,

j = 1, . . . , m.

Then 1 ? β ≤ ξ1 = 1 ? ξ2 ? · · · ? ξm ≤ 1 ? α. ′ ′ Consequently v ∈ co(S, JS ), where JS = [1 ? β, 1 ? α], I2 , . . . , Im . Therefore ′ co(S, JS ) ? co(S, JS ). The converse inclusion holds by Proposition 3.2. Therefore ′ ′ ′ co(S, JS ) = co(S, JS ). Since each interval in JS is bounded, the set co(S, JS ) is bounded and so is co(S, JS ). This completes the proof of ”if” part of the theorem. Next we prove the contrapositive of the “only if” part of the theorem. Assume that (i), (ii) and (iii) are all false. This is equivalent to the fact that the family JS contains at least two unbounded intervals, say I1 and I2 , such that I1 is not bounded from below and I2 is not bounded from above. Let v ∈ co(S, JS ) be such that
m m

v=
j =1

cj xj ,
j =1

cj = 1 ,

cj ∈ Ij ,

j = 1, . . . , m.

Then (?∞, c1 ] ? I1 Consequently, for all t ≥ 0, Clearly and [c2 , +∞) ? I2 .

(c1 ? t)x1 + (c2 + t)x2 + c3 x3 + · · · + cm xm = v + t(x2 ? x1 ) ∈ co(S, JS ). v + t(x2 ? x1 ) ≥ t x2 ? x1 ? v , t ≥ 0.

10

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

Since by assumption x1 = x2 , the last inequality implies that co(S, JS ) is unbounded. The theorem is proved. Proposition 3.5. Let T : L → K be an a?ne transformation between linear spaces L and K. Let S = x1 , . . . , xm be a ?nite subset of L and let JS = I1 , . . . , Im be a corresponding set of intervals for which co(S, JS ) is bounded. Let Q = T (S ) = {y1 , . . . , yk } be the set with k elements, where k ≤ m. Set
′ ′ , . . . , Ik JQ = I1

where

′ Ij :=

Ii : T xi = yj .

Then co Q, JQ = T co(S, JS ) . Each vertex of T co(S, JS ) is an image of a vertex of co(S, JS ). Proposition 3.6. Let S be a ?nite subset of L and let T : L → L be an a?ne bijection such that T (S ) = S . Assume that JS has the property that Ij = Ik whenever xj = T xk . Then T co(S, JS ) = co(S, JS ). Corollary 3.7. Let S ? L be a ?nite set centrally symmetric with respect to u ∈ L. Assume that JS has the property that Ii = Ij for xi and its symmetric image xj . Then co(S, JS ) is also centrally symmetric with respect to u. 4. Convex interval hulls and polytopes Example 2.7 shows that a convex interval hull of four points can have twelve vertices. In the next theorem we give an upper bound for the number of vertices of a convex interval hull for a ?nite set with m points. For a real number t, ?t? denotes the greatest integer that does not exceed t. Theorem 4.1. Let S = {x1 , . . . , xm } be a subset of L and let JS be a family of closed intervals such that co(S, JS ) is bounded. Then co(S, JS ) is the convex hull of at most n m n points, where n= m +1 2

and this bound is best possible. Proof. It follows from Proposition 3.3 that there is no loss of generality if we assume that all the intervals in JS are bounded. Set Ij = [aj , bj ], aj < bj , j = 1, . . . , m, m and, as before, set α = j =1 aj . Clearly, for α = 1 the set co(S, JS ) is a singleton and the theorem is trivial in this case. Therefore, we can assume that α < 1. In order to prove the theorem we will show that co(S, JS ) is an image under an a?ne transformation of a polytope in Rm having not more than n m n vertices. To this end take the unit vectors e1 , . . . , em in Rm and put Q= 1?α 1?α e1 , . . . , em b 1 ? a1 b m ? am
′ where Ij = 0,

assigning to Q the family of intervals
′ ′ JQ = I1 , . . . , Im ,

b j ? aj , j = 1, . . . , m. 1?α

CONVEX OPERATOR

11

This, after a straightforward substitution ηj ? ?
m

For such Q and JQ we have ? ? co Q, JQ = ?

m

ηj
j =1

1?α ′ ej : ηj ∈ Ij , b j ? aj

m

ηj = 1
j =1

? ? ?

.

co Q, JQ

Therefore, if v is a vertex of D, then v must be on an edge of C . Clearly, if e is an edge of C intersecting Π but not lying on Π, then there can be only one vertex of D on e. By [1, Theorem 5] a hyperplane can intersect at most n m n edges of C . Consequently, from the two observations it follows that D has at most n m n vertices. Now consider the a?ne transformation T : Rm → L de?ned as follows
m m m

where C is the unit hypercube in R . From the above it is immediately seen that co Q, JQ = D is the intersection of the hypercube C and the hyperplane ? ? m ? ? (bj ? aj ) ?j = 1 ? α . Π := (?1 , . . . , ?m ) ∈ Rm : ? ?
j =1

? ? (bj ? aj ) ?j = 1 ? α ?j ej : 0 ≤ ?j ≤ 1 , = ? ? j =1 j =1 ? ? m ? ? (bj ? aj ) ?j = 1 ? α , = (?1 , . . . , ?m ) ∈ C : ? ?
m j =1 m

1?α = ?j , gives b j ? aj

T :
j =1

ζj ej →

aj xj +
j =1 j =1

(bj ? aj ) ζj xj ,

(ζ1 , . . . , ζm ) ∈ Rm . ?

Calculating T (D) we obtain ?
m m

1?α ′ ηj T (D) = T ? ej : ηj ∈ Ij , b ? a j j j =1
m

m

j =1

ηj = 1 ?
m

=
j =1 m

aj xj +
j =1

′ (1 ? α) ηj xj : ηj ∈ Ij , m

ηj = 1
j =1

=
j =1

′ , aj + (1 ? α) ηj xj : ηj ∈ Ij

ηj = 1 .
j =1

Substituting ξj = aj + (1 ? α) ηj , j = 1, . . . , m, and using two facts: the ?rst one ′ that ξj ∈ [aj , bj ] if and only if ηj ∈ Ij and the second that
m m

ξj =
j =1 j =1 m

aj + (1 ? α) ηj = α + 1 ? α = 1,
m

we get T (D) =
j =1

ξj xj : ξj ∈ [aj , bj ],

ξj = 1
j =1

= co(S, JS ).

12

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

It follows now from Proposition 3.5 that T (D) has fewer vertices than D. Since D m has at most n m n vertices we conclude that co(S, JS ) has at most n n vertices. To show that the bound is best possible we provide an example in which co(S, JS ) m has exactly n m and n vertices. Take S = {e1 , . . . , em } ? R JS = I1 , . . . , Im , where Ij = 0, 2 , j = 1, . . . , m. 2(m ? n) + 1

Similarly as above we can check that co(S, JS ) = D1 is the intersection of C and the hyperplane H= (ζ1 , . . . , ζm ) ∈ Rm : ζ1 + · · · + ζm = m ? n + 1 2 .

One can immediately check that H intersects exactly n m n edges of C at the points whose m ? n coordinates are equal to 1, n ? 1 coordinates are equal to 0 and exactly one coordinate is equal to 1/2. It is easy to see that no three such points are collinear. Similarly as in the case of D, all the vertices of D1 must be the points of intersection of H and edges of C . Clearly, no edge of C lies on H . Therefore the intersection of H and C has exactly n m n vertices. Since co(S, JS ) coincides with the intersection of the hyperplane H and C it has exactly n m n vertices. The proof of the theorem is complete. Remark 4.2. In the proof of Theorem 5 in [1] the hyperplane is mentioned as one which makes the bound n m best possible. In fact, this n m hyperplane contains n vertices of C . Since each vertex belongs to exactly n edges it could be argued that the hyperplane Πn intersects n m n edges of C . Note that our hyperplane H actually intersects n m edges of C at distinct points. n The subsequent theorem shows that in special cases the number of vertices of co(S, JS ) cannot be too large. We will need an additional de?nition. A family JS = {Ij = [aj , bj ] , j = 1, . . . , m} is called wide if dk + dj > 1 ? α for all k = j , m where di = bi ? ai and α = i=1 ai . One can easily check that the family JS considered in the example ?nishing the proof of Theorem 4.1 is wide only when n = 3 or n = 4 and in both cases the maximal number of vertices of co(S, JS ) guaranteed by Theorem 4.1 is the same as the one guaranteed by the following theorem. Theorem 4.3. Let S = {x1 , . . . , xm } be a subset of distinct points in L. Assume that JS = {Ij = [aj , bj ] : j = 1, . . . , m} is a wide family of intervals, with aj < bj < 1 ? α + aj and α < 1. Then co(S, JS ) is the convex hull of at most m(m ? 1) points and this bound is best possible. Proof. Similarly as in the proof of Theorem 4.1 we shall show that co(S, JS ) is an image upon a linear transformation of a polytope, call it B , having m(m ? 1) vertices and lying in the hyperplane Π1 = (ξ1 , . . . , ξm ) ∈ Rm : ξ1 + ξ2 + · · · + ξm = 1 . To construct B , we ?rst consider the points vj = (a1 , . . . , 1 ? α + aj , . . . , am ), j = 1, . . . , m, Πn = {(ζ1 , . . . , ζm ) ∈ Rm : ζ1 + · · · + ζm = n}

CONVEX OPERATOR

13

lying on Π1 . Clearly, ? = conv{v1 , . . . , vm } is a fully dimensional simplex in Π1 . De?ne + + + B = ? ∩ H1 ∩ H2 ∩ · · · ∩ Hm in which + Hj = {(ξ1 , . . . , ξm ) ∈ Rm : ξj ≤ bj }, j = 1, . . . , m, is the halfspace bounded by the hyperplane There are m ? 1 edges of ? emanating from a vertex vj of ?. Clearly, each one k of these edges intersects the hyperplane Hj at a point vj , k = j . It is easy to check that k vj = (a1 , . . . , bj , . . . , ck , . . . , am ), k = j, where ck = 1 ? α ? dj + ak . Thus, each intersection ?j = ? ∩ Hj , j = 1, . . . , m, is j ?1 j +1 1 2 m . , vj , . . . , vj a simplex with m ? 1 vertices vj , vj , . . . , vj Now we shall check that every vertex of any simplex ?j , j = 1, . . . , m, is a vertex + k k of B . Indeed, take vj = (a1 , . . . , bj , . . . , ck , . . . , am ), k = j . Obviously vj ∈ ? ∩ Ht + k for t = k . To show that also vj ∈ ? ∩ Hk we need to check that ck (the k -th k coordinate of vj ) is less than bk . This is true since the inequality is equivalent to ck = 1 ? α ? dj + ak < bk Hj = (ξ1 , . . . , ξm ) ∈ Rm : ξj = bj .

1 ? α < bk ? ak + dj = dk + dj and the latter inequality is true because the family JS is wide. In this way we have shown that every vertex of ? gives rise to m ? 1 vertices of B . Thus B is a polytope with m(m ? 1) vertices. Now consider a linear transformation TS : Rm → L de?ned by
m

TS (ξ1 , ξ2 , . . . , ξm ) :=
j =1

ξj xj .

We want to show that co(S, JS ) = TS (B ). The inclusion TS (B ) ? co(S, JS ) simply follows from the de?nitions given above. To show the reverse inclusion suppose to the contrary that there exists Of course, z = ?j xj for some ?1 , . . . , ?m such that aj ≤ ?j ≤ bj , j = 1, . . . , m, m and j =1 ?j = 1. Obviously,
m m j =1

z ∈ co(S, JS ) \ TS (B ).

(?1 , . . . , ?m ) ∈ Π1 ∩

j =1

+ Hj \ B.

From the de?nition of B it follows now that (?1 , . . . , ?m ) ∈ ?. As ? is a fully dimensional simplex in Π1 we have (4.1) From (4.1) we get (4.2) (?1 , . . . , ?m ) ∈ a? {v1 , . . . , vm } \ conv{v1 , . . . , vm }.
m

(?1 , . . . , ?m ) =
j =1

λj vj

14

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK m

for some numbers λ1 , . . . , λm , satisfying j =1 λj = 1, among which at least one does not belong to the interval [0, 1]. In connection with the last observation we infer that there exists i0 such that λi0 < 0. It is easy to check that (4.2) is equivalent to which gives (?1 , . . . , ?m ) = (a1 + λ1 (1 ? α), . . . , am + λm (1 ? α)), ?i0 = ai0 + λi0 (1 ? α) < ai0

and contradicts the condition ai0 ≤ ?i0 ≤ bi0 . Thus co(S, JS ) ? TS (B ) and consequently co(S, JS ) = TS (B ). Therefore co(S, JS ) cannot have more than m(m ? 1) vertices. Next we show that the number m(m ? 1) is attained for wide families. Let e1 , . . . , em be the unit vectors in Rm . De?ne S = { e 1 , . . . , em } , where Ij = 0, 2/3 , j = 1, . . . , m. JS = I1 , . . . , Im ,

Clearly JS is a wide family and co(S, JS ) has exactly m(m ? 1) vertices. 5. Minimal families of intervals The convex interval hull of a set S essentially depends on the family of intervals JS associated with S . In Example 2.1 we saw that the convex interval hull produced by the family JS of intervals [0, tj ] with tj > 1 produces the same convex interval hull as the family of intervals [0, 1]. This observation indicates that the latter family is in some sense minimal. In this section we de?ne and explore the minimality of families of intervals. De?nition 5.1. Let S be a ?nite set of points in L. A family of intervals JS = I1 , . . . , Im is a minimal interval family for the set S if
′ ′ ′ ′ , Ij ? Ij , j = 1, . . . , m, JS = I1 , . . . , Im

and imply that
′ co(S, JS ) = co(S, JS ) ′ Ij = Ij , j = 1, . . . , m.

De?nition 5.2. Let J = I1 , . . . , Im be a family of bounded intervals such that m Ij = [aj , bj ], aj ≤ bj , j = 1, . . . , m. Set α = m j =1 aj and β = j =1 bj . The family J is called irreducible if bk ? ak ≤ min{1 ? α, β ? 1} for all k = 1, . . . , m. Let, as before,
m m

J = I1 , . . . , Im , Ij = [aj , bj ], j = 1, . . . , m, α =

aj , β =
j =1 j =1

bj ,

and assume α ≤ 1 ≤ β . In the rest of this section we will use the following notation. With the family J we associate the following family J :
m m

J = I1 , . . . , Im , Ij = [aj , bj ], j = 1, . . . , m, α =

aj , β =
j =1 j =1

bj ,

CONVEX OPERATOR

15

where aj = max aj , bj ? (β ? 1) , bj = min bj , aj + (1 ? α) . Since we assume α ≤ 1 ≤ β , we clearly have (5.1) aj ≤ aj ≤ b j ≤ b j , j = 1, . . . , m. The following implication is straightforward: if J is irreducible, then J = J . In the next lemma we study the relationship between J and J further. Among other statements we prove the converse of the last implication. We set Π1 = ζ1 , . . . , ζm ∈ Rm : ζ1 + · · · + ζm = 1 .

Lemma 5.3. Let J = I1 , . . . , Im , Ij = [aj , bj ], j = 1, . . . , m, be a family of m m bounded intervals. Set α = j =1 aj and β = j =1 bj and assume α ≤ 1 ≤ β . The following three statements hold. (a) Let k ∈ {1, . . . , m}. The projection of the set I1 × · · · × Im ∩ Π1 ? Rm to the k -th coordinate axes in Rm is the interval Ik = ak , bk . (b) I1 × · · · × Im ∩ Π1 = I1 × · · · × Im ∩ Π1 . (c) The family J is irreducible. Proof. The statement (a) claims the equality of two sets. To prove it, let Then ξ1 , . . . , ξm ∈ I1 × · · · × Im ∩ Π1 .
m m

ξk = 1 ? and ξk = 1 ?

j =1,j =k m

ξj ≤ 1 ?

j =1,j =k m

aj = 1 ? α ? ak

j =1,j =k

ξj ≥ 1 ?

j =1,j =k

bj = 1 ? β ? bk .

Since ak ≤ ξk ≤ bk , it follows that ak ≤ ξk ≤ bk . This proves that the projection onto k -th coordinate is contained in the interval Ik . For simplicity of notation, we will prove the converse inclusion for k = 1. Let ξ1 ∈ I1 . Then and consequently (5.2) Since the function 1 ? min b1 , a1 + 1 ? α ≤ 1 ? ξ1 ≤ 1 ? max a1 , b1 ? β + 1 α ? a1 ≤ 1 ? ξ1 ≤ β ? b1 .
m

ζ2 , . . . , ζm →

ζj
j =2

is a continuous function on I2 ×· · ·× Im with the minimum α ? a1 and the maximum β ? b1 , its range is α ? a1 , β ? b1 . Now (5.2) implies that there exists such that
m j =2 ξj

= 1 ? ξ1 . Thus

ξ2 , . . . , ξm ∈ I2 × · · · × Im

ξ1 , . . . , ξm ∈ I1 × · · · × Im ∩ Π1 ,

16

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

and (a) is proved. The statement (b) follows from the fact that (a) holds for all k = 1, . . . , m, and Ik ? Ik . To prove (c), we notice that (b) implies that for each k = 1, . . . , m, the projection of I1 ×· · ·× Im ∩ Π1 to the k -th coordinate axes in Rm is the interval Ik = ak , bk . Furthermore, an application of (a) to the family J yields that the same projection is the interval max ak , bk ? (β ? 1) , min bk , ak + (1 ? α) Consequently, and hence ak = max ak , bk ? (β ? 1) , ak ≥ bk ? (β ? 1), bk = min bk , ak + (1 ? α) , bk ≤ ak + (1 ? α). .

This implies that J is irreducible and the lemma is proved.

Proposition 5.4. Let S be a ?nite subset of L and let JS be a corresponding family of bounded intervals such that co(S, JS ) = ?. Then co(S, JS ) = co(S, JS ). Proof. The proposition follows from (b) in Lemma 5.3. Theorem 5.5. Let S be a ?nite subset of L and let JS be a corresponding family of bounded intervals such that co(S, JS ) = ?. If JS is a minimal family for S , then JS is irreducible. Proof. We prove the contrapositive. Assume that S has m elements and let JS = I1 , . . . , Im . Assume further that JS is not irreducible. Then there exists k ∈ {1, . . . , m} such that Ik is a proper subset of Ik . But co(S, JS ) = co(S, JS ) by Proposition 5.4. Since Ij ? Ij for all j = 1, . . . , m, JS is not a minimal family for S. The following example shows that the converse of Theorem 5.5 is not true. Example 5.6. Consider the set S of 4 points in R2 from Example 2.7. Let JS be the family of four copies of the interval [0, 1]. Then co(S, JS ) = conv S . The family JS is clearly irreducible, but it is not a minimal family for S , since the family ′ JS = [0, 1], [0, 1], [0, 1], [0, t] , for arbitrary t ∈ [0, 1), clearly produces the same convex interval hull. In the next theorem we show that for a?nely independent sets the converse of Theorem 5.5 holds true. Recall that a set S = {y1 , . . . , ym } of points in L is a?nely independent if and only if the a?ne mapping (5.3) is a bijection between Πm 1 ξ1 , . . . , ξm → ξ1 y1 + · · · + ξm ym and a? S .

Theorem 5.7. Let S be a ?nite a?nely independent subset of L and let JS be an associated family of bounded intervals. The family JS is a minimal family for S if and only if it is irreducible.

CONVEX OPERATOR

17

Proof. Let S be an a?nely independent set with m elements and JS = I1 , . . . , Im . We prove the contrapositive of the “if” part of the theorem. Assume that JS is not a minimal family for S . Then there exist a family of intervals (5.4)
′ ′ ′ JS = I1 , . . . , Im

such that

′ ) = co(S, JS ), co(S, JS

′ Ij ? Ij , j = 1, . . . , m,

′ and there exists k ∈ {1, . . . , m} for which Ik is a proper subset of Ik . Setting ′ ′ ′ Ik = ak , bk , Ik = ak , bk , the last condition is equivalent to

(5.5)

′ b′ k ? ak < b k ? ak .

Since the mapping (5.3) is a bijection, (5.4) is equivalent to
′ ′ I1 × · · · × Im ∩ Π1 = I1 × · · · × Im ∩ Π1 . ′ = J . Therefore, by (5.1) and By Lemma 5.3(a), the last equality implies that JS S (5.5), ′ b k ? ak = b ′ k ? a′ k ≤ b ′ k ? ak < b k ? ak .

Hence JS = JS , and consequently JS is not irreducible. 6. The convex interval hull and the homothety
δ :L→L Let δ be a nonzero real number and v ∈ L. The transformation Hv de?ned by δ Hv (x) := v + δ x, x ∈ L,

is called a homothety. If δ > 0 the homothety is called positive and if δ < 0 the homothety is called negative. The number δ is called the ratio of the homothety. δ δ The image of K ? L under Hv is denoted by Hv (K ) and it is called a homothet of 0 K . It is convenient to set Hv (K ) = ?. Let S = {x1 , . . . , xm }, be a ?nite set of points in L. We are interested only in δ homotheties that map a? S to a? S . Let v ∈ L and δ = 0. Clearly Hv (a? S ) ? a? S if and only if there exist νj ∈ R, j = 1, . . . , m, such that
m m

(6.1)

v=
j =1

νj xj

and

δ =1?

νj .
j =1

Theorem 6.1. Let S = {x1 , . . . , xm } be a ?nite set of points in L and let JS = I1 , . . . , Im be a corresponding family of nonempty intervals. Let v ∈ L and δ = 0 δ be such that Hv (a? S ) ? a? S . Assume that (6.1) holds and set hj (t) = νj + δ t, t ∈ R. Then ′ δ , co(S, JS ) = co S, JS Hv where
′ ′ ′ ′ JS = {I1 , . . . , Im }, Ij = hj Ij , j = 1, . . . , m. ′ ′ δ co(S, JS ) , let y ∈ co S, JS Proof. To prove the inclusion co S, JS . Then ? Hv there exist ξj ∈ Ij , j = 1, . . . , m, such that m m

y=
j =1

hj ξj xj

and
j =1

hj ξj = 1.

18

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

Since, by (6.1),
m

ξj =
j =1

1 νj 1? δ j =1
m

m

= 1,

with x =

m j =1 ξj

xj ∈ co S, JS we have
m

m δ ξj xj = Hv (x). j =1

y=
j =1

νj + δ ξj xj =
j =1

νj xj + δ

The converse inclusion is proved similarly and the theorem is established. Corollary 6.2. Let S = {x1 , . . . , xm } be a ?nite set of points in L and let cj ∈ R m be such that γ = j =1 cj = 1. Set hj (t) = cj + (1 ? γ )t and
′ ′ ′ JS = I1 , . . . , Im

with

′ Ij = hj [0, 1] ,

j = 1, . . . , m.
m

Then
1?γ ′ conv S , = Hv co S, JS

where

v=
j =1

cj xj .

Remark 6.3. We continue to use the notation of Corollary 6.2. Further, we assume that cj ≥ 0, j = 1, . . . , m, and 0 < γ < 1. Simple algebra yields
1?γ (x) = v + (1 ? γ )x = Hv

1 1 v + (1 ? γ ) x ? v , γ γ

x ∈ a? S.

1 1?γ v is a ?xed point of Hv . Since 0 < 1 ? γ < 1 This expression shows that γ 1 1?γ conv S is a contraction of conv S and it is and γ v ∈ conv S the homotet Hv completely contained in conv S . The Gauss-Lucas theorem states that all the roots of the derivative of a complex non-constant polynomial p lie in the convex hull of the roots of p, called the Lucas polygon of p. The reasoning presented in Remark 6.3 was used in [3] to improve the Gauss-Lucas theorem by proving that all the nontrivial roots of the derivative of p lie in a convex polygon that is a strict contraction of the Lucas polygon of p and that is completely contained in it.

We conclude this article with a result motivated by Examples 2.2, 2.3, 2.8 and 2.9. It is clear that the convex interval hull co(S, JS ) in Figure 2 is the closure of a set di?erence of conv S and the union of two smaller homotets of conv S . Similarly, co(S, JS ) in Figure 1 is the closure of a set di?erence of a large homotet of conv S and the union of two smaller homotets of conv S . The reader will easily observe analogous properties of the convex interval hulls in Figures 3, 13 and 14. In Theorem 6.5 below we give a general result which explains these observations. Lemma 6.4. Let J = I1 , . . . , Im , Ij = [aj , bj ], j = 1, . . . , m, be an irreducible m family of intervals. Set α = m j =1 aj and β = j =1 bj and assume α ≤ 1 ≤ β . For k, j ∈ {1, . . . , m} de?ne
0 Ij = aj , aj + (1 ? α) ,

k Ij =

? ? aj , aj + (1 ? α) ? (bk ? ak ) ? b , a + (1 ? α) j j

for for

j = k, j = k.

CONVEX OPERATOR

19

Set B = I1 × · · · × Im Then B ∩ Bu = ? and (6.2) Π1 , Bu = Π1

m k k . I1 × · · · × Im

k=1

0 0 B ∪ Bu = I1 × · · · × Im

Π1 .

Proof. The equality B ∩ Bu = ? is obvious. Since J is irreducible we have bj ≤ 0 0 aj +1 ? α for all j = 1, . . . , m. Consequently B ∪ Bu is a subset of I1 ×· · ·× Im ∩ Π1 . To prove the converse inclusion in (6.2), let (6.3) and assume that (6.4) (6.5)
0 0 ∩ Π1 (ξ1 , . . . , ξm ) ∈ I1 × · · · × Im

Then there exists k ∈ {1, . . . , m} such that Next we prove the implication
m

(ξ1 , . . . , ξm ) ∈ / I1 × · · · × Im ∩ Π1 . ξk ∈ bk , ak + (1 ? α) .

(6.6)
j =1

ξj = 1 ? ξj ≤ aj + (1 ? α) ? (bk ? ak ) ? j ∈ {1, . . . , m} \ {k } .

Since the contrapositive is easier to prove, assume (6.7) Then, using (6.5) and (6.7), we ?nd
m

? l ∈ {1, . . . , m} \ {k } such that ξl > al + (1 ? α) ? (bk ? ak ). ξj > bk + al + (1 ? α) ? (bk ? ak ) + α ? ak ? al = 1,

j =1

and (6.6) is proved. Hence, we have shown that (6.3), (6.4) and (6.5) imply that ξj ∈ aj , aj + ≤ (1 ? α) ? (bk ? ak ) ? j ∈ { 1 , . . . , m} \ { k } .

This together with (6.5) implies that (ξ1 , . . . , ξm ) ∈ Bu and the lemma is proved. Theorem 6.5. Let S = {x1 , ..., xm } be an a?nely independent set in L. Let JS = I1 , . . . , Im , Ij = [aj , bj ], j = 1, . . . , m, be an irreducible family of intervals m and assume α = j =1 aj < 1. Then co S, JS is the closure of the set di?erence of the sets
m δ conv S Hv

and
j =1

j Hv + d j xj conv S

δ ?d

where v =

m j =1

aj xj , δ = 1 ? α, and dj = bj ? aj , j = 1, . . . , m.
m

Proof. The claim of the theorem is equivalent to the equality (6.8) co S, JS
j δ Hv + d j xj conv S = Hv conv S

δ ?d

j =1

together with the condition that the set co S, JS has no common interior points δ ?d j with the polytopes Hv+dj xj conv S , j = 1, . . . , m. To prove (6.8) and the stated

20

? BRANKO CURGUS AND KRZYSZTOF KOLODZIEJCZYK

condition we use Lemma 6.4 and the notation introduced there. For k = 1, . . . , m, set Since S is a?nely independent the a?ne mapping (6.9)
0 0 0 , JS = I1 , . . . , Im k k k , JS = I1 , . . . , Im

J S = I1, . . . , Im .

k

k

k

is a bijection between Π1 and a? S . Together with Lemma 6.4 this implies
m

ξ1 , . . . , ξm → ξ1 y1 + · · · + ξm ym

(6.10)

co S, JS

k=1

0 k = co S, JS co S, JS

and, for k = 1, . . . , m, co S, JS
k co S, JS = ?.

Since (6.9) de?nes a continuous mapping it follows that co S, J S is a closure of
k co S, JS . Therefore, for k = 1, . . . , m, the polytopes co S, J S and co S, JS have no common interior points. By Corollary 6.2 δ ?d k co S, J S = Hv +dk xk conv S k k

k

and

Substituting the last equations in (6.10) we get (6.8). The theorem is proved. References
[1] R. Ahlswede, Z. Zhang, An identity in combinatorial extremal theory. Adv. Math. 80 (1990), no. 2, 137–151. [2] V. Boltyanski, H. Martini and P. S. Soltan, Excursions into Combinatorial Geometry, Springer, 1997. ? [3] B. Curgus and V. Mascioni, A contraction of the Lucas polygon, Proc. Amer. Math. Soc. 132 (2004) no. 10, 2973-2981. [4] J. W. Green and W. Gustin, Quasiconvex sets, Canad. J. Math. 2 (1950), 489-507. [5] T. S. Motzkin, Endovectors, Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society: Convexity, 1963, 361-387. [6] M. L. J. van de Vel, Theory of convex structures, North-Holland, 1993. Department of Mathematics, Western Washington University, Bellingham, Washington 98226, USA E-mail address : curgus@cc.wwu.edu Institute of Mathematics and Computer Science, Wroclaw University of Technology, 50-370 Wroclaw, Poland E-mail address : Krzysztof.Kolodziejczyk@pwr.wroc.pl

0 δ co S, JS = Hv conv S .

convex closed set 单调的 monotonic 无穷 infinity ...operator 函子 functor 微分方程 differential equation...sets 有穷自动机 finite automaton 数学归纳法 ...

. (S1×S2×...×Sm) = ×i=1,…,m (Si) is a convex set. 1.9...4 . The union of open sets is open. . A finite intersection of open ...