Problem A. 934. (April 2026)
A. 934. Let \(\displaystyle \mathcal{T}\) denote the set of countable, undirected trees. A subset \(\displaystyle X\) of the real numbers is called bariton if every nonempty subset of \(\displaystyle X\) has a least element.
a) Prove that for every bariton \(\displaystyle X\) there exists a function \(\displaystyle f\colon X\to \mathcal{T}\) such that for all \(\displaystyle y\), \(\displaystyle z\in X\) we have \(\displaystyle y\leq z\) if and only if \(\displaystyle f(y)\) is isomorphic to a subgraph of \(\displaystyle f(z)\).
b) Does the statement remain true if we additionally require that for every \(\displaystyle x\in X\), all vertices of \(\displaystyle f(x)\) have finite degree? (A graph with vertex set \(\displaystyle V\) is called countable if there exists an injective map \(\displaystyle V\to\mathbb{N}\).)
Proposed by Márton Németh, Budapest
(7 pont)
Deadline expired on May 11, 2026.
Solution.
a) \(\displaystyle X\) is countable: for any \(\displaystyle x\in X\), the set
\(\displaystyle \{y\mid y>x\}\cap X \)
has a least element, hence one can choose \(\displaystyle \varepsilon_x>0\) such that
\(\displaystyle (x,x+\varepsilon_x)\cap X=\emptyset. \)
That is, we assigned to every element of \(\displaystyle X\) an interval, and these intervals are pairwise disjoint. Since every interval contains a rational number, \(\displaystyle X\) is countable.
Furthermore, by assumption \(\displaystyle X\) is well-ordered, hence \(\displaystyle X\cong \alpha\) for some countable ordinal \(\displaystyle \alpha\). Thus it suffices to construct a function
\(\displaystyle f:\alpha\to\mathcal{T} \)
such that for \(\displaystyle y,z\in\alpha\),
\(\displaystyle y\le z \)
holds if and only if \(\displaystyle f(y)\) is isomorphic to a subgraph of \(\displaystyle f(z)\).
First we construct, by transfinite recursion, an auxiliary function
\(\displaystyle g:\alpha\to\mathcal{T}', \)
where \(\displaystyle \mathcal{T}'\) denotes the set of directed, countable trees, satisfying a similar condition.
If \(\displaystyle \alpha=0\), then \(\displaystyle g:\emptyset\to\mathcal{T}\) exists trivially. Otherwise (both in the successor and limit ordinal cases), let \(\displaystyle g(\alpha)\) be the directed tree having a root \(\displaystyle R\), together with directed edges from \(\displaystyle R\) to the roots of all trees \(\displaystyle g(\gamma)\) (taking disjoint copies of each). Observe that in every tree constructed this way, the edges point away from a designated root, and every such tree is countable, since a countable union of countable sets is countable.
Finally, we show that the trees \(\displaystyle g(\gamma)\) constructed in this way satisfy the desired condition. If \(\displaystyle y\le z\), then clearly \(\displaystyle g(y)\) appears inside \(\displaystyle g(z)\).
Now let \(\displaystyle z<y\), and suppose that \(\displaystyle g(y)\) is isomorphic to a subgraph of \(\displaystyle g(z)\). Let \(\displaystyle R_0\) be the root of \(\displaystyle g(z)\). Let \(\displaystyle R_1\) be the vertex of \(\displaystyle g(z)\) corresponding to the root of \(\displaystyle g(y)\). Let \(\displaystyle R_2\) be the vertex of \(\displaystyle g(z)\) corresponding to the root of the copy of \(\displaystyle g(z)\) appearing as a subtree inside \(\displaystyle g(y)\), and so on. Clearly,
\(\displaystyle R_0,R_2,R_4,\ldots \)
together with some intermediate vertices form an infinite path in \(\displaystyle g(z)\).
But this is impossible, which we prove by induction. In \(\displaystyle g(0)\) there is no infinite path. Assume that for every \(\displaystyle \gamma<\alpha\), the tree \(\displaystyle g(\gamma)\) contains no infinite path. Then any infinite path in \(\displaystyle g(\alpha)\) would have to continue from the root into the root of some \(\displaystyle g(\gamma)\), contradicting the induction hypothesis. Hence \(\displaystyle g(\alpha)\) also contains no infinite path. This proves the claim.
Finally, we construct \(\displaystyle f\) from \(\displaystyle g\): replace every directed edge in \(\displaystyle g(\alpha)\) as follows. Remove the edge \(\displaystyle (u\to v)\), introduce new vertices \(\displaystyle a,b,c\), and add the edges
\(\displaystyle (u,a),\ (a,b),\ (b,v),\ (b,c). \)
Clearly, the required embeddings still exist.
Moreover, any embedding of the original vertices of \(\displaystyle g(z)\) into \(\displaystyle f(z)\) must map them to original vertices of \(\displaystyle f(y)\), so the converse direction also follows.
b) The statement remains true. We give a construction that works for an arbitrary subset \(\displaystyle X\subseteq\mathbb{R}\), keeps all vertex degrees finite, and does not use transfinite recursion.
First construct an infinite symmetric binary search tree \(\displaystyle M\): let the root be \(\displaystyle \epsilon\), the children of \(\displaystyle \epsilon\) be \(\displaystyle 0\) and \(\displaystyle 1\), and in general the children of any vertex \(\displaystyle w\) be \(\displaystyle w0\) and \(\displaystyle w1\).
Now construct a bijection
\(\displaystyle h:V(M)\to\mathbb{Q} \)
such that
\(\displaystyle h(w0)<h(w)<h(w1) \)
for every vertex \(\displaystyle w\).
Let
\(\displaystyle \mathbb{Q}=\{q_0,q_1,\ldots\} \)
be an arbitrary enumeration of the rational numbers. At step \(\displaystyle i\ge0\), choose a vertex \(\displaystyle w\) with \(\displaystyle |w|=i\), and assign
\(\displaystyle h(w)=q_i \)
in such a way that the condition is not violated by the previously assigned values (if the rational number \(\displaystyle q_i\) has already been assigned to an earlier vertex, skip this step). Finally, assign arbitrary remaining values to the vertices
\(\displaystyle \{w:|w|=i\}. \)
This is always possible because every interval contains a rational number.
Now define the function \(\displaystyle f\). Take an arbitrary real number \(\displaystyle x\). To every vertex \(\displaystyle w\) of \(\displaystyle M\) satisfying
\(\displaystyle h(w)\le x, \)
attach a leaf. This yields a tree \(\displaystyle M_x\). Finally, attach \(\displaystyle 5\) leaves to the root of \(\displaystyle M\). This gives a tree \(\displaystyle M_x'\). Define
\(\displaystyle f(x)=M_x'. \)
The verification that the construction works is left to the reader.
Statistics:
8 students sent a solution. 7 points: Aravin Peter, Áron Bence, Bodor Mátyás, Diaconescu Tashi, Kis Ágoston, Sami El-Hajjar. 6 points: Morvai Várkony Albert. 2 points: 1 student.
Problems in Mathematics of KöMaL, April 2026