Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

4.3 A sandwich theorem

4.3 A sandwich theorem

Theorem 4.3.1 Let B be a family of parallel compact segments with different supporting lines in the coordinateplane such that any three segments have a common transversal line. Then there exists a line transversal to all the members of B.

Proof Without loss of generality we can suppose that all the segments parallel to the second coordinate axis labelled by y. Consider such a segment with endpoints (a,r) and (a,s), where r < s and let

y = m x + b

(4.12)

be a line intersecting this segment. Then the common point has the second coordinate ma+b. Therefore

r m a + b s

showing that

- m a + r b - m a + s .

(4.13)

Let us define the parallel lines

y = - a x + r   a n d   y = - a x + s

(4.14)

corresponding to the endpoints of the segment and consider the point p with coordinates (m,b) corresponding to the line 4.12. Inequalities 4.13 shows that p is an element of the band bounded by the parallel lines 4.14. Therefore we can reformulate our condition in the following way: we have a collection of bands such that any three bands have a common point. The goal is to prove that all of them have a common point. Since the segments have different supporting lines it is easy to create a compact convex set K in the family we are interested in. Actually the intersection of finitely many not parallel bands is a convex polygon as the intersection of finitely many closed half-planes, see chapter 9. Then the corresponding version 4.1.7 of Helly's theorem implies the existence of the common point of the bandsand we also have a line intersecting all segments in B.

Remark Theorem 4.3.1 plays an important role in the theory of approximation of continuous functions with polynomials. In what follows we show another application resulting in a sandwich theorem [44]. The result presents necessary and sufficient conditions under which the graphs of two functions can be separated by a straight line (functions having lines as graphs are called affine functions).

Theorem 4.3.2 (K. Nikodem and Sz. Wasowicz) Let f and g be real functions defined on a real interval I. There exists an affine function h satisfying the inequalities

f h g

if and only if

f ( λ x + ( 1 - λ ) y ) λ g ( x ) + ( 1 - λ ) g ( y )

(4.15)

and

g ( λ x + ( 1 - λ ) y ) λ f ( x ) + ( 1 - λ ) f ( y )

(4.16)

hold for any x, y from I and λ between 0 and 1.

Proof Since affine functions preserve the affine (especially convex) combinations of the elements it is obvious that if an affine function h is between f and g then conditions 4.15 and 4.16 are also satisfied for any x, y from I and λ between 0 and 1.

Figure 32: The proof of the sandwich theorem.

To prove the converse of the statement first of all note that f(x) is less or equal than g(x). It can be easily seen by substitution λ=1. Consider now the set of segments with endpoints (x, f(x)) and (x, g(x)) as x runs through the elements of the interval I. These are parallel compact segments with different supporting lines in the coordinate plane. To finish the proof we are going toshow that this collection of segments satisfies the condition of the previous theorem. Let x(1) < x(2) < x(3) be three different points in I and consider the coefficient λ such that x(2)=λ x(1)+(1 - λ)x(3). Using the notations

y i = f ( x i )   a n d   z i = g ( x i ) ,   w h e r e   i = 1,2 , 3

condition 4.15 says that (x(2),y(2)) is under the line of (x(1),z(1)) and (x(3),z(3)). At the same time, by condition 4.16, (x(2),z(2)) is above the line of (x(1),y(1)) and (x(3),y(3)). These conditions obviously guarantee the existence of a common transversal to the segments at x(1), x(2) and x(3), respectively. Finally the previous theorem shows the existence of a common transversal to all the segments as well. This is just the graphof an affine function h between f and g as was to be proved.

Corollary 4.3.3 If a convex function majorizes a concave one then there exists an affine function between them.

Remark Necessary and sufficient conditions for the existence of separation by members of a given linear interpolation family can be found in [46]: the proof is also based on Helly's theorem.