7
$\begingroup$

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. 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 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) 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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

The argument in Chrobak’s paper can be applied to this problem as well, with the same bounds.

Let $\{D_i:i<k\}$ 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<k\})$. 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<k}y_i\le\sum_{i<k}|D_i|\le n$, 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<k$ 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<n$, $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}$.

$\endgroup$
4
  • $\begingroup$ Thank you for writing this down! Do you have a reference for the $\lfloor(n_{i_j}+1)^2/4\rfloor$ bound? $\endgroup$
    – alsips-cl
    Dec 25, 2023 at 17:10
  • $\begingroup$ 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 ... $\endgroup$ Dec 25, 2023 at 18:54
  • $\begingroup$ ... 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). $\endgroup$ Dec 25, 2023 at 18:58
  • $\begingroup$ 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$. $\endgroup$ Dec 25, 2023 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.