<p>The argument in <a href="https://doi.org/10.1016/0304-3975(86)90142-8" rel="nofollow noreferrer">Chrobak’s paper</a> can be applied to this problem as well, with the same bounds.</p>
<p>Let <span class="math-container">$\{D_i:i&lt;k\}$</span> be the set of strongly connected components of <span class="math-container">$G$</span> that contain a cycle (i.e., other than a lone loopless vertex), let <span class="math-container">$y_i$</span> be the gcd of the lengths of all cycles in <span class="math-container">$D_i$</span>, and let <span class="math-container">$y=\operatorname{lcm}(\{y_i:i&lt;k\})$</span>. Observe that any closed walk in <span class="math-container">$G$</span> is included in some <span class="math-container">$D_i$</span>, and has length divisible by <span class="math-container">$y_i$</span> (as it can be decomposed into cycles).</p>
<p>Since <span class="math-container">$\sum_{i&lt;k}y_i\le\sum_{i&lt;k}|D_i|\le n$</span>, we have <span class="math-container">$y\le g(n)$</span>. The proof of Chrobak’s Lemma 4.3 actually shows the following:</p>
<blockquote>
<p><strong>Lemma.</strong> For all <span class="math-container">$s,t\in V$</span> and <span class="math-container">$x\ge n$</span>, <span class="math-container">$x'\ge2n^2$</span> such that <span class="math-container">$x\equiv x'\pmod y$</span>, if there exists a walk from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$x$</span>, then there exists a walk from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$x'$</span>.</p>
<p>(More precisely: for every walk of length <span class="math-container">$x\ge n$</span>, there is <span class="math-container">$i&lt;k$</span> such that for every <span class="math-container">$x'\ge2n^2$</span>, <span class="math-container">$x'\equiv x\pmod{y_i}$</span>, there exists a walk of length <span class="math-container">$x'$</span>.)</p>
</blockquote>
<p><strong>Proof:</strong> A walk <span class="math-container">$w$</span> of length <span class="math-container">$x\ge n$</span> contains a cycle, hence it intersects some <span class="math-container">$D_i$</span>. Let <span class="math-container">$D_{i_0},\dots,D_{i_r}$</span> be the list of all <span class="math-container">$D_i$</span>’s that <span class="math-container">$w$</span> intersects, and let <span class="math-container">$y'=\gcd(\{y_{i_j}:j\le r\})\mid y$</span>. By successively removing cycles from <span class="math-container">$w$</span>, we obtain a walk <span class="math-container">$w_0$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> that still intersects each <span class="math-container">$D_{i_j}$</span>, and that is simple, hence of length <span class="math-container">$x_0&lt;n$</span>, <span class="math-container">$x_0\equiv x\pmod{y'}$</span>. If <span class="math-container">$x'\ge x_0+(n-1)^2$</span> and <span class="math-container">$x'\equiv x\pmod{y'}$</span>, then standard bounds on the Frobenius problem show that <span class="math-container">$x'=x_0+\sum_ia_i|c_i|$</span>, where <span class="math-container">$a_i\ge0$</span>, and each <span class="math-container">$c_i$</span> is a cycle in some <span class="math-container">$D_{i_j}$</span>. Thus, we may construct a walk from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$x'$</span> by attaching to <span class="math-container">$w_0$</span> an appropriate number of copies of each <span class="math-container">$c_i$</span>. The only issue is that <span class="math-container">$c_i$</span> does not necessarily share a vertex with <span class="math-container">$w_0$</span> [Chrobak seems to ignore this point]. To fix this, we first attach to <span class="math-container">$w_0$</span> for each <span class="math-container">$j\le r$</span> a closed walk that connects all points of <span class="math-container">$D_{i_j}$</span>; such a walk exists of length at most <span class="math-container">$|D_{i_j}|^2$</span> (and necessarily divisible by <span class="math-container">$y_{i_j}$</span>, thus by <span class="math-container">$y'$</span>), hence the total added length is at most <span class="math-container">$\sum_j|D_{i_j}|^2\le n^2$</span>. It follows that we can construct <span class="math-container">$w'$</span> of length <span class="math-container">$x'$</span> whenever <span class="math-container">$x'\equiv x\pmod{y'}$</span> satisfies <span class="math-container">$x'\ge n^2+(n-1)^2+x_0$</span>, which certainly holds if <span class="math-container">$x\ge2n^2$</span>.</p>
<blockquote>
<p><strong>Corollary.</strong> For any <span class="math-container">$S\subseteq V$</span>, <span class="math-container">$G^{2n^2}(S)=G^{y+2n^2}(S)$</span>, thus <span class="math-container">$|\{\rho(G,S)\}|\le y+2n^2\le g(n)+2n^2$</span>. That is, <span class="math-container">$g(n)\le f(n)\le g(n)+2n^2$</span>.</p>
</blockquote>
<p><strong>Proof:</strong> <span class="math-container">$t\in G^x(S)$</span> iff there is <span class="math-container">$s\in S$</span> and a walk of length <span class="math-container">$x$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>; thus, the Lemma implies that <span class="math-container">$G^x(S)=G^{x'}(S)$</span> whenever <span class="math-container">$x,x'\ge2n^2$</span> and <span class="math-container">$x\equiv x'\pmod y$</span>.</p>
<p><strong>NB:</strong> The length of a closed walk that connects all vertices of <span class="math-container">$D_{i_j}$</span>, <span class="math-container">$|D_{i_j}|=n_{i_j}$</span>, can be improved to <span class="math-container">$\lfloor(n_{i_j}+1)^2/4\rfloor$</span> (this is tight). This reduces the overall bound to <span class="math-container">$f(n)\le g(n)+\frac54n^2$</span>.</p>
<p>On second thought, we don’t need a closed walk connecting <em>all</em> cycles in <span class="math-container">$D_{i_j}$</span>, but only a set of cycles such that the gcd of their lengths is <span class="math-container">$y_{i_j}$</span>. This reduces the length of the walk to <span class="math-container">$\sim n_{i_j}\frac{\log n_{i_j}}{\log\log n_{i_j}}$</span> (this bound is tight), as <span class="math-container">$\sim\frac{\log n_{i_j}}{\log\log n_{i_j}}$</span> cycles suffice (we take an arbitrary cycle <span class="math-container">$c$</span>, and then for each prime <span class="math-container">$p$</span> dividing <span class="math-container">$|c|/y_{i_j}$</span>, a cycle whose length is not divisible by <span class="math-container">$py_{i_j}$</span>).</p>
<p>Thus, <span class="math-container">$f(n)\le g(n)+n^2+(1+o(1))n\frac{\log n}{\log\log n}$</span>.</p>

CC BY-SA 4.0
2023-12-25T17:10:44.503Z
Thank you for writing this down! Do you have a reference for the $\lfloor(n_{i_j}+1)^2/4\rfloor$ bound?
alsips-cl
CC BY-SA 4.0
2023-12-25T18:54:24.463Z
I don’t have a reference, but it’s a simple argument. To simplify the notation, let $G$ be a strongly connected digraph of size $n$; I want to show that there is a closed walk connecting all vertices of $G$ of length at most $\lfloor(n+1)^2/4\rfloor$. Let $p=(x_0,\dots,x_l)$ be a simple path in $G$ of maximal length, and let $x_{l+1},\dots,x_{n-1}$ be the remaining vertices of $G$. We augment $p$ with simple paths from $x_l$ to $x_{l+1}$, from $x_{l+1}$ to $x_{l+2}$, etc., and from $x_{n-1}$ to $x_0$; these are $n-l$ paths, each with at most $l$ edges (by the maximality of $p$), thus ...
Emil Jeřábek
CC BY-SA 4.0
2023-12-25T18:58:56.240Z
... in total, the closed walk has length at most $(n-l+1)l$. This expression is maximized for $l=(n+1)/2$, in which case we get $(n+1)^2/4$ (or rather, $\lfloor(n+1)^2/4\rfloor$ as it must be an integer).
Emil Jeřábek
CC BY-SA 4.0
2023-12-25T19:03:36.037Z
To see that the bound is tight, consider a graph consisting of a path with $\lfloor n/2\rfloor$ vertices, whose endpoint connects to $\lceil n/2\rceil$ other vertices (call these “special”), each of which connects back to the start of the path. Any path connecting one special vertex to another has at least $\lfloor n/2\rfloor+1$ edges, hence a closed walk that (wlog) starts in one special vertex and traverses all the other has length at least $\lceil n/2\rceil(\lfloor n/2\rfloor +1)=\lfloor(n+1)^2/4\rfloor$.
Emil Jeřábek
CC BY-SA 4.0
2023-12-22T13:48:09.520Z
2023-12-24T10:27:30.220Z
2023-12-24T10:27:30.220Z
Emil Jeřábek
<p>For a given directed graph <span class="math-container">$G = (V, E)$</span> (possibly with loops), and some <span class="math-container">$S\subseteq V$</span> define the operation <span class="math-container">$G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$</span>.</p>
<p>Now consider the infinite sequence <span class="math-container">$\rho(G, S) = S, G(S), G(G(S)), G(G(G(S))), ...$</span> and call <span class="math-container">$|\{\rho(G, S)\}|$</span> the number of unique elements in the sequence.</p>
<p>I'm interested in the asymptotical behavior of the function <span class="math-container">$f(n)$</span> defined as the maximum size of <span class="math-container">$|\{\rho(G, S)\}|$</span> among all graphs <span class="math-container">$G$</span> with <span class="math-container">$n$</span> nodes.</p>
<p>There is an obvious upper bound of <span class="math-container">$2^n$</span> and there is a lower bound of <span class="math-container">$\Omega( e^{\sqrt{n \log n}})$</span> by using a <span class="math-container">$G$</span> that is made of disjoint cycles of different sizes that are coprime to one another. This bound is given by <a href="https://en.wikipedia.org/wiki/Landau%27s_function" rel="nofollow noreferrer">Landau's function</a>. My question is:</p>
<blockquote>
<p>Is it true that <span class="math-container">$f(n)\in \Theta(g(n))$</span>, where <span class="math-container">$g(n)$</span> is Landau's function?</p>
</blockquote>
<p><strong>Obs. 1</strong>: This is closely related to the problem of determinizing an NFA over a unary alphabet. The sequence <a href="https://oeis.org/A157656" rel="nofollow noreferrer">A157656</a> on the OEIS describes the exact value for each <span class="math-container">$n$</span> when considering a single initial state.</p>
<p>More relevantly, there is a classic result by Marek Chrobak (<a href="https://www.sciencedirect.com/science/article/pii/0304397586901428" rel="nofollow noreferrer">link</a>) that says for any <span class="math-container">$n$</span>-state unary NFA, there exists an equivalent unary DFA with <span class="math-container">$O(g(n))$</span> states. There should be a straightforward way of using this to solve the question in the positive that I'm not seeing.</p>

CC BY-SA 4.0
2023-12-22T15:15:21.047Z
**Comments have been [moved to chat](https://chat.stackexchange.com/rooms/150463/discussion-on-question-by-alsips-cl-counting-the-different-subsets-of-nodes-seen); please do not continue the discussion here.** Before posting a comment below this one, please review the [purposes of comments](/help/privileges/comment). Comments that do not request clarification or suggest improvements usually belong as an [answer](/help/how-to-answer), on [meta], or in [chat]. Comments continuing discussion may be removed.
Lev Reyzin
<graph-theory><automata-theory><dfa><nfa><unary-languages>
Counting the different subsets of nodes seen when iterating a subset through a directed graph
alsips-cl
# Counting the different subsets of nodes seen when iterating a subset through a directed graph

(Asked by: username_0 on 2023-12-17)

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$.

Now consider the infinite sequence $\rho(G, S) = S, G(S), G(G(S)), G(G(G(S))), ...$ and call $|\{\rho(G, S)\}|$ the number of unique elements in the sequence.

I'm interested in the asymptotical behavior of the function $f(n)$ defined as the maximum size of $|\{\rho(G, S)\}|$ among all graphs $G$ with $n$ nodes.

There is an obvious upper bound of $2^n$ and there is a lower bound of $\Omega( e^{\sqrt{n \log n}})$ by using a $G$ that is made of disjoint cycles of different sizes that are coprime to one another. This bound is given by [Landau's function](https://en.wikipedia.org/wiki/Landau%27s_function). My question is:

> Is it true that $f(n)\in \Theta(g(n))$, where $g(n)$ is Landau's function?

**Obs. 1**: This is closely related to the problem of determinizing an NFA over a unary alphabet. The sequence [A157656](https://oeis.org/A157656) on the OEIS describes the exact value for each $n$ when considering a single initial state.

More relevantly, there is a classic result by Marek Chrobak ([link](https://www.sciencedirect.com/science/article/pii/0304397586901428)) that says for any $n$-state unary NFA, there exists an equivalent unary DFA with $O(g(n))$ states. There should be a straightforward way of using this to solve the question in the positive that I'm not seeing.

**Tags:** graph-theory, automata-theory, dfa, nfa, unary-languages
> **Comments:**
> **username_1**: **Comments have been [moved to chat](https://chat.stackexchange.com/rooms/150463/discussion-on-question-by-alsips-cl-counting-the-different-subsets-of-nodes-seen); please do not continue the discussion here.** Before posting a comment below this one, please review the [purposes of comments](/help/privileges/comment). Comments that do not request clarification or suggest improvements usually belong as an [answer](/help/how-to-answer), on [meta], or in [chat]. Comments continuing discussion may be removed.  

---

## 1 answers

### Answer by username_2 on 2023-12-22. Score: 1 | Accepted answer

The argument in [Chrobak’s paper](https://doi.org/10.1016/0304-3975(86)90142-8) can be applied to this problem as well, with the same bounds.

Let $\{D\_i:i be the set of strongly connected components of $G$ that contain a cycle (i.e., other than a lone loopless vertex), let $y\_i$ be the gcd of the lengths of all cycles in $D\_i$, and let $y=\operatorname{lcm}(\{y\_i:i. Observe that any closed walk in $G$ is included in some $D\_i$, and has length divisible by $y\_i$ (as it can be decomposed into cycles).

Since $\sum\_{i, we have $y\le g(n)$. The proof of Chrobak’s Lemma 4.3 actually shows the following:

> **Lemma.** For all $s,t\in V$ and $x\ge n$, $x'\ge2n^2$ such that $x\equiv x'\pmod y$, if there exists a walk from $s$ to $t$ of length $x$, then there exists a walk from $s$ to $t$ of length $x'$.
>
> (More precisely: for every walk of length $x\ge n$, there is $i such that for every $x'\ge2n^2$, $x'\equiv x\pmod{y\_i}$, there exists a walk of length $x'$.)

**Proof:** A walk $w$ of length $x\ge n$ contains a cycle, hence it intersects some $D\_i$. Let $D\_{i\_0},\dots,D\_{i\_r}$ be the list of all $D\_i$’s that $w$ intersects, and let $y'=\gcd(\{y\_{i\_j}:j\le r\})\mid y$. By successively removing cycles from $w$, we obtain a walk $w\_0$ from $s$ to $t$ that still intersects each $D\_{i\_j}$, and that is simple, hence of length $x\_0, $x\_0\equiv x\pmod{y'}$. If $x'\ge x\_0+(n-1)^2$ and $x'\equiv x\pmod{y'}$, then standard bounds on the Frobenius problem show that $x'=x\_0+\sum\_ia\_i|c\_i|$, where $a\_i\ge0$, and each $c\_i$ is a cycle in some $D\_{i\_j}$. Thus, we may construct a walk from $s$ to $t$ of length $x'$ by attaching to $w\_0$ an appropriate number of copies of each $c\_i$. The only issue is that $c\_i$ does not necessarily share a vertex with $w\_0$ [Chrobak seems to ignore this point]. To fix this, we first attach to $w\_0$ for each $j\le r$ a closed walk that connects all points of $D\_{i\_j}$; such a walk exists of length at most $|D\_{i\_j}|^2$ (and necessarily divisible by $y\_{i\_j}$, thus by $y'$), hence the total added length is at most $\sum\_j|D\_{i\_j}|^2\le n^2$. It follows that we can construct $w'$ of length $x'$ whenever $x'\equiv x\pmod{y'}$ satisfies $x'\ge n^2+(n-1)^2+x\_0$, which certainly holds if $x\ge2n^2$.

> **Corollary.** For any $S\subseteq V$, $G^{2n^2}(S)=G^{y+2n^2}(S)$, thus $|\{\rho(G,S)\}|\le y+2n^2\le g(n)+2n^2$. That is, $g(n)\le f(n)\le g(n)+2n^2$.

**Proof:** $t\in G^x(S)$ iff there is $s\in S$ and a walk of length $x$ from $s$ to $t$; thus, the Lemma implies that $G^x(S)=G^{x'}(S)$ whenever $x,x'\ge2n^2$ and $x\equiv x'\pmod y$.

**NB:** The length of a closed walk that connects all vertices of $D\_{i\_j}$, $|D\_{i\_j}|=n\_{i\_j}$, can be improved to $\lfloor(n\_{i\_j}+1)^2/4\rfloor$ (this is tight). This reduces the overall bound to $f(n)\le g(n)+\frac54n^2$.

On second thought, we don’t need a closed walk connecting *all* cycles in $D\_{i\_j}$, but only a set of cycles such that the gcd of their lengths is $y\_{i\_j}$. This reduces the length of the walk to $\sim n\_{i\_j}\frac{\log n\_{i\_j}}{\log\log n\_{i\_j}}$ (this bound is tight), as $\sim\frac{\log n\_{i\_j}}{\log\log n\_{i\_j}}$ cycles suffice (we take an arbitrary cycle $c$, and then for each prime $p$ dividing $|c|/y\_{i\_j}$, a cycle whose length is not divisible by $py\_{i\_j}$).

Thus, $f(n)\le g(n)+n^2+(1+o(1))n\frac{\log n}{\log\log n}$.

> **Comments:**
> **username_0**: Thank you for writing this down! Do you have a reference for the $\lfloor(n_{i_j}+1)^2/4\rfloor$ bound?  
> **username_2**: I don’t have a reference, but it’s a simple argument. To simplify the notation, let $G$ be a strongly connected digraph of size $n$; I want to show that there is a closed walk connecting all vertices of $G$ of length at most $\lfloor(n+1)^2/4\rfloor$. Let $p=(x_0,\dots,x_l)$ be a simple path in $G$ of maximal length, and let $x_{l+1},\dots,x_{n-1}$ be the remaining vertices of $G$. We augment $p$ with simple paths from $x_l$ to $x_{l+1}$, from $x_{l+1}$ to $x_{l+2}$, etc., and from $x_{n-1}$ to $x_0$; these are $n-l$ paths, each with at most $l$ edges (by the maximality of $p$), thus ...  
> **username_2**: ... in total, the closed walk has length at most $(n-l+1)l$. This expression is maximized for $l=(n+1)/2$, in which case we get $(n+1)^2/4$ (or rather, $\lfloor(n+1)^2/4\rfloor$ as it must be an integer).  
> **username_2**: To see that the bound is tight, consider a graph consisting of a path with $\lfloor n/2\rfloor$ vertices, whose endpoint connects to $\lceil n/2\rceil$ other vertices (call these “special”), each of which connects back to the start of the path. Any path connecting one special vertex to another has at least $\lfloor n/2\rfloor+1$ edges, hence a closed walk that (wlog) starts in one special vertex and traverses all the other has length at least $\lceil n/2\rceil(\lfloor n/2\rfloor +1)=\lfloor(n+1)^2/4\rfloor$.  

---

