text:
\begin{document}

\title[Covering
$3$-edge-coloured random graphs with monochromatic trees]{Covering
$3$-edge-coloured random graphs with monochromatic trees}

\author[Y.~Kohayakawa]{Yoshiharu Kohayakawa}
\address{Instituto de Matem\'{a}tica e Estat\'{\i}stica, Universidade de S\~{a}o
  Paulo, Brazil}
\email{yoshi@ime.usp.br}

\author[W.~Mendon\c{c}a]{Walner Mendon\c{c}a}
\address{Instituto Nacional de Matem\'{a}tica Pura e Aplicada, Rio de Janeiro,
Brazil}
\email{walner@impa.br}

\author[G.~O.~Mota]{Guilherme Oliveira Mota}
\address{Instituto de Matem\'{a}tica e Estat\'{\i}stica, Universidade de S\~{a}o
  Paulo, Brazil}
\email{mota@ime.usp.br}

\author[B.~Sch\"{u}lke]{Bjarne Sch\"{u}lke}
\address{Fachbereich Mathematik, Universit\"{a}t Hamburg, Hamburg,
Germany}
\email{bjarne.schuelke@uni-hamburg.de}

\thanks{\rule[-.2\baselineskip]{0pt}{\baselineskip}
  Y.~Kohayakawa was partially supported by CNPq (311412/2018--1, 423833/2018--9) and FAPESP (2018/04876--1).

  G.~O.~Mota was partially supported by CNPq
  (304733/2017--2, 428385/2018--4) and FAPESP (2018/04876--1).

  W.~Mendon\c{c}a was partially supported by CAPES (88882.332408/2010--01).

  B.~Sch\"ulke was partially supported by G.I.F. Grant Agreements
  No.~I-1358--304.6/2016.

  The cooperation of the authors was supported by a joint CAPES/DAAD
  PROBRAL project (Proj.~430/15, 57350402, 57391197).

  This study was financed in part by CAPES, Coordenação
  de Aperfeiçoamento de Pessoal de Nível Superior, Brasil,
  Finance Code 001.

  FAPESP is the S\~ao Paulo Research Foundation.  CNPq is the National
  Council for Scientific and Technological Development of Brazil.
}

\subjclass{05C80 (primary); 05C70 (secondary)}
\keywords{Graph partitioning, monochromatic trees, random
  graphs}

\begin{abstract}
  We investigate the problem of determining how many monochromatic trees are
  necessary to cover the vertices of an edge-coloured random graph. More
  precisely, we show that for $p\gg n^{-1/6}{(\ln n)}^{1/6}$, in any
  $3$-edge-colouring of the random graph $G(n,p)$ we can find three monochromatic
  trees such that their union covers all vertices. This improves, for three
  colours, a result of Buci\'c, Kor\'andi and Sudakov.
\end{abstract}

\maketitle

\section{Introduction}

Given a graph $G$ and a positive integer $r$, let $\tc_r(G)$ denote the minimum
number $k$ such that in any $r$-edge-colouring of $G$, there are $k$
monochromatic trees $T_1,\ldots,T_k$ such that the union of their vertex sets covers $V(G)$,
i.e.,
\begin{align*}
	V(G) = V(T_1)\cup \dots \cup V(T_k).
\end{align*}
We define $\tp_r(G)$ analogously by requiring the union above to be disjoint.

It is easy to see that $\tp_2(K_n) = 1$ for all $n\geq 1$, and Erd\H{o}s,
Gy\'arf\'as~and Pyber~\cite{EGP91} proved that $\tp_3(K_n) = 2$ for all
$n\geq 1$, and conjectured that $\tp_r(K_n)=r-1$ for every $n$ and $r$. Haxell
and Kohayakawa~\cite{HaKo96} showed that $\tp_r(K_n) \leq r$ for all
sufficiently large $n \ge n_0(r)$. We remark that it is easy to see that
$\tc_r(K_n) \leq r$ (just pick any vertex $v \in V(K_n)$ and let~$T_i$, for
$i\in[r]$, be a maximal monochromatic tree of colour $i$ containing $v$), but it
is not even known whether or not $\tc_r(K_n) \leq r-1$ for every $n$ and $r$ (as
would be implied by the conjecture of Erd\H{o}s, Gy\'arf\'as~and Pyber).

Concerning general graphs instead of complete graphs, Gy\'arf\'as~\cite{Gyarfas}
noted that a well-known conjecture of Ryser on matchings and transversal sets in
hypergraphs is equivalent to the statement that for every graph $G$ and
integer~$r\geq 2$, we have $\tc_r(G)\leq (r-1)\alpha(G)$. In particular, Ryser's
conjecture, if true, would imply that $\tc_r(K_n) \leq r-1$, for every $n\geq 1$
and $r \geq 2$. Ryser's conjecture was proved in the case $r = 3$ by
Aharoni~\cite{Aharoni}, but for $r\geq 4$ very little is known. For example,
Haxell and Scott~\cite{HaSc12} proved (in the context of Ryser's original
conjecture) that there exists $\epsilon >0$ such that for $r\in \{4,5\}$, we
have $\tc_r(G)\leq (r-\epsilon)\alpha(G)$, for any graph $G$.

Bal and DeBiasio~\cite{BaDe} initiated the study of covering and partitioning
random graphs by monochromatic trees. They proved that if $p\ll
{\left(\frac{\log n}{n}\right)}^{1/r}$, then with high probability\footnote{We
  will write shortly \emph{w.h.p.} for \emph{with high probability}.} we have
$\tc_r(\gnp) \to \infty$. They conjectured that for any $r\geq 2$, this was the
correct threshold for the event $\tp_r(\gnp) \leq r$. Kohayakawa, Mota and
Schacht~\cite{KoMoSc} proved that this conjecture holds for $r=2$, while Ebsen,
Mota and Schnitzer\footnote{A description of this construction can be found
  in~\cite{KoMoSc}.} showed that it does not hold for more than two colours.

Buci\'c, Kor\'andi and Sudakov~\cite{BuKoSu} proved that if $p \ll
{\left(\frac{\log n}{n}\right)}^{\sqrt r/2^{r-2}}$, then w.h.p.\ we have
$\tc_r(\gnp) \geq r+1$, which implies that the threshold for the event
$\tc_r(G)\leq r$ is in fact significantly larger than the one conjectured by Bal
and DeBiasio when $r$ is large. Buci\'c, Kor\'andi and Sudakov also proved that
w.h.p.\ we have $\tc_r(\gnp) \leq r$ for $p \gg {\left(\frac{\log
      n}{n}\right)}^{1/2^r}$. They were also able to roughly determine the
typical behaviour of $\tc_r(G(n,p))$ in terms of the range where $p$ lies in
(see~\cite[Theorem~1.3 and Theorem~1.4]{BuKoSu}).

Considering colourings with three colours, the results from~\cite{BuKoSu} imply
that if $p \gg {\left( \frac{\log n}{n} \right)}^{1/8}$, then w.h.p.\ we have
$\tc_3(G(n,p))\leq 3$, and if ${\left( \frac{\log n}{n} \right)}^{1/6} \ll p \ll
{\left(\frac{\log n}{n} \right)}^{1/7}$, then w.h.p.\ $\tc_3(G(n,p))\leq 88$. Our
main result improves these bounds for three colours.

\begin{theorem}\label{main_res}
  If $p = p(n)$ satisfies $p \gg {\big(\frac{\log n}{n}\big)}^{1/6}$, then with high probability we
  have
  \[
    \tc_3\big( G(n,p) \big) \leq 3.
  \]
\end{theorem}

It is easy to see that if $p = 1 - \omega(n^{-1})$, then w.h.p.\ there is a
$3$-edge-colouring of~$G(n,p)$ for which three monochromatic trees are needed to
cover all vertices --- it suffices to consider three non-adjacent vertices
$x_1$, $x_2$ and $x_3$, and colour the edges incident to~$x_i$ with colour~$i$
and colour all the remaining edges with any colour. Therefore, the bound for
$tc_3(\gnp)$ in~\cref{main_res} is the best possible as long as $p$ is not too
close to $1$.

We remark that, from the example described in~\cite{KoMoSc}, we know that for $p
\ll {\left( \frac{\log{n}}{n} \right)}^{1/4}$, we have w.h.p.\ $\tc_3(G(n,p))
\geq 4$. It would be very interesting to describe the behaviour of $\tc_3(\gnp)$
when ${\big(\frac{\log n}{n}\big)}^{1/4}\ll p \ll {\big(\frac{\log
    n}{n}\big)}^{1/6}$.

This paper is organized as follows. In~\cref{sec:preliminaries} we present some
definitions and auxiliary results that we will use in the proof of
Theorem~\ref{main_res}, which is outlined in~\cref{sec:sketch}. The details of
the proof of~\cref{main_res} are given in Section~\ref{sec:proof}.

\section{Preliminaries}\label{sec:preliminaries}
Most of our notation is standard (see~\cites{Bo98,BM08,Di10}
and~\cites{Bo01,JLR00}). However, we will mention in the following few
definitions regarding hypergraphs that will play a major role in our proofs just
for completeness.

We say that a set $A$ of vertices in a hypergraph $\mathcal{H}$ is a
\emph{vertex cover} if every hyperedge of $\mathcal{H}$ contains at least one
element of $A$. The \emph{covering number} of $\mathcal{H}$, denoted by
$\tau(\mathcal{H})$, is the smallest size of a vertex cover in $\mathcal{H}$. A
\emph{matching} in $\mathcal{H}$ is a collection of disjoint hyperedges in
$\mathcal{H}$. The \emph{matching number} of $\mathcal{H}$, denoted
by~$\nu(\mathcal{H})$, is the largest size of a matching in $\mathcal{H}$. An
immediate relationship between $\tau(\mathcal{H})$ and $\nu(\mathcal{H})$ is the
inequality~$\nu(\mathcal{H}) \leq \tau(\mathcal{H}) $. If additionally
$\mathcal{H}$ is $r$-uniform, then we have~$\tau(\mathcal{H}) \leq r
\nu(\mathcal{H})$. A conjecture due to Ryser (which first appeared in the thesis
of his Ph.D. student, Henderson~\cite{Ryser}) states that for every $r$-uniform
$r$-partite hypergraph $\mathcal{H}$, we have $\tau(\mathcal{H})\leq
(r-1)\nu(\mathcal{H})$. Note that K\"{o}nig-Egerv\'{a}ry theorem corresponds to
Ryser's conjecture for $r=2$. Aharoni~\cite{Aharoni} proved that Ryser's
conjecture holds for $r=3$, but the conjecture remains open for $r\geq 4$.

Given a vertex $v$ in a 3-uniform hypergraph $\mathcal{H}$, the \emph{link
  graph} of $\mathcal{H}$ with respect to~$v$ is the graph $L_v = (V,E)$ with
vertex set $V = V(\mathcal{H})$ and edge set $E = \{xy : \{x,y,v\} \subseteq
\mathcal{H}\}$.

We will use the following theorem due to Erd\H{o}s, Gy\'arf\'as and
Pyber~\cite{EGP91} in the proof of our main result.
\begin{theorem}[Erd\H{o}s, Gy\'arf\'as and
  Pyber]\label{lemma:EGP91} For any
  $3$-edge-colouring of a complete graph $K_n$, there exists a partition of
  $V(K_n)$ into~$2$ monochromatic trees.
\end{theorem}

We will also use the following lemma, which is a simple application of
Chernoff's inequality. For a proof of the first item see~\cite[Lemma~3.8]{KMNSS}.
The second item is an immediate corollary of~\cite[Lemma~3.10]{KMNSS}.
\begin{lemma}\label{lem:gnp}
  Let~$\eps > 0$. If~$p=p(n)\gg{\left(\frac{\log{n}}{n}\right)}^{1/6}$, then
  w.h.p.\ $G\in G(n,p)$ has the following properties.
  \begin{enumerate}[label=\rmlabel]
  \item For any disjoint sets~$X,Y\subseteq V(G)$ with~$|X|,|Y|
    \gg \frac{\log{n}}{p}$, we have
    \begin{align*}
    |E_G(X,Y)| = (1\pm \eps)p|X||Y|.
    \end{align*}
  \item Every vertex $v\in V(G)$ has degree $d_G(v)=(1\pm
    \eps)pn$ and
    every set of~$i\leq 6$ vertices has $(1\pm\eps) p^i n$ common neighbours.
  \end{enumerate}
\end{lemma}

\section{A sketch of the proof}\label{sec:sketch}

In this section we will give an overview of the proof of~\cref{main_res}.
Let $G = G(n,p)$, with $p \gg {\left( \frac{\log{n}}{n} \right)}^{1/6}$, and let
$\phi: E(G) \to \{\red,~\green,~\blue\}$ be any 3-edge-colouring of~$G$. We consider an
auxiliary graph~$F$, with~$V(F)=V(G)$ and~$ij \in E(F)$ if and only if there is,
in the colouring~$\phi$, a monochromatic path in~$G$ connecting $i$ and $j$.
Then we define a 3-edge-colouring~$\phi'$ of~$F$ with~$\phi'(ij)$ being the color of any
monochromatic path in~$G$ connecting~$i$ and~$j$. Note that any covering of~$F$
with monochromatic trees with respect to the colouring~$\phi'$ corresponds to a
covering of~$G$ with monochromatic trees with respect to the colouring~$\phi$ with
the same number of trees.

Next, we consider different cases depending on the value of~$\alpha(F)$.
If~$\alpha(F)=1$, then~$F$ is a complete $3$-edge-coloured graph and by a
theorem of Erd\H{o}s, Gy\'{a}rf\'{a}s and Pyber (see~\cref{lemma:EGP91}), there
exists a partition of~$V(F)$ into~$2$ monochromatic trees. The remaining proof
now is divided into the cases $\alpha(F) \geq 3$ and $\alpha(F) = 2$.

\medskip
\noindent \textit{Case $\alpha(F) \geq 3$.} From the condition on the independence number of $G$, there
exist three vertices $r,b,g\in V(G)$ that pairwise do not have any monochromatic
path connecting them. With high probability, they have a common neighbourhood in
$G$ of size at least $np^3/2$.
 Let~$X_{rbg}$ be the largest subset of this common
neighbourhood such that for each~$i\in\{r,b,g\}$, the edges from $i$ to $X_{rbg}$ in
$G$ are all coloured with one colour. Then, since there are no monochromatic
paths between any two of $r$, $b$, $g$, we have $|X_{rbg}| \geq np^3/12$ and moreover
we may assume that all edges between~$r$ and~$X_{rbg}$ are red, all between~$b$ and~$X_{rbg}$ are
blue and those between~$g$ and~$X_{rbg}$ are green. Now we notice that all vertices that
have a neighbour in~$X_{rbg}$ are covered by the union of the spanning trees of the
red component of~$r$, the blue component of~$b$ and the green component of~$g$.

We are done in the case where every vertex has a neighbour in $X_{rbg}$, as the vertices in $X_{rbg} \cup N_G(X_{rbg})$ are covered by the red, blue and green
component containing $r$, $b$ and $g$, respectively.
Otherwise, w.h.p.\ any vertex $y\in V \setminus \left( X_{rbg} \cup N_G(X_{rbg}) \right)$ has many common neighbours with~$r$,~$g$ and~$b$ in $G$ that are
also neighbours of some vertex in $X_{rbg}$.
 An analysis of the possible colourings of the edges between $X_{rbg}$ and the common neighbourhood of the vertices $r$, $b$, $g$ and $y$ yields the following: for some $i \in \{r,g,b\}$, let us say $i=r$, every vertex $y \in X_{rbg}$
can be connected to~$r$ by a monochromatic path in colour~$\red$ or either
to~$g$ or~$b$ by a monochromatic path in the colour~$\blue$ or~$\green$,
respectively.

This already gives us that all vertices in~$G$ can be covered by~$5$
monochromatic trees, since all the vertices in~$N_G(X_{rbg})$ lie in the $\red$ component
of~$r$, or the $\green$ component of~$g$, or in the $\blue$ component of~$b$ and every
vertex in $V\setminus N_G(X_{rbg})$ lies in the $\red$ component of~$r$, in the $\blue$ component of $g$ or in the $\green$
component of $b$. By analysing the colours of edges to the common neighbourhood
of carefully chosen vertices, we are able to show that actually three of those
five trees already cover all the vertices of $G$.

\medskip
\noindent \textit{Case $\alpha(F) =2$.} Let us consider a $3$-uniform hypergraph
$\mathcal{H}$ defined as follows (this definition is inspired by a construction
of Gy\'{a}rf\'{a}s~\cite{Gyarfas}). The vertices of $\mathcal{H}$ are the
monochromatic components of~$F$ and three vertices form a hyperedge if the
corresponding three components have a vertex in common (in particular, those
three monochromatic components must be of different colours).
Hence~$\mathcal{H}$ is an~$3$-uniform $3$-partite hypergraph.

We observe that if~$A$ is a vertex cover of~$\mathcal{H}$, then the
monochromatic components associated with the vertices in~$A$ cover all the
vertices of~$G$. This implies that $\tc_{3}(G) \leq \tau(\mathcal{H})$. Also, it
is easy to see that $\nu(\mathcal{H}) \leq \alpha(F)=2$. Now, recall that
Aharoni's result~\cite{Aharoni} (which corresponds to Ryser's conjecture for
$r=3$) states that for every $3$-uniform $3$-partite hypergraph $\mathcal{H}$ we
have $\tau(\mathcal{H}) \leq 2\nu(\mathcal{H})$. Together with the previous
observation, this implies $\tc_3(G) \leq 4$. But our goal is to prove that
$\tc_3(G) \leq 3$. To this aim, we analyze the hypergraph $\mathcal{H}$ more
carefully, reducing the situation to a few possible settings of components
covering all vertices. In each of those cases, we can again analyse the possible
colouring of edges of common neighbours of specific vertices, inferring that
indeed there are~$3$ monochromatic components cover all vertices.

\section{Proof of~\cref{main_res}}\label{sec:proof}

Instead of analysing the colouring of the graph $G=G(n,p)$, it will be helpful
to analyse the following auxiliary graph.

\begin{definition}[Shortcut graph]
  Let $G$ be a graph and $\varphi$ be a $3$-edge-colouring of $G$. The
  \emph{shortcut graph} of $G$ (with respect to $\varphi$) is the graph
  $F=F(G,\phi)$ that has $V(G)$ as the vertex set and the following edge set:
  \[\{uv : u,v \in V(G) \text{ and $u$ and $v$ are connected in $G$ by a path
      monochromatic under $\phi$}\}.\]
\end{definition}

We can consider a natural edge colouring~$\phi'$ of $F(G,\phi)$ by assigning to
an edge~$uv\in E(F(G,\phi))$ the colour of any monochromatic path connecting~$u$
and~$v$ in~$G$ under the colouring~$\phi$. We will say that~$\phi'$ is an
\emph{inherited colouring} of $F(G,\phi)$. Let~$\tc(F,\phi')$ be the minimum
number of monochromatic components (under the colouring~$\phi'$) covering all
the vertices of~$F$. Note that any covering of~$F(G,\phi)$ with monochromatic
trees under~$\phi'$ corresponds to a covering of~$G$ with monochromatic trees
under the colouring~$\phi$. In particular, if we show that for every
$3$-edge-colouring $\phi$ of $G$, we have $\tc(F,\phi')\leq 3$, for every
ineherited colouring $\phi'$, then we have shown that $\tc_3(G) \leq 3$.
Therefore,~\cref{main_res} follows from the following lemma.

\begin{lemma}\label{lemma:main}
  Let $p\gg{\left(\frac{\log n}{n}\right)}^{1/6}$ and let $G =\gnp$. The
  following holds with high probability. For any $3$-edge-colouring $\phi$ of
  $G$ and any inherited colouring $\phi'$ of the shortcut graph $F = F(G,\phi)$,
  we have $\tc(F,\phi')\leq 3$.
\end{lemma}

The proof of~\cref{lemma:main} is divided into two different cases,
depending on the independence number of $F$. Subsections~\ref{sec:alpha2}
and~\ref{sec:alpha3} are devoted, respectively, to the proof of
\cref{lemma:main} when $\alpha(F)\geq 3$ and $\alpha(F)\leq 2$.

From now on, we fix $\eps>0$ and assume that~$p\gg{\left(\frac{\log
  n}{n}\right)}^{1/6}$ and $n$ is sufficiently large. Then, by~\cref{lem:gnp},
we may assume that the following holds w.h.p.:
\begin{enumerate}
\item There is an edge between any two sets of size~$\omega\left((\log n)/p\right)$.
\item Every vertex $v\in V(G)$ has degree $d_G(v)=(1\pm \eps)pn$.
\item Every set of~$i\leq 6$ vertices has $(1\pm\eps) p^i n$ common neighbours.
\end{enumerate}

\subsection{Shortcut graphs with independence number at least three}\label{sec:alpha2}

\begin{proof}[Proof of~\cref{lemma:main} for $\alpha(F)\geq 3$]
  Since $\alpha (F) \geq 3$, there exist three vertices~$r,b,g\in V(G)$ that
  pairwise do not have any monochromatic path connecting them in~$G$. In
  particular, if $v$ is a common neighbour of $r$, $b$ and $g$ in $G$, then the
  edges $vr$, $vb$ and $vg$ have all different colours. The common neighbourhood
  of $r$, $b$ and $g$ in $G$ has size at least~$np^3/2$. Let~$X_{rbg}$ be the
  largest subset of this common neighbourhood such that for each~$i\in
  \{r,b,g\}$, the edges between $i$ and the vertices of $X_{rbg}$ are all
  coloured with the same colour in~$G$. Then~$\vert X_{rbg}\vert\geq np^3/12$.
  Without loss of generality, assume that all edges between~$r$ and the vertices
  of~$X_{rbg}$ are red, between~$b$ and the vertices of~$X_{rbg}$ are blue and
  those between~$g$ and the vertices of~$X_{rbg}$ are green.
  Let~$C_\red(r)$,~$C_\blue(b)$ and~$C_\green(g)$ be respectively the red, blue
  and green components in $G$ containing~$r$,~$g$ and~$b$.

  Notice that all vertices of~$F$ that have a neighbour in~$X_{rbg}$ are covered
  by~$C_\red(r)$,~$C_\blue(b)$ or~$C_\green(g)$. Therefore, the proof would be
  finished if every vertex had a neighbour in~$X_{rbg}$. If this is not the
  case, we fix an arbitrary vertex~$y\in V\setminus \left(X_{rbg} \cup
    N_G(X_{rbg}) \right)$. By our choice of~$p$, there are at least~$np^4/2$
  common neighbours of~$y$,~$r$,~$b$ and~$g$. Let~$X_{yrbg}$ be the largest
  subset of the common neighbourhood of~$y$,~$r$,~$b$ and~$g$ such that for
  each~$i\in\{r,b,g\}$, the edges between~$i$ and~$X_{yrbg}$ are all coloured
  the same. Then~$|X_{yrbg}|\geq np^4/12$. Note that since~$y\notin
  N_G(X_{rbg})$, the sets~$X_{yrbg}$ and~$X_{rbg}$ are disjoint. Furthermore,
  since~$|X_{yrbg}|,|X_{rbg}| \gg \frac{\log{n}}{p}$, we have
  \begin{align*}
    |E_G(X_{yrbg},X_{rbg})|\geq 1.
  \end{align*}

  We now analyse the colours between~$r$, $b$, $g$ and the set~$X_{yrbg}$.
  Again, since there is no monochromatic path connecting any two of~$r$,~$b$
  and~$g$, all~$i \in \{r,b,g\}$ have to connect to~$X_{yrbg}$ in different
  colours. Since~$X_{yrbg}$ is disjoint of~$X_{rbg}$, we cannot have~$r$,~$b$
  and~$g$ being simultaneously connected to~$X_{yrbg}$ by red, blue and green
  edges, respectively. Assume first that for each~$i \in \{r,b,g\}$, the edges
  between~$i$ and~$X_{yrbg}$ have different colours from the edges between~$i$
  and~$X_{rbg}$. Then let~$uv$ be an edge between~$X_{yrbg}$ and~$X_{rbg}$ and
  notice that whatever the colour of~$uv$ is, we will have a monochromatic path
  connecting two of the vertices in~$\{r,g,b\}$. Therefore, we can assume that
  for some~$i \in \{r,g,b\}$, we have that all the edges between~$i$
  and~$X_{rbg}$ and all the edges between~$i$ and~$X_{yrbg}$ coloured the same.
  Without loss of generality, we may say that such~$i$ is~$r$. In this case, the
  edges between~$b$ and~$X_{yrbg}$ are green and the edges between~$g$
  and~$X_{yrbg}$ are blue. Finally, all the edges between~$X_{yrbg}$ and~$X_{rbg}$ are
  red, otherwise we would be able to connect~$b$ and~$g$ by some monochromatic
  path. Figure~\ref{fig:rbgy} shows the colouring of the edges that we have
  analysed so far.

  \begin{figure}
    \centering
    \begin{tikzpicture} [scale=1, thick, auto, vertex/.style={circle, draw,
        fill=black!50, inner sep=0pt, minimum width=4pt}]

      \node [vertex, label=left:$r$](r) at (0,2) {};
      \node [vertex, label=left:$b$](b) at (0,0) {};
      \node [vertex, label=left:$g$](g) at (0,-2) {};
      \node [vertex, label=right:$y$](y) at (6,0) {};
      \node [vertex, label={[label distance=.4cm]-45:$X_{rbg}$}](j) at (4,-1) {};
      \node [vertex, label={[label distance=.2cm]+45:$X_{yrbg}$}](i) at (4,1) {};

      \draw (j) circle (0.6 cm);
      \draw (i) circle (0.4 cm);

      \draw [red!75!black] (r)--(j);
      \draw [blue!75!black] (b)--(j);
      \draw [green!75!black] (g)--(j);

      \draw (y)--(i);
      \draw [red!75!black](j)--(i);
      \draw [red!75!black] (r)--(i);
      \draw [green!75!black] (b)--(i);
      \draw [blue!75!black] (g)--(i);

    \end{tikzpicture}
    \caption{Analysis of the colouring of the edges incident on $X_{rbg}$ and on
      $X_{yrbg}$.}\label{fig:rbgy}
  \end{figure}

  Let us now consider any further vertex~$x\in V\setminus \left(X_{rbg} \cup
    N_G(X_{rbg}) \right)$ with~$x\neq y$, if such a vertex exists. We
  define~$X_{xrbg}$ analogously to~$X_{yrbg}$ and observe that the colour
  pattern from~$r$,~$b$,~$g$ to~$X_{xrbg}$ must be the same as the one
  to~$X_{yrbg}$. Indeed, if this is not the case, then a similar analysis of the
  colours of the edges between~$\{r,b,g\}$ and~$X_{xrbg}$ yields that for
  some~$i \in \{b,g\}$, we know that the edges connecting~$i$ to~$X_{xrbg}$ are
  of the same colour as the edges connecting~$i$ to~$X_{rbg}$. Without loss of
  generality, let us say that~$i$ is~$g$. Then the edges between~$b$
  and~$X_{xrbg}$ are red and the edges between~$r$ and~$X_{xrbg}$ are green,
  otherwise~$X_{xrbg}$ and~$X_{rbg}$ would not be disjoints sets.
  Figure~\ref{fig:rbgyx} shows the colouring of the edges incident to~$X_{yrbg}$
  and~$X_{xrbg}$. Since~$|X_{yrbg}|,|X_{xrbg}| \gg \frac{\log{n}}{p}$, we have
  that there is some edge~$uv$ between~$X_{yrbg}$ and~$X_{xrbg}$. But then
  however we colour~$uv$, we will get an monochromatic path connecting two
  vertices in~$\{r,b,g\}$, which is a contradiction. Thus, the colour pattern of
  edges between~$\{r,b,g\}$ and~$X_{xrbg}$ is the same as the colour pattern of
  the edges between~$\{r,b,g\}$ and~$X_{yrbg}$.

  \begin{figure}
    \centering
    \begin{tikzpicture} [scale=1, thick, auto, vertex/.style={circle, draw,
        fill=black!50, inner sep=0pt, minimum width=4pt}]

      \node [vertex, label=above:$r$](r) at (0,2) {};
      \node [vertex, label=above:$b$](b) at (0,0) {};
      \node [vertex, label=above:$g$](g) at (0,-2) {};
      \node [vertex, label=right:$y$](y) at (6,1) {};
      \node [vertex, label=right:$x$](x) at (6,-1) {};
      \node [vertex, label={[label distance=.4cm]left:$X_{rbg}$}](j) at (-2,0) {};
      \node [vertex, label={[label distance=.2cm]+45:$X_{yrbg}$}](i) at (4,1) {};
      \node [vertex, label={[label distance=.2cm]-45:$X_{xrbg}$}](k) at (4,-1) {};

      \draw (j) circle (0.6 cm);
      \draw (i) circle (0.4 cm);
      \draw (k) circle (0.4 cm);

      \draw [red!75!black] (r)--(j);
      \draw [blue!75!black] (b)--(j);
      \draw [green!75!black] (g)--(j);

      \draw (y)--(i);
      \draw [red!75!black] (r)--(i);
      \draw [green!75!black] (b)--(i);
      \draw [blue!75!black] (g)--(i);

      \draw (x)--(k);
      \draw [blue!75!black] (r)--(k);
      \draw [red!75!black] (b)--(k);
      \draw [green!75!black] (g)--(k);

      \draw (i)--(k);
    \end{tikzpicture}
    \caption{Analysis of the color of the edges incident on $X_{yrbg}$ and on
      $X_{xrbg}$.}\label{fig:rbgyx}
  \end{figure}

  Therefore, we have that each vertex in $X_{rbg} \cup N_G(X_{rbg})$ belongs to
  one of the monochromatic components $C_\red(r)$, $C_\blue(b)$ or
  $C_\green(g)$, while a vertex in $V(G)\setminus \left(X_{rbg} \cup
    N_G(X_{rbg}) \right)$ belongs to one of the monochromatic components
  $C_\red(r)$, $C_\green(b)$ or $C_\blue(g)$ where the latter two are the green
  component containing~$b$ and the blue component containing~$g$, respectively.
  This gives a covering of $G$ with five monochromatic trees. Next we will show
  that actually three of those trees already cover all the vertices.

  Suppose that at least~$4$ among the components
  $C_{\red}(r)$,~$C_{\blue}(b)$,~$C_{\green}(b)$,~$C_{\green}(g)$,
  and~$C_{\blue}(g)$ are needed to cover all vertices. Since there does not
  exist any monochromatic path between any two of~$r$, $b$, $g$, we know that
  for each~$i \in \{r,b,g\}$, any monochromatic component containing~$i$ does
  not intersect~$\{r,g,b\}\setminus\{i\}$. Hence, among those at least~$4$
  components, we have for each~$i\in\{r,b,g\}$ one component containing it and,
  without loss of generality, two containing~$b$. That is, three components of
  those at least $4$ components needed to cover all the vertices
  are~$C_{\red}(r)$,~$C_{\blue}(b)$ and~$C_{\green}(b)$. Now there are two cases
  regarding the fourth component: we need~$C_{\green}(g)$ as the fourth
  component or we need~$C_{\blue}(g)$ (those two cases might intersect).

  We begin with the first case, where we need the components $C_{\red}(r)$,
  $C_{\blue}(b)$, $C_{\green}(b)$ and $C_{\green}(g)$ to cover all the vertices
  of $G$. Let
  \[
    \tilde{b} \in C_{\blue}(b) \setminus \left( C_{\red}(r) \cup C_{\green}(b)
      \cup C_{\green}(g) \right)
  \]
  and let
  \[
    \tilde{g} \in C_{\green}(b)\setminus \left( C_{\red}(r) \cup C_{\blue}(b)
      \cup C_{green}(g) \right).
  \]
  Then let~$X_{\tilde{b}\tilde{g}rbg}$ be the maximum set of common neighbours
  of~$\tilde{b},\tilde{g},r,g,b$ such that for each~$i \in \{\tilde{b},
  \tilde{g}, r, b, g\}$, the edges from~$i$ to~$X_{\tilde{b}\tilde{g}rbg}$ are
  all coloured the same. Since~$\vert X_{\tilde{b}\tilde{g}rbg}\vert \geq
  np^5/240 \gg \frac{\log{n}}{p} $, we have
  \[
    |E_G(X_{\tilde{b}\tilde{g}rbg},X_{yrbg})| \geq 1 \qand
    |E_G(X_{\tilde{b}\tilde{g}rbg},X_{rbg})| \geq 1.
  \]
  We will analyse the possible colours of the edges between the specified
  vertices and~$X_{\tilde{b}\tilde{g}rbg}$. If for each of~${r,b,g}$, the colour
  it sends to~$X_{\tilde{b}\tilde{g}rbg}$ is different from the colour it sends
  to~$X_{rbg}$, then any edge between~$X_{\tilde{b}\tilde{g}rbg}$ and~$X_{rbg}$
  ensures a monochromatic path between two of~$r$,~$b$,~$g$ (in the colour of
  that edge). Similarly, it cannot happen that for each of~${r,b,g}$, the colour it sends
  to~$X_{\tilde{b}\tilde{g}rbg}$ is different from the colour it sends
  to~$X_{yrbg}$. Thus, since~$r$ sends red to both~$X_{rbg}$ and~$X_{yrbg}$ while the colours from~$b$ (and~$g$) to~$X_{rbg}$ and~$X_{yrbg}$ are switched, the colour of the edges between~$r$
  and~$X_{\tilde{b}\tilde{g}rbg}$ is red.

  Now note that, by the choice of~$\tilde{b}$ and~$\tilde{g}$, the edges between
  each of them and~$X_{\tilde{b}\tilde{g}rbg}$ can not be red. Further, the
  choice implies that an edge between~$\tilde{b}$
  and~$X_{\tilde{b}\tilde{g}rbg}$ can not be of the same colour (green or blue)
  as an edge between~$\tilde{g}$ and~$X_{\tilde{b}\tilde{g}rbg}$. If~$g$ would
  send blue (and hence~$b$ would send green) edges
  to~$X_{\tilde{b}\tilde{g}rbg}$, there would either be a blue path between~$b$
  and~$g$ (if the edges between~$\tilde{b}$ and~$X_{\tilde{b}\tilde{g}rbg}$ are
  blue) or~$\tilde{b}$ would lie in~$C_\green(b)$ (if the edges
  between~$\tilde{b}$ and~$X_{\tilde{b}\tilde{g}rbg}$ are green). Since both
  those situations would mean a contradiction, we may assume that each
  of~$r$,~$b$,~$g$ sends edges with that colour to~$X_{\tilde{b}\tilde{g}rbg}$
  as it does to~$X_{rbg}$. But then~$X_{\tilde{b}\tilde{g}rbg}$ is actually a
  subset of~$X_{rbg}$ and therefore~$\tilde{g}$, having an edge to~$X_{rbg}$,
  lies in one of~$C_{\red}(r)$, $C_\blue(b)$, or $C_\green(g)$, a contradiction.

  In the case where the forth component that we need is~$C_\blue(g)$, we repeat
  the construction of~$X_{\tilde{b}\tilde{g}rbg}$ similarly as before by letting
  \[
    \tilde{b} \in C_\blue(b) \setminus ( C_\red(r)\cup C_\green(b)\cup
    C_\blue(g))
  \]
  and
  \[
    \tilde{g}\in C_\green(b) \setminus ( C_\red(r)\cup C_\blue(b)\cup
    C_\blue(g)) .
  \]
  Also as before, we end up with~$X_{\tilde{b}\tilde{g}rbg}$ being part
  of~$X_{rbg}$. From the choice of~$\tilde{g}$, the edges it sends
  to~$X_{\tilde{b}\tilde{g}rbg}$ have to be green, since otherwise it would be
  in~$C_{\red}(r)$ or~$C_\blue(b)$. But that gives a green path between~$b$
  and~$g$, a contradiction.

  Summarising, we infer that three components
  among~$C_\red(r)$,~$C_\blue(b)$,~$C_\green(b)$,~$C_\green(g)$ and~$C_\blue(g)$
  cover the vertex set of~$G$.
\end{proof}

\subsection{Shortcut graphs with independence number at most two}\label{sec:alpha3}
\begin{proof}[Proof of~\cref{lemma:main} for~$\alpha(F)\leq 2$]
  We start by noticing that if~$\alpha (F)=1$, then the graph~$F$ together with
  the colouring~$\varphi'$ is a complete~$3$-coloured graph and therefore,
  by~\cref{lemma:EGP91}, there exists a partition of~$V(F)$ into~$2$
  monochromatic trees. Thus, we may assume that~$\alpha(F)=2$.

  Let $\mathcal{H}$ be the 3-uniform hypergraph with~$V(\mathcal{H})$ being the
  collection of all the monochromatic components of~$F$ under the
  colouring~$\varphi'$ and three monochromatic components form a hyperedge
  in~$\mathcal{H}$ if they share a vertex. Notice that~$\mathcal{H}$ is
  3-partite, since distinct monochromatic components of the same colour do not
  have a common vertex and therefore they can not belong to the same hyperedge.
  In other words, the colour of each component give us a 3-partition of the
  vertex set of~$\mathcal{H}$. We denote by~$V_{\red}$,$V_{\blue}$ and~$V_{\green}$ the set of vertices of~$V(\mathcal{H})$ that correspond to,
  respectively, red, blue and green components. Such construction was inspired
  by a construction due to Gy\'arf\'as~\cite{Gyarfas}.

  Note that every vertex~$v$ of~$F$ is contained in a monochromatic component
  for each one of the colours (a monochromatic component could consist
  only of $v$). Therefore, any vertex cover of~$\mathcal{H}$ corresponds to a
  covering of the vertices of~$F$ with monochromatic trees. Indeed, if~$A$ is a
  vertex cover of~$\mathcal{H}$, then consider the monochromatic components
  corresponding to each vertex in~$A$. If any vertex~$v$ of~$F$ is not covered
  by those components, then the vertices in $\mathcal{H}$ corresponding to the
  red, green and blue components in $F$ containing $v$ do not belong to $A$ and
  they form an hyperedge. But this contradicts the fact that $A$ is a vertex
  cover of $\mathcal{H}$. Therefore,
  \begin{align}\label{tctau}
    \tc(F,\phi') \leq \tau(\mathcal{H}).
  \end{align}

  Let~$L = \bigcup_{s\in V_{\red}}L_s$ be the union of the link graphs~$L_s$ of all
  vertices~$s\in V_{\red}$. Any vertex cover of this bipartite graph~$L$
  corresponds to a vertex cover of~$\mathcal{H}$ of the same size. Therefore,
  \begin{align}\label{tautau}
    \tau(\mathcal{H}) \leq \tau(L).
  \end{align}
  Furthermore, by K\"{o}nig's theorem we know that $\tau(L) = \nu(L)$. Thus, if
  $\nu(L) \leq 3$, then by~\eqref{tctau} and~\eqref{tautau}, we have
  \begin{align*}
    \tc(F,\phi') \leq \tau(\mathcal{H}) \leq \tau(L) = \nu(L) \leq 3.
  \end{align*}
  Therefore, we may assume that \(\nu(L) \geq 4\), and fix a matching~$M_L$ of
  size at least~$4$ in~$L$. Let us say that $M_L$ consists of the edges
  $G_1B_1$, $G_2B_2$, $G_3B_3$, and $G_4B_4$, where $\{G_1,G_2,G_3,G_4\}
  \subseteq V_{\green}$ and $\{B_1,B_2,B_3,B_4\} \subseteq V_{\blue}$.

  Now we give an upper bound for~$\nu(\mathcal{H})$. Note that any
  matching~$M_{\mathcal{H}}$ in~$\mathcal{H}$ gives us an independent set~$I$ in~$F$.
  Indeed, for each hyperedge~$e \in M_{\mathcal{H}}$, let~$v_e\in V(F)$ be any vertex in the
  intersection of those monochromatic components associated to the vertices
  in~$e$ and let~$I = \{v_e : e \in M_{\mathcal{H}}\}$. We claim that~$I$ is an independent
  set in~$F$. Indeed, if~$v_e$ and $v_f$ were adjacent vertices in~$I$, then~$e$
  and~$f$ intersect, as the edge connecting~$v_e$ to~$v_f$
  in~$F$ will connect the monochromatic components containing~$v_e$ and~$v_f$ of
  that colour that is given to the edge~$v_e v_f$. Therefore,
  since~$\alpha(F) = 2$, we have
  \begin{align}\label{nual}
    \nu(\mathcal{H}) \leq \alpha(F) = 2.
  \end{align}
  Now, if there are three different edges in~$M_L$ that are edges in the link
  graphs of three different vertices of~$V_{\red}$, then there would be a
  matching of size~$3$ in~$\mathcal{H}$, contradicting~\eqref{nual}. Therefore,
  we may assume that~$M_L$ is contained in the union of at most two link graphs,
  say~$L_{R_1}$ and~$L_{R_2}$, of vertices $R_1,R_2 \in V_\red$. Now we are left
  with three cases: (Case~\ref{case_1}) two edges of~$M_L$ belong to~$L_{R_1}$
  and two belong to~$L_{R_2}$; (Case~\ref{case_2}) three edges of~$M_L$ belong
  to~$L_{R_1}$ and one to~$L_{R_2}$; (Case~\ref{case_3}) the four edges of $M_L$
  belong to~$L_{R_{1}}$. Without loss of generality, we can describe each of
  those three cases as follows (see
  Figures~\ref{fig:case1},~\ref{fig:case2} and~\ref{fig:case3}):

  \begin{case}\label{case_1}
    The edges $G_1B_1$ and $G_2B_2$ belong to~$L_{R_1}$ and the edges $G_3B_3$
    and $G_4B_4$ belong to~$L_{R_2}$. That means that all the following four
    sets are non-empty:
    \begin{align*}
      J_1&:=R_1\cap G_1\cap B_1,\\
      J_2&:=R_1\cap G_2\cap B_2,\\
      J_3&:=R_2\cap G_3\cap B_3,\\
      J_4&:=R_2\cap G_4\cap B_4.
    \end{align*}
  \end{case}

  \begin{case}\label{case_2}
    The edges $G_1B_1$, $G_2B_2$ and $G_3B_3$ belong to~$L_{R_1}$ and the edge
    $G_4B_4$ belongs to~$L_{R_2}$. That means that all the following four sets
    are non-empty:
    \begin{align*}
      J_1&:=R_1\cap G_1\cap B_1,\\
      J_2&:=R_1\cap G_2\cap B_2,\\
      J_3&:=R_1\cap G_3\cap B_3,\\
      J_4&:=R_2\cap G_4\cap B_4.
    \end{align*}
  \end{case}

  \begin{case}\label{case_3}
    The edges $G_1B_1$, $G_2B_2$, $G_3B_3$ and $G_4B_4$ belong to~$L_{R_1}$.
    That means that all the following four sets are non-empty:
    \begin{align*}
      J_1&:=R_1\cap G_1\cap B_1,\\
      J_2&:=R_1\cap G_2\cap B_2,\\
      J_3&:=R_1\cap G_3\cap B_3,\\
      J_4&:=R_1\cap G_4\cap B_4.
    \end{align*}

    In this case, let~$R_2$ be any other red component different from~$R_1$ and
    let~$B$ and~$G$ be, respectively, a blue and a green component with~$R_2\cap
    B \cap G\neq \emptyset$. Suppose that $G \notin \{G_1,G_2,G_3,G_4\}$. Then
    the three of the edges $G_1,B_1$, $G_2,B_2$, $G_3,B_3$ and $G_4,B_4$ are not
    incident to $GB$ (because $B$ must be different of at least three of the
    sets $B_1$, $B_2$, $B_3$ and $B_4$) and those three edges together with $GB$
    may be analysed just as in Case~\ref{case_2}. Therefore, we may suppose that
    $G \in \{G_1,G_2,G_3,G_4\}$. Let us say, without loss of generality, that $G
    = G_4$. If $B \notin\{B_1,B_2,B_3\}$, then the edges $G_1B_1$, $G_2B_2$ and
    $G_3B_3$ belong to $L_{R_1}$, the edge $GB$ belongs to $L_{R_2}$ and this
    case may be analysed, again, just as in Case~\ref{case_2}. Therefore, we may
    assume that $B \in \{B_1,B_2,B_3\}$. Let us say, without loss of generality
    that $B = B_3$. Then let $J_5$ be the following non-empty set:
    \begin{align}\label{eq:case3-extra}
      J_5:=R_2\cap G_4\cap B_3.
    \end{align}
  \end{case}

  Let us further remark that, since~$\nu (\mathcal{H})\leq 2$, in each of the
  three cases above, we have
  \begin{align*}
    V(F) = R_1 \cup R_2 \cup G_1 \cup G_2 \cup G_3 \cup G_4 \cup B_1 \cup B_2
    \cup B_3 \cup B_4.
  \end{align*}
  Otherwise, for any uncovered vertex~$v \in V(F)$, the hyperedge given by the
  red, blue and green components containing $v$ together with the hyperedges
  $R_1B_1G_1$ and $R_2B_3G_3$ (in Cases~\ref{case_1} and~\ref{case_2}) or~$R_2B_3G_4$ (in Case~\ref{case_3}) give a matching of size~$3$ in~$\mathcal{H}$.

  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=1, thick, auto, vertex/.style={circle, draw,
        fill=black!50, inner sep=0pt, minimum width=4pt}]

      \node [label={[label distance=.8cm]left:$R_1$}](r1) at (0,0) {};
      \node [label={[label distance=.8cm]right:$R_2$}](r2) at (4,0) {};

      \node [label={[label distance=.1cm]-45:$B_1$}](b1) at (0.25,-1) {};
      \node [label={[label distance=.1cm]-135:$G_1$}](g1) at (-0.25,-1) {};
      \node [vertex, label={[label distance=.1cm]above:$j_1$}](j1) at (0,-0.85) {};

      \node [label={[label distance=.1cm]45:$B_2$}](b2) at (0.25,1) {};
      \node [label={[label distance=.1cm]135:$G_2$}](g2) at (-0.25,1) {};
      \node [vertex, label={[label distance=.1cm]below:$j_2$}](j2) at (0,0.85) {};

      \node [label={[label distance=.1cm]-135:$B_3$}](b3) at (3.75,-1) {};
      \node [label={[label distance=.1cm]-45:$G_3$}](g3) at (4.25,-1) {};
      \node [vertex, label={[label distance=.1cm]above:$j_3$}](j3) at (4,-0.85) {};

      \node [label={[label distance=.1cm]135:$B_4$}](b4) at (3.75,1) {};
      \node [label={[label distance=.1cm]45:$G_4$}](g4) at (4.25,1) {};
      \node [vertex, label={[label distance=.1cm]below:$j_4$}](j4) at (4,0.85) {};

      \draw[red!75!black, line width=1pt] (r1) circle (1 cm);
      \draw[red!75!black, line width=1pt] (r2) circle (1 cm);

      \draw[blue!75!black, line width=1pt] (b1) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g1) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b2) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g2) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b3) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g3) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b4) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g4) circle (0.4 cm);

    \end{tikzpicture}
    \caption{Case 1}\label{fig:case1}
  \end{figure}

  Let us start with Case~\ref{case_1}.

\medskip

\noindent\textit{Proof in Case~\ref{case_1}}:
  We will prove that~$R_1$ and~$R_2$ together with possibly one further
  monochromatic component cover $V(F)$. For each $i \in \{1,2,3,4\}$, let $\tilde{B}_i =
  B_i\setminus(R_1\cup R_2)$ and $\tilde{G}_i = G_i\setminus (R_1 \cup R_2)$.

  Pick vertices~$j_i\in J_i$, with~$i\in\{1,2,3,4\}$, arbitrarily. Consider a
  vertex~$o\in \tilde{B}_1$ (if such a vertex exists). Since~$\alpha (F) = 2$,
  there is an edge connecting two of~$o$,~$j_2$,~$j_3$. Because $j_2$ and $j_3$
  belong to different components of each colour, such an edge must be incident to
  $o$. So let us say that such edge is $oj_i$, for some $i\in\{2,3\}$. Since~$o
  \notin R_1 \cup R_2$, the edge $oj_i$ cannot be red. And since $o \in B_1$,
  $oj_i$ cannot be blue either, otherwise we would connect the blue
  components $B_1$ and $B_i$. Now assume that $o$ and $j_2$ are not adjacent.
  Then $oj_3$ is a green edge in $F$. By analogously analysing the edge between
  $o$, $j_2$ and $j_4$ together with the supposition that $oj_2$ is not an edge
  in $F$, we get that $oj_4$ must be a green edge in $F$. But then we have a
  green path $j_3oj_4$ connecting $j_3$ to $j_4$, a contradiction. Therefore
  $oj_2$ is an edge in $F$ and it is green. That implies that $o \in G_2$.
  Therefore $\tilde{B}_1 \subseteq G_2$. Analogously, we can conclude the
  following:
  \begin{equation}
    \begin{aligned}\label{conn_comp}
      & \tilde{B}_1 \subseteq G_2, & \tilde{G}_1 \subseteq B_2, \\
      & \tilde{B}_2 \subseteq G_1, & \tilde{G}_2 \subseteq B_1, \\
      & \tilde{B}_3 \subseteq G_4, & \tilde{G}_3 \subseteq B_4, \\
      & \tilde{B}_4 \subseteq G_3, & \tilde{G}_4 \subseteq B_3. \\
    \end{aligned}
  \end{equation}

  \begin{claim}
    We have $\tilde{B}_1 \cup \tilde{G}_1 \cup \tilde{B}_2 \cup \tilde{G}_2 =
    \emptyset$ or $\tilde{B}_3 \cup \tilde{G}_3 \cup \tilde{B}_4 \cup
    \tilde{G}_4 = \emptyset$.
  \end{claim}
  \begin{claimproof}
    Suppose for a contradiction that there exist~$o_1\in \tilde{B}_1 \cup
    \tilde{G}_1 \cup \tilde{B}_2 \cup \tilde{G}_2$ and~$o_2\in \tilde{B}_3 \cup
    \tilde{G}_3 \cup \tilde{B}_4 \cup \tilde{G}_4$. Recall that from our choice
    of $p$, there is some~$z\in N(j_1,j_2,j_3,j_4,o_1,o_2)$. Two of the edges
    $zj_i$,for $i \in \{1,2,3,4\}$, have the same colour. Since each $j_i$ belongs to
    different green and blue components, those two edges are red. Since
    $\{j_1,j_2\} \in R_1$ and $\{j_3,j_4\}\in R_2$, those two red edges are
    either $zj_1$ and $zj_2$ or $zj_3$ and $zj_4$. Let us say that $zj_1$ and
    $zj_2$ are red (the other case is similar). Then one of the edges $zj_3$ and
    $zj_4$ has to be green and the other blue. Now, since~$o_1 \notin R_1$, the
    edge $zo_1$ is either green or blue. Then one of the paths~$o_1zj_3$ or
    $o_1zj_4$ is green or blue. This implies that $o_1 \in B_3\cup G_3\cup
    B_4\cup G_4$. On the other hand,~\eqref{conn_comp} implies that $o_1 \in
    \left(B_1\cup B_2\right) \cap \left(G_1 \cup G_2\right)$. But then we
    reached a contradiction, since that would mean that $o_1$ belongs to two
    different components of the same colour.
  \end{claimproof}

  We may assume without loss of generality that~$\tilde{B}_3 \cup \tilde{G}_3
  \cup \tilde{B}_4 \cup \tilde{G}_4$ is empty. Then, recalling
  that~$\nu(\mathcal{H})\leq 2$ and in view of~\eqref{conn_comp}, the union of
  the components~$R_1$, $B_1$, $G_1$ and $R_2$ covers every vertex of $F$. If we
  show that ${B}_1\subseteq G_1 \cup R_1 \cup R_2$ or that ${G}_1\subseteq B_1
  \cup R_1 \cup R_2$, then we get three monochromatic components covering the
  vertices of $F$. Our next claim states precisely that.

  \begin{claim}
    We have $\tilde{B}_1\setminus G_1 = \emptyset$ or $\tilde{G}_1 \setminus
    B_1= \emptyset$.
  \end{claim}
  \begin{claimproof}
    Suppose that there exist two distinct vertices~$b\in \tilde{B}_1\setminus
    G_1$ and~$g\in \tilde{G}_1\setminus B_1$. Let~$z\in N(j_1,j_2,j_3,j_4,b,g)$.
    As before, either~$zj_1$ and~$zj_2$ or~$zj_3$ and~$zj_4$ are red edges. First assume that $zj_1$ and $zj_2$ are red. Then one of the edges $zj_3$ and
    $zj_4$ has to be green and the other blue. Now, since $b \notin R_1$, the
    edge $zb$ is either green or blue. Then one of the paths $bzj_3$ or $bzj_4$
    is green or blue. This implies that $b \in B_3\cup G_3\cup B_4\cup G_4$. On
    the other hand,~\eqref{conn_comp} implies that $b \in B_1 \cap G_2$. Then we
    reached a contradiction, since that would mean that $b$ belongs to two
    different components of the same colour.

    Therefore, the edges $zj_3$ and $zj_4$ are red and one of the edges $zj_1$
    and $zj_2$ is green and the other is blue. First let us say that $zj_1$ is
    green and $zj_2$ is blue. Since $b\notin (R_1\cup R_2)$, the edge $zb$
    cannot be red. Also the edge $zb$ cannot be blue otherwise the path $bzj_2$
    would connect the components $B_1$ and $B_2$. Finally, $zb$ cannot be green,
    otherwise the path~$bzj_1$ would gives us that $b\in G_1$. Therefore $zj_1$
    is blue and $zj_2$ is green. But this case analogously leads to a
    contradiction (with~$g$ and~$G_i$ instead of~$b$ and~$B_i$ and green and
    blue switched).
  \end{claimproof}

  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=1, thick, auto, vertex/.style={circle, draw,
        fill=black!50, inner sep=0pt, minimum width=4pt}]

      \node [label={[label distance=.8cm]left:$R_1$}](r1) at (0,0) {};
      \node [label={[label distance=.8cm]right:$R_2$}](r2) at (4,0) {};

      \node [label={[label distance=.1cm]-45:$B_1$}](b1) at (0.25,-1) {};
      \node [label={[label distance=.1cm]-135:$G_1$}](g1) at (-0.25,-1) {};
      \node [vertex, label={[label distance=.1cm]above:$j_1$}](j1) at (0,-0.85) {};

      \node [label={[label distance=.1cm]45:$B_2$}](b2) at (0.25,1) {};
      \node [label={[label distance=.1cm]135:$G_2$}](g2) at (-0.25,1) {};
      \node [vertex, label={[label distance=.1cm]below:$j_2$}](j2) at (0,0.85) {};

      \node [label={[label distance=.1cm]15:$B_3$}](b3) at (1,0.25) {};
      \node [label={[label distance=.1cm]-15:$G_3$}](g3) at (1,-0.25) {};
      \node [vertex, label={[label distance=.1cm]left:$j_3$}](j3) at (0.9,0) {};

      \node [label={[label distance=.1cm]135:$B_4$}](b4) at (3.75,1) {};
      \node [label={[label distance=.1cm]45:$G_4$}](g4) at (4.25,1) {};
      \node [vertex, label={[label distance=.1cm]below:$j_4$}](j4) at (4,0.85) {};

      \draw[red!75!black, line width=1pt] (r1) circle (1 cm);
      \draw[red!75!black, line width=1pt] (r2) circle (1 cm);

      \draw[blue!75!black, line width=1pt] (b1) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g1) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b2) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g2) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b3) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g3) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b4) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g4) circle (0.4 cm);

    \end{tikzpicture}
    \caption{Case 2}\label{fig:case2}
  \end{figure}

We proceed to the proof of Case~\ref{case_2}.

\medskip

\noindent\textit{Proof in Case~\ref{case_2}}:
  As in Case~\ref{case_1}, pick vertices~$j_i\in J_i$, with~$i\in\{1,2,3,4\}$
  arbitrarily. We claim that~$V(F)\subseteq R_1 \cup R_2 \cup B_4 \cup G_4$.
  Indeed, let~$o\in V(F)\setminus (R_1\cup R_2)$. Notice that
  since~$\alpha(F)=2$, there is an edge in each of the following sets of three
  vertices:~$\{o, j_4, j_1\}$,~$\{o, j_4, j_2\}$, and~$\{o, j_4, j_3\}$. We
  claim that~$oj_4$ is an edge of $F$. Indeed, if this was not the case, then
  since there cannot be an edge between~$j_4$ and~$j_i$ for~$i=1,2,3$, we would
  have the edges~$oj_1$,~$oj_2$ and~$oj_3$ and all of them would be coloured
  green or blue. Thus, two of them would be coloured the same, connecting two
  distinct components of one colour in this colour, a contradiction. So~$oj_4\in
  E(F)$ and since~$oj_4$ cannot be red, we conclude that~$o\in (B_4\cup G_4)$.
  Therefore,~$R_1$,~$R_2$,~$B_4$ and~$G_4$ cover all vertices of~$F$.

  If $B_4\setminus (R_1\cup R_2\cup G_4)=\emptyset$ or $G_4\setminus (R_1\cup
  R_2\cup B_4)=\emptyset$, then we get three monochromatic components covering
  $V(F)$. So let us assume that there exist~$b\in B_4\setminus (R_1\cup R_2\cup
  G_4)$ and~$g\in G_4\setminus (R_1\cup R_2\cup B_4)$. If $b$ and~$g$ are not
  adjacent, then since each of the sets~$\{b, g, j_i\}$, for~$i=1,2,3$, has to
  induce at least one edge, there are two edges between $b$
  and~$\{j_1,j_2,j_3\}$ or two edges between $g$ and~$\{j_1,j_2,j_3\}$. However,
  from the choice of $b$, we know that all the edges between $b$
  and~$\{j_1,j_2,j_3\}$ are green, and therefore two of such edges would give us
  a green connection between two different green components, a contradiction.
  Similarly, from the choice of $g$, we know that all the edges between $b$ and
  $\{j_1,j_2,j_3\}$ are blue, and two of such edges would give us a blue
  connection between two different blue components, again a contradiction.

  Hence, we conclude that $bg\in F$ for any $b\in B_4\setminus (R_1\cup R_2\cup
  G_4)$ and any~$g\in G_4\setminus (R_1\cup R_2\cup B_4)$ and any such edge $bg$
  is red. Therefore, there is a red component~$R_3$ covering~$(B_4\triangle
  G_4)\setminus (R_1\cup R_2)$, where~$B_4\triangle G_4$ denotes the symmetric
  difference. If~$(B_4\cap G_4) \setminus (R_1\cup R_2) =\emptyset$,
  then~$R_1$,~$R_2$ and~$R_3$ cover~$V(F)$ and we are done. Therefore, suppose
  there is a vertex~$x\in (B_4\cap G_4) \setminus (R_1\cup R_2)$.
  If~$R_2\setminus (B_4\cup G_4)=\emptyset$, then~$R_1$,~$B_4$,~$G_4$
  cover~$V(F)$ and we are done. Therefore, suppose there is a vertex $y\in
  R_2\setminus (B_4\cup G_4)$. Note that~$xy\notin E(F)$, since $x$ and $y$
  belong to different components in each of the colours. Also, $xj_i\notin
  E(F)$, for~$i\in\{1,2,3\}$, since otherwise two different components of the
  same colour would be connected in that colour by the edge $xj_i$. Now~$\alpha
  (F)=2$ implies that~$yj_i\in E(F)$, for~$i\in\{1,2,3\}$ (otherwise,
  $\{x,y,j_i\}$ would be an independent set). But these edges must all be green
  or blue, hence two of them are of the same colour, connecting two different
  components of one colour in that colour, a contradiction.

  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=1, thick, auto, vertex/.style={circle, draw,
        fill=black!50, inner sep=0pt, minimum width=4pt}]

      \node [label={[label distance=.8cm]left:$R_1$}](r1) at (0,0) {};
      \node [label={[label distance=.8cm]right:$R_2$}](r2) at (4,0) {};

      \node [label={[label distance=.2cm]below:$B_1$}](b1) at (-0.25,-0.9) {};
      \node [label={[label distance=.1cm]-135:$G_1$}](g1) at (-0.75,-0.7) {};
      \node [vertex, label={[label distance=.1cm]above:$j_1$}](j1) at (-0.5,-0.75) {};

      \node [label={[label distance=.2cm]above:$B_2$}](b2) at (-0.25,0.9) {};
      \node [label={[label distance=.1cm]135:$G_2$}](g2) at (-0.75,0.7) {};
      \node [vertex, label={[label distance=.1cm]below:$j_2$}](j2) at (-0.5,0.75) {};

      \node [label={[label distance=.1cm]below:$B_3$}](b3) at (2,-0.25) {};
      \node [label={[label distance=.1cm]below:$G_3$}](g3) at (0.75,-0.7) {};
      \node [vertex, label={[label distance=.1cm]left:$j_3$}](j3) at (0.7,-0.5) {};

      \node [label={[label distance=.1cm]above:$B_4$}](b4) at (0.75,0.7) {};
      \node [label={[label distance=.1cm]above:$G_4$}](g4) at (2,0.25) {};
      \node [vertex, label={[label distance=.1cm]left:$j_4$}](j4) at (0.7,0.5) {};

      \node [vertex, label={[label distance=.2cm]right:$j_5$}](j5) at (3.2,0) {};

      \draw[red!75!black, line width=1pt] (r1) circle (1 cm);
      \draw[red!75!black, line width=1pt] (r2) circle (1 cm);

      \draw[blue!75!black, line width=1pt] (b1) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g1) circle (0.4 cm);

      \draw[blue!75!black, line width=1pt] (b2) circle (0.4 cm);
      \draw[green!75!black, line width=1pt] (g2) circle (0.4 cm);

      \draw[rotate around={-80:(b3)},blue!75!black, line width=1pt] (b3) ellipse (8pt and 1.6cm);
      \draw[green!75!black, line width=1pt] (g3) circle (0.4 cm);

      \draw[rotate around={80:(g4)},green!75!black, line width=1pt] (g4) ellipse (8pt and 1.6cm);
      \draw[blue!75!black, line width=1pt] (b4) circle (0.4 cm);

    \end{tikzpicture}
    \caption{Case 3}\label{fig:case3}
  \end{figure}

We arrived at the last case, Case~\ref{case_3}.

\medskip

\noindent\textit{Proof in Case~\ref{case_3}}:
  Similarly to the previous cases, let us pick vertices~$j_i\in J_i$,
  with~$i\in\{1,2,3,4,5\}$ arbitrarily. We will show first that we can cover all vertices
  of~$F$ with~$4$ monochromatic components. Let~$o_1,o_2 \in V(F)\setminus
  (R_1\cup B_3\cup G_4)$ and let~$z\in N(j_1,j_2,j_3,o_1,o_2,j_5)$. At least one
  of the edges~$zj_1$,~$zj_2$ and~$zj_3$ is red, as otherwise we would connect
  two distinct components of one colour in that colour. Therefore~$z \in R_1$. Since~$o_1,o_2,j_5 \notin R_1$, the edges~$zo_1$,~$zo_2$ and~$zj_5$ cannot be red.
  Furthermore,~$o_1z$ and~$o_2z$ are coloured with a colour different from the
  colour of the edge~$j_5z$, as otherwise they would belong to~$B_3$ or~$G_4$.
  Thus,~$o_1$ and~$o_2$ are connected by a monochromatic path in green or blue.
  Hence, we showed that any two vertices of~$V(F)\setminus (R_1\cup B_3\cup
  G_4)$ are connected by a monochromatic path in green or blue. We infer
  that there is a green or blue component covering~$V(F)\setminus (R_1\cup
  B_3\cup G_4)$. Therefore,~$R_1$,~$B_3$,~$G_4$ and one further blue or green
  component~$C$ cover all vertices of~$G$. Let us assume that~$C$ is a green
  component; the case where~$C$ is a blue component is analogous.

  We claim that~$R_1 \cup B_3 \cup C$, or~$R_1 \cup G_4 \cup C$, or~$R_1 \cup
  B_3 \cup G_4$ covers~$V(F)$. Indeed, suppose for the sake of contradiction that
  there exist vertices~$g\in G_4\setminus (R_1\cup B_3\cup C)$,~$b\in
  B_3\setminus (R_1\cup G_4\cup C)$ and~$c\in C\setminus (R_1\cup B_3\cup G_4)$.
  Let~$z\in N(j_1,j_2,j_3,g,b,c)$ and note that one of~$zj_1$,~$zj_2$ and~$zj_3$
  is red. Consequently~$gz$,~$cz$ and~$bz$ are not red. Notice, however, that~$gz$ and~$bz$ can not be both green and neither both blue. Now let us say~$cz$
  is green. Since~$c \notin G_4$ and~$g \in G_4$, we would have~$gz$ blue in
  this case. But then~$bz$ must be green and since~$c\in C$ and~$C$ is a green
  component, we have~$b \in C$, which is a contradiction. Therefore~$cz$
  must be blue. Then, since~$c \notin B_3$ and~$b \in B_3$, the edge~$bz$ should
  be green. Thus the edge~$gz$ is blue. Since this argument holds for any~$g\in
  G_4\setminus (R_1\cup B_3\cup C)$ and~$c\in C\setminus (R_1\cup B_3\cup G_4)$,
  we conclude that~$V(F)\setminus (R_1\cup B_3)$ can be covered by one blue
  tree. Hence,~$G$ can be covered by the three monochromatic trees.
This finishes the last case and thereby the proof of~\cref{lemma:main}.
\end{proof}

\bibliography{bib}
\end{document}

config: arxiv


TITLE: Rapid question about Electromagnetic Tensor
QUESTION [1 upvotes]: How can I express the Electromagnetic tensor in terms of multilinear map action?
I know that if $F$ is the Electromagnetic Tensor then we can write F as:
$$ \textbf{F} = F_{\alpha \beta} \textbf{e}^{\alpha}\otimes\textbf{e}^{\beta} $$
But I want to know that notion here:
$$ [\textbf{F}](?,?) = [F_{\alpha \beta} \textbf{e}^{\alpha}\otimes\textbf{e}^{\beta}](?,?) $$
Ok. If we have $[F_{\alpha \beta} \textbf{e}^{\alpha}\otimes\textbf{e}^{\beta}](\textbf{E},\textbf{B})$, then:
$$[F_{\alpha \beta} \textbf{e}^{\alpha}\otimes\textbf{e}^{\beta}](\textbf{E},\textbf{B}) = [F_{\alpha \beta} \textbf{e}^{\alpha}\otimes\textbf{e}^{\beta}](E^{i}\textbf{e}_{i},B^{j}\textbf{e}_{j}) = F_{\alpha \beta}E^{i}B^{j} [\textbf{e}^{\alpha}\otimes\textbf{e}^{\beta}](\textbf{e}_{i},\textbf{e}_{j}) = F_{\alpha \beta}E^{i}B^{j}\textbf{e}^{\alpha}(\textbf{e}_{i})\textbf{e}^{\beta}(\textbf{e}_{j}) = F_{\alpha \beta}E^{i}B^{j}\delta^{\alpha} _{i}\delta^{\beta}_ {j} = F_{\alpha \beta}E^{\alpha}B^{\beta}$$

REPLY [1 votes]: Yes, the electromagnetic tensor $F$ is a functional which is bilinear and antisymmetrical in its arguments.  Moreover this functional is defined pointwise on a manifold (can be $\mathbb{R}^3$ or  $\mathbb{R}^4$) and is also shortly called 2-form. The arguments are actually tangent vectors (more see below) of the tangent space of the considered point (The tangent space changes at each point). If it did not depend on the point of the considered manifold, it would only be a bilinear form, a rather simple notion of linear algebra.
Typically one would evaluate (apply the EM tensor) F on tangent vectors of a surface, and eventually add up the results along all points of the surface, in that case one gets a well-known integral $\int \bf{B} dA$  (the magnetic flux)  or  for instance if added up along a line in  $\mathbb{R}^3$: $\int \bf{E} d\bf{r}\cdot d t $,  i.e. the abstract notion of pointwise defined bilinear form (shortly 2-form) gets a rather intuitive sense.
To make it even more clear in the notation you used one would consider $e^{\alpha}$ and  $e^{\beta}$ as co-vectors as elements of the cotangential spaces dual to the corresponding tangential spaces (for each point of the manifold there is another one).  The co-vector property is expressed in the relations $e^\alpha(e_\gamma)=\delta^\alpha_\gamma$, where $\delta^i_j$ is the Kronecker symbol.
In the formalism of differential forms one would write these co-vectors as: $e^\alpha = du^\alpha$ ($\alpha =0,1,2,3$ in Minkowski space)  with $u=(t,x,y,z)$  for instance (other defintions are possible).  Then the whole EM tensor $F$ would be writtten in 4-dim. space at a point $u=(t,x,y,z)$):
$F(u) =  E_x(u) dt \wedge dx + E_y(u) dt \wedge dy + E_z(u) dt \wedge dz  + B_x(u) dy \wedge dz + B_y(u) dz \wedge dx + B_z(u) dx \wedge dy$
In this formula the antisymmetric $\wedge$ product was used with is defined like  $u \wedge v = \frac{1}{2} (u\otimes v - v\otimes u)$ (I would not consider the product defined by $\otimes$ as symmetrical, just as without any symmetry).
If this expression gets applied on a flat surface (for simplicity) in the x-y plane one would use $(e_x, e_y)  = (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})$  are the tangent vectors of the x-y plane.
Actually on manifolds tangential vectors are defined as directional derivatives. A directional derivative along the x-vector is just the partial derivative in x-direction, shortly  $\frac{\partial}{\partial x}$. The more general case should be intuitively rather clear.
Then the flux given by $F$ through a little surface element $dx dy$  is $F$ applied on the tangential vectors of this surface element:
$F (u)(e_x, e_y)   = F(u)(\frac{\partial}{\partial x}, \frac{\partial}{\partial y}) = E_x(u) dt \wedge dx (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})   + E_y(u) dt \wedge dy (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})+ E_z(u) dt \wedge dz (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})
                            + B_x(u)dy \wedge dz  (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})  + B_y(u) dz \wedge dx (\frac{\partial}{\partial x}, \frac{\partial}{\partial y})  + B_z(u) dx \wedge dy(\frac{\partial}{\partial x}, \frac{\partial}{\partial y})$
Using the properties of vector with respect to co-vectors:   $ dx (\frac{\partial}{\partial x})=1$ but $dt (\frac{\partial}{\partial x})=0$  and $dy (\frac{\partial}{\partial x})=0$  and $dz (\frac{\partial}{\partial x})=0$  and $dt (\frac{\partial}{\partial y})=0$ and  $dx (\frac{\partial}{\partial y})=0$  and $dy (\frac{\partial}{\partial y})=1$  and $dz (\frac{\partial}{\partial y})=0$
one would finally get:   $F_u (e_x, e_y)   = B_z(u=(t,x,y,z))$.
Keep in mind that the components of $F$ already represent components of $\bf{E}$ and $\bf{B}$, the evaluation is carried out on tangential vectors of a surface, or  on tangential vectors of a line, but not on $\bf{E}$ and $\bf{B}$, i.e. $\bf{E}$ and $\bf{B}$ cannot be used (it would not make sense)  as arguments in the 2-form $F$ as apparently suggested.
Actually, if the concepts around differential forms  appear too abstract, you can still imagine the  tangential vectors of each point of the surface as little arrows and imagine $e^{\alpha}$ and $e^{\beta}$ as vectors of the dual space, but sooner or later it is useful to also embrace the analytical aspect of $F$ as a differential form which serves above all to be integrated over. To keep it simple I will not add the formula how to integrate differential forms, but it can be found easily on wikipedia.


TITLE: The group is not simple
QUESTION [0 upvotes]: I want to show that if $|G|=pqr$ where $p,g,r$ are primes, then $G$ is not simple.
We have that a group is simple if it doesn't have any non-trivial normal subgroups, right?
$$$$
I have done the following:
There are $p$-Sylow, $q$-Sylow and $r$-Sylow in $G$.
$$P\in \text{Syl}_p(G), \ |P|=p, \\ Q\in \text{Syl}_q(G), \ |Q|=q, \\ R\in \text{Syl}_r(G), \ |R|=r$$
$|\text{Syl}_p(G)|=1+kp \mid |G|=pqr$ so $1+kp\mid pqr \Rightarrow 1+kp\mid qr$.
So, $$1+kp=\left\{\begin{matrix}
1 \\
q \\
r \\
qr
\end{matrix}\right.$$
Similarily, $|\text{Syl}_q(G)|=1+kq \mid |G|=pqr$ so $1+kq\mid pqr \Rightarrow 1+kq\mid pr$.
So, $$1+kq=\left\{\begin{matrix}
1 \\
p \\
r \\
pr
\end{matrix}\right.$$
And, $|\text{Syl}_r(G)|=1+kr \mid |G|=pqr$ so $1+kr\mid pqr \Rightarrow 1+kr\mid pq$.
So, $$1+kr=\left\{\begin{matrix}
1 \\
p \\
q \\
pq
\end{matrix}\right.$$
Is this correct?
Suppose that $|\text{Syl}_p(G)|=1$ or $|\text{Syl}_q(G)|=1$ or $|\text{Syl}_r(G)|=1$. That means that there is one Sylow subgroup that has order $p$, $q$, $r$, respectively, right? Is this Sylow subgroup normal?
Suppose that $|\text{Syl}_p(G)|=q$. That means that the number of $p$-Sylow subgroups is $q$, each of which has order $p$, right? How can we check if these subgroups are normal?

REPLY [2 votes]: Assuming the three primes are different (otherwise you can try to show separatedly), say $\;p<q<r\;$ . Assume $\;1<n_r\;$ , then $\;n_r=pq\;$ , otherwise $\;n_r=p\;$ or $\;n_r=q\;$, which cannot be as also $\;n_r=1\pmod r\;$ and $\;r>q>p\;$ .
Thus, we already have $\;pq(r-1)=pqr-pq\;$ elements of order $\;r\;$ in the group. If we assume that also $\;n_q>1\;$ , then since there are $\;n_q>q>p\;$ Sylow $\;q-$ subgroups, we have at least $\;p(q-1)=pq-p\;$ elements of order $\;q\;$ .
Toghether, we have at least $\;pqr-pq+pq-p=pqr-p\;$ elements of order $\;r\;$ or $\;q\;$ , leaving only $\;p\;$ elements which must be a unique Sylow $\;p$ - subgroup which is then normal.


TITLE: How does one find if the following series converges: $\sum_{n=1}^{\infty} \left(1-\cos\dfrac{\pi}{n}\right)$
QUESTION [1 upvotes]: $$\sum_{n=1}^{\infty} \left(1-\cos\frac{π}{n}\right)$$
Its limit is $0$ so the necessary condition is verified. Now I don't know how to check whether it converges or not

REPLY [6 votes]: $$0\le1-\cos\frac{\pi}{n}=2\sin^2\frac{\pi}{2n}\le2\left(\frac{\pi}{2n}\right)^2=\frac{\left(\frac{\pi^2}{2}\right)}{n^2}$$
Note that $\sum_n\frac{1}{n^2}$ converges, and you have that your sum also does.


TITLE: Calculation of a an integral
QUESTION [0 upvotes]: Good Evening. I am having a problem with a step in the calculation of the following integral:
$$\int_{0}^x \frac{dt}{\sin^2 t +\cos t}
=\int_{0}^x \frac{dt}{-\cos^2 t +\cos t+1}
=-\int_{0}^x \frac{dt}{\cos^2 t -\cos t-1} $$
Let $X=\cos t$
$$X^2-X-1=0 \Leftrightarrow X=\frac{1-\sqrt{5}}{2} \mbox{and } X=\frac{1+\sqrt{5}}{2}$$
$$\frac{1}{X^2-X-1}=\frac{\frac{\sqrt{5}}{5}}{X-(\frac{1+\sqrt{5}}{2})}-\frac{\frac{\sqrt{5}}{5}}{X-(\frac{1-\sqrt{5}}{2})}$$
Therefore: $$-\int_{0}^x \frac{dt}{\cos^2 t -\cos t-1}= -\int_{0}^x \frac{\frac{\sqrt{5}}{5}}{\cos t-(\frac{1+\sqrt{5}}{2})}dt + \int_{0}^x \frac{\frac{\sqrt{5}}{5}}{\cos t-(\frac{1-\sqrt{5}}{2})}dt$$
I am having trouble calculating the two last integrals. Please help
Thank you in advance.

REPLY [2 votes]: The $\tan(t/2)$ method is one way to go (though a bit cumbersome). Let $y = \tan(t/2)$. We get that $$dy = \sec^2(t/2) \dfrac{dt}2 \implies dt = \dfrac{2 dy}{1+y^2}$$
Also, recall that $$\sin(t) = \dfrac{2y}{1+y^2} \,\,\,\text{ and }\,\,\, \cos(t) = \dfrac{1-y^2}{1+y^2}$$
Then we get that
$$I = \int \dfrac{dt}{\sin^2(t) + \cos(t)} = \int \dfrac{2dy}{\dfrac{4y^2}{1+y^2} + 1-y^2} = \int \dfrac{2(1+y^2) dy}{1+4y^2 - y^4}$$
I leave the rest to you since you should be able to finish it by splitting into appropriate partial fractions.


TITLE: Find all the cyclic subgroups of $\mathbb{Z}_{p^r} \times \mathbb{Z}_{p^r}$ of order $p^r$
QUESTION [1 upvotes]: I need to prove that $\mathbb{Z}_{p^r} \times \mathbb{Z}_{p^r}$ has $p^{r-1}(p+1)$ cyclic subgroups of order $p^r$.
My attempt is to find all elements $(a,b) \in \mathbb{Z}_{p^r} \times \mathbb{Z}_{p^r}$ of order $p^r$ and then divide them by $\phi(p^r)$. I know that in $\mathbb{Z}_{p^2}$ there are $p^2-p$ elements of order $p^2$. How can I count the number of elements in $\mathbb{Z}_{p^r}$ such that $p^r(a,b)=(0,0)$?
Can anyone help me?

REPLY [2 votes]: You are on the right track.  An element $(a,b) \in \mathbb{Z}_{p^r} \times \mathbb{Z}_{p^r}$ is of order $p^r$ if and only if at least one of $a,b$ is of order $p^r$ in $\mathbb{Z}_{p^r}$.  Since there are $\phi(p^r)$ such elements in $\mathbb{Z}_{p^r}$, by inclusion and exclusion, we get $$2\phi(p^r)p^r-\left(\phi(p^r)\right)^2$$ such $(a,b)$.
Now dividing by $\phi(p^r)$ as you suggest, will give the answer.
EDIT
When we count the elements, the expression $$2\phi(p^r)p^r$$ counts the elements where both $a$ and $b$ are of order $\phi(p^r)$ twice, so we have to subtract them.$$|A\cup B|=|A|+|B|-|A\cap B|$$


TITLE: Finding values of a and b such that the given function is continuous at $ x = \frac{\pi}{4} $ and $ x = \frac{\pi}{2}$ .
QUESTION [0 upvotes]: Find the values of a and b such that the given function is continuous at $ x = \frac{\pi}{4}$ and $x = \frac{\pi}{2}$.
  $$f(x)= \left\{\begin{matrix}
x + a\sqrt{2} \sin x \ ;& 0\le x < \frac{\pi}{4} \\
2x\cot x + b \ ; & \frac{\pi}{4} \le x \le \frac{\pi}{2} \\
a\cos 2x - b\sin x \ ; &  \frac{\pi}{2} < x \le \pi
\end{matrix}\right. $$

This is what I've tried yet :
Finding LHL : $\lim_{x\to {(\pi/4)}^{-}} f(x)$ = $x + a  $
FINDING RHL : $\lim_{x \to {(\pi/4)}^{+}} f(x)$ = ?
There will be two functions possible for $x\to (\pi/4)^+$ : $2x\cot x + b$ and $a\cos 2x - b \sin x$. How should I compute RHL here? I just need a hint. Thanks!

REPLY [1 votes]: Hint: when $x\to (\pi/4)+$, it is only a little bit bigger than $\pi/4$, i.e. much smaller than $\pi/2$.


TITLE: Can you work out a point from the length of two lines and the position they start at?
QUESTION [0 upvotes]: I know two points in the plane, $(0,0)$ and $(20,0)$. I also know that a point between and above them(the apex of a triangle formed from these three points) is $15$ from $(0,0)$ and $25$ from $(20,0)$. But I can’t work out what this third point’s position is, though I’m sure it is possible to work it out. Can anyone help, and I’m a secondary student, so can the explanations not be too advanced?

REPLY [0 votes]: As others have pointed out, the third vertex lies on the intersection of a pair of circles with radii equal to the distances from the two given points. However, you can save yourself a lot of work by recognizing that this is a 3-4-5 right triangle. Since the distance between the two given point is $20=5\cdot 4$ and the third vertex is at a distance of $15=5\cdot 3$ from the origin, the right angle must be at the origin, so the third vertex is at $(0,15)$.


TITLE: If $Z\subseteq Y\subseteq X$ and $Z$ is compact in $Y$, then $Z$ is compact in $X$
QUESTION [1 upvotes]: Let be X a topological space and let be $Z,Y\subseteq X$ such that $Z\subseteq Y$: so if Z is compact in Y then Z is compact in X.
To prove the assertion let be U an open cover of Z in X and we consider the open cover $\mathcal{U}'=\{U\cap Y:U\in\mathcal{U}\}$ of $Z$ in $Y$ -indeed $Z\subseteq\bigcup\mathcal{U}=\bigcup_{U\in\mathcal{U}}U\rightarrow Z=Z\cap Y\subseteq(\bigcup_{U\in\mathcal{U}}U)\cap Y=\bigcup_{U\in\mathcal{U}}(U\cap Y)=\bigcup\mathcal{U}'$- thus there exist $\mathcal{U}''\subseteq\mathcal{U}'$ such that $|\mathcal{U}''|<ℵ_0$ and $Z\subseteq\bigcup\mathcal{U}''$ and so $\mathcal{U'''}=\{U\in\mathcal{U}:U\cap Y\in\mathcal{U}''\}$ is an open and finite cover of Z in X -indeed $|\mathcal{U}'''|=|\mathcal{U}''|<\aleph_0$ and $Z\subseteq\bigcup\mathcal{U}''\subseteq\bigcup\mathcal{U}'''$- and so this prove that $Z$ is compact in $X$.
It is my proof correct? if not, how prove the assertion? could be that if is false?
Could someone help me, please?

REPLY [2 votes]: Your idea is good, but the symbology used is too heavy and confusing.
If $\mathcal{U}$ is an open cover of $Z$ by open subsets of $X$, then
$$
\mathcal{U}'=\{U\cap Y:U\in\mathcal{U}\}
$$
is an open cover of $Z$ by open subsets of $Y$.
By assumption, there exist $U_1,U_2,\dots,U_n\in\mathcal{U}$ such that
$$
Z\subseteq(U_1\cap Y)\cup(U_2\cap Y)\cup\dots\cup(U_n\cap Y)
$$
and this clearly implies
$$
Z\subseteq U_1\cup U_2\cup\dots\cup U_n
$$


TITLE: Gramian matrix test
QUESTION [1 upvotes]: Are there some test to know if a matrix $M$ is gramian ? $M$ is gramian if it exists a matrix W such $M=W^HW$. Also if it is possible to determine $W$.
Thanks

REPLY [1 votes]: Gramian matrix is positive-definite. So it's possible to find square root. It will be symmetrical so this it is possible to write such decomposition for any positive definite matrix. The solution of $M=WW^{T}$ it is not unique, because starting from nonsymmetric matrix $A$ one can construct matrix $B=AA^T$ and then a symmetric solution of $B=WW^T$.


TITLE: How to solve $z^4 = -16$?
QUESTION [0 upvotes]: In Fraleigh's A First Course in Abstract Algebra he solves the problem
$z^4=-16$
by rewriting in polar form that gives
$z^4=|z|^4(\cos(4\theta)+i\sin(4\theta))$
$|z|^4(\cos(4\theta)+i\sin(4\theta))=-16+0i = 16(-1+0i)$
He then says that we can immediately conclude that $|z|^4=16$. He does not go through the process of taking the absolute value of $z$. Assuming that it is $16$ just because it is in the right form seems strange to me. If you can conclude this based on form then why couldn't you factor out some other number like $-16$?

REPLY [1 votes]: Well $|z^4|=|z|^4=|-16|=16$ is pretty obvious because when you take the modulus you are dealing with non-negative real numbers.
Then $\cos^2 4\theta +\sin ^2 4\theta =1$ which is a feature of the polar form and is replicated in the form $|e^{i\phi}|=1$ for any real $\phi$ - we take $\phi = 4\theta$ here for convenience because we know we will be taking a fourth root.
Essentially, then,  this is putting $z=|z|e^{i\theta}$ so that $z^4=|z|^4 e^{i4\theta}$, and this is a standard technique for such questions. Some care needs to be taken, however you do this, to identify all four of the fourth roots.


TITLE: Prove that $2^x = 3 \cdot 9^m+5$ has no positive integer solutions for $m \geq 2$
QUESTION [5 upvotes]: Prove that $2^x = 3 \cdot 9^m+5$ has no positive integer solutions for $m \geq 2$.

I noticed that $x \equiv 5 \bmod 6$ and thus $2^x \equiv 4 \bmod 7$, but that doesn't seem to help me since $3 \cdot 9^4 +5 \equiv 4 \bmod 7$. Pretty much any other mod I use doesn't seem to work so I think proof by contradiction or something may work better.

REPLY [4 votes]: Any solutions must be fairly small - either $m \le 11$ or $x \le 20$.  I assume you have checked all those cases and found no solutions but the two you're already aware of; indeed, there aren't any.
Let's prove this - though with a warning: there's lots of computation and black magic ahead.
EDIT: It turns out we can substantially reduce the amount of computation.  See edit at the bottom.

Suppose $m \ge 12$, and work modulo $3^{12}$.  Since $2$ is a primitive root modulo $3^{12}$, we have a congruence restriction on $x$ modulo $\phi(3^{12}) = 2\cdot3^{11} = 354294.$  In particular, we must have $$x \equiv 199283\pmod{354294}.$$
Now suppose $x \ge 21$, and work modulo $2^{21}$.  $3$ is not quite a primitive root modulo $2^{21}$ - it generates an index-$2$ subgroup of $(\mathbb Z/2^{21}\mathbb Z)^{\times}$, but nonetheless we obtain the restriction $$m \equiv 15627\pmod{524288}.$$
Now let's look for small primes divisible by both 354294 and 524288.  It turns out that $$p = 1+11\cdot\mathrm{lcm}(354294,524288) = 1021636509697$$ is prime, and $11$ is the smallest number for which this is true.

Now consider the sets $$S_2 = \left\{2^{199283+354294\cdot k}\pmod{p}\right\}, \qquad S_3 = \left\{3^{15627+524288\cdot k}\pmod{p}\right\}.$$
It's clear from definitions that $$|S_2| = \mathrm{ord}_p\left(2^{354294}\right) = 720896, \qquad |S_3| = \mathrm{ord}_p\left(3^{524288}\right) = 649539.$$
So we expect approximately $$\frac{720896\cdot649539}{1021636509697} = 0.458\cdots$$ elements in $S_2 \cap (S_3 + 5)$.  If we have no such elements, then there can't be any solutions to $2^x = 3^m + 5$ with $m \ge 12$ and $x \ge 21$.
We get lucky, and there aren't any elements in the intersection!  TA-DA - there are no solutions other than the two you know!

In all seriousness, this shouldn't have worked.  $S_2$ is one-fourth the size we expect; $S_3$ is one-third the size.  And it was still about a fifty-fifty shot if there was anything in their intersection at all.  And $p$ was a factor of two smaller than expected.  We should have had to find much bigger congruences and use those.  But black magic happened, and everything worked out.
One more remark: the reason we chose $p$ divisible by both 354294 and 524288 was that it forced the sizes of $S_2$ and $S_3$ to be fairly small relative to $p$.  But their product should have been roughly $11/2$ the size of $p$ in the worst possible case; as I've said, we got lucky.

EDIT: Here's how to make the numbers involved much smaller.
Work modulo $3^5$; then $x \equiv 23\pmod{162}$.  Work modulo $2^2$; $m$ must be odd.  Then work modulo $163$.  The only possible residue of $2^{23+162k}\pmod{163}$ is $139$, and $134$ is not a possible residue for $3\cdot9^m$ modulo $163$.  Hence we're done.


TITLE: Projective line intersecting 3 projective subspaces
QUESTION [3 upvotes]: I am trying to solve the following problem:

Let $\mathbb{P}(U),$ $\mathbb{P}(V)$ and $\mathbb{P}(W)$ be projective subspaces of dimension $k,$ $l$ and $m$ respectively in $\mathbb{P}_K^n$.
Suppose $k+l+m\geq n-1$. Prove that there is a projective line intersecting all 3 subspaces.

So if $\mathbb{P}(U)\cap \mathbb{P}(V)\neq \emptyset,$ then it's easy because we just take any (projective) point in their intersection and any (projective) point in $\mathbb{P}(W)$ and form the projective line between them.
If $\mathbb{P}(U)\cap \mathbb{P}(V)=\emptyset,$ then $U\cap V=\{0\}$ and so $\dim(U + V)=\dim(U)+\dim(V)$ and so
$$\dim((U+V)\cap W)=k+l+m+3-\dim(U+V+W)\geq (k+l+m-(n-1))+1\geq 1$$
hence $\mathbb{P}(U+V)$ intersects $\mathbb{P}(U),$ $\mathbb{P}(V)$ and $\mathbb{P}(W)$ but it might not be a line... so now I'm stuck.
Any help greatly appreciated!

REPLY [2 votes]: I've only got time to outline this, but here we go...
We have subspaces $U, V, W$ of $K^{n+1}$, of dimension $\tilde k = k+1, \tilde l = l+1$, and $\tilde m = m+1$ respectively, with $\tilde k + \tilde l + \tilde m \geq n + 2$.
First, note that if any two subspaces have a non-zero vector in common, we are done, because their projectivisations intersect, and we can just take a line from this intersection to any point of the third subspace.  So assume that $U \oplus V \hookrightarrow K^{n+1}$.  Now, $\dim (K^{n+1} / (U \oplus V)) = n+1 - \tilde k - \tilde l \leq \tilde m - 1 = \dim W - 1$.  So there is at least one vector $w \in W \cap ( U \oplus V)$.  Write $w = u + v$, with $u \in U, v \in V$.  Assume $u \neq 0$ and $v\neq 0$, because otherwise $w \in V$ or $w \in U$, and we have already dealt with that case.
$w, u, v$ span a two-dimensional subspace, and upon projectivisation, this gives a line that intersects all three subspaces of interest.


TITLE: Determine the following sum
QUESTION [1 upvotes]: Let $S(n)$ be the sum of the digits of n in its binary representation. For example the binary notation for 19 is $10011$ and $S(19)=3$. Determine $\sum_{n=1}^{\infty} \frac{S(n)}{n(n+1)}$?
I've made several tables trying to pinpoint any useful pattern, but I've had minimal luck. The best I'd came to was determining that the number of digits is $\left \lceil{\frac{ln(n)}{ln(2)}}\right \rceil$ which gives a bound for $S(n)$. What I'd picked up from those tables is $S(2^k-1)=k$ and $S(2^k)=1$. However, breaking the sum up into those n's that are powers of 2 proved to be a bit of a disaster.

REPLY [2 votes]: $$F=\sum\limits_{n=1}^\infty\frac{S(n)}{n(n+1)}$$
This series is absolutely convergent since terms are positive and $S(n)=O(\log_2(n))$, making the general term $O\left(\frac{\ln(n)}{n^2}\right)$. Therefore we are allowed to manipulate the series and rearrange terms at will.
Notice that multiplying a number by $2$ will simply shift the binary development to the left and add a zero.
This does not change the value of the sum of digits so $\begin{cases}S(2n)=S(n)\\S(2n+1)=S(2n)+1=S(n)+1\end{cases}$
Let split $F$ along odd and even indexes:
$\begin{align}\displaystyle F
&=\frac{S(1)}2+\sum\limits_{n=1}^\infty\bigg(\frac{S(2n)}{2n(2n+1)}+\frac{S(2n+1)}{(2n+1)(2n+2)}\bigg)\\\\
&=\frac 12+\frac 12\sum\limits_{n=1}^\infty\bigg(\frac{S(n)}{n(2n+1)}+\frac{S(n)+1}{(2n+1)(n+1)}\bigg)\\\\
&=\frac 12+\frac 12\sum\limits_{n=1}^\infty S(n)\Big(\underbrace{\frac 1{n(2n+1)}+\frac 1{(2n+1)(n+1)}}_{\frac 1{n(n+1)}}\Big)+\sum\limits_{n=1}^\infty\underbrace{\frac 1{(2n+1)(2n+2)}}_{\frac 1{2n+1}-\frac 1{2n+2}}\end{align}$
The first series is $\frac 12F$ so we arrive to a formulation without $S(n)$.
$$F=1+2\sum\limits_{n=1}^\infty\bigg(\frac 1{2n+1}-\frac 1{2n+2}\bigg)\\$$
Beware it is NOT telescopic, but we can use $\int_0^1 x^n=\frac 1{n+1}$ and $\sum x^n=\frac 1{1-x}$. Note that in what's follow we can swap $\int$ and $\sum$ thanks to Fubini-Tonelli combined with absolute convergence.

$\begin{align}\displaystyle F
&=1+2\sum\limits_{n=1}^\infty\int_0^1\Big(x^{2n}-x^{2n+1}\Big)dx
=1+2\int_0^1(1-x)\Big(\sum\limits_{n=1}^\infty x^{2n}\Big)dx\\\\
&=1+2\int_0^1 (1-x)\frac{x^2}{1-x^2}dx=1+2\int_0^1 \frac{x^2}{x+1}dx\\\\
&=1+2\bigg[\tfrac 12 x^2-x+\ln(x+1)\bigg]_0^1=1+2\Big(\ln(2)-\tfrac 12\Big)
\end{align}$

$$F=2\ln(2)$$


TITLE: Is it true that the Fourier coefficient of convolution is the product of the coefficients?
QUESTION [1 upvotes]: what I mean by the title is the following: if we define the convolution between two $2\pi$-periodic, $C^1$ functions as $f*g(x) = (2\pi)^{-1}\int_{-\pi}^\pi f(x-y)g(y)dy$, is it true that the Fourier coefficients of $f*g(x)$ equal $\hat{f}(n)\hat{g}(n)$ where $\hat{f}(n),\hat{g}(n)$ are the Fourier coefficients of $f,g$ respectively?
I think I have a correct proof of this, but I am just unsure, but the result seems so beautiful, so I wanted to hear your expert opinions. Please do not post the proof of this...
Thanks

REPLY [3 votes]: Given the assumed smoothness of $f$ and $g$ this is a simple exercise about double integrals. I write $\int_T$ for the integral over a full period. Then
$$\widehat{f*g}(n)={1\over2\pi}\int_T f*g(x)\>e^{-inx}\>dx={1\over4\pi^2}\int_T\left(\int_Tf(x-y)g(y)\>dy\right)e^{-inx}\ dx\ .$$
Interchanging the order of integration gives
$$\widehat{f*g}(n)={1\over4\pi^2}\int_T g(y) \left(\int_Tf(x-y)\>e^{-inx}\> dx\right)\,dy\ .$$
In the inner integral we substitute $x:=y+t$ $(t\in T)$ and obtain
$$\widehat{f*g}(n)={1\over4\pi^2}\int_T g(y) \left(\int_Tf(t)\>e^{-in(y+t)}\> dt\right)\,dy={1\over4\pi^2}\int_T g(y) e^{-iny}\left(\int_Tf(t)\>e^{-int}\> dt\right)\,dy\ .$$
On the right hand side the inner integral is independent of $y$ and essentially $=\hat f(n)$. We therefore can write
$$\widehat{f*g}(n)=\hat f(n)\>{1\over2\pi}\int_T g(y) e^{-iny}\>dy=\hat f(n)\cdot\hat g(n)\ .$$


TITLE: How do I factorize $210a^6m^3-107a^4m^2l+18a^2l^2m-l^3$ into a term composed of multiplications of polynomials?
QUESTION [0 upvotes]: I need to factorize $210a^6m^3-107a^4m^2l+18a^2l^2m-l^3$ into a term composed of multiplications of polynomials. WolframAlpha gave me the following answer $(6a^2m-l)(l-5a^2m)(l-7a^2m)$. Is there a method I could use to obtain this (or the factorization of any other polynomial? Thanks! :)

REPLY [1 votes]: Hint: with $z = \cfrac{a^2m}{l}$ the expression writes as:
$$
l^3 \cdot \left(210 z^3 - 107 z^2+18 z -1\right)
$$
Checking the cubic for rational roots finds the factorization:
$$
210 z^3 - 107 z^2+18 z -1 = (7 z - 1) (6 z - 1) (5 z - 1)
$$


TITLE: The fourier series of periodic and real analytic function
QUESTION [0 upvotes]: Let $f$ be a real analytic and periodic function defined on the interval $[0, 2\pi]$. Then $f$ is infinitely differentiable for sure. Therefore, the fourier coefficients of $f$ decay faster than any polynomial function of the integer.
So it is clear that the fourier series of $f$ converges aboslutely and uniformly. (Moreover, the series converges to $f$ pointwise.)
Am I correct?

REPLY [1 votes]: Let $f$ be periodic. $\sum |\hat {f} (n)| <\infty$ implies that the Fourier series converges absolutely and uniformly. Since this condition is satisfied here (by comparison with $\sum\frac 1 {n^{2}}$) the answer is a definite YES.