Games automata play

Universal trees

August 03, 2018 | by Nathanaël Fijalkow

This post introduces the notion of universal trees and poses an open problem: what is the exact size of the smallest universal tree?

The motivation for studying universal trees comes from parity games. This post does not explain this connection at all, the goal is to present an open problem of purely combinatorial nature as I hope to appeal to my combinatorially-minded friends.

For the parity games aficionados, a short chronology:

Definition

We fix two parameters: $n$, which will be the number of leaves, and $h$, which will be the height. We look at totally ordered trees with unbounded degree, meaning that each node may have arbitrarily many children and the children of a node are totally ordered. The depth of a node is its distance to the root. For all trees we consider the leaves have the same depth, which is the height of the tree. The size of a tree is its number of leaves.

A tree of size $11$ and height $2$

We say that a tree embeds into another if the first one can be obtained by removing nodes from the second. We say that a tree $T$ is $(n,h)$-universal if all trees of size $n$ and height $h$ embed into $T$.

A tree of size $5$ and height $2$, and one possible embedding into the tree above

An example of a $(n,h$)-universal tree is the complete tree of height $h$ with each node of degree $n$. It has size $n^h$.

The naive $(5,2)$-universal tree has size $25$

Objective: Construct small universal trees

The details for the upper and lower bounds presented in this post can be found in this technical report.

Upper bounds

Theorem: There exists a $(n,h)$-universal tree of size $f(n,h)$, where

A generous upper bound on the expression above is $n^{O(\log(h))}$. A refined analysis reveals that the expression is polynomial in $n$ and $h$ if $h = 0(\log(n))$.

The construction of Jurdziński and Lazić yields such a tree. We present here a streamlined version, which is marginally better.

We construct an $(n,h)$-universal tree of size $f(n,h)$ by induction, where

The inductive construction

To construct the $(n,h)$-universal tree $T$, let:

  • $T_\text{middle}$ a $(n,h-1)$-universal tree;
  • $T_\text{left}$ a $(\lfloor n/2 \rfloor,h)$-universal tree;
  • $T_\text{right}$ a $(n - 1 - \lfloor n/2 \rfloor,h)$-universal tree.

Now construct $T$ as in the drawing above.

We argue that it is $(n,h)$-universal. Consider a $(n,h)$-tree $t$. The question is which part will embed into $T_\text{left}, T_\text{middle}$, and $T_\text{right}$. Let $v_1,\ldots,v_m$ be the children of the root of $t$, and let $n(v_i)$ be the size of the tree rooted in $v_i$. Choose the unique $v_p$ such that

and

To embed $t$ into $T$, proceed inductively

  • map $v_p$ to the root of $T_\text{middle}$
  • map the tree obtained by keeping the subtrees rooted in $v_1,\ldots,v_{p-1}$ to $T_\text{left}$
  • map the tree obtained by keeping the subtrees rooted in $v_{p+1},\ldots,v_m$ to $T_\text{right}$

Lower bounds

Theorem: Any $(n,h)$-universal tree has size at least $g(n,h)$, where

We show by induction that

Let $T$ be a $(n,h)$-universal tree, and $\delta \in [1,n]$. We claim that the number of nodes at depth $h-1$ of degree greater to or larger than $\delta$ is at least $g(\lfloor n / \delta \rfloor,h-1)$.

Let $T_\delta$ be the subtree of $T$ obtained by

  • removing all leaves, and
  • removing the nodes at depth $h-1$ of degree less than $\delta$ in $T$. (Note that this can create new leaves, they are recursively removed.)
Construction of $T_\delta$

The tree $T_\delta$ has height $h-1$. We argue that $T_\delta$ is $(\lfloor n / \delta \rfloor,h-1)$-universal. Indeed, let $t$ be a tree with $\lfloor n / \delta \rfloor$ leaves of height $h-1$. To each leaf of $t$ we append $\delta$ children, yielding the tree $t_+$ which has $\lfloor n / \delta \rfloor \cdot \delta \le n$ leaves and height $h$. Since $T$ is $(n,h)$-universal, the tree $t_+$ embeds into $T$. Observe that the embedding induces an embedding of $t$ into $T_\delta$, since the leaves of $t$ have degree $\delta$ in $t_+$, hence are also in $T_\delta$.

So far we proved that the number of nodes at depth $h-1$ of degree greater to or larger than $\delta$ is at least $g(\lfloor n / \delta \rfloor,h-1)$. Now, note that the sum over $\delta \in [1,n]$ of the number of nodes at depth $h-1$ of degree greater to or larger than $\delta$ is a lower bound on the number of leaves, which concludes.

Between lower and upper bounds?

One can show that

so there is a (reasonably small but still) gap. Here is what I know:

  • the lower bound is not tight. For $h = 2$ and $n = 5$, there are no universal trees of size $10$, easily seen by necessary conditions (there must be a node with $5$ leaves and two other nodes with $2$ leaves).
  • the upper bound is tight for $h = 2$ (there is a bit of work to check this)

Open question: what is the exact size of the smallest $(n,h)$-universal tree?