# Find $k$ such that the every $k$-dense graph has $> 2^{k+1} -1$ vertices.

Let $$G=(V,E)$$ be a directed graph.

We say that $$w \in V$$ is a child of $$v \in V$$ if $$(v,w) \in E$$. For $$v \in V$$, define the set of children of $$v$$ to be $$\mathcal{C}(v) := \{ w \in V \ | \ w \ \text{is a child of v} \},$$ and for a set $$S \subseteq V$$, define the set of children of $$S$$ to be $$\mathcal{C}(S) := \left (\bigcup_{v \in S} \mathcal{C}(v) \right) \setminus S.$$ We write $$|\mathcal{C}(v)|$$ (respectively $$|\mathcal{C}(S)|$$) for the number of children of $$v$$ (respectively $$S$$).

For $$k \in \mathbb{N}$$, we say that $$G=(V,E)$$ is $$k$$-dense if $$\forall v \in V$$ $$|\mathcal{C}(v)| = 2$$ and $$\forall m \in \{ 2 , \dots k \}$$ $$\forall v_1,\dots,v_m \in V$$ $$|\mathcal{C}(\{ v_1 , \dots , v_m \})| \geq m$$.

Hypothesis: There exists some $$k \in \mathbb{N}$$ such that every $$k$$-dense graph has strictly more than $$2^{k+1}-1$$ vertices.

NB: This question (also on MSE) proves that every $$k$$-dense graph has at least $$2^{k+1}-1$$ vertices, and mentions that this lower bound is likely not obtained for all but finitely-many $$k \in \mathbb{N}$$. I have not had time to work on an answer to the part of the problem given here, but it could possibly be solved with some straightforward computation so thought it worth writing down.

• When you say each two nodes have at least three children, do you mean that for any nodes $a, b$, the union of the set of children of $a$ and the set of children of $b$ is a set of cardinality at least $3$? Commented Feb 19, 2019 at 21:55
• Thank you for the query and sorry that I haven't been on MSE lately to reply, but hopefully I have made my question clear now. Commented Mar 10, 2019 at 20:01