352 (2000), no. 1, 257–284.

[19]
, Design of sturm global attractors 1: Meanders with three noses,
and reversibility, arXiv preprint arXiv:2302.12531 (2023).

[20]
J. Guckenheimer, Sensitive dependence to initial conditions for one
dimensional maps, Communications in Mathematical Physics 70 (1979),
no. 2, 133–160.

[21]
M. Hurley, Chain recurrence and attraction in non-compact spaces,
Ergodic Theory and Dynamical Systems 11 (1991), no. 4, 709–729.

[22]
, Chain recurrence, semiflows, and gradients, Journal of Dynamics
and Differential Equations 7 (1995), 437–456.

[23]
V.G. Ivancevic and T.T. Ivancevic, Ricci flow and nonlinear
reaction–diffusion systems in biology, chemistry, and physics, Nonlinear
Dynamics 65 (2011), 35–54.

[24]
L. Jonker and D. Rand, Bifurcations in one dimension, Inventiones
mathematicae 62 (1980), no. 3, 347–365.

[25]
Keonhee L., Ngoc-Thach N., and Yinong Y., Topological stability and
spectral decomposition for homeomorphisms on noncompact spaces, Discrete and
Continuous Dynamical Systems 38 (2018), no. 5, 2487–2503.

[26]
D.A. Mizin, On the global structure of a dynamical system, Differential
Equations and Control Processes (Differencialnie Uravnenia i Protsesy
Upravlenia) 3 (2002), 83–107, <https://diffjournal.spbu.ru/>.

[27]
R. Moeckel, Some comments on'The gradient structure of a flow: I',
1988, pp. 9–9.

[28]
S.E. Newhouse, Diffeomorphisms with infinitely many sinks, Topology
13 (1974), no. 1, 9–18.

[29]
D.E. Norton, The fundamental theorem of dynamical systems,
Commentationes Mathematicae Universitatis Carolinae 36 (1995),
no. 3, 585–597.

[30]
J. Oh, Spectral decomposition for homeomorphisms on non-metrizable
totally disconnected spaces, Journal of the Korean Mathematical Society
59 (2022), no. 5, 987–996.

[31]
G. Osipenko, Dynamical systems, graphs, and algorithms, Springer, 2006.

[32]
J.C. Robinson, Infinite-Dimensional Dynamical Systems: An
introduction to dissipative parabolic PDEs and the theory of global
attractors.,  (2001).

[33]
S. Smale, On gradient dynamical systems, Annals of Mathematics (1961),

[34]
, Differentiable dynamical systems, Bulletin of the American
mathematical Society 73 (1967), no. 6, 747–817.

[35]
S. Smale and R.F. Williams, The qualitative analysis of a difference
equation of population growth, Journal of Mathematical Biology 3
(1976), no. 1, 1–4.

[36]
T. Ura, Sur les courbes définies par les équations
différentielles dans l’espace à $ m $ dimensions, Annales
scientifiques de l'École normale supérieure, vol. 70, 1953,
pp. 287–360.

[37]
J. Wiseman, The generalized recurrent set and strong chain recurrence,
Ergodic Theory and Dynamical Systems 38 (2018), no. 2, 788–800.

Axioms $\cD$.

$\cD_{\cO}$: $D\supset\cO$

We want $\Sto$ is be an extension of  $\Fto$: $x\Fto y\implies x\Sto y$.

$\cD_{\text{clos}}$: $D$ is closed in $X\times X$.

We want points of $\omega(x)$ to be downstream from $x$.

$\Down(x)\supset\Down(y)$ for each $y\in\Down(x)$.

We want transitivity: if $x\leadsto y$ and $y\leadsto z$, then $x\leadsto z$. This way, nodes are disjoint.

Remark: by applying $\Dc$ and $\Dt$ to $\Do$, it follows at once that $\Down(x)\supset\cO(x)\cup\Down(\Om(x))$.

$\Down(x)= \cO(x)\cup\Down(\Om(x))$.

We want stream relations to be minimal, in the sense that $\Down(x)$ is the smallest possible set it can be.

This axiom has strong consequences, in particular that every node is forward invariant. In turn, this implies that each node contains a recurrent point, tying nodes to the dynamics of $F$.

Important examples of stream structures.
The next three propositions show that the three concepts of recurrence introduced above are indeed the recurrence sets of stream structures.

Joe's GR

Strong CR is...

Largest and smallest stream structures of a semi-flow.
We show below that every semi-flow has a (trivial) largest stream structure and a (usually non-trivial) smallest stream structure.

The set $X\times X$ is a stream structure for every semi-flow $F$ on $X$.

The intersection $D$ of a collection of stream structures $D_\alpha$ is a stream structure and $\sR_D$ is the  intersection of the $\sR_{D_\alpha}$.

We leave to the reader the proof that $D$ satisfies $\Dc$ and $\Dt$.
We now show $D$ satisfies $\Db$.
Note that, for every $x$, the whole $\cO(x)$ is contained in each $\Down_\alpha(x)$ and so $\cO(x)\subset \Down(x)$.
Let $y\in\cO(x)$.

\begin{align*}
\Down(x)&=\cap_\alpha\Down_\alpha(x)=\cap_\alpha(\cO(x)\cup\Down_\alpha(y))=\\
\end{align*}

Now, let $x\in\sR_D$.
If $x$ is fixed, then clearly $x\in\cap_\alpha\sR_{\Down_\alpha}$.
Assume now $x$ is not fixed.
Then $(x,F^1(x))\in D$ and $(F^1(x),x)\in D$, so $x\in\sR_{Down_\alpha}$ for every $\alpha$.
Now let $x\in\cap_\alpha\sR_{\Down_\alpha}.$
Then $(x,F^1(x))\in\Down_\alpha$ and $(F^1(x),x)\in\Down_\alpha$ for every $\alpha$, so that $(x,F^1(x))\in D$ and $(F^1(x),x)\in D$.
Hence, $x\in\sR_D$.

For any relation $P$ on $X$,
there exists a smallest stream structure $D$ for $F$ that contains $P$.
In particular, every semi-flow $F$ has a smallest stream structure.

Given any relation $P$ on $X$, the set $\cD(P)$ of all stream structures containing $P$ is always non-empty, since it contains at least the trivial stream structure $D=X\times X$.
Moreover, by Lemma <ref>, the intersection $D_\cap$ of all stream structures in $\cD(P)$ is a stream structure. Hence, $D_\cap$ is the smallest stream structure containing $P$.
By taking $P=\cO$, we get a stream structure that cannot be contained in a smaller stream structure.

In the following examples...

[Identity flow]
Consider first the trivial semi-flow on $X$, namely $F^t(x)=x$ for every $x$ and all $t\geq0$.
Hence, every point is fixed by $F^t$.
Then the smallest Downhill structure of $F$ is the diagonal of $X\times X$, namely the set $(x,x)$, which in this case coincides with $\cO$; its largest structure is the whole $X\times X$.
In both cases, $\sR=X$.
In the first case, though, $\Node(x)=\{x\}$ for each $x$; in the second case, $\Node(x)=X$  for each $x$, namely the whole space $X$ is a node and the graph $\Gamma$ consists in that single node and has no edges.

[Clockwise flow on a circle with two fixed points]
Let $X$ be the circle $\mathbb S^1$ and assume that $F$ has two fixed points $N$ and $S$, and that every other point moves clockwise.
Let $H_1$ be the open arc of $X$ between $S$ and $N$ where points are moving towards $N$ under $F$ and by $H_2$ the other open arc.
Then, if $x\in H_1$, we have that $\Om(x)=\{N\}$ and so $N\in\Down(x)$.
Since $N\in\Down(x)$ for points $x\in H_1$ arbitrarily close to $S$ then, by $\Dc$, we get that $N\in\Down(S)$.
By a similar argument, we get that $y\in\Down(N)$ for all $y\in H_2$ and so also $S\in\Down(N)$.
Ultimately, therefore, $\Down=X^2$, so that all points are $\star$-recurrent and $\star$-equivalent to each other.
In other words, $\Node(x)=X$ for every $x$.
As above, $\Gamma$ consists in just a node and no edges.
In particular, this system has a single stream structure.

[Attractor-repellor pair on a circle]

Consider the same setting of the previous example and switch the flow on $H_1$, so that points on both $H_1$ and $H_2$ are moving towards $S$.
Then $\Down(N)=X$, as above, while $\Down(S)=\{S\}$.
For each point $x$ in either $H_1$ or $H_2$, $\Down(x)$ is the closed arc, on the half-circle containing $x$, between $x$ and $S$.
Hence, no point besides $N$ and $S$ is $\star$-recurrent
and each of those two fixed points is a node in itself.
Moreover $N\leadsto S$, so that $\Gamma$ consists in the two nodes $N$ and $S$ and an edge from $N$ to $S$.
Notice that, in this case, $\Down=\overline{\cO}$, namely this is the smallest possible stream structure for this semi-flow.

[Enlarging a node]
Consider the previous example and denote by $\Down$ its stream structure.
Notice that $\Down$ consists in the following points: (1) all  pairs $(x,y)$, with $y$ between $x$ and $S$ in the arc containing $x$; (2) all pairs $(N,x)$ for $x\in X$ (see Fig. <ref>(left)).
Now, let $x_1\in H_1$ and $x_2\in H_2$ and define $\Down_1$ as the set obtained by adding to $\Down$ the following pairs:
(1) all pairs $(x,x_1)$ for $x$ between $x_1$ and $S$ in $H_1$; (2) all pairs $(x,x_2)$ for $x$ between $x_2$ and $S$ in $H_2$.

The set $\Down_1$ is a stream structure,
as illustrated in Fig. <ref>(right).
Just as $\sR_{\Down}$, the set $\sR_{\Down_1}$ has  two nodes: $\Node(N)$, that is equal to $X$ even for $\Down_1$, and $\Node(S)$, that is now the closed arc between $x_1$ and $x_2$ containing $S$.
The graph did not change: $\Gamma_{\Down_1}=\Gamma_{\Down}$.
Notice that, in this case, $\Node(S)$ is positively invariant but not invariant under the semi-flow.

[A relation  satisfying $\Dc,\Dt,\Do$ but not $\Db$]
Consider the previous example and denote by $\Down$ its stream structure.
Notice that $\Down$ consists in the following points: (1) all  pairs $(x,y)$, with $y$ between $x$ and $S$ in the arc containing $x$; (2) all pairs $(N,x)$ for $x\in X$ (see Fig. <ref>(left)).
Now, let $x_1\in H_1$ and $x_2\in H_2$ and define $\Down_1$ as the set obtained by adding to $\Down$ the following pairs:
(1) all pairs $(x,x_1)$ for $x$ between $x_1$ and $S$ in $H_1$; (2) all pairs $(x,x_2)$ for $x$ between $x_2$ and $S$ in $H_2$.

The set $\Down_1$ is a stream structure,
as illustrated in Fig. <ref>(right).
Just as $\sR_{\Down}$, the set $\sR_{\Down_1}$ has  two nodes: $\Node(N)$, that is equal to $X$ even for $\Down_1$, and $\Node(S)$, that is now the closed arc between $x_1$ and $x_2$ containing $S$.
The graph did not change: $\Gamma_{\Down_1}=\Gamma_{\Down}$.
Notice that, in this case, $\Node(S)$ is positively invariant but not invariant under the semi-flow.

An example of a flow where there is a point $x$ that is non-wandering but is not in its own limit set $\omega(x)$. The space is a Mobius strip where the left side and right side are identified with a twist: The upper left edge is identified with the lower right edge.  The top and bottom of the strip can be assumed to consist of fixed points.
The horizontal middle line $M$ is the line equidistant from the top and bottom edges in the figure. It is invariant. It has two fixed points $p_1,p_2$ and $x\in M$ is any point between them in the figure. bla bla
The point $x$ is on the
A point $y$

(left) The set $\Down\subset\bS^1\times\bS^1$ in Ex. <ref> is painted in green.
(right) The set $\Down_1$ of Ex. <ref>, a [we need a term to say that $\Down_1\supset\Down$] of the $\Down$ set in the left.
The rectangle illustrates how to verify geometrically axiom $\Dt$.

[$\varepsilon$-recurrence]The following example is important for control theory, when $x$ maps to $f(x)+u$ for $|u|\leq\varepsilon$.

Let $f$ be a continuous map on $X$ and $\varepsilon>0$. Define

\Down_\varepsilon=\{(x,y): d(y,f(x))\leq\varepsilon\}.

Then $\Down_\varepsilon$ satisfies axioms $\cD$, so it is a Downstream structure.

Consider the specific case $X=\mathbb R$ and $f(x)=x/2$.
Then $x\leadsto x$ whenever $|x|\leq2\varepsilon$ but $x$ is a fixed point only for $x=0$.
In particular, $\Node(0)=[-2\varepsilon,2\varepsilon]$ and $f(\Node(0))$ is strictly smaller than $\Node(0)$.

Prolongations of trajectories.
Generalized recurrence.

Let $P$ be the set of pairs in Auslander's super-prolongation.
Then $P$ is a downstream structure and it is the smallest downstream structure.
In particular, each downstream structure $P'$ (based on $F$) contains $P$.

Let $\Down_1$ and $\Down_2$ be stream structures for a semi-flow $F^t$ with graphs, respectively, $\Gamma_1$ and $\Gamma_2$.
Assume they have the same nodes (considered as subsets of $X$) and
let $N_1$ and $N_2$ be two nodes.
Then $N_1\leadsto N_2$ is true for $\Down_1$ if and only if is true for $\Down_2$, , $\Gamma_1=\Gamma_2$.

Let $\Down$ and $\Down^*$ be two stream structures for the semi-flow $F^t$, with graphs, respectively, $\Gamma$ and $\Gamma^*$.
Assume that each node of $\Down$ is a subset of a node of $\Down^*$ and
let $N_1\subset N_1^*$ and $N_2\subset N_2^*$,
where $N_1,N_2$ are nodes of $\Down$ and $N_1^*,N_2^*$ are nodes of $\Down^*$.
Then, if $N_1\leadsto N_2$ in $\Down$, then $N_1^*\leadsto N_2^*$ in $\Down^*$, , $\Gamma$ maps into $\Gamma^*$.

Notice that, in the above conjecture, it is possible that $N_1\neq N_2$ while $N_1^*=N_2^*$.

§.§ Important extensions of $\Fto$

§ MAIN PROPERTIES OF NODES AND GRAPH

Notice that $\Om(z)=Circ$, and $x\in Circ$ and $\Om(x)=\{S\}$, so $x\notin \Om(x)$. Notice that $\Node(x)=Circ$, so it is strictly larger than $\Om(x)$.

The following properties follow immediately from the axioms:

* ($\cD_{clos}$). Assume $C$ is compact. Then $\Down(C)$ and $\Up(C)$ are closed.

* ($\cD_{\cO}, \cD_{clos}$). $\Om(x)\subset\Down(x)$.

* ($\Dt$) $x\in\Down(y)$ and $y\in\Down(x)$ if and only if $x,y\in\sR$ and $\Node(x)=\Node(y)$.

1. The set $\Down$ is a closed set of pairs by $\Dc$.
For a continuous map $\pi$ and a compact set $Q$, the inverse image $\pi^{-1}(Q)$ is closed.
Let $\pi$ be the projection from $\Down$ to $X$ defined by $\pi((x,y))=x$ and notice that $\Down(Q)=\pi^{-1}(Q)$.
Hence, $\Down(Q)$ is closed.
The proof for $\Up(Q)$ is similar.

2. This follows immediately from $\cD_{clos}$ plus $\cD_{\cO}$.

3. We leave this proof to the reader.

Now we discuss transitivity. Recall,

$\Dt$: if $y\in\Down(x)$, then $\Down(y)\subset\Down(x)$,,
if $x\leadsto y$ and $y\leadsto z$, then $x\leadsto z$.

By applying $\Dc$ and $\Dt$ to $\Db$, we obtain the following important characterization of $\Down(x)$.

For all $x$,
(x) = (x)∪((x)).

Let $A$ denote the left side of Eq. <ref> and $B$ the right.
We need to prove that $A\supset B$ and $A\subset B$.

The first inclusion is trivial.
Now, let $z\in\Down(x)$.
By $\Db$, either $z\in\cO(x)$ or $y\leadsto z$ for all $y\in\cO(x)$.
In the second case, by $\Dc$, $z\in\Down(\omega(x))$.
Hence, $A\subset B$.

In the reminder of the article, we are going to use consistently this stronger version of Thm <ref> in place of the original one.

Probably not useful

Without transitivity, distinct nodes can have points in common.

$\cD^w_{trans}$: if either

$z\in\cO(y)$ and $y\in\Down(x)$

$z\in\Down(y)$ and $y\in\cO(x)$,

then $z\subset\Down(x)$.

Using $\cD_{clos}$, we see that we can replace the orbit with its closure in the axiom above.

Relation between limit sets, orbits and $\star$-recurrence.

Notice that points of $\Om(x)$ are  not necessarily recurrent (see Fig. <ref>).
It is therefore perhaps surprising that, as the proposition below shows, every limit point is $\star$-recurrent.

Assume that $\Om(x)$ is non-empty.
Then $\Om(x)$ is a $\star$-equivalent set, namely $\omega(x)\subset\sR$ and
$y\lra z$ for all $y,z\in\Om(x)$.

There exists a sequence $t_n\to\infty$ so that $y_n\bydef F^{2t_n}(x)\to y$ and $z_n\bydef F^{2t_n+1}(x)\to z$.
We can assume $y\neq z$, since otherwise is trivial.

Then $(y_n,z_n)\in\Down$, so $(y,z)\in\Down$.
There is no difference in assumptions between $y$ and $z$, so $(z,y)\in\Down$.
Hence, $y\lra z$.

In particular, this means that each limit-set $\Om(x)$ is contained in a node.

If $x$ is recurrent, $\cO(x)\subset\omega(x)\subset\Node(x)$.

Next proposition shows that both $\cO(x)$ and $\omega(x)$ are inside $\Node(x)$ even when $x$ is just $\star$-recurrent.

If $x$ is $\star$-recurrent,
the set $\cO(x)$ is  $\star$-equivalent.
In particular, $\cO(x)\cup\Om(x)\subset\Node(x)$.

If $x$ is periodic, then $\cO(x)=\Om(x)$ and the claim follows

since every point in a periodic orbit is down from every other point of the orbit.

Assume now that $x$ is not periodic.

Since $x\in\sR$ and $x$ is not fixed, there exist $y\in\sR$, with $y\neq x$, such that $x\lra y$, namely $x\Sto y$ and $y\Sto x$.

Let $z\in\cO(x)$.
Since $x\Fto z$, then, by $\Dt$, it is sufficient to show that either $z\Sto x$ or $z\Sto y$.

Recall that, by $\Db$, $\Down(x)=\cO(x)\cup\Down(z)$.
Since $z\in\Down(x)$, then either $y\in\cO(x)$ or $y\in\Down(z)$.
The only non-trivial case is when $y\in\cO(x)$ and $y\Fto z$.
In this case $z\in\cO(y)$ and so, again by $\Db$, we get that
Since $x\in\Down(y)$, the only non-trivial case is that $x\in\cO(y)$.
But then $\cO(x)=\cO(y)$,

namely the orbit is periodic, against our working assumption.
Hence, $x\lra z$ for every $z\in\cO(x)$, namely $\cO(x)\subset\Node(x)$.
By $\Dc$, this also implies that $\Om(x)\subset\Node(x)$.

Let $z\in\Down(x)\cap\sR$.

We need to prove that $z\in\Down(y)$.

First, assume that $y\in\cO(x)$.
Then, by $\Db$,
If $z\in\cO(x)$ then, since $z\in\sR$, by Prop. <ref>, $\cO(z)$ is $\star$-equivalent and therefore $z\lra y$. Hence, in either case, $z\in\Down(y)$.

Now, assume that $y\in \Om(x)$.
In this case, by Thm. <ref>, $\Down(x)=\cO(x)\cup\Down(y)$.
If $z\in\cO(x)$, then $\cO(z)$ is $\star$-equivalent and, by Cor. <ref>, $\overline{\cO(z)}\subset\Node(z)$.

Hence $y\in \Om(x)=\Om(z)\subset\Node(z)$ and so, in either case, $z\in\Down(y)$.

In the next proposition, we consider the natural flow induced on $X\times X$ defined by

The set $\sR$ is closed and each node is closed.

Let $x_n$ be a sequence of $\star$-recurrent points such that $x_n\to x$ in $X$ as $n\to\infty$.
If $x$ is fixed, then $x\in\sR$, so we can assume that $x$ is fixed either and there is a $t>0$ such that $y\bydef F^t(x)$ is not equal to $x$.
We can furthermore assume, taking a subsequence if necessary, that none of the $x_n$ is fixed either and that $y_n\bydef F^t(x_n)$ is not equal to $x_n$.
By Prop. <ref>, all points of $\cO(x_n)$ are mutually $\star$-equivalent,

so that $y_n\leadsto x_n$ and $x_n\leadsto y_n$ for every $n\geq1$.

By $\Dc$, therefore, $x\leadsto y$ and $y\leadsto x$, so that $x\in\sR$.

To prove that each node is closed, we can use the above argument with the assumption that the $x_n$ are in the same node, so $x_n\lra x_m$ for all $n,m$, so that $x_n\lra x$ for all $n$.

The following holds:

* Assume that $X$ is compact.
Then, for every $x$, there exist a recurrent point for $F$ in $\Om(x)$.

Let $y\in\Om(x)$.
If $y$ is not recurrent, then $y\not\in\Om(y) $ and so $\Om(y)$ is a proper subset of $\Om(x)$.
Let $\Lambda$ be the set of all subsets of $\Om(x)$ that are the limit set of some point in $\Om(x)$.
The collection of such sets is partially ordered by inclusion.
By Zorn's lemma, there is a maximal ordered collection of these sets.
They are all compact, so their intersection $\Omega^*$ is compact and non-empty.
Since the intersection of invariant sets is invariant, for each $y\in \Omega^*$ we have that $\Om(y)\subset \Omega^*$.
By maximality, $\Om(y)$ must be in the chain  and it cannot be strictly smaller than $\Omega^*$.
Hence, $y\in\Om(y)=\Omega^*$.

If $X$ is compact, every node contains a recurrent point.

Let $N$ be a node and $x\in N$.
Since $\cO(x)\subset N$ (Prop. <ref>) and $N$ is closed (Prop. <ref>), $\omega(x)\subset N$.
Hence, by the lemma above, there is a recurrent point in $N$.

The following sets are all positively invariant under $F^t$ for each $t\geq0$:

* $\Down$;

* $\Down(C)$ for any $C\subset X$;

* each node $N$.

We start by showing that
$F^t(\Down(x))\subset\Down(x)$ for all $t\geq0$.
Let $y\in\Down(x)$, , $x\leadsto y$.
It suffices to show that $F^t(y)\in\Down(x)$.
This follows from $\Dt$.

Finally, since $F^t(\Down(x))\subset\Down(x)$ for every $x$ and $\Down(C)=\cup_{x\in C}\Down(x)$, it follows that also $F^t(\Down(C))\subset\Down(C)$.

We now show that $F^t(\Down)\subset\Down$.
Assume $x\leadsto y$.
We need to prove that $F^tx\leadsto F^ty$.
By $\Db$ there are two cases: either $y\in\cO(x)$, in which case the result is clearly true, or $\Om(x)\leadsto y$.
In the latter case, $F^tx\leadsto\Om(x)\leadsto y\leadsto F^ty$.

Finally, let $N$ be a node and let $x\in N$.
By Prop. <ref>,
since $x\in \sR$, $x\lra F^tx$, so $F^tx\in N$.

Trapping regions.

A set $Q\subset X$ is a trapping region (for $X$) if $F(Q)$ is a subset of the interior of $Q$. We say that $Q$ is globally attracting (in  $X$) if, for each $x\in X, F^j(x)\in Q$ for some $j\ge 0$.

The most relevant case for us is when $X$ has a compact globally attracting trapping region $Q$.
Under these assumptions, the reader can check that:

* for each $x$, there is a $y\in\cO(x)$ such that $\cO(y)\subset Q$;

* for each $x$, $\Om(x)$ is non-empty and $\Om(x)\subset Q$.
In particular, for each $x$, there exist a node $N$ such that $\Om(x)\subset N$.

Let $X=(0,1)$ and $F(x)=ax(1-x)$ where $2 <a<4$. Then $F(\frac{1}{2}) = \frac{a}{4}>\frac{1}{2}$, and
0< 1-a/4<1/2<a/4<1.
Then $Q_\beta :=[1-\frac{a}{4},\frac{a}{4}]\subset X$ is a compact globally attracting trapping region for $X$.

Recall that a set is called connected if it is not the union of two closed disjoint subsets. “Closed” here means that if $x_n$ is a convergent sequence in a closed set, then its limit point is also in the closed set.
Recall, finally, that $\sR$ is a closed set (Thm. <ref>).

We say that a graph $\Gamma$ is connected if, whenever $\sR$ can be written as the union of two invariant disjoint closed sets $N_1$ and $N_2$, there is an edge connecting $N_1$ and $N_2$;  there exist $\star$-recurrent points $x\in N_1,y\in N_2$ such that either $x\leadsto y$ or $y\leadsto x$.

PUT SOMEWHERE:
It is quite common for a graph to have only finitely many nodes.

We must decide whether to keep this remark or the one right below Def3.1.

Remark on trapping regions.
Let $Q\subset X$ be compact and forward-invariant, , $F^t(Q)\subset Q$ for $t\geq0$.
If $x\in Q$, then $\Om(x)\subset Q$ is non-empty and there exists a node $N\subset Q$ such that $\omega(x)\subset N$.

MOVE OR DELETE

If $F(Q)=Q$, then there is a backward trajectory that limits at a node.

Connectedness of the graph.

§ IMPORTANT CASES OF $\STAR$-RECURRENCE

The non-wandering set.

Def of NW

Auslander's generalized recurrence.
paperi rilevanti: Garay 1985 <cit.>, Wiseman 2018 [37], Auslander 1963 [5], Auslander and Seiberg 1963 <cit.>, Auslander and Seiberg 1964 <cit.>, Ding 2016 <cit.>

paperi rilevanti: Hurley 1995 [22]

Strong Chain-recurrence.

§ TOP AND BOTTOM NODES

In a compact set, the following hold:

1. the union of nodes in a maximal chain is compact;

2. each maximal tower of nodes has a top node and a bottom node.

A node $N$ is a top node if there are no nodes upstream of it (for example, a repelling fixed point)

and is a bottom node if there are no nodes downstream of it (for example, when the node is an attractor).

Notice that this node is unique since, if $M_0$ and $M_1$ are upstream nodes, then $M_0\leadsto M_1$ and $M_1\leadsto M_0$ and so $M_0=M_1$.

Assume $\Om(x)$ is compact and non-empty.
Then $C\Om(x)$ is a union of nodes.
The node containing $\Om(x)$ is upstream of all nodes in $C\Om(x)$.

For example, suppose
$\Om(x)$ is a saddle fixed point $y$.
The unstable manifold of $y$ may go to several nodes, all of which would be in $C\Om(x)$.

If $x$ is $\star$-recurrent, it is in a node $N$ and $N$ is the top node in $C\Om(x)$.

The above needs a proof if it is true.

Assume that $(X,F)$ has a compact globally attracting trapping region $Q$ and let $\cN$ be a collection of nodes $N$ of a stream structure of $F$.

Then, for each node $N\in\cN$, there is a top node $T$ and a bottom node $B$ such that $T\Sto N\Sto B$.
In particular, there are a top and a bottom node for $\cN$ (not necessarily in $\cN$).

By Zorn's Lemma, there is a maximal ordered chain $\cT$ of nodes in $\cN$ (ordered by $\leadsto$).
For each node $N\in\cT$, set
$U^+_N = \Up(N)\cap\sR$.
This is the union of all points belonging to nodes that are upstream from $N$.

Since $\sR\subset Q$ is compact, also $U^+_N$ is compact.
Furthermore, the collection of all the $U^+_N$, for $N\in\cN$, is a nested set of compact sets. Hence, its intersection $V$ is non-empty and compact and consists of points that are mutually $\star$-equivalent.

Hence, $V$ is contained in a top node $N_{top}$.

Given two graphs $\Gamma,\Gamma'$, we say that $\Gamma'$ is a subgraph of $\Gamma$ if the set of nodes of $\Gamma'$ is a subset of the set of nodes of $\Gamma$ and, if there is an edge from node $N$ to node $M$ in $\Gamma'$, there is an edge from node $N$ to node $M$ in $\Gamma$.

Given a graph $\Gamma$ of a stream structure, we call tower any subgraph $\Gamma'\subset\Gamma$ such that there is an edge between each $M,N\in\Gamma'$.
We say that $\Gamma'$ is a maximal tower if it contains both a top and a bottom node.

Let $F$ be a semi-flow on a compact topological space $X$ and $\Gamma$ the graph of a stream structure of $F$.

Then, given any tower $T$ of $\Gamma$, there is a maximal tower $T'$ of which $T$ is a subgraph.

Let $\cM$ be a set of nodes $M_s$. Assume $\cM$ is a maximal ordered chain. First some definitions:

1. Let  $U$ be the set of $y\in M_s$ for all $M_s\in\cM$.

2. For $x\in U$, let $U_x^+$ be the set of all $y\in U$ for which $y\leadsto x$.

3. For $x\in U$, let $U_x^-$ be the set of all $y\in U$ for which $x\leadsto y$.

Then $U$, $U_c^+$, and $U_c^-$
are closed.

I have changed these sets to be sets of points instead of nodes.

Suppose, contrary to the assumption that $U$ is not closed, that there exists $x\in\overline{U}\setminus U$.
Then $x$ is $\star$-recurrent by Prop. <ref>???, so $x$ is in some node $N$, where $N\cap U$ is empty.

Let $U_x^\pm=U_x^+\cap U^-_x$.
If $U_x^\pm$ is empty, then $\cM'=\cM\cup\{N\}$ is an ordered chain of nodes, since either $M_s\leadsto N$ or $N\leadsto M_s$ for each $M_s$ in $\cM$.
This contradicts the maximality of $\cM$.
Then $U_x^\pm$ is not empty and it is a node.
For each $\epsilon>0$, there exists an $M_s$ which contains points $m_1,m_2$ such that $\dist(m_1,x)<\epsilon/2$ and $\dist(m_2,z)<\epsilon/2$ for some point $z\in U_x^\pm$.
Since $m_1,m_2$ are in the same node, there exists a $\epsilon/2$-chain from $m_1$ to $m_2$.
Therefore that chain is an $\epsilon$-chain from $x$ to $z$.
So $x\leadsto z$.
By a similar argument, $z'\leadsto x$ for some $z'\in U_x^\pm$.
Since $U^\pm_x$ is a node, $x$ must belong to it and so $x\in U$, contradicting our initial hypothesis that $x\in\overline{U}\setminus U$.
Therefore $U$ must be closed.

§ OTHER STUFF ON GRAPHS

Conjecture: all “well-known” types of recurrence produce the same graph, provided the number of nodes is at most countable.
Note that non-wandering can have intersecting nodes, which is not allowed by $\Dt$.

§.§ An $L^1$ graph definition.

The simplest case where $L^1$-nodes differ from regular nodes is the dynamical system given by the identity map on a connected set $X$.

Then, for $x,y\in X$, $x\lra y$ and so all points of $X$ belong to the same node.
However, using $L^1$-$\epsilon$-chains, each point in $X$ is a distinct $L^1$-node.

For another example where the two definitions give rise to different nodes, consider the differential equation
u̇ = v,

v̇ = -u.
The $L^1$-nodes are the invariant circles centered at $(0,0)$ since, if there is an $L^1$-$\epsilon$-chain from $x$ to $y$ for every $\epsilon$, then $x$ and $y$ are on the same trajectory, a circle centered at the origin; however, for the regular definition, all points belong to the same node, because there is an $\epsilon$-chain from each $x$ to each $y$.
For both kinds of chains, the graph has no edges in these examples.

Graphs are metric spaces.
For two $\star$ recurrent points $x, y$,
define $\rho(x,y) := \min \eps$ such that there is an $\eps$-chain from $x$ to $y$.
If $y$ is downstream from $x$, then  $\rho(x,y)=0$, and in general  $\rho(x,y) \ne\rho(x,y)$.
We have defined $\rho$ only for $\star$ recurrent points. In particular, $\rho(x,y)=0$ if and only $x$ and $y$ are in the same node.
More generally, the value of $\rho(x,y)$ depends only on the nodes $x$ and $y$ are in. Hence
for nodes $N$ and $N^*$, we set
ρ(N,N^*) = ρ(x,y) for any  x ∈N and y ∈N^*.
Now, define
(N,N^*) := ρ(N,N^*)+ρ(N^*,N).

It follows that $\Dist(N,N^*) = 0$ if and only if $N = N^*$.
Notice that, for $\star$ recurrent points $x, y, z$,
ρ(x,y) + ρ(y,z) ≥ρ(x,z).
This triangle inequality implies that $\Dist$ also satisfies a triangle inequality on any nodes
$N, N^{*}$, and $N^{**}$, ,
(N,N^*) + (N^*,N^**) ≥(N,N^**).

Let $g$ be as above, and let $X$ be an interval containing $Q$. Then there is a continuous function $\Gamma:X\to\bR$ (with Lipschitz constant 1) such that

|\Gamma(x_1)-\Gamma(x_2)| = \dist(x_1,x_2)

for every $x_1,x_2\in Q$.

If $x_1$ and $x_2$ are nodes, then $\dist(x_1,x_2)\leq|x_1-x_2|$.
For a node $x_0$, let $w(x_0)=\{(x,y):x\in Q, y\in\bR, \dist(x_0,x)\geq y\}$.

[A node without edges in a graph with infinitely many nodes]An example of a node that is a top and bottom node at the same time and is in a connected graph with infinitely many nodes.
The scalar ordinary differential equation
dx/dt = - x^2sinπ/x
where the right-hand side is defined to be 0 at $x=0$. For integers $n\neq 0$, the points $x=\pm\frac{1}{n}$ are fixed points and are attracting odd for $n$ and repelling for even. Notice that all trajectories with $x(0)>1$ are attracted to the point $x=1$ while those with $x(0)<-1$ are attracted to the point $x=-1$.
Hence there are a countable number of nodes, and there is an edge between adjacent nodes, one of which is an attractor and a top node and the other is a repellor and a bottom node.
The graph is a connected curve that includes the node $x=0$. However, there are no edges to or from that node. Hence it is both a top and a bottom node. This graph is plotted as a saw tooth plot with top nodes higher than the bottom nodes they connect to. An infinite number of nodes converge to the node at $x=0$.

Let $K\subset\bR$ be a compact set that contains no intervals.
Assume $g:\R\to\R$ is a differentiable function such that $g(x)=0$ if and only if $x\in K$ and consider the ODE
dx/dt = g(x).
Suppose that (2) has a globally attracting compact set $Q$, so that $K\subset Q$.
Each node of the graph corresponds to a unique point of $K$, so we write that $x$ is a node iff $g(x)=0$.

Let $K$ be a middle-thirds Cantor set, and assume $g:\R\to\R$ is a differentiable function such that $g(x)=0$ if and only if $x\in K.$
Assume $x_1 < x_2$ are two points of $K$ such that no points of $K$ are in $(x_1,x_2)$. Hence $g(x)\neq 0$ for $x \in (x_1, x_2)$. There are countably many such pairs, and most nodes are not in such a pair. If $g>0 $ on $(x_1, x_2)$, then there is an edge from $x_1$ to $x_2$.
dx/dt = g(x).
The nodes of the graph are the points of $K$, so there are uncountably many nodes. Need more about the graph.

* Is $\sR(F^k)=\sR(F)$? True only for some structure, see Wiseman (2016). It is true for GR and CR but not all SCR.
* If $F^t(A)\subset A$ for all $t\geq0$, is $\sR(F|_A)=\sR(F)\cap A$? Nope, see next item.
* In particular, is $\sR(F|_{\sR(F)})=\sR(F)$? Nope, it does not hold for GR (and so for SCR).Good to verify why it does not work.

§ REACTION-DIFFUSION PDES

§.§ Our PDE stuff

§.§.§ Looking for PDEs with infinite graphs.

Let $\mathbb T^n$ be the $n$-torus written as $[0,2\pi]^n$ with periodic boundary conditions.

Let $u(t,x)=(u^i(t,x))\in\bR^k$ be $2\pi$-periodic in each coordinate $x^1,\dots,x^n$.
Assume that, for all $t\geq0$, $u(t,\cdot)\in L^2(\mathbb T^n)$ and satisfies the

PDE system

u̇^1    = Δu^1 +λf^1(u^i),

u̇^k    = Δu^k +λf^k(u^i) .

For $\lambda$ small enough, the graph of (<ref>) contains only functions constant in space, i.e. each chain-recurrent solution $u(t,x)$ is independent on $x$.

The Chafee-Infante case – an argument using the Poincaré inequality.
We consider now the scalar RD PDE

u_t = u_{xx} + \lambda f(u),

in one space dimension with

$$f(u) = u-u^3.$$

This is the Chafee-Infante PDE.
We set periodic conditions on the PDE, namely $u(t,x)$ is $x$-periodic with period $2\pi$.
This PDE defines a flow on $H^2(\mathbb T^1)$.

Assume $0\leq\lambda<1$.
Let $u(t,x)$ be solution $u(t,x)$ of the Chafee-Infante PDE, where $u(t,x)=u(t,x+2\pi)$ for all $t\geq0$.
Then, if $u$ is chain-recurrent, $u_x$ is identically 0.

We will use below the following Poincaré inequality, which is stated in more generality in the Appendix:

u_x_L^2(𝕋^1)≤u_xx_L^2(𝕋^1) for each u∈H^2(𝕋^1).

V(u) = \frac{1}{2}\|u_x\|^2_{L^2}.

Then we have that

\blue \frac{d}{dt}V(u(t)) =

\langle u_x,\dot u_x\rangle_{L^2}

(integrating by parts)

-\langle u_{xx},\dot u\rangle_{L^2}

-\langle u_{xx},u_{xx}+\lambda f(u)\rangle_{L^2}

-\|u_{xx}\|^2_{L^2} - \lambda \langle u_{xx},f(u)\rangle_{L^2}

(integrating by parts)

-\|u_{xx}\|^2_{L^2} + \lambda \langle u_{x},f'(u)u_x\rangle_{L^2}

-\|u_{xx}\|^2_{L^2} - 3\lambda \langle u_x,u^2 u_x\rangle_{L^2} + \lambda\langle u_x,u_x\rangle_{L^2}=

\blue
-\|u_{xx}\|^2_{L^2} - 3\lambda\|u u_x\|^2_{L^2}+ \lambda\|u_x\|^2_{L^2}.

Therefore, by the Poincaré inequality (<ref>),
d/dtV(u(t)) ≤-u_xx^2_L^2 - 3λuu_x^2_L^2 + λu_xx^2_L^2.
Hence, for all $\lambda\in[0,1)$, we have that $\frac{d}{dt}V(u)\leq0$. For such $\lambda$, therefore, any solution $u(t)$ defined for all $t\geq0$ converges to a solution whose second space derivative is identically zero. Together with the boundary periodic conditions,

this means that $u(t)$ must converge to a function constant in space.

More general $f(u)$ for scalar $u$.

The “Lorenz-diffusion” case.

Consider the system

\begin{cases}
\dot u &=\Delta u + \lambda (-{\blue\sigma} u + {\blue\sigma} v)  \\
\dot v &=\Delta v + \lambda ({\blue r} u -uw - v)\\
\dot w &=\Delta w + \lambda (uv - {\blue b} w)  % ending with \\ produces an extra equation number, 4 numbers in total.
% \end{split}
\end{cases}

on $L^2(\mathbb T^1)$.
We call this system the “Lorenz-diffusion” PDE.

An alternative form of this PDE, after a time rescaling, is

\begin{cases}
\dot u &=\frac{1}{\lambda}\Delta u +  (-{\blue\sigma} u + {\blue\sigma} v)  \\
\dot v &=\frac{1}{\lambda}\Delta v +  ({\blue r} u - uw - v)\\
\dot w &=\frac{1}{\lambda}\Delta w +  (uv - {\blue b} w).  % ending with \\ produces an extra equation number, 4 numbers in total.
% \end{split}
\end{cases}

For $\lambda$ sufficiently small, the nodes of the Lorenz-diffusion PDE and of the Lorenz ODE are the same; , each chain-recurrent solution $(u(t,x),v(t,x),w(t,x))$ of the PDE is independent of $x$. As a function of $t$, it is a solution of the Lorenz ODE.

There is a $R>0$ such that each solution of the Lorenz-diffusion PDE enters a $L^2$-ball of radius $R$ in finite time.

W(u,v,w) = r \|u\|^2_{L^2} + \sigma \|v\|^2_{L^2} + \sigma\|w-2r\|^2_{L^2}.

Then, over any solution of the PDE,

\frac{d}{dt}W =

2r\langle u,\dot u\rangle_{L^2}
2\sigma\langle v,\dot v\rangle_{L^2}
2\sigma\langle w-2r,\dot w\rangle_{L^2}

2r\langle u,\Delta u+\lambda (-\sigma u + \sigma v)\rangle_{L^2}

+ 2\sigma\langle v,\Delta v + \lambda (-uw+r u - v)\rangle_{L^2}

+2\sigma\langle w-2r,\Delta w + \lambda (uv - b w)\rangle_{L^2}=

(integrating by parts)

-\|\nabla u\|^2_{L^2}-\|\nabla v\|^2_{L^2}-\|\nabla w\|^2_{L^2}

-r\|u\|^2_{L^2}+{\blue r\langle u,v\rangle_{L^2}}
-{\red \langle v,uw\rangle_{L^2}}
+{\blue r\langle u,v\rangle_{L^2}}-\|v\|^2_{L^2}

+{\red \langle w,uv\rangle_{L^2}}-b\|w\|^2_{L^2}
-{\blue 2r\langle u,v\rangle_{L^2}}+2rb\langle 1,w\rangle_{L^2}

(using Holder inequality $\langle 1,w\rangle_{L^2}=\|w\|_{L^1}\leq \|1\|_{L^2}\|w\|_{L^2}$)

\leq
-\|\nabla u\|^2_{L^2}-\|\nabla v\|^2_{L^2}-\|\nabla w\|^2_{L^2}

\|w\|_{L^2}),

where $S=\|1\|_{L^2}$.
This quantity is negative for all $\|u\|^2_{L^2},\|v\|^2_{L^2},\|w\|^2_{L^2}$ large enough for the very same reason it is so in case of the Lorenz ODE system on $\bR^3$.

Remark: seems to me that, with the argument above, one can show that, if an ODE system
$$\dot {\mathbf x}=F({\mathbf x})$$
has bounded solutions, then the solutions of the corresponding parabolic PDE system
$$\dot{\mathbf u}=\Delta {\mathbf u}+F(\mathbf u)$$
are bounded as well.

In particular, what we prove here for the “Lorenz-diffusion” system should actually hold for the PDE version of any other dissipative vector field $F$.

For all $\lambda >0$ small enough, the functional

V(u,v,w) = \frac{1}{2}\|u_x\|^2_{L^2}+\frac{1}{2}\|v_x\|^2_{L^2}+\frac{1}{2}\|w_x\|^2_{L^2}

is eventually decreasing on the solutions of the Lorenz-diffusion PDE.

Let $(u(t),v(t),w(t))$ be a solution of the Lorenz-diffusion PDE. Then

\frac{d}{dt}V(u(t),v(t),w(t)) =
\langle u_x,\dot u_x\rangle_{L^2}
\langle v_x,\dot v_x\rangle_{L^2}
\langle w_x,\dot w_x\rangle_{L^2}

-\langle u_{xx},\dot u\rangle_{L^2}
-\langle v_{xx},\dot v\rangle_{L^2}
-\langle w_{xx},\dot w\rangle_{L^2}

-\langle u_{xx},u_{xx} + \lambda (-\sigma u + \sigma v)\rangle_{L^2}

-\langle v_{xx},v_{xx} + \lambda (-uw+\rho u - v)\rangle_{L^2}

-\langle w_{xx},w_{xx} + \lambda (uv - \beta w)\rangle_{L^2}

+\sigma\langle u_{x}, v_x\rangle_{L^2}

-\langle v_{x},u_xw+uw_x\rangle_{L^2}
+\rho \langle v_{x},u_x\rangle_{L^2}
-\rho \|v_{x}\|^2_{L^2}

+\langle w_{x},u_xv+uv_x\rangle_{L^2}

Using the bound on norms of $u,v,w$ established in the proposition above and using Poincaré inequality to bound the gradients, we get that $dV/dt$ is bound from above by a quadratic form having coefficients $-1$ on the diagonal and $\lambda$ times some finite coefficients in all off-diagonal terms.
For $\lambda$ small enough, this quadratic form is negative-definite.

Hence, all solutions of the Lorenz-diffusion PDE are $L^2$-bounded and no solution with a non-zero space gradient can be recurrent.

§.§.§ Hamiltonian-diffusion parabolic PDEs.

Consider a Hamiltonian dynamical system given, on $\bR^n$,

§.§.§ Gradient systems of quasilinear PDEs have a finite graph.

We consider here the PDE system

u̇^1    = Δu^1 + f^1(u^i)

u̇^k    = Δu^k + f^k(u^i) .

Assume that the vector field $(f^1,\dots,f^k)$ is a gradient vector field.
Then the graph of System (<ref>) has a finite number of nodes and every node is a fixed point (equilibrium solution).

Assume that the vector field $F=(f^1,\dots,f^k)$ is a gradient vector field and that $F=\nabla U$.

L(u^1,\dots,u^k) = \frac{1}{2}\sum_{i=1}^k\|\nabla u^i\|^2_{L^2(\Omega)} + \langle U(u^1,\dots,u^k),1\rangle_{L^2(\Omega)}

is a Lyapunov function for System (<ref>).

Consider a curve $\{u^i(t)\}\in L^2(\Omega)$ solution of System (<ref>).

\frac{d}{dt}L(u^1,\dots,u^k)

\sum_{i=1}^k\left[\langle\nabla u^i,\nabla\dot u^i\rangle_{L^2(\Omega)}
\langle f^i(u),\dot u^i\rangle_{L^2(\Omega)} \right]

\sum_{i=1}^k\left[-\langle\Delta u^i,\dot u^i\rangle_{L^2(\Omega)}
\langle f^i(u),\dot u^i\rangle_{L^2(\Omega)} \right]

-\sum_{i=1}^k\|\dot u^i\|^2_{L^2(\Omega)}\leq0.

Since there is a Lyapunov function, all limit points must be equilibria of the system. I am not sure, though, how to prove the finiteness of the number of nodes. In the single equation case, Lappicy claims that it is a consequence of the dissipativity but it's unclear to me what does he means.

§.§ Some general results from Robinson [32]
Throughout this section, we denote by $\Omega\subset\bR^n$ a bounded open set with a smooth boundary
and by $f:\bR\to\bR$ a $C^1$ function such that:

1. there are constants $c,k>0$ with $p>2$ such that, for all $s\in\bR$,

$$|s f(s)|\leq k+c|s|^p;$$

2. $f'(s)$ is bounded from above.

For instance, this holds for any non-linear odd polynomial with negative leading coefficient.

Consider the Reaction-Diffusion (RD) PDE given by

\begin{equation}
\label{eq:RD}
u_t = \Delta u+f(u),\; u(0,x)=u_0(x),\;u\big|_{\partial\Omega}=0.
\end{equation}

A function $u\in L^2(\Omega)$ has a weak partial derivative with respect to $x^i$ if there exist a function $v\in L^2(\Omega)$ such that

\int_\Omega u(x)\partial_i\varphi(x)\,dx
\int_\Omega v(x)\varphi(x)\,dx

for every $\varphi\in C^\infty_c(\Omega)$.

Notice that weak derivatives are unique as points of $L^2(\Omega)$ (i.e. modulo a set of points of measure zero).

We denote by $H^2(\Omega)$ the set of all $u\in L^2(\Omega)$ such that:

* $u$ has a weak gradient $\nabla u$;

* $\nabla u$ has a finite $L^2$ norm.

Notice that $H^2(\Omega)$ is a Banach space with respect to the norm

\|u\|_{H^2} = \|u\|_{L^2} + \|\nabla u\|_{L^2}.

Similarly, it is possible to define weak derivatives of any order and the corresponding spaces $H^k(\Omega)$ of $L^2$ functions that have $L^2$ derivatives of every order from 1 to $k$.

Let $k>n/2$. Then
$H^k(\Omega)\subset C^{k-[n/2]-1}(\Omega)$. In particular,

\bigcap_{k=1}^\infty H^k(\Omega)\subset C^\infty(\Omega).

We are interested in weak solutions of the RD PDE.
These are functions $u\in H^2(\Omega)$ such that

\int\limits_{\bR_+\times\Omega}
\left[
\nabla u(t,x)\nabla\varphi(t,x) + f(u(t,x))\varphi(t,x) - u(t,x)\varphi_t(t,x)
\right]
\,dx\,dt=

\int_\Omega u_0(x)\varphi(0,x)dx

for all $\varphi\in C_c^1([0,\infty]\times\Omega)$.

For every $T>0$, Eq. (<ref>) has a unique weak solution

u\in L^2([0,T],H^1_0(\Omega)){\blue \,\bigcap\,} L^p([0,T]\times H^1_0(\Omega)){\blue \,\bigcap\,} C^0([0,T],L^2(\Omega)).

The RD PDE

defines a continuous evolution semigroup

S:[0,\infty)\times L^2(\Omega)\to L^2(\Omega)

defined by $S^{t_1}(u(t_2,x))=u(t_1+t_2,x)$.

We say that the semigroup $S$ is dissipative if there exists a compact subset $Q\subset L^2(\Omega)$ such that, for each bounded set $B\subset L^2(\Omega)$, there is a $t_B$ such that $S^{t_B}(B)\subset Q$ for all $t\geq t_B$.

The set $Q$ is called an absorbing set for $S$.

Let $S$ be a dissipative continuous semigroup with absorbing set $Q$. Then $\Om(Q)$ is a global attractor for $S$.

A global attractor for a continuous semigroup $S$ is a maximal compact invariant set $A$ of $S$ that attracts all bounded sets, namely

\lim_{t\to\infty}\dist(S^t B,A)=0

for each bounded set $B$.

The RD PDE has an absorbing set in $L^2(\Omega)$ (resp. $H^1_0(\Omega)$). Equivalently, under the evolution semigroup $S$ defined by the RD PDE, there is a positive function $t_2:[0,\infty)\to[0,\infty)$ and a $\rho_2>0$ (resp. $t_1:[0,\infty)\to[0,\infty)$ and a $\rho_1>0$) such that $\|S^tu\|_{L^2}<\rho_2$ for every $t> t_2(\|u\|_{L^2})$ (resp. $\|S^tu\|_{H^1_0}<\rho_1$ for every $t> t_1(\|u\|_{H^1_0})$).

The RD PDE has a global compact attractor $A\subset L^2(\Omega)$.

is bounded in $H^2(\Omega)$. If $\Omega$ has a smooth boundary and $f$ is smooth, then $A$ is bounded in each $H^k(\Omega)$, $k=0,1,2,\dots$. In particular, $A\subset C^\infty(\overline{\Omega})$.

The RD PDE has a global compact attractor $A\subset L^2(\Omega)$.

The “Energy” functional

\Phi(u) = \frac{1}{2}\|\nabla u\|^2_{L^2(\Omega)} + \langle F(u),1\rangle_{L^2(\Omega)}

where $f(s) = F'(s)$,

is a Lyapunov functional on the global attractor $A$ of the RD PDE.

Consider a curve $u(t)\in L^2(\Omega)$ solution of $\dot u=u_{xx}+f(u)$.

\frac{d}{dt}\Phi(u)
\langle\nabla\dot u,\nabla u\rangle_{L^2(\Omega)}
\langle f(u),\dot u\rangle_{L^2(\Omega)}

=\dot u\,\Delta u|_{\partial\Omega}
-\langle\dot u,\Delta u\rangle_{L^2(\Omega)}
-\langle\dot u, f(u)\rangle_{L^2(\Omega)}

-\langle\dot u,\Delta u+f(u)\rangle_{L^2(\Omega)}
= -\|\dot u\|^2_{L^2(\Omega)}\leq0
%    \langle\dot u,\dot u\rangle =
%    \langle\dot u,u_{xx}+f(u)\rangle

§.§ Some properties of global attractors of parabolic PDEs

Let $A$ be the attractor of some RD PDE with semi-flow $\Phi^t$. We say that the dynamics on the attractor is finite-dimensional when, for some integer $n>0$, there is an ODE in $\mathbb R^n$ with flow $\Psi^t$ and invariant compact set $K\subset\mathbb R^n$ such that there is a Lipschitz invertible map $h:K\to A$ such that

h\circ\Psi^t = \Phi^t\circ h

for each $t>0$.

The dynamics on the global attractor of any system of RD PDEs on the circle (i.e. $\Omega=S^1=[-\pi,\pi]/\!\sim$) is finite-dimensional.

Let $H$ be a Banach space and $\Phi^t:H\to H$ an evolution semigroup on it.
An inertial manifold for $\Phi^t$ is a smooth manifold $M$ such that:

* $M$ is finite-dimensional;

* $\Phi^t(M)\subset M$ for all $t\geq0$;

* for every $u_0\in H$ there are constants $a,b>0$ such that

\dist(\Phi^tu_0,M)\leq ae^{-bt}.

Let $f_0$ be a real function with compact support. A PDEs n the circle (i.e. $\Omega=S^1=[-\pi,\pi]/\!\sim$) with $f(u)=u+f_0(u)$ admits an inertial manifold.

This theorem does not hold for systems of RD PDEs <cit.>.

Consider a system of RD PDEs on the circle with $f^i(u) = u^i + f^i_0(u)$, where the $f^i_0$ have compact support.
Then, for any $u_0\in H^1(S^1)$, there exists a unique solution

u\in C([0,T],H^1(S^1)){\blue \bigcap} L^2([0,T],H^2(S^1)), T>0

satisfying $u(0)=u_0$.
In particular, $\Phi^t u_0=u(t)$ is an evolution semigroup.
Moreover there exist constants $\gamma,C,C'>0$ and a monotonic increasing function $Q$ such that:

* $\|u(t)\|_{L^2}\leq Ce^{-\gamma t}\|u_0\|_{L^2}+C$;

* $\|u(t)\|_{H^2}\leq\frac{Q(\|u_0\|_{L^2})}{t^{1/2}}+C'$

Consider a system of RD PDEs on the circle as in the previous theorem.
Then the semigroup $\Phi^t$ has a global attractor $A\subset H^1(S^1)$.
Moreover, $A$ is bounded with respect to the $H^2$ norm.

Consider the PDE

u_t = a(x,u,u_x)u_{xx}+f(x,u,u_x),\;\;u(0,x) = u_0(x),\;\;x\in[0,\pi]

where $f\in C^2$, $a\in C^1$ satisfies $a(x,u,u_x)\geq\varepsilon>0$
and $u$ satisfies Neumann boundary conditions.
Suppose that all equilibria of the PDE are hyperbolic. Then:

* the global attractor $A$ of the PDE consists of finitely many equilibria $E$ and heteroclinic connections $H$;

* there is a heteroclinic orbit $u(t)\in H$ between two equilibria $u_\pm\in E$ so that

iff $u_\pm$ are adjacent and ...

Other general results.

1. The existence of global attractors for a class of reaction–diffusion equations with distribution derivatives terms in $\bR^n$ <cit.>

2. The existence of global attractors for the norm-to-weak continuous semigroup and application to the nonlinear reaction–diffusion equations <cit.>

3. Examples of global attractors in parabolic problems <cit.>

Bifurcations in the Györgyi-Field model for solutions homogeneous in space (so the PDE becomes an ODE). Prove that, if $\Omega$ is “small”, nodes will consist of functions constant in space.

The Chafee-Infante RD PDE.
References: [17, 32].

The Field-Noyes RD PDE.
These is a system of PDEs used as model for the Belousov-Zhabotinsky reactions in chemical kinetics.

Full PDE expression: <cit.>.

Recent review: <cit.>

What Everyone Should Know About the Belousov-Zhabotinsky Reaction <cit.>

Chaos and beauty in a beaker: The early history of the Belousov-Zhabotinsky reaction <cit.>

Bifurcation diagrams of the Poincare sections of some ODE models: <cit.>

Györgyi-Field model of BZ: <cit.>

Bifurcations in the Degn-Harrison model for solutions homogeneous in space (so the PDE becomes an ODE).

The Gray-Scott RD PDE.
Reaction and diffusion of chemical species can produce a variety of patterns, reminiscent of those often seen in nature. The Gray Scott equations model such a reaction. For more information on this chemical system see the articles “Complex Patterns in a Simple System,” by John E. Pearson and “Pattern Formation by Interacting Chemical Fronts,” by K.J. Lee, W.D. McCormick, Qi Ouyang, and H.L. Swinney. These articles appeared in Science, Volume 261, 9 July 1993.

Bifurcation and pattern formation in diffusive
Klausmeier-Gray-Scott model of water-plant interaction <cit.>

Global attractor of the Gray-Scott equations <cit.>

The Degn-Harrison RD PDE.
This paper presents several models of Reaction-Diffusion phenomena in chemistry, in particular the Degn-Harrison one. It includes a very nice bifurcation diagram <cit.>

See also this monograph <cit.>

§ APPENDIX 1

Now we use the lemma below:

The two inequalities below hold:

* Let $\Omega\subset\bR^n$ be a bounded open set. Then there exist a constant $C>0$ such that

\|v\|_{L^2(\Omega)}\leq C\|\nabla v\|_{L^2(\Omega)}

for every $v\in H^1_0(\Omega)$.

* Denote by $\bar v$ the average of a function $v\in L^2(\mathbb T^n)$, where $\mathbb T^n=[0,2\pi]^n$ with periodic conditions on the boundary.

\|v-\bar v\|_{L^2(\mathbb T^n)}\leq \|\nabla v\|_{L^2(\mathbb T^n)}

for every $v\in H^1(\mathbb T^n)$.

1. Let $f$ be a function with compact support on $\Omega$.

\int_\Omega f^2(x) dx = \int_\Omega \left[\frac{\partial}{\partial{xj}}x^j\right] f^2(x) dx =

= - 2\int_\Omega x^j f(x) f_{x^j}(x) dx \leq C\int_\Omega |f(x)|\cdot|\nabla f(x)|dx.

\|f\|^2_{L^2}\leq C\|f\|_{L^2}\|\nabla f\|_{L^2}.

Since functions with compact support are dense in $H^1_0(\Omega)$, the claim follows.

Let $(x^1,\dots,x^n)\in\bR^n (\bmod 2\pi$) be angle coordinates on $\mathbb T^n$.     Set

v(x) = \bar v + \sum_{k\neq0}a_k e^{ik\cdot x},\;k\in\mathbb Z^n.

\nabla v(x) = \sum_{k\neq0}k a_k e^{ik\cdot x}

and, letting $\|k\|=\sqrt{k_1^2+\dots+k_n^2}$,

\|v-\bar v\|^2_{L^2(\mathbb T^n)}=\sum_{k\neq0}|a_k|^2
\leq\sum_{k\neq0}\|k\|^2|a_k|^2 = \|\nabla v\|^2_{L^2(\mathbb T^n)}.

§ APPENDIX 2

We say $y$ is downstream from $x$ (and write $x\leadsto y$) if
for each $\eps>0$, there is an $\eps$-chain from $x$ to $y$.

§ APPENDIX 3

Diffusion reaction processes like BZR = Belousov–Zhabotinsky Reaction – Wikipedia.
It has a nice chaotic flow picture on a torus. The following URLs may not be encoded correctly in TeX.

* <http://www.scholarpedia.org/article/Oregonator>

* <https://itp.uni-frankfurt.de/ gros/StudentProjects/Projects_2020/projekt_schulz_kaefer/>

* <https://faculty.cc.gatech.edu/ turk/bio_sim/hw3.html.old01>

* <https://groups.csail.mit.edu/mac/projects/amorphous/GrayScott/>

[1]
E. Akin, The general topology of dynamical systems, vol. 1, American
Mathematical Soc., 1993.

[2]
E. Akin and J. Auslander, Generalized recurrence, compactifications, and
the Lyapunov topology, Studia Mathematica 1 (2010), no. 201,

[3]
A. Anusic and R. De Leo, Graph and backward asymptotics of the tent map,
arXiv preprint arXiv:2302.04342 (2023).

[4]
N. Aoki and K. Hiraide, Topological theory of dynamical systems: recent
advances,  (1994).

[5]
J. Auslander, Generalized recurrence in dynamical systems, Contr. Diff.
Eqs. 3 (1963), 65–74.

[6]
R. Bowen, $\omega$-limit sets for axiom A diffeomorphisms, Journal of
differential equations 18 (1975), no. 2, 333–339.

[7]
C. Conley, The gradient structure of a flow: I, IBM Research, RC 3932
(#17806) (1972), reprinted in Ergodic Theory Dynam. Systems, vol 8 (1988),
Charles Conley Memorial Issue.

[8]
, On a generalization of the morse index, Ordinary differential
equations, Elsevier, 1972, pp. 27–33.

[9]
, Isolated invariant sets and the morse index, no. 38, American
Mathematical Soc., 1978.

[10]
T. Das, K. Lee, D. Richeson, and J. Wiseman, Spectral decomposition for
topologically Anosov homeomorphisms on noncompact and non-metrizable
spaces, Topology and its Applications 160 (2013), no. 1, 149–158.

[11]
R. De Leo, Solvability of the cohomological equation for regular vector
fields on the plane, Annals of Global Analysis and Geometry 39
(2011), no. 3, 231–248.

[12]
, Backward asymptotics in S-unimodal maps, International
Journal of Bifurcations and Chaos 32 (2022), no. 6.

[13]
R. De Leo and J.A. Yorke, The graph of the logistic map is a tower,
Discrete and Continuous Dynamical Systems 41 (2021), no. 11.

[14]
, Infinite towers in the graph of a dynamical system, Nonlinear
Dynamics 105 (2021).

[15]
W. de Melo and S. van Strien, One-dimensional dynamics, vol. 25,
Springer Science & Business Media, 1993.

[16]
R. Easton, Chain transitivity and the domain of influence of an invariant
set, The Structure of Attractors in Dynamical Systems: Proceedings, North
Dakota State University, June 20–24, 1977 (1977), 95–102.

[17]
B. Fiedler and C. Rocha, Heteroclinic orbits of semilinear parabolic
equations, Journal of differential equations 125 (1996), no. 1,

[18]
, Orbit equivalence of global attractors of semilinear parabolic
differential equations, Transactions of the American Mathematical Society
352 (2000), no. 1, 257–284.

[19]
, Design of sturm global attractors 1: Meanders with three noses,
and reversibility, arXiv preprint arXiv:2302.12531 (2023).

[20]
J. Guckenheimer, Sensitive dependence to initial conditions for one
dimensional maps, Communications in Mathematical Physics 70 (1979),
no. 2, 133–160.

[21]
M. Hurley, Chain recurrence and attraction in non-compact spaces,
Ergodic Theory and Dynamical Systems 11 (1991), no. 4, 709–729.

[22]
, Chain recurrence, semiflows, and gradients, Journal of Dynamics
and Differential Equations 7 (1995), 437–456.

[23]
V.G. Ivancevic and T.T. Ivancevic, Ricci flow and nonlinear
reaction–diffusion systems in biology, chemistry, and physics, Nonlinear
Dynamics 65 (2011), 35–54.

[24]
L. Jonker and D. Rand, Bifurcations in one dimension, Inventiones
mathematicae 62 (1980), no. 3, 347–365.

[25]
Keonhee L., Ngoc-Thach N., and Yinong Y., Topological stability and
spectral decomposition for homeomorphisms on noncompact spaces, Discrete and
Continuous Dynamical Systems 38 (2018), no. 5, 2487–2503.

[26]
D.A. Mizin, On the global structure of a dynamical system, Differential
Equations and Control Processes (Differencialnie Uravnenia i Protsesy
Upravlenia) 3 (2002), 83–107, <https://diffjournal.spbu.ru/>.

[27]
R. Moeckel, Some comments on'The gradient structure of a flow: I',
1988, pp. 9–9.

[28]
S.E. Newhouse, Diffeomorphisms with infinitely many sinks, Topology
13 (1974), no. 1, 9–18.

[29]
D.E. Norton, The fundamental theorem of dynamical systems,
Commentationes Mathematicae Universitatis Carolinae 36 (1995),
no. 3, 585–597.

[30]
J. Oh, Spectral decomposition for homeomorphisms on non-metrizable
totally disconnected spaces, Journal of the Korean Mathematical Society
59 (2022), no. 5, 987–996.

[31]
G. Osipenko, Dynamical systems, graphs, and algorithms, Springer, 2006.

[32]
J.C. Robinson, Infinite-Dimensional Dynamical Systems: An
introduction to dissipative parabolic PDEs and the theory of global
attractors.,  (2001).

[33]
S. Smale, On gradient dynamical systems, Annals of Mathematics (1961),

[34]
, Differentiable dynamical systems, Bulletin of the American
mathematical Society 73 (1967), no. 6, 747–817.

[35]
S. Smale and R.F. Williams, The qualitative analysis of a difference
equation of population growth, Journal of Mathematical Biology 3
(1976), no. 1, 1–4.

[36]
T. Ura, Sur les courbes définies par les équations
différentielles dans l’espace à $ m $ dimensions, Annales
scientifiques de l'École normale supérieure, vol. 70, 1953,
pp. 287–360.

[37]
J. Wiseman, The generalized recurrent set and strong chain recurrence,
Ergodic Theory and Dynamical Systems 38 (2018), no. 2, 788–800.

§ NOTES FROM JOE AUSLANDER MAY 10 2023

Consider a real action $(t,x) \to tx$ on a locally compact metric space $X$.
If $x \in X$, the prolongation of $x$,

$$D_1(x)=\{y : \text{ there are }x_n \to x, t_n \geq 0 \text{ and } t_nx_n \to y\}.$$

If we require $t_n \to \infty$, then we have the prolongational limit set $\Lambda_1(x)$.
Note that the orbit closure of $x$ is a subset of $D_1(x)$, and the $\omega$ limit set of $x$ is a subset of $\Lambda_1(x)$.

Also x is non-wandering iff $x \in \Lambda_1^*(x)$

Now here is what is interesting. Unlike the orbit closure and omega limit set, $D_1(x)$ and $\Lambda_1(x)$ are not transitive.
(Simple examples have $y \in D_1(x)$ and $z \in D_1(y)$ but $z \notin D_1(x)$ and also for $\Lambda_1(x)$).
So we can “transitize" $D_1$  and $\Lambda_1$ and obtain transitive relations which however are not closed. Close them but (in general) not transitive.
Keep going alternating transitizing and closing and we get a family of prolongations $D_\alpha(x)$ and prolongational limit sets $\Lambda_\alpha(x)$
This gives rise to a family of recurrence relations $x \in \Lambda_\alpha(x)$ (generalizing non-wandering).

This process stabilizes no later than the first uncountable ordinal.

Another approach is via “Lyapunov" functions, continuous real-valued functions non-increasing along orbits
$f(tx) \leq f(x)$ for $x \in X, t>0$. If $x$ is non-wandering then it's an easy exercise that such an $f$ is constant on its orbit.
Same (by induction) for $x \in \Lambda_\alpha(x)$.

In fact, one can show (not quite trivial) that all Lyaps $f$ are constant on an orbit if and only if $x \in \Lambda_\alpha(x)$, all $\alpha$
(in which case we say $x$ is a “generalized recurrent point").

An interesting class of flows is those for which there are no generalized recurrent points. An instructive example is the “improper saddle point"
$dx/dt=\sin y$, $dy/dt=\cos^2(y)$ orbits are $x=c+\sec y$ and lines $y= (2k+1)\pi/2$.

An equivalent characterization: there is a Lyapunov function strictly decreasing on orbits $f(tx)<f(x)$, $x \in X, t>0$.

Now (and this may be related to what you were telling me about “graphs") this induces a closed partial order on the orbit space, and the topology on the orbit space is $T_1$ (points are closed). I would like to be able to “classify" such flows.

Over the last century, this concept has been already extended in several directions, each of which corresponding to a relation that extends $\Fto$.
The following is a list of the most relevant for us:

* Non-wandering and Prolongations. We write that $x\NWto y$ if there exist sequences $x_i\to x$ and $t_i\to\infty$  as $i\to\infty$ such that $F^{t_i}(x_i)\to y$ as $i\to\infty$. This may be restated as follows. For each pair of neighborhoods $N_x, N_y$ of $x$ and $y$, there is a sequence of times $t_i\to\infty$ such that $F^{t_i}(N_x)$ intersects $N_y$.
We say $x$ is non-wandering if $x\NWto x$.

The first prolongational limit set $\Lambda_1(x)$ is $\{y : x \NWto y\}$.

* Prolongations.
Auslander obtains additional points further downstream by using transfinite induction combined with taking closures of the points obtained.
Write that $x\Pto y$ if $y$ is in the first uncountable ordinal's prolongational limit set of $x$. This is too brief and needs a reference.

* Lyapunov functions. We say that $V$ is a Lyapunov function for $F$ if $V$ is continuous on $X$ and $V(F^t(x))$ is monotonically decreasing, as a function of $t$,  for each $x$.
Let $\Lambda_F$ be the set of all Lyapunov functions for $X$.

We write $x\Lto y$ if $V(x)\geq V(y)$ for every $V\in\Lambda_F$.

* $\varepsilon$-chains. We say a finite sequence $(x_i)_{i=0}^n$ is a chain (with respect to the time-1 map $F^1$) from $x$ to $y$ if $x_0=x, x_n=y$, and we say the chain is a $\varepsilon$-chain

{\rm dist}\Big(F^1(x_i),x_{i+1}\Big)<\varepsilon \text{ for }  i=0,\dots,n-1.

We write $x\CRto y$ if, for every $\varepsilon>0$, there is an $\varepsilon$-chain
from $x$ to $y$.

* $\varepsilon$-sum chains (or strong $\varepsilon$ chains).
We say the above $(x_i)_{i=0}^n$ chain is an $\varepsilon$-sum chain if

\sum_{i=0}^{n-1} {\rm dist}\Big(F^1(x_i),x_{i+1}\Big)<\varepsilon.$$

Write that $x\SUMto y$ if, for every $\varepsilon>0$, there is an $\varepsilon$-sum-chain
from $x$ to $y$.

Throughout the article, we write

$x\Sto y$ if $y$ is downstream from $x$.

For sets $S_1,S_2\subset X$, we write

S_1S_2 if and only if s_1s_2 for each s_1∈S_1, s_2∈S_2.

In our axiomatic structure below, $\leadsto$ is an undefined primitive notion upon which, together with the map $F$, the rest is built.

For a primitive to be mathematically useful, we need to describe its properties, and those are the axioms below.
To describe these axioms, we describe sets that are defined in terms of $\leadsto$.

se nodes, though, can have non-empty intersection.

Referring to the example above, the set $NW_\ell$ has exactly three nodes:
the repelling fixed point $0$, the repelling Cantor set $C$ and the attractor $A$.
As we mentioned, though, $C$ and $A$ have non-empty intersection.

The relation $\overline{\cO_F}$, Non-Wandering points and the first prolongation.
The reason why $R_{\cO_F}$ does not contain, in general, all recurrent points is that $\cO_F$ not closed.
By closing $\cO_F$, we get a new relation  extending $\Fto$ that we denote by $\NWto$ and is characterized as follows:
$x\NWto y$ iff there is a sequence $\{(x_n,y_n)\}\subset\cO_F$ such that $(x_n,y_n)\to(x,y)$ in the product topology.

Hence, with respect to $\NWto$, every point of $\Om_F(x)$ is downstream from any point of $\cO_F(x)$.

Unfortunately, though, we lost transitivity: if $y\in\Om_F(x)$ and $z\in\Om_F(y)$, in general $z\not\in\Om_F(x)$.

Consider the logistic map $\ell$ at the right endpoint of the period-3 window.
This map has three closed forward invariant indecomposable sets:

the repelling fixed point $0$, a repelling Cantor set $C$ and an attracting period-3 cycle of intervals $A$.
The Cantor set and the attractor intersect each other; in particular, their intersection contains a period-3 repelling periodic orbit $\gamma$.
Let $x\in C\setminus A$, $y\in\gamma$ and $z\in A\setminus C$.
Then $x\NWto y$ and $y\NWto z$ but, since $C$ in invariant and $z$ is in the interior of $A$, $(x,z)\not\in\overline{\cO_\ell}$.

When $X$ is a metric space, we can describe $\NWto$ in terms of chains as follows.

In a metric space, $x\NWto y$ if and only if, for every $\eps>0$, there is a $\eps$-A$\omega$chain from $x$ to $y$.

Even though $\overline{\cO_F}$ is not transitive, we can still define a “recurrent set” for it:

The set $NW_F$ of Non-Wandering points of a semi-flow $F$ is the set of all points $x$ such that either $x$ is fixed or, for every $\eps>0$, there is an $\eps$-A$\omega$chain from $x$ to itself.

Note that, because of the lack of transitivity, in general there is no equivalence relation defined on $NW$.
One can still define nodes for $NW$ as maximal subsets $N\subset NW$ such that, for every $x,y\in N$, $x\NWto y$ and $y\NWto x$.
These nodes, though, can have non-empty intersection.

Referring to the example above, the set $NW_\ell$ has exactly three nodes:
the repelling fixed point $0$, the repelling Cantor set $C$ and the attractor $A$.
As we mentioned, though, $C$ and $A$ have non-empty intersection.

Continuous dynamical systems include discrete-time maps and the continuous-time processes described by ordinary and partial differential equations.

What is the graph of a dynamical system? To give an overview of a particular system, one might initially  start by describing the attractors. The logistic map $rx(1-x)$ has exactly one bounded attractor for $1 < r< 4$. That attractor can be a fixed point, a periodic orbit, a chaotic set, or a quasi-periodic set depending on $r$.

For special parameter values $r$ of the logistic map, there can be infinitely many disjoint compact sets, only one of which is the attractor.
That situation occurs for example in the $r$ value made famous by Mitchell Feigenbaum. In his case, there are infinitely many unstable periodic orbits (with periods $2^k$ for $k=1,2,3,\ldots$), and the collection of orbits limits on a quasiperiodic  attractor.
The term “attractor” here is used in a broad sense as defined by Jack Milnor.

A graph consists of nodes and directed edges which may connect two nodes.
Each node of the graph is a compact invariant set
that has a trajectory that is “dense” in the compact set. Furthermore, the compact set cannot be a subset of a larger such set.
Different approaches to graph.
If there are two nodes, $N_1$ and $N_2$, and there is an unstable manifold of $N_1$ that runs to $N_2$ then there will be an edge from $N_1$ to $N_2$. There can be additional edges, which we describe later.

Move this elsewhere: Each quasi-periodic set Q of the logistic map has a positively invariant neighborhood N in which almost all points in N have trajectories converging to Q in forward time, but also N contains infinitely many periodic orbits that are not in Q. Clearly those periodic orbits aren't attracted to Q.

In defining the graph of a dynamical system, there are a number of choices.
The different approaches sometimes yield the same graph for a dynamical system and sometimes do not.
One approach is to use non-wandering sets to define nodes. That is not our approach.

We introduce a new concept of (summable) $\eps$-chain, which is a bit different from the (max) $\eps$-chain of
Charles Conley. This chain allows us to extend the idea of graphs to ordinary and partial differential equations.

It  emphasizes “chain recurrence”. The directed edges tell how the nodes are related.

To understand how complicated graphs can be, we have mentioned above the example of the logistic map that has infinitely many nodes for certain $r$.

How complicated can the graphs be?
Many dynamical systems will have a finite number of nodes.
In contrast to the one-attractor logistic map,
Sheldon Newhouse, followed by Clark Robinson,  described maps in the plane that have infinitely many coexisting attractors – for certain carefully chosen parameter values. Each attractor must be a node. The  graphs of such Newhouse systems have not been described.

We will show examples in which the set of nodes is a Cantor set.

We will establish some properties of these graphs and describe some graphs in special cases.

Our  examples will vary from the graph of the logistic map to ordinary differential equations to partial differential equations,  and we will describe some general properties of such graphs.

Dynamical systems are associated with a space $X$ on which the action occurs. For the logistic map, $X$ is an interval.
Alternatively, for a partial differential equation, $X$ could be the set of $C^2$ functions on a Euclidean space $J$ on which a diffusion equation defined.
Maybe our system is something like this: Let $J$ be a compact manifold, with or without boundary. A typical example  $u=u(t,x)$

u_t = \sum_i a_{i}\frac{\partial^2}{\partial x^2_i} u + f(x,u,\nabla u),
%\frac{\partial u}{\partial t}= a(x) \nabla{\red ^2} u(x) + b(x) \text{ where }x\in J.

where $a_i$ is diffusion speed coefficient for $x_i$.

Or for the Lorenz system with $u=(x,y,z)$

\begin{cases}
\dot x &=a\Delta x -\sigma x +\sigma y  \\
\dot y &=a\Delta y-xz+\rho x -y\\
\dot z &=a\Delta z + xy - \beta z  % ending with \\ produces an extra equation number, 4 numbers in total.
% \end{split}
\end{cases}

The one in Fig 1 is the only version of the BZ PDE I could find so far.

Let $Q_\beta$ be the set of states in $X$ where the spatial $C^2$ norm is less than some positive constant $\le\beta$;
, the functions and their first two spatial derivatives all have norm $\le\beta$. The set $Q_\beta$ is compact in the $C^0$ or uniform convergence topology by the Ascoli-Arzela Theorem. The closed unit ball in $C^2$ is compact in the $C^0$ metric if $J$ is compact.
For $\le\beta$ sufficiently large, it seems likely that $Q_\beta$ is a compact trapping region that is globally attracting in $C^2$.
For many reaction-diffusion systems with a compact space,  $Q_\beta$, is a trapping region that is globally attracting in $C^2$ for sufficiently large $\beta$.

We are now ready to classify non-wandering graphs of T-unimodal maps.

Hence, namely the nodes of $\NW_{\ell_\mu}$

The results of Guckenheimer [20] and van Strien <cit.> imply that,

when $\mu\in(2,4)$ and $\mu$ is not an end-point of a periodic window, all non-wandering nodes of $\ell_\mu$ are disjoint.

In [13] we studied the graph $\Gamma_\mu$ of the logistic map defined in the following way: the nodes of $\ell_\mu$ are the chain-recurrent nodes (see Sec.???) and there is an edge from node $N$ to node $M$ if and only if there is a bi-infinite trajectory $\{x_n\}_{n\in\bZ}$ such that $\alpha(x_n)\subset N$ and $\omega(x_n)\subset M$.
We ultimately proved that $\Gamma_\mu$ is a tower

namely the nodes of $\NW_{\ell_\mu}$ can be sorted in a linear order $N_0,N_1,\dots,N_p$ (where $p$ can be infinite) so that there is an edge from $N_i$ to $N_j$ if and only if $j>i$.
In this ordering, node $N_0$ is always the repelling fixed point 0 and $N_p$ is always the attractor.

As we showed in [13], non-wandering nodes of the logistic map coincide with the chain-recurrent nodes when are disjoint from all other non-wandering nodes.
Hence, as the following proposition shows, what we have found in [13] is ultimately the structure of the non-wandering graph of the logistic map.

Let $\mu\in(2,4)$ be a parameter that is not an end-point of a periodic window.
Then $\Gamma_{\NW_{\ell_\mu}}=\Gamma_\mu$.

When $\mu$ is an end-point of a periodic window, then $p<\infty$ and nodes $N_{p-1}$ and $N_p$ have a non-empty intersection.
In this case, $\Gamma_{\NW_{\ell_\mu}}$ is equal to the tower above with the addition of an extra edge from $N_p$ to $N_{p-1}$, namely there is a loop between the last two nodes.
In Fig.??? we show the graph of the logistic map in Example <ref>.


# GOVERN: Gradient Orientation Vote Ensemble for Multi-Teacher Reinforced
Distillation

Wenjie Zhou, Zhenxin Ding, Xiaodong Zhang
Haibo Shi, Junfeng Wang, Dawei Yin
Baidu Inc., Beijing, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Corresponding author.

###### Abstract

Pre-trained language models have become an integral component of question-
answering systems, achieving remarkable performance. For practical deployment,
it is critical to carry out knowledge distillation to preserve high
performance under computational constraints. In this paper, we address a key
question: given the importance of unsupervised distillation for student
performance, how does one effectively ensemble knowledge from multiple
teachers at this stage without the guidance of ground-truth labels? We propose
a novel algorithm, GOVERN, to tackle this issue. GOVERN has demonstrated
significant improvements in both offline and online experiments. The proposed
algorithm has been successfully deployed in a real-world commercial question-
answering system.

##  1 Introduction

Traditional search engine aims at deliver relevant web pages to satisfy users’
question, while sometimes the single paragraph that answer the question might
buried deep in a web page, it asks for a web-based Open domain Question
Answering (OpenQA) system to find that needle-in-a-haystack information (e.g.
Qu et al., 2021; Zhang et al., 2023).

BERT-liked pre-trained language models have achieved state-of-the-art
performance in OpenQA (e.g. Zhang et al., 2021). However, due to computational
costs, the direct application of these models in real-time search engines like
Google is currently unfeasible. For instance, the top-performing models on the
Natural Question dataset, R2-D2 (Fajcik et al., 2021) and UnitedQA (Cheng et
al., 2021) come with 1.29 billion and 2.09 billion model parameters,
respectively. Further complicating matters is the fact that ensemble methods,
which can enhance performance, entail even greater computational overheads.

The distillation of knowledge from multiple teachers has emerged as a powerful
technique for improving the performance and generalization of deep neural
networks while reducing the computational cost. This two-stage training
paradigm, which training large model with limited labeled data as teacher and
then using it to generate soft label on large amount unlabeled data for the
purpose of student training, was first proposed by Hinton et al. (2015). Since
the knowledge from single teacher may be biased and inaccurate, ensemble
distillation from multiple teachers was considered by previous works to
achieve more promising performance (e.g. You et al., 2017; Fukuda et al.,
2017a).

Several dynamic distillation methods were proposed to solve the problem that
different teacher is good at different sample and low-quality teachers may
mislead the student. e.g. Yuan et al. (2021) proposed a novel RL-based
approach to dynamically assigns weights among teachers, Cai et al. (2022)
ensembles multi-teacher logits supervised by human-annotated labels in an
iterative way. But these dynamic teacher selection methods need supervision
signal as guidance, that means they can not apply to unsupervised distillation
which is the most important stage in distillation (Su et al., 2021).

In this paper, we propose an algorithm called Gradient Orientation Vote
Ensemble Reinforced distillatioN (GOVERN) to do sample-wise dynamic teacher
selection without the need of label guidance. In the stage of unsupervised
distillation, we take the gradient orientation provided by teachers as vote
and follow the majority rule to do sample-wise dynamic teacher selection.
While in supervised distillation stage, we use GOVERN to improve confidence
aware ensemble method proposed by Zhang et al. (2022) with the help of human
label.

Our main contributions are summarized as follows:

  * •

We propose GOVERN to do sample-wise dynamic teacher selection without the need
of label guidance. We also give a mathematical proof that GOVERN can perform
better than mean ensemble. To the best of our knowledge, GOVERN is the first
method which can find sample-wise high-quality teachers without label
guidance.

  * •

We propose a distillation framework for industrial application which combines
GOVERN into both of the unsupervised and supervised distillation stage.

  * •

We conduct extensive experiments to demonstrate the effectiveness of GOVERN.
Results show that GOVERN is benefit in both distillation stage and can boost a
real-world question answering system’s performance.

##  2 Answer Selection Task

In a web-based Open domain Question Answering (OpenQA) system, the primary
objective is to select the relevant paragraphs $A_{q}={a_{i}}_{i=1}^{N}\subset
P_{q}$ which can solve the custom’s question $q\in Q$, where $P_{q}$ is a
collection of paragraphs obtained in web pages retrieved by search engine. A
classic framework of this system is made up of two-stage modules including
retriever and ranker, where both modules can be distilled down to a task of
classifying the relevance between a question and an answer. Our work focus on
improving the performance of classification model with the limit of model
size.

The classification model assesses the relevance of a paragraph, denoted as
$p$, to a specific question, denoted as $q$, by calculating the relevance
score, $f(q,p;\theta)$. This scoring function, $f$, which is parameterized by
$\theta$, symbolizes the degree of relevance between the question $q$ and the
paragraph $p$. In practical application, a score threshold is established for
the purpose of classification.

During training, the classification model is optimized by minimizing the loss
over training data:

$\displaystyle\mathop{min}\limits_{\theta}\mathop{\Sigma}\limits_{q\in
Q}\mathop{\Sigma}\limits_{p\in P_{q}}l(y_{p}^{q},f(q,p;\theta))$ (1)

where $l$ is the loss function such as cross-entropy loss, margin loss or MSE
loss, and $y_{p}^{q}$ is the relevance label of q-p pair.

##  3 Methodology

We use multiple teachers ensemble distillation as the method to improving the
performance of online model with the constriction of computational cost.
Within a frequently employed Knowledge Distillation (KD) framework, a large
teacher model, denoted as T, is meticulously pretrained or finetuned well
ahead of time. The knowledge contained within the teacher model is
subsequently transferred to a smaller student model, denoted as S, by
minimizing the disparity between the two. This process can be mathematically
formulated:

$\displaystyle\mathop{min}\limits_{\theta}\mathop{\Sigma}\limits_{x}l(f^{S}(x;\theta),f^{T}(x;\Theta))$
(2)

where x embodies the input sample, while $f^{S}(\cdot)$ and $f^{T}(\cdot)$
denote the scoring function of the teacher and student models respectively.
Additionally, $L(\cdot)$ serves as a loss function that calculates the
variation between the behaviors of the two models.

Specifically, we first utilize unsupervised distillation on a vast amount of
task-specific, unlabeled data, followed by supervised distillation on the
labeled data. The procedures of the distillation can be viewed in Figure 1.

Figure 1:  Procedures of Gradient Orientation Vote Ensemble Reinforced
Distillation

###  3.1 Unsupervised Distillation

Unsupervised distillation, performed on a substantial amount of task-specific
and unlabeled data, is vital for enhancing the performance of the student
network. However, due to the absence of supervised signals, the prevalent
unsupervised ensemble distillation method resorts to mean-ensemble to
amalgamate the abilities of multiple models (You et al., 2017). Other studies
have employed a weighted approach whereby individual teacher models are
assigned varying weights to accentuate the contribution of higher performing
models to knowledge transfer (e.g. Fukuda et al., 2017b; Kwon et al., 2020; Du
et al., 2020; Liu et al., 2020). Methods to determine these weighting
coefficients encompass weighting based on experience, calculating the weights
based on logistic regression model, latent factor or multi-objective
optimization in the gradient space.

While these weighting methods do account for the performance differences among
various teacher models, they employ a uniform weighting coefficient for all
samples during the distillation process. This approach neglects the varying
emphasis on each teacher’s abilities and their respective confidence levels
regarding samples with differing distributions.

Here, we propose a novel unsupervised voting method called Gradient
Orientation Vote Ensemble Reinforced distillatioN (GOVERN), which does not
rely on any human-annotated signals and dynamically assigns different teachers
to different samples. In the following, we will introduce the implementation
of this unsupervised distillation method and then mathematically prove its
superiority over the mean-ensemble method.

####  3.1.1 GOVERN

In unsupervised distillation using mean-ensemble, for a sample, the distilled-
model calculates $logit_{0}$, and N teacher-models calculate $logit_{i}$
respectively $(1<=i<=N)$. The distillation loss is:

$\displaystyle Dist(logit_{0},Mean(logit_{1},...,logit_{N}))$ (3)

where $Dist$ is a distance metric function that can be selected from MSE,
cross-entropy, etc.

We take each teacher’s gradient descent orientation into consideration while
doing ensemble. Specifically, when $logit_{i}>logit_{0}$, the gradient of
$Dist(logit_{0},logit_{i})$ calculated is greater than 0, otherwise it is less
than 0, so the gradient descent orientation is noted as:

$\displaystyle Grad_{i}$ $\displaystyle=SIGN(gradient(logit_{0},logit_{i}))$
$\displaystyle=\left\\{\begin{array}[]{rcl}1&&{logit_{i}>logit_{0}}\\\
0&&{logit_{i}=logit_{0}}\\\ -1&&{logit_{i}<logit_{0}}\end{array}\right.$ (7)

The voted result is calculated as the sum of $Grad_{i}$:

$\displaystyle\chi(sample)=\left\\{\begin{array}[]{rcl}1&&{\Sigma_{i=1}^{N}{Grad_{i}}>0}\\\
0&&{\Sigma_{i=1}^{N}{Grad_{i}}=0}\\\
-1&&{\Sigma_{i=1}^{N}{Grad_{i}}<0}\end{array}\right.$ (11)

Each teacher is considerate as a voter in this way, then the loss for
unsupervised distillation is represented as below:

$\displaystyle W_{i}$
$\displaystyle=\left\\{\begin{array}[]{rcl}1&&{\chi*Grad_{i}\geq 0}\\\
0&&{\chi*Grad_{i}<0}\\\ \end{array}\right.$ (14)
$\displaystyle\mathcal{L}_{UD}$
$\displaystyle=MSE(logit_{0},\frac{\sum_{i=1}^{N}W_{i}logit_{i}}{\sum_{i=1}^{N}{W_{i}}})$
(15)

that means, we restrict our approach to guiding the student model’s training
under the current sample solely by utilizing the majority of teacher models
with consistent gradient orientations.

####  3.1.2 Proof

In this section, we mathematically prove that the sample-wise dynamic
weighting ensemble algorithm GOVERN is better than mean-ensemble.

First, let’s consider the positive samples. For a binary classification model
with an accuracy rate of p, the probability of correct classification after
each sampling follows a Bernoulli distribution. Thus, the expected
classification accuracy of a single teacher is p, and the variance is p(1-p).

To simplify computation, we assume the performance of the N teachers is
consistent, i.e., $p=p_{1}=...=p_{N}$, where $p_{i}$ is the accuracy of
$T_{i}$. The mean ensemble of N teachers is formulated as:

$\displaystyle X_{ME}=\frac{\Sigma_{i}X_{i}}{N}$ (16)

given that $X_{i}$ which follows Bernoulli distribution are independent and
identically distribute, we obtain the conclusion that $E(X_{ME})=p$,
$D(X_{ME})=p(1-p)/N$.

Therefore, compared to a single model, the mean-ensemble demonstrates better
robustness.

Next, we consider the case where N teachers form a vote-ensemble classifier
based on the principle of maximum voting. Then the expectation of the
classifier is as follows:

$\displaystyle p_{0}=\sum_{m=\frac{N+1}{2}}^{N}C_{N}^{m}p^{m}(1-p)^{N-m}$ (17)

Utilizing mathematical induction, it is trivial to prove when $p>1/2$,
$p_{0}>p$. This is called Condorcet’s jury theorem and details of proof can be
found in (Sancho, 2022).

In the stage of distillation, with the assumption that teacher’s performance
is better than student, we have $P(logit_{i}>logit_{0})>1/2$ for positive
samples, where $logit_{i}$ is the output of $T_{i}$ and $logit_{0}$ is the
output of student. So GOVERN is better than mean-ensemble.

For the negative samples, we can prove GOVERN is better in the same way.

###  3.2 Supervised Distillation: GOVERN-CA

Inspired by Confidence-Aware Multi-teacher Knowledge Distillation (CA-MKD)
proposed by Zhang et al. (2022), we further develop GOVERN algorithm with the
help of human label. On each training sample, we select the teachers which
share the same gradient descent orientation with the human label. Furthermore,
we assign weights among these selected teachers to reflect their sample-wise
confidence by calculating the cross entropy loss between the prediction of
teachers and human label:

$\displaystyle y(sample)=\left\\{\begin{array}[]{rcl}1,&&{if\quad positive}\\\
-1,&&{if\quad negative}\\\ \end{array}\right.$ (20) $\displaystyle
W_{i}=\left\\{\begin{array}[]{rcl}1&&{y*Grad_{i}>0}\\\ 0&&{y*Grad_{i}\leq
0}\\\ \end{array}\right.$ (23)
$\displaystyle\omega_{i}=\frac{W_{i}}{\Sigma_{j}W_{j}}(1-\frac{exp(L_{CE}^{i})}{\Sigma_{j}{W_{j}}exp(L_{CE}^{j})})$
(24)

where $L^{i}_{CE}$ denotes the cross entropy loss between the prediction of
$i$-th teacher and human label, $Grad_{i}$ is defined in (11). The loss for
supervised distillation is aggregated with calculated weights:

$\displaystyle\mathcal{L}_{SD}$
$\displaystyle=MSE(logit_{0},\Sigma_{i=1}\omega_{i}logit_{i})$ (25)

According to the aforementioned formulas, we only select teacher with the
correct gradient descent orientation. Besides, the teacher whose prediction
closely align with the ground-truth labels is assigned a greater weight
$\omega_{i}$. This weighting is attributed to the model’s substantial
confidence in making accurate judgments, thereby providing correct guidance.

Dataset | #Question | #Question-Paragraph Pair
---|---|---
unlabeled data | 3,126,132 | 100M
train data | 190,211 | 2,472,749
test data | 3,301 | 93,446

Table 1: Dataset Statistic

Model | Architecture | Results
---|---|---
| $n_{params}$ | $n_{layers}$ | $d_{model}$ | $n_{heads}$ | q R@P=90% | qp R@P=90%
Teacher1-125M | 125M | 12 | 768 | 12 | 79.51% | 70.52%
Teacher2-350M | 350M | 24 | 1024 | 16 | 81.79% | 73.92%
Teacher3-1.5B | 1.5B | 48 | 1536 | 24 | 82.55% | 73.09%
Teacher4-10B | 10B | 48 | 4096 | 64 | 83.06% | 73.31%
Ensemble Model
Mean Ensemble | - | - | - | - | 84.16% | 76.71%
Logistic Regression Weighted Ensemble | - | - | - | - | 83.44% | 76.91%
Distilled Model
Mean Ensemble Distillation on unlabeled data | 125M | 12 | 768 | 12 | 82.04% | 74.63%
LR Ensemble Distillation on unlabeled data | 125M | 12 | 768 | 12 | 81.98% | 75.24%
GOVERN on unlabeled data | 125M | 12 | 768 | 12 | 83.65% | 76.02%
\+ CA-MKD on labeled data | 125M | 12 | 768 | 12 | 82.68% | 75.67%
\+ GOVERN-CA on labeled data | 125M | 12 | 768 | 12 | 83.69% | 76.43%

Table 2: Results of offline experiments. Metrics denoted in bold represent the
best results in the unsupervised distillation phase, while underscored and
bolded denote the best results in the supervised distillation phase.

##  4 Experiments and Results

###  4.1 Dataset

The questions and relevant web-pages we use are collected from a commercial
search engine, the objective is to select a paragraph which can answer the
question from the web-pages. We set question-paragraph pairs as samples need
to be classified. Hundred millions of unlabeled pairs are collected for
unsupervised distillation, and we obtained millions of labeled pairs which are
used for teacher’s fine-tune through crowd-sourcing annotators. The statistic
of dataset is summarized in Table 1.

###  4.2 Experiment Details

Teacher Architecture In order to obtain multiple models with different
structure and ability, we use pretrained models with different layer and fine-
tune them on different samplings of the total labeled data. The specific
structural parameters for each teacher model can be found in Table 2. Each
model has been trained using a sample of 90% of the total data for training
purposes.

Student Architecture  Considering the computing resources and time consuming,
we use the 12-layer transformer structure as the model for online deployment.

In the training procedure, we use the Adam optimizer (Kingma and Ba, 2015)
with $\beta_{1}=0.9$ and $\beta_{2}=0.99$. For all teacher models, we set the
learning rate as 2e-5, the batch size as 64, and the warm-up step as 1000. The
maximum length of input text is set as 384 and cross-entropy is used as loss
function. In the distillation stage, we set the warm-up step as 1000, the
learning rate as 2e-5 and the batch size as 64. The maximum length of input
text is set as 384 and MSE is used as loss function. The best checkpoint is
picked according to the performance on dev-set.

###  4.3 Evaluation Metrics

The metrics we used for experimental evaluation are introduced as below.

Precision-Recall is a useful measure of success of prediction when the classes
are very imbalanced. $P=T_{p}/(T_{p}+F_{p}),R=T_{p}/(T_{p}+F_{n})$ ,where
$T_{p}$, $F_{p}$ and $F_{n}$ represent for the number of true positives, false
positives and false negatives, respectively.

Different threshold of a classifier leads to different Precision-Recall,
follow the need of online system, we take recall value where precision equals
to 90% as evaluation metrics.

q R@P=90% This metric only takes the paragraph with highest predicted score
among all candidates under given question into consideration. A question is
noted as $T_{p}$ if the score of selected answer is higher than threshold and
the label is positive, while $F_{p}$ means the score of selected answer is
higher than threshold but the label is negative. If the score of selected
answer is lower than threshold but it does exist a positive answer for this
question, we note it as $F_{n}$. This question granularity metric follows the
behavior of web-based OpenQA system since system only displays the best answer
was found, so it can best imitate model’s performance in online system.

qp R@P=90% This metric takes every qp-pair sample into consideration so it can
reflect model’s general ability to find answers.

We also conduct a comparison called Good or Same or Bad (GSB) evaluation
between two systems by inviting professional annotators to estimate which
system produced a greater answer for each given question (Zhao et al., 2011).
The gain of a new system can be formulated as:

$\displaystyle\Delta_{GSB}$
$\displaystyle=\frac{\\#Good-\\#Bad}{\\#Good+\\#Same+\\#Bad}$ (26)

where #Good (or #Bad) denotes the number of questions that the new (or base)
system provides better answer and #Same denotes the number of questions that
answer are equal in quality.

###  4.4 Main Results

The main results of distillation methods comparison are shown in Table 2, we
also display the results of teachers and ensemble methods. The methods used in
the offline comparison experiments include:

Mean Ensemble We simply average the output of all teachers as the final
predict score.

Logistic Regression Weighted Ensemble We trained a logistic regression model
based on the development set to determine the weighting coefficients, and use
them to obtain a weighted ensemble model.

CA-MKD This an algorithm proposed by Du et al. (2020) which adaptively assigns
sample-wise reliability for each teacher prediction with the help of ground-
truth labels, with those teacher predictions close to one-hot labels assigned
large weights.

###  4.5 Online Experiment

To investigate the effectiveness of our proposed method in the real production
environment, we deploy the proposed model in a commercial search engine, and
conduct online experiments for comparison of MED and GOVERN.

| Random | Tail
---|---|---
$\Delta_{GSB}$ | +4.5% | +7.75%
$G:S:B$ | 27: 364: 9 | 39: 353: 8

Table 3: Results of online experiments.

In contrast to random questions, tail questions are defined as those with a
search frequency of less than 10 times per week. Given that heterogeneous
search questions adhere to long-tail distributions, these tail questions
constitute a significant portion of the questions processed by the search
engine. It is evident that the proposed method consistently enhances the
performance of the online QA system.

###  4.6 Ablation Study

We executed a series of experiments to illustrate the applicability of our
method under various conditions. Due to computational resource constraints, we
employed a 12-layer transformer as the teacher model and a 4-layer transformer
as the student model for ablation study. The training data was divided into
ten folds, with each teacher model trained on nine out of the ten folds,
resulting in ten distinct teacher models. For the distillation process, we
utilized fifty million unlabeled samples. The epoch for training was set to
one.

Number of Teachers The impact of varying the number of teachers is illustrated
in Figure 2. Experimental results indicate that the GOVERN algorithm
consistently improves as the number of teachers increases. In contrast, mean-
ensemble methods reach a performance plateau relatively quickly.

Figure 2:  The effect of the number of teachers.

Effect of Single Teacher We further investigate the impact of varying the
performance of a single teacher, with results presented in Table 4. The
findings suggest that the GOVERN algorithm has the capacity to effectively
select high-performing teachers, while simultaneously disregarding the noise
generated by less effective ones.

| qp prAUC
---|---
GOVERN with 5-teachers | 88.19%
replace one teacher with 10B model | 89.03%
replace one teacher with 4-layer model | 88.11%

Table 4: Effect of Single Teacher.

##  5 Related Work

Following the seminal work of Hinton et al. (2015), several studies have
sought to develop advanced ensemble algorithms for distillation. We categorize
these works into two groups based on their dependency on ground-truth labels.

Unsupervised Ensemble Distillation There are a few works focused on the
ensemble method on unsupervised data Li and Wang, 2019; Sui et al., 2020,
these works simply use the average prediction of multiple teachers as the
distillation signal. Recently, Wu et al. (2022) and Iliopoulos et al. (2022)
made efforts on knowledge distillation with unlabeled examples, but these
studies primarily concentrate on dynamically assigning weight to unlabeled
examples. These approaches do not address the issue of teachers specializing
in varying sample distributions.

Supervised Ensemble Distillation Li et al. (2021) first explored the idea of
dynamic knowledge distillation with the help of ground-truth label. Yuan et
al. (2021) proposed a novel RL-based approach, which dynamically assigns
weights to teacher models at instance level. Cai et al. (2022) proposed
algorithm ensembles multi-teacher logits supervised by human-annotated labels
in an iterative way. Zhang et al. (2022) introduced confidence-aware mechanism
on both predictions and intermediate features for multi-teacher knowledge
distillation.

##  6 Conclusion

In this paper, we present a novel algorithm, GOVERN, which dynamically selects
teachers based on their gradient descent orientation. This algorithm does not
require ground-truth labels, making it suitable for use during unsupervised
distillation stages. Additionally, it can be integrated with existing
supervised ensemble methods. The effectiveness of our method is affirmed
through extensive experimentation.

## Limitations

The proposed GOVERN algorithm does not currently account for the varying
performance levels of different teachers. This could be a shortcoming as it
may be beneficial to assign a higher weight to more competent teachers, even
if they share the same gradient descent orientation as other selected
teachers.

## References

  * Cai et al. (2022) Lianshang Cai, Linhao Zhang, Dehong Ma, Jun Fan, Daiting Shi, Yi Wu, Zhicong Cheng, Simiu Gu, and Dawei Yin. 2022.  PILE: Pairwise iterative logits ensemble for multi-teacher labeled distillation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing: Industry Track_ , pages 587–595, Abu Dhabi, UAE. Association for Computational Linguistics.
  * Cheng et al. (2021) Hao Cheng, Yelong Shen, Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. 2021.  UnitedQA: A hybrid approach for open domain question answering.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3080–3090, Online. Association for Computational Linguistics.
  * Du et al. (2020) Shangchen Du, Shan You, Xiaojie Li, Jianlong Wu, Fei Wang, Chen Qian, and Changshui Zhang. 2020.  Agree to disagree: Adaptive ensemble knowledge distillation in gradient space.  In _Neural Information Processing Systems_.
  * Fajcik et al. (2021) Martin Fajcik, Martin Docekal, Karel Ondrej, and Pavel Smrz. 2021.  R2-D2: A modular baseline for open-domain question answering.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 854–870, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Fukuda et al. (2017a) Takashi Fukuda, Masayuki Suzuki, Gakuto Kurata, Samuel Thomas, Jia Cui, and Bhuvana Ramabhadran. 2017a.  Efficient knowledge distillation from an ensemble of teachers.  In _Interspeech_.
  * Fukuda et al. (2017b) Takashi Fukuda, Masayuki Suzuki, Gakuto Kurata, Samuel Thomas, Jia Cui, and Bhuvana Ramabhadran. 2017b.  Efficient knowledge distillation from an ensemble of teachers.  In _Interspeech 2017, 18th Annual Conference of the International Speech Communication Association, Stockholm, Sweden, August 20-24, 2017_ , pages 3697–3701. ISCA.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the knowledge in a neural network.
  * Iliopoulos et al. (2022) Fotis Iliopoulos, Vasilis Kontonis, Cenk Baykal, Gaurav Menghani, Khoa Trinh, and Erik Vee. 2022.  Weighted distillation with unlabeled examples.  In _NeurIPS_.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Kwon et al. (2020) Kisoo Kwon, Hwidong Na, Hoshik Lee, and Nam Soo Kim. 2020.  Adaptive knowledge distillation based on entropy.  In _2020 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2020, Barcelona, Spain, May 4-8, 2020_ , pages 7409–7413. IEEE.
  * Li and Wang (2019) Daliang Li and Junpu Wang. 2019.  Fedmd: Heterogenous federated learning via model distillation.  _CoRR_ , abs/1910.03581.
  * Li et al. (2021) Lei Li, Yankai Lin, Shuhuai Ren, Peng Li, Jie Zhou, and Xu Sun. 2021.  Dynamic knowledge distillation for pre-trained language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 379–389, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Liu et al. (2020) Yuang Liu, Wei Zhang, and Jun Wang. 2020.  Adaptive multi-teacher multi-level knowledge distillation.  _Neurocomputing_ , 415:106–113.
  * Qu et al. (2021) Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021.  RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5835–5847, Online. Association for Computational Linguistics.
  * Sancho (2022) Álvaro Romaniega Sancho. 2022.  On the probability of the condorcet jury theorem or the miracle of aggregation.  _Math. Soc. Sci._ , 119:41–55.
  * Su et al. (2021) Weiyue Su, Xuyi Chen, Shikun Feng, Jiaxiang Liu, Weixin Liu, Yu Sun, Hao Tian, Hua Wu, and Haifeng Wang. 2021.  Ernie-tiny : A progressive distillation framework for pretrained transformer compression.  _CoRR_ , abs/2106.02241.
  * Sui et al. (2020) Dianbo Sui, Yubo Chen, Jun Zhao, Yantao Jia, Yuantao Xie, and Weijian Sun. 2020\.  FedED: Federated learning via ensemble distillation for medical relation extraction.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2118–2128, Online. Association for Computational Linguistics.
  * Sun et al. (2019) Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. 2019.  Patient knowledge distillation for BERT model compression.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4323–4332, Hong Kong, China. Association for Computational Linguistics.
  * Wang et al. (2021) Wenhui Wang, Hangbo Bao, Shaohan Huang, Li Dong, and Furu Wei. 2021.  MiniLMv2: Multi-head self-attention relation distillation for compressing pretrained transformers.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 2140–2151, Online. Association for Computational Linguistics.
  * Wu et al. (2022) Chuhan Wu, Fangzhao Wu, Tao Qi, and Yongfeng Huang. 2022.  Unified and effective ensemble knowledge distillation.  _CoRR_ , abs/2204.00548.
  * You et al. (2017) Shan You, Chang Xu, Chao Xu, and Dacheng Tao. 2017.  Learning from multiple teacher networks.  _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Yuan et al. (2021) Fei Yuan, Linjun Shou, Jian Pei, Wutao Lin, Ming Gong, Yan Fu, and Daxin Jiang. 2021\.  Reinforced multi-teacher selection for knowledge distillation.  In _Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021_ , pages 14284–14291. AAAI Press.
  * Zhang et al. (2022) Hailin Zhang, Defang Chen, and Can Wang. 2022.  Confidence-aware multi-teacher knowledge distillation.  In _IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2022, Virtual and Singapore, 23-27 May 2022_ , pages 4498–4502. IEEE.
  * Zhang et al. (2021) Hang Zhang, Yeyun Gong, Yelong Shen, Weisheng Li, Jiancheng Lv, Nan Duan, and Weizhu Chen. 2021.  Poolingformer: Long document modeling with pooling attention.  In _International Conference on Machine Learning_ , pages 12437–12446. PMLR.
  * Zhang et al. (2023) Qin Zhang, Shangsi Chen, Dongkuan Xu, Qingqing Cao, Xiaojun Chen, Trevor Cohn, and Meng Fang. 2023.  A survey for efficient open domain question answering.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 14447–14465, Toronto, Canada. Association for Computational Linguistics.
  * Zhao et al. (2011) Shiqi Zhao, Haifeng Wang, Chao Li, Ting Liu, and Yi Guan. 2011.  Automatically generating questions from queries for community-based question answering.  In _Proceedings of 5th International Joint Conference on Natural Language Processing_ , pages 929–937, Chiang Mai, Thailand. Asian Federation of Natural Language Processing.