TITLE: How to tell which function affect behavior of a function the most?
QUESTION [1 upvotes]: The problem that got me thinking. $\left(\dfrac{\sin x}{x}\right)^2$
The overall pattern of this function is a parabola but it has been pulled down by $1/x$ and it wobbles because of $\sin x$.
So, in general is there any mathematical method/way to determine which function is the most dominate?
so for any $\left(f\left(g\right)\right)^{h}$ how could I tell which function $f,g,h$ will affect the shape of the graph most?

REPLY [1 votes]: Your problem is an ill-posed one.
Note that there are many properties of graphs that you can call "shape" (for example regularity, it is clearly something different than the large scale geometry of the graph). Even if you choose one of the shape properties you have to specify how you measure its changes.
Last but not least: if you pick a function $\psi$ it is very unlikely that it has a unique representation $\psi=(f\circ g)^h$...


TITLE: $p$-nilpotent finite group $G$ is a $p$-normal group?
QUESTION [3 upvotes]: Is it true that a $p$-nilpotent finite group $G$ is necessarily a $p$-normal group?
The definitions are here: p-nilpotent and p-normal (I like the 2nd definition)
Let $p$ be a prime and $P,Q$ be $p$-Sylow subgroups of $G$ such that $Z(Q)\subseteq P$.
We have to show $Z(Q)=Z(P)$. Writing $Q=P^{g}$ we can write this as $Z(P)^g=Z(P)$.
The group $G$ is $p$-nilpotent, so it has a $p$-normal complement by definition. Let $N$ be a $p$-normal complement for $G$, i.e., a normal subgroup $N$ of $G$ such that $G=NP$ and $N\cap P=1$.
So again, we need to show $Z(P)^g=Z(P)$. We could write $g=np$ and this becomes $Z(P)^n=Z(P)$, for the center $Z(P)$ is a normal subgroup of $P$. But I'm not sure what to do now.
Any help? Thank you.

REPLY [3 votes]: Suppose $Q = P^{g}$ is another Sylow $p$-subgroup such that $Z(P) \le Q$. We show that $Z(P) = Z(Q)$.
Note first that we may take $g \in N$.
Let $z \in Z(P)$, and $y \in Q$, so that $y = x^{g}$ for some $x \in P$.
Then
\begin{equation}
[z, y]
=
[z, x^{g}]
=
[z, x [x, g]]=
[z, [x, g]] [z, x]^{[x, g]}
=
[z, [x, g]].
\end{equation}
Now $[z, y] \in Q$, but also $[z, [x, g]] \in N$, as $g \in N\trianglelefteq G$, so $[z, y] = 1$ as $Q \cap N = 1$
This shows that $Z(P) \le Z(Q)$, equality follow from the fact that they have the same order.


TITLE: Limit of the sequence of regular n-gons.
QUESTION [3 upvotes]: Let $A_n$ be the regular $n$-gon inscribed in the unit circle.
It appears intuitively obvious that as $n$ grows, the resulting polygon approximates a circle ever closer.
Can it be shown that the limit as $n \rightarrow \infty $ of $A_n$ is a circle?

REPLY [3 votes]: Suppose you take the $n$-gons $A_n$ to be inscribed in the unit circle $S^1$, so we're not talking about a sequence of $n$-gons that is growing without bound, or oscillating in size, or anything like that. There is a notion of distance between subsets of a metric space called the Hausdorff distance. In this case the Hausdorff distance is defined as
$$d_H(X,Y)=\max \left\{\sup_{x\in X} \; \inf_{y\in Y} \; |x-y|, \sup_{y\in Y} \; \inf_{x\in X} \; |x-y| \right\}$$
where $X$ and $Y$ are two subsets of $\mathbb R^2$. (For a general metric space, replace $|x-y|$ by $d(x,y)$.) Now $A_n$ does indeed limit to $S^1$ in the sense that $d_H(A_n,S^1)\to 0$.


text:
\begin{document}
\begin{frontmatter}

\title{Location of leaks in pipelines using parameter identification tools}

\author[First]{L. Torres}

\address[First]{Instituto de Ingenier\'ia, UNAM, Mexico City, Mexico\\ (ftorreso@iingen.unam.mx).}

\begin{abstract}
This work proposes an approach to locate leaks by identifying the parameters of finite models associated with these
fault events. The identification problem is attacked by using well-known identification methods such as the Prediction Error Method and extended Kalman filters.
In addition, a frequency evaluation is realized to check the conditions for implementing any method which require an excitation condition.
\end{abstract}

\begin{keyword}
Fault detection and isolation, Leak detection and isolation, parameter estimation, hydraulic systems, pipelines.
\end{keyword}

\end{frontmatter}

\section{Introduction}
Water is the most precious resource on earth, reason by which leak detection methods have become issues of primary relevance in modern hydraulic networks.
The main purpose of such methods is to obtain information in time on the leak location, to avoid undesirable consequences - as economical losses, damages to the environment, damages to the population, etc.

Due to its relevance, this problem has thus already been widely considered, and for a long time now (see e.g. the survey of \cite{Babbitt1920}), which led to the development of a wide variety of techniques, from visual
inspection to acoustic methods. But among them, the class of so-called {\em transient-based} approaches has been more particulary studied in the last two decades, motivated by the fact that compared with more conventional methods, they have the advantage of being non-invasive, less expensive, and with a large operational range.

The recent paper of \cite{Colombo2009} presents a pretty well-documented overview on LDI techniques,
distinguishing {\em direct transient} methods, {\em inverse transient} approaches, and {\em frequency-based} analysis: the first ones are designed to give a direct interpretation of signal changes so as to detect
leak effects in them (see e.g. \cite{Brunone1999,Brunone2001,Beck2005,Wang2002}); the second type of approaches refers to the problem of recovering parameters of a time-domain model from a set of actual measurements,
allowing then to compare current measurements with a leak-free situation and monitor leaks in this way (e.g. as in \cite{Digerness1980,Billman1987,Allidina1988,Pudar1992,Liggett1994,Vitkovsky2000,Kapelan2004}), while the third
family of techniques gathers all works related to frequency response analysis with regard to the effect of leaks (cf \cite{Mpesha2001,Ferrante2004,Lee2005a,Lee2005b,Covas2005}).

In fact, when aiming at leak detection using transient information from a model, with only a limited number of measurements,
{\em identification} (or similarly {\em observer} tools - eg as in \cite{Verde2004,Besancon2007b,Torres2011Tunez,DosSantos2011}) can provide a good framework,
typically combining transient signal exploitation with frequency requirements. This is in particular true when considering situations of possible {\em multiple simultaneous leaks} (eg as in  \cite{Verde2005}),
whereas most of the available studies are limited to the case of single leak detection. In addition, various of those mentioned methods require an adequate quantity of sensors along the pipeline.

In the case of a pipe section delimited by a pair of (flow or pressure) sensors at each end, the detectability of multiple simultaneous leaks (with their location) is lost in steady-state, and requires instead
an appropriate excitation (see eg \cite{Verde2003,Verde2004,Torres2011}).

Injecting excitation in the systems allows to recover a frequency response diagram with the additionally required information.
In that way, the identification approach can be related to
studies on frequency response analysis. Classically indeed, the frequency response  describes how the pipeline reacts at various frequencies,
by relating the amplitude and phase of the system input and output at each frequency.
The characteristics of the pipeline can then be extracted by using any frequency sweeping technique, and the unique requirement is that the frequency content of the input signal should be as high as possible such that maximum
information is extracted from the pipeline. An example of a wide bandwidth signal is a single sharp pulse that can be generated
through the fast perturbation of a valve as is suggested by \cite{Lee2008}, or sinusoidal oscillations at various frequencies as is proposed in \cite{Covas2005}, \cite{Sattar2008}.
.

Most of such frequency approaches have in fact been based on some signatures in the frequency response diagram, used to estimate the leak position or magnitude.

There are another interesting methods based on more sophisticated tools as the presented in \cite{Barradas2009} which use Artificial Neural Networks (ANN) to detect and diagnose multiple leaks in a pipeline by recognizing
the pattern of the flow.

The purpose of the present paper is to emphasize how directly handling the leak detection issue as a problem of parameter identification instead, one can  efficiently use the frequency information
provided by the excitation of the system at certain frequencies.
The main advantage of this approach over the other frequency-sweep-based methods is that the estimations of the positions and magnitudes of the leaks are obtained
directly, avoiding the interpretation of signatures or patterns.

Fault detection via parameter identification is in fact a general methodology which relies on the principle that possible faults in a
monitored system are associated with specific parameters and states of the mathematical
model of the system given in the form of an input-output relation. For a better understanding of the concept one can refer to
the books written by \cite{Isermann2011} and \cite{Isermann2011a} for instance.

In a pipeline, leaks can then be seen as fault events associated to certain parameters to be considered in a model, such as the position and magnitude of the leak.
As an option, a finite model can be obtained by solving approximately the Water Hammer equations classically describing the flow dynamics in a pipeline (\cite{Chaudry1979}). Once  the finite model is obtained,
leak equations and their associated parameters can be included in it.

To diagnose the presence of leaks in a pipeline from a point of view parameter identification, an adequate identification approach must be chosen.
There is a large variety of approaches to identify parameters, and for an admittedly review of some of these ones, the reader may consult \cite{Ljung1999} or \cite{Kailath2000}.
In addition, different input signals can be used to excite the system, depending on the method chosen for the estimation, such as sine wave excitation,
multi-tone excitation , random noise excitation, and pseudo-random signals. See for instance \cite{Novak2010,Solomou2004}.

In the present work, to attack the identification problem, it is proposed to use the {\em Prediction Error Method} (PEM) off-line with chirp signals as excitation inputs, as well as Extended Kalman Filters (EKF) based
on the finite nonlinear models. The main reasons for these choices are: the popularity of the methods, their easy implementation and the wide quantity of available software to carry out them.
To implement the approaches, firstly, the pipeline equations are discretized via the finite difference method, then the resulting nonlinear ODE system and their linearized versions
are used to design the algorithms.

The paper is organized as follows: Section 2 is dedicated to the modeling of a pipeline and the deduction of finite models, while Section 3 exposes a frequency analysis of them.
Section 4 describes how the leak location can be carried out by means of parameter identification and using finite models. In section 5, well-known identification algorithms are presented, whereas in
Section 6, these are tested for leak location in simulation. Section 7 finally concludes the paper.

\section{Modeling a pipeline}

Assuming convective changes in velocity to be negligible, constant liquid density and constant pipe cross-sectional area, the
momentum and continuity equations governing the dynamics of the
fluid in a pipeline can be expressed as (\cite{Chaudry1979})
\begin{eqnarray}\label{WH}

\nonumber\frac{\partial Q(z,t)}{\partial t}&+&a_1\frac{\partial H(z,t)}{\partial z}+\mu Q(z,t)|Q(z,t)|=0\\
\frac{\partial H(z,t)}{\partial t}&+&a_2\frac{\partial Q(z,t)}{\partial z}=0
\end{eqnarray}
where $(z,t) \in (0,L)\times(0,\infty)$ are the time ($s$) and space
($m$) coordinates respectively, $L$ is the length of the pipe,
$H(z,t)$ is the pressure head [$m$] and $Q(z,t)$ is the flow rate [$m^3/s$].
The physical parameters of the pipeline are $$a_1=gA_r, \displaystyle a_2=\frac{b^2}{gA_r}, \mu=\displaystyle\frac{\mathfrak{f}}{2\phi A_r},$$
where $b$ is the wave speed in the fluid [$m/s$],
$g$ is the gravitational acceleration [$m/s^2$], $A_r$ is the
cross-sectional area of the pipe [$m^2$], $\phi$ is the inside diameter
of the pipe [$m$], and $\mathfrak{f}$ is the Darcy-Weichbach friction factor.

Closed-form solutions of these equations are not available. However,
several methods have been used to numerically integrate them, such
as the method of characteristics \cite{Chaudry1979}, the finite
difference method \cite{Wylie1978}, the orthogonal collocation method
\cite{Torres2008}, etc.

\subsection{Nonlinear finite models}
The presence of a leak in a given position $z_{f_i}$
must be handled as a boundary condition for the system (\ref{WH}). This
condition is the loss of flow
caused by the leak given by:
\begin{equation}\label{leakstep}
Q_{f_i}(t)=\sigma_{i}\sqrt{H_i(z_{f_i},t)}
\end{equation}
where $\sigma_{i}=\sqrt{2g}A_fC_f>0$, $A_f$ is the sectional area of the
leak, $C_f$ the discharge coefficient.

There are four possible configurations for the finite models; this depending on the Dirichlet boundary conditions
imposed on the flow rates and pressure heads at the ends of the pipeline. For an explanation more detailed see \cite{Torres2011}.

System (\ref{WH}) with included leaks can be discretized in $n_s$ sections as follows:
\begin{equation}\label{Q-modelDifHH}
\dot{Q}_i=\frac{a_1}{\Delta z_i}(H_i-H_{i+1})-\mu Q_i|Q_i|;
\end{equation}
\begin{equation}\label{H-modelDifHH}
\dot{H}_{i+1}=\frac{a_2}{\Delta z_{i}}(Q_{i}-Q_{i+1}-\sigma_{i}\sqrt{H_{i+1}});
\end{equation}
with $i=1,\ldots,n_s$.

If the upstream and downstream pressure heads of the pipeline ($H_{in}$, $H_{out}$)
are considered as the boundary conditions (BC), then $H_1=H_{in}$, $H_{n_s+1}=H_{out}$. The natural frequency of the pipeline under this
configuration is given in \cite{Chaudry1979} and expressed as:
\begin{equation}\label{FnaturalHH}
\omega_{th}=\frac{\pi b}{L},
\end{equation}

If the upstream pressure head and the downstream flow of the pipeline ($H_{in}$, $Q_{out}$)
are the BC, then $H_1=H_{in}$ and $Q_{n_s+1}=Q_{out}$.
The natural frequency for this boundary configuration is given for instance in \cite{Zecchin2010}
and expressed as:
\begin{equation}\label{FnaturalHQ}
\omega_{th}=\frac{\pi b}{2L}.
\end{equation}

Considering that only two measurements at both ends of the pipeline are available (pressures or flow rates),
the output vector is given by:
$$y=\left[
\begin{array}{ccc}
1&\ldots&0\\
0&\ldots&1\\
\end{array}
\right]x=Cx$$
where $C$ has the appropriate dimensions.

It has been shown in \cite{Verde2007}
that equations (\ref{Q-modelDifHH})-(\ref{H-modelDifHH})
are useful to conceive algorithms for single leak detection.
\subsection{Linear finite model}
By linearizing Eq. (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) around the equilibrium points $(\bar{Q}_i,\bar{H}_{i})$,
it is obtained the linear model given by Eq. (\ref{SistemaLineal}) corresponding to the pipeline with $(H_{in},Q_{out})$ as BC.
\begin{figure*}[t]
\begin{equation}\label{SistemaLineal}
\small
\underbrace{\left[\begin{array}{c}
\dot{\tilde{Q}}_1\\
\dot{\tilde{H}}_2\\
\dot{\tilde{Q}}_i\\
\dot{\tilde{H}}_{i+1}\\
\vdots\\
\dot{\tilde{Q}}_{n_s}\\
\dot{\tilde{H}}_{n_s+1}
\end{array}
\right]}_{\dot{x}^{*}}=\underbrace{\left[
\begin{array}{cccccccc}
-2\mu\bar{Q}_1&-\displaystyle\frac{a_1}{\Delta z_1}&\ldots&\ldots& \ldots&\ldots&0&0\\
\displaystyle\frac{a_2}{\Delta z_1}&-\displaystyle\frac{a_2\sigma_1}{2\Delta z_1\sqrt{\bar{H}_2}}&-\displaystyle\frac{a_2}{\Delta z_1}&\ldots&\ldots&\ldots&0&0\\
0&\displaystyle\frac{a_1}{\Delta z_i}&-2\mu \bar{Q}_i&-\displaystyle\frac{a_1}{\Delta z_i}&\ldots&\ldots&0&0\\
0&0&\displaystyle\frac{a_2}{\Delta z_i}&-\displaystyle\frac{a_2\sigma_{i}}{2\Delta z_i\sqrt{\bar{H}_{i+1}}}&-\displaystyle\frac{a_2}{\Delta z_i}&\ldots&0&0\\
&&&\ddots&\ddots&\ddots&0&0\\
0&&\ldots&&&\displaystyle\frac{a_1}{\Delta z_{n_s}}&-2\mu\bar{Q}_n&-\displaystyle\frac{a_1}{\Delta z_{n_s}}\\
0&&\ldots&&&&\frac{a_2}{\Delta z_n}&0\\
\end{array}
\right]}_{A^{*}}\underbrace{\left[
\begin{array}{c}
\tilde{Q}_1\\
\tilde{H}_2\\
\tilde{Q}_i\\
\tilde{H}_{i+1}\\
\vdots\\
\tilde{Q}_{n_s}\\
\tilde{H}_{n_s+1}\\
\end{array}
\right]}_{x^{*}}
+\underbrace{\left[
\begin{array}{cc}
\displaystyle\frac{a_1}{\Delta z_1}&0\\
0&0\\
0&0\\
0&0\\
\vdots&\vdots\\
\vdots&\vdots\\
0&-\displaystyle\frac{a_2}{\Delta z_{n_s}}\\
\end{array}
\right]}_{B^{*}}\underbrace{\left[
\begin{array}{c}
H_{in}\\
Q_{out}\\
\end{array}
\right]}_{u^{*}}
\end{equation}
\end{figure*}
When the BC are $(H_{in},H_{out})$, the last state (a pressure) of model given by Eq. (\ref{SistemaLineal}) must be eliminated.

\section{Frequency analysis of the pipeline with leaks}
In this section, we present a frequency analysis of the
pipeline models previously given. The aim is to
highlight some important aspects to be considered
for leak detection when parameter identification methods are employed.

For the analysis, the physical parameters listed in Table \ref{tab:res} are used, corresponding to a pipeline available at CINVESTAV.
For more details about the configuration see \cite{Begovich2009}.
\begin{table}[htb]
\caption{Test-bed parameters} \label{tab:res}
\begin{center}
\begin{tabular}{|c||c||c||c||c|}
\hline
$g$&$L$&$b$&$\phi$&$\mathfrak{f}$\\ \hline \hline
9.81& 87& 376& 0.0654&0.0181076 \\ \hline
[$m/s^2$]&[$m$]&[$m/s$]&[$m$]&-\\ \hline
\end{tabular}
\end{center}
\end{table}
This pipeline has a pump at the upstream and a valve at the downstream, both devices are able to generate frequencies
in the interval $\omega=[0-6.28]$ $[rad/s]$. Changes in the upstream pressure can be obtained by varying the
working frequency of a pump installed at the upstream. Changes in the outlet flow can be generated through perturbations of the valve.

A relevant issue to analyze in the finite models is its frequency behavior
as function of the spatial discretization.
Fig. \ref{FrequencyVsSpace} and Fig. \ref{FrequencyVsSpacePHASE} expose the frequency behavior (magnitude and phase) of the nonlinear model given by Eq. (\ref{Q-modelDifHH})-(\ref{H-modelDifHH})
discretized into different $n_s$ sections. The frequency diagram was obtained using the physical parameters listed in Table \ref{tab:res} and the pressure head inputs:
\begin{equation}\label{chirp}
H_{in}=15+\sin\left(\omega_0+\pi kt\right)t\;[m],\;H_{out}=7.6\;[m]
\end{equation}
with $\omega_0=0$ as the start frequency and $k=0.0001$ as the rate of frequency increase.
The window of time has been fixed $T_w=10000$ $[s]$, such that the higher frequency of the signal has been $\omega=6.28$ $[rad/s]$.
For this boundary configuration, the natural frequency is $\omega_{th}=13.5774$ $[rad/s]$.
Due to the configuration of the pipeline treated here, changes in the pressure affect the behavior of the flow.

There are two significant aspects to remark from this figure, firstly, the existence of resonant peaks at frequencies which are multiples of the natural
frequency. Secondly, a better representation of these peaks with a higher quantity of sections,

which is indeed important to represent accurately the real behavior of a pipeline in the frequency domain.
Hence, if we want to use a finite model at certain frequencies for any task of fault detection, we have to use a model with the enough quantity of sections. On the contrary, if the
work frequencies are low, then a model with many sections is not needed.
\begin{figure}[htb]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{FrequencyVsSpace.eps}}
\par} \caption{Frequency response as function of the spatial discretization}\label{FrequencyVsSpace}
\end{figure}

\begin{figure}[htb]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{FrequencyVsSpacePHASE.eps}}
\par} \caption{Frequency response as function of the spatial discretization}\label{FrequencyVsSpacePHASE}
\end{figure}

Fig. \ref{WithLeaks} and Fig. \ref{WithLeaksPHASE} illustrate a comparison between the frequency behavior of the normal-operation pipeline
and the frequency behavior of the pipeline affected by one and two leaks. To obtain these plots, the nonlinear model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) with 22 sections was excited only via pressure
using the pressures (\ref{chirp}). The compared data are the magnitude and phase of the relation $Q_{out}/H_{in}$.
In case of the presence of leaks, the resonant peaks are diminished and the phase is altered. This fact is very significant because is the evidence of a special frequency behavior due to the presence of leaks.
Behavior required  in identifications tasks.

\begin{figure}[htb]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{WithLeaks.eps}}
\par} \caption{Frequency response as function of the spatial discretization}\label{WithLeaks}
\end{figure}

\begin{figure}[htb]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{WithLeaksPHASE.eps}}
\par} \caption{Frequency response as function of the spatial discretization}\label{WithLeaksPHASE}
\end{figure}

\section{Leak location}
Hereafter, we present how the nonlinear and linear models previously presented can be handled for leak location
by means of parameter identification.
Note that, the smallest detectable leak for this methodology and other ones depends on the residual generated by the inlet and outlet flows, \emph{i.e} $r_1=Q_{in}-Q_{out}$.
When this residual exceed a threshold, a leak is detectable. To impose a threshold, the precision of the instruments and noise must be considered.
In the work \cite{Torres2013IMTA} diverse residuals to detect a leak and faults in sensors and actuators are studied.

\subsection{Single leak location}
When a leak happens, a discontinuity in the mass flow rate occurs, then the pipeline can be seen as partitioned in two sections (see Fig. \ref{UneFuite}). Reflecting on this point, the models to be used for the conception of location algorithms must represent at least two sections of the pipeline, reason by which the nonlinear model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) and the linear model (\ref{SistemaLineal}) must be set with $n_s\geq2$.

\subsubsection{Nonlinear model}
In order to use a nonlinear model for the location of a leak trough the parameters linked with the leak event, let us consider
that the inputs are the pressures at the ends of the pipeline, \emph{i.e.}, $u=[H_{in},H_{out}]$, the end flow rates as the outputs, \emph{i.e.},
$y=[Q_{in},Q_{out}]=[Q_{1},Q_{2}]$ and the fluid model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) with $n_s\geq2$, \emph{i.e.},
\begin{eqnarray}\label{NonlinearOneLeak}
\nonumber\dot Q_{1}&=&-\mu|Q_{1}|Q_{1}+\frac{a_1}{\Delta z_1}(H_{in}-H_{2})\\
\nonumber\dot H_{2}&=&\frac{a_2}{\Delta z_{1}}(Q_{1}-Q_{2}-\sigma_{1}\sqrt{H_{2}})\\
\dot Q_{2}&=&-\mu|Q_{2}|Q_{2}+\frac{a_1}{L-\Delta z_1}(H_{2}-H_{out})\\
\nonumber\dot \Delta z_1&=&0\\
\nonumber\dot \sigma_{1}&=&0
\end{eqnarray}
where the added states $\Delta z_1$ and $\sigma_1$ represent the leak position ($z_{f_1}$) and its coefficient, while $H_2$ is the pressure at leak point ($H_{f_1}$). Notice that
the second section of the model is given by $\Delta z_2=L-\Delta z_1$. Therefore, by identifying only the parameters which extend the
state vector, one can locate the position of the leak and its magnitude.

\subsubsection{Linear model}
In order to obtain an adequate linear model for a single leak detection, let us consider the following points:
\begin{itemize}
\item If $n_s=2$ is chosen for the system (\ref{SistemaLineal}), the state vector of the resulting two-sections system is given by $$x^1=[x_1,x_2,x_3]=[\tilde{Q}_1, \tilde{H}_2, \tilde{Q}_2].$$
with equilibrium points
$$\bar{x}^1=[\bar{x}_1,\bar{x}_2,\bar{x}_3]=[\bar{Q}_1, \bar{H}_2, \bar{Q}_2].$$
\item Considering as BC the pressure heads at the pipeline ends, $u^1=[H_{in},H_{out}]$ is the input vector of the system, while $y^1=[Q_{in},Q_{out}]$ is the output vector.
\item The position of the leak, $z_{f_1}$, is given by the size of the first section i.e. $z_{f_1}=\Delta z_1$.
\item The parameter vector $\theta$ to be estimated must be defined on basis of the required leak information. Then, $\theta$ have been set with
$$\theta_1=\displaystyle\frac{1}{\Delta z_1}, \displaystyle\theta_2=\frac{\sigma_1}{\sqrt{\bar{x}_2}}.$$
\end{itemize}
Finally, the required model for leak detection is given by the equations system (\ref{LinearModelAlphas}) with a second section expressed as $\Delta z_2=L-\theta_1^{-1}=\gamma(\theta_1)$.

\begin{equation}\label{LinearModelAlphas}
\small
\dot{x}^1=\left[
\begin{array}{ccc}
-2\mu\bar{x}_1&-a_1\theta_1&0\\
a_2\theta_1&-\frac{a_2\theta_1\theta_2}{2}&-a_2\theta_1\\
0&\frac{a_1}{\gamma(\theta_1)}&-2\mu\bar{x}_3\\
\end{array}
\right]x^1
+\left[\begin{array}{cc}
a_1\theta_1& 0\\
0&0\\
0&-\frac{a_1}{\gamma(\theta_1)}\\
\end{array}
\right]u^1
\end{equation}

It is so important to note that the change in the operation point of the pressure ($\bar{x}_2$)
is included in the estimation of $\theta_2$. This can be made because one is interested to get the position and the loss of flow function of $\theta_2$, instead of the leak
coefficient $\sigma_1$ and pressure at the leak position $\bar{x}_2$.
\begin{figure}[htb]
{\par\centering
\resizebox*{9cm}{!}{\includegraphics{Fuites.eps}}
\par} \caption{Partition of the pipeline because of leak presence}\label{UneFuite}
\end{figure}

\subsection{Two-leaks location}
Because of the two discontinuities caused in a pipeline by the presence of two simultaneous leaks, models representing three sections must be used for the location purpose (see Fig. \ref{UneFuite}). Thus, $n_s\geq3$ for the nonlinear system (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) and the linear system (\ref{SistemaLineal}).

\subsubsection{Nonlinear model}
In order to use a nonlinear model for the location of a leak trough the parameters linked with the leak event, let us consider
that the inputs are the pressures at the ends of the pipeline, \emph{i.e.}, $u=[H_{in},H_{out}]$, the end flow rates as the outputs, \emph{i.e.},
$y=[Q_{in},Q_{out}]=[Q_{1},Q_{3}]$ and the fluid model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) with $n_s\geq3$, \emph{i.e.},
\begin{eqnarray}\label{NonlinearTwoLeaks}
\nonumber\dot Q_{1}&=&-\mu|Q_{1}|Q_{1}+\frac{a_1}{\Delta z_1}(H_{in}-H_{2})\\
\nonumber\dot H_{2}&=&\frac{a_2}{\Delta z_{1}}(Q_{1}-Q_{2}-\sigma_{1}\sqrt{H_{2}})\\
\dot Q_{2}&=&-\mu|Q_{2}|Q_{2}+\frac{a_1}{\Delta z_2}(H_{2}-H_{3})\\
\nonumber\dot H_{3}&=&\frac{a_2}{\Delta z_{2}}(Q_{2}-Q_{3}-\sigma_{2}\sqrt{H_{3}})\\
\nonumber\dot Q_{3}&=&-\mu|Q_{3}|Q_{3}+\frac{a_1}{L-\Delta z_1-\Delta z_2}(H_{3}-H_{out})\\
\nonumber\dot \Delta z_1&=&0\;\;\dot\sigma_{1}=0\;\;\dot \Delta z_2=0\;\;\dot \sigma_{2}=0
\end{eqnarray}
where the joint states $\Delta z_1$, $\Delta z_2$, $\sigma_1$ and $\sigma_2$ represent the position of both leaks ($z_{f_1}$, $z_{f_2}$) and their coefficients respectively, whereas $H_2$ and $H_3$ are the pressures at the leak points ($H_{f_1}$,$H_{f_2}$). Notice that
the third section of the model is given by $\Delta z_3=L-\Delta z_1-\Delta z_2$. Therefore, by identifying only the parameters which extend the
state vector, one can locate the both leak positions and their magnitudes.

\subsubsection{Linear model}
Let us take into account the following considerations to obtain a suitable model for the detection of two simultaneous leaks:
\begin{itemize}
\item If $n_s=3$ for the system (\ref{SistemaLineal}), the state vector of the resulting three-sections system is given by $$x^2=[x_1,x_2,x_3,x_4,x_5,x_6]=[\tilde{Q}_1, \tilde{H}_2, \tilde{Q}_2, \tilde{H}_3, \tilde{Q}_3, \tilde{H}_4].$$
and the vector of equilibrium points is expressed by
$$\bar{x}^2=[\bar{x}_1,\bar{x}_2,\bar{x}_3,\bar{x}_4,\bar{x}_5,\bar{x}_6]=[\bar{Q}_1, \bar{H}_2, \bar{Q}_2, \bar{H}_3, \bar{Q}_3,\bar{H}_4].$$
\item Considering as boundary conditions, the input vector is $H_{in},Q_{out}$ $u^2=[H_{in},Q_{out}]$, while $y^2=[Q_{in},H_{out}]$ is the output vector.
\item The position of the first leak, $z_{f_1}$, is given by the size of the first section i.e. $z_{f_1}=\Delta z_1$, whereas the position
of the second leak, $z_{f_2}$, is given by the size of the first section plus the second section i.e. $z_{f_1}=\Delta z_1+\Delta z_2$.
\item The parameter vector $\theta$ to be estimated have been fixed with the components:
$$\theta_1=\displaystyle\frac{1}{\Delta z_1}, \displaystyle\theta_2=\frac{\sigma_1}{\sqrt{\bar{x}_2}},\displaystyle\theta_3=\frac{1}{\Delta z_2},\theta_4=\bar{x}_3,\displaystyle\theta_5=\frac{\sigma_2}{\sqrt{\bar{x}_4}}.$$

\end{itemize}
In this case, similarly to the single leak estimation, one is interested in the loss of flows which are functions of $\theta_2,\theta_5$ respectively, instead of the four independent parameters.

Finalizing, a suitable model for simultaneous-leaks detection is given by the system (\ref{Lineal2Fugas}) with a third section given by $\Delta z_3=L-\theta_1^{-1}-\theta_3^{-1}=\alpha(\theta_1,\theta_3)$.
This model can be useful for the detection of sequential leaks by assuming $\theta_1$ and $\theta_2$ as known parameters.

\begin{figure*}[hbtp]
\begin{eqnarray}\label{Lineal2Fugas}
\small
\dot{x}^2&=&
\left[\begin{array}{cccccc}
-2\mu \bar{x}_1&-a_1\theta_1&0&0&0&0\\
a_2\theta_1&-\frac{1}{2}a_2\theta_1\theta_2&-a_2\theta_1&0&0&0\\
0&a_1\theta_3&-2\mu\theta_4&-a_1\theta_3&0&0\\
0&0&a_2\theta_3&-\frac{1}{2}a_2\theta_3\theta_5&-a_2\theta_3&0\\
0&0&0&\frac{a_1}{\alpha(\theta_1,\theta_3)}&-2\mu \bar{x}_5&-\frac{a_1}{\alpha(\theta_1,\theta_3)}\\
0&0&0&0&\frac{a_2}{\alpha(\theta_1,\theta_3)}&0\\
\end{array}
\right]x^2
+\left[
\begin{array}{cc}
a_1\theta_1&0\\
0&0\\
0&0\\
0&0\\
0&0\\
0&-\frac{a_2}{\alpha(\theta_1,\theta_3)}\\
\end{array}
\right]u^2
\end{eqnarray}
\end{figure*}

\section{Identification methods}
Following, two of the most popular methods of identification used in this work are briefly described.
\subsection{Prediction Error Method}
Consider an innovation representation of a continuous-time LTI system of the form
\begin{eqnarray}\label{LTISystem}

\nonumber\dot{x}(t)&=&A(\theta)x(t)+B(\theta)u(t)\\
y(t)&=&C(\theta)x(t)+D(\theta)u(t)
\end{eqnarray}
where $y\in\mathfrak{R}^p$ is the output vector, $u\in\mathfrak{R}^m$ the input vector, $x\in\mathfrak{R}^n$ the state vector and (A,B,C,D) are matrices of appropriate dimensions. The unknown parameters in the
state space model are contained in these matrices.

Consider the application of the Prediction Error Method (PEM) to the multi-input multi-output (MIMO) model (\ref{LTISystem}). The prediction error $e(t,\theta)$ is computed by a linear state space model with inputs
$u(t)$, $y(t)$ of the form
\begin{eqnarray}\label{LTIError}

\nonumber\hat{\dot{x}}(t,\theta)&=&[A(\theta)-K(\theta)C(\theta)]\hat{x}(t,\theta)+B(\theta)u(t)+K(\theta)y(t)\\
e(t,\theta)&=&-C(\theta)\hat{x}(t,\theta)-D(\theta)u(t)+y(t)
\end{eqnarray}
with the initial condition $\hat{x}(0,\theta)=0$. Then, in terms of $e(t,\theta)$, the performance index is given by

$$\displaystyle V_N(\theta)=\int_0^T\|e(t,\theta)\|^2dt,\quad T>0$$
Thus the parameter vector is obtained by minimizing $V_N(\theta)$ with respect to $\theta$.
$$\hat\theta=\texttt{arg}\min V_N(\theta)$$
If we can evaluate the gradient $\partial V_N/\partial\theta$, we can in principle compute a (local) minimum of the criterion
$V_N(\theta)$ by utilizing a (conjugate) gradient method.

In this work, this methodology has been applied off-line. For a more detailed explanation of the method, the reader can be consult \cite{Katayama2005}.
\subsection{Extended Kalman Filter}
An extended model, such as (\ref{NonlinearOneLeak}) and (\ref{NonlinearTwoLeaks}), can be represented by the following state
representation:

\begin{equation}\label{system}
\begin{split}
\dot{{x}}(t)&=f({x}(t),{u}(t))\\
{y}(t)&=h({x}(t))
\end{split}
\end{equation}
then an observer can be designed as follows (\cite{Reif1998}):
\begin{equation}\label{Observer}
\dot{\hat{{x}}}(t)=f(\hat{{x}}(t),{u}(t))+{K}(t)[{y}(t)-h(\hat{{x}}(t))]\\
\end{equation}
where the state estimate is denoted by $\hat{{x}}(t)$ and the
observer gain ${K}(t)$ is a time-varying $q  \times m$ matrix
computed as
\begin{equation}\label{Ganancia}
{K}(t)={P}(t){C}^\mathrm{T}(t){R}^{-1}
\end{equation}
where
\begin{equation}\label{Ricatti}
\begin{split}
\dot{{P}}(t)&=({A}(t)+\alpha
{I}){P}(t)+{P}(t)({A}^\mathrm{T}(t)+\alpha
{I})\\&-{P}(t){C}^\mathrm{T}(t){R}^{-1}{C}(t){P}(t)+{W}
\end{split}
\end{equation}
with
\begin{equation*}\label{Jacobianos}
{A}(t)=\left.\frac{\partial f(\hat{x}(t),u(t))}{\partial x(t)}\right|_{x=\hat x},\\
{C}(t)=\left.\frac{\partial h(\hat{x}(t))}{\partial x(t)}\right|_{x=\hat x}
\end{equation*}
\begin{equation*}
{P}(0)={P}(0)^\mathrm{T}>{0}, {W}={W}^\mathrm{T} \geq {0}, {R}={R}^\mathrm{T}>{0}\\
\end{equation*}
and a positive real number $\alpha >0$.

\section{Identification tests}
In order to show the feasibility of the approach proposed in this article, some results
concerning the location of leaks using the PEM and EKF's are presented in the following.

To locate one leak an extended Kalman filter (\ref{Observer}) was conceived, and for its design the model (\ref{NonlinearOneLeak}) represented by the general form (\ref{system}) was considered.

In Figure \ref{EstimacionMediciones}, the measured outputs and their estimations performed by the filter are exposed.
Whereas in Fig. \ref{Posicion} is presented the estimation and the real position. The tuning parameter of the filter was fixed $\alpha=0.3$ and this was initialized with different
initial conditions with respect to the system.

\begin{figure}[hhh]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{EstimacionMediciones.eps}}
\par} \caption{Leak location using an Extended Kalman Filter}\label{EstimacionMediciones}
\end{figure}

\begin{figure}[hhh]
{\par
\hskip-0.4cm
\resizebox*{10cm}{!}{\includegraphics{Posicion.eps}}
\par} \caption{Leak location using an Extended Kalman Filter}\label{Posicion}
\end{figure}

Now, we give some results corresponding to the detection and isolation of two simultaneous leaks.
The leaks were generated simultaneously at $z_{f_1}=39.15$ [$m$] and at $z_{f_2}=65.25$ [$m$] with coefficients
$\sigma_1=0.4\times10^{-3}$ [$m^2$] and $\sigma_2=0.2\times10^{-3}$ [$m^2$] respectively. Then the parameter vector to be estimated was
$${\theta}=[0.0255,0.1113\times 10^{-3},0.0383,0.0097,0.0637\times 10^{-3}]$$
The pipeline affected by the leaks was represented by the nonlinear model with twenty sections and it was excited with
\begin{equation}\label{chirp2}
H_{in}=19+0.4\sin\left(\omega_0+\pi kt\right)t\;[m]
\end{equation}
and the downstream flow rate
\begin{equation}\label{chirp2}
Q_{out}=9.08\times 10^{-3}+0.1\times 10^{-3}\sin\left(\omega_0+\pi kt\right)t\;[m^3/s]
\end{equation}
where $\omega_0=0$ and $k=0.0001$. The window of time was fixed $T_w=20000$ $(s)$.
The natural frequency in this case is given by $\omega_{th}=6.788$ $(rad/s)$ calculated from Eq.(\ref{FnaturalHQ}).
For the choice of these signals have been considered:
(a) the amplitude being enough small to keep the validity of the linear models, (b) the performance of the actuators installed in the pipeline for the generation of the signals,
(c) the use of a chirp signal because of their advantages in estimation algorithms w.r.t. noise (see \cite{Novak2010}) and (d) the sample time used to carry out the PEM,
which in this test simulation has been chosen $T=0.01$ $(s)$.

The parameter vector was initialized as
$$\hat{\theta}(0)=[0.02,0.25298\times 10^{-3},0.05,0.01119,0.18898\times 10^{-3}]$$

The vector estimated by the PEM was:
$$\hat{\theta}=[0.0234,0.2016\times10^{-3},0.0356,0.01665,0.0391\times 10^{-6}]$$

From these estimations, the estimated positions were $\hat{z}_{f_1}= 43.87$ $[m]$ and $\hat{z}_{f_2}=70.21$ $[m]$.

To conclude this section, it is necessary to highlight the performance of the Extended Kalman Filter designed for the single leak location, which works
very well even in low frequencies and varied initial conditions. This, because it was designed with a nonlinear model and the parameters to identify were only two.
On the contrary, the PEM algorithm designed for the location of two leaks was sensitive to the initial conditions and shown problems concerning to the identification region.
This fact is due to the low frequencies used for the parameter identification, the small dimension of the model and the high quantity of parameters
to identify.  Therefore, some proofs must be carried out at high frequencies and using high dimensional models.

\section{Conclusion}
Here, we have proposed an approach based on the identification of parameters and operation changes related with leaks.

To put into practice the identification tasks, it has been essential to excite the system with a persistent input. Since the entire frequency behavior of a pipeline can only be modeled by complex models
(see \cite{Matko2000}), a frequency evaluation of approximated solutions of the fluid pipeline equations has been done in order to verify the validity
of the proposed identification method. From this, it has been shown that simple models can be used to identify the leak parameters, but only at low frequencies.
If higher frequencies are required, then more complex models must be used.

config: arxiv


TITLE: How do I correctly solve $ \sqrt { x - 6 } - \sqrt { 10 - x } \geq 1 $ ?
QUESTION [4 upvotes]: $ \sqrt { x - 6 } - \sqrt { 10 - x } \geq 1 $
My solving :
$x$ $\in$ $ [ 6 , 10 ] $ for both the expressions under square root to be valid .
Now
$$ \sqrt {x-6} > \sqrt { 10 - x } $$ since their diff. is positive.
Which means x belongs to [ 8 , 10 ] .
Now
$$ x - 6 + 10 - x -2 \sqrt { -x^2 + 16x -60 } \geq 1 $$
$$ \implies 4x^2 - 64x + 249 \geq 0 $$
$$ \implies x \in [{{16 + \sqrt 7 }\over 2 } , 10 ] $$
But the answer is
$$ [{{16 + \sqrt 7 }\over 2} , 0 ] $$
Who is wrong , me or the book ?

REPLY [1 votes]: Another proof that you are correct and that the book is wrong.
Consider the function $$f(x)=\sqrt { x - 6 } - \sqrt { 10 - x }-1$$ which is defined for $6\leq x \leq 10$. Its first derivative being $$f'(x)=\frac{1}{2 \sqrt{x-6}}+\frac{1}{2 \sqrt{10-x}}$$ it is always positive in the interval  .
So, $f(x)$ is increasing and has only one root in the interval (call it $x_*$). For any $x > x_*$ belonging to the interval, the inequality will be satisfied.
You properly found the value of the root.


TITLE: Numerically equivalent set differences
QUESTION [1 upvotes]: I am studying for an exam, one of the practice questions is as follows

Let $S$ and $T$ be two sets. Prove that if $|S - T| = |T - S|$, then $|T| = |S|$.

The given answer shows that since a bijection exists between $|S-T|$ and $|T-S|$, we prove a bijection exists between $|T|$ and $|S|$ and therefore QED.
Is this really necessary though? Cant I just say

Let $V = S \cap T$, therefore
  $S-T = S-V$, $T-S = T-V$, let $w = |V|$, it follows that $|S-T| = |S-V| = |S| - w$,
      so on for $|T-S|$ and subtract $w$ from both sides and QED

This seems too simple, where am I making a mistake?

REPLY [1 votes]: It is too simple, and wrong. If you want to use cardinal arithmetic in a proof then you need to read up on it and understand it.
You assert that |S - V| = |S| - |V|.
For infinite sets subtraction of cardinalities is genrally not defined. You can see why with the following example....
Consider Z the set of integers and N the set of positive integers.
They have the same cardinality, i.e. |Z| = |N|, but |Z - N| is the set of non-positive integers and its cardinality is the same as N (and Z), so we have |Z - N| = |N| (and  = |Z|). On the other hand N - Z = {} and |N - Z| = 0.


TITLE: Cantor normal form
QUESTION [3 upvotes]: Every ordinal number $α$ can be uniquely written as ${\displaystyle \omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}}$, where $k$ is a natural number, ${\displaystyle c_{1},c_{2},\ldots ,c_{k}}$ are positive integers, and ${\displaystyle \beta _{1}>\beta _{2}>\ldots >\beta _{k}\geq 0}$ are ordinal numbers. This decomposition of $α$ is called the Cantor normal form of $α$, and can be considered the base-$ω$ positional numeral system. The highest exponent ${\displaystyle \beta _{1}}$ is called the degree of ${\displaystyle \alpha }$ , and satisfies ${\displaystyle \beta _{1}\leq \alpha }$ . The equality ${\displaystyle \beta _{1}=\alpha }$  applies if and only if ${\displaystyle \alpha =\omega ^{\alpha }}$. In that case Cantor normal form does not express the ordinal in terms of smaller ones; this can happen as explained below.
A minor variation of Cantor normal form, which is usually slightly easier to work with, is to set all the numbers $c_i$ equal to 1 and allow the exponents to be equal. In other words, every ordinal number $α$ can be uniquely written as ${\displaystyle \omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k}}}$, where k is a natural number, and ${\displaystyle \beta _{1}\geq \beta _{2}\geq \ldots \geq \beta _{k}\geq 0}$ are ordinal numbers.
My question is how to calculate the Cantor normal form of the ordinal $α^α$ where $α$ is the ordinal $(ω^{ω^{2}} + 7)ω^{ω^{3}}ω + ω + ω4$.
Is it possible to use theorem in the following link?
https://proofwiki.org/wiki/Ordinal_Exponentiation_via_Cantor_Normal_Form/Limit_Exponents
Thank you for your time and help.

REPLY [1 votes]: This is not a complete answer yet.

First let's consider the ordinal:
$(\omega^{\omega^{2}} + 7)\omega^{\omega^{3}}\omega + \omega + \omega 4$. The first thing we can note is that this expression is well-defined because addition and multiplication (of ordinals) is associative. First, let us simply this expression in various steps.
(1) $(\omega^{\omega^{2}} + 7)\omega^{\omega^{3}} \cdot \omega + \omega + \omega \cdot 4$
(2) $(\omega^{\omega^{2}} + 7)\omega^{\omega^{3}} \cdot \omega^1 + (\omega + \omega \cdot 4)$
(3) $(\omega^{\omega^{2}} + 7)\omega^{\omega^{3}+1} + \omega \cdot 5$
(4) $(\omega^{\omega^{2}})\omega^{\omega^{3}+1} + \omega \cdot 5$
The reason for (3) to (4) is that if $l$ is a limit ordinal then $(\alpha+7) \cdot l=\alpha \cdot l$ (for any arbitrary $\alpha \geq 1$).
(5) $\omega^{\omega^{2}+(\omega^{3}+1)}+ \omega \cdot 5$
(6) $\omega^{\omega^{3}+1}+ \omega \cdot 5$
The reason for (5) to (6) is that $\omega^{2}+(\omega^{3}+1)=(\omega^{2}+\omega^{3})+1=\omega^3+1$
So essentially we want $m^m$ where $m=\omega^{\omega^{3}+1}+ \omega \cdot 5$.

Edit1: If what is written below is correct (I need to check the details though), then it should take one pretty close to the answer. In the next edit I will try to complete it.
So we define $m_0=\omega^{\omega^{3}}$ and $m_1=\omega^{\omega^{3}+1}$. Let's first try to calculate ${m_0}^{m_0}$. I think we can show that for any arbitrary $\alpha \geq 1$, we should have: ${m_0}^\alpha={\omega}^{\omega^3 \cdot \alpha}$. If we add the additional condition that $\alpha=\omega^\omega \cdot n$ (for some ordinal $n \geq 1$), then we have $\omega^3 \cdot \alpha =\alpha$. However, $\omega^{\omega^{3}}=m_0$ satisfies the condition in last sentence. Hence $\omega^3 \cdot m_0 =m_0$.
Due to last paragraph, we can write ${m_0}^{m_0}={\omega}^{\omega^3 \cdot m_0}=\omega^{m_0}=\omega^{(\omega^{\omega^3})}=\omega^{\omega^{\omega^3}}$. As an aside we see that $m_0^{(\omega^\omega)}={\omega}^{(\omega^3 \cdot {\omega^\omega})}={\omega}^{({\omega^\omega})}=\omega^{\omega^\omega}$. This is not too different from $(\omega^\omega)^{(\omega^\omega)}=\omega^{\omega^\omega}$.
Now let's come to calculating ${m_1}^{m_0}$. I think we can show that for any arbitrary $\alpha \geq 1$, we should have: ${m_0}^\alpha={\omega}^{(\omega^3+1) \cdot \alpha}$. If we add the additional condition that $\alpha=\omega^\omega \cdot n$ (for some ordinal $n \geq 1$), then we have $(\omega^3+1) \cdot \alpha =\alpha$. However, $\omega^{\omega^{3}}=m_0$ satisfies the condition in last sentence. Hence $(\omega^3+1) \cdot m_0 =m_0$.
Due to the last paragraph we get ${m_1}^{m_0}={\omega}^{(\omega^3+1) \cdot m_0}=\omega^{m_0}=\omega^{(\omega^{\omega^3})}=\omega^{\omega^{\omega^3}}$.

Now let's focus our attention $m^{m_0}$ where $m=\omega^{\omega^{3}+1}+ \omega \cdot 5$. It seems to me that there might be an easier way to deduce it based on something like this. Define $m_2=\omega^{\omega^{3}+2}$. Now we should have $m<m_2$.
So we have $m_1<m<m_2$. Hence we must have $m_1^{m_0} \leq m^{m_0} \leq m_2^{m_0}$. But it seems like ${m_2}^{m_0}=\omega^{\omega^{\omega^3}}$ based on reasoning similar to ${m_1}^{m_0}=\omega^{\omega^{\omega^3}}$. The inequality mentioned above seems to force us to conclude that $m^{m_0}=\omega^{\omega^{ \omega^3}}$.

If we have an expression for $m^{m_0}$ then it seems that getting $m^m$ from there shouldn't be too difficult.
(To be completed)


TITLE: Show that $X = \{ \text{The set of all series which converge to } a \in [-1,1] \}$ is not compact.
QUESTION [0 upvotes]: Show that $X = \{ \text{The set of all series which converge to }a \in [-1,1] \}$ is not compact. The metric on this space is given by $$ d\left(\bar a, \bar b\right)=\left(\sum_{k=1}^{\infty}| a_k -b_k |^2\right)^{1/2}.$$

My idea was to take $N_r(x_i)$ for some fixed $r$ and $x_i \in X$ to show that the only covering of $X$ requires that  $n \rightarrow \infty$ of $$ \bigcup_{i=1}^{n} N_r(x_i)$$ But, I don't know how to show this. Alternatively, is there another way just based on definition of compactness alone to show that this space is not compact?

REPLY [1 votes]: Take for fixed $n$ the point $e_n$ which is the sequence defined by $(e_n)_n = 1$ and $(e_n)_m = 0$ for $m \neq n$.
All these are simple series that all converge to 1, so they're all in $X$.
The distance $d'(e_n, e_m) = \sqrt{2}$ for $n \neq m$, by simple computation.
Consider $(e_n)$ as a sequence in $X$, and note that if it would have a convergent subsequence (in the whole space or $X$), its terms would have to get closer together (the subsequence is Cauchy..), and this never happens. So $X$ is not sequentially compact (which is equivalent to compact in metric spaces).


TITLE: topology - Quotient topology
QUESTION [6 upvotes]: Let $k:X \to Y$ be an onto map.How to prove that the quotient topology on $Y$ induced by $k$ is the largest topology relative to  which $k$ is continuous.

REPLY [10 votes]: I’m going to assume that you’ve defined the quotient topology $\tau$ on $Y$ as follows: a set $U\subseteq Y$ is open iff $k^{-1}[U]$ is open in $X$. It’s an immediate consequence of this definition that the topology $\tau$ on $Y$ makes $k$ continuous, so what you have to show is that if $\tau'$ is another topology on $Y$ making $k$ continuous, and $\tau\subseteq\tau'$, then $\tau=\tau'$. In other words, you must show that it’s impossible to have $\tau'\supsetneqq\tau$: there is no topology on $Y$ that is strictly stronger than $\tau$ and makes $k$ continuous.
Here’s a large hint to get you started. Suppose that $\tau\subseteq\tau'$, where $\tau'$ is a topology on $Y$ making $k$ continuous. If $\tau'\ne\tau$, there is a set $U\in\tau'\setminus\tau$. By hypothesis $k$ is continuous as a map from $X$ to $\langle Y,\tau'\rangle$, so $k^{-1}[U]$ is open in $X$. Now apply the definition of the quotient topology $\tau$ to get a contradiction.


TITLE: A Borel-Cantelli Type Statement
QUESTION [4 upvotes]: Let $(X, \mathcal X, \mu)$ be a probability space and $E_1, E_2, E_3, \ldots$ be measurable sets such that there is $\varepsilon>0$ satisfying $\mu(E_i)\geq \varepsilon$ for each $i$.

Question. Is is true that infinitely many of the $E_i$'s occur with positive probability, or, in other words, is it true that $\mu(\limsup E_n) > 0$?

If the $E_i$'s were pairwise independent then we know that answer is yes by Borel-Cantelli.

REPLY [4 votes]: The claim is true: Let $S = \sum_{i=1}^\infty \chi_{E_i}$. Suppose for the sake of contradiction that $S < \infty$ a.e. Then, there exists an $M$ such that $\Pr(S\le M) \ge 1 - \frac\varepsilon 2$. If $A$ is the event that $S\le M$,  then $\mu(A\cap E_i) \ge \frac\varepsilon 2$ for all $i$. But this would imply $\int_A S\,d\mu = \sum_{i=1}^\infty \mu(A\cap E_i) = \infty$, which is impossible because $S\le M$ on $A$.

REPLY [0 votes]: I think an affirmative answer follows from https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma#Kochen%E2%80%93Stone
The $\sum P(A_n) = \infty$ condition is clear. To verify the lim inf, we note that $(\sum_{n = 1}^k P(A_n))^2 \geq \epsilon^2 k^2$ and $\sum_{1 \leq m,n \leq k } P(A_m \cap A_n) \leq k^2 $, so that $\frac{ \sum_{1 \leq m,n \leq k } P(A_m \cap A_n) }{( \sum \mathbb{P}(A_n) )^2} \leq \frac{k^2}{k^2 \epsilon^2} = 1/\epsilon^2 < \infty$.


TITLE: What can I do this cos term to remove the divide by 0?
QUESTION [2 upvotes]: I was asked to help someone with this problem, and I don't really know the answer why. But I thought I'd still try.
$$\lim_{t \to 10} \frac{t^2 - 100}{t+1} \cos\left( \frac{1}{10-t} \right)+ 100$$
The problem lies with the cos term. What can I do with the cos term to remove divide by 0 ?
I found the answer to be $100$ (Google), but I do not know what they did to the $\cos$ term. Is that even the answer ?
Thanks!

REPLY [4 votes]: The cos term is irrelevant. It can only wiggle between $-1$ and $1$, and is therefore killed by the $t^2-100$ term, since that approaches $0$.
For a less cluttered version of the same phenomenon, consider the function $f(x)=x\sin\left(\frac{1}{x}\right)$ (for $x\ne 0$). The absolute value of this is always $\le |x|$, so (by Squeezing) $f(x)\to 0$ as $x\to 0$.

REPLY [4 votes]: The function is bounded below by $\left|\frac{t^2-100}{t+1}\right|(-1)+100$ and bounded above by  $\left|\frac{t^2-100}{t+1}\right|(+1)+100$.  Each approaches 100, so by the squeeze theorem the original limit is 100.


TITLE: Is the universe deterministic when looking backwards?
QUESTION [14 upvotes]: Someone once told me that if, in theory, we could know the position and motion of all the particles in the universe, we could use that data to run time backwards, and work out everything that had come before.  That means the current state of the universe effectively encodes all of history.
Is this theory reasonable?
I have two main concerns, so it would be great if you could address these in your answer:

Due to entropy, information is lost over time.  I believe that means the same state could be arrived at by two different histories.  (For example, once a glass of water is still or frozen, we don't know if it was poured 100 years ago or 10,000 years ago.)  If that is true, I don't see how we could determine history from state alone.
From A Brief History of Time (Stephen Hawking) I got the impression that time was symmetrical: it acted the same regardless of which way it was running.  So if the universe is deterministic going forwards, that would also mean it is deterministic going backwards.  Was Hawking correct about time symmetry, or did I just misunderstand him?

REPLY [0 votes]: No, the universe is not deterministic when looking backwards.   The determination of position and velocity of a particle can NEVER (by the Heisenberg uncertainty principle) be known at any time, so neither forward-time nor backward-time
"predictions" of a particle trajectory are absolute.
If you can't absolutely predict a particle, a universe is out of the
question.


TITLE: Find bifurcations of $x' =x^6 - 2 x^4 + \mu $
QUESTION [1 upvotes]: Consider the family of ODEs given by $x' =x^6 - 2 x^4 + \mu $ for $\mu \in R$.
We want to find the bifurcation points for this family, ie the points where the number of solutions changes.
I can certainly plot this equation and find the bifurcation points graphically, but I was hoping to find an analytical way of solving this problem.

REPLY [1 votes]: For one-dimensional autonomous equations of type $\dot{x} = P(x, \mu)$ all bifurcation values can be found from solving the system
$$ P(x^\ast, \mu^\ast) = 0, \, P'_{x} (x^\ast, \mu^\ast) = 0.$$
This is basically because all bifurcations in 1d case happen only with equilibria (this is why we have the first equation) and equilibrium becomes non-hyperbolic iff the derivative $P'_{x} = 0$ at it (and it is the second equation). In your case it means:
$$ x^6 - 2x^4 + \mu = 0, 6x^5 - 8x^3 = 0,$$
which transforms to
$$ x^2 = \dfrac{4}{3}, \, x^6 - 2x^4 + \mu = 0,$$
and finally
$$ x^2 = \dfrac{4}{3}, \, \mu = \dfrac{32}{27}. $$
At $\mu = \dfrac{32}{27}$ two equilibria coalesce at $x = \sqrt{\dfrac{4}{3}}$ and $x = -\sqrt{\dfrac{4}{3}}$. This is because technically it's the only bifurcation that can happen in 1d autonomous equations.


TITLE: Pauli Matrix Question
QUESTION [0 upvotes]: I'm working through a paper and can't complete a calculation, which seems very trivial.
The paper has a matrix $\mathbf{T}(z)$ which is a $2\times2$ matrix with elements bounded by $1$. Each entry contains a smooth function in $z$. The paper writes
$$-\boldsymbol{\sigma}_{3}\mathbf{T}\boldsymbol{}\sigma_{3} -\boldsymbol{\sigma}_{1}\mathbf{T}\boldsymbol{}\sigma_{1} = -2\mathbf{T}, $$
where
$$\boldsymbol{\sigma}_{1} = \begin{bmatrix}0\quad1 \\ 1 \quad 0\end{bmatrix}, \quad \boldsymbol{\sigma}_{3} = \begin{bmatrix}1\quad 0\\ 0\quad -1\end{bmatrix}$$

REPLY [1 votes]: Define your matrix elements $T =\begin{pmatrix}t_{11} & t_{12} \\ t_{21} & t_{22}\end{pmatrix}$
Develop the equation and you'll find the set of 4 equations :
$\begin{pmatrix}t_{11}+t_{22}&-t_{12}+t_{21}\\t_{12}-t_{21}&t_{11}+t_{22} \end{pmatrix} = 2\begin{pmatrix}t_{11}&t_{12}\\ t_{21}&t_{22}\end{pmatrix}$
which is solved by $t_{12}=0$, $t_{21}=0$ and $t_{11}=t_{22}$.
Therefore, $T$ is proportional to the identity matrix.


TITLE: Find the distribution of some random variable connected to Wiener Process. Please, check my solution.
QUESTION [2 upvotes]: I need to find a distribution of $ 5W_1-W_3+W_7 $, where $W_t$ stands for Wiener Process $W_t\sim\mathcal{N}(0,t)$. Is this solution right?
$E(5W_1-W_3+W_7)=5E(W_1)-E(W_3)+E(W_7)=0$ and since $W_7-W_3$ has the same distribution as $W_{7-3}=W_4 \sim \mathcal{N}(0,4)$
$D^2(5W_1-W_3+W_7)=D^2(5W_1+W_4)=5^2D^2(W_1)+D^2(W_4)+2\mathrm{cov}(5W_1,W_4)=25+4+2\cdot 5\mathrm{cov}(W_1,W_4)=29+10\mathrm{min}\{1,4\}=39$
Hence the final answer is $(5W_1-W_3+W_7) \sim\mathcal{N}(0,39)$
If something is wrong can you point it out for me, please?
Thanks in advance!

REPLY [1 votes]: Just write $W_t = \sum_{i=1}^t X_i$ where $X_i$'s are i.i.d. $\mathcal{N}(0, 1)$. You'll see that
\begin{align}
\text{Cov}(W_t, W_{t+\ell}) = \text{Var}(W_t) = t
\end{align}
for $\ell \ge 0$.
From this, you can get
\begin{align}
\text{Var}(5W_1 - W_3 + W_7) & =
\text{Var}(5W_1) + \text{Var}(W_3) + \text{Var}(W_7) + \\
& \phantom{{} = {}} - 2\text{Cov}(5W_1, W_3) + 2\text{Cov}(5W_1, W_7) - 2 \text{Cov}(W_3, W_7) \\
& = 25 + 3 + 7 - 10 + 10 - 6 = 29.
\end{align}


text:
\begin{document}

\maketitle

\begin{abstract}
We define a new graph invariant called the scramble number.  We show that the scramble number of a graph is a lower bound for the gonality and an upper bound for the treewidth.  Unlike the treewdith, the scramble number is not minor monotone, but it is subgraph monotone and invariant under subdivision.  We compute the scramble number and gonality of several families of graphs for which these invariants are strictly greater than the treewidth.
\end{abstract}

\section{Introduction}

In \cite{BakerNorine}, Baker and Norine introduce the theory of divisors on graphs, and in \cite{Baker08}, Baker defines a new graph invariant known as the \emph{gonality}.  Due to its connection to algebraic geometry, this invariant has received a great deal of interest \cite{dbG, NPHard, RandomGonality, ExpanderGonality, Hendrey, AidunMorrison, Morrison}.  Computing the gonality $\mathrm{gon}(G)$ of a graph $G$ is NP-hard \cite{NPHard}.  To find an upper bound, one only has to produce an example of a divisor with positive rank, but it is much more difficult to find lower bounds.  A significant step in this direction was obtained in \cite{dbG}, in which the authors show that the gonality of a graph $G$ is bounded below by a much-studied graph invariant known as the \emph{treewidth}, $\mathrm{tw}(G)$.

In this paper we define a new graph invariant, which we call the \emph{scramble number} of $G$ and denote $\mathrm{sn}(G)$.  We refer the reader to \S~\ref{Sec:Scramble} for a definition.  Our main result is the following.

\begin{theorem}
\label{Thm:MainThm}
For any graph $G$, we have
\[
\mathrm{tw} (G) \leq \mathrm{sn} (G) \leq \mathrm{gon} (G) .
\]
\end{theorem}

Theorem~\ref{Thm:MainThm} is proved in two parts.  The left inequality is proved in Corollary~\ref{Cor:TW} and the right inequality in Theorem~\ref{Thm:Bound}.  The proof of Theorem~\ref{Thm:Bound} follows closely that of \cite{dbG}.  Indeed, the scramble number is defined in such a way as to generalize the statement of \cite[Theorem~3.1]{dbG} without significantly altering its proof.

After establishing Theorem~\ref{Thm:MainThm}, we then examine properties of the scramble number.  We show that it is subgraph monotone (Proposition~\ref{Prop:Subgraph}) and invariant under subdivision (Proposition~\ref{Prop:Refinement}) but not minor montone (Example~\ref{Ex:Minor}).  In Examples~\ref{Ex:Path} and~\ref{Ex:COL}, we show that $\mathrm{sn} (G)$ is unbounded in $\mathrm{tw} (G)$, and $\mathrm{gon} (G)$ is unbounded in $\mathrm{sn} (G)$.

The fact that the treewidth bound can be strict is not new.  See, for example, \cite{Hendrey}, where it is shown that, for all integers $k \geq 2$ and $\ell \geq k$, there exists a $k$-connected graph of treewidth $k$ and gonality at least $\ell$.  The strength of Theorem~\ref{Thm:MainThm} is that it can be used to compute the gonality in cases where this bound is strict.  This is demonstrated in \S~\ref{Sec:Examples}, where we use Theorem~\ref{Thm:MainThm} to compute the gonality of several families of graphs.  In \cite{Morrison}, the authors compute the treewidth of the \emph{grid graphs} $G_{m,n}$, the \emph{stacked prisms} $Y_{m,n}$, and the \emph{toroidal grid graphs} $T_{m,n}$.  (See \S~\ref{Sec:Examples} for precise definitions of these graphs.)  Combining their results with the bound from \cite{dbG}, they compute the gonalities of all these graphs except for $T_{n,n}$, $T_{n+1,n}$, and $Y_{2n,n}$.  Using Theorem~\ref{Thm:MainThm}, we complete this project, computing the gonalities of the graphs in these families and some minor generalizations.  Even in cases where the gonality was already known, our constructions are quite a bit simpler than those that arise in computations of treewidth.  For this reason, we suspect that scrambles may be useful in further computations of graph gonality.

\textbf{Acknowledgments.}  This research was conducted as a project with the University of Kentucky Math Lab.  The third author was supported by NSF DMS-1601896.  We would like to thank Ralph Morrison for some discussions on this material.  We would also like to thank the anonymous referees for several helpful comments, including the suggestion to add Examples~\ref{Ex:Path} and~\ref{Ex:COL}.

\section{Preliminiaries}

In this section, we fix notation and review some basic definitions.  For simplicity, we will assume throughout that all graphs are connected, possibly with multiple edges, but no loops.  Given a graph $G$, we write $V(G)$ for its vertex set and $E(G)$ for its edge set.  If $A$ is a subset of $V(G)$, we write $A^c$ for its complement.  If $A$ and $B$ are subsets of $V(G)$, we write $E_G (A,B)$ for the set of edges with one endpoint in $A$ and the other endpoint in $B$.  We write $E (A,B)$ when the graph $G$ is clear from the context.  A set of vertices $B \subseteq V(G)$ is \emph{connected} if, for every proper subset $A \subsetneq B$, the set $E(A, B \smallsetminus A)$ is nonempty.

A \emph{subgraph} of a graph $G$ is a graph that can be obtained from $G$ by deleting edges and deleting isolated vertices.  A \emph{minor} of a graph $G$ is a graph that can be obtained from $G$ by contracting edges, deleting edges, and deleting isolated vertices.  If $e \in E(G)$ is an edge with endpoints $v$ and $w$, the \emph{edge-subdivision} of $G$ at $e$ is obtained by introducing a new vertex $u$ in the middle of $e$.  In other words, the vertex set of the edge-subdivision is $V(G) \cup \{ u \}$, and the edge set of the edge-subdivision is $E(G) \cup \{ uv, uw \} \smallsetminus \{ e \}$.  A \emph{subdivision} of a graph $G$ is one that can be obtained from $G$ by finitely many edge-subdivisions.

We briefly describe the theory of divisors on graphs.  For a more detailed treatment, we refer the reader to \cite{BakerNorine} or \cite{BakerJensen}.  A \emph{divisor} on a graph $G$ is a formal $\mathbb{Z}$-linear combination of vertices of $G$.  It is standard to think of a divisor as a stack of poker chips on each of the vertices, with negative coefficients corresponding to vertices that are ``in debt''.  For this reason, divisors are sometimes referred to as \emph{chip configurations}.  (We use the term ``divisor'' to emphasize the connection with algebraic geometry.)  The \emph{degree} of a divisor is the sum of the coefficients:
\[
\mathrm{deg} \left( \sum_{v \in V(G)} a_v \cdot v \right) := \sum_{v \in V(G)} a_v .
\]
In other words, the degree is the total number of poker chips.  A divisor is said to be \emph{effective} if all of the coefficients are nonnegative -- that is, none of the vertices are in debt.  The \emph{support} of an effective divisor $D$, denoted $\mathrm{Supp}(D)$, is the set of vertices with nonzero coefficient.

Given a divisor $D$ on $G$ and a vertex $v \in V(G)$, we may \emph{fire} the vertex $v$ to obtain a new divisor.  For each edge $e$ with $v$ as an endpoint, this new divisor has 1 fewer chip at $v$, and 1 more chip at the other endpoint of $e$.  If we fire every vertex in a subset $A \subseteq V(G)$, we say that we fire the subset $A$.  (The resulting divisor is independent of the order in which one fires the vertices in $A$.)  We say that two divisors are \emph{equivalent} if one can be obtained from the other by a sequence of chip-firing moves.  Given a vertex $v \in V(G)$, an effective divisor $D$ is \emph{$v$-reduced} if, for every subset $A \subseteq V(G) \smallsetminus \{ v \}$, the divisor obtained by firing $A$ is not effective.  Every effective divisor is equivalent to a unique $v$-reduced divisor.  We say that a divisor $D$ on $G$ has \emph{positive rank} if its $v$-reduced representative contains $v$ in its support, for every vertex $v \in V(G)$.  The \emph{gonality} of $G$ is the minimum degree of a divisor of positive rank on $G$.

\section{Brambles and Scrambles}
\label{Sec:Scramble}

We make the following definition.

\begin{definition}
A \emph{scramble} in a graph $G$ is a set $\mathscr{S} = \{ E_1 , \ldots E_n \}$ of connected subsets of $V(G)$.
\end{definition}

We will often refer to the subsets $E_i$ as \emph{eggs}.  Scrambles with certain properties have been studied extensively in the graph theory literature.

\begin{definition}
A \emph{bramble} is a scramble $\mathscr{S}$ with the property that $E \cup E'$ is connected for every pair $E, E' \in \mathscr{S}$.  It is called a \emph{strict bramble} if every pair of elements $E, E' \in \mathscr{S}$ has nonempty intersection.
\end{definition}

\begin{definition}
A set $C \subseteq V(G)$ is called a \emph{hitting set} for a scramble $\mathscr{S}$ if $C \cap E \neq \emptyset$ for all $E \in \mathscr{S}$.
\end{definition}

The \emph{order} of a bramble $\mathscr{B}$ is the minimum size of a hitting set for $\mathscr{B}$.  The \emph{bramble number} of a graph $G$ is the maximum order of a bramble in $G$, and is denoted $\mathrm{bn}(G)$.  A result of Seymour and Thomas shows that the bramble number of a graph is closely related to another well-known graph invariant, known as the \emph{treewidth} $\mathrm{tw}(G)$.  In particular, $\mathrm{tw}(G) = \mathrm{bn}(G) - 1$ for any graph $G$ \cite{SeymourThomas}.  Here, we define some related notions for more general scrambles.

\begin{definition}
\label{Def:ScrambleOrder}
The \emph{scramble order} of a scramble $\mathscr{S}$ is the maximum integer $k$ such that:
\begin{enumerate}
\item  no set $C \subseteq V(G)$ of size less than $k$ is a hitting set for $\mathscr{S}$, and
\item  if $A \subseteq V(G)$ is a set such that there exists $E, E' \in \mathscr{S}$ with $E \subseteq A$ and $E' \subseteq A^c$, then $\vert E(A,A^c) \vert \geq k$.
\end{enumerate}
The scramble order of a scramble $\mathscr{S}$ is denoted $\vert \vert \mathscr{S} \vert \vert$.
The \emph{scramble number} of a graph $G$, denoted $\mathrm{sn}(G)$, is the maximum scramble order of a scramble in $G$.
\end{definition}

We note the following observations about the scramble order of brambles.

\begin{lemma}
The order of a strict bramble is equal to its scramble order.
\end{lemma}

\begin{proof}
Let $\mathscr{B}$ be a strict bramble of order $k$.  By definition, there is a hitting set $C \subseteq V(G)$ of size $k$ for $\mathscr{B}$, and no such set of size less than $k$.  The scramble order of $\mathscr{B}$ is therefore at most $k$.  Since $\mathscr{B}$ is a strict bramble, any two sets $E, E' \in \mathscr{B}$ have nonempty intersection.  It follows that there is no set $A \subseteq V(G)$ that contains $E$ and whose complement contains $E'$, so property (2) of Definition~\ref{Def:ScrambleOrder} is satisfied vacuously.
\end{proof}

\begin{lemma}
\label{Lem:BrambleScramble}
Let $\mathscr{B}$ be a bramble of order $k$.  Then the scramble order of $\mathscr{B}$ is either $k$ or $k-1$.
\end{lemma}

\begin{proof}
By definition, there is a hitting set $C \subseteq V(G)$ of size $k$ for $\mathscr{B}$, and no such set of size less than $k$.  The scramble order of $\mathscr{B}$ is therefore at most $k$.  By \cite[Lemma~3.3]{dbG}, if $E, E' \in \mathscr{B}$ and $A \subseteq V(G)$ is a subset such that $E \subseteq A$ and $E' \subseteq A^c$, then $\vert E(A,A^c) \vert \geq k-1$.  It follows that the scramble order of $\mathscr{B}$ is at least $k-1$.
\end{proof}

\begin{corollary}
\label{Cor:TW}
For any graph $G$, we have $\mathrm{tw}(G) \leq \mathrm{sn}(G)$.
\end{corollary}

\begin{proof}
Let $\mathscr{B}$ be a bramble of maximum order $k$ in $G$.  By \cite{SeymourThomas}, we have $\mathrm{tw}(G) = k-1$.  By Lemma~\ref{Lem:BrambleScramble}, the scramble order of $\mathscr{B}$ is at least $k-1$, hence $\mathrm{sn}(G) \geq k-1$.
\end{proof}

\section{Properties of the Scramble Number}

We now prove our main result about the scramble number.  Namely, that the scramble number of a graph is a lower bound for the graph's gonality.  Our argument follows closely that of \cite[Theorem~3.1]{dbG}, which shows that the treewidth of a graph is a lower bound for the graph's gonality.  Indeed, we defined the scramble number with the specific goal of stating \cite[Theorem~3.1]{dbG} in its maximum generality.

\begin{theorem}
\label{Thm:Bound}
For any graph $G$, we have $\mathrm{sn}(G) \leq \mathrm{gon}(G)$.
\end{theorem}

\begin{proof}
Let $\mathscr{S}$ be a scramble on $G$, and let $D'$ be a divisor of positive rank on $G$.  We will show that $\mathrm{deg}(D') \geq \vert \vert \mathscr{S} \vert \vert$.  Among the effective divisors equivalent to $D'$, we choose $D$ such that $\mathrm{Supp}(D)$ intersects a maximum number of eggs in $\mathscr{S}$.  If $\mathrm{Supp}(D)$ is a hitting set for $\mathscr{S}$ then, by definition,
\[
\mathrm{deg}(D) \geq \vert \mathrm{Supp}(D) \vert \geq \vert \vert \mathscr{S} \vert \vert .
\]

Conversely, suppose that there is some egg $E \in \mathcal{S}$ that does not intersect $\mathrm{Supp}(D)$, and let $v\in E$.  Since $D$ has positive rank and $v \notin \mathrm{Supp}(D)$, it follows that $D$ is not $v-$reduced.  Therefore there exists a chain
\[
\emptyset \subsetneq U_1 \subseteq \cdots \subseteq U_k \subseteq V(G) \smallsetminus \{v \}
\]
and a sequence of effective divisors $D_0 , D_1, \ldots, D_k$ such that:
\begin{enumerate}
\item  $D_0 = D$,
\item  $D_k$ is $v$-reduced, and
\item  $D_i$ is obtained from $D_{i-1}$ by firing the set $U_i$, for all $i$.
\end{enumerate}
Since $D$ has positive rank, we see that $v \in \mathrm{Supp}(D_k)$ and hence $\mathrm{Supp}(D_k)$ intersects $E$.  By assumption, $\mathrm{Supp}(D_k)$ does not intersect more eggs than $\mathrm{Supp}(D)$, so there is at least one egg $E'$ that intersects $\mathrm{Supp}(D)$ but not $\mathrm{Supp}(D_k)$.  Let $i \leq k$ be the smallest index such that there is some $E' \in \mathscr{S}$ that intersects $\mathrm{Supp}(D)$ but not $\mathrm{Supp}(D_i)$.  Then $E' \cap \mathrm{Supp}(D_{i-1}) \neq \emptyset$ and $E' \cap \mathrm{Supp}(D_i) = \emptyset$.  By \cite[Lemma~3.2]{dbG}, it follows that $E' \subseteq U_i$.

Again, by assumption, $\mathrm{Supp}(D_{i-1})$ does not intersect more eggs than $\mathrm{Supp}(D)$, so $\mathrm{Supp}(D_{i-1})$ does not intersect $E$.  Let $j \geq i$ be the smallest index such that $E \cap \mathrm{Supp}(D_{j-1}) = \emptyset$ and $E \cap \mathrm{Supp}(D_j) \neq \emptyset$.  Since $D_{j-1}$ can be obtained from $D_j$ by firing $U_j^c$, we see that $E \subseteq U_j^c \subseteq U_i^c$.  Since $E \subseteq U_i^c$ and $E' \subseteq U_i$, it follows by the definition of a scramble that $\vert E(U_i , U_i^c) \vert \geq \vert \vert \mathscr{S} \vert \vert$.  Since
\[
\mathrm{deg}(D_{i-1}) \geq \sum_{u \in U_i} D_{i-1}(u) \geq \vert E(U_i, U_i^c) \vert,
\]
we have
\[
\mathrm{deg}(D_{i-1}) \geq \vert \vert \mathscr{S} \vert \vert .
\]
\end{proof}

We include here some observations about graphs of low scramble number.

\begin{corollary}
\label{Cor:Tree}
The scramble number of a graph $G$ is 1 if and only if $G$ is a tree.
\end{corollary}

\begin{proof}
If $G$ is a tree, then
\[
1 = \mathrm{tw}(G) \leq \mathrm{sn}(G) \leq \mathrm{gon}(G) = 1,
\]
so $\mathrm{sn}(G) = 1$.  On the other hand, if $\mathrm{sn}(G)=1$, then $\mathrm{tw}(G) \leq \mathrm{sn} (G) = 1$.  If $G$ is a simple graph, then this implies that $G$ is a tree.  To see that $G$ must be simple, let $v$ and $w$ be two adjacent vertices in $G$.  If there are multiple edges between $v$ and $w$, then the scramble $\mathscr{S} = \{ \{ v \} , \{ w \} \}$ has scramble order 2.  Since $\mathrm{sn} (G) = 1$, it follows that any pair of vertices in $G$ is connected by at most 1 edge.
\end{proof}

\begin{corollary}
\label{Lem:Cycle}
If $G$ is a cycle, then $\mathrm{sn}(G) = 2$.
\end{corollary}

\begin{proof}
If $G$ is a cycle, then
\[
2 = \mathrm{tw}(G) \leq \mathrm{sn}(G) \leq \mathrm{gon}(G) = 2,
\]
so $\mathrm{sn}(G) = 2$.
\end{proof}

One of the major advantages of the treewidth bound from \cite{dbG} is that the treewidth is minor monotone.  In other words, if $G'$ is a graph minor of a graph $G$, then $\mathrm{tw}(G') \leq \mathrm{tw}(G)$.  This is not true for the scramble number, as the following example shows.

\begin{example}
\label{Ex:Minor}
Let $G$ be the graph depicted in Figure~\ref{Fig:Gon3}.  If $v$ is the green vertex, then the divisor $3v$ has positive rank.  It follows that the gonality of $G$ is at most 3, and thus the scramble number of $G$ is at most 3 by Theorem~\ref{Thm:Bound}.

\begin{figure}[h]

\begin{tikzpicture}
\draw (0,1)--(1,0);
\draw (0,1)--(1,1);
\draw (0,1)--(1,2);
\draw (1,0)--(1,1);
\draw (1,0)--(2,0);
\draw (1,1)--(1,2);
\draw[red][thick] (1,1)--(2,1);
\draw (1.5,1.2) node{e};
\draw (1,2)--(2,2);
\draw (2,0)--(2,1);
\draw (2,0)--(3,1);
\draw (2,1)--(2,2);
\draw (2,1)--(3,1);
\draw (2,2)--(3,1);
\filldraw[green] (0,1) circle (3pt);
\draw (-0.3,1) node{v};
\draw (0,1) circle (3pt);
\filldraw (1,0) circle (2pt);
\filldraw (1,1) circle (2pt);
\filldraw (1,2) circle (2pt);
\filldraw (2,0) circle (2pt);
\filldraw (2,1) circle (2pt);
\filldraw (2,2) circle (2pt);
\filldraw (3,1) circle (2pt);
\end{tikzpicture}

\caption{A graph $G$ with scramble number 3.}
\label{Fig:Gon3}
\end{figure}

Now, let $G'$ be the graph pictured in Figure~\ref{Fig:S4}, obtained by contracting the red edge $e$ in $G$.  The 4 colored subsets are the eggs of a scramble $\mathscr{S}$, which we now show has scramble order 4.  Because the 4 eggs are disjoint, there is no hitting set of size less than 4.  Now, let $A \subseteq V(G')$ be a set with the property that both $A$ and $A^c$ contain an egg.  By exchanging the roles of $A$ and $A^c$, we may assume that $A$ contains the center red vertex.  If $A$ consists solely of this vertex, then $\vert E(A,A^c) \vert = 6$.  Otherwise, $A$ contains some, but not all, of the vertices on the hexagonal outer ring.  We then see that $E(A,A^c)$ contains at least two edges in the hexagonal outer ring, and at least two edges that have the center red vertex as an endpoint.  Thus, $\vert E(A,A^c) \vert \geq 4$.

\begin{figure}[h]
\begin{tikzpicture}
\draw (0,1) circle (3pt);
\draw (1,0) circle (3pt);
\draw (1.5,1) circle (3pt);
\draw (1,2) circle (3pt);
\draw (2,0) circle (3pt);
\draw (3,1) circle (3pt);
\draw (2,2) circle (3pt);
\draw (0,1)--(1,0);
\draw (0,1)--(3,1);
\draw (0,1)--(1,2);
\draw (1,0)--(2,2);
\draw (1,0)--(2,0);
\draw (1,2)--(2,0);
\draw (1,2)--(2,2);
\draw (2,2)--(3,1);
\draw (2,0)--(3,1);
\filldraw[gold] (0,1) circle (3pt);
\draw (-0.3,1) node{Y};
\filldraw[blue] (1,0) circle (3pt);
\draw (1,-0.3) node{B};
\filldraw[red] (1.5,1) circle (3pt);
\draw (1.5,1.3) node{R};
\filldraw[gold] (1,2) circle (3pt);
\draw (1,2.3) node{Y};
\filldraw[blue] (2,0) circle (3pt);
\draw (2,-0.3) node{B};
\filldraw[green] (3,1) circle (3pt);
\draw (3.3,1) node{G};
\filldraw[green] (2,2) circle (3pt);
\draw (2,2.3) node{G};
\end{tikzpicture}

\caption{The graph $G'$ is a graph minor of $G$ with higher scramble number.}
\label{Fig:S4}

\end{figure}

\end{example}

While the scramble number is not minor monotone, it is subgraph monotone.

\begin{proposition}
\label{Prop:Subgraph}
If $G'$ is a subgraph of $G$, then $\mathrm{sn}(G') \leq \mathrm{sn}(G)$.
\end{proposition}

\begin{proof}
Let $\mathscr{S}'$ be a scramble on $G'$, and let $\mathscr{S}$ be the scramble on $G$ with the same eggs as $\mathscr{S}'$ on $G'$.  We will show that $\vert \vert \mathscr{S} \vert \vert \geq \vert \vert \mathscr{S}' \vert \vert$.  If $C \subseteq V(G)$ is a hitting set for $\mathscr{S}$, then $C \cap V(G')$ is a hitting set for $\mathscr{S}'$.  Thus, for every hitting set $C$ of $\mathscr{S}$, we have $\vert C \vert \geq \vert \vert \mathscr{S}' \vert \vert$.  Now, let $A$ be a subset of $V(G)$ such that $A$ and $A^c$ both contain eggs of $\mathscr{S}$.  Then $A \cap V(G')$ is a subset of $V(G')$ with the property that both it and its complement contain eggs of $\mathscr{S}'$, and $\vert E_G (A,A^c) \vert \geq \vert E_{G'}(A \cap V(G'), A^c \cap V(G')) \vert$.
It follows that $\vert \vert \mathscr{S} \vert \vert \geq \vert \vert \mathscr{S}' \vert \vert$.
\end{proof}

The scramble number is also invariant under subdivision.

\begin{proposition}
\label{Prop:Refinement}
If $G'$ is a subdivision of $G$, then $\mathrm{sn} (G) = \mathrm{sn} (G')$.
\end{proposition}

\begin{proof}
By induction, it suffices to consider the case where $G$ has one fewer vertex than $G'$.  Let $v$ and $w$ be adjacent vertices in $G$, and let $G'$ be the graph obtained by subdividing an edge between $v$ and $w$, introducing a vertex $u$ between them.

First, we will show that $\mathrm{sn} (G) \leq \mathrm{sn} (G')$.  To see this, let $\mathscr{S}$ be a scramble on $G$.  For each egg $E \in \mathscr{S}$, we define a connected subset $E' \subseteq V(G')$ as follows.  If $v \notin E$, then $E' = E$, and if $v \in E$, then $E' = E \cup \{ u \}$.  Let
\[
\mathscr{S}' = \{ E' \vert E \in \mathscr{S} \} .
\]
We will show that $\vert \vert \mathscr{S}' \vert \vert \geq \vert \vert \mathscr{S} \vert \vert$.

Let $C \subseteq V(G')$ be a hitting set for $\mathscr{S}'$.  If $u \notin C$, then $C$ is also a hitting set for $\mathscr{S}$.  On the other hand, if $u \in C$, then since every egg in $\mathscr{S}'$ that contains $u$ also contains $v$, the set $C' = C \cup \{ v \} \smallsetminus \{ u \}$ is a hitting set for $\mathscr{S}'$ with the property that $u \notin C'$ and $\vert C' \vert \leq \vert C \vert$.  Now, let $A$ be a subset of $V(G')$ such that both $A$ and $A^c$ contain eggs of $\mathscr{S}'$.  By exchanging $A$ and $A^c$, we may assume that $u \notin A$.  We may then think of $A$ also as a subset of $V(G)$ with the property that both $A$ and $A^c$ contain eggs of $\mathscr{S}$.  If both $v$ and $w$ are contained in $A$, then the number of edges leaving $A$ in $V(G)$ is 2 fewer than the number of edges leaving $A$ in $V(G')$.  Otherwise, these two numbers are equal.  It follows that $\vert \vert \mathscr{S}' \vert \vert \geq \vert \vert \mathscr{S} \vert \vert$.

We now show that $\mathrm{sn} (G) \geq \mathrm{sn} (G')$.  To see this, let $\mathscr{S}'$ be a scramble on $G'$ of maximal scramble order.  If $\mathrm{sn} (G) = 1$, then by Corollary~\ref{Cor:Tree}, we see that $G$ is a tree.  It follows that $G'$ is a tree as well, and $\mathrm{sn}(G') = 1$ by another application of Corollary~\ref{Cor:Tree}.  We may therefore assume that $\mathrm{sn} (G) \geq 2$.  If $\vert \vert \mathscr{S}' \vert \vert \leq 2$ the result follows, so we assume from here on that $\vert \vert \mathscr{S}' \vert \vert \geq 3$.

If every egg in $\mathscr{S}'$ contains $u$, then $\mathscr{S}'$ has a hitting set of size 1, a contradiction.  It follows that if $\{ u \} \in \mathscr{S}'$, then the set $A = \{ u \}$ has the property that both $A$ and $A^c$ contain eggs of $\mathscr{S}'$.  Thus, $\vert \vert \mathscr{S}' \vert \vert \leq \vert E_{G'} (A,A^c) \vert = 2$, another contradiction.  We may therefore assume that $\{ u \} \notin \mathscr{S}'$.  Let
\[
\mathscr{S} = \{ E' \cap V(G) \vert E' \in \mathscr{S}' \}.
\]
Note that each element of $\mathscr{S}$ is a connected subset of $V(G)$, so $\mathscr{S}$ is a scramble in $G$.  We will show that $\vert \vert \mathscr{S} \vert \vert \geq \vert \vert \mathscr{S}' \vert \vert$.  First, let $C \subseteq V(G)$ be a hitting set for $\mathscr{S}$.  Since $\{ u \} \notin \mathscr{S}'$, we see that $C$ is also a hitting set for $\mathscr{S}'$, so $\vert C \vert \geq \vert \vert \mathscr{S}' \vert \vert$.

Now, let $A$ be a subset of $V(G)$ with the property that both $A$ and $A^c$ contain eggs of $\mathscr{S}$.  Without loss of generality, assume that $v \in A$.  By considering several cases, we will show that $\vert \vert \mathscr{S}' \vert \vert \leq \vert E_G (A,A^c) \vert$.  First, assume that there is an egg $E' \in \mathscr{S}'$ such that $E' \cap V(G) \subseteq A^c$ and $u \notin E'$.  In this case, let $A' = A \cup \{ u \}$.  We see that $A'$ contains an egg in $\mathscr{S}'$, $A'^c$ contains the egg $E'$, and $\vert E_G (A,A^c) \vert = \vert E_{G'}(A',A'^c) \vert$.  It follows that $\vert \vert \mathscr{S}' \vert \vert \leq \vert E_G (A,A^c) \vert$.  Conversely, if there is an egg $E' \in \mathscr{S}'$ such that $E' \cap V(G) \subseteq A^c$ and $u \in E'$, then since eggs are connected and $E' \neq \{ u \}$, we have $w \in E' \cap V(G) \subseteq A^c$.  In this case, if there is an egg $E' \in \mathscr{S}'$ such that $E' \cap V(G) \subseteq A$ and $u \notin E'$, then by a similar argument setting $A' = A$, we see that $\vert \vert \mathscr{S}' \vert \vert \leq \vert E_G (A,A^c) \vert$.

Finally, consider the case where every egg $E' \in \mathscr{S}'$ such that $E' \cap V(G)$ is contained in either $A$ or $A^c$ contains $u$.  As above, this implies that the edge between $v$ and $w$ must be in $E_G (A,A^c)$.  We will construct a hitting set $C$ for $\mathscr{S}'$ of size $\vert C \vert \leq \vert E_G (A,A^c) \vert$, thus showing that $\vert \vert \mathscr{S}' \vert \vert \leq \vert E_G (A,A^c) \vert$.  To construct $C$, let $u \in C$, and, for every edge in $E_G (A,A^c)$ other than the edge between $v$ and $w$, choose one of its endpoints to be in $C$.  Clearly, $\vert C \vert \leq \vert E_G (A,A^c) \vert$.  To see that $C$ is a hitting set, let $E' \in \mathscr{S}'$ be an egg.  If $E' \cap V(G)$ is contained in either $A$ or $A^c$, then $u \in E' \cap C$ by assumption.  On the other hand, if $E' \cap V(G)$ is contained in neither $A$ nor $A^c$, then since $E'$ is connected, the set $E_{G'}(E' \cap A, E' \cap A^c)$ is nonempty.   Since $C$ contains an endpoint of every edge in this set, it follows that $E' \cap C$ is nonempty.
\end{proof}

\begin{example}
\label{Ex:Hyp}
The graph on the left in Figure~\ref{Fig:Refinement} has gonality 2.  By Theorem~\ref{Thm:Bound}, its scramble number is at most 2.  Since it is not a tree, by Corollary~\ref{Cor:Tree}, its scramble number is exactly 2.

On the other hand, the graph on the right has gonality 3.  Since it is a subdivision of the graph on the left, however, by Proposition~\ref{Prop:Refinement} the two graphs have the same scramble number.  Thus, the graph on the right is an example where the gonality and scramble number disagree.

\begin{figure}[h]

\begin{tikzpicture}
\filldraw (0,1) circle (2pt);
\filldraw (1,0) circle (2pt);

\filldraw (1,2) circle (2pt);
\filldraw (2,0) circle (2pt);

\filldraw (2,2) circle (2pt);
\filldraw (3,1) circle (2pt);
\draw (0,1)--(1,0);

\draw (0,1)--(1,2);
\draw (1,0)--(1,1);
\draw (1,0)--(2,0);
\draw (1,1)--(1,2);

\draw (1,2)--(2,2);
\draw (2,0)--(2,1);
\draw (2,0)--(3,1);
\draw (2,1)--(2,2);

\draw (2,2)--(3,1);

\filldraw (4,1) circle (2pt);
\filldraw (5,0) circle (2pt);

\filldraw (5,2) circle (2pt);
\filldraw (6,0) circle (2pt);

\filldraw (6,2) circle (2pt);
\filldraw (7,1) circle (2pt);
\filldraw (5.5,0) circle (2pt);
\draw (4,1)--(5,0);

\draw (4,1)--(5,2);
\draw (5,0)--(5,1);
\draw (5,0)--(6,0);
\draw (5,1)--(5,2);

\draw (5,2)--(6,2);
\draw (6,0)--(6,1);
\draw (6,0)--(7,1);
\draw (6,1)--(6,2);

\draw (6,2)--(7,1);
\end{tikzpicture}

\caption{Two graphs with the same scramble number, but different gonalities}
\label{Fig:Refinement}
\end{figure}
\end{example}

The following examples, suggested by the anonymous referee, show that $\mathrm{sn}(G)$ is unbounded in $\mathrm{tw}(G)$, and $\mathrm{gon}(G)$ is unbounded in $\mathrm{sn}(G)$.

\begin{example}
\label{Ex:Path}
In this example, we construct a family of graphs, all with treewidth 2, that have increasingly large scramble number.
For $k \geq 2$, let $G_k$ be the graph obtained from the path graph $P_k$ on $k$ vertices by replacing every edge with $k$ parallel edges.  For example, $G_3$ is pictured in Figure~\ref{Fig:SP}.  The treewidth of a graph with parallel edges is equal to that of the underlying simple graph.  Because $G_k$ is obtained from a path graph by introducing parallel edges, we have $\mathrm{tw} (G_k) = 1$.  On the other hand, we will see that $\mathrm{sn} (G_k) = k$.  To see this, note that $\mathrm{gon} (G_k) = k$, so it suffices to construct a scramble $\mathscr{S}$ of order $k$.  Let $\mathscr{S}$ be the scramble whose eggs are the individual vertices of $G_k$.  Since the eggs are disjoint, a minimal hitting set has size $k$.  If $A \subsetneq V(G_k)$ is a non-empty subset, then $\vert E(A,A^c) \vert \geq k$.  It follows that $\vert \vert \mathscr{S} \vert \vert = k$.
\begin{figure}[h]
\scalebox{1.5}{
\begin{tikzpicture}
\draw (0,0) circle (0.5);
\draw (1,0) circle (0.5);
\draw (-0.5,0)--(0.5,0);
\draw (0.5,0)--(1.5,0);
\draw [ball color=black] (-0.5,0) circle (0.55mm);
\draw [ball color=black] (0.5,0) circle (0.55mm);
\draw [ball color=black] (1.5,0) circle (0.55mm);
\end{tikzpicture}
}
\caption{The graph $G_3$.}
\label{Fig:SP}
\end{figure}

\end{example}

\begin{example}
\label{Ex:COL}
In this example we construct a family of graphs, all with scramble number 2, that have increasingly large gonality.
Let $G_k$ be the graph obtained from the path graph $P_k$ on $k$ vertices by replacing every edge with 2 parallel edges.  Since $G_k$ is not a tree, we have
\[
2 \leq \mathrm{sn} (G_k) \leq \mathrm{gon} (G_k) = 2,
\]
hence $\mathrm{sn} (G_k) = 2$.  Now, let $G'_k$ be the graph obtained from $G_k$ by subdividing one edge from each pair $k-1$ times.  An example of such a graph appears in Figure~\ref{Fig:COL}.  The graph $G'_k$ is a chain of $k-1$ loops, suitably chosen to be Brill-Noether general by \cite{CDPR}.  In particular, $\mathrm{gon}(G'_k) = \lceil \frac{k+2}{2} \rceil$.  By Proposition~\ref{Prop:Refinement}, however, we have $\mathrm{sn} (G'_k) = \mathrm{sn} (G_k) = 2$.

\begin{figure}[h]
\scalebox{1.5}{
\begin{tikzpicture}
\draw (0,0) circle (0.5);

\draw (1,0) circle (0.5);

\draw (2,0) circle (0.5);

\draw [ball color=black] (-0.5,0) circle (0.55mm);
\draw [ball color=black] (-0.35,0.35) circle (0.55mm);
\draw [ball color=black] (0,0.5) circle (0.55mm);
\draw [ball color=black] (0.35,0.35) circle (0.55mm);
\draw [ball color=black] (0.5,0) circle (0.55mm);

\draw [ball color=black] (0.65,0.35) circle (0.55mm);
\draw [ball color=black] (1,0.5) circle (0.55mm);
\draw [ball color=black] (1.35,0.35) circle (0.55mm);
\draw [ball color=black] (1.5,0) circle (0.55mm);

\draw [ball color=black] (1.65,0.35) circle (0.55mm);
\draw [ball color=black] (2,0.5) circle (0.55mm);
\draw [ball color=black] (2.35,0.35) circle (0.55mm);
\draw [ball color=black] (2.5,0) circle (0.55mm);

\end{tikzpicture}
}
\caption{The graph $G'_4$.}
\label{Fig:COL}
\end{figure}
\end{example}

\section{Examples}
\label{Sec:Examples}

In this section, we compute the scramble numbers and gonalities of several well-known families of graphs.  Our hope is that these examples illustrate the advantages of the scramble number as a tool for computing gonality, as our constructions are relatively simple in comparison to the preexisting literature.

Our examples all arise as Cartesian products of graphs.  Recall that the Cartesian product of two graphs $G_1$ and $G_2$, denoted $G_1 \mathbin{\square} G_2$, is the graph with vertex set $V(G_1) \times V(G_2)$ and an edge between $(u_1, u_2)$ and $(v_1, v_2)$ if either $u_1 = v_1$ and there is an edge between $u_2$ and $v_2$, or $u_2 = v_2$ and there is an edge between $u_1$ and $v_1$.  For a fixed vertex $v \in G_1$, we refer to the set
\[
C_v = \Big\{ (v,w) \in V(G_1 \mathbin{\square} G_2) \vert w \in G_2 \Big\}
\]
as a \emph{column}.  Similarly, for $w \in G_2$, we refer to the set
\[
R_w = \Big\{ (v,w) \in V(G_1 \mathbin{\square} G_2) \vert v \in G_1 \Big\}
\]
as a \emph{row}.  A bound on the gonality of Cartesian products can be found in \cite{AidunMorrison}.

\begin{proposition}\cite[Proposition~3]{AidunMorrison}
\label{Prop:ProductBound}
For any two graphs $G_1$ and $G_2$,
\[
\mathrm{gon}(G_1 \mathbin{\square} G_2) \leq \min \Big\{ \mathrm{gon}(G_1) \vert V(G_2) \vert, \mathrm{gon}(G_2) \vert V(G_1) \vert \Big\} .
\]
\end{proposition}

We provide several examples where this bound is achieved.  It is a standard result that the $m \times n$ grid graph has treewidth $\min \{ m,n \}$, and it is shown in \cite{dbG} that such graphs have gonality $\min \{ m,n \}$ as well.  A grid graph is an example of the product of two trees, a family of graphs whose gonality is computed in \cite{AidunMorrison}.  We reproduce this result here using the scramble number.

\begin{proposition}\cite[Proposition~11]{AidunMorrison}
If $T_1$ and $T_2$ are trees, then
\[
\mathrm{gon} (T_1 \mathbin{\square} T_2) = \mathrm{sn} (T_1 \mathbin{\square} T_2) = \min \Big\{ \vert V(T_1) \vert, \vert V(T_2) \vert \Big\} .
\]
\end{proposition}

\begin{proof}
By Proposition~\ref{Prop:ProductBound}, the gonality of $T_1 \mathbin{\square} T_2$ is at most $\min \{ \vert V(T_1) \vert, \vert V(T_2) \vert \}$.  We therefore seek to bound the gonality from below.  By Theorem~\ref{Thm:Bound}, it suffices to construct a scramble of scramble order $\min \{ \vert V(T_1) \vert, \vert V(T_2) \vert \}$.

Let $\mathscr{S}$ be the set of columns in $T_1 \mathbin{\square} T_2$.  Any row $R_w$ is a hitting set for $\mathscr{S}$, and $\vert R_w \vert = \vert V(T_1) \vert$.  Moreover, if $v \in T_1$ is a leaf, then $\vert E( C_v , C_v^c ) \vert = \vert V(T_2) \vert$.  It follows that
\[
\vert \vert \mathscr{S} \vert \vert \leq \min \Big\{ \vert V(T_1) \vert, \vert V(T_2) \vert \Big\} .
\]

Since the number of columns is $\vert V(T_1) \vert$ and they are disjoint, there is no hitting set of size less than $\vert V(T_1) \vert$.  Now, let $A$ be a subset of $V(T_1 \mathbin{\square} T_2)$ with the property that both $A$ and $A^c$ contain a column.  Then every row of $T_1 \mathbin{\square} T_2$ contains a vertex in $A$ and a vertex in $A^c$, so every row contains an edge in $E(A,A^c)$.  It follows that $\vert E(A,A^c) \vert$ is greater than or equal to the number of rows, which is $\vert V(T_2) \vert$, hence
\[
\vert \vert \mathscr{S} \vert \vert \geq \min \Big\{ \vert V(T_1) \vert, \vert V(T_2) \vert \Big\} .
\]
\end{proof}

In \cite{Morrison}, the authors compute the treewidth of the \emph{stacked prism graphs} $Y_{m,n}$, the product of a cycle with $m$ vertices and a path with $n$ vertices.  They show that the gonality of $Y_{m,n}$ is equal to its treewdith, except in the special case where $m = 2n$.  We prove the following generalization, which holds even in this special case.  Even in the cases where the gonality has been previously computed, we believe that our constructions, using scrambles rather than brambles, are much simpler.  For this reason, we have treated these graphs for all $m$ and $n$ uniformly.

\begin{proposition}
\label{Prop:StackedPrism}
If $C$ is a cycle and $T$ is a tree, then
\[
\mathrm{gon} (C \mathbin{\square} T) = \mathrm{sn} (C \mathbin{\square} T) = \min \Big\{ \vert V(C) \vert, 2 \vert V(T) \vert \Big\} .
\]
\end{proposition}

\begin{proof}
By Proposition~\ref{Prop:ProductBound}, we have $\mathrm{gon} (C \mathbin{\square} T) \leq \min \{ \vert V(C) \vert, 2\vert V(T) \vert \}$.  We now compute a lower bound.  By Theorem~\ref{Thm:Bound}, it suffices to construct a scramble of scramble order $\min \{ \vert V(C) \vert, 2 \vert V(T) \vert \}$.

Again, we let $\mathscr{S}$ be the set of columns in $C \mathbin{\square} T$.  (See, for example, Figure~\ref{Fig:StackedPrism}.)  Any row $R_w$ is a hitting set for $\mathscr{S}$, and $\vert R_w \vert = \vert V(C) \vert$.  Moreover, for any $v \in C$ we have $\vert E( C_v , C_v^c ) \vert = 2 \vert V(T) \vert$.  It follows that
\[
\vert \vert \mathscr{S} \vert \vert \leq \min \Big\{ \vert V(C) \vert, 2 \vert V(T) \vert \Big\} .
\]

Since the number of columns is $\vert V(C) \vert$ and they are disjoint, there is no hitting set of size less than $\vert V(C) \vert$.  Now, let $A$ be a subset of $V(C \mathbin{\square} T)$ with the property that both $A$ and $A^c$ contain a column.  Then every row of $C \mathbin{\square} T$ contains a vertex in $A$ and a vertex in $A^c$, so every row contains at least two edges in $E(A,A^c)$.  It follows that $\vert E(A,A^c) \vert$ is greater than or equal to twice the number of rows, which is $\vert V(T) \vert$, hence
\[
\vert \vert \mathscr{S} \vert \vert \geq \min \Big\{ \vert V(C) \vert, 2 \vert V(T) \vert \Big\} .
\]
\end{proof}

\begin{figure}[h]

\begin{tikzpicture}
\draw (0,1) circle (3pt);
\draw (1,0) circle (3pt);
\draw (1,1) circle (3pt);
\draw (0,0) circle (3pt);
\draw (2,2) circle (3pt);
\draw (2,-1) circle (3pt);
\draw (-1,2) circle (3pt);
\draw (-1,-1) circle (3pt);
\draw (0,0)--(1,0);
\draw (0,0)--(0,1);
\draw (0,1)--(1,1);
\draw (1,0)--(1,1);
\draw (2,2)--(2,-1);
\draw (2,2)--(-1,2);
\draw (-1,-1)--(2,-1);
\draw (-1,-1)--(-1,2);
\draw (-1,-1)--(0,0);
\draw (2,-1)--(1,0);
\draw (-1,2)--(0,1);
\draw (2,2)--(1,1);
\filldraw[green] (0,1) circle (3pt);
\draw (0,1.3) node{G};
\filldraw[red] (1,0) circle (3pt);
\draw (1,-0.3) node{R};
\filldraw[blue] (1,1) circle (3pt);
\draw (1,1.3) node{B};
\filldraw[yellow] (0,0) circle (3pt);
\draw (0,-0.3) node{Y};
\filldraw[blue] (2,2) circle (3pt);
\draw (2,2.3) node{B};
\filldraw[red] (2,-1) circle (3pt);
\draw (2,-1.3) node{R};
\filldraw[green] (-1,2) circle (3pt);
\draw (-1,2.3) node{G};
\filldraw[yellow] (-1,-1) circle (3pt);
\draw (-1,-1.3) node{Y};
\end{tikzpicture}

\caption{The stacked prism graph $Y_{4,2}$ with a scramble of scramble order 4.  Note that, by \cite[Proposition~3.3]{Morrison}, the treewidth of $Y_{4,2}$ is only 3.}
\label{Fig:StackedPrism}
\end{figure}

Note that in the special case where $m = 2n$, Proposition~\ref{Prop:StackedPrism} shows that the scramble number of the stacked prism graph $Y_{m,n}$ can be strictly greater than the treewidth.  In \cite{Morrison}, the authors also compute the treewidth of the \emph{toroidal grid graphs} $T_{m,n}$, the product of a cycle with $m$ vertices and a cycle with $n$ vertices.  They further show that the gonality of $T_{m,n}$ is equal to its treewidth, except in the special cases where $m = n $ or $m = n \pm 1$.  As with the stacked prism graphs, we compute the gonality of these graphs for all $m$ and $n$ uniformly, including the cases not covered in \cite{Morrison}.

\begin{proposition}
For all $m,n \geq 2$, we have
\[
\mathrm{gon}(T_{m,n}) = \mathrm{sn}(T_{m,n}) = \min \{ 2m, 2n \} .
\]
\end{proposition}

\begin{proof}
By Proposition~\ref{Prop:ProductBound}, $\mathrm{gon}(T_{m,n}) \leq \min \{ 2m, 2n \}$, so we will compute a lower bound.  By Theorem~\ref{Thm:Bound}, it suffices to construct a scramble of scramble order $\min \{ 2m, 2n \}$.  Let
\[
\mathscr{S} = \Big\{ C_v \smallsetminus \{ (v,w) \} \mid (v,w) \in V(T_{m,n}) \Big\}
\]
be the set of columns in $T_{m,n}$ with one vertex removed.  (See, for example, Figure~\ref{Fig:Torus}.)  The union of any two rows is a hitting set for $\mathscr{S}$ of size $2m$.  Moreover, for any vertex $v$ in the cycle of length $m$, we see that both $C_v$ and $C_v^c$ contain an egg, and we have $\vert E( C_v , C_v^c ) \vert = 2n$.  It follows that
\[
\vert \vert \mathscr{S} \vert \vert \leq \min \{ 2m, 2n \} .
\]

If $C$ is a subset of the vertices of size less than $2m$, then some column contains at most 1 vertex of $C$, hence $C$ is not a hitting set for $\mathscr{S}$.  Now, let $A$ be a subset of $V(T_{m,n})$ with the property that both $A$ and $A^c$ contain eggs.  Specifically, suppose that $A$ contains every vertex in column $C_v$ except for possibly $(v,w)$, and that $A^c$ contains every vertex in column $C_{v'}$ except for possibly $(v',w')$.  Note that, if $n \geq 3$, then we must have $v \neq v'$.  If $n=2$ and $v=v'$, then the $4=2n$ edges in column $C_v$ are all contained in $E(A,A^c)$.  We now assume that $v \neq v'$, and consider the rows of $T_{m,n}$.  Note that the only row that may be contained in $A$ is $R_{w'}$, and the only row that may be contained in $A^c$ is $R_w$.  If neither $A$ nor $A^c$ contains the row $R_{w''}$, then at least two edges in $R_{w''}$ are contained in $E(A,A^c)$.  We therefore see that the number of row-edges in $E(A,A^c)$ is at least:
\[
\left\{ \begin{array}{ll}
2n-4 & \textrm{if $R_{w'} \subseteq A$ and $R_w \subseteq A^c$} \\
2n-2 & \textrm{if one of $R_{w'} \subseteq A$ or $R_w \subseteq A^c$} \\
2n & \textrm{otherwise.}
\end{array} \right.
\]

We now consider column-edges.  If $R_w \subseteq A^c$, then since $A$ contains $C_v \smallsetminus \{ (v,w) \}$, we see that the two edges in column $C_v$ with endpoints $(v,w)$ are contained in $E(A,A^c)$.  Similarly, if $R_{w'} \subseteq A$, then the two edges in column $C_{v'}$ with endpoints $(v',w')$ are contained in $E(A,A^c)$.  It follows that $\vert E(A,A^c) \vert \geq 2n$, hence
\[
\vert \vert \mathscr{S} \vert \vert \geq \min \{ 2m , 2n \} .
\]
\end{proof}

\begin{figure}[h]

\begin{tikzpicture}
\filldraw[green] (0,0) circle (3pt);
\draw (0,0.3) node{G};

\filldraw[green] (0,2) circle (3pt);
\draw (0,2.3) node{G};
\filldraw[green] (0,3) circle (3pt);
\draw (0,3.3) node{G};
\filldraw[blue] (2,0) circle (3pt);
\draw (2,0.3) node{B};
\filldraw[blue] (2,1) circle (3pt);
\draw (2,1.3) node{B};

\filldraw[blue] (2,3) circle (3pt);
\draw (2,3.3) node{B};
\draw (0,0) circle (3pt);
\draw (0,1) circle (3pt);
\draw (0,2) circle (3pt);
\draw (0,3) circle (3pt);
\draw (1,0) circle (3pt);
\draw (1,1) circle (3pt);
\draw (1,2) circle (3pt);
\draw (1,3) circle (3pt);
\draw (2,0) circle (3pt);
\draw (2,1) circle (3pt);
\draw (2,2) circle (3pt);
\draw (2,3) circle (3pt);
\draw (3,0) circle (3pt);
\draw (3,1) circle (3pt);
\draw (3,2) circle (3pt);
\draw (3,3) circle (3pt);

\end{tikzpicture}

\caption{Two representative eggs in $T_{4,4}$.}
\label{Fig:Torus}
\end{figure}

\bibliographystyle{alpha}
\bibliography{ref}

\end{document}


TITLE: Classical Limit of Schwarzschild Metric
QUESTION [0 upvotes]: The orbit of a test particle orbiting a black hole can be described by the Lagrangian
$$\mathcal{L} = -\frac{1}{2}\left(-\left(1-\frac{2 G m}{c^2 r}\right) \dot{t}^2 + \left(1-\frac{2 G m}{c^2 r}\right)^{-1}\dot{r}^2 + r^2 \dot{\varphi^2}\right),$$
where the dot denotes the derivative with aspect to a parameter $s$, and $m$ is the mass of the black hole.
In the classical limit $c \rightarrow \infty$, so that the terms $\propto G$ vanish. So if the Equations of Motion, from Eulers Equations, are written down, which also show that $t = s$, there are no terms containing $G$, since they all vanish in the considered limit.
But since we are talking about the classical limit, and about a test particle, the Lagrangian is of the form
$$ \tilde{\mathcal{L}} = \frac{m_{Testparticle}v^2}{2} + \frac{G m m_{Testparticle}}{r},$$ so there are terms containing $G$ and therefor the potential energy.
To me, this seems to be contradictory.

REPLY [1 votes]: I see a couple problems here.  First off, there's a mistake in your Lagrangian.  If you're going to use non-geometrized units, you should probably be consistent about it.
\begin{equation}
  \mathcal{L} = -\frac{1}{2}\left[-\left(1-\frac{2 G m}{c^2 r}\right) c^2 \dot{t}^2 + \left(1-\frac{2 G m}{c^2 r}\right)^{-1}\dot{r}^2 + r^2 \dot{\varphi^2}\right].
\end{equation}
Note the extra $c$ in the time term.
Now, the $c \to \infty$ limit looks dubious.  This should be your clue that it's not such a meaningful limit; it's more of a hand-wavy mnemonic.  In fact, the Newtonian limit is $v/c \to 0$, which is different as you've just discovered.  If you expand in powers of $v/c$, this is called a "post-Newtonian" expansion.
In fact, in your version you've effectively taken the limit $2Gm/c^2 r \to 0$, which is the classical limit of flat spacetime.  What you've done is taken the lowest-order term in a "post-Minkowski" expansion.  You've simply found that removing curvature from GR removes gravity.  If you want to find Keplerian gravity, just do the expansion, and keep another term around.
Of course, you always need to be careful when interchanging the orders of limits (which includes taking derivatives here).