TITLE: Using a summation factor to solve a recurrence
QUESTION [0 upvotes]: On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher
\begin{align}
n(n-1)a_n &=(n-1)(n-2)a_{n-1} + 2(n-1)\\
&=(n-2)(n-3)a_{n-2}+2(n-2)+2(n-1)\\
&=2(1+2+\cdots+n-1)\\
&=n(n-1)\\
a_n&=1
\end{align}
Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.

REPLY [2 votes]: $$
n(n-1)a_n = (n-1)(n-2)a_{n-1}+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_{n-1} = m(m-1)a_m$.  From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_{m-1}+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_{m-1} = k(k-1)a_k$.  We apply the recurrence again.
$$
n(n-1)a_n = \left[[(k-1)(k-2)a_{k-1}+2(k-1)]+2(m-1)\right]+2(n-1)
$$
And so on.  Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$.  This continues until we run out of positive terms.

REPLY [1 votes]: The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_{n-1} = (n-2)(n-3)a_{n-2}+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_{n-k} + \sum_{i=1}^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_{n-1}+2(n-1)$. Then $y_{n}-y_{n-1}=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.

REPLY [0 votes]: What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.


TITLE: Near-field energy transfer
QUESTION [1 upvotes]: If you absorb energy in the near field of the antenna, it will produce a loading effect on the source. Whereas in the far field it will not.
Is there an intuitive explanation why this is true for one type of the field and not the other?
Can the common electrical transformer be thought of as two antennas in each others near field?

REPLY [0 votes]: The far field is a traveling wave, once generated it radiates away from the source off into free space. The near field is a standing wave, which stores reactive energy. Your question as to why coupled near fields load each other and coupled far fields do not is not exactly correct; they both load each other in different ways.
For example, the transformer you described is coupled by a mutual inductance, a reactive coupling. An antenna has a radiation resistance, typically describing its ability to radiate into free space. This is a resistance and not a reactance because the power is lost. It radiates into space unlike the near field, which is stored. If radiating antennas are very close, they will load each other both reactively and resistively since they will be in each other's near and far field. The Yagi-Uda antenna is an example of such a case where mutual impedance must be taken into account for proper antenna design.
For practical communication purposes, however, antennas are usually too far to load each other. Which makes sense, because the power received is many orders of magnitude below the power transmitted.


TITLE: How do you find the formula for an area of the circle through integration?
QUESTION [3 upvotes]: I got this question on my Maths exam today, and the Department of Education has stated it is on the syllabus, but none of the three textbooks I could get my hands mention anything about it. One mentions the volume of a cone, but none the area of a circle.

Use integration methods to establish the formula $A = \pi r^2$ for the area of a disc with radius $r$

How would I do this?

REPLY [5 votes]: I think the best answer is the one given here: http://www.nick-santos.com/jokes/2007/05/mathematician-and-plumber.html
EDIT (at Aryabhatta's suggestion): The area is $$\int\int_{\rm circle}1\,dy\,dx=\int_0^{2\pi}\int_0^Rr\,dr\,d\theta={\rm etc.}$$ but this loses all the flavor of the link.
MORE EDIT: The link died, so I updated in the comments. But in case that link dies, too, here's what's actually there. Nick Santos got it from the geometer Peter Doyle.
Once upon a time there was a mathematician. His toilet was clogged. So he called the plumber. The plumber arrived later that evening, unclogged the toilet in 15 minutes, and handed the mathematician the bill. The mathematician looked at the bill and shouted: "Great scott! What a bill! You plumbers must make a fortune charging people this much. Do you mind if I ask how much you make?"
The plumber doesn't mind. He grins and names his salary.
The Mathematician: "That's more than I make. And it looks a lot easier than theoretical mathematics."
The Plumber: "Well, friend, you sound eager, so I'll give you a tip. The plumbing business is swell. And my foreman needs more men for the job. Tell him I sent you, and you can see for yourself what the work is like. One thing though: don't tell him you're a mathematician. He hates elitists, and he won't hire anyone with higher than an 8th grade education."
Well the mathematician was as serious as he claimed. The next day he did indeed go to see the plumber's foreman. By pretending to be a middle-school drop-out, he got the job easily. And lo! It was better than he had hoped. He found himself with better pay, fewer hours, and more respect than he ever had as a theoretical mathematician.
The mathematician worked many years as a happy plumber. The plumbing industry flourished, and one day the foreman decided that his plumbers really had to be at a 9th-grade level in order to remain competitive in this rapidly-growing field. He hired several private tutors, and required his plumbers to attend night classes.
On the first day of class, the math teacher was trying to gauge what his students knew. He singled out one plumber and asked, "Do you know the formula for the area of the circle?" Of course, the tutor had picked our mathematician, and like any good mathematician, he responded, "No. But I know how to derive it." "Derive it for me then," challenged the teacher.
So the mathematician went to the blackboard and began to compute the area of the circle as any good mathematician would. He wrote out the double integral with respect to x and y, computed the Jacobian with respect to r and theta so that he could perform a change of basis in terms of polar coordinates, then evaluated the double integral. And came to the solution $-\pi r^2$.
"Wait!" said the mathematician right before he announced his answer. "That can't be right!" He began to check his work, looking for where the negative got introduced. But he couldn't find his mistake. At last he threw up his hands, erased his computation, and started over again. He quickly set up the double integral, did the change of basis to polar coordinates, and simplified. And again he arrived at $-\pi r^2$!
By now the mathematician was frantic. How could he have gotten such a ridiculous answer twice? Had his math skills really gotten so bad? He wildly looked to the teacher, but the teacher knew nothing of multi-variable calculus, and had no idea what was going on. Then he looked to the class...and noticed something quite odd.
The eyes of every plumber were fixed upon him! The class was anxiously, quietly trying to get his attention without alerting the teacher. Each one had his hands cupped around his mouth, and they were all whispering the same words over and over again in unison. Slowly, he leaned in to hear better. And this is what he heard:
"You forgot to take the absolute value of the Jacobian!"


text:
\section{Obstructed Q-nodes} \label{sec:q_nodes}

Suppose that a Q-node with subtrees $T_1,\dots,T_n$ is obstructed. Then the two possible
orderings of this Q-node are not compatible with $\wlt$. Notice that at most four cliques are
sufficient to create the obstruction. We next prove that at
most three cliques are already sufficient.

\begin{lemma} \label{lem:q_node_three_cliques}
If a Q-node is obstructed, there exists an obstruction created by at most three maximal cliques.
\end{lemma}

\begin{proof}
Suppose that an obstruction is created by four cliques $a \in T_\alpha$, $b \in T_\beta$, $c \in
T_\gamma$ and $d \in T_\delta$ such that $\alpha < \beta$, $\gamma < \delta$, $a \wlt b$, and $c
\wgt d$. We know that $I_a$ is on the left of $I_b$, and $I_c$ is on the right of $I_d$.
Notice that the four subtrees $T_\alpha$, $T_\beta$, $T_\gamma$ and $T_\delta$ are not necessarily
distinct. We classify all possible orderings $<$ of $\alpha$, $\beta$, $\gamma$, $\delta$ in two
general cases, namely, $\alpha \neq \gamma$ and $\alpha = \gamma$. In the first case, we may assume
without loss of generality that $\alpha < \gamma$.

\emph{Case 1: $\alpha < \gamma < \delta$} (see Fig.~\ref{fig:Q_node_three_cliques}a). Consider the
relative positions of $I_c$ and $I_d$ with respect to $I_a$. If $I_d$ is to the left of $I_a$, we
have $d \wlt a \wlt b$, and these three cliques already create an obstruction. If $I_c$ is to the
right of $I_a$, then we get $a \wlt c$ and $c \wgt d$, creating an obstruction. If neither happens,
then $I_c$ and $I_d$ are subintervals of $I_a$. Thus $c,d \wlt b$. If $\beta \le \gamma$, we have $a
\wlt b$ and $b \wgt d$, creating an obstruction. If $\beta > \gamma$, then $d \wlt c \wlt b$, which
also creates an obstruction.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_three_cliques.eps}
\caption{Two cases of the proof of Lemma~\ref{lem:q_node_three_cliques}. The Q-node is depicted in
the top, while in the bottom we have the relative positions of the intervals.}
\label{fig:Q_node_three_cliques}
\end{figure}

\emph{Case 2: $\alpha = \gamma$} (see Fig.~\ref{fig:Q_node_three_cliques}b). If $I_c$ does not
intersect $I_b$, or $I_d$ does not intersect $I_a$, it is easy to see that three of the cliques
already create an obstruction. Suppose next that these intersections occur. Then $d \wlt b$. If
$\delta < \beta$ or $\beta < \delta$, it is again easy to show that three cliques are enough to
create an obstruction. It only remains to consider the case where $\alpha = \gamma < \beta =
\delta$.

Since the intervals $I_c$ and $I_a$ are non-intersecting, we may assume without loss of generality
that there exists $x \in P(a) \setminus P(c)$. This vertex $x$ belongs to sections of $T_\alpha$.
Thus $x \notin P(d)$, and we get that $I_a \subsetneq I_d$. By Lemma~\ref{lem:open_intervals}, $P(d)
\subsetneq P(a)$; in particular, $P(d)$ contains no private pre-drawn interval from sections of
$T_\beta$, and all pre-drawn intervals of $s_\beta(Q)$ are also contained in $s_\alpha(Q)$.

Since $P(d) \setminus P(b) = \emptyset$, there exists $y \in P(b) \setminus P(d)$ which is contained
in sections of $T_\beta$. We next apply the argument in the previous paragraph, and obtain $y \notin
P(c)$, $I_b \subsetneq I_c$, and $P(c) \subsetneq P(b)$. Consequently, $P(c)$ contains no private
pre-drawn intervals from sections of $T_\alpha$, and all pre-drawn intervals of $s_\alpha(Q)$ are
contained in $s_\beta(Q)$. We conclude that $P(c) = P(d)$ and $I_c = I_d$, which gives a
contradiction.\qed
\end{proof}

In summary, we can assume that a minimal obstruction involves at most three maximal cliques.  These
three cliques belong to either two or three different subtrees.

In the rest of the section, many figures describe positions of derived pre-drawn intervals in
sections of the Q-node and its subtrees; for instance Fig.~\ref{fig:Q_node_two_subtrees}. Some of
these intervals necessarily belong to sections of the Q-node, since they belong to maximal cliques
of several subtrees; for instance $t_2$ in Fig.~\ref{fig:Q_node_two_subtrees}. But for the remaining
intervals, it is not important to distinguish whether they belong to sections of the Q-node or one
of its subtrees, only their relative positions in the Q-node matter; for instance $q$ and $x_1$ in
Fig.~\ref{fig:Q_node_two_subtrees}.

\subsection{Cliques in Two Different Subtrees} \label{sec:q_nodes_two_subtrees}

In this section, we deal with the case where the maximal cliques belong to two different subtrees.

\begin{lemma}[The Q-node case, Two Subtrees] \label{lem:q_node_two}
If at most three cliques creating the obstruction belong to two different subtrees, then $G$ and
$\calR'$ contain an SE, $1$-FAT, $2$-FAT, $1$-BI, or $2$-BI obstruction.
\end{lemma}

\begin{proof}
The proof is similar to that of Lemma~\ref{lem:p_node}.  If two maximal cliques create an
obstruction, we can argue as in the first paragraph of the proof of Lemma~\ref{lem:p_node}, and we
obtain an SE obstruction.  It remains to deal with the case of three maximal cliques $a$, $b$, and
$c$.

We can assume that $a \wlt b \wlt c$ and that, for some $i < j$, we have $a,c \in T_i$ and $b \in
T_j$. Furthermore, without loss of generality, there exist $p \in P(a) \setminus P(c)$. Since $p$
belongs to sections of $T_i$, then $p \notin P(b)$, and thus $\inter p'$ lies to the left of $I_b$.
We distinguish two cases.

\emph{Case 1:} $P(b) \setminus P(c) \ne \emptyset$. Then there exists $q \in P(b) \setminus P(c)$
such that $\inter q'$ lies between $\inter p'$ and $I_c$. Since $q$ is non-adjacent to $p$, it
belongs to sections of either $Q$ or $T_j$. Notice that in any case $s_q^\lft(Q)$ is on the right of
$s_i(Q)$.  Arguing as in Case 1 of the proof of Lemma~\ref{lem:p_node}, we observe that there exists
$r \in P(c) \setminus P(b)$. Furthermore, it follows that $\inter r'$ lies to the right of $\inter
q'$;  see Fig.~\ref{fig:Q_node_two_subtrees}a on the left.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_two_subtrees.eps}
\caption{(a) Case 1: The pre-drawn intervals and the situation in the
MPQ-tree for $s_i(Q) \subsetneq s_q^\lft(Q)$. (b) Case 2: The pre-drawn intervals and the
situation when there exists no path from $x$ to $z$ avoiding the vertices of $b$.}
\label{fig:Q_node_two_subtrees}
\end{figure}

If there exists a path $P_1$ from $p$ to $r$ avoiding $N[q]$, we get a $1$-FAT obstruction for $x_1
= p$, $y_1 = q$, $z_1 = r$ and $P_1$. By Lemma~\ref{lem:different_sections}, we know that $s_i(Q)
\ne s_q^\lft(Q)$. If $s_i(Q) \not\subseteq s_q^\lft(Q)$, then there exists some $w \in s_i(Q)
\setminus s_q^\lft(Q)$. Therefore, $P_1 = pwr$ is such a path. It remains to deal with the case
where no such path $P_1$ exists, which implies that $s_i(Q) \subsetneq s_q^\lft(Q)$; see
Fig.~\ref{fig:Q_node_two_subtrees}a on the right.

Consider the set $W = s_i(Q)$. Let $t_2$ be a vertex of $W$ whose section $s_{t_2}^\rt(Q)$ is
leftmost. Let $C$ be the component of $G[Q] \setminus W$ containing $q$. Since $s_q^\lft(Q)
\setminus W$ is non-empty, $C$ consists of the vertices of at least two subtrees of the Q-node. If
$t_2$ was adjacent to all vertices of $C$, it would be possible to flip the ordering of this
component, contradicting the fact that there are only two possible orderings for $Q$. Therefore,
$t_2$ is not adjacent to all vertices of $C$.  We choose $x_1 \in C \setminus N[t_2]$ whose section
$s_{x_1}^\lft(Q)$ is leftmost.  Let $P_1$ be a shortest path from $q$ to $x_1$ whose inner vertices
are adjacent to $t_2$. It follows that $x_2 = p$, $y_2 = q$, $z_2 = r$, $P_2 = x_2t_2$, $t_2$,
$x_1$, and $P_1$ define a $2$-FAT obstruction. (By Lemma~\ref{lem:monotone_paths}, all inner
vertices of $P_1$ are adjacent to $t_2$.)\qed

\emph{Case 2:} $P(b) \setminus P(c) = \emptyset$. Then there exists $r \in P(c) \setminus P(b)$.
Since $\inter r'$ lies on the right of $I_b$, the vertex $r$ is not contained in $a$ and it belongs
to sections of $T_i$. We use the same approach as in Case 2 of the proof of Lemma~\ref{lem:p_node}.
Since $P(b) \subseteq P(a) \cap P(c)$, every pre-drawn interval of $P(b)$ covers
$[\clql(a),\clqr(c)]$.  Let $u \in P^\endlft(b)$ and $v \in P^\startrt(b)$ (possibly $u=v$).

By applying Sliding Lemma~\ref{lem:sliding} twice, we get $x,z \notin P(b)$ such that $\inter x'$
covers $\ell(v)$ and $\inter z'$ covers $r(u)$; see Fig.~\ref{fig:Q_node_two_subtrees}b on the left.
Suppose that there exists a path $P_{x,z}$ from $x$ to $z$ avoiding all vertices of $b$. Let $x_1 =
x$, $z_1 = z$, and $P_1$ be a shortest path from $x_1$ to $z_1$ in $G[Q] \setminus b$.
By Lemma~\ref{lem:non_adjacent}, there exists $y_1 \in b$ non-adjacent to $P_1$. We
obtain a $1$-BI obstruction.

Suppose next that there is no path $P_{x,z}$ avoiding $b$.  We know that $x$ and $y$ belong to
sections of $T_i$, since there exist paths $P_{x,p}$ and $P_{r,z}$ avoiding $b$, from the above
applications of Sliding Lemma~\ref{lem:sliding}.  Since no path $P_{x,z}$ avoiding $b$ exists, we
have $s_i(Q) \subsetneq s_j(Q)$.  As in Case 1, let $W = s_i(Q)$, and let $t_2$ be a vertex of $W$
whose section $s_{t_2}^\rt(Q)$ is leftmost (possibly $t_2 = u$ or $t_2 = v$).  We again infer that
$t_2$ is not adjacent to all vertices of $C$, where $C$ is the component of $G[Q] \setminus W$
containing $b \setminus W$. We choose $x_1 \in C \setminus N[t_2]$ whose section $s_{x_1}^\lft(Q)$
is leftmost. Since $s_i(Q) \subsetneq s_j(Q) \subseteq b$, there exists $y_2 \in b$ non-adjacent to
$x$ and $z$. We get a 2-BI obstruction for $x_2 = x$, $y_2$, $z_2 = z$, $u$, $v$, a shortest path
$P_1$ from $y_2$ to $x_1$ in $C$, and $P_2 = x_2t_2$. (By Lemma~\ref{lem:monotone_paths}, all inner
vertices of $P_1$ are adjacent to $t_2$.)\qed
\end{proof}

\subsection{$k$-FAT and $(k,\ell)$-CE Lemmas} \label{sec:q_nodes_k_fat}

In this section, we give two tools for the case, analyzed in
Section~\ref{sec:q_nodes_three_subtrees}, where the three maximal cliques creating the obstruction belong to
three different subtrees. These tools give insight into the structure of the Q-nodes, and explain
the way in which complex obstructions such as $k$-FAT and $(k,\ell)$-CE obstructions are formed.

\heading{$\boldsymbol k$-FAT Lemma.} First, we present a useful lemma that allows to locate $k$-FAT
obstructions. The key idea of the proof is similar to Case 1 of the proof of
Lemma~\ref{lem:q_node_two}, but applied inductively for $k$.

\begin{lemma}[$\boldsymbol k$-FAT] \label{lem:k_fat}
Let $Q$ be a Q-node with children $T_1,\dots,T_n$, and let $a$, $b$ and $c$ be three cliques of
$T[Q]$ contained respectively in $T_\alpha$, $T_\beta$ and $T_\gamma$, for $\alpha < \beta < \gamma$.
Let $x_k \in P(a)$, $y_k \in P(c)$ and $z_k \in P(b)$ be three disjoint pre-drawn intervals such
that $\inter{y_k}'$ is between $\inter{x_k}'$ and $\inter{z_k}'$. Then $G[Q]$ and
$\calR'[\{x_k,y_k,z_k\}]$ contain a $k$-FAT obstruction.
\end{lemma}

\begin{proof}
The proof, illustrated in Fig.~\ref{fig:q_nodes_k_fat_statement}, is by induction. We always denote
the vertices as in the definition of $k$-FAT obstructions. If we find a $1$-FAT or $2$-FAT
obstruction, the statement is true.  Otherwise, we recurse on a smaller part of the Q-node, where we
find a structure identical to a $(k-1)$-FAT obstruction, except for the fact that the vertex
$x_{k-1}$ is free. Together with some vertices in the remainder of the Q-node, we obtain a $k$-FAT
obstruction. We next provide the details.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_k_fat_statement.eps}
\caption{On the left, the position of the pre-drawn intervals.  In
the middle, the construction of $W_k \subsetneq N[y_k]$ in $G[Q]$. On the right, the Q-node with the
three subtrees and the intervals of $W_k$ depicted in its sections.}
\label{fig:q_nodes_k_fat_statement}
\end{figure}

Let $k$ be some yet unspecified integer, determined by the recursion. We want to argue that $G[Q]$
contains a $k$-FAT obstruction because the ordering of $\inter{x_k}'$, $\inter{y_k}'$ and
$\inter{z_k}'$ is incorrect (in every representation, $\inter{z_k}$ is between $\inter{x_k}$ and
$\inter{y_k}$). Suppose that there exists a path from $x_k$ to $z_k$ whose inner vertices are
non-adjacent to $y_k$. Then we obtain a $1$-FAT obstruction. It remains to deal with the harder
situation where no such path exists.

Let $C(x_k)$ be the connected component of $G[Q] \setminus N[y_k]$ containing $x_k$. By our
assumption, $z_k \notin C(x_k)$. We denote by $W_k$ the subset of $N[y_k]$ containing those vertices
that are adjacent to some vertex of $C(x_k)$; see Fig.~\ref{fig:q_nodes_k_fat_statement}, middle.
Notice that the vertices of $C(x_k)$ appear only in sections and subtrees to the left of
$s_\beta(Q)$.  Therefore, every vertex of $W_k$ lies in the sections of $Q$ and stretches from the
left of $s_\beta(Q)$ to $s_\gamma(Q)$; see Fig.~\ref{fig:q_nodes_k_fat_statement}, right. In other
words, $W_k \subseteq s_\beta(Q) \cap s_\gamma(Q)$ and every vertex of $W_k$ is adjacent to $z_k$.

Let $C$ be a connected component of $G[Q] \setminus W_k$. If $C$ contains a vertex from some section
of $Q$, we call it \emph{big}. Notice that in this situation $C$ has a vertex contained in two
consecutive sections of $Q$ and their subtrees. Otherwise, $C$ consists of some vertices of a
subtree of $Q$, and we call it \emph{small}. The section above a subtree containing a small
component is a subset of $W_k$. Additionally, if two small components are placed in two different
subtrees, the two sections above these subtrees are different.

The graph $G[Q] \setminus W_k$ is disconnected, as $x_k$ and $z_k$ belong to different
components. Let us denote the connected component containing $y_k$ by $C(y_k)$, and the one
containing $z_k$ by $C(z_k)$.
Let $t_k$ be a vertex of $W_k$ whose section
$s_{t_k}^\rt(Q)$ is leftmost. Let $P_k$ be a shortest path from $x_k$ to $t_k$ in $G[C(x_k) \cup \{t_k\}]$; see
Fig.~\ref{fig:q_nodes_k_fat_statement}, right. We distinguish two cases.

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_k_fat_two_cases.eps}
\caption{(a) In Case 1, there exists a path $P_{k-1}$ from $x_{k-1}$ to $y_k$ whose inner
vertices avoid $z_k$. (b) In Case 2, we have
$C(y_k) = C(z_k)$ and such a path might no longer exist. For instance, every path from $x_{k-1}$ to
$y_k$ in $C(y_k)$ might use the depicted interval in the sections of $Q$, which is also
adjacent to $z_k$.}
\label{fig:q_nodes_k_fat_two_cases}
\end{figure}

\emph{Case 1: $C(y_k) \ne C(z_k)$.} This case is very similar to the proof of
Lemma~\ref{lem:q_node_two}; see Fig.~\ref{fig:q_nodes_k_fat_two_cases}a. Every vertex of $W_k$ is
adjacent to some vertex of $C(x_k)$ and to some vertex of $C(y_k)$. Therefore, it is also adjacent
to every vertex of $C(z_k)$. If $C(z_k)$ was big, then we could reverse its sections in the Q-node,
contradicting the fact that there are only two possible orderings for a Q-node. Therefore, $C(z_k)$
is small. Notice that then $C(y_k)$ is not small, since otherwise we would get $s_\beta(Q) = W_k =
s_\gamma(Q)$, contradicting Lemma~\ref{lem:different_sections}. Thus, $C(y_k)$ is big.

Let us set $y_{k-1} = z_k$ and $z_{k-1} = y_k$. The vertex $t_k$ is not universal for $C(y_k)$;
otherwise, every vertex of $W_k$ would be universal and this would give additional orderings of
$C(y_k)$ in $Q$.  Let $x_{k-1}$ be a vertex of $C(y_k) \setminus N[t_k]$ whose section
$s_{x_{k-1}}^\lft(Q)$ is leftmost. Notice that $s_{x_{k-1}}^\lft(Q)$ is always the next section to
$s_{t_k}^\rt(Q)$. Let $P_{k-1}$ be a shortest path from $x_{k-1}$ to $z_{k-1}$ in $C(y_k)$. By
Lemma~\ref{lem:monotone_paths}, all inner vertices of $P_{k-1}$ are adjacent to $t_k$.  Since this
path lies in $C(y_k)$, the inner vertices are non-adjacent to $y_{k-1}$, $x_k$ and $P_k$. We have
constructed a $2$-FAT obstruction.

\emph{Case 2: $C(y_k) = C(z_k)$.} In this case, the component $C(y_k)$ is big; see
Fig.~\ref{fig:q_nodes_k_fat_two_cases}b. Therefore, similarly as above, $t_k$ is not universal for
$C(y_k)$. We put $y_{k-1} = z_k$ and $z_{k-1} = y_k$. We choose $x_{k-1} \in C(y_k) \setminus
N[t_k]$ in the same way as in Case 1.  Notice that $x_{k-1}$ is a non-neighbor of $y_{k-1}$, since
otherwise it would be a neighbor of $t_k$.  On the other hand, $x_{k-1}$ might be adjacent to
$z_{k-1}$ or not. If it is, we get a $2$-FAT obstruction for $k=2$ with $P_1 = x_{k-1}z_{k-1}$. If
it is not, we proceed as follows.

As before, every shortest path from $x_{k-1}$ to $z_{k-1}$ has all inner vertices adjacent to $t_k$.
Since all vertices of $C(y_k)$ are non-adjacent to $x_k$ and the inner vertices of $P_k$, every
shortest path satisfies this as well.  There exists a shortest path from $x_{k-1}$ to
$z_{k-1}$ in $C(y_k)$, but we cannot guarantee that the inner vertices of this path are non-adjacent
to $y_{k-1}$. We solve this issue by applying the entire argument of the proof recursively to
$C(y_k)$.

In every representation extending the partial representation, the intervals of $C(x_k)$ form a
connected subset of the real line placed to the left of $\inter{y_k}'$. Therefore, $\inter{t_k}$
stretches from $C(x_k)$ to $\inter{z_k}'$, covering $\inter{y_k}'$. Thus $\inter{x_{k-1}}$ is placed
to the right of $\inter{z_k}' = \inter{y_{k-1}}'$ in every extending representation (see
Fig.~\ref{fig:k_FAT}b).  Again, $\inter{y_{k-1}}'$ has to be placed between $\inter{x_{k-1}}$ and
$\inter{z_{k-1}}'$. We assume that $\inter{x_{k-1}}$ is pre-drawn on the right of $\inter{y_{k-1}}'$
and repeat the same argument for $C(y_k)$ and the MPQ-tree restricted to these vertices. The role of
$x_k$, $y_k$ and $z_k$ is played by $x_{k-1}$, $y_{k-1}$ and $z_{k-1}$, respectively. (The ordering
of the pre-drawn intervals is flipped.)

The paragraphs above show the induction step of our proof (by induction on, say, the number of
considered sections of $Q$). By the induction hypothesis, we find a $(k-1)$-FAT obstruction.  By
making $x_{k-1}$ free and adding $x_k$, $t_k$ and $P_k$, we get a $k$-FAT obstruction in the
original partial representation.  Clearly $t_k$ is adjacent to the entire $(k-1)$-FAT obstruction
with the exception of $x_{k-1}$, since all further vertices are contained in a section to the left
of $s_{x_{k-1}}^\lft(Q)$. The reason is that we always use shortest paths which are $Q$-monotone by
Lemma~\ref{lem:monotone_paths}.  By the same reason, they are non-adjacent to the inner vertices of
$P_k$ and to $x_k$, as required.

To make the argument complete, we should check that all the assumptions used throughout the proof
apply recursively, in particular the arguments concerning non-universality of $t_{k-1}$ and
reversing big components. This is true because both components $C(y_{k-1})$ and $C(z_{k-1})$ of
$C(y_k) \setminus W_{k-1}$ appear to the left of $x_{k-1}$, so $t_k$ and the other vertices of $W_k$
are universal for them. This property is preserved throughout the recursion, so $C(y_\ell)$ and
$C(z_\ell)$ are adjacent to all vertices of $W_k,W_{k-1},\dots,W_{\ell+1}$. Similarly,
the rest of the inductive proof can be formalized.\qed
\end{proof}

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_using_k_fat.eps}
\caption{Suppose that we show that a partial representation $\calR'$ has three pre-drawn intervals
as on the left, and that there is a vertex $y_k$ adjacent to $u$ and non-adjacent to $x_k$ and
$z_k$. Then $\inter{y_k}$ has to be placed between $\inter{x_k}'$ and $\inter{z_k}'$ in every
extending representation. Thus, we can assume it is pre-drawn there and obtain a modified partial
representation $\widehat\calR'$. If we further show that $x_k$, $y_k$ and $z_k$ are placed in
appropriate sections of $G[Q]$ for some Q-node $Q$, we can apply $k$-FAT Lemma~\ref{lem:k_fat} and
we get a $k$-FAT obstruction in $G[Q]$ and $\widehat\calR'[\{x_k,y_k,z_k\}]$. Together with $\inter
u'$, this forms a $k$-BI obstruction in $G$ and $\calR'$.}
\label{fig:q_nodes_using_k_fat}
\end{figure}

The above proof shows that the structure of a Q-node can be highly complicated, leading to
complicated obstructions such as $k$-FAT. Actually, $k$-FAT Lemma~\ref{lem:k_fat} is a very useful tool
because it can be also applied in situations where not all
$x_k$, $y_k$, and $z_k$ are pre-drawn, to build other obstructions.
Fig.~\ref{fig:q_nodes_using_k_fat} shows an example.

\begin{lemma} \label{lem:k_fat_contains_1_fat}
Consider a $k$-FAT obstruction $H_k$ for $k>2$. If we swap the positions of $\inter{x_k}'$ and
$\inter{y_k}'$, then we obtain a new obstruction which contains a $1$-FAT obstruction for $x'_1 =
y_k$, $y'_1 = x_k$, and $z'_1 = z_k$. Further, if $k=2$ and this does not happen, then $x_2$ is
adjacent to $t_2$.
\end{lemma}

\begin{proof}
For $k \ge 3$, the graph $H_k \setminus N[x_k]$ is connected; in particular, there
exists a path $P'_1 = y_kt_{k-1}z_k$ avoiding $N[x_k]$. For $k=2$, there exists a path $P'_1 =
y_2t_2z_2$ avoiding $N[x_2]$, unless $x_2$ is adjacent to $t_2$.\qed
\end{proof}

\heading{$\boldsymbol{(k,\ell)}$-CE Lemma.} Suppose that we have the situation in
Fig.~\ref{fig:q_nodes_kl_ce_statement}. We can easily show that there is some $(k,\ell)$-CE
obstruction by applying $k$-FAT Lemma~\ref{lem:k_fat} twice, once when $\inter{x_k}$ is on the left
of $\inter{y_k}$ and once when it is on the right.  The following lemma reveals its structure in
detail.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_kl_ce_statement.eps}
\caption{When $\inter u'$ single overlaps $\inter{z_k}'$, and the vertices $x_k$, $y_k$, and $z_k$ are
placed in the MPQ-tree as on the right, we get a $(k,\ell)$-CE obstruction.}
\label{fig:q_nodes_kl_ce_statement}
\end{figure}

\begin{lemma}[$(\boldsymbol{k},\boldsymbol{\ell})$-CE] \label{lem:kl_ce}
Let $Q$ be a Q-node with children $T_1,\dots,T_n$, and let $a$, $b$ and $c$ be three cliques of
$T[Q]$ contained respectively in $T_\alpha$, $T_\beta$ and $T_\gamma$, for $\alpha < \beta < \gamma$.
Let $x_k \in a$, $y_k \in c$ and $z_k \in P(b)$ be three non-adjacent vertices having a common
pre-drawn neighbor $u$ such that $\inter{u}'$ single overlaps $\inter{z_k}'$.
Then $G[Q] \cup \{u\}$ and $\calR'[\{z_k,u\}]$ contain a $(k,\ell)$-CE obstruction, where either $\ell=1$ or
$k = \ell = 2$.
\end{lemma}

\begin{proof}
The simplest case is when there exist a path $P_k$ from $x_k$ to $z_k$ avoiding $N[y_k]$, and a path
$P_\ell'$ from $y_k$ to $z_k$ avoiding $N[x_k]$. Let $P_k$ and $P_\ell'$ be shortest such paths as
in Fig.~\ref{fig:q_nodes_kl_ce_statement}, right. We get a $(1,1)$-CE obstruction. By
Lemma~\ref{lem:monotone_paths}, the paths $P_k$ and $P_\ell'$ are monotone. Therefore, their inner
vertices are non-adjacent to each other, with the possible exception of the last vertices before
$z_k$, which can be adjacent or even identical. Concerning minimality, we can always find one of the
three finite $(1,1)$-CE obstructions depicted in Fig.~\ref{fig:kl_CE_obstructions}a. The reason is
that when paths $P_k$ and $P'_\ell$ are long, we can take as $x_k$ and $y_k$ one of their inner
vertices, making them shorter.

Suppose next that there exists no path $P_k$ from $x_k$ to $z_k$ avoiding $N[y_k]$.  Let $C(x_k)$,
$W_k$, and $t_k$ be defined as in the proof of $k$-FAT Lemma~\ref{lem:k_fat}. Following the argument
in that proof, we get the subgraph $H_k$ of a $k$-FAT obstruction, which is not the complete $k$-FAT
obstruction because $x_k$ and $y_k$ are free.

\emph{Case 1: There exists some path $P_\ell'$ from $y_k$ to $z_k$ avoiding $N[x_k]$.} Let $P'_\ell$
be a shortest such path (notice that $\ell = 1$). Together with the above subgraph $H_k$, we get a $(k,1)$-CE
obstruction; see Fig.~\ref{fig:q_nodes_kl_ce_two_cases}a. In particular, if some vertex $w \in W_k$
is non-adjacent to $x_k$ (possibly $w = t_k$), we can use $P'_\ell = y_kwz_k$.

We note that when $k \ge 3$, such a path $P_\ell'$ necessarily exists, as we can use $P'_\ell =
y_kt_{k-1}z_k$, as argued in Lemma~\ref{lem:k_fat_contains_1_fat}. Therefore, the $(k,1)$-CE
obstructions consist of the subgraph $H_k$ together with $u$; assuming minimality, we have that
either $u$ is adjacent to all vertices of $H_k$, or $u = t_k$.  If $k = 2$, then $P_\ell'$ might
still exist but it might be longer and might use inner vertices not contained in $H_k$. Concerning
minimality, we always find one of the three $(2,1)$-CE obstructions depicted in
Fig.~\ref{fig:kl_CE_obstructions}b. Indeed, $P_2$ can be assumed to be of length one or two, since
otherwise we could use one of its inner vertices as $x_2$. For length two, we get $P'_1 =
y_kt_kz_k$. For length one, we get a path $P'_1$ from $z_2$ to $y_2$, and we can assume that $y_2$
is adjacent to $x_1$ (otherwise we could use as $y_2$ the neighbor of $x_1$ on $P_1$).

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_kl_ce_two_cases.eps}
\caption{(a) Case 1: If there exists a path $P'_\ell$ from $y_k$ to $z_k$ avoiding $N[x_k]$, then we get a
$(k,1)$-CE obstruction. (b) Case 2: We get a $(2,2)$-CE obstruction.}
\label{fig:q_nodes_kl_ce_two_cases}
\end{figure}

\emph{Case 2: No such path $P'_\ell$ exists.}
By Lemma~\ref{lem:k_fat_contains_1_fat}, $k = 2$.
We want to show that there exists a $(2,2)$-CE obstruction.

Notice that all vertices $w\in W_k$ are
adjacent to $x_k$, $y_k$, and $z_k$, since otherwise there would exist a path $P'_\ell = y_kwz_k$.
Hence the vertices of $W_k$ belong to sections of $Q$, covering all subtrees between $T_\alpha$ and
$T_\gamma$; see Fig.~\ref{fig:q_nodes_kl_ce_two_cases}b. Let $C(y_k)$ and $C(z_k)$ be the components
of $G[Q] \setminus W_k$ containing $y_k$ and $z_k$, respectively.  Since there exists no path
$P'_\ell$, we obtain that $C(x_k)$, $C(y_k)$, and $C(z_k)$ are pairwise different.  To determine the
structure of a $(2,2)$-CE obstruction, we apply the argument from Case 1 of the proof of
$k$-FAT Lemma~\ref{lem:k_fat} symmetrically twice.

Let $t_k$ be a vertex of $W_k$ having leftmost section $s_{t_k}^\rt(Q)$ and let $t'_\ell$ be a
vertex of $W_k$ having rightmost section $s_{t'_\ell}^\lft(Q)$ (possibly $t_k = t'_\ell$).  It is
easy to see that $C(z_k)$ is small, otherwise we could flip it and obtain an
ordering of the maximal cliques not compatible with the Q-node.

Similarly as in the proof of $k$-FAT Lemma~\ref{lem:k_fat}, this implies that both $C(x_k)$ and
$C(y_k)$ are big. Therefore, $t_k$ is not universal for $C(y_k)$ and $t'_\ell$ is not universal for
$C(x_k)$. As in the proof of $k$-FAT Lemma~\ref{lem:k_fat}, we choose $x_{k-1} \in C(y_k)$
non-adjacent to $t_k$  and $y'_{\ell-1} \in C(x_k)$ non-adjacent to $t'_\ell$.  There exist paths
$P_{k-1}$ from $x_{k-1}$ to $y_k$ and $P'_{\ell-1}$ from $y'_{\ell-1}$ to $x_k$.  In consequence, we
obtain a $(2,2)$-CE obstruction.

Regarding minimality, notice that we can assume that $y_2$ is adjacent to $x_1$, and $x_2$ is adjacent to $y'_1$;
otherwise, we could choose as $y_2$ and $x_2$ the neighbors of $x_1$ and $y'_1$ on the paths $P_1$ and
$P'_1$, respectively. We get the four minimal finite $(2,2)$-CE obstructions that are illustrated in
Fig.~\ref{fig:kl_CE_obstructions}c.
\qed
\end{proof}

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_three_subtrees_diagram.eps}
\caption{A summary of Section~\ref{sec:q_nodes_three_subtrees}. The diagram starts in the middle with
Lemma~\ref{lem:q_node_wlog_lemma}. Inside the cases, we draw the positions of $I_a$, $I_b$, $I_c$,
and some pre-drawn intervals. An arrow at a pre-drawn interval means that it may be further
stretched in the given direction.  The obtained obstructions are highlighted in gray, the used tools
have highlighted borders.}
\label{fig:q_nodes_three_subtrees_diagram}
\end{figure}

\subsection{Cliques in Three Different Subtrees} \label{sec:q_nodes_three_subtrees}

When a Q-node $Q$ is obstructed by three maximal cliques $a \in T_\alpha$, $b \in T_\beta$ and
$T_\gamma$, where $\alpha < \beta < \gamma$, the situation is quite complex.
Fig.~\ref{fig:q_nodes_three_subtrees_diagram} gives an overview of the cases and obstructions
obtained in this case.

\begin{lemma} \label{lem:q_node_wlog_lemma}
Without loss of generality, we can assume that $a \wlt b \wgt c$ and $\clqr(a) \le \clqr(c)$.
\end{lemma}

\begin{proof}
Since $a$, $b$ and $c$ create an obstruction, $b$ is either a minimal or a maximal element in $\wlt
|_{\{a,b,c\}}$. Without loss of generality (using the flip operation), we can assume that $b$ is
maximal, so $a \wlt b \wgt c$.  Since we can swap $a$ and $c$ by reversing the Q-node, we can assume
that $\clqr(a) \le
\clqr(c)$.\qed
\end{proof}

Since $a \wlt b \wgt c$, both $I_a$ and $I_c$ appear on the left of $I_b$.  Since $\clqr(a) \le
\clqr(c)$, either $I_a$ contained in $I_c$, or $I_a$ is on the left of $I_c$. The first case is easier:

\begin{lemma} \label{lem:q_node_containment_case}
If $I_a$ is contained in $I_c$, then $G$ and $\calR'$ contain a $(k,\ell)$-CE obstruction, where
$\ell = 1$ or $2 \ge k \ge \ell$.
\end{lemma}

\begin{proof}
The proof is illustrated in Fig.~\ref{fig:q_nodes_containment_case}.  By
Lemma~\ref{lem:open_intervals}, $P(c) \subseteq P(a)$. Since $b$ is placed between $a$ and $c$ in
the Q-node $Q$, every vertex contained in both $a$ and $c$ is contained in $b$ as well. Hence $P(c)
\subsetneq P(b)$, and there exists $r \in P(b) \setminus P(c)$. Since $\inter r'$ is on the right of
$I_c$, it is also on the right of $I_a$, and thus $r \notin P(a)$.

Let $u \in P^{\endlft}(c)$. We apply Sliding Lemma~\ref{lem:sliding} to $I_c$, $I_b$, and $\inter
r'$. We get a pre-drawn interval $\inter{z_k}'$ covering $r(u)$, and an induced path $P_{r,z_k}$
from $r$ to $z_k$ consisting of pre-drawn intervals not in $P(c)$. Therefore $z_k$ is on the left of
$c$ in $Q$. Since all pre-drawn intervals of $P_{r,z_k}$ do not belong to $P(c)$, they are on the
right of $I_c$. Thus they are also on the right of $I_a$, which implies that they do not belong to
$P(a)$. Consequently, $z_k$ is between $a$ and $c$ in $Q$.

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_containment_case.eps}
\caption{Proof of Lemma~\ref{lem:q_node_containment_case}. On the left, the pre-drawn
intervals. On the right, their positions in the MPQ-tree.}
\label{fig:q_nodes_containment_case}
\end{figure}

Let $x_k \in a$ and $y_k \in c$ be vertices non-adjacent to $z_k$. By $(k,\ell)$-CE
Lemma~\ref{lem:kl_ce}, $x_k$, $y_k$, $z_k$, and $u$ create a $(k,\ell)$-CE obstruction, for $\ell =
1$ or $2 \ge k \ge \ell$. Notice that the clique associated to $z_k$ is some $b'\neq b$.\qed
\end{proof}

The case where $I_a$ is on the left of $I_c$ is further divided into several subcases. In the next two lemmas, we focus on the situation where $P(b) \setminus P(c) \ne \emptyset$.

\begin{lemma} \label{lem:q_node_p_and_r_case}
If $I_a$ is on the left of $I_c$, $P(b) \setminus P(c) \ne \emptyset$ and $P(a) \setminus P(c) \ne
\emptyset$, then $G$ and $\calR'$ contain a $k$-FAT, $k$-BI ($k \le 2$), $k$-FB, or $k$-EFB
obstruction.
\end{lemma}

\begin{proof}
The proof is illustrated in Fig.~\ref{fig:q_nodes_p_and_r_case}.  Let $p \in P(a) \setminus P(c)$ and
$r \in P(b) \setminus P(c)$. Then $\inter p'$ is on the left of $I_c$, and $\inter r'$ is on the
right of $I_c$.  Clearly, $\inter p'$ and $\inter r'$ are disjoint, so $p$ appears in the Q-node on
 the left of $r$. Let $u \in P^{\endlft}(c)$ and $v \in P^{\startrt}(c)$ (possibly $u = v$).

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_p_and_r_case.eps}
\caption{Proof of Lemma~\ref{lem:q_node_p_and_r_case}. On the left, the pre-drawn
intervals, with possible sliding on each side. On the right, their positions in the MPQ-tree.}
\label{fig:q_nodes_p_and_r_case}
\end{figure}

If $r(u) \le r(r)$, then $z_k = r$. Obviously, $z_k$ is between $p$ and $c$ in the Q-node.
Otherwise, $P(c) \subsetneq P(b)$, and we apply Sliding Lemma~\ref{lem:sliding} to $I_c$, $I_b$, and
$r$. We obtain a pre-drawn interval $\inter{z_k}'$ not contained in $P(c)$ covering $r(u)$, and a
path $P_{r,z_k}$ whose inner vertices are pre-drawn and not contained in $P(c)$. Notice that all of
these pre-drawn vertices are on the right of $I_c$.  Therefore, these vertices are not contained in
$P(a)$. In this case, we also get that $z_k$ is between $p$ and $c$ in the Q-node.

Similarly, if $\ell(p) \le \ell(v)$, then $x_k = p$. Otherwise, we use the flipped version of
Sliding Lemma~\ref{lem:sliding} to $I_c$, $I_a$, and $p$, which gives a pre-drawn interval
$\inter{x_k}'$ not contained in $P(c)$ covering $\ell(v)$. By a similar argument, in both cases, we
show that $x_k$ is on the left of $z_k$ in the Q-node.

Let $y_k \in c$ be a vertex non-adjacent to $z_k$ (possibly, $y_k = u$ or $y_k = v$).  Such a vertex
exists because $z_k$ is on the left of $c$ in the Q-node. Notice that $y_k$ is also non-adjacent to
$x_k$. Since $y_k$ is adjacent to $u$ and $v$, in every extending representation $\inter{y_k}$ is
between $\inter{x_k}'$ and $\inter{z_k}'$. So we can assume that it is pre-drawn in this position
and, by $k$-FAT Lemma~\ref{lem:k_fat}, we get a $k$-FAT obstruction. Together with $u$ and $v$ (or
possibly only one of them), we get one of the obstructions in
Fig.~\ref{fig:q_nodes_p_and_r_case_obstructions}.\qed

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_p_and_r_case_obstructions.eps}
\caption{The different obstructions obtained in the proof of Lemma~\ref{lem:q_node_p_and_r_case}.
If $\ell(x_k) \le \ell(u) \le r(u) \le r(z_k)$, we get one of the obstructions (a) to (c). Since
$z_k$ is in the Q-node between $x_k$ and $c$, if $u$ or $v$ intersect $x_k$, then they also
intersect $z_k$. In the cases (d) and (e), $\ell(u) < \ell(x_k)$ and $r(z_k) < r(v)$. Since $u$
intersects $z_k$, there are only two possible obstructions.}
\label{fig:q_nodes_p_and_r_case_obstructions}
\end{figure}

\end{proof}

\begin{lemma} \label{lem:q_node_q_and_r_case}
If $I_a$ is on the left of $I_c$, $P(b) \setminus P(c) \ne \emptyset$ and $P(a) \subsetneq
P(c)$, then $G$ and $\calR'$ contain a $k$-FAT, $(k,1)$-CE, $k$-FS, $k$-FDS, $k$-FNS, or $k$-EFS obstruction.
\end{lemma}

\begin{proof}
We choose $r \in P(b) \setminus P(c)$ and $q \in P(c) \setminus P(a)$ with leftmost right endpoint.
Then $\inter r'$ is on the right of $I_c$ and $\inter q'$ is on the right of $I_a$.  We note that
$q$ might be adjacent to $r$ or not, and might belong to $P(b)$ or not. Since $P(a) \subsetneq
P(c)$, we get from the structure of the Q-node that also $P(a) \subsetneq P(b)$.  Let $u \in
P^{\endlft}(a)$. Notice that at least one of $q$ and $u$ belongs to $P^{\endlft}(c)$.

\emph{Case 1: $u \in P^{\endlft}(c)$}. Then $r(u) \le r(q)$ and $P(c) \subsetneq P(b)$; the
situation is depicted in Fig.~\ref{fig:q_nodes_q_and_r_case}a.  We apply Sliding
Lemma~\ref{lem:sliding} to $I_c$, $I_b$, and $r$. We get a pre-drawn interval $z_k \notin P(c)$
covering $r(u)$, and a path $P_{r,z_k}$ consisting of pre-drawn intervals not contained in $P(c)$.
Therefore, $z_k$ is on left of $c$ in the Q-node. Since $I_a$ is on the left of $I_c$, all vertices
of $P_{r,z_k}$ are also not contained in $P(a)$. Thus $z_k$ is on the right of $a$ in the Q-node.

Choose $y_k \in c$ non-adjacent to $z_k$.  By Lemma~\ref{lem:non_adjacent}, there exists $x_k \in a$
non-adjacent to both $z_k$ and $q$.  Since $z_k$ is between $a$ and $c$ in the Q-node, also $x_k$ is
non-adjacent to $y_k$.  Since $y_kqz_k$ is a path avoiding $N[x_k]$, by $(k,\ell)$-CE
Lemma~\ref{lem:kl_ce} we obtain a $(k,1)$-CE obstruction.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_q_and_r_case.eps}
\caption{Proof of Lemma~\ref{lem:q_node_q_and_r_case}. On the left, the pre-drawn
intervals. On the right, their positions in the MPQ-tree. (a) Case 1. (b) Subcase 2A. (c) Subcase 2B.}
\label{fig:q_nodes_q_and_r_case}
\end{figure}

\emph{Case 2: $q \in P^{\endlft}(c)$}. Then $r(q) < r(u)$.
First we argue that, without loss of generality, we can assume that either $\inter q'$ and $\inter
r'$ are disjoint, or $\inter r'$ covers $r(q)$. Suppose that $\inter r'$ is contained in $\inter
q'$. Since $q \in P^{\endlft}(c)$, this implies that $P(c) \subsetneq P(b)$. By applying Sliding
Lemma~\ref{lem:sliding} to $I_c$, $I_b$ and $r$, we obtain a pre-drawn interval $\widetilde r$ not
in $P(c)$ which covers $r(q)$.  We also get a path $P_{r,\widetilde r}$ whose vertices are
pre-drawn and not contained in $P(c)$; since $I_a$ is on the left of $I_c$, they are also not in $P(a)$.
Therefore $\widetilde r$ is between $a$ and $c$ in the Q-node. Further, $\widetilde r$ belongs to
some clique $\widetilde b$ for which $I_{\widetilde b}$ is on the right of $I_c$. From now on, we
work with $\widetilde r$ as $r$, and with $\widetilde b$ as $b$. Hence the
assumption on the relative positions of $\inter q'$ and $\inter r'$ holds.

We apply Sliding Lemma~\ref{lem:sliding} to $I_a$, $I_b$ and $r$, and we get a pre-drawn interval $s
\notin P(a)$ covering $r(u)$. This sliding is weaker that in Case 1: we know that $s$ is on the
right of $a$, but we do not know its position with respect to $c$.  We distinguish three subcases
according to the relative positions of $q$ and $s$ in the Q-node.

\emph{Subcase 2A: $s$ is on the right of $q$.}
The situation is depicted in Fig.~\ref{fig:q_nodes_q_and_r_case}b.  Let $x_k = s$ and $y_k = r$.  If
$\inter q'$ is on the left of $\inter r'$, let $z_k = q$. Otherwise, let $z_k \in c$ be a vertex
non-adjacent to $r$, but possibly adjacent to $x_k$.  Since in every extending
representation $z_k$ is placed on the left of $y_k$, we can apply $k$-FAT
Lemma~\ref{lem:k_fat} to $x_k$, $y_k$ and $z_k$, and get a subgraph $H_k$.  If $\inter q'$ is on the
left of $\inter r'$, then $H_k$ gives a $k$-FAT obstruction.  If $\inter r'$ covers $r(q)$, then
$H_k$ together with $\widetilde u = q$ gives a $k$-FS obstruction.

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_q_and_r_case_obstructions.eps}
\caption{Four possible obstructions obtained in Subcase 2C of the proof of
Lemma~\ref{lem:q_node_q_and_r_case}. (a) If $s \notin P(c)$, we get a $(k,1)$-CE obstruction. (b) If
$\inter q'$ intersects $\inter r'$, we get a $k$-FNS obstruction. Recall that the relative order of
$\ell(q)$ and $\ell(s)$ does not matter. (c) If $\inter q'$ is on the left of $\inter r'$ and
$\ell(q) \le \ell(s)$, we get a $k$-FDS obstruction.  (d) If $\inter q'$ is on the left of $\inter
r'$ and $\ell(s) < \ell(q)$, we get a $k$-EFS obstruction.}
\label{fig:q_nodes_q_and_r_case_obstructions}
\end{figure}

\emph{Subcase 2B: $s$ is on the left of $q$.}
We choose $x_k \in a$ and $y_k \in c$ non-adjacent to $s$; such vertices exist because $s$ is
between $a$ and $c$ in the Q-node. By $(k,\ell)$-CE Lemma~\ref{lem:kl_ce}, we get a $(k,\ell)$-CE
obstruction for $x_k$, $y_k$, $z_k = s$ and $u$. Notice that we can construct a path
$P_{y_k,z_k}$ from $y_k$ to $z_k$ avoiding $N[x_k]$ by applying Sliding Lemma~\ref{lem:sliding} to
$I_a$, $I_c$, and $q$. Thus $\ell = 1$.

\emph{Subcase 2C: $\inter s'$ intersects $\inter q'$.}
Notice that $\inter s'$ also intersects $\inter r'$. Therefore, if $s \notin P(c)$, then it appears
in the Q-node between $a$ and $c$. Let $z_k = s$, we get a $(k,1)$-CE obstruction as follows.  We
choose $y_k \in c$ non-adjacent to $z_k$.  By Lemma~\ref{lem:non_adjacent}, there exists $x_k \in a$
non-adjacent to $q$, $y_k$, and $z_k$. By $(k,\ell)$-CE Lemma~\ref{lem:kl_ce}, we get a $(k,1)$-CE
obstruction for $x_k$, $y_k$, $z_k$ and $u$ as illustrated in
Fig.~\ref{fig:q_nodes_q_and_r_case_obstructions}a; notice that the path $y_kqz_k$ avoids $N[x_k]$.

It remains to deal with the situation when $s \in P(c)$.  Let $z_k = r$. If $\inter q'$ intersects
$\inter {r}'$, let $y_k \in c$ be a vertex non-adjacent to $r$; otherwise let $y_k = q$. By
Lemma~\ref{lem:non_adjacent}, there exists $x_k \in a$ non-adjacent to $q$, $y_k$, and $z_k$.  In
every extending representation, $\inter{y_k}$ is placed on the left of $\inter{z_k}'$, and
$\inter{x_k}$ is placed on the left of $\inter{y_k}$.  Therefore, by $k$-FAT Lemma~\ref{lem:k_fat},
we get a subgraph $H_k$ of a $k$-FAT obstruction.  Together with $u$, $v = s$, $w = q$ (for $y_k \ne
q$), or possibly some of them, we get a $k$-FDS, $k$-EFS, or $k$-FNS obstruction; see
Fig.~\ref{fig:q_nodes_q_and_r_case_obstructions}b, c, and d.\qed
\end{proof}

The case where $P(b) \subsetneq P(c)$ is addressed in Lemmas~\ref{lem:q_node_p_and_q_case}
and~\ref{lem:q_node_q_case}. First, we need an auxiliary result.

\begin{lemma} \label{lem:q_node_q_case_wlog}
If $I_a$ is on the left of $I_c$ and $P(b) \subsetneq P(c)$, there exist $q \in P(c) \setminus
P(b)$ and $r \in P(b) \setminus P(a)$ such that $\inter q'$ is on the right of $I_a$ and on the left
of $I_b$, and $\inter r'$ is on the right of $I_a$, containing $I_c$ and $I_b$.  Without loss of
generality, $\inter q'$ covers $\ell(r)$.
\end{lemma}

\begin{proof}
The proof is depicted in Fig.~\ref{fig:q_nodes_q_case_wlog}. Clearly, there exists $q \in P(c) \setminus
P(b)$. Due to the structure of the Q-node, we also have that $q \notin P(a)$.  Therefore, $\inter
q'$ is between $I_a$ and $I_b$.

\begin{figure}[b!]
\centering
\includegraphics{q_nodes_q_case_wlog.eps}
\caption{Proof of Lemma~\ref{lem:q_node_q_case_wlog}. On the left, the pre-drawn
intervals. On the right, their positions in the MPQ-tree.}
\label{fig:q_nodes_q_case_wlog}
\end{figure}

Next, we argue that there exists $r \in P(b) \setminus P(a)$. For contradiction, assume that $P(b)
\subsetneq P(a)$. Let $v \in P^{\startrt}(b)$; notice that $v$ contains $I_a$ and $I_c$. By the
flipped version of Sliding Lemma~\ref{lem:sliding} applied to $I_c$, $I_b$ and $q$, there exists a
path consisting of pre-drawn intervals not contained in $P(b)$ from $q$ to $z$, where $\inter z'$
covers $\ell(v)$. At least one interval of this path intersects $I_a$, so it belongs to $P(a)$. This
contradicts the fact that $b$ is between $a$ and $c$ in the Q-node. Hence, there exists $r \in P(b)
\setminus P(a)$.

We choose $r$ having rightmost left endpoint. Clearly, $\inter r'$ is on the right of $I_a$, and
contains $I_b$ and $I_c$. Suppose that $\ell(r) < \ell(q)$. Since $r$ has  rightmost left endpoint
among all intervals in $P(b) \setminus P(a)$, and every interval in $P(a)$ has its left endpoint
more to the left, we obtain that $r \in P^{\startrt}(b)$. Therefore, we can apply the flipped
version of Sliding Lemma~\ref{lem:sliding} to $I_c$, $I_b$ and $q$. We get a pre-drawn interval
$\widetilde q \notin P(b)$ covering $\ell(r)$, and a path $P_{q,\widetilde q}$ from $q$ to
$\widetilde q$ whose vertices are not in $b$.  Therefore, $\widetilde q$ is on the right of $b$ in
the Q-node. Let $\widetilde c$ be a maximal clique containing $\widetilde q$. Since $I_{\widetilde
c}$ is contained in $\widetilde q$, it is between $I_a$ and $I_b$. Therefore, we can work with
$\widetilde q$ and $\widetilde c$ instead of $q$ and $c$. Thus we can assume that $\inter q'$ covers
$\ell(r)$.\qed
\end{proof}

For $P(b) \subsetneq P(c)$, we distinguish two cases.

\begin{lemma} \label{lem:q_node_p_and_q_case}
If $I_a$ is on the left of $I_c$, $P(b) \subsetneq P(c)$, and $P(a) \setminus P(c) \ne
\emptyset$, then $G$ and $\calR'$ contain a $k$-FS obstruction.
\end{lemma}

\begin{proof}
The proof is illustrated in Fig.~\ref{fig:q_nodes_p_and_q_case}. By Lemma~\ref{lem:q_node_q_case_wlog}, there exist $q \in P(c) \setminus
P(b)$ and $r \in P(b) \setminus P(a)$ such that $\inter q'$ covers $\ell(r)$. Let $x_k \in P(a) \setminus P(c)$
and $y_k = q$. Then $\inter{x_k}'$ is on the left of $I_c$, and therefore also on the left of $I_b$. Thus
$x_k \notin P(b)$. We infer that $x_k$ is on the left of $b$ in the Q-node, so it is non-adjacent to
$y_k$. In consequence, $\inter{x_k}'$ is on the left of $\inter{y_k}'$. Let $z_k \in b$ be a vertex
non-adjacent to $y_k$.

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_p_and_q_case.eps}
\caption{Proof of Lemma~\ref{lem:q_node_p_and_q_case}. We derive that $\inter{x_k}'$ is on the
left of $\inter q'$, which gives a $k$-FS obstruction based on the positions in the Q-node.}
\label{fig:q_nodes_p_and_q_case}
\end{figure}

If $z_k$ is adjacent to $x_k$, we get a $1$-FS obstruction.  Otherwise, in every extending
representation, $\inter{z_k}$ is to the right of $\inter{y_k}'$.  By $k$-FAT
Lemma~\ref{lem:k_fat}, we get a subgraph $H_k$ of a $k$-FAT obstruction.  Together with $u = r$,
this leads to a $k$-FS obstruction.\qed
\end{proof}

\begin{lemma} \label{lem:q_node_q_case}
If $I_a$ is on the left of $I_c$, $P(b) \subsetneq P(c)$ and $P(a) \subsetneq P(c)$, then $G$ and $\calR'$ contain a
$(k,1)$-CE, $k$-FB, $k$-BI, $k$-FDS, or $k$-EFDS obstruction.
\end{lemma}

\begin{proof}
Let $p \in P^{\endlft}(a)$, and $q$ be the vertex from Lemma~\ref{lem:q_node_q_case_wlog}. By
applying Sliding Lemma~\ref{lem:sliding} to $I_a$, $I_c$ and $q$, we get a pre-drawn interval $s
\notin P(a)$ covering $r(p)$, and path $P_{q,s}$ of intervals not in $P(a)$, so $s$ appears on the
right of $a$ in the Q-node.  Similarly, as in Case 2 of the proof of
Lemma~\ref{lem:q_node_q_and_r_case}, we distinguish three cases according to the relative positions
of $s$ and $q$ in the Q-node; see Fig~\ref{fig:q_nodes_q_case}.

\begin{figure}[t!]
\centering
\includegraphics{q_nodes_q_case.eps}
\caption{Proof of Lemma~\ref{lem:q_node_q_case}. On the left, the pre-drawn
intervals. On the right, their positions in the MPQ-tree. (a) Case 1. (b) Case 2. (c) Case 3, if
$\ell(y_k) \le \ell(s)$. (d) Case 3, if $\ell(y_k) > \ell(s)$.}
\label{fig:q_nodes_q_case}
\end{figure}

\emph{Case 1: $s$ is on the left of $q$.} By Lemma~\ref{lem:non_adjacent}, there exists $x_k \in a$
non-adjacent to all vertices of $P_{q,s}$, in particular non-adjacent to $s$ and $q$.  Let $y_k =
q$, $z_k = s$, and $u = p$.  Clearly, $z_k$ is between $x_k$ and $y_k$ in the Q-node. By
$(k,\ell)$-CE Lemma~\ref{lem:kl_ce} and the existence of $P_{y_k,z_k}$, we get a $(k,1)$-CE
obstruction. Notice that $\inter{y_k}'$ can be made free; see Fig.~\ref{fig:q_nodes_q_case}a.

\emph{Case 2: $s$ is on the right of $q$.} Since $q$ is between $b$ and $s$ in the Q-node, we get
that $s \notin P(b)$. Let $x_k = s$, $z_k = q$, and $u = r$, where $r$ is the vertex from
Lemma~\ref{lem:q_node_q_case_wlog}. There exists $y_k \in b$ non-adjacent to $z_k$ and, by the
structure of the Q-node, also non-adjacent to $x_k$.  Since $y_k$ is adjacent to $p$ and $r$,
$\inter{y_k}$ is between $\inter{x_k}'$ and $\inter{z_k}'$ in every extending representation.  By
$k$-FAT Lemma~\ref{lem:k_fat}, we get a subgraph $H_k$ of a $k$-FAT obstruction.  If $r(r) \le
r(x_k)$, together with $u$, we obtain a $k$-FB or a $k$-BI obstruction. If $r(r) > r(x_k)$, together
with $u$ and $v=p$, we obtain a $k$-BI obstruction; see Fig.~\ref{fig:q_nodes_q_case}b.

\emph{Case 3: $\inter s'$ intersects $\inter q'$.}
Since $s$ contains $I_b$, it belongs to $P(b)$. Let $y_k = q$, $u = p$, $v = s$, and $w = r$; we
note that possibly $s=r$.  By Lemma~\ref{lem:non_adjacent}, there exists $x_k \in a$ non-adjacent to
$y_k$, $v$, and $w$. Since $x_k$ is adjacent to $u$, then $\inter{x_k}$ is on the left of
$\inter{y_k}'$ in every extending representation. Finally, there exists $z_k \in b$ non-adjacent to
$y_k$. Since $z_k$ is adjacent to $u$, $v$, and $w$, we have that $\inter{z_k}$ is on the right of
$\inter{y_k}'$ in every extending representation.

Since $z_k$ is between $x_k$ and $y_k$ in the Q-node, we can apply $k$-FAT Lemma~\ref{lem:k_fat},
which gives a subgraph $H_k$ of a $k$-FAT obstruction.  If $\ell(y_k) \le \ell(v)$, together with
$u$ and $v$, we obtain a $k$-FDS obstruction; see Fig.~\ref{fig:q_nodes_q_case}c. If $\ell(y_k) >
\ell(v)$, together with $u$, $v$, and $w$, we get a $k$-EFDS obstruction; see
Fig.~\ref{fig:q_nodes_q_case}d.\qed
\end{proof}

In summary, we conclude:

\begin{lemma}[The Q-node, Three Subtrees] \label{lem:q_node_three}
If the three cliques creating the obstruction belong to three different subtrees, then $G$ and
$\calR'$ contain a $k$-FAT, $k$-BI ($k \le 2$), $k$-FS, $k$-EFS, $k$-FB, $k$-EFB, $k$-FDS,
$k$-EFDS, $k$-FNS, or $(k,\ell)$-CE obstruction (either $k=\ell=2$, or $k \ge \ell = 1$).
\end{lemma}

\begin{proof}
For an overview, see the diagram in Fig.~\ref{fig:q_nodes_three_subtrees_diagram}. The proof follows
from Lemmas~\ref{lem:q_node_wlog_lemma}, \ref{lem:q_node_containment_case},
\ref{lem:q_node_p_and_r_case}, \ref{lem:q_node_q_and_r_case}, \ref{lem:q_node_q_case_wlog},
\ref{lem:q_node_p_and_q_case}, and \ref{lem:q_node_q_case}.\qed
\end{proof}

config: arxiv


text:
\section{Preliminaries}\label{sec:preliminaries}
\revision{
In this section, we introduce the spaces along with the embedding results, and the useful inequalities and auxiliary results which are used in the Section \ref{sec:mathematical_analysis}.
\subsection{Notation and embedding results}}
Let $\W^{k}_{p}(\Omega;\R^d)$ denote the Sobolev space of order $k$ with weak derivatives in the space  $\L_p(\Omega;\R^d)$ of $p$-integrable functions having value in $\R^d$. Shortly, we write $\W^k_p(\Omega;\R)=\W^k_p(\Omega)$, $\H^1(\Omega)=\W^{1}_{2}(\Omega)$ and $\H_{0,\Sigma}^1(\Omega;\R^d)$ denotes the space of $\H^1(\Omega;\R^d)$ functions with vanishing trace on $\Sigma \subset \p\Omega$, see \cite{brezis2010functional} for more details.

For notational simplicity, we denote $\|\cdot\|_{\L_2(\Omega;\R^d)}$ and $\|\cdot\|_{\L_2(\Sigma;\R^d)}$ by $\|\cdot\|$ and $\|\cdot\|_{\Sigma}$ respectively, $(\cdot,\cdot)_{\L_2(\Omega;\R^d)}$ and $(\cdot,\cdot)_{\L_2(\Sigma;\R^d)}$ by $(\cdot,\cdot)$ and $(\cdot,\cdot)_{\Sigma}$ respectively, and the brackets $\left<\cdot,\cdot\right>$ denote the duality pairing on $\H^{-1}(\Omega)\times\H^1(\Omega)$. The symbol $\C^k(\cdot)$ denotes the space of $k$-times continuously differentiable functions and $\C_b(\cdot)$ denotes the space of bounded continuous functions. Let $\HS$ be a real separable Hilbert space with norm $\|\cdot\|_{\HS}$ and $\HSV$ \revision{be a Hilbert space} such that $\HSV\doublehookrightarrow\HS\hookrightarrow\HSVD$ is a Gelfand triple. We define the Bochner space
$$\L_p(0,T;\HS):=\left\{ \!\varphi: (0,T) \to X : \varphi \text{ Bochner measurable and } \|\varphi\|_{\L_p(0,T;\HS)}^p\!:=\int_0^T\!\!\! \|\varphi(t)\|_{\HS}^p \dd t < \infty\right\},$$
where $p \in [1,\infty)$. For $p=\infty$ we modify it in the usual sense with the Bochner norm $$\|\varphi\|_{\L_\infty(0,T;\HS)}:=\esssup_{t\in (0,T)} \|\varphi(t)\|_{\HS}.$$
We introduce the Sobolev--Bochner space
$$\W^{1}_{p,q}(0,T;\HSV,\HSVD):=\{ \varphi \in \L_p(0,T;\HSV) : \partial_t \varphi \in \L_q(0,T;\HSVD) \},$$

and its fractional counter-part
\begin{equation*}
    \W^{\alpha}_{p,q}(0,T;\varphi_0,\HSV,\HSVD):=\{\varphi\in\L_p(0,T;\HSV): g_{1-\alpha}*(\varphi-\varphi_0)\in {}_{0}\W^{1}_{p,q}(0,T;\HSV,\HSVD)\},
\end{equation*}
where $\varphi_0\in \HS$ and ${}_{0}\W^{1}_{p,q}$ denotes functions in $\W^{1}_{p,q}$ with vanishing trace at $t=0$. This definition of the fractional Sobolev--Bochner space indeed corresponds to the space of integrable fractional time-derivatives.

In the existence proof we typically apply compactness results. A special case of the Aubin--Lions compactness theorem  \cite[Corollary 4]{simon1986compact},  states the following compact embedding
\begin{equation} \label{Lem_Aubin}
p\in[1,\infty), \quad \W^{1}_{p,1}(0,T;\HSV,\HSVD)\doublehookrightarrow \L_p(0,T;\HS).
\end{equation}

In the fractional setting, we have the following analogous result
\begin{equation} \label{Lem_FractionalAubin}
\begin{aligned}
p\in[1,\infty), r\in\left(\frac{p}{1+p\alpha},\infty\right)\cap[1,\infty),\quad&
 \W^{\alpha}_{p,r}(0,T;\varphi_0,\HSV,\HSVD)\doublehookrightarrow \L_p(0,T;\HS),
\end{aligned}
\end{equation}
where $\varphi_0 \in \HS$ is given. The proof follows the lines of \cite[Theorem 4.2]{li2018some} using the estimates from \cite[Proposition 3.4]{li2018some}.

We also employ the following continuous embedding into the time-continuous function space to establish additional regularity of the solutions of the partial differential equations,
\begin{equation} \label{Lem_InterpolationEmbedding}
\W^1_{2,2}(0,T;\HSV,\HSVD) \hookrightarrow \C([0,T];[\HSV,\HSVD]_{1/2}),
\end{equation}
where $[\HSV,\HSVD]_{1/2}$ denotes the interpolation space of order $1/2$ of $\HSV$ and $\HSVD$, see \cite[Theorem 3.1, Chapter 1]{lions2012non}, e.g. $[\H_0^1(\Omega),\H^{-1}(\Omega)]_{1/2}=\L_2(\Omega)$. In the fractional setting, we have a continuous embedding analogous to the one above. Indeed,
\begin{equation}\label{Lem_ContinousEmbedding_fractional}
    \varphi_0\in \HS,\, \varphi\in \W^{\alpha}_{2,2}(0,T;\varphi_0,\HSV,\HSVD)\implies g_{1-\alpha}*(\varphi-\varphi_0)\in \C([0,T];\HS),
\end{equation}

after possibly being redefined on a set of measure zero, see \cite[Theorem 2.1]{zacher2009weak}.

Throughout the whole paper, we denote by $C$ a generic positive constant which is independent of the unknowns $\phi, \mu, \vec{u}, \psi$ and $\chi$.

\subsection{Useful inequalities and auxiliary results}
We recall the Poincar\'e--Wirtinger, Poincar\'e, Korn and Sobolev inequalities, see \cite{brezis2010functional,ciarlet2013linear},
\begin{align}\label{inequality:Poincare_Korn_Sobolev}
    \begin{aligned}
	\|\varphi-\overline{\varphi}\| & \leq C \|\nabla \varphi\| && \text{for all } \varphi \in \H^1(\Omega),   \\
	\|\varphi\|              & \leq C  \|\nabla \varphi\| && \text{for all } \varphi \in \H^1_{0,\Sigma}(\Omega), \\
	\|\varphi\|_{\H^1(\Omega;\R^d)}              & \leq C  \|\symgrad(\varphi)\| && \text{for all } \varphi \in \H^1_{0,\Sigma}(\Omega;\mathbb{R}^d),
	\\[-.18cm]
	 \|\varphi\|_{\W^{m}_{q}(\Omega;\R^d)} & \leq C \|\varphi\|_{\W^{k}_{p}(\Omega;\R^d)} && \text{for all } \varphi \in \W^{k}_{p}(\Omega;\R^d), \quad k-\frac{d}{p} \geq m-\frac{d}{q}, \quad k \geq m,
\end{aligned}
\end{align}
where $\overline{\varphi}=\frac{1}{|\Omega|}\int_\Omega \varphi(\vec{x}) \,\textup{d} x$ denotes the mean of $\varphi$. Also, we often make use of the $\epsilon$-Young and the Young convolution inequalities, given by
\begin{align}\label{inequality:Youngs}
    \begin{aligned}
    ab &\leq \epsilon a^p + \frac{b^q}{q (\epsilon p)^{q/p}} && \text{for all } a,b \geq 0, \quad  \frac{1}{p} + \frac{1}{q} = 1, \quad\epsilon>0,\\
    \| \varphi_1 * \varphi_2 \|_{\L_r(\Omega)} &\leq \| \varphi_1  \|_{\L_p(\Omega)}  \| \varphi_2 \|_{\L_q(\Omega)} && \text{for all } \varphi_1 \in \L_p(\Omega), \varphi_2 \in \L_q(\Omega), \quad \frac{1}{p} + \frac{1}{q} = \frac{1}{r}+1,
    \end{aligned}
\end{align}
and H\"older's inequality, given by
\begin{align}\label{inequality:Holder}
    \begin{aligned}
    \| \varphi_1 \varphi_2 \|_{\L_1(\Omega)} &\leq \| \varphi_1  \|_{\L_p(\Omega)}  \| \varphi_2 \|_{\L_q(\Omega)} && \text{for all } \varphi_1 \in \L_p(\Omega), \varphi_2 \in \L_q(\Omega), \quad \frac{1}{p} + \frac{1}{q} = 1,
    \end{aligned}
\end{align}
see \cite[Appendix B]{evans2010partial}.

The following inequality, which is analogous to the chain rule, is required to obtain a priori estimates to prove the existence of weak solutions of a time-fractional partial differential equation.
\begin{lemma} Suppose $\varphi\in\L_2(0,T;\L_2(\Omega,\R^d))$, and there exists $\varphi_0\in \L_2(\Omega,\R^d)$ such that $g_{1-\alpha}*(\varphi-\varphi_0)\in{}_{0}\W^1_{2,2}(0,T;\L_2(\Omega,\R^d),\L_2(\Omega,\R^d))$. Let $\Func\in\C^1(\R^d)$ be a convex function such that $g_{1-\alpha}*\int_\Omega \Func(\varphi)\dd x\in {}_{0}\W^1_1(0,T)$.

Then for almost all $t\in(0,T)$, we have
\begin{equation}\label{basic_inequality_fractional_chain_rule}
\begin{aligned}
\left( \Func'(\varphi(t)),\partial_t(g_{1-\alpha}*\varphi)(t)\right) &\geq \partial_t\left(g_{1-\alpha}*\int_\Omega \Func(\varphi)\dd x\right) (t)\\
&+ \left(-\int_\Omega \Func(\varphi(t))\dd x
+\left(\Func'(\varphi(t)),\varphi(t)\right)\right)g_{1-\alpha}(t).
\end{aligned}
\end{equation}
        \label{Lem_basic_inequality_fractional_chain_rule}
\end{lemma}
\begin{proof}
Let $k\in\W^1_1(0,T)$. Then from a straightforward computation, we have the following identity for almost all $t\in[0,T]$
\begin{equation}
\begin{aligned}
\int_\Omega \Func'(\varphi(t)):\partial_t(k*\varphi)(t)\dd x = \partial_t\left(k*\int_\Omega \Func(\varphi)\dd x\right)(t) +  k(t) \left( \int_\Omega -\Func(\varphi(t))+\Func'(\varphi(t)):\varphi(t)\dd x\right)\\
- \int_0^t \frac{\dd}{\dd \rm{s}} k(s) \left(\int_\Omega  \Func(\varphi(t-s))-\Func(\varphi(t)) - \Func'(\varphi(t)):(\varphi(t-s)-\varphi(t)) \dd x\right)  \mathrm{d}s.
\end{aligned}
\end{equation}
We remark that the identity for functions with values in $\R$ can be seen in \cite[Lemma 6.1]{kemppainen2016decay} and the integrated form for functions in $\R^d$ can be seen in \cite[Lemma 18.4.4]{gripenberg1990volterra}. We note that if $k$ is non-negative and non-increasing then the last term is positive, since $\Func$ is a convex functional. The inequality \eqref{basic_inequality_fractional_chain_rule} follows as in \cite[Theorem 2.1]{vergara2008lyapunov} by approximating $g_{1-\alpha}$ with a more regular kernel $k_n\in\W^{1,1}(0,T)$, using the above identity and taking the limit.
\end{proof}

A particular form of Lemma \ref{Lem_basic_inequality_fractional_chain_rule} with $\Func(\varphi)=\frac{1}{2}\varphi^2$ is proved in \cite[Theorem 2.1]{vergara2008lyapunov} with functionals having value in any Hilbert space, and we have for almost all $t\in[0,T]$

\begin{equation}\label{basic_inequality_fractional}
\frac{1}{2}\dt (g_{1-\alpha}*\|\varphi\|^2)(t) + \frac{1}{2} g_{1-\alpha}(t)\|\varphi(t)\|^2 \leq \left(\varphi(t),\partial_t (g_{1-\alpha}*\varphi)(t)\right).
\end{equation}

\begin{remark}\label{rem:kernel_property1}
The first term in \eqref{basic_inequality_fractional} is well-posed for $\varphi\in\W^{\alpha}_{2,2}(0,T;\varphi_0,\L_2(\Omega,\R^d),\L_2(\Omega,\R^d))$ because of the following implication, which indeed holds true for a wide class of kernels and is proved in \cite[Proposition 2.1]{vergara2008lyapunov},
\begin{equation}\label{eqn:kernel_property}
\varphi\in\L_2(0,T;\H),\, g_{1-\alpha}*\varphi\in{}_{0}\H^1(0,T;\H)\implies g_{1-\alpha}*\|\varphi\|_{\H}^2\in{}_{0}\W^{1}_{1}(0,T).
\end{equation}
\end{remark}

The following are the Gronwall--Bellman and generalised Gronwall--Bellman with singularity, used for providing explicit bounds on solutions.
\begin{lemma}[Gronwall--Bellman, cf. {\cite[Appendix B]{evans2010partial}}] Assume $C_1,C_2\geq 0$ are constants. If $\varphi(t)$ is a non-negative, integrable function on $[0,T]$, satisfying
		$$\varphi(t) \leq C_1 + C_2 \int_0^t \varphi(s) \, \dd s,$$
for almost all $t\in [0,T]$, then it holds
$\varphi(t) \leq C_1 e^{C_2 T}$
for almost all $t \in [0,T]$.
		\label{Lem_Gronwall}
\end{lemma}

\begin{lemma}[Generalized Gronwall--Bellman, cf. {\cite[Corollary 1]{ye2007generalized}}]
Assume that $a(t)$ is a non-negative integrable function on the interval $[0,T]$, and $b>0$ is a constant. If $\varphi(t)$ is a non-negative, integrable function satisfying
\begin{equation*}
\varphi(t)\leq a(t)+\frac{b}{\Gamma(\alpha)}\int_0^t (t-s)^{\alpha-1}\varphi(s)\, \textup{d}s,
\end{equation*}
for almost all $t\in[0,T]$, then for almost all $t\in[0,T]$ the following holds true,
\begin{equation*}
    \varphi(t)\leq a(t) + \int_0^t b\Gamma(\alpha) (t-s)^{\alpha-1} E_{\alpha,\alpha}(b\Gamma(\alpha)(t-s)^{\alpha}) a(s)\dd s,
\end{equation*}
where $E_{\alpha,\alpha}(x)=\sum_{k=0}^{\infty}\frac{x^k}{\Gamma(\alpha k +\alpha)}$ is the two-paramater Mittag--Leffler function.
	\label{Lem_Gronwall_fractional}
\end{lemma}

\begin{lemma}[Fractional integration by parts, cf. {\cite[Proposition 3.1]{djilali2018galerkin}}]
Let $\varphi_1\in\L_2(0,T;\H)$ and $\varphi_2\in\H^1(0,T;\H)$. Then
\begin{equation*}
\begin{aligned}
\int_0^T\left(\p_t(g_{1-\alpha}*\varphi_1)(t),\varphi_2\right)\dd t  = -\int_0^T\left(\varphi_1,(g_{1-\alpha}*'\p_t\varphi_2)(t)\right)\dd t+\left((g_{1-\alpha}*\varphi_1)(t),\varphi_2\right)|^{t=T}_{t=0},

\end{aligned}
\end{equation*}
where the convolution $*'$ is defined by $(g_\alpha*'\varphi)(t)=\int_t^T g_\alpha(t-s)\varphi(s)\dd s$.
		\label{Lem_frac_integration_by_parts}
\end{lemma}


TITLE: Find the singular value decomposition.
QUESTION [0 upvotes]: Consider the matrix:
$A= \begin{bmatrix}
    -1&1&0\\
    -1&1&0\\
    1&1&0\\
    1&1&0
  \end{bmatrix}$
Find the singular value decomposition (SVD). Then indicate the corresponding orthonormal basis for: $C(A)$,$N(A)$,$C(A^T)$, and $N(A^T).$
goal: $A = U \Sigma V^T$
U and V are orthogonal matrices. Their columns are orthonormal sets. $\Sigma$ is a diagonal matrix  with non-negative entries.
Equations:
$(1) A^TA = V\Sigma^T\Sigma V^T \\(2) AV=U\Sigma$
Firstly, $A^TA = \begin{bmatrix}
    4&0&0\\
    0&4&0\\
    0&0&0
  \end{bmatrix}$
Compute eigenvalues: $\lambda_1 = 4 \lambda_2 = 4 \lambda_3 = 0$
The eigenvectors:
$v_1= \begin{bmatrix}
1\\
0\\
0
\end{bmatrix}$,$v_2= \begin{bmatrix}
0\\
1\\
0
\end{bmatrix}$ $v_3 = \begin{bmatrix}
0\\
1\\
0
\end{bmatrix}$
Then, $V =\begin{bmatrix}
   1&0&0\\
   0&1&0\\
   0&0&1
  \end{bmatrix}$
We get, $AV = \begin{bmatrix}
   -1&1&0\\
   -1&1&0\\
    1&1&0\\
    1&1&0
  \end{bmatrix}=U\Sigma $(This is $U\Sigma$ combined, to separate we need entries to have unit length).
$U=\begin{bmatrix}
   -\frac{1}{2}&\frac{1}{2}&0\\
   -\frac{1}{2}&\frac{1}{2}&0\\
    \frac{1}{2}&\frac{1}{2}&0\\
    \frac{1}{2}&\frac{1}{2}&0
  \end{bmatrix}$ and $\Sigma$ is column space with square roots of the eigenvalues.
$\Sigma =\begin{bmatrix}
2\\
2\\
0
\end{bmatrix}$.
Then here is my goal equation:$A = U \Sigma V^T$
$\Rightarrow A= \begin{bmatrix}
    -1&1&0\\
    -1&1&0\\
    1&1&0\\
    1&1&0
  \end{bmatrix} =\begin{bmatrix}
   -\frac{1}{2}&\frac{1}{2}&0\\
   -\frac{1}{2}&\frac{1}{2}&0\\
    \frac{1}{2}&\frac{1}{2}&0\\
    \frac{1}{2}&\frac{1}{2}&0
  \end{bmatrix}\begin{bmatrix}
2\\
2\\
0
\end{bmatrix}\begin{bmatrix}
   1&0&0\\
   0&1&0\\
   0&0&1
  \end{bmatrix}$
There must be an error. Not sure how to get the SVD.
Lastly,
$rref = \begin{bmatrix}
   1&-1&0\\
   0&1&0\\
    0&0&0\\
    0&0&0
  \end{bmatrix}$
The first column of U is spans the column space of A: $C(A) = \begin{bmatrix}
-\frac{1}{2}\\
-\frac{1}{2}\\
\frac{1}{2}\\
\frac{1}{2}
\end{bmatrix}$
The first column of V spans the row space of A: $C(A^T) =\begin{bmatrix}
1\\
0\\
0
\end{bmatrix}$
The second column of V spans the null space of A: $N(A) = \begin{bmatrix}
0\\
1\\
0
\end{bmatrix}$
The second and third columns of U span the left null space: $N(A^T)\{\begin{bmatrix}
\frac{1}{2}\\
\frac{1}{2}\\
\frac{1}{2}\\
\frac{1}{2}
\end{bmatrix},\begin{bmatrix}
0\\
0\\
0\\
0
\end{bmatrix} \} $

REPLY [1 votes]: You have written $\Sigma$ as a vector. It is a diagonal matrix. The rank of $A$ is two (why?). Thus, column space and row-space should have two vectors in their basis.


TITLE: "Space" of L-functions
QUESTION [2 upvotes]: Ok, so this is a rather loose question (but one that has been on my mind for some time) so I don't expect any rigorous (but hopefully serious and thoughtful) answers.
Think of an L-function attached to some motive (I refrain from giving a more detailed description of what this means; if in doubt think of Artin L-functions). Is there in any sense a ''space'' (vector space, scheme,...) of L-functions?
I know that this is not a very precise question, but my thoughts on this are not very precise either (more like a vague dream world), but I know that there are people out there on this forum who know a lot about L-functions. Hopefully some of these can make my dream world a little more real, or shatter it completely.
I should also say that the recent philosophical question modularity gave me the courage (!) to ask the present one.
Edit: I should perhaps stress that I'm not quite sure myself of what I mean but I'm hoping for experts to give their informed opinions of what could be true.
Edit: Ok, to accomodate Gerhard P's comment below in some small way let me give the following motivation.
Suppose given a Galois representation (over some fixed base). I'm particularly thinking of those rep's with finite image. To such a representation you can attach an L-function as the Artin L-function of the fixed field of the kernel of the rep. Suppose now that you deform the representation in "a moduli space" (or in some parameter space) of Galois representations. Is there a sense in which the L-function deforms with it to a family of L-functions in some "space" of L-functions?
This can (probably) be generalized to other motives.

REPLY [2 votes]: Just to summarize some of the comments:
Strong Multiplicity One says that if the local factors of two (cuspidal) automorphic L-functions agree at all but finitely many places, then they agree at all places ("all but finitely many places" can conjecturally be replaced with "all places in a set of Dirichlet density greater than $1-1/2n^2$"). So, in this sense, the space of automorphic L-functions is rigid (you can't make changes to a small number of places and get something automorphic). This can fail for residual representations but I don't have good examples to share.
In another sense, you could deform an L-function $L(s,\pi)$ by considering $L(s,\pi\otimes|\cdot|^z)=L(s+z,\pi)$, where $\pi\otimes|\cdot|^z$ is $\pi$ with its central character twisted by $|\cdot|^z$ (some care is necessary if $z$ is not imaginary). Also, Eisenstein series exist in meromorphically parametrized families, so their L-functions also exist in families. For example, the L-function for the classical non-holomorphic Eisenstein series $E_z$ is $\xi(s+z)\xi(s+1-z)$.
Regarding vector spaces, note that the sum of two automorphic L-functions will (generally) not have an Euler product, so won't be automorphic in the usual sense.
Finally, just to explicitly tie the above in with the original question, Artin L-functions are conjecturally cuspidal automorphic for $GL_n$, and motivic $L$-functions are conjecturally automorphic for some group $G$ which can them be conjecturally transfered to $GL_n$.


TITLE: Proving the image measure $\mu_\psi$ to be $\sigma$-finite as part of the proof of a corollary of Radon-Nikodyn theorem
QUESTION [3 upvotes]: Definition of image measure
Let $(X,\mathcal{A},\mu)$ be a measure space and $(Y,\mathcal{E})$ be a measurable space. Let $\psi: X\to Y$ be a measurable function. Let  $\mu_\psi$ denote the image measure:
$\mu_\psi(B)=\mu(\psi^{-1}(B)), \forall B\in \mathcal{E} $.
Radon-Nikodym theorem
Let $(X,\mathcal{A})$ be a measurable space and  let  $\mu$ and $\nu$ be $\sigma-$finite measures over it. Let $\nu $ be absolutely continuous  with respect to $\mu$. Then, there exists a measurable function $f\ge 0$, unique a.e.  such that
$\nu(A)=\int_A f d\mu, \forall A\in \mathcal {A}$
with $f$ called the R-N derivative
Proposition
Let $(X,\mathcal{A},\mu)$ and $(Y,\mathcal{E},\lambda) $  be measure spaces. Let $\psi: X\to Y$ be a measurable function and $\mu_\psi$ denote the image measure of $\mu$ with respect to $\psi$. Let $\mu$ and $\lambda$ be $\sigma$-finite and  $\mu_\psi$ absolutely continuous with respect to $\lambda$ with Radon-Nikodyn derivative $f_\psi=\frac{d\mu_\psi}{d\lambda}$. Let $ g:Y\to \overline{ \mathbb{R} } $ be a measurable function.
Then$\int_Xg\circ\psi d\mu=\int_Ygd\mu_\psi=\int_Y g f_\psi d \lambda$
In order to prove the above proposition,which follows directly from  the R-N theorem, I need $\mu_\psi$ to be $\sigma$-finite. My lecturer said that follows from $\mu $ and $\lambda$ being $\sigma$-finite. But I am unable to prove it. Furthermore I've seen a number of posts where it says that the image measure of a $\sigma$-finite measure is not sigma finite. But in this case there's also $\lambda$ that is $\sigma$-finite, so  maybe that helps?  How do I prove $\mu_\psi$ is sigma finite?
My thoughts:
Since $\lambda$ is $\sigma$-finite, there exists  a sequence $\{B_n\}$ of $\mathcal{E}$-measurable  functions such that $\lambda(B_n)<\infty$ and $\bigcup_n B_n=Y$
Since $\psi$ is measurable, the sequence $\psi^{-1}(B_n)$ is made of $\mathcal{A}$-measurable sets such that $\bigcup_n\psi^{-1}(B_n)=\psi^{-1}(\bigcup_n B_n)=\psi^{-1}(Y)=X$.
So the $\psi^{-1}(B_n)$ covers X, but I don't think I can deduce from this that  $\mu(\psi^{-1}(B_n))<\infty$  .How should I do it then?

REPLY [1 votes]: If I understand you correctly,
then from the assumptions that $\mu$ and $\lambda$ are $\sigma$-finite
and that $\mu_\psi$ is absolutely continuous with respect to $\lambda$
you want to derive that $\mu_\psi$ is also $\sigma$-finite.
But I believe that the following presents a counter-example.
Let $X = Y = \mathbb{R}$,
let $\mu$ and $\lambda$ both be the Lebesgue measure,
and let $\psi:X\to Y$ be defined by
\begin{equation*}
\psi(x) = x - [x]
\end{equation*}
for every $x\in\mathbb{R}$,
where $[x]$ is $x$ rounded down.
So $\psi$ can be thought of as a periodic "saw-shaped" function
with "teeth" that range from $0$ to $1$.
A set $B$ in $Y$ is disjoint from $[0,1)$
if and only if $\psi^{-1}(B)$ is empty.
So we can restrict attention to subsets $B$ of $[0,1)$.
Let $B$ be such a set.
For any $x$ in $B$ and any integer $n$,
\begin{equation*}
\psi(n + x) = n + x - [n + x] = n + x - n = x,
\end{equation*}
so
\begin{equation*}
\psi^{-1}(B)
= \{n + x:x\in B, n\in\mathbb{Z}\}
=\bigcup_{n\in\mathbb{Z}}\{n + x:x\in B\}
.
\end{equation*}
It follows that
\begin{equation*}
\mu_\psi(B)
=
\mu(\psi^{-1}(B))
=
\sum_{n\in\mathbb{Z}}\mu(\{n + x:x\in B\})
=
\sum_{n\in\mathbb{Z}}\mu(B)
\end{equation*}
where in the last step I used that the Lebesgue measure $\mu$
is translation invariant.
If $\lambda(B)$ equals $0$ then so does $\mu(B)$,
because both are the Lebesgue measure,
and then $\mu_\psi(B) = 0$,
and so $\mu_\psi$ is absolutely continuous with respect to $\lambda$.
But if $\lambda(B)$ does not equal $0$,
then $\mu_\psi(B)$ is infinite.
So $\mu_\psi$ cannot be $\sigma$-finite.
EDIT:
Actually,
for $\mu_\psi$ to have a Radon-Nikodym derivative with respect to $\lambda$,
which I think is what you are actually after,
I don't think you need $\mu_\psi$ to be $\sigma$-finite.
I will just quote the Radon-Nikodym theorem and Exercise 6 from chapter 4 in Donald Cohn's Measure Theory:
"Theorem 4.2.2 (Radon-Nikodym theorem)
Let $(X,\mathcal{A})$ be a measurable space,
and let $\mu$ and $\nu$ be $\sigma$-finite positive measures on $(X,\mathcal{A})$.
If $\nu$ is absolutely continuous with respect to $\mu$,
then there is an $\mathcal{A}$-measurable function $g:X\to[0,\infty)$
such that $\nu(A)=\int_A gd\mu$ holds for each $A$ in $\mathcal{A}$.
The function $g$ is unique up to $\mu$-almost everywhere equality."
"Exercise 6. Show that the assumption that
$\nu$ is $\sigma$-finite can be removed from Theorem 4.2.2
if $g$ is allowed to have values in $[0,\infty]$.
(Hint: Reduce the general case to the case where $\mu$ is finite.
For each positive integer $n$ choose a Hahn decomposition $(P_n,N_n)$
for the signed measure $\nu - n\mu$;
then consider the measures
$A\mapsto \nu(A\cap(\cap_n P_n))$
and
$A\mapsto \nu(A\cap(\cap_n P_n)^c)$.)"


TITLE: Show $|\mathbb R| = |(0, 1)|$
QUESTION [1 upvotes]: There does exist this question here below, but my question is a bit different:
Prove that $|\mathbb{R}| = |(0, 1)|$.
Here is my proof below from the given hint:
Consider $f: (0, 1) \to \mathbb R$ as $f(x) = \tan\left(\left(\pi(x - \frac 12\right)\right)$.
Note, $f$ is continuous on $(0, 1).$ Let $x \in (0, 1).$ Then $\displaystyle{\lim_{x \to 1^-}f(x) = \infty, \ \lim_{x \to 0^+}f(x) = -\infty}$ and so $f(x) \in (-\infty, \infty) = \mathbb R.$ Now let $[x_1, x_2] \subset (0, 1).$ Then $[f(x_1), f(x_2)] \in  f(0, 1).$ By Intermediate Value Theorem, for any $d \in [f(x_1), f(x_2)]$, there's some $c \in [x_1, x_2]$ s.t. $f(c) = d.$ Thus by definition, $f$ is surjective.
Again, let $x_1, x_2 \in (0, 1)$ s.t. $x \ne x_2.$ WLOG, suppose $x_1 < x_2.$ Since $f$ is strictly increasing on $(0, 1)$, we have $f(x_1) < f(x_2)$ meaning $f(x_1) \ne f(x_2)$ and so $f$ is injective by definition $\square$
I realize I have to prove $f$ is both continuous and strictly increasing on its domain and the fact that the given limits diverge, but for the purposes of this proof Im not worried about that.
My question:
Assuming the proof of surjectivity of $f$ is correct (?), how can we be sure there is no  $y \in \mathbb R$ s.t. $y \not \in \bigcup f([a, b])$ for arbitrary $a, b \in (0, 1)?$ Are the reals and the union of all the closed subsets of $f(0, 1)$ equivalent? Thanks.
Edit:
Nevermind, for some reason I thought $|f(0, 1)| < |\mathbb R|$ even though right at beginning I showed $\mathbb R$ is actually the image of $f.$ Brainfart moment, sorry.

REPLY [1 votes]: Essentially you have to use the fact that $\lim_{x\rightarrow 1^-} f(x)=+\infty$ and $\lim_{x\rightarrow 0^+} f(x)=-\infty$. By definition, they are saying for any $y$, you can find $a,b$ such that $f(a)<y<f(b)$. So $y\in f([a,b])$, which is a subset of the union of all such sets. Hence, any $y$ must be in $\cup f([a,b])$.