Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs*

NEW

Problem: Reconstructed statement: For every $k\in\mathbb N_0$, there is a finite connected hypergraph $H$ such that

where $\kappa_{ST}$ is the Sonntag--Teichert competition number and $\phi_{ST}$ is the corresponding ST-phylogeny number: for an acyclic digraph $D$,

and

with phylogeny realization taken by the induced trace on the original vertex set.

Result: The statement is true.

For $k=0$, take the one-edge hypergraph $H$ with vertex set $\{a,b\}$ and edge $\{a,b\}$. Then $\kappa_{ST}(H)=1$, since the edge is all of $V(H)$ and so cannot be an in-neighborhood of an original vertex; one new sink realizes it. Also $\phi_{ST}(H)=0$, realized by the acyclic digraph $a\to b$. Thus $\phi_{ST}(H)-\kappa_{ST}(H)+1=0$.

Now let $k\ge1$, and put $t=k+2$. Let

Define a hypergraph $H_t$ on $V$ with edges

It is connected because $V$ itself is an edge.

First, $\kappa_{ST}(H_t)=1$. One new vertex $z$ suffices: add arcs $x\to r_i$ for every $x\in F_i$, and arcs $v\to z$ for every $v\in V$. With order $C<R<z$, the digraph is acyclic, and its nontrivial in-neighborhoods are exactly $F_1,\dots,F_t,V$. Conversely, the edge $V$ cannot be the in-neighborhood of any original vertex, since no vertex belongs to its own in-neighborhood. Hence at least one added vertex is necessary.

Second, $\phi_{ST}(H_t)=t-2$. For the upper bound, use $t-2$ new vertices $w_2,\dots,w_{t-1}$. Realize $F_1$ at $c_t$, realize $F_t$ at $c_{t-1}$, realize $V$ at $r_t$, and realize each $F_i$ for $2\le i\le t-1$ at $w_i$. This is done by putting arcs from every other vertex of the desired edge into the representing vertex; the order

is acyclic. The induced trace of the ST-phylogeny hypergraph is exactly $H_t$.

For the lower bound, consider any acyclic phylogeny realization and restrict a topological order to $V$. If an edge of $H_t$ is represented by an original vertex, that vertex must be the maximum element of that edge in this restricted order. Among the core edges $F_i=C\setminus\{c_i\}$, only two vertices can occur as such maxima: the latest and second-latest vertices of $C$. The large edge $V$ contributes at most one further maximum. Hence at most three edges of $H_t$ can be represented by original vertices. Since $H_t$ has $t+1$ edges, at least $(t+1)-3=t-2$ added vertices are necessary. Therefore $\phi_{ST}(H_t)=t-2$.

Thus

So every nonnegative integer occurs.

Citation: No prior resolution is used here. The problem and notation are from Xiong, Zaw, and Zhu, “Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs,” Problem 2(ii).