Parker Glynn-Adey

Level Sets of Functions from Binary Trees

Posted in Math by pgadey on 2011/06/23

A quick lemma I found, while reading THE MORSE LANDSCAPE OF A RIEMANNIAN DISK by S. FRANKEL & M. KATZ. Inst. Fourier, Grenoble 43, 2 (1993), 503-507.

Let T_n denote a binary tree of height n. Recall, the binary tree of height zero is a point, the root, and that we construct T_{n+1} by taking a point as its root and linking this point to the roots of two copies of T_n.

If f : T_n \rightarrow \mathbb{R} is a continuous function, then f has a level set with n/2 points.

We proceed by induction. The cases n = 1 and n = 2 are easy, since we only require a single point in our level set. Consider L = \inf_{T_n} f and U = \sup_{T_n} f. By continuity of f, and the closedness of T_n, we can pick representatives L_0, U_0 \in T_n such that f(L_0) = L and f(U_0) = U. As we are in a binary tree, we have a unique shortest path joining L_0 and U_0. If this path passes through the root of T_n then it must avoid a copy of T_{n-2} sitting within T_n. Otherwise, it avoids a copy of T_{n-1} sitting within T_n. Now consider the restriction of f to the complement of this path. Since this induces a continuous function on the avoided binary tree, there must be some x with (n-2)/2 pre-images. But then, considering f on the minimal path, we have L \leq x \leq U and hence we obtain another pre-image. It follows we have (n-2)/2 + 1 = n/2 distinct pre-images of x, completing the induction.

Tagged with: ,