\section{Introduction}

Studies on microscopic models for vehicle traffic
provided a good point of view on the phase transition
from the free traffic flow to the congested one. Related
self-driven many-particle systems have attracted
considerable interests not only from engineers but
also from physicists~\cite{Chowdhury2000,Helbing2001}.
Among such models, the optimal velocity (OV) model~\cite{Bando1995},
which is a car-following model describing an adaptation to
the optimal velocity that depends on the headway
between two neighboring vehicles, is well-known for
its successful rationalization of ``phantom traffic jams''
in the high-density regime.

Whereas the OV model consists of ordinary differential equations (ODE),
cellular automata (CA) such as the Nagel--Schreckenberg model~\cite{Nagel1992},
the elementary CA of Rule 184 (ECA184)~\cite{Wolfram1986}, the Fukui--Ishibashi
(FI) model~\cite{Fukui1996} and the slow-to-start (s2s)
model~\cite{Takayasu1993} are extensively used in analyses of traffic flow.
A way toward amalgamation of the ODE-type and the CA-type models was opened
by the discovery of the discrete OV (dOV)
model~\cite{Takahashi2009} that provides
an ultradiscretization~\cite{Tokihiro1996} of the OV model.
The resultant ultradiscrete OV (uOV) model includes both the ECA184
and the FI model as its special cases.
We should note here that
another ultradiscretization~\cite{Kanai2009} of the OV model
is developed out of the
ultradiscretization of the mKdV equation~\cite{Takahashi1997},
which also has an application to the traffic flow~\cite{Emmerich1998}.

Inspiration brought by
the ultradiscretization of the OV model in ref.~\cite{Takahashi2009}
leads us to
an ultradiscretizable hybrid of the OV and the s2s models,
which was named the optimal velocity model with
the slow-to-start effect, or shortly, the s2s--OV model~\cite{Oguma2009},
\begin{equation}
  \dfrac{\d x_k(t)}{\d t}
  = v_0\Bigl(1+\dfrac{1}{t_0}\int_0^{t_0}
  {\rm e}^{-(\Delta x_k(t-t^\prime)-x_0)/\delta x}\d t^\prime
  \Bigr)^{-1}
  -v_0\bigl(1+{\rm e}^{x_0/\delta x}\bigr)^{-1},
  \label{eq:s2s--OV}
\end{equation}
where $t_0$ and $x_k(t)$ are the monitoring period and the position of the $k$-th car at the time $t$, respectively.
The interval between the cars $k$ and $k+1$ is
denoted by $\Delta x_k(t)=x_{k+1}(t)-x_k(t)$.
Sensitivity to the interval is controlled by $\delta x>0$ and
$x_0$ means the length of the road occupied by a vehicle.
In the limit $t_0\rightarrow 0$,
the s2s--OV model reduces to
the Newell model~\cite{Newell1961},
which is a car-following model describing an retarded adaptation
to the optimal velocity determined by the headway in the past.
The ultradiscrete limit of the s2s--OV model includes
a traffic-flow model of the CA-type,
\begin{equation}
  x_k^{n+1}=x_k^n+\min\Bigl(\min_{n^\prime=0}^{n_0}\bigl(\widetilde{\Delta}
  x_k^{n-n^\prime}\bigr),v_0\delta t\Bigr),
  \label{eq:s2s--OVCA}
\end{equation}
where the position of the $k$-th car $x_k^n$, $k=1,2,\cdots, K$, and
the headway between the cars $k$ and $k+1$
at the $n$-th discrete time
$\widetilde{\Delta}x_k^{n}:=x_{k+1}^{n}-x_{k}^n-x_0\geq 0$
are integers. We should note that the headway $\widetilde{\Delta}x_k^{n}$
and the interval $\Delta x_k^{n}:=x_{k+1}^{n}-x_{k}^n=\widetilde{\Delta}x_k^{n}+x_0$
between the cars $k$ and $k+1$ are used in different meanings in this paper.
If all the initial headways $\widetilde{\Delta}x_k^{0}$
are non-negative, then car crash is prohibited at any time.
Positive integers $v_0$, $x_0$ and $\delta t$ means
the speed limit, the size of a cell and the discrete time step,
respectively.
When we consider the time-evolution of the vehicles in the following,
the latter two
parameters, $x_0$ and $\delta t$, are fixed at one.
Then eq.~\eref{eq:s2s--OVCA} reduces to
\begin{equation}
  x_k^{n+1}=x_k^n+\min\Bigl(\min_{n^\prime=0}^{n_0}\bigl(
  x_{k+1}^{n-n^\prime}-x_{k}^{n-n^\prime}-1\bigr),v_0\Bigr).
  \label{eq:s2s--OVCA2}
\end{equation}
We call a positive integer $n_0$ the monitoring period since the minimum
of the headway
$\widetilde{\Delta}x_k^{n-n^\prime}:=x_{k+1}^{n-n^\prime}-x_k^{n-n^\prime}-x_0$
of $n_0+1$ discrete times, $n-n^\prime=n-n_0, n-n_0+1,\cdots, n$,
is involved in the time evolution~\eref{eq:s2s--OVCA}. This CA describes
many cars running on a single lane highway in one direction, which is driven
by cautious drivers requiring enough headway to go on at least for
$n_0$ time steps before they accelerate their cars.
Since the above CA~\eref{eq:s2s--OVCA} is an extension of the CA
case of the uOV model~\cite{Takahashi2009} incorporating the
s2s effect in the sense of delay in drivers' response,
we call the CA~\eref{eq:s2s--OVCA} the CA variant of the
OV model with the s2s effect,  or the s2s--OVCA for short.

\begin{figure}[h]
\begin{center}
\includegraphics[width=60mm]{fig1a.eps}
\includegraphics[width=60mm]{fig1b.eps}
\end{center}
\caption{The spatio-temporal pattern (left)
and the fundamental diagram (right) of the s2s--OVCA~\cite{Oguma2009}.
The number of the cells $L$ is fixed at $L=100$
and the periodic boundary condition is imposed.
The number of the cars in the above spatio-temporal pattern is $K=30$.
The maximum velocity $v_0$ and the monitoring
period $n_0$ are $v_0=3$ and $n_0=2$.
The flows $Q$ are computed by averaging over the time
period $800\leq n\leq 1000$, in which the traffic is expected to be in
equilibrium.}
\label{fig:1}
\end{figure}

Figure~\ref{fig:1} gives typical
examples of the spatio-temporal pattern showing jams and the
fundamental diagram of the s2s--OVCA~\cite{Oguma2009}.
The spatio-temporal pattern shows the trajectories of
vehicles. Though irregular patterns are observed at the
initial stage of time evolution, trajectories become regular in the long run,
which consist of
several jam clusters moving backward at the same velocity and
vehicles running at the top speed.
The fundamental diagram, or the flow--density relation, in other words,
gives the relation between the vehicle flow
\[
  Q:=\dfrac{1}{(n_f-n_i+1)L}\sum_{k=1}^K\sum_{n=n_i}^{n_f}
  \dfrac{x_k^{n+1}-x_k^n}{\delta t},
\]
which is equivalent to the total momentum of
vehicles per unit length averaged over the period $n_i\leq n\leq n_f$
when the traffic is expected to be in equilibrium,
and the vehicle density $\rho:=\frac{K}{Lx_0}$ where $L$ is
the total number of the cells, or the length of the circuit,
on which the periodic boundary condition is imposed.
The fundamental diagram has the inverse-$\lambda$ shape with
several phases of traffic, namely, free, jam
as well as metastable slow traffics,
which captures the characteristic
of observed flow--density relations~\cite{Chowdhury2000,Helbing2001}.
A comment here might be in order.
A CA-type model that is different from the s2s--OVCA
showing a fundamental diagram with several branches
was reported.~\cite{Nishinari2004} But all of its branches except for
the free line have negative inclinations. This feature is also different
from that of the fundamental diagram of the s2s--OVCA.
As we can
see in Fig.~\ref{fig:1}, the fundamental diagram consists of straight
branches, whose number, four in this case, is the same as that
of all possible integral velocities, $v=0, 1, 2$ and $3(=v_0)$.
The main result of this paper is to present
a set of exact solutions of the s2s--OVCA, which
explains the piecewise linear fundamental diagram
of the s2s--OVCA.

The outline is as follows.
In \S\ref{sec:1}, the fundamental diagram given in Fig.~\ref{fig:1}
will be examined. An empirical formula for the fundamental diagram
of the s2s--OVCA will be introduced. A set of exact solutions of the
s2s--OVCA that reproduces the empirical formula will be presented
in \S\ref{sec:2} and \S\ref{sec:3}. Concluding remarks are
given in the final section.
Derivation of the s2s--OVCA~\eref{eq:s2s--OVCA} from the s2s--OV
model~\eref{eq:s2s--OV} is briefly summarized in an appendix.

\section{Numerical Observation of the Fundamental Diagram}
\label{sec:1}
By numerical experiments~\cite{Oguma2009}, the
fundamental diagram of the s2s--OVCA was observed to be
piecewise linear and possesses $v_0$ branches irrespective of
the parameter $n_0$. Let us have a close look at the
fundamental diagram in Figs.~\ref{fig:1} and \ref{fig:2} and
examine these features more in detail.

\begin{figure}[h]
\label{fig:2}
\begin{center}
\includegraphics[width=60mm]{fig2.eps}
\end{center}
\caption{(Color online) An empirical formula for the fundamental diagram of the
s2s--OVCA. All the dots on the diagram were numerically
computed~\cite{Oguma2009} for the case
in which the maximum velocity $v_0$ and the monitoring
period $n_0$ are $v_0=3$ and $n_0=2$.
Each solid line corresponds to
the formula in the same color or in the same grayscale.
Each branch is labeled with a number that shows the
integral velocity $v$ corresponding to the branch.
The end points of the branches are determined by the maximum
density for each integral velocity. The branch points of the slow
or the jamming lines, which are encircled with thin small circles,
give the lowest densities for these lines.}
\end{figure}

As shown in Fig.~\ref{fig:2},
each branch corresponds to an integral
velocity that is less than or equal to the maximum velocity
$v_0$.
All the end points of the branches are observed to be
on the line
\begin{equation}
  Q\delta t+\rho x_0=1.
  \label{eq:max_density}
\end{equation}
This is because
the density at the end point is determined by
the maximum density $\rho_{\rm max}(v)$
that allows the velocity of the slowest
car to be $v$. Because of the time evolution of
the s2s--OVCA~\eref{eq:s2s--OVCA}, a car running at a velocity $v$
must have an interval that is larger than or equal to $v\delta t+x_0$.
Imagining a traffic such that all the cars flow
at the same velocity $v$ with the minimum interval $v \delta t+x_0$,
we conclude that
the maximum density $\rho_{\rm max}(v)$ is determined by
\begin{equation}
  \rho_{\rm max}(v)=\dfrac{1}{v\delta t+x_0},
  \label{eq:max_density1}
\end{equation}
since each car occupies $v\delta t+x_0$ cells.
The flow corresponding to the traffic is given by
\begin{equation}
  Q\bigl(\rho_{\rm max}(v)\bigr)=v\rho_{\rm max}(v).
  \label{eq:free_line1}
\end{equation}
Equations~\eref{eq:max_density1} and \eref{eq:free_line1} simultaneously
holds on the end points and they yield
$Q\bigl(\rho_{\rm max}(v)\bigr)\delta t+\rho_{\rm max}(v)x_0=1$. Thus
all the end points must satisfy the relation~\eref{eq:max_density}.

The free line is a branch that agrees with the
straight line whose
inclination equals to the maximum velocity $v_0$,
\begin{equation}
  Q=v_0\rho,
  \label{eq:free_line}
\end{equation}
since all the cars on the free line flow at the maximum speed
$v_0$.
Any other branches branch off from the free line. By observation,
the density of the branching point of the branch corresponding
to a velocity $v$ reads
\begin{equation}
  \rho_{\rm min}(v)=\dfrac{1}{n_0(v_0-v)\delta t+v_0\delta t +x_0}.
  \label{eq:min_density}
\end{equation}
This observation is explained as follows. Suppose
one car, say the car $k$,
runs at the velocity $v$ and all the other $K-1$ cars
run at the maximum velocity $v_0$.
At the moment the $k$-th car
slows down to $v$, the interval between
the cars $k$ and $k+1$ is $v\delta t +x_0$. Since
it takes at least $n_0+1$ time steps for the car $k$ to
speed up to $v_0$, the interval between the cars $k$ and $k+1$
expands up to $H=(n_0+1)(v_0-v)\delta t+v\delta t+x_0
=1/\rho_{\rm min}(v)> v_0\delta t$ by the time the $k$-th
car speeds up to $v_0$. If all the cars can obtain the
interval $H$, slow cars running at the velocity $v$
should vanish in the end. Thus the density at
the branching point of the branch corresponding
to the velocity $v\delta t$
is given by $\rho_{\rm min}(v)=1/H$,
which is nothing but the minimum
density of the branch.

Suppose the slow branches form straight lines. Then these lines
must be the segments connecting the branching point
$\bigl(\rho_{\rm min}(v), v_0\rho_{\rm min}(v)\bigr)$
and the end point
$\bigl(\rho_{\rm max}(v), v\rho_{\rm max}(v)\bigr)$.
The expression for these line segments is obtained
by eqs.~\eref{eq:max_density1},
\eref{eq:free_line1}
and \eref{eq:min_density} as
\begin{equation}
  Q = \dfrac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho
  +\dfrac{1}{(n_0+1)\delta t},
  \label{eq:empirical}
\end{equation}
which agrees fairly well with
the branches for the slow traffics
consisting of the numerically obtained dots in Fig.~\ref{fig:2}.
Coincidence of the $Q$-interception of slow branches
$\frac{1}{(n_0+1)\delta t}$,
which also appears in Fig.~\ref{fig:2},
is also shown in the above empirical formula.

The aim of the following two sections is to explain
the empirical formula for the fundamental diagram~\eref{eq:empirical}
based on exact solutions of the s2s--OVCA.

\section{Solutions with a Single Slow Cluster}
\label{sec:2}

After transient flow goes on evolving irregularly for a while,
the traffic reaches ``equilibrium'' in the long run where
slow-traffic clusters of seemingly invariant sizes move regularly,
as one can see in the spatio-temporal pattern in Fig.~\ref{fig:1}.
Here we allow equilibrium to change sizes of slow or fast clusters
periodically but prohibit it from increasing or
decreasing their sizes monotonically.
We shall investigate such equilibrium flows and their flow--density
relations. Limiting ourselves to simple cases, we begin with
equilibrium flows with, at most, a single slow cluster.

To begin with, we shall see a specific spatio-temporal pattern
starting from the following initial configuration,
\begin{equation}
  0:~\verb*|1 2 3 4       5    |.
  \label{eq:example}
\end{equation}
Note that the number 0 at the leftmost shows the time.
The digits and the blank symbols \verb*| | in the above configuration
mean the indices of the cars and the empty cells, respectively.
We set the monitoring period $n_0$ at 2.
The velocity of the cars 4 and 5 is 3, which is the top velocity $v_0$
of this case. The velocity of the cars 1, 2 and 3, whose headways are 1, is 1.
Then in this case,
the headways of all the cars in the past have nothing to do with
the time evolution starting from the above configuration~\eref{eq:example}.
The periodic boundary condition is assumed so
the length of the circuit is 19 in this case.

Using eq.~\eref{eq:s2s--OVCA2}, which is equivalent to
the s2s--OVCA~\eref{eq:s2s--OVCA} with $x_0=\delta t=1$,
we can confirm that the following spatio-temporal pattern evolves
out of the above initial configuration~\eref{eq:example},
\begin{eqnarray}
  &0:& \verb*|1 2 3 4       5    | \nonumber \\
  &1:& \verb*| 1 2 3   4       5 | \label{eq:example2} \\
  &2:& \verb*|5 1 2 3     4      | \nonumber \\
  &3:& \verb*| 5 1 2 3       4   | \nonumber.
\end{eqnarray}
Moving all the cells of the initial configuration
one cell rightward as well as neglecting the difference of the car indices,
we get the configuration at the time 3. In this sense, the
initial configuration~\eref{eq:example} gives a periodic motion of the vehicles
and hence an equilibrium flow of the s2s--OVCA~\eref{eq:s2s--OVCA}.
Roughly speaking, we shall construct equilibrium flows of the above type
in the following.

The most simple equilibrium flow is the free traffic in which
all the cars always run at the top velocity $v_0$.
In other words, the free traffic is a traffic flow
with no slow cluster. The headway
of a car running at the top velocity must be larger than or equal to
$v_0\delta t$ and so is each headway in the free traffic.
Since all the cars share the same velocity in the free traffic,
all the headways are invariant. Thus the free traffic is in
equilibrium. One concludes that
the flow--density relation for the free traffic is given
by the free line~\eref{eq:free_line} because of its definition
given above.

A snapshot of an equilibrium flow with only a single slow
cluster is given by a configuration of vehicles shown below,
\begin{equation}
  \underbrace{
  |\stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{k}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto}}_{\displaystyle L}
  |\stackrel{1}{\langle v\rangle},
  \label{eq:equilibrium_initial}
\end{equation}
where $m=0,1,\cdots,n_0$ and $l x_0/\delta t=0,1\cdots,v_0-v-1$.
The car $n$, $n=1,2,\cdots, K$, which will move
at a velocity $v$, $v=0,1,\cdots,v_0$, in the next turn,
is denoted by $\stackrel{n}{\langle v\rangle}$.
Thus the cars 1 to $k$ form a single
slow cluster in the above configuration and the cars
$k+1$ to $K$ form a single fast cluster. Thus the integer $k=0,1,
\cdots, K$ gives the number of cars in the slow cluster.
We shall not deal with the case $k=0$ since its corresponding
configuration gives a free traffic without
slow clusters. Thus $k$ is limited to $k=1,2,\cdots,K$ in the following.

An arrow $\stackrel{h}{\rightarrow}$, $h=0,1,2,\cdots$,
is the headway whose number is $h$, or $h$ empty cells
between the neighboring cars.
The symbol $[n]$ that appears on the arrows
means $[n]=v\delta t+n(v_0-v)\delta t$.
Two headways in front of the cars $k$ and $K$,
which are the tops of the slow and the fast clusters respectively,
are denoted by wavy arrows $\leadsto$ in order to stress
that they are going to change by $(v_0-v)\delta t$ at each step.
Dots between a pair of cars
with the same velocity $v$ and headway $[h]$,
$\stackrel{n_1}{\langle v\rangle}\stackrel{[h]}{\rightarrow}\cdots
\stackrel{n_2}{\langle v\rangle}\stackrel{[h]}{\rightarrow}$,
mean that all the cars and the headways in between also have the
same velocity and headway,
$\stackrel{n}{\langle v\rangle}\stackrel{[h]}{\rightarrow}$,
$n_1\leq {}^\forall n \leq n_2$.
The vertical bars mark the initial cell of the car 1.
The car 1 and the vertical bar, which appear again on the rightmost,
show the periodicity of the circuit and they will be omitted
in the following.
Note that the initial configuration~\eref{eq:example}
is given by the snapshot~\eref{eq:equilibrium_initial} with
$v_0=3,\ v=1,\ n_0=2,\ K=5,\ k=3$ and $l=3$,
\[
  0:~\verb*|1 2 3 4       5    |=
  |\stackrel{1}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{2}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{3}{\langle 1\rangle}\stackrel{1}{\leadsto}
  \stackrel{4}{\langle 3\rangle}\stackrel{7}{\rightarrow}
  \stackrel{5}{\langle 3\rangle}\stackrel{4}{\leadsto},
\]
where $1=[0]$, $7=[3]$, $4=[3]-3$ and $x_0=\delta t=1$.

The circuit length $L$, which is shown under the brace
in the above configuration, is then given by
\begin{equation}
  L=L_0-(n_0-m)(v_0-v)\delta t-lx_0,
  \label{eq:circuit_length}
\end{equation}
where $L_0:=(K-k)(n_0+1)(v_0-v)\delta t
+K\bigl(x_0+v\delta t\bigr)$.
With use of $\rho_{\rm min}(v)$ given in eq.~\eref{eq:min_density},
the formula for the circuit length~\eref{eq:circuit_length} is
cast into
\begin{equation}
  k(n_0+1)(v_0-v)\delta t=\dfrac{K}{\rho_{\rm min}(v)}-L
  -(n_0-m)(v_0-v)\delta t-l x_0,
  \label{eq:circuit_length2}
\end{equation}
where $1/\rho_{\rm min}(v)$ is an integer.
Since the parameter $k$ gives the number of cars in a slow cluster,
it must be non-negative.
Equation \eref{eq:circuit_length2} gives the
condition for $k$ to be non-negative as
\[
  0\leq\dfrac{K}{\rho_{\rm min}(v)}-L
  -(n_0-m)(v_0-v)\delta t-l x_0.
\]
Thus we obtain the necessary condition for $k$ to be non-negative as
\begin{equation}
  \rho:=\dfrac{K}{L}\geq\rho_{\rm min}(v),
  \label{eq:min_density2}
\end{equation}
since $\frac{(n_0-m)(v_0-v)\delta t+l x_0}{L}\geq 0$.
The lower bound of $\rho$ in the above inequality
coincides with the numerically obtained
minimum density~\eref{eq:min_density} for the branch
corresponding to a velocity $v$.

We should confirm here that there always exist non-negative
integers $k, l$ and $m$ satisfying eq.~\eref{eq:circuit_length}
for arbitrarily given $L, K, n_0, v_0$ and $v$ that meet
the condition~\eref{eq:min_density2}.
The r.h.s.~of eq.~\eref{eq:circuit_length2} must be divided by
$(n_0+1)(v_0-v)\delta t$. Since the third and fourth terms
cover all the residue classes modulo $(n_0+1)(v_0-v)\delta t$,
there always exist some non-negative integers $k, l$ and $m$
satisfying the above equation for
arbitrary $L, K, n_0, v_0$ and $v$.

The time evolution out of the
initial configuration \eref{eq:equilibrium_initial} gives an
equilibrium flow with a single slow cluster.
Let us confirm it by
checking each step of the time evolution. We exclude the case
$k=K$ and shall deal with it separately.
Watching the initial state again,
\begin{equation}
  0:
  |\stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{k}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto},
  \label{eq:equilibrium0}
\end{equation}
where $0$ at the leftmost shows the time,
we notice that the
cars 1 to $k$ run at a slow velocity $v$ and the cars $k+1$ to $K$
run at the top velocity $v_0$. Thus only two
headways denoted by wavy arrows for clarity,
namely those of the cars $k$ and $K$ that are
the tops of the slow cluster and the fast cluster respectively,
are going to change by $(v_0-v)\delta t$ at each step.
The configuration of the next time step is then given by
\[
  1:
  |\stackrel{v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{k}{\langle v\rangle}_1
  \stackrel{[1]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m]-lx_0}{\leadsto}.
\]
The subscript 1 of the car $k$ shows
that it is the first turn for the car $k$ to have a headway
which is long enough, $[1]=v_0\delta t$,
to run at the top speed $v_0$.
Similarly, a subscript $n$ of the $k$-th car,
$\stackrel{k}{\langle v\rangle}_n$, $v<v_0$,
whose headway is longer than or equal to $v_0\delta t$,
means that it is the $n$-th turn for the car to have
its headway long enough to run at
the maximum velocity $v_0$.
This symbol is going to appear shortly and to be
used in the same meaning in the following.
The thick arrow at the leftmost
shows the displacement of the car 1 from its initial cell.
Until the car $K$ decelerates at the $m$-th time step,
the cars 1 to $k$ run at a slow velocity $v$ and all the others
run at the top speed $v_0$.
Thus the configuration at the $n$-th
time step, $1\leq n \leq m-1$, is expressed by
\begin{equation}
  n:
  |\stackrel{nv\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{k}{\langle v\rangle}_n
  \stackrel{[n]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m+1-n]-lx_0}{\leadsto}.
  \label{eq:equilibrium1}
\end{equation}
At the $m$-th time step, the headway of the car $K$
shortens to $[1]-lx_0=v_0\delta t-lx_0$ and its velocity
immediately slows down to $v_0-lx_0/\delta t$. Thus
there additionally appears another varying headway
denoted by a wavy arrow in front of the car $K-1$.
The configuration at the $m$-th time step is then given by
\begin{equation}
  m:
  |\stackrel{m v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  {\stackrel{k}{\langle v\rangle}}_{m}\hspace*{-1em}
  \stackrel{[m]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\leadsto}
  \stackrel{K}{\langle v_0-lx_0/\delta t\rangle}
  \stackrel{[1]-lx_0}{\leadsto}.
  \label{eq:equilibrium3}
\end{equation}
At this moment, velocities of the cars $K-1$, $K$ and 1 are
respectively $v_0$, $v_0-lx_0/\delta t$ and $v$, as well as
the headways of the cars $K-1$ and $K$ irregularly shortens by $lx_0$
and $(v_0-v)\delta t-lx_0$.
We classify the car $K$ with the intermediate velocity
$v_0-lx_0/\delta t$ into the fast cluster.
The slow cluster with the velocity $v$ consists of cars with
only a single slow velocity $v$.
Thus the car $K$ has been the top
of the fast cluster by this turn. But in the next turn,
the car $K$ also slows down to $v$
and becomes the bottom of the slow cluster. Thus the
configuration at the $(m+1)$-th time step is
\[
  m+1:
  |\stackrel{(m+1) v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  {\stackrel{k}{\langle v\rangle}}_{m+1}\hspace*{-2em}
  \stackrel{[m+1]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]-lx_0}{\leadsto}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}.
\]
Until the car $k$ accelerates at the $(n_0+1)$-th time step,
$k+1$ cars, namely
the cars 1 to $k$ as well as the car $K$,
run at a slow velocity $v$ and all the others
run at the top speed $v_0$.
Thus the configuration at the $n$-th
time step, $m+1\leq n\leq n_0$, is expressed by
\begin{equation}
  n:
  |\stackrel{n v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  {\stackrel{k}{\langle v\rangle}}_{n}
  \stackrel{[n]}{\leadsto}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0-n+m+2]-lx_0}{\leadsto}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}.
  \label{eq:equilibrium2}
\end{equation}
At the $(n_0+1)$-th time step, the car $k$ accelerates to
the top velocity $v_0$ since
its headway has kept no less than $v_0\delta t$ for $n_0$
time steps by the time.
Thus the car $k$ switches to the fast cluster and the
cars 1 to $k-1$ as well as the car $K$ now form the slow cluster.
The place of the varying headway denoted by a wavy arrow also
moves from the car $k$ to the car $k-1$. Thus the configuration
at the $(n_0+1)$-th time step looks as
\begin{equation}
  n_0+1:
  |\stackrel{(n_0+1) v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  {\stackrel{k}{\langle v_0\rangle}}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}.
  \label{eq:equilibrium6}
\end{equation}
Since the vehicles are running on the circuit of the length $L$,
we may put the car $K$ behind the car 1. Then the
configuration at the $(n_0+1)$-th time step
\begin{equation}
  n_0+1:
  |\stackrel{n_0v\delta t-x_0}{\Rightarrow}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  {\stackrel{k}{\langle v_0\rangle}}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto},
  \label{eq:equilibrium5}
\end{equation}
becomes the same as the initial configuration up to
the rightward displacement of $n_0v\delta t-x_0$ cells.
Thus the motion of vehicles
evolving out of the initial configuration~\eref{eq:equilibrium0} is
periodic with the period $n_0+1$, which shows the corresponding
traffic is in equilibrium.

The configuration for the case $k=K$
\[
  n:|\stackrel{nv\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \cdots
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
\]
gives a constant traffic flow in which all the cars run at the
slow velocity $v$ with the same headway $[0]=v\delta t$.
Thus we confirm that the case $k=K$ also
gives an equilibrium traffic.

We should note that the fast cluster in the case $k=K-1$
temporally vanishes from the $(m+1)$-th time step
to the $n_0$-th time step,
\begin{equation}
\begin{split}
  0:|&
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-1}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto},\\
  n:
  |&\stackrel{nv\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-1}{\langle v\rangle}_n
  \stackrel{[n]}{\leadsto}
  \stackrel{K}{\langle v_0\rangle}
  \stackrel{[m+1-n]-lx_0}{\leadsto},
  \quad 1\leq n\leq m-1, \\
  m:
  |&\stackrel{mv\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-1}{\langle v\rangle}_m
  \stackrel{[m]}{\leadsto}
  \stackrel{K}{\langle v_0-lx_0/\delta t\rangle}
  \stackrel{[1]-lx_0}{\leadsto},\\
  n:
  |&\stackrel{n v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-1}{\langle v\rangle}_n
  \stackrel{[m+1]-lx_0}{\leadsto}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow},
  \quad m+1\leq n\leq n_0.
\end{split}
\label{eq:equilibrium7}
\end{equation}
But it appears appears again at the $(n_0+1)$-th time step
\[
  n_0+1:|\stackrel{(n_0+1)v\delta t}{\Rightarrow}
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{K-3}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\leadsto},
\]
which goes back to the shifted initial configuration,
\[
  n_0+1:|\stackrel{n_0v\delta t-x_0}{\Rightarrow}
  \stackrel{K}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \cdots
  \stackrel{K-3}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  \stackrel{K-2}{\langle v\rangle}
  \stackrel{[0]}{\leadsto}
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[m+1]-lx_0}{\leadsto}.
\]
Thus such vanishment of the fast cluster as we have observed above
does not break equilibrium of the traffic.

Now let us compute the flow of this periodic motion averaged over the period
$n_0+1$.
As we have already seen in the above time evolutions for the
cases $k=1,2,\cdots, K-1$, $k$ and $K-k$ cars respectively run
at the velocities $v$ and $v_0$ in $0\leq n\leq m-1$.
At the $m$-th time step,
$k$ and $K-k-1$ cars run at the velocities $v$ and $v_0$ and remaining
one car move at $v_0-lx_0/\delta t$. In the following period,
$m+1\leq n\leq n_0$, $k+1$ and $K-k-1$ cars move
at the velocities $v$ and $v_0$, respectively.
Thus the average flow $Q$ is
\begin{align*}
  Q & = \dfrac{1}{(n_0+1)L}\Bigl(
  m\bigl(kv+(K-k)v_0\bigr) +\bigl(kv+(K-k-1)v_0+v_0-lx_0/\delta t\bigr)\\
  & \quad + (n_0-m)\bigl((k+1)v+(K-k-1)v_0\bigr)  \Bigr)\\
  & = \dfrac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho
  +\dfrac{1}{(n_0+1)\delta t},
\end{align*}
which is the same as the empirical formula for
the flow--density relation~\eref{eq:empirical}.
For the case $k=K$, the flow $Q$ and the density $\rho$ are
respectively given by
\[
  Q=\rho v, \quad \rho=\dfrac{1}{v\delta t+x_0}.
\]
A straightforward calculation shown below
\begin{align*}
  Q & = \rho\dfrac{(n_0+1)v\delta t}{(n_0+1)\delta t}
    = \dfrac{(n_0v\delta t-x_0)+(v\delta t+x_0)}{(n_0+1)\delta t}\rho \\
    & = \dfrac{n_0v\delta t-x_0}{(n_0+1)\delta t}\rho
    + \dfrac{1}{(n_0+1)\delta t}
\end{align*}
proves that the above two
quantities are related by the flow--density relation~\eref{eq:empirical}.

The above formula is interpreted in a different and more intuitive manner.
The configurations~\eref{eq:equilibrium0} and \eref{eq:equilibrium5}
shows the rightward displacement of
the entire configuretion~\eref{eq:equilibrium0}
by $n_0v\delta t-x_0$ cells in $n_0+1$
time steps. The flow provided by this motion of the entire
configuration gives the first
term $\frac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho$
of the above formula. Here we should remind ourselves of
the leftward displacement of the car $K$ by $L$ cells, namely
whole the circuit length, which is fictitiously introduced
to make the shifted initial configuration~\eref{eq:equilibrium5}
from the real configuration~\eref{eq:equilibrium6} at the $(n_0+1)$-th
discrete time. In order to compensate the underestimation of the
flow caused by this fictitious displacement,
we have to add the flow corresponding to
the rightward displacement of the car $K$ by $L$ cells
in $n_0+1$ time steps
\[
  \dfrac{1}{(n_0+1)L}\cdot\dfrac{L}{\delta t}
  =\dfrac{1}{(n_0+1)\delta t},
\]
which agrees with the second term of the above formula for the
average flow.

\section{Solutions with Multiple Slow Clusters}
\label{sec:3}

As we have observed in the spatio-temporal pattern in Fig.~\ref{fig:1},
several slow or jam clusters that share the same slow velocity coexist
in equilibrium. Here we make solutions as such.

Roughly speaking, we can make an equilibrium solution with
multiple slow clusters by putting several snapshots of the
equilibrium solutions in the previous section together.
Let us see how this idea works via observation of a specific
example. Thanks to the periodic boundary condition, we can
move the leftmost empty cell of
the configuration~\eref{eq:example2} to the rightmost,
\begin{eqnarray*}
  \verb*| 1 2 3   4       5 | & = &
  |\stackrel{1}{\Rightarrow}\verb*|1 2 3   4       5  | \\
  & = &|\stackrel{1}{\Rightarrow}
  \stackrel{1}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{2}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{3}{\langle 1\rangle}_1\stackrel{3}{\leadsto}
  \stackrel{4}{\langle 3\rangle}\stackrel{7}{\rightarrow}
  \stackrel{5}{\langle 2\rangle}\stackrel{2}{\leadsto}.
\end{eqnarray*}
Putting the above configuration and
the configuration~\eref{eq:example}
\[
  \verb*|1 2 3 4       5    |=|
  \stackrel{1}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{2}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{3}{\langle 1\rangle}\stackrel{1}{\leadsto}
  \stackrel{4}{\langle 3\rangle}\stackrel{7}{\rightarrow}
  \stackrel{5}{\langle 3\rangle}\stackrel{4}{\leadsto}
\]
together, we get a configuration with two slow clusters as
\begin{eqnarray}
  &&\verb*|1 2 3   4       5  6 7 8 9       0    |\nonumber\\
  &&\qquad =
  \stackrel{1}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{2}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{3}{\langle 1\rangle}_1\stackrel{3}{\leadsto}
  \stackrel{4}{\langle 3\rangle}\stackrel{7}{\rightarrow}
  \stackrel{5}{\langle 2\rangle}\stackrel{2}{\leadsto}
  \stackrel{6}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{7}{\langle 1\rangle}\stackrel{1}{\rightarrow}
  \stackrel{8}{\langle 1\rangle}\stackrel{1}{\leadsto}
  \stackrel{9}{\langle 3\rangle}\stackrel{7}{\rightarrow}
  \stackrel{0}{\langle 3\rangle}\stackrel{4}{\leadsto}
  \label{eq:example3}
\end{eqnarray}
Using eq.~\eref{eq:s2s--OVCA2}, we can confirm that
the time evolution out of the above configuration gives
a spatio-temporal patterns below,
\begin{eqnarray*}
  &0:& \verb*|1 2 3   4       5  6 7 8 9       0    | \\
  &1:& \verb*| 1 2 3     4      5 6 7 8   9       0 | \\
  &2:& \verb*|0 1 2 3       4    5 6 7 8     9      | \\
  &3:& \verb*| 0 1 2   3       4  5 6 7 8       9   |.
\end{eqnarray*}
Moving all the cells of the initial configuration
one cell rightward as well as neglecting the difference of the car
indices, we get the configuration at the time 3. Thus the
configuration~\eref{eq:example3} gives a periodic motion of the vehicles
and hence an equilibrium flow of the s2s--OVCA~\eref{eq:s2s--OVCA}.
In the following, we shall confirm that the above construction
of equilibrium flows with multiple slow clusters works
in general, too.

As building blocks of such
solutions, we introduce symbols denoting slow and fast clusters in the
snapshots of the equilibrium solutions \eref{eq:equilibrium0},
\eref{eq:equilibrium1}, \eref{eq:equilibrium3} and \eref{eq:equilibrium2}
in the previous section,
\begin{equation}
  n:|\stackrel{d}{\Rightarrow}
  \langle S\rangle
  \stackrel{h_{s}}{\leadsto}
  \langle F \rangle\stackrel{h_{f}}{\leadsto},\quad
  d=\left\{\begin{array}{ll}
    nv\delta t & 0\leq n\leq m \\
    (n-1)v\delta t-x_0 & m+1\leq n\leq n_0
  \end{array}\right.,
  \label{eq:slowandfastclusters}
\end{equation}
where $\langle S\rangle\stackrel{h_{s}}{\leadsto}$ and
$\langle F\rangle\stackrel{h_{f}}{\leadsto}$
respectively denote the slow and the fast clusters
with varying headways $\stackrel{h_{s,f}}{\leadsto}$ whose lengths
are $h_{s,f}$ on their tops.
For instance, the slow and fast clusters in the
snapshot of the $m$-th time step~\eref{eq:equilibrium3} are
respectively given by
\begin{align*}
  &  \langle S\rangle\stackrel{h_{s}}{\leadsto} :=
  \stackrel{1}{\langle v\rangle}\stackrel{[0]}{\rightarrow}\cdots
  \stackrel{k-1}{\langle v\rangle}
  \stackrel{[0]}{\rightarrow}
  {\stackrel{k}{\langle v\rangle}}_{m}\hspace*{-1em}
  \stackrel{[m]}{\leadsto} \\
  &  \langle F\rangle_F\stackrel{h_{f}}{\leadsto} :=
  \stackrel{k+1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\rightarrow}\cdots
  \stackrel{K-1}{\langle v_0\rangle}
  \stackrel{[n_0+1]}{\leadsto}
  \stackrel{K}{\langle v_0-lx_0/\delta t\rangle}
  \stackrel{[1]-lx_0}{\leadsto},
\end{align*}
where $h_s=[m]$ and $h_f=[1]-lx_0$.
Note that the car $K$ with the intermediate velocity
$v_0-lx_0/\delta t$ is classified into the fast cluster.
We also note that we can always rearrange the order of the vehicles
into the form of eq.~\eref{eq:slowandfastclusters}, thanks to
the periodic boundary condition.

An equilibrium solution with $N$ slow clusters are made with the
slow and fast clusters~\eref{eq:slowandfastclusters} with the same
monitoring period $n_0$, the slow velocity $v$ and the top
velocity $v_0$. First, we prepare $N$ pairs of slow and fast clusters in the
configurations of $N$ equilibrium solutions with only a single
slow cluster,
$\langle S_i \rangle\stackrel{h_{s_i}}{\leadsto}$,
$\langle F_i \rangle\stackrel{h_{f_i}}{\leadsto}$
$i=1,2,\cdots,N$.
We shall consider a configuration made by putting these pairs of slow and fast
clusters in line,
\begin{equation}
  \langle S_{1} \rangle\stackrel{h_{s_1}}{\leadsto}
  \langle F_{1} \rangle\stackrel{h_{f_1}}{\leadsto}
  \langle S_{2} \rangle\stackrel{h_{s_2}}{\leadsto}
  \langle F_{2} \rangle\stackrel{h_{f_2}}{\leadsto}
  \cdots
  \langle S_{N} \rangle\stackrel{h_{s_N}}{\leadsto}
  \langle F_{N} \rangle\stackrel{h_{f_N}}{\leadsto}.
  \label{eq:multi_initial}
\end{equation}
where the periodic boundary condition is imposed.
Thus the total length
of the circuit is the sum of the lengths of all the clusters.

We observed that vanishment of a fast cluster~\eref{eq:equilibrium7}
does not break equilibrium because
the vanished fast cluster was revived by acceleration of
the top car of the slow cluster behind.
However, the top car of the fast cluster does not slow down
if the slow cluster in front of it vanishes.
Thus a vanishing slow cluster does break equilibrium.
If slow down to the slow velocity $v$ of
the top car of any fast cluster $\langle F_i\rangle$ is no later than
speed up to the top velocity $v_0$ of the bottom car of the slow
cluster $\langle S_{i+1}\rangle$ in front of
the fast cluster $\langle F_i\rangle$,
such vanishment of slow clusters is prevented. Thus we require
the above ``no vanishing slow cluster'' (NVSC) rule to be fulfilled
by any pairs of the fast and slow clusters,
$\langle F_i\rangle$ and $\langle S_{i+1}\rangle$, in the
configurations \eref{eq:multi_initial}.

We shall see below that
the above configuration~\eref{eq:multi_initial} satisfying
the NVSC rule
gives an equilibrium solution with $N$ slow clusters.
Speaking more specifically,
we shall confirm that the motion of vehicles belonging to a
pair of slow and fast clusters $\langle S_{i} \rangle
\stackrel{h_{s_{i}}}{\leadsto}\langle F_{i}
\rangle\stackrel{h_{f_{i}}}{\leadsto}$, $i=1,2,\cdots,N$, in
the  above configuration~\eref{eq:multi_initial}
with multiple slow clusters is the same as that without
any other pairs of slow and fast clusters
we have investigated in detail in the previous section.

Consider the time evolution of a fast cluster
and its varying headway
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$, $i=1,2,\cdots,N$.
It is determined
by the motion of the vehicle at the bottom of the slow cluster
$\langle S_{i+1} \rangle\stackrel{h_{s_{i+1}}}{\leadsto}$
in front of it,
which is different from its original partner in the solution
with a single slow-cluster
$\langle S_{i}\rangle\stackrel{h_{s_{i}}}{\leadsto}$ behind it.
However, thanks to the NVSC rule, the bottom of
$\langle S_{i+1} \rangle\stackrel{h_{s_{i+1}}}{\leadsto}$
keeps the slow velocity $v$ until the top of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$
slows down to $v$. Thus the motion of the bottom of
$\langle S_{i+1} \rangle\stackrel{h_{s_{i+1}}}{\leadsto}$
is the same as that of the bottom of
$\langle S_{i}\rangle\stackrel{h_{s_{i}}}{\leadsto}$ and
so is the motion of the fast cluster
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$
until its top slows down to $v$.
Let us now think about the time evolution
after the top of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$
slows down to $v$. In the same manner we observed in the solution
with only a single slow cluster in the previous section,
the top of $\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$
keeps the slow velocity $v$ at least for
$n_0+1$ time steps.
The time evolution of the
varying headway, which locates in front of the second car of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$,
and the motion of the remaining cars of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$ are now
determined by the above motion of the top of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$.
Thus the time evolution of
the fast cluster and its varying headway
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$ remains
the same as that with only a single slow cluster we observed
in the previous section at least for
$n_0+1$ time steps after the top of
$\langle F_{i} \rangle\stackrel{h_{f_{i}}}{\leadsto}$
slows down to $v$ and at least for $n_0+1$ time steps
from the beginning.

Let us turn ourselves now to
the time evolution of a slow cluster and its varying headway
$\langle S_{i} \rangle
\stackrel{h_{s_{i}}}{\leadsto}$, $i=1,2,\cdots,N$.
The time evolution is determined
by the motion of the vehicle at the bottom of the fast cluster
in front of it,
which is nothing but its original partner in the solution
with a single slow-cluster, $\langle F_{i}
\rangle\stackrel{h_{f_{i}}}{\leadsto}$. We now know that
the time evolution of the fast cluster $\langle F_{i}
\rangle\stackrel{h_{f_{i}}}{\leadsto}$ is the
same as those with only a single slow cluster for $n_0+1$ time steps.
Thus the time evolution of the the slow cluster
$\langle S_{i} \rangle\stackrel{h_{s_{i}}}{\leadsto}$
and its varying headway in the
configuration
with multiple slow clusters~\eref{eq:multi_initial} is the same as that
in the configuration with only a single slow cluster
for $n_0+1$ time steps.

As we saw in the configuration with only a single slow cluster
in the previous section, the time evolution of
the slow and the fast clusters as well as their varying headways are
periodic with the period $n_0+1$. Thus,
also in the configuration
with multiple slow clusters~\eref{eq:multi_initial},
the time evolution of
all of the slow and the fast clusters as well as their varying
headways are periodic with the period $n_0+1$.
To summarize, we have confirmed that
the motion of vehicles belonging to a
pair of slow and fast clusters $\langle S_{i} \rangle
\stackrel{h_{s_{i}}}{\leadsto}\langle F_{i}
\rangle\stackrel{h_{f_{i}}}{\leadsto}$, $i=1,2,\cdots,N$, in
the configuration~\eref{eq:multi_initial}
with multiple slow clusters is the same as that without
any other pairs of slow and fast clusters
we have investigated in detail in the previous section and that
it gives an equilibrium solution with $N$ slow clusters.

Let us examine the flow--density relation of the traffic evolving out
of the configuration with $N$ slow clusters~\eref{eq:multi_initial}.
Let $L_i$, $K_i$, $Q_i$ and $\rho_i:=K_i/L_i$ be the circuit length, the number
of vehicles,
the mean flow averaged over one period, i.e.
$n_0+1$ time steps, and the density of vehicles for the configuration
with only one slow cluster,
$\langle S_i\rangle\stackrel{h_{s_{i}}}{\leadsto}\langle F_i\rangle\stackrel{h_{f_{i}}}{\leadsto}$,
$i=1,2,\cdots,N$. In \S\ref{sec:2}, we confirmed that $Q_i$ and $\rho_i$
satisfied the flow--density relation~\eref{eq:empirical},
\begin{equation}
  Q_i=\dfrac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho_i
  +\dfrac{1}{(n_0+1)\delta t}.
  \label{eq:empirical2}
\end{equation}
The circuit length $L$ and the number of vehicles $K$
of the configuration with
$N$ slow clusters are then expressed by
$L:=\sum_{i=1}^N L_i$ and $K:=\sum_{i=1}^N K_i$.
The mean flow $Q$ that is again averaged over the period
as well as the vehicle density $\rho$
of the configuration with $N$ slow clusters are expressed by
\begin{align*}
  Q & = \dfrac{1}{L}\sum_{i=1}^N L_i Q_i=\sum_{i=1}^{N}\lambda_i Q_i, \\
  \rho & = \dfrac{K}{L} =\sum_{i=1}^N \lambda_i\rho_i,
\end{align*}
with $\lambda_i:=L_i/L$. Using an identity $\sum_{i=1}^N\lambda_i=1$
as well as the flow density relation for the configuration with
a single slow cluster~\eref{eq:empirical2}, one
straightforwardly confirms
\begin{align*}
  Q-\dfrac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho & =
  \sum_{i=1}^N\lambda_i\Bigl(
      Q_i-\dfrac{n_0 v\delta t-x_0}{(n_0+1)\delta t}\rho_i
  \Bigr) \\
  & = \Bigl(\sum_{i=1}^N\lambda_i\Bigr)\dfrac{1}{(n_0+1)\delta t}
  = \dfrac{1}{(n_0+1)\delta t},
\end{align*}
which concludes that
$Q$ and $\rho$ also satisfy the flow--density relation~\eref{eq:empirical}.
Note that the relation can be confirmed in a more intuitive manner,
as we have shown for the configuration with only a single slow
cluster.

\section{Concluding Remarks}
\label{sec:4}
We have introduced a set of exact solutions of the s2s--OVCA and
have explained the piecewise linear fundamental diagram of the model.
The empirical formula for the flow--density relation of
the s2s--OVCA~\eref{eq:empirical} has been
read out of the numerically obtained fundamental diagram in Figs.~\ref{fig:1}
and \ref{fig:2}. A set of exact periodic solutions that possesses only
a single slow cluster has been presented, which has reproduced the
formula for the flow--density relation of the s2s--OVCA~\eref{eq:empirical}.
With the use of these solutions, another set of exact periodic solutions
with multiple slow clusters, which have been observed in the numerically
obtained spatio-temporal pattern in Fig.~\ref{fig:1} has been
introduced. And these solutions again have explained the flow--density
relation of the s2s--OVCA~\eref{eq:empirical}.

We should comment about a couple of problems in our mind
related to the present results.
The solutions given in \S\ref{sec:2} and \S\ref{sec:3} provide
a set of equilibrium flows which correspond all the points
on the fundamental diagram of the s2s--OVCA. But we do not know
if the set we have presented in \S\ref{sec:2} and \S\ref{sec:3}
gives all possible equilibrium flows or not.
There might be a solution giving an equilibrium flow that does not belong to
the set. By numerical experiments~\cite{Oguma2009}, we observed
that time evolutions out of all the initial conditions we
verified eventually go to some equilibrium flows. But this observation
still remains numerical observation and lacks proof.
For the case of $n_0=1$,
these problems were investigated~\cite{Tian2009} and
should be extended to all the cases of $n_0$'s.
As was shown in our previous paper~\cite{Oguma2009},
the s2s--OVCA~\eref{eq:s2s--OVCA} transforms to
the s2s--OV model~\eref{eq:s2s--OV} through
the inverse ultradiscretization and the continuous limit.
Note that the monitoring period $n_0$ in the
s2s--OVCA must be a free parameter so as to make
the monitoring period $t_0$ in the
s2s--OV model a free parameter.
It should be clarified if the characteristics of the equilibrium
solution of the s2s--OVCA given in this paper remain in
the solution of the s2s--OV model.

\acknowledgements One of the authors (HU) is grateful to
K.~Oguma for the previous collaboration.


\section{Introduction}

Notation in this note is standard. We consider undirected graphs without loops and multiedges. For a graph $G$, denote by $E(G)$ the set of edges and $V(G)$ the set of vertices of $G$. The \emph{order} of a graph is the number of its vertices. The number of edges of $G$ is denoted by $e(G) = |E(G)|$. For $U \subseteq V(G)$, let $G[U]$ be the subgraph of $G$ induced by $U$. A path on $k$ vertices is denoted by $P_k$, a star with $k+1$ vertices is denoted by $S_k$ and a cycle with $k$ edges is denoted by $C_k$. A \emph{matching} in $G$ is a set of vertex disjoint edges from $E(G)$, denote by $M_k$ a matching of size $k$. Denote by $T_{n,p}$ the $p$-class \emph{Tur\'an graph}, namely the complete $p$-partite graph on $n$ vertices with the size of each partite set as equal as possible.

The \emph{extremal number}, $\ex(n,H)$, of a graph $H$ is the maximum number of edges in a graph on $n$ vertices which does not contain $H$ as a subgraph. An $H$-free $n$-vertex graph with $\ex(n,H)$ edges is called an \emph{extremal graph} for $H$, or $H$-\emph{extremal}. Tur\'an \cite{Turan41,Turan54} showed that $T_{n,p}$ is the unique extremal graph for $K_{p+1}$. The Erd\H{o}s-Stone-Simonovits Theorem \cite{ErSim66,ErSt46} states that asymptotically Tur\'an's construction is best-possible for any $(p+1)$-chromatic graph $H$ (as long as $p\ge 2$). More precisely $\ex(n,H) = \left(1-\frac{1}{p}\right)\frac{n^2}{2} + o(n^2)$.

Given a graph $H$, the \emph{blow-up} of $H$, denoted as $H^{p+1}$, is the graph obtained from replacing each edge in $H$ by a clique of size $p+1$ where the new vertices of the cliques are all different (see Figure~\ref{fig-0}(a)).

Erd\H{o}s, F\"{u}redi, Gould and Gunderson \cite{Inter-tri} determined, for sufficiently large $n$, the extremal number for triangles intersecting in exactly one common vertex. One can think of this graph as blowing up edges of a star to triangles. More generally, $k$ cliques of size $p+1$ intersecting in exactly one common vertex is $S_k^{p+1}$, Chen, Gould, Pfender and Wei \cite{Inter-cli} generalized the main result of \cite{Inter-tri} to $S_k^{p+1}$:

\begin{theorem}\label{inter-clique}\cite{Inter-cli}
For any $p\ge 2$ and $k\ge 1$, and for any $n\ge 16k^3(p+1)^8$, we have
$$\ex(n,S_k^{p+1})=\ex(n,K_{p+1})+
\left\{
  \begin{array}{l l}
    k^2-k & \quad \text{if $k$ is odd,}\\
    k^2-\frac{3}{2}k & \quad \text{if $k$ is even.}\\
  \end{array} \right.$$
\end{theorem}

Given two vertex-disjoint graphs $H$ and $G$, denote by $H\bigotimes G$ the graph obtained by joining each vertex of $H$ to each vertex of $G$. Let $H(n,p,s)$ be $K_{s-1}\bigotimes T_{n-s+1,p}$ (see Figure~\ref{fig-0}(b)) and $H'(n,p,s)$ be any of the graphs obtained by putting one extra edge in any class of $T_{n-s+1,p}$ in $H(n,p,s)$.

\begin{figure}[ht]
\begin{center}
\includegraphics{Hn}
\end{center}
\caption{(a) $C_4^4$; (b) $H(n,p,s)$; (c) $H^*(n)$.}
\label{fig-0}
\end{figure}

Recently, Glebov \cite{Cli-path} determined, for sufficiently large $n$, the extremal number and the extremal graphs for the blow-up of paths. More history of this topic are given in Section~\ref{prel}.

\begin{theorem}\label{cli-path}\cite{Cli-path}
For any $p\ge 2$ and $k\ge 1$, and for any $n>16k^{11}(p+1)^8$, $H(n,p,\lfloor\frac{k-1}{2}\rfloor+1)$ ($H'(n,p,\lfloor\frac{k-1}{2}\rfloor+1)$ resp.) is the unique extremal graph for $P_{k+1}^{p+1}$ when $k$ is odd (even resp.).
\end{theorem}

The main motivation for this note is that \cite{Inter-cli}, \cite{Inter-tri} and \cite{Cli-path} give sporadic results about problems of the same flavor. We unite these extremal problems for blow-ups of graphs and look at the general theory behind these results by investigating the decomposition families of the forbidden graphs. Using the method in \cite{S-sym} (see also \cite{S-I}, \cite{S-H}), we determine the extremal number and found all extremal graphs for all blow-ups of cycles. Somewhat surprisingly, the result for blow-ups of cycles is not much different from blow-ups of paths except for $C_3^3$. Before stating our results, we need a definition. Let $H^*(n)$ be graphs obtained by putting (almost) perfect matchings in both classes in $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$ (see Figure~\ref{fig-0}(c)).

\begin{theorem}\label{cli-cycle}
For any $p\ge 2$ and $k\ge 3$, when $n$ is sufficiently large, we have the following results:

(i) For any $C_k^{p+1}\neq C_3^3$, $H(n,p,\lfloor\frac{k-1}{2}\rfloor+1)$ ($H'(n,p,\lfloor\frac{k-1}{2}\rfloor+1)$ resp.) is the unique extremal graph for $C_{k}^{p+1}$ when $k$ is odd (even resp.).

(ii) For $C_3^3$, if $4|n$, $H^*(n)$ is the unique extremal graph; otherwise both $H^*(n)$ and $H(n,2,2)$ are extremal graphs.
\end{theorem}

\begin{figure}[ht]
\begin{center}
\includegraphics{C-3-3}
\end{center}
\caption{(a) $C_3^3$; (b) $H^*(n)$; (c) $H(n,2,2)$.}
\label{C33}
\end{figure}

\begin{rmk}
Both $H'(n,p,s)$ and $H^*(n)$ might contain non-isomorphic graphs. However graphs in the same family are similar in the sense that they have the same number of edges. Since their difference does not matter in this note, we will treat each of them as a ``unique'' graph instead of families of graphs.
\end{rmk}

In addition, for a large class of trees, we determined the extremal number for their blow-up graphs and found their unique extremal graph.

\begin{theorem}\label{cli-trees}
Given a tree $T$, denote by $A$ and $B$ its two color classes with $|A|\le |B|$. For any $p\ge 3$, when $n$ is sufficiently large, we have that

(i) if $T$ has a leaf in $A$ and $\alpha(T)=|B|$, then $H(n,p,|A|)$ is the unique extremal graph for $T^{p+1}$.

(ii) if the minimum degree in $A$ is 2, then $H'(n,p,|A|)$ is the unique extremal graph for $T^{p+1}$.
\end{theorem}

\begin{rmk}
Trees considered in Theorem~\ref{cli-trees} (i) include even paths and those in (ii) include odd path. Hence it implies Theorem~\ref{cli-path} when $p\ge 3$. For $p=2$, the technique in the proof of Theorem~\ref{blow-up cycle} (see Appendix) works for blow-ups of paths. It is not difficult to see that in a proper subdivision of any star, its smaller color class either has minimum degree 2 or has a leaf and its independence number equals to the size of the larger color class, thus Theorem~\ref{cli-trees} can be applied to blow-ups of a proper subdivision of stars, which is an extention of Theorem~\ref{inter-clique}.
\end{rmk}

The rest of this paper is organized as follows: in Section~\ref{prel} we provide more motivation and the key lemma. Section~\ref{blow-up cycle} gives a proof for Theorem~\ref{cli-cycle} when $p\ge 3$ and Section~\ref{blow-up tree} is devoted to proof of Theorem~\ref{cli-trees} (i). The proof for Theorem~\ref{cli-trees} (ii) is similar, we include a sketch of its proof in Appendix together with a proof for Theorem~\ref{cli-cycle} when $p=2$.

We finish this section with a few more definitions that will be used later. We denote the \emph{degree} of a vertex $v$ by $d(v)$ and write $N(v)$ for the set of its neighbors and for $S\subseteq V(G)$, let $N(S)$ be the set of vertices that have some neighbors in $S$. Denote by $K_t^-$ the graph obtained from deleting an edge from a complete graph on $t$ vertices.
A \emph{dominating vertex} in $G$ is a vertex that is adjacent to all other vertices in $G$.
A \emph{linear forest} is a forest whose connected components are paths.
Two disjoint vertex sets $U$ and $W$ are \emph{completely joined} in $G$ if $uw\in E(G)$ for all $u\in U, w\in W$. Write $kH$ for the vertex disjoint union of $k$ copies of $H$. For two vertex-disjoint graphs $H$ and $G$, denote by $H\cup G$ the disjoint union of $H$ and $G$.

\section{Motivation and History}\label{prel}

Given a graph $H$, a \emph{vertex split} on some vertex $v\in V(H)$ is defined as follows: replace $v$ by an independent set of size $d(v)$ in which each vertex is adjacent to exactly one distinct vertex in $N_H(v)$. Given a vertex subset $U\subseteq V(H)$, a vertex split on $U$ means applying vertex split on the vertices in $U$ one by one. It is not difficult to see that the order of vertices we apply vertex split does not matter. Denote by $\mathcal{H}(H)$ the family of graphs that can be obtained from $H$ by applying vertex split on some $U\subseteq V(H)$. Note that $U$ could be empty, therefore $H\in \mathcal{H}(H)$. For example, $\mathcal{H}(P_{k+1})$ is the family of all linear forests with $k$ edges and $\mathcal{H}(C_k)$ consists of $C_k$ and all linear forests with $k$ edges. Given a family $\mathcal{L}$, define $p=p(\mathcal{L})=\displaystyle\min_{L\in \mathcal{L}}\chi(L)-1$.

\begin{defn}
Denote by $I_v$ the $v$-vertex graph with no edges. Given a family $\mathcal{L}$, let $\mathcal{M}:=\mathcal{M}(\mathcal{L})$ be the family of minimal graphs $M$ for which there exist an $L\in\mathcal{L}$ and a $t=t(L)$ such that $L\subseteq M'\bigotimes K_{p-1}(t,\ldots,t)$, where $M'=M\cup I_t$. We call $\mathcal{M}$ the \emph{decomposition family} of $\mathcal{L}$.
\end{defn}

Thus, a graph $M$ is in $\mathcal{M}$ if the graph obtained from putting $M$ into a class of a large $T_{n,p}$ contains some $L\in\mathcal{L}$. If $L\in\mathcal{L}$ with minimum chromatic number $p+1$, then $L\subseteq K_{p+1}(t,\ldots,t)$ for some $t\ge 1$, therefore the decomposition family $\mathcal{M}$ always contains some bipartite graphs.

\begin{expl}
Denote by $O_6$ the edge-graph of the octahedron, namely $O_6=K_{2,2,2}$. Since $O_6=C_4\bigotimes I_2$, we have that $\mathcal{M}(O_6)=\{C_4\}$. For any $\ell>1$, $\mathcal{M}(C_{2\ell+1})=\{P_2\}$. For blow-ups of stars, $\mathcal{M}(S_k^{p+1})=\{S_k, M_k\}$ for $p\ge 2$ and $k\ge 1$; for blow-ups of paths $\mathcal{M}(P_{k+1}^{p+1})=\{$all linear forests with $k$ edges$\}=\mathcal{H}(P_{k+1})$ and for cycles $\mathcal{M}(C_k^{p+1})=\{C_k, $ all linear forests with $k$ edges$\}=\mathcal{H}(C_k)$ for $p\ge 3$ and $k\ge 1$.
\end{expl}

For a family of forbidden graph $\mathcal{L}$ with decomposition family $\mathcal{M}$, we have
\begin{equation}\label{eq:bounds}
e(T_{n,p})+ \ex(\frac{n}{p},\mathcal{M})\le \ex(n,\mathcal{L})\le e(T_{n,p})+(1+o(1))p\cdot \ex(\frac{n}{p},\mathcal{M}),
\end{equation}
where the lower bound is obtained from putting an $\mathcal{M}$-extremal graph in one of the classes in $T_{n,p}$ (see \cite{bib-bollobas-EGT}).

The Erd\H{o}s-Stone-Simonovits Theorem determines asymptotically the extremal functions of non-bipartite graphs, while the decomposition family governs the finer error terms as shown in~\eqref{eq:bounds}, thus it helps to give sharper bounds on the extremal number.

There are examples where the upper bound in~\eqref{eq:bounds} holds. Let $Q(r,p)$ be the graph consisting of a dominating vertex and a $p$-class Tur\'an graph on $rp$ vertices, namely $Q(r,p)=T_{rp,p}\bigotimes I_1$. Notice that $\mathcal{M}(Q(r,p))=\{S_r\}$, thus an $\mathcal{M}(Q(r,p))$-free graph has maximum degree $r-1$. Simonovits \cite{Simonovits1966} showed that a $Q(r,p)$-extremal graph can be obtained from putting (almost) $(r-1)$-regular triangle-free graphs into each class of a $T_{n,p}$.

We recall the Octahedron Theorem by Erd\H{o}s and Simonovits \cite{octahedron}, which gives an example where neither the upper bound nor the lower bound in~\eqref{eq:bounds} is true.

\begin{theorem}\label{oct}
For sufficiently large $n$, every $O_6$-extremal graph $S_n$ can be obtained as $S_n=U_m\bigotimes Z_{n-m}$, for some $m$-vertex $C_4$-extremal graph $U_m$ and some $(n-m)$-vertex $P_3$-extremal graph $Z_{n-m}$, where $m=n/2+o(n)$.
\end{theorem}

A graph $L$ is \emph{weakly edge-color-critical}, or shortly \emph{weakly-critical}, if there is an edge $e\in E(L)$ for which $\chi(L-e)<\chi(L)$. Simonovits \cite{Simonovits1966} proved that the Tur\'an graph is the unique extremal graph for weakly-critical graphs when $n$ is sufficiently large. In the same paper, he also proved when the forbidden graph is $L=sH$, where $H$ is weakly-critical, and $\chi(H)=p+1\ge 3$, then for sufficiently large $n$, the unique $L$-extremal graph is $H(n,p,s)$. Later in \cite{S-sym}, he further generalized this result to the following theorem.

\begin{theorem}\label{Hnps-thm}
Let $\mathcal{L}$ be the family of forbidden graphs and $p=p(\mathcal{L})=\displaystyle\min_{L\in \mathcal{L}}\chi(L)-1$. If by omitting any $s-1$ vertices of any $L\in \mathcal{L}$ we obtain a graph with chromatic number at least $p+1$, but by omitting $s$ suitable edges of some $L\in \mathcal{L}$ we get a $p$-colorable graph, then $H(n,p,s)$ is the unique extremal graph for $n$ sufficiently large.
\end{theorem}

Simonovits~\cite{when-Hnps} asked the following question.
\begin{ques}\label{question}
Characterize graphs whose unique extremal graph is of the form $H(n,p,s)$.
\end{ques}

We make a step towards answering Question~\ref{question}: notice that the blow-ups of cycles and trees does not satisfy the hypothesis in Theorem~\ref{Hnps-thm}, hence Theorem~\ref{cli-cycle} and~\ref{cli-trees} provides an additional family of forbidden graphs whose unique extremal graph is $H(n,p,s)$ for suitable $p$ and $s$.

On the other hand, the results in \cite{Inter-cli}, \cite{Inter-tri}, \cite{Cli-path}, \cite{Simonovits1966} and \cite{S-sym} show that for blow-ups of stars, paths and many other families of graphs, the lower bound construction is optimal. Our results show that for blow-ups of cycles and a large class of trees, this is also the case. It would be interesting to describe all decomposition families $\mathcal{M}$ where the lower bound in~\eqref{eq:bounds} is sharp. Here we make the first attempt towards this direction.

The following lemma shows that the decomposition family of blow-ups of some graphs (in particular bipartite graphs) is actually the family obtained from splitting its vertices.

\begin{lemma}\label{key-lem}
Given $p\ge 3$ and any graph $H$ with $\chi(H)\le p-1$, $\mathcal{M}(H^{p+1})=\mathcal{H}(H)$. In particular, a matching of size $e(H)$ is in $\mathcal{M}(H^{p+1})$.
\end{lemma}

\noindent\textbf{Proof.}
Note that $\chi(H^{p+1})=p+1$, by the definition of decomposition family, any graph $M$ in $\mathcal{M}(H^{p+1})$ is a minimal graph under the condition that there exists a copy of $M$ in $H$, such that removing the vertex set of $M$ together with a suitable independent set $I_v$ results in a $(p-1)$-colorable graph. Since $I_v$ is an independent set, it can have at most one vertex from each $(p+1)$-clique in $H^{p+1}$. Recall the removal of $M\cup I_v$ decreases the chromatic number by at least two, this implies $M$ should have at least one vertex from each $(p+1)$-clique in $H^{p+1}$. Since a vertex from $M$ and a vertex from $I_v$ in the same $(p+1)$-clique would be adjacent, which contradicts the minimality of $M$, thus $I_v$ is empty and $M$ includes exactly two vertices from each $(p+1)$-clique in $H^{p+1}$. Locally, for each $v\in H$, $N_H(v)\cup \{v\}$ spans a $S_{d_H(v)}^{p+1}$ in $H^{p+1}$.
If the center of that $S_{d_H(v)}^{p+1}$ is in $M$, then $M$ also contains exactly one other vertex from each of the $(p+1)$-cliques in this $S_{d_H(v)}^{p+1}$. This implies $v$ is not a split vertex in $M$. Otherwise, $M$ contains two vertices from each $(p+1)$-cliques of $S_{d_H(v)}^{p+1}$, which implies that $v$ was split into $d_H(v)$ leaves in $M$. Hence $\mathcal{M}(H^{p+1})=\mathcal{H}(H)$. In particular, by splitting all vertices of $H$, we obtain a matching of size $e(H)$.
\qed

\medskip

The following definition was introduced in \cite{S-sym}.

\begin{defn}\label{def:sym}
Denote by $\mathbb{D}(n,p,r)$ the family of $n$-vertex graphs $G_n$ satisfying the following symmetry condition:

(i) It is possible to omit at most $r$ vertices of $G_n$ so that the remaining graph $G'$ is a product of graphs of almost equal order:
$G'=\displaystyle\prod_{i\le p}G^i$, where $|V(G^i)|=n_i$ and $|n_i-\frac{n}{p}|\le r$, for every $i\le p$.

(ii) For every $i\le p$, there exist connected graphs $H_i$ such that $G_i=k_iH_i$, where $k_i=\frac{n_i}{|V(H_i)|}$ and any two copies $H_i^j,H_i^{\ell}$ in $G_i$ ($1\le j< \ell\le k_i$), are \emph{symmetric subgraphs} of $G_n$: there exists an isomorphism $\omega:H_i^j\rightarrow H_i^{\ell}$ such that for every $x\in H_i^j$, $u\in G_n-H_i^j-H_i^{\ell}$, $xu\in E(G_n)$ if and only if $\omega(x)u\in E(G_n)$.
\end{defn}

The graphs $H_i$ will be called the \emph{blocks}, the vertices in $G_n-G'$ will be called \emph{exceptional} vertices (see Figure~\ref{symm}).

\begin{figure}[ht]
\begin{center}
\includegraphics{symm}
\end{center}
\caption{Symmetric subgraphs: blocks here are $K_4^-$, $K_3$ and $P_2$ respectively.}
\label{symm}
\end{figure}

We will need the following two results of Simonovits (\cite{S-sym, S-H}).

\begin{theorem}\label{th:S-sym}\cite{S-sym}
Assume that a finite family $\mathcal{L}$ of forbidden graphs with $p(\mathcal{L})=p$ is given. If for some $L\in \mathcal{L}$ and $\ell:=|V(L)|$,
\begin{equation}\label{eq:path}
L\subseteq P_{\ell}\bigotimes K_{p-1}(\ell,\ell,\ldots,\ell),
\end{equation}
then there exist $r=r(L)$ and $n_0=n_0(r)$ such that $\mathbb{D}(n,p,r)$ contains an $\mathcal{L}$-extremal graph for every $n>n_0$. Furthermore, if this is the only extremal graph in $\mathbb{D}(n,p,r)$, then it is the unique extremal graph for every sufficiently large $n$.
\end{theorem}

\begin{theorem}\label{S-H}\cite{S-H}
Assume that a finite family $\mathcal{L}$ of forbidden graphs with $p(\mathcal{L})=p$ is given. If for some $L\in \mathcal{L}$ and $\ell:=|V(L)|$,
\begin{equation}\label{eq:matching}
L\subseteq \ell P_2\bigotimes K_{p-1}(2\ell,2\ell,\ldots,2\ell),
\end{equation}
then there exist $r=r(L)$ and $n_0=n_0(r)$ such that $\mathbb{D}(n,p,r)$ contains an $\mathcal{L}$-extremal graph for every $n>n_0$. Furthermore for any $\mathcal{L}$-extremal graph $G\in\mathbb{D}(n,p,r)$, we have that

(i) all blocks of $G$ will consist of isolated vertices: the product graph $G'$ will be a Tur\'{a}n graph $T_{n',p}$.

(ii) each exceptional vertex in $G-G'$ is joined either to all the vertices of $G'$ or to all the vertices of $p-1$ classes of $G'$ and to no vertex of the remaining class.
\end{theorem}

The key idea of the proof of Theorem~\ref{cli-cycle} is using Theorem~\ref{S-H} to get a good vertex partition of an extremal graph of $C_k^{p+1}$. Then show that in this partition, there are $t$ exceptional vertices, where $t=\lfloor\frac{k-1}{2}\rfloor$, and the remaining of the graph is a Tur\'an graph (with one extra edge if $k$ is even). This together with $G$ being extremal imply $G\simeq H(n,p,t+1)$ ($H'(n,p,t+1)$ if $k$ is even).

\begin{rmk}
Assume first $k$ is odd. Notice that $H(n,p,t+1)$ is $C_{k}^{p+1}$-free. Indeed the set of $t$ dominating vertices in $H(n,p,t+1)$ together with one class of $T_{n-t,p}$ is $\mathcal{H}(C_{k})$-free. By Lemma~\ref{key-lem}, $\mathcal{M}(C_k^{p+1})=\mathcal{H}(C_{k})$ when $p\ge 3$, and observe that when $p=2$, $\mathcal{M}(C_k^{3})\subseteq \mathcal{M}(C_k^{p+1})$. Thus $H(n,p,t+1)$ is the product of $p-1$ empty graphs and one $\mathcal{M}(C_{k}^{p+1})$-free graph, which is the lower bound construction in~\eqref{eq:bounds}. Hence $H(n,p,t+1)$ is $C_{k}^{p+1}$-free. Similarly when $k$ is even, $H'(n,p,t+1)$ is $C_{k}^{p+1}$-free.
\end{rmk}

\section{Proof of Theorem~\ref{cli-cycle}}\label{blow-up cycle}

\noindent\textbf{Proof.}
We prove Theorem~\ref{cli-cycle} for $p\ge 3$. A crucial observation is that \eqref{eq:path} is equivalent to $\mathcal{M}(C_k^{p+1})$ containing some linear forest of size at most $\ell$ and (3) is equivalent to $\mathcal{M}(C_k^{p+1})$ containing a matching of size at most $\ell$. Since $P_{k+1}\in\mathcal{M}(C_k^{p+1})$, \eqref{eq:path} is satisfied with $L=C_k^{p+1}, \ell=k+1$. Thus by Theorem~\ref{th:S-sym}, there exists an extremal graph $G$ in $\mathbb{D}(n,p,r)$ of $C_{k}^{p+1}$ for some $r$. It suffices to prove that $G\simeq H(n,p,t+1)$ ($H'(n,p,t+1)$ resp.) when $k$ is odd (even resp.). Then Theorem~\ref{th:S-sym} implies it would be the unique extremal graph. Since $M_k\in\mathcal{M}(C_k^{p+1})$, \eqref{eq:matching} is also satisfied with $L=C_k^{p+1}, \ell=k$. We can apply Theorem~\ref{S-H} to get a vertex partition of $G$. Let $A_1,\ldots,A_p$ be the $p$ classes in $T_{n',p}$. Let $W$ be the set of vertices in $G-T_{n',p}$ that are joined to all vertices in $T_{n',p}$ and let $B_i$ be the set of vertices in $G-T_{n',p}-W$ that are joined to all the vertices in $T_{n',p}$ but $A_i$ (see Figure~\ref{longpath}(a)). Define $C_i=A_i\cup B_i$, for all $i$. Note that in $G$ all the cross-edges between $A_i$ and $C_j$ with $i\neq j$ are present, there might be some missing edges between some $B_i$ and $B_j$. Let $D_i\subseteq C_i$ consist of vertices with no neighbor in $W$. Recall that $\mathcal{M}(C_k^{p+1})=\{C_k, $ all linear forests with $k$ edges$\}$. We will frequently use the following fact.

\begin{claim}\label{M}
For any $i\le p$, $G[W\cup C_i]$ is $\mathcal{M}(C_k^{p+1})$-free.
\end{claim}
\noindent\textbf{Proof.}
Notice that $W\cup C_i$ is completely joined to $\displaystyle\bigcup_{j\neq i}A_j$. If for some $M\in\mathcal{M}(C_k^{p+1})$, $M\subseteq G[W\cup C_i]$, then $M'\bigotimes K_{p-1}(n'/p,\ldots,n'/p)\subseteq G$. This, by the definition of decomposition family, implies $C_k^{p+1}\subseteq G$, a contradiction.
\qed
\medskip

\begin{figure}[ht]
\begin{center}
\includegraphics{longpath}
\end{center}
\caption{(a): a partition of $G$; (b): If $|W|>t$, then $2|W|+1\ge k+1$, $P_{k+1}\subseteq G[W\cup A_i]$.}
\label{longpath}
\end{figure}

\begin{claim}\label{c1}
$|W|=t=\lfloor\frac{k-1}{2}\rfloor$.
\end{claim}
\noindent\textbf{Proof.}
First of all, $|W|\le t$. Indeed, by Claim~\ref{M}, $G[W\cup C_i]$ is $\mathcal{M}(C_k^{p+1})$-free. Since $W$ and $A_i$ are completely joined, if $|W|>t$, then $P_{k+1}\subseteq G[W\cup A_i]$ (see Figure~\ref{longpath}(b)). But $P_{k+1}\in\mathcal{M}(C_k^{p+1})$, a contradiction.

On the other hand, suppose $|W|\le t-1$, then some simple calculation shows
$$e(G)\le e(T_{n,p})+\frac{t-1}{p}n+o(n).$$
However since $C_{k}^{p+1}\not\subseteq H(n,p,t+1)$, we have
$$e(G)\ge e(H(n,p,t+1)) \ge e(T_{n,p})+\frac{t}{p}n+o(n),$$
a contradiction.
\qed
\medskip

\noindent\textbf{Case 1:} $k$ is odd. Then $t=\frac{k-1}{2}$.
We shall show that for each $i\le p$, $G[C_i]$ has no edge. Then by Claim~\ref{c1} and the maximality of $G$,  $G\simeq H(n,p,t+1)$. Indeed, any edge $xy\in C_i$ together with a $P_{2|W|+1}=P_k$ in $G[W\cup A_i]$ avoiding $\{x,y\}$ form a linear forest with $k$ edges, which is in $\mathcal{M}(C_{k})$. This contradicts Claim~\ref{M}.

\medskip

\noindent\textbf{Case 2:} $k$ is even. Then $t=k/2-1$. It suffices to prove following claim. This together with Claim~\ref{c1} and the maximality of $G$ implies $G\simeq H'(n,p,t+1)$.

\begin{claim}\label{c2}
When $k$ is even, we have (i) each $G[C_i]$ has at most one edge; (ii) the edge in $C_i$ has at least one endpoint not in $D_i$; and (iii) there is at most one class $G[C_i]$ having one such edge.
\end{claim}

\noindent\textbf{Proof.}
(i): For contradiction suppose there are two edges in some $G[C_i]$, say $e_1$ and $e_2$. Then one can find a copy of $P_{2|W|+1}=P_{k-1}$ in $G[W\cup A_i]$ avoiding the endpoints of $e_1,e_2$, so we get a linear forest with $k$ edges in $G[W\cup C_i]$, a contradiction.

(ii): Suppose $u_iv_i\in E(G[C_i])$ and $u_i,v_i\in D_i$. Since $k$ is even hence $k\ge 4$, therefore $W$ is not empty: $|W|=t=k/2-1\ge 1$. Denote $G_0$ the graph obtained by deleting the edge $u_iv_i$ and adding all edges between $\{u_i,v_i\}$ and $W$. There are at least two such cross-edges since $W$ is nonempty and $u_i,v_i\in D_i$. Thus $e(G_0)>e(G)$. It remains to show $G_0$ is also $C_{k}^{p+1}$-free, which contradicts to the extremality of $G$. Notice that $u_i$ and $v_i$ is not joined to any vertex in $C_i$ in $G_0$. Hence they have the same neighborhood as vertices in $A_i$. Also since $G$ and $G_0$ only differ at $u_i$ and $v_i$, a copy of $C_k^{p+1}$ in $G_0$ must involve $u_i$ or $v_i$ or both. But then one can obtain a copy of $C_k^{p+1}$ in $G$ by replacing vertices from $\{u_i,v_i\}$ by vertices from $A_i$, a contradiction.

(iii): Suppose for some $i\neq j$, $u_iv_i\in E(G[C_i])$ and $u_jv_j\in E(G[C_j])$ with $u_i\not\in D_i$ and $u_j\not\in D_j$. Then we can find a copy of $P_k$ in $G[C_i\cup W]$ which starts at a vertex in $A_i$ and whose last edge is $u_iv_i$. Denote vertices of such a path $x_1,x_2,\ldots,x_{k-2},u_i,v_i$ with $x_1\in A_i$. We can then extend this path to a $P_k^{p+1}$ in $G$ (see Figure~\ref{path-cyl}(a)).

Since $p\ge 3$, there is a third class, say $A_{\ell}$ with $\ell\neq i,j$. The last clique on this copy of $P_k^{p+1}$, namely the one containing $u_i$ and $v_i$, intersect $A_{\ell}$ at exactly one vertex, call it $u_{\ell}$. Then this $P_k^{p+1}$ together with the $(p+1)$-clique consisting of one vertex from each $A_q$, $q\neq i,j,\ell$, and $u_{\ell}, x_1,u_j,v_j$, form a $C_{k}^{p+1}$ (see Figure~\ref{path-cyl}(b)), where $x_1,\ldots,x_{k-2},u_i,u_{\ell},x_1$ is the vertices of $C_k$ that was blown up. This yields a contradiction.
\begin{figure}[ht]
\begin{center}
\includegraphics{path-cy}
\end{center}
\caption{When $k=4$: (a) Extend a $P_k$ to a $P_k^{p+1}$; (b) Obtain a $C_{k}^{p+1}$ from $P_{k}^{p+1}$.}
\label{path-cyl}
\end{figure}
\qed

\section{Proof of Theorem~\ref{cli-trees}}\label{blow-up tree}
In this section, unless otherwise specified, $p\ge 3$ and $T$ is a tree with two color classes (partite sets) $A$ and $B$ such that $|A|\le |B|$. Let $a=|A|$, $b=|B|$. Recall that, by Lemma~\ref{key-lem}, $\mathcal{M}(T^{p+1})=\mathcal{H}(T)$. In particular, $T\in \mathcal{M}(T^{p+1})$.

\begin{lemma}\label{T-free}
If $T$ has a leaf in $A$ and $\alpha(T)=b$, then for any $m\ge 1$, $K_{a-1}\bigotimes \overline{K}_m$ is $\mathcal{H}(T)$-free, hence $\mathcal{M}(T^{p+1})$-free.
\end{lemma}

\noindent\textbf{Proof.}
For simplicity, let $G=K_{a-1}\bigotimes \overline{K}_m$ with $V(G)=X\cup Y$, where $X$ is the set of vertices in the $(a-1)$-clique and $Y$ is the remaining independent set. We may assume $|Y|=m\ge b+1$, otherwise $|V(G)|<|V(F)|$ for any $F\in \mathcal{H}(T)$. First notice that $T\not\subseteq G$. Indeed, an embedding of $T$ in $G$ has at least $|V(T)|-(a-1)=b+1$ vertices in $Y$, which contradicts to $\alpha(T)=b$. For contradiction, suppose that some forest $F\in \mathcal{H}(T)$ is in $G$. Recall that $F$ is obtained from splitting vertices in some $U\subseteq V(T)$ to sets of leaves in $F$. For any $v$ in $U$, denote by $L(v)\subseteq V(G)$ the set of leaves in $F$ corresponding to $v$. We shall get a copy of $T$ in $G$ from a copy of $F$ by applying the following operation to every $v\in U$ to undo the vertex split: pick any $v\in U$, look at the corresponding $L(v)$ in $F$. First discard edges in $F$ adjacent to $L(v)$. Then if $L(v)\subseteq Y$, add in $F$ edges from $N_G(L(v))$ to a vertex in $Y$; otherwise add in $F$ edges from $N(L(v))$ to a vertex in $L(v)\cap X$ (see Figure~\ref{figTfree}).
\qed
\medskip
\begin{figure}[ht]
\begin{center}
\includegraphics{figTfree}
\end{center}
\caption{Circled vertices are in $L(v)$. (a): $L(v)\subseteq Y$; (b): $L(v)\cap X\neq \emptyset$.}
\label{figTfree}
\end{figure}

From Lemma~\ref{T-free}, we immediately get the following.

\begin{prop}
$H(n,p,a)$ is $T^{p+1}$-free.
\end{prop}

\noindent\textbf{Proof.}
Since $H(n,p,a)$ is the product of $p-1$ independent sets and one $\mathcal{M}(T^{p+1})$-free graph (obtained from combining the set of $a-1$ dominating vertices with the remaining independent set). This is the lower bound construction in~\eqref{eq:bounds}. Hence $H(n,p,a)$ is $T^{p+1}$-free.
\qed
\medskip

\noindent\textbf{Proof of Theorem~\ref{cli-trees} (i).} Since a matching of size $e(T)$ is in $\mathcal{M}(T^{p+1})$, we can proceed as in the proof of Theorem~\ref{cli-cycle} and define $W,A_i,B_i,C_i$ in the same way. If $|W|\ge a$, then $T\subseteq G[W\cup C_i]$ for any $i$. However $T\in \mathcal{M}(T^{p+1})$, this implies $T^{p+1}\subseteq G$, a contradiction. If $|W|\le a-2$, then
$$e(G)=e(T_{n,p})+\frac{a-2}{p}n+o(n)<e(T_{n,p})+\frac{a-1}{p}n+o(n)=e(H(n,p,a)),$$
a contradiction. Thus $|W|=a-1$. Also we may assume that $W$ is non-empty. Indeed, if $W=\emptyset$, then $a=1$. Since $T$ has a leaf in $A$, it implies $T$ is $P_2$, then $T^{p+1}$ is $K_{p+1}$ and its unique extremal graph is $H(n,p,1)=T_{n,p}$.

It remains to show that $e(G[C_i])=0$ for all $1\le i\le p$. Let $u$ be a leaf of $T$ in $A$, and $v$ be its neighbor in $B$. Let $T'=T-u$ and let $F$ and $F'$ be the forests obtained from splitting $v$ in $T$ and $T'$ respectively. Notice that $F=F'\cup K_2$. Indeed, $v$ has one more neighbor (leaf $u$) in $T$, which becomes a $K_2$ after splitting. Suppose there is an edge $xy$ in $G[C_i]$ for some $i$. Since $u\in A$ and $|W|=a-1$, $T'$ has an embedding in $G[W\cup C_i- \{x,y\}]$ with $v$ in $C_i$. Splitting $v$ in this copy of $T'$ (not using $x$ or $y$), we get a copy of $F'$ in $W\cup C_i-\{x,y\}$. Note that for any $i\le p$, $G[W\cup C_i]$ is $\mathcal{M}(T^{p+1})$-free, since $W\cup C_i$ is completely joined to $A_j$, $\forall j\neq i$. Thus edge $xy$ together with this $F'$ yields a copy of $F$ in $G[W\cup C_i]$. However $F\in \mathcal{H}(T)=\mathcal{M}(T^{p+1})$, a contradiction.
\qed
\section*{Acknowledgments}
The author would like to thank J\'ozsef Balogh for encouragement and valuable comments and remarks. He would also like to thank Roman Glebov for helpful discussions.