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: ,