<p>Let <span class="math-container">$D(V, A)$</span> be a DAG.</p>
<p><strong>Definition 0</strong>: We name a path between two nodes <span class="math-container">$i$</span> and <span class="math-container">$j$</span> as an <span class="math-container">$i$</span>-<span class="math-container">$j$</span>-path.</p>
<p><strong>Definition 1</strong>: Let <span class="math-container">$p$</span> be a path, we call <span class="math-container">$|p|$</span> the path length, representing the number of arcs of this path.</p>
<p>For instance, let <span class="math-container">$p = (v_1, v_2, v_3)$</span> be a path, then <span class="math-container">$|p| = 2$</span>.</p>
<p><strong>Definition 2</strong>: We call <span class="math-container">$D(V, A)$</span> a rooted DAG iff. <span class="math-container">$\exists! r \in V : \delta^{-}(r) = \emptyset \wedge \forall_{t \in V} (\exists r\text{-}t\text{-path } \in D)$</span>.</p>
<p>More info about rooted DAGs can be found <a href="https://cs.stackexchange.com/questions/67849/what-do-you-call-a-dag-with-a-single-root-source">here</a>.</p>
<p><strong>Definition 3</strong>: We call <span class="math-container">$D(V, A)$</span> an intransitive DAG iff. <span class="math-container">$\neg (\exists_{i\text{-}j\text{-path }p} (|p| &gt; 1) \wedge (i, j) \in A)$</span>, <span class="math-container">$\forall i, j \in V$</span>, i.e. <span class="math-container">$D$</span> is considered intransitive iff. the arc <span class="math-container">$(i, j)$</span> does not exist, or a path between <span class="math-container">$i$</span> and <span class="math-container">$j$</span>, of length greater than one, does not exist.</p>
<p>For instance, in the below example we have an intransitive DAG.</p>
<pre><code>1 -&gt; 2 -&gt; 3 -&gt; 4 (Example 1)
</code></pre>
<p>And, below we have a transitive DAG, where the addition of path 2 -&gt; 5 -&gt; 6 -&gt; 3 to the above example makes it unable to satisfy the intransitivity conditions. To make intransitive, without losing any node, suffices to remove the arc <span class="math-container">$(2, 3)$</span>.</p>
<pre><code>       --&gt; 5 -&gt; 6 --&gt;
      /              \
1 -&gt; 2 -------------&gt; 3 -&gt; 4 (Example 2)
</code></pre>
<p>More info about transitivity can be found <a href="https://math.stackexchange.com/questions/659942/maximum-number-of-edges-in-a-dag-without-transitivity-condition">here</a> and <a href="https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.transitive_reduction.html" rel="nofollow noreferrer">here</a>.</p>
<p><strong>Definition 4</strong>: We say that an <span class="math-container">$i$</span>-<span class="math-container">$j$</span>-path <span class="math-container">$p$</span> is maximal, iff. isn't possible to extend <span class="math-container">$p$</span> by its extremities.</p>
<p>For instance, in the <em>Example 2</em> we have that path 1 -&gt; 2 -&gt; 5 -&gt; 6 isn't maximal, since it can be extended by nodes 3 and 4. And, the path 1 -&gt; 2 -&gt; 3 -&gt; 4 is maximal.</p>
<p><strong>Corollary 0</strong>: Any maximal path of a rooted DAG starts at the (<em>single</em>) root <span class="math-container">$r$</span>.</p>
<p>Assuming that, <span class="math-container">$D$</span> is a rooted intransitive DAG, what would be some upper bounds for the number of maximal paths of <span class="math-container">$D$</span>?</p>
<p>A valid upper bound would be the maximum number of paths a DAG could have, which would be <span class="math-container">$2^{|V| - 2}$</span>, source <a href="https://math.stackexchange.com/questions/677082/maximum-possible-number-of-paths-in-an-acyclic-digraph/677113#677113">here</a>.
However, I looking for tighter bounds for this, since the maximali- and transitivi-ties are not being considered by this current bound.</p>
<p><strong>Partial results</strong>:</p>
<p><strong>1st lower bound</strong>: Considering the below class of rooted intransitive DAGs, we obtain the presented lower bounds.</p>
<p>2-width layer:</p>
<p>A lower bound of <span class="math-container">$\Omega(2^{\lfloor \frac{n}{3} \rfloor})$</span>.</p>
<pre><code>  -&gt; 2 -&gt;      -&gt; ... -&gt;        -&gt; n - 2 -&gt;  
 /       \    /         \      /           \
1         -&gt; 4           -&gt; n - 3           -&gt; n  (Example 3)
 \       /    \         /      \           /
  -&gt; 3 -&gt;      -&gt; ... -&gt;        -&gt; n - 1 -&gt; 

0            1           (n/3) - 1            n/3 = Layer

 n | layers | # paths
---------------------
4  |    1   |   2
7  |    2   |   4
10 |    3   |   8
13 |    4   |   16
...|   ...  |   ...
</code></pre>
<p>3-width layer:</p>
<p>A lower bound of <span class="math-container">$\Omega(3^{\lfloor \frac{n}{4} \rfloor})$</span>.</p>
<pre><code>  -&gt; 2 -&gt;      -&gt; ... -&gt;         -&gt; n - 3 -&gt;  
 /       \    /         \       /           \
1 -&gt; 3 ---&gt; 5  -&gt; ... ---&gt; n - 4 -&gt; n - 2 ---&gt; n  (Example 4)
 \       /    \         /       \           /
  -&gt; 4 -&gt;      -&gt; ... -&gt;         -&gt; n - 1 -&gt; 

0            1           (n/4) - 1            n/4 = Layer

 n | layers | # paths
---------------------
5  |    1   |   3
9  |    2   |   9
12 |    3   |   27
15 |    4   |   81
...|   ...  |   ...
</code></pre>
<p><span class="math-container">$k$</span>-width layer:</p>
<p>A lower bound of <span class="math-container">$\Omega(k^{\lfloor \frac{n}{k + 1} \rfloor})$</span>.</p>

CC BY-SA 4.0
2024-01-26T23:50:24.620Z
What are your thoughts?  What progress have you made?  What is the best upper bound and lower bound you've been able to find so far?  See the section labelled "Questions should be based on knowledge sharing" in [help/on-topic] ("Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge.").
D.W.
CC BY-SA 4.0
2024-01-28T00:03:17.513Z
@D.W. and NealYoung, thanks by the help and comments, I am sorry for the inconvenient. I've expanded my question. Please, let me know if there is any missing point on it. Thanks and regards.
Matheus Diógenes Andrade
CC BY-SA 4.0
2024-01-28T02:38:02.763Z
What's the best lower bound you have found?  It's easy to show a lower bound of $2^{n/2-1}$, using a layered graph with 2 nodes per layer.  Have you tried explicitly computing the number for $n=1,2,3,4,\dots$ (by enumerating all graphs of that size) and looking it up at https://oeis.org/?  Can you show the number for $n=1,2,\dots,5$?
D.W.
CC BY-SA 4.0
2024-01-28T04:40:28.117Z
You can achieve $\Omega(3^{n/3})$ by using three nodes per layer, which is a bit better as $3^{1/3}>2^{1/2}$
Command Master
CC BY-SA 4.0
2024-01-28T12:09:32.553Z
Is this not basically the same as asking for a bound on the number of maximal chains in a finite poset of size $n$? (give or take one on $n$ in order to add the "root element") According to the answer to [this question](https://math.stackexchange.com/questions/4573267/largest-number-of-maximal-chains-in-a-finite-poset), the (tight) upper bound is given by [this OEIS sequence](https://oeis.org/A000792) which is $\Theta(3^{n/3})$.
Tassle
CC BY-SA 4.0
2024-01-29T22:30:10.970Z
@Tassle, a-prior it doesn't seem so, as the DAG corrresponding to a poset will in general have transitive arcs.  However, it seems likely that any valid upper bound for maximal chains in a poset should yield a valid upper bound for this problem.
Neal Young
CC BY-SA 4.0
2024-01-30T10:34:29.880Z
@NealYoung But a path taking such a transitive arc doesn't correspond to a maximal chain, does it? We can still add the elements which were "shortcuted" to the chain. Maybe I'm misunderstanding something.
Tassle
CC BY-SA 4.0
2024-01-30T14:36:00.283Z
"Maximal" is defined in the post as *"Definition 4: We say that an --path  is maximal, iff. isn't possible to extend  by its **extremities**."*  Note "extremities"...
Neal Young
CC BY-SA 4.0
2024-01-30T22:07:12.257Z
@NealYoung Sure, but I'm talking about a maximal chain in the corresponding poset. A maximal chain in a poset corresponds to a maximal path in the transitive reduction of the poset, which is an intransitive DAG (conversely, any intransitive DAG is the transitive reduction of a poset).
Tassle
CC BY-SA 4.0
2024-01-31T12:05:53.003Z
@Tassle, I see.  So, suppose $G$ is a DAG with a single root.  Then $G$ is the transitive reduction of a poset iff it is an intransitive DAG per OP's definition. Further, the maximal chains in the poset are exactly the paths in $G$ that are maximal per OP's definition (because each edge $(u, w)$ on the path in $G$ is the sole path from $u$ to $w$ in $G$).  Is that right?
Neal Young
CC BY-SA 4.0
2024-01-31T13:18:14.290Z
@D.W. and #CommandMaster, thanks for the comments, as suggested, I have added some examples. Please let me know if some there is miskate.
Matheus Diógenes Andrade
CC BY-SA 4.0
2024-01-31T13:21:23.763Z
@NealYoung and #Tassle, thanks for the comments. #Tassle it seems so that the bound commented by you is right.
Matheus Diógenes Andrade
CC BY-SA 4.0
2024-01-31T14:42:20.057Z
The post currently shows an explicit lower bound of $k^{n/(k+1)}$.  But per @CommandMaster's comment, can't you easily improve this to $k^{n/k}$?  The dag is $G=(V, E)$ with $V=[n]$ and $E=\{(i, j) \in [n] \times [n] : \lceil (j-1)/k\rceil - \lceil (i-1)/k\rceil = 1\}$.  For $k=3$ this seems to match the bound from Tassle's comment.
Neal Young
CC BY-SA 4.0
2024-02-03T09:51:28.330Z
@NealYoung not sure if the commented bound is valid for all cases. But, I am still thinking about the bound associated to the number of maximal paths of finite posets.
Matheus Diógenes Andrade
CC BY-SA 4.0
2024-02-03T09:52:02.477Z
@Tassle do you have more resources on the bound you commented?
Matheus Diógenes Andrade
<graph-theory><directed-acyclic-graph><upper-bounds><transitive-reduction>
Upper bound on the number of maximal paths in rooted intransitive DAGs
Matheus Diógenes Andrade
# Upper bound on the number of maximal paths in rooted intransitive DAGs

(Asked by: username_0 on 2024-01-26)

Let $D(V, A)$ be a DAG.
Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path.
Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs of this path.
For instance, let $p = (v_1, v_2, v_3)$ be a path, then $|p| = 2$.
Definition 2: We call $D(V, A)$ a rooted DAG iff. $\exists! r \in V : \delta^{-}(r) = \emptyset \wedge \forall_{t \in V} (\exists r\text{-}t\text{-path } \in D)$.
More info about rooted DAGs can be found here.
Definition 3: We call $D(V, A)$ an intransitive DAG iff. $\neg (\exists_{i\text{-}j\text{-path }p} (|p| > 1) \wedge (i, j) \in A)$, $\forall i, j \in V$, i.e. $D$ is considered intransitive iff. the arc $(i, j)$ does not exist, or a path between $i$ and $j$, of length greater than one, does not exist.
For instance, in the below example we have an intransitive DAG.
1 -> 2 -> 3 -> 4 (Example 1)

And, below we have a transitive DAG, where the addition of path 2 -> 5 -> 6 -> 3 to the above example makes it unable to satisfy the intransitivity conditions. To make intransitive, without losing any node, suffices to remove the arc $(2, 3)$.
       --> 5 -> 6 -->
      /              \
1 -> 2 -------------> 3 -> 4 (Example 2)

More info about transitivity can be found here and here.
Definition 4: We say that an $i$-$j$-path $p$ is maximal, iff. isn't possible to extend $p$ by its extremities.
For instance, in the Example 2 we have that path 1 -> 2 -> 5 -> 6 isn't maximal, since it can be extended by nodes 3 and 4. And, the path 1 -> 2 -> 3 -> 4 is maximal.
Corollary 0: Any maximal path of a rooted DAG starts at the (single) root $r$.
Assuming that, $D$ is a rooted intransitive DAG, what would be some upper bounds for the number of maximal paths of $D$?
A valid upper bound would be the maximum number of paths a DAG could have, which would be $2^{|V| - 2}$, source here.
However, I looking for tighter bounds for this, since the maximali- and transitivi-ties are not being considered by this current bound.
Partial results:
1st lower bound: Considering the below class of rooted intransitive DAGs, we obtain the presented lower bounds.
2-width layer:
A lower bound of $\Omega(2^{\lfloor \frac{n}{3} \rfloor})$.
  -> 2 ->      -> ... ->        -> n - 2 ->  
 /       \    /         \      /           \
1         -> 4           -> n - 3           -> n  (Example 3)
 \       /    \         /      \           /
  -> 3 ->      -> ... ->        -> n - 1 -> 

0            1           (n/3) - 1            n/3 = Layer

 n | layers | # paths
---------------------
4  |    1   |   2
7  |    2   |   4
10 |    3   |   8
13 |    4   |   16
...|   ...  |   ...

3-width layer:
A lower bound of $\Omega(3^{\lfloor \frac{n}{4} \rfloor})$.
  -> 2 ->      -> ... ->         -> n - 3 ->  
 /       \    /         \       /           \
1 -> 3 ---> 5  -> ... ---> n - 4 -> n - 2 ---> n  (Example 4)
 \       /    \         /       \           /
  -> 4 ->      -> ... ->         -> n - 1 -> 

0            1           (n/4) - 1            n/4 = Layer

 n | layers | # paths
---------------------
5  |    1   |   3
9  |    2   |   9
12 |    3   |   27
15 |    4   |   81
...|   ...  |   ...

$k$-width layer:
A lower bound of $\Omega(k^{\lfloor \frac{n}{k + 1} \rfloor})$.

**Tags:** graph-theory, directed-acyclic-graph, upper-bounds, transitive-reduction
> **Comments:**
> **username_1**: What are your thoughts?  What progress have you made?  What is the best upper bound and lower bound you've been able to find so far?  See the section labelled "Questions should be based on knowledge sharing" in [help/on-topic] ("Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge.").  
> **username_0**: @D.W. and NealYoung, thanks by the help and comments, I am sorry for the inconvenient. I've expanded my question. Please, let me know if there is any missing point on it. Thanks and regards.  
> **username_1**: What's the best lower bound you have found?  It's easy to show a lower bound of $2^{n/2-1}$, using a layered graph with 2 nodes per layer.  Have you tried explicitly computing the number for $n=1,2,3,4,\dots$ (by enumerating all graphs of that size) and looking it up at https://oeis.org/?  Can you show the number for $n=1,2,\dots,5$?  
> **username_2**: You can achieve $\Omega(3^{n/3})$ by using three nodes per layer, which is a bit better as $3^{1/3}>2^{1/2}$  
> **username_3**: Is this not basically the same as asking for a bound on the number of maximal chains in a finite poset of size $n$? (give or take one on $n$ in order to add the "root element") According to the answer to [this question](https://math.stackexchange.com/questions/4573267/largest-number-of-maximal-chains-in-a-finite-poset), the (tight) upper bound is given by [this OEIS sequence](https://oeis.org/A000792) which is $\Theta(3^{n/3})$.  
> **username_4**: @Tassle, a-prior it doesn't seem so, as the DAG corrresponding to a poset will in general have transitive arcs.  However, it seems likely that any valid upper bound for maximal chains in a poset should yield a valid upper bound for this problem.  
> **username_3**: @NealYoung But a path taking such a transitive arc doesn't correspond to a maximal chain, does it? We can still add the elements which were "shortcuted" to the chain. Maybe I'm misunderstanding something.  
> **username_4**: "Maximal" is defined in the post as *"Definition 4: We say that an --path  is maximal, iff. isn't possible to extend  by its **extremities**."*  Note "extremities"...  
> **username_3**: @NealYoung Sure, but I'm talking about a maximal chain in the corresponding poset. A maximal chain in a poset corresponds to a maximal path in the transitive reduction of the poset, which is an intransitive DAG (conversely, any intransitive DAG is the transitive reduction of a poset).  
> **username_4**: @Tassle, I see.  So, suppose $G$ is a DAG with a single root.  Then $G$ is the transitive reduction of a poset iff it is an intransitive DAG per OP's definition. Further, the maximal chains in the poset are exactly the paths in $G$ that are maximal per OP's definition (because each edge $(u, w)$ on the path in $G$ is the sole path from $u$ to $w$ in $G$).  Is that right?  
> **username_0**: @D.W. and #CommandMaster, thanks for the comments, as suggested, I have added some examples. Please let me know if some there is miskate.  
> **username_0**: @NealYoung and #Tassle, thanks for the comments. #Tassle it seems so that the bound commented by you is right.  
> **username_4**: The post currently shows an explicit lower bound of $k^{n/(k+1)}$.  But per @CommandMaster's comment, can't you easily improve this to $k^{n/k}$?  The dag is $G=(V, E)$ with $V=[n]$ and $E=\{(i, j) \in [n] \times [n] : \lceil (j-1)/k\rceil - \lceil (i-1)/k\rceil = 1\}$.  For $k=3$ this seems to match the bound from Tassle's comment.  
> **username_0**: @NealYoung not sure if the commented bound is valid for all cases. But, I am still thinking about the bound associated to the number of maximal paths of finite posets.  
> **username_0**: @Tassle do you have more resources on the bound you commented?  

---

## 0 answers

