TITLE: Rolling A Die Question
QUESTION [0 upvotes]: When we roll a single six-sided die, what is the probability of rolling 3 even and 1 odd number?
I want to solve this using $P(E) = \frac{|E|}{|S|}$ where $|E|$ is the event space, and $|S|$ is the sample space.
I can get the sample space: $|S| = 6^4$ because we are dealing with a six-sided die being rolled four times.
But how do you get the event space for this? I know getting an even number of one roll is $\frac{1}{2}$ and same with an odd, but would it maybe be $3^4 + 1^4$ because we want three even numbers and one odd number?

REPLY [1 votes]: In how many ways can you put the $1$ odd die? $4$
In how many ways can you choose a even number in one trial? $3$ ( in three,instead?)
In how many ways can you choose a odd number in one trial? $3$
So the probability is $\frac{4\cdot 3^4}{6^4} = \frac{1}{4}  $
In these cases, one good way to think it's to build a 'mental tree' of the sample space and to distinguish the branches in the event space.


TITLE: How to solve $\frac{dy}{dx} = 1 + xy$?
QUESTION [0 upvotes]: I tried to solve this as linear differential equation but integrating factor is like an error function. I tried in other methods but there is no result. Please mention the solution if you know.
$$\frac{dy}{dx}=1+xy$$

REPLY [0 votes]: There is an advanced approach, I don't know if this could help. Let $u=u(x,y)$. Using the characteristic method for solving PDE, we have $\frac{u_x}{u_y}=-\frac{dy}{dx}=-(1+xy)$. This implies that
\begin{align}
u_x+(1+xy)u_y
=0 \qquad\qquad (1)
\end{align}
Assume that $u(x,y):={\rm{e}}^{\alpha x + \beta y}$ is a solution; where $\alpha$ and $\beta$ are arbitrary constants. Substitute in the equation $(1)$, we get
\begin{align}
\alpha {\rm{e}}^{\alpha x + \beta y}+\beta(1+xy) {\rm{e}}^{\alpha x + \beta y}=\left[\alpha+\beta(1+xy)\right] {\rm{e}}^{\alpha x + \beta y}=0
\end{align}
but ${\rm{e}}^{\alpha x + \beta y}\ne 0$ for all $x,y$ and $\alpha,\beta$. So that we have $\alpha+\beta(1+xy)=0$
\begin{align}
\alpha=-\beta(1+xy) \qquad \qquad \qquad \qquad(2)
\end{align}
Thus,
\begin{align}
u(x,y):={\rm{e}}^{\alpha x + \beta y}= {\rm{e}}^{-\beta(1+xy) x + \beta y}= {\rm{e}}^{-\beta(x+x^2y) + \beta y}
\end{align}
which gives an implicit solution of the D.E.


TITLE: $f : \mathbb R \to \mathbb R $ be a differentiable and $f'(x) $ is bounded function then $f$ is unbounded.
QUESTION [3 upvotes]: $f : \mathbb R \to \mathbb R $ be a differentiable function with $f(0) =0$. If for all $x \in \mathbb R , 1< f'(x) < 2$ then $f$ is unbounded.
We know that when $f'(x) > 0$ then $f$ is increasing and when $f'(x)$ is bounded then $f$ is uniformly continuous. From there how can we conclude that $f$ is unbounded??

REPLY [1 votes]: Or, using the fundamental theorem of calculus instead of the mean value theorem, we have, for $x \ge 0$, and any value of $f(0)$,
$f(x) - f(0) = \int_0^x f'(s) ds \ge \int_0^x (1) ds = (1)(x - 0) = x; \tag{1}$
thus
$f(x) \ge x + f(0) \to \infty \;\; \text{as} \; \;x \to \infty; \tag{2}$
and likewise, for $x \le 0$,
$f(0) - f(x) = \int_x^0 f'(s) ds \ge \int_x^0 (1) ds = (1)(0 - x) = -x; \tag{3}$
that is,
$f(0) -f(x) \ge -x, \tag{4}$
or
$f(x) \le x + f(0) \to -\infty \;\; \text{as} \;\; x \to  -\infty, \tag{5}$
showing $f(x)$ is unbounded in either direction.  QED!
NB: We observe, with copper.hat, that the assumption $f(x) \ge \epsilon$ for any $\epsilon  > 0$ is also sufficient to yield the same result.


TITLE: Choosing a dominated sequence with certain properties
QUESTION [1 upvotes]: Given a sequence $\{d_{m}\}_{m\in{\bf{Z}}^{n}}$ of nonnegative numbers with $d_{m}\rightarrow 0$ as $|m|\rightarrow\infty$, I am looking for a sequence $\{a_{j}\}_{j\in{\bf{Z}}}$ such that the product $a_{m_{1}}\cdots a_{m_{n}}\geq d_{(m_{1},...,m_{n})}$ and $a_{j}\rightarrow 0$ as $|j|\rightarrow\infty$, does anyone here know how to construct explicitly such a sequence $\{a_{j}\}_{j\in{\bf{Z}}}$?

REPLY [0 votes]: I suppose $|(m_1, \dots, m_n)|:= \max_{i=0}^n |m_i|$.
Then we can take an increasing sequence $(M_k)_{k\in\mathbb{N}}\subset\mathbb{N}$ s.t.
\begin{eqnarray}
|m|\geq M_k \Rightarrow d_m < \frac{1}{k^n}.
\end{eqnarray}
Let $X:=\max\{1, \max_{m\in\mathbb{Z}^n}d_m\}^{1/n}$ and put
\begin{eqnarray}
a_j :=
\begin{cases}
X & (|j|<M_1)\\
\frac{1}{k} & (M_k \leq |j| < M_{k+1}).
\end{cases}
\end{eqnarray}


text:
\section{The \LCycle-cycle detection data structure}\label{sec:cyc_det_ds}

\CycleNote

Our goal in this section is to derive an analogue of Lemma~\ref{lem:kpath-bnd-td} for the $\geq k${\sc{-Cycle}} problem. That is, we are going to design a data structure that for a dynamic graph $G$, modified over time by edge insertions and removals, recognizes whether $G$ contains a cycle on at least $k$ vertices. More precisely, the data structure works under the invariant that this is never the case, and refuses any edge insertion that breaks this~invariant.

The main idea is to combine the data structure presented in the previous section with the top-tree data structure~\cite{AlstrupIP,AlstrupJ}, which we recall next.

\paragraph{Top trees.} The top trees data structure~\cite{AlstrupIP,AlstrupJ} maintains a dynamic forest $\Upsilon$ subject to edge insertions and deletions. Contrary to forests we maintained so far, $\Upsilon$ is not rooted, that is, it is a union of unrooted trees.

The top tree data structure is designed to aggregate information along paths in the maintained forest $\Upsilon$. The idea is that each tree $S$ in forest $\Upsilon$ is assigned a pair $\partial S$ of (not necessarily distinct) vertices in $S$, called the {\em{boundary}} of $S$. The purpose of distinguishing the boundary vertices is to be able to easily access the information associated with the unique path between them within $S$. This information has to be aggregated when the forest $\Upsilon$ changes, and to do this efficiently, the path information is distributed in a binary tree called the \emph{top tree}. We outline next the most important properties of top trees, but for details we refer to~\cite{AlstrupIP,AlstrupJ}.

So as mentioned before, for each pair $(S,\partial S)$ a (rooted and binary) top tree $\Lambda(S,\partial S)$ is constructed and maintained. The top tree construction is based on a recursive partition of $S$ into clusters, each cluster $C$ having its own boundary pair of vertices $\partial C$.
For a connected subtree $C$ of $S$, a boundary vertex is a vertex of $C$ that is either a vertex of $\partial S$, or a neighbor of a vertex not in $C$. We say that $C$ is a {\em{cluster}} of $S$ if it has at most two boundary vertices $x,y$; then $\partial C = \{x,y\}$. Moreover, if $x \neq y$, we call $C$ a path cluster. The recursive partition into clusters starts with the root cluster, which is $S$ itself. A cluster $C$ is partitioned into clusters $A$ and $B$, where $A$ and $B$ share one boundary vertex, and $(\partial A \cup \partial B) \setminus (\partial A \cap \partial B) \subseteq \partial C \subseteq (\partial A \cup \partial B)$.
In the top tree $\Lambda(S,\partial S)$ cluster $C$ becomes a parent of $A$ and $B$. The leafs of $\Lambda(S,\partial S)$ are  clusters containing single edge, one per each edge of $S$.

The partition procedure (which we do not describe here, see~\cite{AlstrupJ}) guarantees that the height of each top tree $\Lambda(S,\partial S)$ is $\Oh(\log |S|)$.
The top trees data structure provides the following methods for updating the forest $\Upsilon$:
\begin{itemize}[nosep]
 \item $\link(u,v)$: Given vertices $u,v$ lying in different trees of $\Upsilon$, links these trees by adding the edge $uv$ to $\Upsilon$.
 \item $\cut(e)$: Remove the edge $e$ from $\Upsilon$.
 \item $\expose(u,v)$: Return $\nil$ if $u$ and $v$ are not in the same tree of $\Upsilon$. Otherwise, if $S$ is the tree that contains $u$ and $v$, then the top tree $\Lambda(S,\partial S)$ is rebuilt so that $u$ and $v$ become the boundary vertices of its root cluster. This new root cluster is returned by the method.
\end{itemize}

As presented in~\cite{AlstrupIP,AlstrupJ}, the top tree data structure can be enriched by additionally storing some piece of information about each cluster. Here, one assumes that these pieces of information are compositional, in the sense that the information for child clusters can be aggregated to the information about the parent cluster. Actually, the example provided by Alstrup et al. in~\cite{AlstrupJ} in Lemma~$5$ is exactly the one we need here: for a path cluster $C$ one can store the length of the path within $C$ between the boundary vertices of $C$. This leads to an implementation of the following query with worst-case running time $\Oh(\log n)$:
\begin{itemize}[nosep]
 \item $\pathlf(u,v)$: Given vertices $u$ and $v$, return the length of the $u$-to-$v$ path in $\Upsilon$, or $\infty$ if $u$ and $v$ are in different trees of $\Upsilon$.
\end{itemize}
In our application, we will also need to efficiently report $u$-to-$v$ paths assuming they are short. The following lemma summarizes all that we need from the top tree data structure.

\begin{comment}
Each of these methods is implemented as a sequence of the following two local operations:
\begin{itemize}[nosep]
 \item $\merge(A,B)$: Given clusters $A$ and $B$ sharing one boundary vertex, create a new cluster $C$ with children $A$ and $B$, whose boundary $\partial C$ are the boundary nodes of $A$ and $B$ excluding the shared boundary vertex. The method returns the new cluster $C$.
 \item $\splitt(C)$: Given the root cluster $C$ of a top tree $\Lambda(C,\partial C)$ that has children $A$ and $B$, delete $C$ and thus turn $\Lambda(C,\partial C)$ into two top trees: $\Lambda(A,\partial A)$ and $\Lambda(B,\partial B)$.
\end{itemize}
The following theorem connects $\merge$ and $\splitt$ operations with $\link$, $\cut$ and $\expose$.
\begin{theorem}
[\cite{AlstrupIP,AlstrupJ}]\label{thm:alstrup} For a dynamic forest $\Upsilon$ on $n$ vertices we can maintain top trees of height $\Oh(\log n)$ supporting each of $\link$, $\cut$, or $\expose$ with a sequence of $\Oh(\log n)$ operations $\splitt$ and $\merge$. Here the sequence itself is identified in $\Oh(\log n)$ time. The space usage of the top trees is linear in $n$.
\end{theorem}

\newcommand{\len}{\mathsf{len}}

We enrich the top tree data structure as follows: for each pair $(C,\partial C)$ appearing in the data structure, we remember a single integer $\len(C,\partial C)$ equal to the length of the unique path in $C$ between the two vertices in $\partial C$. Note that $\len(C,\partial C)=0$ if the boundary of $C$ consists of only one vertex. Since this information can be recomputed during the $\merge$ and $\splitt$ operations without any overhead in the asymptotic running time, by Theorem~\ref{thm:alstrup} we may assume that our top tree data structure is equipped with it.
\end{comment}

\begin{lemma}\label{lem:TT}
  There is a top trees data structure $\Topt[\Upsilon]$ which maintains a dynamic forest $\Upsilon$ on $n$ vertices subject to edge additions and removals. The data structure provides the following methods:
\begin{itemize}[nosep]
 \item $\link(u,v)$: Given vertices $u$ and $v$, if $u$ and $v$ lie in the same tree of $\Upsilon$, do nothing and return $\false$. Otherwise, add the edge $uv$ to $\Upsilon$ and return $\true$.
 \item $\cut(e)$: Given an edge $e$ of $\Upsilon$, remove $e$ from $\Upsilon$.
 \item $\pathlf(u,v)$: Given vertices $u$ and $v$, return the length of the $u$-to-$v$ path in $\Upsilon$, or $\infty$ if $u$ and $v$ are in different trees of $\Upsilon$.
 \item $\pathf(u,v)$: Given vertices $u$ and $v$, return the $u$-to-$v$ path in $\Upsilon$, or $\nil$ if $u$ and $v$ are in different trees in $\Upsilon$.
\end{itemize}
All the methods run in worst case $\Oh(\log n)$ time with the exception of $\pathf(u,v)$, which runs in worst case time $\Oh(|\pi| \cdot \log n)$, where $\pi$ is the returned path. The data structure uses $\Oh(|\Upsilon|)$ space.
\end{lemma}
\begin{proof}
 The data structure is the variant of the top tree data structure described in~\cite{AlstrupIP,AlstrupJ} that in addition to the basic data, also stores, for each cluster $C$, the length of the path within $C$ between the vertices of the boundary of $C$. As shown in~\cite{AlstrupIP,AlstrupJ}, the first three operations can be implemented in this data structure with worst-case running time $\Oh(\log n)$. Hence, it remains to implement the query $\pathf(u,v)$.

 For $\pathf(u,v)$, we first apply $\expose(u,v)$.  This method either reports that $u$ and $v$ are in different trees of $\Upsilon$ --- in which case we may return $\nil$ as the answer to the query --- or returns the cluster associated with the tree $S$ containing $u$ and $v$, after setting $\partial S$ to consist of $u$ and $v$. Then, we construct the $u$-to-$v$ path in $\Upsilon$ using a recursive procedure $\pathf(C)$ that for a path cluster $C$, given as a node in $\Topt[\Upsilon]$ and where $\partial C$ consists of two different vertices,
 returns the path $\pi(C)$ connecting the vertices of $\partial C$ within $C$. This procedure works as follows. If $C$ is a leaf cluster, then return the single edge of $C$. Otherwise, if $A$ and $B$ are the child clusters of $C$, then return the concatenation of $\pi(A)$, computed using a recursive call $\pathf(A)$, and $\pi(B)$, computed using a recursive call $\pathf(B)$. Here, if either $\partial A$ or $\partial B$ consist of only one vertex, then ignore the corresponding recursive call.

 Observe, that we only call the recursion on path clusters. Now, for the analysis, we distinguish two types of recursive calls: the first type recurses on both children or is called on a path cluster consisting of a single edge, and the second type recurses on one child only. Observe that the total number of calls of the first type is bounded by $\Oh(|\pi(S)|)$, as each such call can be attributed either to a distinct edge of $\pi(S)$, or to splitting $\pi(S)$ into two nonempty paths. Furthermore, after a sequence of $\Oh(\log |S|)$ calls of the second type there must be a call of the first type.
 Thus, the procedure $\pathf(S)$ constructs the sought path $\pi(S)$ in time $\Oh(|\pi(S)| \cdot \log n)$.
\end{proof}

\paragraph*{The data structure.}
Equipped with the top trees data structure we are ready to prove the main result of this section, stated in the following lemma.

\begin{lemma}\label{lem:kcycle-restricted}
Let $k$ be a fixed parameter.
Suppose we are given a dynamic graph $G$, updated by edge insertions and removals, and access to a dictionary on the edges of $G$, which uses $\mdict$ memory and each dictionary operation runs in time bounded by $\tdict$.
Then there is a dynamic data structure that maintains $G$ under such updates as long as the following invariant holds: $G$ does not contain a simple cycle on at least $k$ vertices. If an edge insertion violates this invariant, the data structure refuses to carry out the insertion and reports this outcome. The data structure uses $(n \cdot 2^{\Oh(k^2 \log k)} + \mdict)$ memory and guarantees worst-case running time of $\Oh(k \log n)+2^{\Oh(k^2 \log k)} \tdict + 2^{\Oh(k^4)}$ per operation. The initialization for an edgeless graph on $n$ vertices takes time $\Oh(n)$.
\end{lemma}
\begin{proof}
We may assume that $\tdict\leq \Oh(\log n)$.
The data structure maintains a top trees data structure $\Topt[\Upsilon]$, provided by Lemma~\ref{lem:TT}, in which we store a maximal spanning forest $\Upsilon$ of $G$. We note that the $\Topt[\Upsilon]$ structure is completely oblivious of the edges of $E(G)\setminus E(\Upsilon)$, so we will need to ensure that $\Upsilon$ remains maximal while implementing edge insertions and deletions in $G$.

Moreover, we maintain the structure $\Tdep_{k^2,k}[G,\Prt]$ provided by Lemma~\ref{lem:kpath-bnd-td-ms}, i.e., the structure $\Tdep_{d,k}[G,\Prt]$ for $d=k^2$. This structure maintains a nice partition $\Prt$ of $G$ that will at all times coincide with the partition of $G$ into biconnected components, except that methods that we use for edge insertion and removal may temporarily change $\Prt$ into a coarser nice partition, but by the time a method terminates, $\Prt$ becomes the partition into biconnected components again. As we assume the invariant that $G$ never contains a cycle of length at least $k$, by Lemma~\ref{lem:cycle-td} all the biconnected components of $G$ always have treedepth bounded by $k^2$. The memory usage is dominated by memory used by $\Tdep_{k^2,k}[G,\Prt]$ structure, which is $(n \cdot 2^{\Oh(k^2 \log k)} + \mdict)$ due to Lemma~\ref{lem:kpath-bnd-td-ms}.

We now move on to describing the procedures for inserting and removing edges.

\paragraph{Insert.} We start with procedure $\ins(uv)$ for inserting an edge (see Algorithm~\ref{alg:addcd} for a pseudocode). We start by verifying that $uv$ is not yet present in $G$, as otherwise there is nothing to do. Then we apply the query $\Topt[\Upsilon].\pathlf(u,v)$ to check the distance between $u$ and $v$ in $\Upsilon$ (see Lemma~\ref{lem:TT} for the interface of $\Topt[\Upsilon]$). We distinguish three cases.

The first case is when $\Topt[\Upsilon].\pathlf(u,v)$ returns $\infty$, meaning that $u$ and $v$ are not in the same connected component of $G$. Then, the newly added edge $uv$ becomes a bridge and hence it forms a new biconnected component of $G$. We use the method $\Tdep_{k^2,d}[G,\Prt].\new(uv)$ method to add up a new biconnected component $H=(\{ u,v \}, \{ uv \})$ to $\Prt$. We also update $\Upsilon$ by calling $\Topt[\Upsilon].\link(u,v)$. This case is handled in $\Oh(\log n)$ time, as the dominating operations are $\Topt[\Upsilon].\pathlf(u,v)$ and $\Topt[\Upsilon].\link(u,v)$.

The second case is when $\Topt[\Upsilon].\pathlf(u,v)$ returns a value that is larger or equal to $k$. Clearly, adding $uv$ in this case violates the invariant, as $uv$ closes the cycle of length at least $k$. Hence, if this is the case, the method terminates by throwing a suitable exception, and in particular the edge insertion is not carried out. Similarly as before, handling this case takes $\Oh(\log n)$ time.

We are left with the case when $\Topt[\Upsilon].\pathlf(u,v)$ returns a value smaller than $k$. In such case, we retrieve the entire path $\pi$ in $\Upsilon$ between $u$ and $v$ using $\Topt[\Upsilon].\pathf(u,v)$; this takes time $\Oh(k\log n)$. We use this path to merge the biconnected components along $\pi$. More precisely, observe that $\pi$ can be partitioned into subpaths $\pi_1,\ldots,\pi_\ell$ so that $\pi_1$ is contained in a biconnected component $H_1$, $\pi_2$ is contained in another biconnected component $H_2$, and so on. What should happen after inserting the edge $uv$ to $G$, is that all these biconnected component $H_1,\ldots,H_\ell$ should be merged into one part of $\Prt$, to which $uv$ should be inserted --- this new, merged part $H$ is a new biconnected component after the insertion. To simulate this, we iterate through the edges on $\pi$ and if for two consecutive edges $xy$ and $yz$ we find out that they belong to different parts in $\Prt$ --- which can be checked using method $\same(xy,yz)$ --- then we merge those parts using method $\merge(xy,yz)$. Note that at each point, method $\merge$ may report that the treedepth of the obtained graph is larger than $d=k^2$, in which case we roll back the changes and report  violation of the invariant. This is correct by Lemma~\ref{lem:cycle-td}, as we conclude that after adding $uv$, the biconnected component of $G$ containing $uv$ would have treedepth larger than $k^2$.

Finally, all the merges have been executed, and hence all the edges of $\pi$ are now in the same part of $\Prt$. We now verify whether adding $uv$ to $G$ does not break the invariant using query $\Tdep_{k^2,k}[G,\Prt].\pathlb(u,v,e_u,e_v)$, where $e_u$ and $e_v$ are respectively the first and the last edge of $\pi$. Recall that this query checks whether the part of $\Prt$ containing $e_u$ and $e_v$ contains a simple $u$-to-$v$ path on at least $k$ vertices, which at this point is equivalent to checking whether adding $uv$ to $G$ would create a cycle on at least $k$ vertices. If no violation of the invariant is discovered, we may safely add the edge $uv$ using method $\Tdep_{k^2,k}[G,\Prt].\ins(u,v,e_u,e_v)$.

As for the running time, observe that $\ell<k$, hence we use methods $\same$ and $\merge$ of $\Tdep_{k^2,k}[G,\Prt]$ at most $k$ times, which is followed by a single $\pathlb$ query and a single $\ins$ update. By Lemma~\ref{lem:kpath-bnd-td-ms}, this takes time $2^{\Oh(k^4)}+k^{\Oh(k^2)}\tdict$, which results in the total running time of $2^{\Oh(k^4)}+k^{\Oh(k^2)}\tdict + \Oh(k \log n)$ for the insertion procedure.

 \begin{algorithm}\label{alg:addcd}

     \SetKwInOut{Input}{Input}
     \SetKwInOut{Output}{Output}
    \SetKw{Raise}{raise exception:\ }

     \vskip 0.2cm

     \Input{An edge $uv$}
     \Output{The data structure is updated by inserting $uv$ to $G$}

     \vskip 0.1cm
     \If{$\Tdep_{k^2,k}[G,\Prt].\edge(uv)$} { \Return{}}
     $p \gets \Topt[\Upsilon].\pathlf(u,v)$ \\

     \If{ $p=\infty$ }
     {
        $\Tdep_{k^2,k}[G,\Prt].\new(uv)$ \\
        $\Topt[\Upsilon].\link(u,v)$ \\
        \Return
     }
     \If{ $k\leq p<\infty$ }
     {
          \Raise {\normalfont{long cycle detected}}
     }
     $\pi \gets \Topt[\Upsilon].\pathf(u,v)$
     \tcp*{$\pi[i]$ denotes the $i$th edge of $\pi$}
     \For{ $i \gets 1$ \normalfont{\textbf{to}} $p-1$ }
     {
        \If{ $\Tdep_{k^2,k}[G,\Prt].\same(\pi[i],\pi[i+1])$ }
        {
           $\Tdep_{k^2,k}[G,\Prt].\merge(\pi[i],\pi[i+1])$\\
           \If{\normalfont{exception is caught}}
           {
           roll back all the changes \\
           \Raise {\normalfont{long cycle detected}}
           }
        }

     }
     \If{$\Tdep_{k^2,k}[G,\Prt].\pathlb(u,v,\pi[1],\pi[p-1])$}
     {
       roll back all the changes \\
       \Raise {\normalfont{long cycle detected}}
     }
     $\Tdep_{k^2,k}[G,\Prt].\ins(u,v,\pi[1],\pi[p-1])$\\

     \caption{Edge insertion algorithm}
 \end{algorithm}

\paragraph{Remove.} We now move on to describing the method $\rem(uv)$ for removing an edge $uv$ from $G$ (see Algorithm~\ref{alg:remcd} for the pseudocode). Again, we start by checking whether $uv$ is present in $G$, as otherwise there is nothing to do. Then we check whether $uv$ is a bridge using method $\bridge(uv)$. If so, we remove it from $G$ and update the forest $\Upsilon$ appropriately.

Hence, from now on we may assume that $uv$ is not a bridge. Therefore, in the biconnected component $H$ of $G$ that contains $uv$ there is a $u$-to-$v$ path that does not use the edge $uv$. Observe that any such path cannot have more than $k-1$ vertices, for otherwise there would a cycle of length at least $k$ in $G$, violating the invariant assumptions. We find such a path $\pi$ by applying the $\pathub(i,u,v,uv,uv)$ method for all $i$ from $3$ to $k-1$.
Observe that if we now remove $uv$ from $H$, then all the cut-vertices in the obtained graph $H-uv$ lie on $\pi$. Hence, we may carry out the removal of $uv$ as follows.

First, we need to update $\Topt[\Upsilon]$ in case $uv \in E(\Upsilon)$. For this, we first remove $uv$ from $E(\Upsilon)$ by cutting $\Upsilon$ using $\Topt[\Upsilon].\cut(uv)$ method. We then find a substitution edge on $\pi$, that is, an edge of $\pi$ that connects two different trees of $\Upsilon$, and we insert it into $\Upsilon$ in place of $uv$.

Second, we remove $uv$ from $H$ by applying $\Tdep_{k^2,k}[G,\Prt].\rem(uv)$. This way $uv$ is removed from the part $H$ of $\Prt$, hence $H$ may break into several biconnected component $H_1,\ldots,H_\ell$. What remains to do is to update $\Prt$ by actually splitting $H$ into $H_1,\ldots,H_\ell$, so that we maintain the invariant that after the method is completed, $\Prt$ is the partition of the graph into biconnected components. Note here that each of the biconnected components $H_1,\ldots,H_\ell$ intersects $\pi$ on a non-empty subpath, so we may suppose that $\pi$ is split into subpaths $\pi_1,\ldots,\pi_\ell$ so that $\pi_i$ is the intersection of $H_i$ with $\pi$.

We now execute the split as follows. We iterate through the consecutive edges on $\pi$ and whenever we find two consecutive edges $xy$ and $yz$ such that $\art(xy,yz)$ yields $\true$, we should apply the $\splitt(xy,yz)$ method to appropriately split two parts of $\Prt$. There is a technical caveat here in that we cannot do it immediately, because the $\splitt$ method assumes that both parts resulting from the split should be biconnected. This, however, can be easily fixed by temporarily adding the edge $yv$ before the split, and removing it after the split. It is straightforward to see that thus, the prerequisites of $\splitt$ are met. Moreover, the temporary insertion of the edge $yv$ could not increase the treedepth above $k^2$, because the obtained graph is a minor of the original biconnected component $H$.

This concludes the description of the method,
As for the running time, we use $\Oh(k)$ operations in the data structure $\Topt[\Upsilon]$, each taking $\Oh(\log n)$ time, and $\Oh(k)$ operations in the data structure $\Tdep_{k^2,k}[G,\Prt]$, each taking at most $2^{\Oh(k^4)}+k^{\Oh(k^2)}\cdot \tau$ time. Hence, the total running time of the method is $2^{\Oh(k^4)}+k^{\Oh(k^2)} \tdict + \Oh(k \log n)$.

 \begin{algorithm}\label{alg:remcd}

     \SetKwInOut{Input}{Input}
     \SetKwInOut{Output}{Output}
    \SetKw{Break}{break}

     \vskip 0.2cm

     \Input{An edge $uv$}
     \Output{The data structure is updated by removing $uv$ from $G$}

     \vskip 0.1cm

     \If{{\normalfont{\textbf{not}}} $\Tdep_{k^2,k}[G,\Prt].\edge(uv)$}
     {
     \Return
     }

     \If{$\Tdep_{k^2,k}[G,\Prt].\bridge(uv)$}
     {
        $\Tdep_{k^2,k}[G,\Prt].\destroy(uv)$ \\
        $\Topt[\Upsilon].\cut(u,v)$ \\
        \Return
     }

     \For{$p \gets 3$ \normalfont{\textbf{to}} $k-1$}
     {
       $\pi \gets \Tdep_{k^2,k}[G,\Prt].\pathub(p,u,v,uv,uv)$\\
       \If{$\pi \neq \nil$}
       {\Break}
     }
     $\Tdep_{k^2,k}[G,\Prt].\rem(uv)$ \\

     \If{$uv \in E(\Upsilon)$ }
        {
        $\Topt[\Upsilon].\cut(uv)$ \;
        \For{$i\gets 1$ \normalfont{\textbf{to}} $p-1$}
        {\If{$\Topt[\Upsilon].\link(\pi[i])$}{\Break}}
        }

     \For{$i \gets 1$ \normalfont{\textbf{to}} $p-1$}
     {
        \If{$\Tdep_{k^2,k}[G,\Prt].\art(\pi[i],\pi[i+1])$}
        {
            $y\gets$ the common endpoint of $\pi[i]$ and $\pi[i+1]$\\
            \If{\normalfont{\textbf{not}} $\Tdep_{k^2,k}[G,\Prt].\edge(y,v)$} {
               $\Tdep_{k^2,k}[G,\Prt].\ins(y,v,\pi[i],\pi[p-1])$\\
               $a \gets \true$\\
            }
            $\Tdep_{k^2,k}[G,\Prt].\splitt(\pi[i],\pi[i+1])$\\
            \If{ $a$ } {
            $\Tdep_{k^2,k}[G,\Prt].\rem(yv)$\\
            }
        }
     }

     \caption{Edge removal algorithm}
 \end{algorithm}
\end{proof}

config: arxiv


TITLE: Is the product rule true in a Banach algebra?
QUESTION [1 upvotes]: Let $X$ be a Banach space and $\mathcal{L}(X)$ the Banach algebra of all bounded linear operators $L:X\to X$, where the norm is given by
$$\|L\|_\mathcal{L}=\sup\{\|L(x)\|_X;\;\|x\|_X=1\}$$
and the product is the composition of operators.
If $T,F:(0,\infty)\to\mathcal{L}(X)$ are differentiable functions, can we apply the product rule to derive $T(t)F(t)$?
Particularly, I'm interested in the case that $\{T(t)\}_{t\geq 0}$ and $\{F(t)\}_{t\geq 0}$ are both uniformly continuous semigroups of bounded linear operators.
Thanks.

REPLY [2 votes]: Yes, you can. For $h \ne 0$,
$$
\begin{align}
    & \frac{1}{h}\left[T(t+h)F(t+h)-T(t)F(t)\right]\\
    & =\frac{1}{h}\{T(t+h)-T(t)\}F(t+h)+T(t)\frac{1}{h}\{F(t+h)-F(t)\}\\
    & =\frac{1}{h}\{T(t+h)-T(t)\}F(t) + T(t)\frac{1}{h}\{F(t+h)-F(t)\} \\
    & + \frac{1}{h}\{T(t+h)-T(t)\}\{F(t+h)-F(t)\}
\end{align}
$$
Therefore,
$$
\begin{align}
      & \left\|\frac{1}{h}\left[T(t+h)F(t+h)-T(t)F(t)\right]-\left[T'(t)F(t)+T(t)F'(t)\right]\right\| \\
     & \le \left\|\frac{1}{h}[T(t+h)-T(t)]-T'(t)\right\|\|F(t)\|
       +\|T(t)\|\left\|\frac{1}{h}[F(t+h)-F(t)]-F'(t)\right\| \\
     & + \left\|\frac{1}{h}[T(t+h)-T(t)]\right\|\left\|\frac{1}{h}[F(t+h)-F(t)]\right\||h|.
\end{align}
$$
The right side tends to 0 as $h\rightarrow 0$ assuming that $T$ and $F$ are differentiable at $t$.


TITLE: An inequality: from the complex to the real case.
QUESTION [2 upvotes]: Let $p\in(1,2]$ and $q\in[2,\infty)$ be its conjugate exponent, then for $z,w\in\mathbb{C}$ the following inequality holds
$$
\Large \left|\frac{z+w}{2}\right|^q+\left|\frac{z-w}{2}\right|^q\leq\left[\frac{1}{2}\left(|z|^p+|w|^p\right)\right]^{\frac{1}{p-1}}\tag 1.
$$
The above inequality is a direct conseguence of the following inequality

If $1<p\le 2$ and $0\le t\le 1$, then $$\Large\left(\frac{1+t}{2}\right)^q+\left(\frac{1-t}{2}\right)^q\le \left(\frac{1}{2}+\frac{1}{2}t^p \right)^{\frac{1}{p-1}}\tag 2,$$ where $q=p/(p-1)$ is the exponent conjugate to $p$.

Question How can I get $(1)$ in the real case using the inequality $(2)$?

REPLY [0 votes]: Remark: I think you want to prove (1) for complex numbers using (2).
It is easy to prove that
$$(|z| + |w|)^2 + (|z| - |w|)^2
= |z + w|^2 + |z - w|^2,$$
$$(|z| + |w|)^2 \ge |z \pm w|^2.$$
Let $f(x) = x^{q/2}$.
Since $q = p/(p - 1) \ge 2$,
$f(x)$ is convex on $x\ge 0$. Using Karamata's inequality, we have
$$f\Big((|z| + |w|)^2\Big)
+ f\Big((|z| - |w|)^2\Big)
\ge f(|z + w|^2) + f(|z - w|^2)$$
that is
$$(|z| + |w|)^q + \Big||z| - |w|\Big|^q
\ge |z + w|^q + |z - w|^q.$$
Thus, it suffices to prove that
$$\left(\frac{|z| + |w|}{2}\right)^q + \left|\frac{|z| - |w|}{2}\right|^q \le \left(\frac{|z|^p + |w|^p}{2}\right)^{1/(p - 1)}.$$
WLOG, assume that $|z| \ge |w|$ and $|z| > 0$. Then $|w|/|z| \in [0, 1]$.
It suffices to prove that
$$\left(\frac{1 + |w|/|z|}{2}\right)^q + \left|\frac{1 - |w|/|z|}{2}\right|^q \le \left(\frac{1 + |w|^p/|z|^p}{2}\right)^{1/(p - 1)}$$
which is true using (2).


TITLE: Will a small solid body spin forever in a vacuum?
QUESTION [1 upvotes]: Given a small solid body like a small asteroid or satellite and some initial slow spin, for example 1 rotation every hour.
If placed in a perfect vacuum with no external forces will this spin forever?
The classical solution (where we approximate the object with a rigid body) will conserve angular momentum.
Is this true even if we acknowledge that the object might over very long timescales be deformed due to internal gravity, loss of heat to the environment through radiation, or through radioactive decay?
Assume infinite time, don't let the lifetime of the universe be a constraint.
If it does slow down why? What is violating the conservation of angular momentum?
I have tried to read about this and am ending up with articles about beta decay and how spin relates to angular momentum but I am not sure this is the right track.
I also found this question
How to model energy loss in a rotating body?
But this asks about modeling and I did not see the answer to my question among those answers.

REPLY [3 votes]: At the very least, a neutrally charged object that is rotating and is NOT a uniformly rotating axially symmetric body produces gravitational waves which clearly is a loss mechanism. Therefore, after some time, it will lose its entire energy.
Refer to Do rotating bodies emit gravitational waves? and https://www.ligo.caltech.edu/page/gw-sources for more details.


TITLE: Matlab Storing Vector after Iterations
QUESTION [0 upvotes]: I am having serious issues storing information in a vector after every iteration. Suppose that we have this code;
delta = 0;
figure(1)
while delta < 30
[t,x_]=Ass3(10,8/3,10+delta,100,1,1,1)
hold on
plot3(x_(:,1),x_(:,2),x_(:,3));
  grid on
  title('Changing Rho on x,y,z plane')
  xlabel('x Value')
  ylabel('y Value')
  zlabel('z Value')
  delta = delta + 5
end
Where Ass3 is another function from a different document.
I want to store a vector after every incremented 'delta'
I have attempted to use an if statement with lengths being less then the length of a different vector but nothing seems to be working.

REPLY [0 votes]: So before actually answering the question, i would recommend a slight edit for your code. As you know how the variable delta will change (starting at zero and increasing in steps of 5 as long as delta < 30), i would replace the while by a for loop.
If you know the length of the vector you want to store after each iteration (let's call this length l) then i would recommend the following:
delta = 0:5:25;
iterations = length(delta);
data = zeros(iterations,l)
figure(1)
for i = 1:iterations
  ...
  data(i,:) = YourVectorToSave;
end

The data array is preallocated here which is the best thing to do when you know how much iterations will be performed and how much data will be stored in each iteration.
If the size of the vector changes between different iterations (or the data is not a vector of doubles), i am not quite sure what i would call the best solution. As I would always recommend to avoid objects with changing size, a possible solution could be a cell array. This would lead to
delta = 0:5:25;
iterations = length(delta);
data = cell(1,iterations)
figure(1)
for i = 1:iterations
  ...
  data{i} = YourVectorToSave;
end


text:
\section{Separability in Uncountable Particular Point Space}
Tags: Separable Spaces, Particular Point Topology

\begin{theorem}
Let $T = \struct {S, \tau_p}$ be an [[Definition:Uncountable Particular Point Topology|uncountable particular point space]].
Let $H = S \setminus \set p$ where $\setminus$ denotes [[Definition:Set Difference|set difference]].
Then $H$ is not [[Definition:Separable Space|separable]].
\end{theorem}

\begin{proof}
By definition, $H$ is [[Definition:Separable Space|separable]] {{iff}} there exists a [[Definition:Countable Set|countable]] [[Definition:Subset|subset]] of $S$ which is [[Definition:Everywhere Dense|everywhere dense]] in $T$.
Let $V \subseteq H$ where $V$ is [[Definition:Countable Set|countable]].
$V$ is not [[Definition:Open Set (Topology)|open]] in $T$ as it does not contain $p$.
From [[Subset of Particular Point Space is either Open or Closed]] it follows that $V$ is [[Definition:Closed Set (Topology)|closed]].
From [[Closed Set Equals its Closure]], $V^- = V$.
But $V^- \ne H$ as $V$ is [[Definition:Countable Set|countable]] and $H$ is [[Definition:Uncountable Set|uncountable]].
So whatever $V$ is, if it is [[Definition:Countable Set|countable]] it is not [[Definition:Everywhere Dense|everywhere dense]].
The result follows from definition of [[Definition:Separable Space|separable]].
{{qed}}
\end{proof}

config: wiki


TITLE: Way to add scores in Fermi Quiz
QUESTION [1 upvotes]: I am setting up a Fermi Quiz. A quiz where you have to estimate the answers to complicated questions, your answers may be out by orders of magnitude.
A question may be:
"How many piano tuners are there in Chicago?"
The correct answer being around 290, however any answer between 140 and 580 is considered quite close.
What would be the best way to calculate the score for such a quiz.

REPLY [1 votes]: I have been thinking about this a lot, because i wanted to make something similar.
In my opinion the best method for scoring is based on the answers of the other participants in the quiz.
You get 100 points if the answer is exactly the right answer, otherwise you get 100 points minus the percentage of participants whose answer is better than yours.
An answer $A$ is better than yours if there are less answers between the correct answer and $A$ than between your answer and the correct answer.
This might seem difficult to calculate, but it is quite easy if you have the distribution of answers available.
Example: if the correct answer is $100$, and the set of answers is ${1,15,50,70,80,95,99,101,110,300,1000}$ the scores would be:
$1:0$ points
$15:10$ points
$50:20$ points
$70:40$ points
$80:60$ points
$95:80$ points
$99:100$ points
$101:100$ points
$110:80$ points
$300:60$ points
$1000:40$ points


TITLE: Prove that $a^2+b^2+c^2\geq [2(a-b)^2(b-c)^2(a-c)^2]^{1/3}$
QUESTION [3 upvotes]: Mathematica seems to know that this statement is true, yet I am struggling to prove it. Possible useful inequalities are Minkowski and the geometric mean. Using the geometric mean inequality I can prove a less strict bound:
$$(a-b)^2+(b-c)^2+(a-c)^2 \geq 0 \implies 4 a^2+4 b^2+4 c^2 \geq (a-b)^2+(b-c)^2+(a-c)^2,$$
then the geometric mean inequality gives
$$ (a-b)^2+(b-c)^2+(a-c)^2 \geq 3[(a-b)^2(b-c)^2(a-c)^2]^{1/3} .$$
Combining the two we get
$$  a^2+b^2+c^2 \geq  \frac{3}{4}[(a-b)^2(b-c)^2(a-c)^2]^{1/3},$$
which is not strong enough.
Can anyone prove this for $2^{1/3}$ in place of $3/4$?

REPLY [1 votes]: Here is another approach that might shed a bit more light on the essence of the inequality.

The AM-GM inequality gives
$$
\begin{align}
a^2+b^2+c^2
&=\frac{(a-b)^2+(b-c)^2+(c-a)^2+(a+b+c)^2}3\\
&\ge\frac{(a-b)^2+(b-c)^2+(c-a)^2}3\\
&\ge\left[(a-b)^2(b-c)^2(c-a)^2\right]^{1/3}\tag{1}
\end{align}
$$
Equality is attained in the second inequality of $(2)$ only when $(a-b)^2=(b-c)^2=(c-a)^2$, which cannot happen since $(a-b)+(b-c)+(c-a)=0$. This indicates that a better inequality may be possible.

If we set $x=a-b$ and $y=b-c$, we can look for the maximum of
$$
\frac{x^2y^2(x+y)^2}{\left(x^2+y^2+(x+y)^2\right)^3}=\frac{z^2(z+1)^2}{\left(z^2+1+(z+1)^2\right)^3}\tag{2}
$$
where $z=x/y$ ($y=0$ is certainly not the maximum). The derivative of the log of $(2)$ is
$$
\frac{2(2z+1)}{z(z+1)}-\frac{6(2z+1)}{z^2+1+(z+1)^2}=\frac{(2+z)(1-z)(1+2z)}{z(1+z)(1+z+z^2)}\tag{3}
$$
which vanishes where $z=-\frac12$, $z=1$, and $z=-2$. Each gives a value of $\frac1{54}$ in $(2)$. Therefore,
$$
\left(x^2+y^2+(x+y)^2\right)^3\ge54x^2y^2(x+y)^2\tag{4}
$$
Substituting back for $x$ and $y$ in $(4)$ gives
$$
\frac{(a-b)^2+(b-c)^2+(c-a)^2}3\ge\left[2(a-b)^2(b-c)^2(c-a)^2\right]^{1/3}\tag{5}
$$

To get the best inequality, we can use $(5)$ instead of the AM-GM:
$$
\begin{align}
a^2+b^2+c^2
&=\frac{(a-b)^2+(b-c)^2+(c-a)^2+(a+b+c)^2}3\\
&\ge\frac{(a-b)^2+(b-c)^2+(c-a)^2}3\\[6pt]
&\ge\left[2(a-b)^2(b-c)^2(c-a)^2\right]^{1/3}\tag{6}
\end{align}
$$


TITLE: Visualization of span of 3 vectors?
QUESTION [3 upvotes]: If I visualize 3 vectors in 3d space, is the span of the 3 vectors a 3d region within the 3 vectors? I need help visualizing so I can understand the concept better.

REPLY [13 votes]: Start of with the three vectors you know and assume they are all different from the zero vector (thus I don't want to span a point).
We start with taking the first vector. He can point in any direction. If the second vectors points in the same direction as the first one, we span a line. Also assume that the third vector also lies in the same direction, then we still span a line. You see, if all those three vectors lie in the same direction, you can only span a line.
If the second vector does not point in the same direction as the first one, we already span a plane.
Now you can take a third vector. If this vector point in the same direction as the plane, you still span the plane. If this vector does not point in the direction of the plane and thus uses your last dimension properly, you span a 3D space.


TITLE: Optimal Strategy for Deal or No Deal
QUESTION [8 upvotes]: When I have watched Deal or No Deal (I try not to make a habit of it) I always do little sums in my head to work out if the banker is offering a good deal. Where odds drop below "evens" it's easy to see it's a bad deal, but what would be the correct mathematical way to decide if you're getting a good deal?

REPLY [5 votes]: There are (at least) two factors that mean that simply calculating the average of the remaining options is not enough to describe how someone should play.

Risk aversion
Someone's utility is not a predictable function of the amount of money that they win. For instance my utility from winning $\$$5 is more than 100 times my utility from winning 5 cents. However, my utility from winning $\$$100 million is less than 100 times my utility from winning $\$$1 million.