Trident Tableaux for Tree-Child Networks with One Reticulation Node: A Bijection with Two-Wall Tableaux

Hexuan Liu

In the authors' words

Motivated by a word encoding of tree-child networks, we introduce trident tableaux, which are Young tableaux with a unique three-cell column satisfying certain conditions on successors. We construct a bijection between trident tableaux with $n + 1$ columns and two-wall tableaux with $n$ columns, that is, two-row fillings with two designated columns in which vertical order is not imposed. The bijection matches the three-part decompositions of the two classes and shows that each class has cardinality $n (n + 1) C_{n} /2$ , where $C_{n}$ is the $n$ -th Catalan number. In particular, it gives a trident-tableau interpretation of a shifted form of OEIS A002457. As a consequence, we obtain an exact enumeration of tree-child networks with one reticulation node that contain a trident, and show that their proportion among all tree-child networks with one reticulation node tends to $1/8$ as the number of leaves tends to infinity.

Main resultThe abstract does not state a limitation.

Trident Tableaux for Tree-Child Networks with One Reticulation Node: A Bijection with Two-Wall Tableaux

In the authors' words

More on Combinatorics & discrete math that day

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond