A Sharp Lower Bound for the Number of Phylogenetic Trees Displayed by a Tree-Child Network

Abstract A normal (phylogenetic) network with k reticulations displays $$2^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:msup> </mml:math> phylogenetic trees. In this paper, we establish an analogous result for tree-child (phylogenetic) networks with no underlying 3-cycles. In particular, we show that a tree-child network with $$k\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> reticulations and no underlying 3-cycles displays at least $$2^{{k}/{2}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:math> phylogenetic trees if k is even and at least $$\frac{3}{2\sqrt{2}}2^{{k}/{2}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>3</mml:mn> <mml:mrow> <mml:mn>2</mml:mn> <mml:msqrt> <mml:mn>2</mml:mn> </mml:msqrt> </mml:mrow> </mml:mfrac> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> if k is odd. Moreover, we show that these bounds are sharp and characterise the tree-child networks that attain these bounds.