text:
\section{Introduction}
\label{sec:intro}

For a finite group $G$ and a subset $S$ of $G\setminus\{1\}$, the (right, undirected) \textit{Cayley graph} of $G$ with respect to $S$, $\Gamma(G,S)$, has vertices corresponding to the elements $g \in G$ and edges $(g,gs)$ and $(g,gs^{-1})$ for each $g \in G$ and $s \in S$.
The Cayley graph is vertex-transitive, regular, and connected when $S$ generates $G$, which we assume throughout.
Label the edge from $g$ to $gs$ by $s$ and that from $gs$ to $g$ by $s^{-1}$ (note that edge labels for $\Gamma(G,S)$ are drawn from $S\cup S^{-1}$).
It is common to consider both together as a single undirected edge with $s$ and $s^{-1}$ indicating travel along the edge in the appropriate direction.

A \textit{path} in $\Gamma$ is an ordered sequence of adjacent vertices in $\Gamma$ and a path is \textit{self-avoiding} if no vertex appears more than once.
A \textit{Hamiltonian path} is a self-avoiding path containing every vertex of $\Gamma$.
When the initial and final vertex of a Hamiltonian path are adjacent it determines a \textit{Hamiltonian cycle} and a graph containing a Hamiltonian cycle is called \textit{Hamiltonian}.

The question, dating back to 1969 in a monograph by Lov\'{a}sz, of whether every connected vertex-transitive graph has a Hamiltonian path, remains unresolved.
The stronger claim, that every connected vertex-transitive graph has a Hamiltonian cycle, is known to be false and it has been observed that the four known counterexamples are not Cayley graphs.
The resulting conjecture that for every finite group $G$ and any generating set $S$ the Cayley graph $\Gamma(G,S)$ has a Hamiltonian cycle also remains unresolved and finding such a cycle is an NP-complete problem in general.
See~\cite{Gallian-Witte84,Curran-Gallian96,Kutnar-Marusic09,Pak-Radoicic09} for surveys of the status and history of the problem and references, including those supplying counter-conjectures.
When $S$ is not closed under inversion, it is possible for the directed graph with vertices the elements of $G$ and only edges $(g,gs)$ for $g \in G$ and $s \in S$ to have no Hamiltonian cycle.
For instance, the directed circulant graph on $\mathbb{Z}_{12}$ with generators $3, 4$ (and $6$) is not Hamiltonian (see~\cite{Gallian-Witte84} and~\cite{Locke-Witte99}).

The conjecture that every (undirected) Cayley graph is Hamiltonian is easy to prove for abelian groups and known to be true for several specific types of groups that are nearly abelian, with either specific or arbitrary generating sets.
For instance the conjecture has been shown true when
\begin{itemize}
\item $G$ is a $p$-group~\cite{Witte86},
\item the commutator subgroup $G'$ is a cyclic $p$-group~\cite{Marusic83, Durnberger83, Durnberger85, Keating-Witte85, DGMW98},
\item the order of $G$ has few prime factors~\cite{KMMMS12},
\item the order of $G$ is odd and $G'$ has order $pq$ or is cyclic of order $p^a q^b$ for $a,b\geq 0$~\cite{Witte-Morris12},
\item $G$ is nilpotent and $G'$ is cyclic~\cite{Ghaderpour-Morris14}.
\end{itemize}
It is also known that the Cayley graph of the semidirect product of two cyclic groups with respect to a specific generating set is Hamiltonian~\cite{Alspach89}.
We prove as our main result (Theorem~\ref{th:cximprimHam}) that the conjecture is true for the highly non-abelian infinite family of complex reflection groups, $G=G(de,e,n)\cong \mathbf{\mu}^n \rtimes S_n$
with respect to commonly used generating sets of reflections.  Here $\mathbf{\mu}$ is the cyclic group of $de$-th roots of unity.

\textbf{Main Result.}
\textit{If $G$ is an irreducible imprimitive complex reflection group and $S$ is a standard generating set for $G$, then the (undirected right) Cayley graph $\Gamma(G,S)$ has a Hamiltonian cycle.}

Our result generalizes that in~\cite{CSW89}, which provides an algorithm to generate a Hamiltonian cycle in each $\Gamma(G,S)$ where $G$ is a finite real reflection group and $S$ is the standard set of generating simple reflections.
That paper utilized the Coxeter presentation of the groups to give an inductive proof of the existence, and hence recursive construction, of a Hamiltonian cycle.
It also explicitly treats the small number of base cases.

Although there is no such uniformly well-behaved presentation or set of generators for complex reflection groups (see~\cite{Bremke-Malle98, Shi02}), we use those that go back to~\cite{Coxeter67, Cohen76} and are given in the standard references~\cite{BMR98, Lehrer-Taylor09}.
While these presentations, generating sets, and resulting Cayley graphs do not tend to satisfy the usual conditions for the existence of Hamiltonian cycles currently given in the literature (see further discussion at the end of Section~\ref{sec:background}), they do allow for an inductive approach similar to that in~\cite{CSW89}.
In order to exploit that approach we must treat six infinite families of groups as base cases.
For three of these families we explicitly write down Hamiltonian cycles and in the remaining three cases our proofs provide a method for doing so.

In two cases we utilize a process we call flipping which is sometimes referred to in the literature as a P\'{o}sa exchange and is
similar to a process utilized in a probabilistic algorithm to find Hamiltonian cycles in general graphs (see~\cite{Angluin-Valiant79}).
It would be interesting to further explore the application of the flipping process and related algorithms to Cayley graphs of complex reflection groups and in particular, to determine whether there exist obstructions to their success in these graphs and if so, under what conditions.
Another interesting direction would be to investigate how our result might be of use in group coding (see~\cite{KNS14}).

The paper is organized as follows.
In Section~\ref{sec:background}, following~\cite{Geck-Malle06}, we review necessary facts about real reflection groups and summarize the classification of complex reflection groups due to Shephard and Todd~\cite{Shephard-Todd54}.
The classification consists of a three-parameter infinite family, $G(de,e,n)$, along with 34 exceptional groups.
This paper treats only the $G(de,e,n)$, though we have conducted some initial investigations for the exceptional complex reflection groups.
Generating sets $S$ for the $G(de,e,n)$ are also given in Section~\ref{sec:background}.
Our formulations of the commonly used Factor Group Lemma (see~\cite{KMMMS12}), the flipping process, and the method of lifting cycles from quotient graphs are described in Section~\ref{sec:lift}.
The main result
and its proof, including all base case lemmas, appear in Section~\ref{sec:cxgroupgraphs}.

\section{Background on reflection groups}
\label{sec:background}

A \textit{Coxeter system} $(G,S)$ is a group $G$ with set of generators $S=\{s_1,\dots,s_n\}$ that has a presentation of the form
\[G=\langle s_1,\dots,s_n \mid (s_i s_j)^{m_{ij}} \rangle,\]
where $m_{ii}=1$ and $m_{ij}=m_{ji}\geq 2$ for $1\leq i\neq j \leq n$.
Such a group is called a \textit{Coxeter group} and is more commonly denoted $W$ due to the connection with Weyl groups.
The presentations of Coxeter groups are classified using diagrams that graphically encode the $s_i$ and the $m_{ij}$.
The classification of finite irreducible Coxeter groups consists of four infinite families and six exceptional groups.
Finite Coxeter groups have a geometric incarnation as they are exactly the finite groups generated by orthogonal reflections of a real vector space (see~\cite{Bourbaki02,Humphreys90}).
It can also be shown that there is a natural set of generating reflections up to conjugacy, so such a choice is fixed and these are termed \textit{simple reflections}.
Every Cayley graph $\Gamma(G,S)$ with $G$ a finite irreducible Coxeter group and $S$ a set of simple reflections is shown in~\cite{CSW89} to have a Hamiltonian cycle.

The notions of reflection and classification of finite groups generated by reflections extend to the setting of an $n$-dimensional complex vector space $V$ (for a brief survey, see~\cite{Geck-Malle06}).
A linear transformation $r:V \to V$ is a \textit{reflection} if it is of finite order and has a $+1$-eigenspace of dimension $n-1$.
In the remaining complex dimension the reflection acts by a root of unity and hence may have order greater than two.
A finite subgroup, $G$, of $\mathrm{GL}(V)$ generated by reflections is called a \textit{reflection group on $V$}.
Since $G$ is finite, the standard averaging technique makes it possible to fix a non-degenerate $G$-invariant hermitian form on $V$ and consider $G$ as a subgroup of the unitary group on $V$.
Finiteness of $G$ also guarantees the representation on $V$ is completely reducible, which means it suffices to consider reflection groups and spaces on which they act irreducibly.
More precisely, $G$ is said to act irreducibly in dimension $k$ if its fixed point space is of dimension $n-k$ and it acts irreducibly when restricted to the complement of that fixed point space.

We describe an infinite family of complex reflection groups.
Let $d,e,n \geq 1$, let $\mathbf{\mu}$ denote the cyclic group of $de$-th roots of unity, and let $\zeta$ generate $\mathbf{\mu}$.
Under the \textit{standard monomial representation}, $G(de,e,n)$ consists of
\begin{align*}
 &\hbox{monomial matrices with nonzero entries $\zeta^{a_1},\dots, \zeta^{a_n}$}, \\
 &\hbox{such that $(\zeta^{a_1}\cdots \zeta^{a_n})^d=1$, or equivalently $a_1+\cdots +a_n \equiv 0 \bmod{e}$.}
\end{align*}
Each such monomial matrix may be written as a product of a diagonal matrix with entries $\zeta^{a_1},\dots,\zeta^{a_n}$ and a permutation matrix (obtained by permuting columns of the identity matrix).
This provides an alternative description of $G(de,e,n)$ as an index $e$ subgroup of $\mathbf{\mu}\wr S_n=\mathbf{\mu}^n \rtimes S_n$, and makes it clear that $|G(de,e,n)|=d^n e^{n-1} n!$.
In this perspective, $G(de,e,n)$ consists of all
\[(a_1,\dots,a_n \mid \sigma) \hbox{ such that } a_i \in \mathbb{Z}_{de},\, a_1+\cdots +a_n \equiv 0 \bmod{e}, \hbox{ and } \sigma \in S_n,\]
and the action of $S_n$ on $\mathbf{\mu}^n$ providing the semidirect product structure on $G(de,e,n)$ is
\[\sigma.(a_1,\dots,a_n)=(a_{\sigma(1)},\dots,a_{\sigma(n)}),\]
so that if $\sigma, \tau \in S_n$,
\[(a_1,\dots,a_n \mid \sigma)(b_1,\dots,b_n \mid \tau)=(a_1+b_{\sigma(1)},\dots,a_n+b_{\sigma(n)} \mid \sigma\tau),\]
where $\sigma\tau$ is computed by applying $\sigma$ first, $\tau$ second.
This is consistent with the use of the right Cayley graph and with matrix multiplication where $(a_1, a_2, \dots , a_n \mid \sigma)$ represents the $n \times n$ matrix whose only nonzero entries are the $\zeta^{a_i}$ in position $i,\sigma(i)$ for $1\leq i\leq n$.

A reflection group $G$ on $V$ is \textit{imprimitive} if there is a decomposition $V=V_1\oplus V_2 \oplus \cdots \oplus V_k$ into proper nonzero subspaces such that $G$ permutes the subspaces.
The groups $G(de,e,n)$ with $de,n\geq 2$ are imprimitive in their action on a system of lines orthogonal to the reflecting hyperplanes and the exceptional groups are primitive.
The symmetric groups $G(1,1,n)$ do not act irreducibly in the standard monomial representation but do act irreducibly on the complement of the span of the sum of all the basis vectors and are primitive on this $(n-1)$-dimensional subspace.

The irreducible finite reflection groups were classified in~\cite{Shephard-Todd54} (see also~\cite{Lehrer-Taylor09}) and consist of the
\begin{itemize}
\item groups $G(de,e,n)$, with $de\geq 2$, $n\geq 1$, and $(de,e,n)\neq (2,2,2)$, which are imprimitive and irreducible in dimension $n$,
\item symmetric groups $G(1,1,n)$, which are primitive and irreducible in dimension $n-1$, and
\item $34$ primitive exceptional groups, numbered $G_4,\dots,G_{37}$, irreducible in dimensions $2$ through $8$.
\end{itemize}

The reason for the numbering is that the original classification listed $G(d,1,1)$, $G(1,1,n)$ and $G(de,e,n)$ with $de,n \geq 2$ separately.
If there is a $G$-invariant real subspace, $V_0$, of $V$ so that the canonical map $\mathbb{C} \otimes_{\mathbb{R}} V_0 \to V$ is a bijection, then $G$ is a \textit{real reflection group}.
The finite real reflection groups occur in the classification from~\cite{Shephard-Todd54} as:
\begin{align*}
G(1,1,n) &\hbox{ of type } A_{n-1}, \hbox{ the symmetric group } S_n, \\
G(2,1,n) &\hbox{ of type } B_n, \hbox{ the binary octahedral group } \{\pm 1\}^n \rtimes S_n, \\
G(2,2,n) &\hbox{ of type } D_n, \hbox{ an index two subgroup of } \{\pm 1\}^n \rtimes S_n, \\
G(m,m,2) &\hbox{ of type } I_2(m), \hbox{ the dihedral group of order } 2n, \hbox{ and} \\
G_{23}, G_{28}, G_{30}&, G_{35}, G_{36}, \hbox{ and } G_{37} \hbox{ of types } H_3, F_4, H_4, E_6, E_7, \hbox{ and } E_8 \hbox{ respectively}.
\end{align*}

The following explicit choices of representations of generators for the groups are provided in~\cite{Lehrer-Taylor09} and are consistent with the presentations provided by the diagrams in~\cite{BMR98}.
For $1\leq i <n$, let
\[r_i=(0,\dots,0 \mid (i\,\,i+1))=\hbox{the identity matrix with columns $i$ and $i+1$ interchanged,}\]
\begin{align*}
s&=(-1,1,0,\dots,0 \mid (1\,\,2))
=\begin{bmatrix}
0 & \zeta^{-1} & 0 & \dots & 0 \\
\zeta & 0 & 0 & \dots & 0 \\
0 & 0 & 1 & \dots & 0 \\
0 & 0 & \dots & \ddots & 0 \\
0 & \dots & \dots & 0 & 1
\end{bmatrix}\!, \hbox{ and } \\
t&=(e,0,\dots,0 \mid 1)
=\begin{bmatrix}
\zeta^e & 0 & \dots & 0 \\
0 & 1 & \dots  & 0 \\
0 & 0 & \ddots & 0 \\
0 & \dots & 0 & 1
\end{bmatrix}.
\end{align*}
Then, using $e=1$ in $t$ for $G(d,1,n)$,
\begin{align*}
G(d,1,n)&=\langle t,r_1,r_2,\dots, r_{n-1}\rangle \hbox{ for } d\geq 2,n\geq 1, \\
G(e,e,n)&=\langle s,r_1,r_2,\dots, r_{n-1}\rangle,  \hbox{ for } e\geq 2, n\geq 1, \hbox{ and } \\
G(de,e,n)&=\langle s,t,r_1,r_2,\dots, r_{n-1}\rangle, \hbox{ for } d,e,n \geq 2.
\end{align*}
In particular, $G(d,1,n)$ and $G(e,e,n)$ are generated by $n$ reflections (are \textit{well-generated}) while the groups $G(de,e,n)$ with $d,e,n\geq 2$ require $n+1$ generators.

We note that the groups $G(de,e,n)$ do not tend to satisfy the sufficient conditions for the existence of Hamiltonian cycles currently known in the literature.
For example, Theorem~1.2 of~\cite{KMMMS12} and related references guarantee the existence of a Hamiltonian cycle in any Cayley graph of a finite group whose order has a ``small'' prime factorization of certain forms, and those of~\cite{Witte86, Witte-Morris12} apply to groups of prime power and odd order respectively.
But such results will not apply in general to the $G(de,e,n)$.
Since $G(de,e,n)$ is a semidirect product involving $S_n$, rather than cyclic groups of prime order and abelian groups, it is not of the form addressed in~\cite{Durnberger83} or~\cite{Alspach89}, and it is also not nilpotent for $n\geq 3$, so the results of~\cite{Ghaderpour-Morris14} on nilpotent groups do not generally apply.
The results of~\cite{DGMW98, Keating-Witte85} apply to groups with commutator subgroups that are cyclic of prime power order.
Using the presentations and the number of one-dimensional characters of $S_n$ and $\mu$, it is easy to count one-dimensional characters of $G=G(de,e,n)$ and the abelian group $G/G'$ and thus to compute $|G'|$.
This yields $|G'|=d^{n-1}$ when $e=n=1$, $|G'|=(de)^{n-1}n!/4$ when $n=2$ and $e$ is even, and $|G'|=(de)^{n-1}n!/2$ in the remaining cases.
This makes it clear that the results of~\cite{DGMW98, Keating-Witte85} do not generally apply.

Some Hamiltonicity results address groups with simple types of generators and relations.
For instance,~\cite{Glover-Marusic07} addresses groups generated by an involution and an element of order at least three whose product is of order three, while the three lemmas in Section 2 of~\cite{Pak-Radoicic09} involve generators that are involutions and/or satisfy very simple relations.
The generating sets we use typically do not meet these hypotheses on the number of, orders of, or relations between the generators.
The main result in~\cite{Pak-Radoicic09} does provide, for an arbitrary group, the existence of a Hamiltonian cycle in its Cayley graph with respect to a relatively small generating set.
While striking, this result serves a different purpose than we address here.
Lastly, several results in the broader graph theory literature on existence of Hamiltonian cycles treat graphs with sufficiently large degree and/or sufficiently small connectivity (see e.g.,~\cite{Dirac52, Jackson80}), which do not apply to the families of Cayley graphs we consider.

\section{Lifting cycles from quotient graphs}
\label{sec:lift}

Rather than specify a sequence of vertices, an equivalent way to describe a Hamiltonian cycle is to specify an initial vertex $v_1$ and a sequence of edges.
In the case of a Cayley graph it suffices to use $v_1=1$ and to list the sequence of edges as a sequence of generators, which we denote below with square brackets to connote an ordered list.
If $P=[s_1,s_2,\dots,s_{k-1},s_k]$ denotes the sequence of edges for a path, then $P\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ will denote $[s_1,s_2,\dots,s_{k-1}]$.

Our treatment of the base cases for the inductive proof of the main result for $G(de,e,n)$ involves the construction of explicit Hamiltonian cycles.
We make use of the following techniques.

\begin{lemma}
\label{lem:l2.6}
Let $G$ be a group with generating set $S$ and let $\Gamma = \Gamma(G, S)$ denote its Cayley graph.
  Let $B = [s_1, s_2, \dots, s_k]$, where each $s_i \in S$. Let  $v = s_1s_2 \cdots s_k$. Let $w_0 = 1$ and
  for $0 < i < k$, let $w_i = s_1s_2 \cdots s_i$.  If $n > 0$,
  the path $P$ defined by $B^n \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ is
  self-avoiding if and only if whenever $0 \leq m < n$ and $v^m w_i = w_j$, it follows that  $m = 0$ and $i = j$.
\end{lemma}
\begin{proof}
 The forward direction is immediate. To establish the converse, observe that vertices
 along the path $P$ are given by expressions of the form $v^m w_i$, where $0 \leq m < n$ and $0 \leq i < k$. Suppose that for
 two such vertices we have
 $v^{m_1} w_i = v^{m_2} w_j$. We can assume that $m_1 \leq m_2$. Cancellation yields
 $v^m w_i = w_j$, where $m = m_2 - m_1 < n$. It follows that $m_1 = m_2$ and $i = j$, establishing that $P$ is self-avoiding.
\end{proof}

\begin{remark}
\label{rem:factorgroup}
  Note that, in the context of Lemma~\ref{lem:l2.6},
  $B^n \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ is a Hamiltonian path if it is self-avoiding and the size of the group $G$ is $nk$. The path $B^n$ is closed if $v$ is of order $n$.
  When $B^n$ is a Hamiltonian cycle, the condition
  \[v^m w_i = w_j \hbox{ implies } m = 0 \text{ and } i = j\]
  is equivalent to
  \[w_0, w_1, \cdots , w_{k-1} \text{ visits each left coset of } H = \langle v \rangle \text{ exactly once. }\]
  See Lemma 2.6 in~\cite{KMMMS12}.
\end{remark}

If a Hamiltonian path is known it may be possible to alter the path into a cycle with a process we call {\it flipping}.
See Figure~\ref{fig:flip1}.

\begin{center}
\begin{figure} [h!]
\begin{center}
\mbox
{
{
\beginpicture
     \setcoordinatesystem units <0.5in,0.5in>

     \setlinear
     \put {$\bullet$} at -7 1.5
     \put {$\bullet$} at -6 1.5
     \plot -6.9 1.5 -5.5 1.5 /
     \plot -4.5 1.5 -.5 1.5 /

     \plot 1.5 1.5 3 1.5 /

     \put {$\dots$} at -5 1.5

     \put {$\dots$} at 1 1.5
     \put {$\dots$} at 0 1.5

     \put {$\bullet$} at -4 1.5
     \put {$\bullet$} at -3 1.5
     \put {$\bullet$} at -2 1.5
     \put {$\bullet$} at -1 1.5
     \put {$\bullet$} at 2 1.5
     \put {$\bullet$} at 3 1.5

     \put{$s_1$} at -6.5 1.8
     \put{$s_k$} at -3.5 1.8
     \put{$s_{k+1}$} at -2.5 1.8
     \put{$s_{k+2}$} at -1.5 1.8
     \put{$s_n$} at 2.5 1.8

     \put{$s$} at .1 1.15

     \put {$\bullet$} at -7 0
     \put {$\bullet$} at -6 0
     \plot -6.9 0 -5.5 0 /
     \plot -4.5 0 -3 0 /
     \plot -2 0 -.5 0 /

     \plot 1.5 0 3 0 /

     \put {$\dots$} at -5 0

     \put {$\dots$} at 1 0
     \put {$\dots$} at 0 0

     \put {$\bullet$} at -4 0
     \put {$\bullet$} at -3 0
     \put {$\bullet$} at -2 0
     \put {$\bullet$} at -1 0
     \put {$\bullet$} at 2 0
     \put {$\bullet$} at 3 0

     \arrow <6pt> [.2,.67] from -2.6 1.5 to -2.4 1.5
     \arrow <6pt> [.2,.67] from -1.6 1.5 to -1.4 1.5
     \arrow <6pt> [.2,.67] from -3.6 1.5 to -3.4 1.5
     \arrow <6pt> [.2,.67] from -5.5 1.5 to -5.3 1.5
     \arrow <6pt> [.2,.67] from -6.5 1.5 to -6.3 1.5
     \arrow <6pt> [.2,.67] from 2.4 1.5 to 2.6 1.5
     \arrow <6pt> [.2,.67] from .4 1.5 to .6 1.5

     \arrow <6pt> [.2,.67] from -.6 1.5 to -.4 1.5
     \arrow <6pt> [.2,.67] from -.4 0 to -.6 0

     \arrow <6pt> [.2,.67] from 1.5 1.5 to 1.7 1.5
     \arrow <6pt> [.2,.67] from 1.7 0 to 1.5 0

     \arrow <6pt> [.2,.67] from -4.7 1.5 to -4.5 1.5
     \arrow <6pt> [.2,.67] from -4.7 0 to -4.5 0

     \arrow <6pt> [.2,.67] from 0 .96 to .2 .96

     \arrow <6pt> [.2,.67] from -1.4 0 to -1.6 0
     \arrow <6pt> [.2,.67] from -3.6 0 to -3.4 0
     \arrow <6pt> [.2,.67] from -5.5 0 to -5.3 0
     \arrow <6pt> [.2,.67] from -6.5 0 to -6.3 0
     \arrow <6pt> [.2,.67] from 2.6 0 to 2.4 0
     \arrow <6pt> [.2,.67] from .6 0 to .4 0

     \arrow <6pt> [.2,.67] from 0 -.54 to .2 -.54

     \put{$s_1$} at -6.5 .3
     \put{$s_k$} at -3.5 .3
     \put{$s_{k+2}^{-1}$} at -1.5 .3
     \put{$s_n^{-1}$} at 2.5 .3

     \put{$s$} at .1 -.35

     \setsolid
     \circulararc 39 degrees from -3.05 0 center at 0 8.5

     \setdots
     \setplotsymbol({\Large .})
	 \plot -3 0 -2 0 /

     \circulararc 39 degrees from -3.05 1.5 center at 0 10
     \setplotsymbol({\tiny -})
     \setsolid

     \put{$\vspace{.5in}$} at -6 -.5

     \endpicture
}
}
\caption {\small Flipping a path}
 \label{fig:flip1}
\end{center}
\end{figure}
\end{center}

\begin{definition}
If $P = [s_1,s_2, \dots , s_n]$ is a path and for some $k < n$ the vertices $s_1s_2\cdots s_k$ and $s_1s_2\cdots s_n$ are adjacent via an edge labeled $s$,
 then the {\it flip} of $P$ with respect to $s$, $F(P,s)$,  is the path $[s_1,s_2,\dots , s_k, s, s_n^{-1}, s_{n-1}^{-1}, \dots, s_{k+2}^{-1}]$.
\end{definition}

The walks $P$ and $F(P,s)$ visit exactly the same vertices.
In particular, if $P$ is self-avoiding, then $F(P,s)$ is self-avoiding.

Several of the proofs presented below make use of a lifting technique similar to that presented in the proof of Theorem~1.1 in~\cite{CSW89}.
It relies on a method for combining disjoint cycles in the Cayley graph.

\begin{definition}
\label{def:cjp}
If $C_1$ and $C_2$ are disjoint cycles in $\Gamma(G,S )$ and $r \in S$, we say that $C_1$ and $C_2$ satisfy the {\it commutative joining property} with respect to $r$ if there exist edges $(g_i,g_i s)$ in the $C_i$ and such that $g_2 = g_1 r$ and $r$ commutes with $s$.
\end{definition}

\begin{figure} [h!]
\begin{center}
\mbox
{
{
\beginpicture
     \setcoordinatesystem units <0.5in,0.5in>

     \setlinear

     \plot 0 1.4 1 1 /
     \plot 1 1 1 .4 /
     \plot 0 0 1 .4 /

     \arrow <6pt> [.2,.67] from 1.65 1 to 1.85 1
     \arrow <6pt> [.2,.67] from 1.65 .4 to 1.85 .4

     \arrow <6pt> [.2,.67] from .4 .16 to .6 .24
     \arrow <6pt> [.2,.67] from 2.9 1.16 to 3.1 1.24
     \arrow <6pt> [.2,.67] from 2.9 .24 to 3.1 .16
     \arrow <6pt> [.2,.67] from .4 1.24 to .6 1.16
     \arrow <6pt> [.2,.67] from 1 .8 to 1 .6

     \plot 1 1 2.5 1 /

     \plot 1 .4 2.5 .4 /

     \plot 2.5 1 3.5 1.4 /

     \plot 2.5 .4 3.5 0 /

     \put {$s$} at 1.7 .85
     \put {$r$} at .7 .7
     \put {$s$} at 1.7 .25

     \put {$C_1$} at 1.7 1.7

     \put {$g_1$} at 1 1.25
     \put {$g_1s$} at 2.4 1.25

     \put {$g_2$} at 1 .05
     \put {$g_2s$} at 2.4 .05

     \put {$\bullet$} at 1 .4
     \put {$\bullet$} at 2.5 .4

     \put {$\bullet$} at 1 1
     \put {$\bullet$} at 2.5 1

     \put {$C_2$} at 1.7 -.3

     \plot 5 1.4 6 1 /
     \plot 6 1 6 .4 /
     \plot 5 0 6 .4 /

     \plot 7.5 1 8.5 1.4 /
     \plot 7.5 1 7.5 .4 /
     \plot 7.5 .4 8.5 0 /

     \put {$r$} at 5.7 .7
     \put {$r^{-1}$} at 7.9 .75

     \put {$\bullet$} at 6 .4
     \put {$\bullet$} at  7.5 .4
     \put {$\bullet$} at 6 1
     \put {$\bullet$} at  7.5 1

     \arrow <6pt> [.2,.67] from 5.6 .24 to 5.4 .16
     \arrow <6pt> [.2,.67] from 7.9 1.16 to 8.1 1.24
     \arrow <6pt> [.2,.67] from 8.1 .16 to 7.9 .24
     \arrow <6pt> [.2,.67] from 5.4 1.24 to 5.6 1.16
     \arrow <6pt> [.2,.67] from 6 .8 to 6 .6
     \arrow <6pt> [.2,.67] from  7.5 .6 to 7.5 .8

     \setdots
     \setplotsymbol({\Large .})

     \plot 6 .4 7.5 .4 /
     \plot 6 1 7.5 1 /

     \setplotsymbol({\tiny -})
     \setsolid

     \put {$C$} at 6.7 1.7

     \put {$g_1$} at 6 1.25
     \put {$g_1s$} at 7.4 1.25

     \put {$g_2$} at 6 .05
     \put {$g_2s$} at 7.4 .05

\endpicture
}
}
\caption {\small Combining cycles with the commutative joining property}
\label{fig:commjoin}
\end{center}
\end{figure}

When two cycles satisfy the commutative joining property they can be combined into a new cycle $C$ which spans the union of the vertex sets of $C_1$ and $C_2$.
This is accomplished by first taking the edge $(g_1, g_1 r)$ from $C_1$ to $C_2$, traversing $C_2$ in reverse until arriving at $g_2 s$, then taking the edge $(g_2 s, g_2 s r^{-1})$.
Because $r$ and $s$ commute, $g_2 s r^{-1} = g_1 r s r^{-1} = g_1 s$ and the cycle is completed by continuing on around $C_1$ to finish back at $g_1$.
See Figure~\ref{fig:commjoin}.

The following propositions extend this joining strategy to sets of disjoint cycles.
\begin{proposition}
\label{prop:multi-join}
Let $G$ be a finite group with generating set $S$. Let $\{C,C_1,\dots,C_n\}$ be a collection of disjoint cycles in $\Gamma(G,S)$ and $r \in S$.
If $C$ and each $C_l$ have the commutative joining property with respect to $r$ then all of the cycles can be combined to form
a single cycle spanning the union of the various vertex sets.

\end{proposition}
\begin{proof}

For each cycle $C_l$, find distinct edge pairs $(g_l, g_ls_l)$ in $C$ and $(g_lr,g_ls_lr)$ in $C_l$ where $r$ and $s_l$ commute.
When $C$ is combined with one of the other cycles as described above, the resulting cycle contains each of the edges $(g_l,g_ls_l)$ corresponding to the remaining $C_l$.
Therefore, the process can be iterated until the cycle contains all of the $C_l$.
\end{proof}

\begin{proposition}
\label{prop:lifting}
Let $G$ be a finite group with generating set $S=\{r_1,\dots,r_n\}$, where $r_n$ is of order two. Let $H=\langle r_1,\dots,r_{n-1}\rangle$.
If $\Gamma(H,S \setminus \{r_n\})$ has a Hamiltonian cycle $C_H$ with the property
\begin{equation*}
 \text{whenever $(g,gs)$, $(gs, gst)$ are consecutive edges in $C_H$, either $s$ or $t$ must commute with $r_n$},
 \end{equation*}
then $\Gamma(G,S)$ has a Hamiltonian cycle.
\end{proposition}
\begin{proof}

 Let $\{H_l \mid l = 1, \dots, k\}$ be the set of left cosets of $H$ with $H_1 = H$. Let $\Gamma_l$ denote the subgraph of $\Gamma(G,S \setminus \{r_n\})$
 with vertex set $H_l$. Each $\Gamma_l$ is isomorphic to $\Gamma(H,S \setminus \{r_n\})$.
 Since $\Gamma(G,S)$ is connected, the set of subgraphs $\Gamma_l$ can be linked using edges labelled $r_n$.
 To start, set $C = C_H$.

 Inductive hypothesis: $\Gamma(G,S)$ contains a cycle $C$ such that
 \begin{itemize}
 \item the vertex set of $C$ is the union of some subcollection of the left cosets of $H$, and

 \item if $r_i$ and $r_j$ are consecutive edge labels in $C$ and neither is
 $r_n$ then $r_i$ and $r_j$ also appear as consecutive edge labels in the cycle $C_H$.

 \end{itemize}

 The inductive hypothesis is trivially satisfied when $C=C_H$.
 If the vertex set of $C$ is all of $G$ we are finished. If not, there is an index $l$ such that
 $C$ and $\Gamma_l$ are disjoint and linked by $r_n$. Find consecutive
 edges $(g^\prime, g^\prime r_i)$ and $(g^\prime r_i, g^\prime r_i r_j) = (g, g r_j)$ in $C$ and a vertex $g_l \in \Gamma_l$
 with $g r_n = g_l$. Observe that neither $r_i$ nor $r_j$ is $r_n$ since $r_n$ is of order 2.

  From the inductive hypothesis the edge labels $r_i$ and $r_j$ must appear as consecutive edge labels in $C_H$. It follows that
  either $r_i$ or $r_j$ commutes with $r_n$. Assume that $r_n$ and $r_j$ commute; the case where $r_n$ commutes with $r_i$ is handled in similar fashion.

  The cycle $C_H$ must contain an edge of the form $(h, h r_j)$ for some $h \in H$. It follows that
  the cycle $C_l = g_lh^{-1}C_H$ is a spanning cycle for $\Gamma_l$ and
  contains the edge $(g_l, g_l r_j)$. Since $C_l$ contains $(g_l,g_lr_j)$ and $gr_n=g_l$, we conclude that  $C$ and $C_l$ have the commutative joining property with respect to $r_n$ and
  can be combined as described above, creating a
 new cycle containing all of the vertices from $C$ and $C_l$, which we again call $C$.

 The new vertex set $C$ is a union of cosets of $H$.
 Consecutive edge labels in $C$, neither of which is $r_n$, signify
 consecutive edges coming from either $C_l$ or the previous version of $C$ and,
 in either case,  must appear as consecutive edge labels in $C_H$. The inductive hypothesis remains valid.

 Continuing in this manner we arrive at a cycle whose vertex set is the union of all of the left cosets of $H$ and is, therefore, a Hamiltonian cycle in $\Gamma(G,S)$.
\end{proof}

In the preceding proof, any choice of an edge labeled $r_n$ connecting $C$ and $\Gamma_l$ will work in the inductive step.
In general, there will be many such edges.
If the conditions on $C_H$ are relaxed to allow the cycle to contain instances of consecutive edge labels signifying generators, neither of which commute with $r_n$, then the inductive step fails unless the edge connecting $C$ and $\Gamma_l$ can be chosen to avoid these ``bad'' portions of the copies of $C_H$ that have accumulated in $C$.

\begin{definition}
\label{def:badness}
Let $G$  be a finite group with generating set $S$. Let $C$ be a cycle in $\Gamma(G, S)$. For $r$ in $S$ define the {\it badness} of $C$ with respect to $r$, denoted
$bad(C,r)$, to be the number of instances in $C$ of consecutive edge labels $s$ and $t$ where $r$ fails to commute with both of the generators $s$ and $t$.
\end{definition}

\begin{corollary}
\label{cor:badness}

Let $G$ be a finite group with generating set $S=\{r_1,\dots,r_n\}$, where $r_n$ is of order two. Let $H=\langle r_1,\dots,r_{n-1}\rangle$.
Let $\{\Gamma_l\}$ denote the components of $\Gamma(G, S \setminus \{r_n\})$.
Denote by $c(i,j)$ the number of distinct edges in $\Gamma(G,S)$ that are  labeled $r_n$ and connect $\Gamma_i$ and $\Gamma_j$.
If $\Gamma(H, S \setminus \{r_n\})$ contains a spanning cycle $C_H$ with $bad(C_H, r_n) < c(i,j)$ for all positive $c(i,j)$ then
  $\Gamma(G,S)$ contains a Hamiltonian cycle.

 \end{corollary}
\begin{proof}
  The proof proceeds exactly as the proof of Proposition \ref{prop:lifting}.   Each constructed $C_l$
  has the same sequence of edge labels as $C_H$ so that $bad(C_l,r_n) = bad(C_H,r_n)$.
  In the inductive step,
  when a $\Gamma_l$ is chosen that is connected to $C$ by an edge labeled $r_n$, there must be $c(i,l)$ different vertices in $C$,
  coming from some previously
  incorporated $C_i \subset \Gamma_i$,
  that connect $C$ to $\Gamma_l$ by applying $r_n$. The edges in $C$ that pass through these vertices come from $C_i$ and bear consecutive
  edge labels consistent with the sequence of edge labels in $C_H$. Since $c(i,l)$ exceeds $bad(C_H,r_n)$, a suitable choice of connecting edge can be made.
\end{proof}

\section{Application to Cayley graphs of complex reflection groups}
\label{sec:cxgroupgraphs}

Examining the diagrams and corresponding presentations in~\cite{BMR98} or the matrix forms of the generators given in Section~\ref{sec:background} shows that in
\begin{align*}
G(d,1,n) & \hbox{ with } d \geq 2, n \geq 3, \\
G(e,e,n) & \hbox{ with } e \geq 2, n \geq 4, \hbox{ and} \\
G(de,e,n)& \hbox{ with } d,e \geq 2, n \geq 4,
\end{align*}
$r_{n-1}$ commutes with all generators other than $r_{n-2}$.
Thus Proposition~\ref{prop:lifting} will apply to treat the induction step in the proof of Theorem~\ref{th:cximprimHam} for these cases.
It will be necessary to separately address the remaining infinite base cases,
\begin{align*}
G(d,1,2) & \hbox{ with } d \geq 2, \\
G(e,e,3) & \hbox{ with } e \geq 2, \\
G(de,e,2) & \hbox{ with } d,e \geq 2, \hbox{ and } \\
G(de,e,3) & \hbox{ with } d,e \geq 2.
\end{align*}

In~\cite{BMR98} the case of $e=2$ in $G(de,e,n)$ is treated separately (though some indication was given it could be combined, we never resolved an issue concerning the double braid relation).
Here we treat separately the cases of $d=2$ in $G(de,e,2)$ and $G(de,e,3)$ but do not distinguish $e=2$.
Explicit Hamiltonian cycles are given for the families $G(d,1,2)$, $G(2e,e,2)$, and $G(e,e,3)$ in Lemmas~\ref{le:G(d,1,2)}, \ref{le:G(2e,e,2)}, and~\ref{le:G(e,e,3)}.
In Lemma~\ref{le:G(de,e,2)} we construct a Hamiltonian cycle in the graph for $G(de,e,2)$ by applying the flipping process to an explicit Hamiltonian path.
Lemmas~\ref{le:G(de,e,3)} and~\ref{le:G(2e,e,3)} achieve the lifting of the cycles given for $G(de,e,2)$ and $G(2e,e,2)$ to $G(de,e,3)$ and $G(2e,e,3)$ respectively.

Recall that we are using right Cayley graphs and all arithmetic is resolved with the appropriate modulus.
In the first two lemmas denote $r_1$ by $r$ and in all proofs denote the elements of the permutation group $S_3$ by:
\[\sigma_0=1, \quad \sigma_1=(1\,\,2), \quad \sigma_2=(2\,\,3), \quad \sigma_3=(1\,\,3), \quad \sigma_4=(1\,\,2\,\,3), \quad \sigma_5=(1\,\,3\,\,2).
\]

\begin{lemma}
\label{le:G(d,1,2)}
Let $G=G(d,1,2)$ with $d\geq 2$, which has presentation
\[G=\langle t,r \mid t^d=r^2=1, trtr=rtrt \rangle.\]
If $B=[[t]^{d-1},r]$, then $B^{2d}$
is a Hamiltonian cycle in $\Gamma(G,\{r,t\})$.
\end{lemma}

\begin{proof}
The elements of $G(d,1,2)$ are of the form
\[\{(a,b \,\mid\, \sigma) \mid 0 \leq a,b < d \hbox{ and } \sigma \in S_2=\{\sigma_0,\sigma_1\}\}.\]
Entries in the tuples representing vertices are determined up to congruence modulo $d$.
Denote the walk $B^{2d}\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ by $P$.
The number of vertices visited by $P$ is $2d^2$ which is the order of the group $G(d,1,2)$.
It suffices to show that $B^{2d}$ is closed and $P$ is self-avoiding.

Let $v = t^{d-1}r$ and $w_i = t^i$ for $0 \leq i < d$.
Since $t$ is of order $d$, the vertices in $w_0, \dots, w_{d-1}$ are distinct.
In tuple notation, $t$ is $(1,0 \mid \sigma_0)$ and $r$ is $(0,0 \mid \sigma_1)$.
From this,
\[v = t^{d-1}r = (d-1,0 \mid \sigma_0)(0,0 \mid \sigma_1) = (-1,0 \mid \sigma_1),\]
$v^2 = (-1,-1 \mid \sigma_0)$, and $v$ is of order $2d$, establishing
that $B^{2d}$ is closed.

Suppose $0 \leq m < 2d$, $0 \leq i,j < d$ and $v^m w_i = w_j$. Since $w_i = (i, 0 \mid \sigma_0)$ and $w_j = (j, 0 \mid \sigma_0)$, $m$ must be even, say $m = 2k$.
Then $v^m w_i = w_j$ becomes $(-k + i,-k \mid \sigma_0) = (j,0 \mid \sigma_0)$.
It follows that $k \equiv 0 \bmod{d}$ and $i \equiv j \bmod{d}$.
Since $0 \leq i,j,k < d$ it must be that $k = 0$ and  $i = j$.
Lemma 3.1 applies to allow us to conclude that $P = B^{2d} \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ is self-avoiding.
\end{proof}

\begin{lemma}
\label{le:G(2e,e,2)}
Let $G=G(2e,e,2)$ with $e\geq 3$, which has presentation
\[G=\langle r,s,t \mid r^2=s^2=t^2=1,\, tsr=srt,\, \underbrace{rtsrsrs\cdots}\limits_{e+1 \; \mathrm{factors}}=\underbrace{tsrsrs\cdots}\limits_{e+1 \; \mathrm{factors}} \rangle.\]
If $B = [[[r,s]^{e-1}],r,t]$ then the walk $B^4$ is a Hamiltonian cycle in $\Gamma(G,\{r,s,t\})$.
\end{lemma}

\begin{proof}
The elements of $G(2e,e,2)$ are of the form

\[\{(a,b \,\mid\, \sigma) \mid 0 \leq a,b < 2e, a + b \equiv 0 \bmod{e} \hbox{, and } \sigma \in S_2=\{\sigma_0,\sigma_1\}\}.\]

Entries in the tuples representing vertices are determined up to congruence modulo $2e$.
We show that $B^4$ is closed and $P=B^4\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ is self-avoiding.

Let $w_{2i} = (rs)^i$ and $w_{2i+1} = (rs)^i r$ for $0 \leq i < e$. Let $v = (rs)^{e-1}rt = (e - 1, 1 \mid \sigma_1)$.
It follows that $v^2 = (e, e \mid \sigma_0)$ so that $v$ is of order $4$ and $B^4$ is closed.
The number of vertices visited by $P$ is $8e$ which is the order of the group $G(2e,e,2)$.
It suffices to show that $P$ is self-avoiding, which we establish using Lemma \ref{lem:l2.6}.

Let $0 \leq m < 4$ and suppose we have $v^m w_i = w_j$.
We may assume that $j$ is even, otherwise, right-multiply by $r$.
It follows that the resulting $m$ and $i$ must have the same parity.
There are two cases to consider:

Case 1:  $m$ is even. Set $m = 2l$ for $l = 0 \text{ or } 1$ and $i = 2 l_i$, $j = 2 l_j$.
Then $v^m w_i = w_j$ becomes
\[(l e + l_i, l e - l_i \mid \sigma_0) = (l_j, -l_j \mid \sigma_0).\]

This yields a system of two congruences that imply $l_i - l_j \equiv 0 \bmod{e}$, forcing $l_i = l_j$ and $i = j$.
It follows that $l$ must be $0$ and so $m = 0$.

Case 2:  $m$ is odd. Set $m = 2 l+1$ for $l = 0 \text{ or } 1$ and $i = 2l_i+1$, $j = 2 l_j+1$.
Then $v^m w_i = w_j$ becomes
\[((l+1)e-l_i-1, le+l_i+1 \mid \sigma_0) = (l_j, -l_j \mid \sigma_0) \]
yielding the system of congruences
\begin{align*}
    e+le - l_i - 1 &\equiv \phantom{-}l_j \bmod{2e}\\
    l e + l_i + 1 &\equiv -l_j \bmod{2e}
  \end{align*}
which has no solution.
Lemma 3.1 applies to allow us to conclude that $P$ is self-avoiding.
 \end{proof}

In the next lemma, to avoid subscripts, continue to denote $r_1$ by $r$ and denote $r_2$ by $q$.

\begin{lemma}
\label{le:G(e,e,3)}
Let $G=G(e,e,3)$ with $e\geq 2$, which has presentation
\[G=\langle s,r,q \mid s^2=r^2=q^2=1,\, sqs=qsq,\, rqr=qrq, qsrqsr=srqsrq,\, \underbrace{srs\cdots}\limits_{e \; \mathrm{factors}}=\underbrace{rsr\cdots}\limits_{e \; \mathrm{factors}}. \rangle\]
Let $A = [q,s,q,r,q,r]$ and $B=[A^e \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}, s]$.
Then $B^e$ is a Hamiltonian cycle in $\Gamma = \Gamma(G,\{s,r,q\})$.
\end{lemma}
\begin{proof}
The elements of $G(e,e,3)$ are of the form
\[\{(a,b,c \,\mid\, \sigma) \mid 0 \leq a,b,c < e, a + b + c \equiv 0 \bmod{e} \hbox{, and } \sigma \in S_3=\{\sigma_0,\sigma_1,\dots,\sigma_5\}\}.\]
Entries in the tuples are determined up to congruence modulo $e$.

Let $1=w_0, w_1, \dots, w_{k-1}$ denote the vertices, in sequence, of the walk $A^e \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ and let $v = w_{k-1}s$. Note that $k = 6e$. In tuple notation,
\begin{alignat*}{2}
q &= (0,0,0 \mid \sigma_2), &\qquad qsqr &= (-1,0,1 \mid \sigma_5), \\
qs &= (-1,0,1 \mid \sigma_4), &\qquad qsqrq &= (-1,0,1 \mid \sigma_1), \\
qsq &= (-1,0,1 \mid \sigma_3), &\qquad qsqrqr &= (-1,0,1 \mid \sigma_0).
\end{alignat*}
Note that all $\sigma \in S_3$ appear in this list.

The walk determined by $A^e\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#} s$ ends in the vertex $v = (qsqrqr)^e rs = (1, -1, 0 \mid \sigma_0)$ and $v$ has order $e$.
Suppose $v^m w_i = w_j$. Write $w_i = (qsqrqr)^{l_i} v_i$ and $w_j = (qsqrqr)^{l_j} v_j$ where $v_i, v_j \in \{1, q, qs, qsq, qsqr, qsqrq\}$.
It follows that the tuples for $v_i$ and $v_j$ must contain the same $\sigma$ and consequently must be equal. Cancellation results in a reduction to either
\[v^m (qsqrqr)^l = 1 \hbox{ or } v^m = (qsqrqr)^l\]
where $l = \vert l_i - l_j \vert $.

The first equation asserts that $(m - l,-m,l \mid \sigma_0) = (0,0,0 \mid \sigma_0)$ forcing $m = l = 0$ and $w_i = w_j$. The second equation asserts
that $(m, -m, 0 \mid \sigma_0) = (-l, 0, l \mid \sigma_0)$, again forcing $m = l = 0$ and $w_i = w_j$. Lemma 3.1 allows us to conclude that $P$ is self-avoiding.
The order of the group $G$ is $6e^2$ and $v$ is of order $e$ so $B^e$ is closed and is a Hamiltonian cycle.
\end{proof}

\begin{lemma}
\label{le:G(de,e,2)}
Let $G=G(de,e,2)$ with $d \geq 3, e\geq 2$, which has presentation
\[G=\langle t,s,r \mid r^2=s^2=t^d=1,\, tsr=srt,\, \underbrace{rtsrsrs\cdots}\limits_{e+1 \; \mathrm{factors}}=\underbrace{tsrsrs\cdots}\limits_{e+1 \; \mathrm{factors}} \rangle.\]
Let $A = [[t]^{d-1},s]^{2d}$, $B=[A\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}, r]$ and $S = \{t, s, r\}$.
Then  $B^e\nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ is a Hamiltonian path in $\Gamma(G,S)$ and two successive flips of this path with respect to $s$ produce a Hamiltonian path $P$ such that $[P, r]$ is a Hamiltonian cycle in $\Gamma(G,S)$.
\end{lemma}

\begin{proof}

Let $H = \langle s, t \rangle$.
An elementary argument establishes that the vertex set of the walk $A$ is $H$.
The proof of Lemma 4.1 can be modified slightly to provide an argument showing that
$A $ is a Hamiltonian cycle in $\Gamma(H,\{s,t\})$. It follows that $|H|=2d^2$ and $H$ has index $e$ in $G$.

The right cosets of $H$ are $H, Hsr, H(sr)^2, \dots , H(sr)^{e-1}$. To see this, suppose for some $0 \leq i, j < e$, that
$(sr)^i$ and $(sr)^j$ determine the same right coset of H. Assume $i \geq j$. It follows
that $(sr)^{k} \in H$ where $k = i-j$. Elements of $H$ of the form $(a, b \mid \sigma_0)$ must arise as $(t^{d-1}s)^{2m}t^n$ for suitable $m, n$.
But $(sr)^k = (-k, k \mid \sigma_0)$ while $(t^{d-1}s)^{2m}t^n = (-me + ne, -me \mid \sigma_0)$.
If $(sr)^k=(t^{d-1}s)^{2m}t^n$ then $k\equiv -me \bmod{de}$ and hence
$k$ must be congruent to 0 modulo $e$, but since $0 \leq k < e$, it must be that $k = 0$.

The graph $\Gamma(G, S)$ is partitioned into $e$ subgraphs corresponding to the cosets of $H$.
Each of these subgraphs has a spanning cycle that is obtained by applying $A$ starting at each of $1, sr, (sr)^2, \dots (sr)^{e-1}$.
If the final $s$ in each of these cycles is replaced by $r$ the effect
is the same as the concatenation of $A$ with $[s,r]$, effectively moving to the next coset.
Since $s$ is of order 2, $[A,s,r] = [A \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#} ,r] = B$.
Thus, $B^e \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ utilizes each subgraph cycle to form a Hamiltonian path in $\Gamma(G, S)$.

The Hamiltonian path $B^e \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ ends at the vertex $(-e,e \mid \sigma_1)$. It remains to show how to alter this path so that it ends in a vertex adjacent to $1$.
The cosets of $H$ are closed with respect to right multiplication by $s$ so that
flipping the path $B^e \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$ with respect to $s$ only alters the segment
spanning the last coset of $H$. The first flip using $s$ reverses the cycle (path) in the last coset, and ends
at
\[(-(e-1),e-1 \mid \sigma_0) t = (1, e-1 \mid \sigma_0).\]
This reversal changes each $t$ to $t^{-1}$ in the portion of the path that is traversed backwards.
The second  flip using $s$ produces a path that ends at
\[(1, e-1 \mid \sigma_0) s t^{-1} = (0, e \mid \sigma_1)t^{-1} = (0, 0 \mid \sigma_1),\]
so the terminal vertex of the path is now adjacent, via $r$, to $1$. Refer to Figure~\ref{fig:flipping}.
\end{proof}
\begin{figure} [h!]
\begin{center}
\mbox
{

\beginpicture
     \setcoordinatesystem units <0.5in,0.5in>

    \setsolid
    \plot -5 1 -2 1 /
    \plot -1 1 3 1 /
    \plot  4 1 6 1 /

    \arrow <6pt> [.2,.67] from -4.5 1 to -4.3 1
    \arrow <6pt> [.2,.67] from -3.5 1 to -3.3 1
    \arrow <6pt> [.2,.67] from -2.5 1 to -2.3 1
    \arrow <6pt> [.2,.67] from -.5 1 to -.3 1
    \arrow <6pt> [.2,.67] from .5 1 to .7 1
    \arrow <6pt> [.2,.67] from 1.5 1 to 1.7 1
    \arrow <6pt> [.2,.67] from 2.5 1 to 2.7 1
    \arrow <6pt> [.2,.67] from 4.5 1 to 4.7 1
    \arrow <6pt> [.2,.67] from 5.5 1 to 5.7 1

    \put{$t$} at -4.5 .7
    \put{$t$} at -3.5 .7

    \put{$t$} at .5 .7

    \put{$t$} at 4.5 .7
    \put{$t$} at 5.5 .7

    \put{$s$} at .39 2
    \put{$s$} at -1.3 1.5

    \put {$\bullet$} at -5 1
    \put {$\bullet$} at -4 1
    \put {$\bullet$} at -3 1

    \put {$\dots$} at -1.5 1

    \put {$\bullet$} at 0 1
    \put {$\bullet$} at 1 1
    \put {$\bullet$} at 2 1

    \put {$\dots$} at 3.5 1

    \put {$\bullet$} at 5 1
    \put {$\bullet$} at 6 1

     \setdots
     \setplotsymbol({\Large .})
     \circulararc -46 degrees from -5 1 center at .5 -12
     \setplotsymbol({\tiny -})
     \setsolid

     \setdots
     \setplotsymbol({\Large .})
     \circulararc -35 degrees from -4 1 center at -1.5 -7
     \setplotsymbol({\tiny -})
     \setsolid

     \endpicture

\vskip .4in
\mbox
{

\beginpicture
     \setcoordinatesystem units <0.5in,0.5in>

    \setsolid
    \plot -4 1 -2 1 /
    \plot -1 1 0 1 /
    \plot  1 1 3 1 /
    \plot  4 1 6 1 /

    \put{$t$} at -3.5 .8

    \put{$t^{-1}$} at 4.5 .8
    \put{$t^{-1}$} at 5.5 .8

    \put{$s$} at .39 2
    \put{$s$} at -1.3 1.5

    \arrow <6pt> [.2,.67] from -3.5 1 to -3.3 1
    \arrow <6pt> [.2,.67] from -2.5 1 to -2.3 1
    \arrow <6pt> [.2,.67] from -.5 1 to -.3 1
    \arrow <6pt> [.2,.67] from 1.7 1 to 1.5 1
    \arrow <6pt> [.2,.67] from 2.7 1 to 2.5 1
    \arrow <6pt> [.2,.67] from 4.7 1 to 4.5 1
    \arrow <6pt> [.2,.67] from 5.7 1 to 5.5 1

    \arrow <6pt> [.2,.67] from .5 2.11 to .7 2.11
    \arrow <6pt> [.2,.67] from -1.4 1.38 to -1.6 1.38

    \put {$\bullet$} at -5 1
    \put {$\bullet$} at -4 1
    \put {$\bullet$} at -3 1

    \put {$\dots$} at -1.5 1

    \put {$\bullet$} at 0 1
    \put {$\bullet$} at 1 1
    \put {$\bullet$} at 2 1

    \put {$\dots$} at 3.5 1

    \put {$\bullet$} at 5 1
    \put {$\bullet$} at 6 1

     \circulararc -46 degrees from -5 1 center at .5 -12

     \circulararc -35 degrees from -4 1 center at -1.5 -7

     \setdots
     \setplotsymbol({\Large .})

     \plot  -5 1 -4 1 /
     \plot  0 1 1 1 /

     \setplotsymbol({\tiny})
     \setsolid

     \endpicture

\caption {\small Altering the Hamiltonian path in Lemma \ref{le:G(de,e,2)}}
\label{fig:flipping}
\end{center}
\end{figure}

\begin{lemma}
\label{le:G(de,e,3)}
Let $G=G(de,e,3)$ with $d\geq 3, e\geq 2$, which has presentation
\begin{align*}
G=\langle t,s,r_1,r_2 \mid r_1^2=r_2^2=s^2=t^d&=1,\, tr_2=r_2t,\, tsr_1=sr_1
,\, sr_2s=r_2sr_2,\, r_1r_2r_1=r_2r_1r_2, \\
\underbrace{r_1tsr_1sr_1s\cdots}\limits_{e+1 \; \mathrm{factors}}&=\underbrace{tsr_1sr_1s\cdots}\limits_{e+1 \; \mathrm{factors}},\,\, r_2sr_1r_2sr_1=sr_1r_2sr_1r_2 \rangle.
\end{align*}
Then $\Gamma(G,\{t,s,r_1,r_2\})$ has a Hamiltonian cycle.
\end{lemma}

\begin{proof}

Let $H = \langle t,s,r_1 \rangle$ and observe that $H$ is isomorphic to
$G(de,e,2)$. Set $S = \{t,s,r_1,r_2\}$. The components, $\{\Gamma_l\}$, of
$\Gamma(G,S \setminus \{r_2\})$ are subgraphs on the various cosets of $H$ with $r_2$-labeled edges removed.
Since $r_2$ is of order two, we have a setting consistent with Corollary \ref {cor:badness}.

For the cycle $C_H$ we take the Hamiltonian cycle constructed in Lemma \ref{le:G(de,e,2)}.
Using the notation of Lemma \ref {le:G(de,e,2)}, $r_1$ is matched with $r$.
Since $t$ and $r_2$ commute, the value of $bad(C_H,r_2)$ is found by counting the number of occurrences of consecutive $rs$ or $sr$ edge pairs.
No such pairs appeared in the initial Hamiltonian path used in the construction of $C_H$.
At most two such pairs are introduced by the two $s$-flips and they must occur at the beginning and end of the altered path through the final coset (examine Figure~\ref{fig:flipping}).
Consequently, $bad(C_H,r_2) \leq 2$.

Suppose $\Gamma_i$ and $\Gamma_j$ are connected by an $r_2$ edge. Let $H_i = g_iH$ and $H_j = g_jH$
denote the left cosets that are the vertex sets of $\Gamma_i$ and $\Gamma_j$, respectively. Then
there are $h_i, h_j \in H$ with $g_ih_ir_2 = g_jh_j$. The generators $t$ and $r_2$ commute so that for $0 \leq k < d$ we have
\[ g_ih_it^kr_2 = g_ih_ir_2t^k = g_jh_jt^k\]
and each $(g_ih_it^k,g_jh_jt^k)$ is an edge linking $\Gamma_i$ and $\Gamma_j$. This shows that $c(i,j) \geq d$. Since $d \geq 3$ and $bad(C_H,r_2) \leq 2$,
Corollary \ref{cor:badness} applies and we conclude that $\Gamma(G,\{t,s,r_1,r_2\})$ has a Hamiltonian cycle.
\end{proof}

\begin{lemma}
\label{le:G(2e,e,3)}
Let $G=G(2e,e,3)$ with $e\geq 2$, which has presentation
\begin{align*}
G=\langle t, s, r_1, r_2 \mid r_1^2=r_2^2=s^2=t^2&=1,\, tr_2=r_2t,\, tsr_1=sr_1
,\, sr_2s=r_2sr_2,\, r_1r_2r_1=r_2r_1r_2, \\
\underbrace{r_1tsr_1sr_1s\cdots}\limits_{e+1 \; \mathrm{factors}}&=\underbrace{tsr_1sr_1s\cdots}\limits_{e+1 \; \mathrm{factors}},\,\, r_2sr_1r_2sr_1=sr_1r_2sr_1r_2 \rangle.
\end{align*}
Then $\Gamma(G,\{t,s,r_1,r_2\})$ has a Hamiltonian cycle.
\end{lemma}

\begin{proof}
Let $S = \{t, s, r_1, r_2\}$ and $H = \langle S \setminus \{r_2\} \rangle$. Observe that each generator in $S$ is of order 2 and that
$H$ is isomorphic to $G(2e,e,2)$.
Let $\{\Gamma_l\}$ denote the components of $\Gamma(G,S \setminus \{r_2\})$. Each $\Gamma_ l $ has as vertex set some left coset of $H$ and
all are isomorphic to $\Gamma_H = \Gamma(H,S \setminus \{r_2\})$.
Let $C_H$ denote the Hamiltonian cycle in $\Gamma_H$ described in Lemma \ref{le:G(2e,e,2)}.
Since $bad(C_H,r_2)$ is quite large (its value is $8(e-1)$) the procedure used in the proof
of Lemma \ref{le:G(de,e,3)} will fail. Our approach here involves chaining together self-avoiding paths derived from $C_H$ into a large cycle $C$ which spans $4e$ of the
$6e$ coset graphs. This large cycle can
then be combined with spanning cycles in the remaining components using the commutative joining property to obtain the desired result.

The left cosets of $H$ are described as
\begin{align*}
 H(k,1) &= \{(k,b,c\mid\sigma) \in G, \sigma \in \{\sigma_3,\sigma_5\} \},\\
 H(k,2) &= \{(a,k,c\mid\sigma) \in G, \sigma \in \{\sigma_2,\sigma_4\} \},\hbox{ and }\\
 H(k,3) &= \{(a,b,k\mid\sigma) \in G, \sigma \in \{\sigma_0,\sigma_1\} \},
\end{align*}
where $0 \leq k < 2e$. For example, $H = H(0,3)$.

From Lemma \ref{le:G(2e,e,2)}, $C_H = [[r_1,s]^{e-1}],r_1,t]^4$. It is easy  to verify that $(r_1s)^{e-1}r_1t = ts$.  It follows that the
path $Q$ obtained from $C_H \nolinebreak\hspace{-.05em}\raisebox{.6ex}{\scriptsize\bf \#}$
by flipping with respect to $s$ is given by
\[Q = [[r_1,s]^{e-1},r_1,t,s,[[r_1,s]^{e-1},r_1,t]^2,[r_1,s]^{e-1}].\]
If  $Q$ is applied starting at 1 the ending vertex is $tsr_1$. See Figure~\ref{fig:flip3}.

\begin{figure} [b!]
\begin{center}
\mbox
{

\beginpicture
     \setcoordinatesystem units <0.5in,0.5in>

    \setsolid
    \plot -5 1 -4 1 /
    \plot -3 1 0 1 /

    \plot 1 1 3 1 /
    \plot  4 1 7 1 /

    \arrow <6pt> [.2,.67] from -4.5 1 to -4.3 1
    \arrow <6pt> [.2,.67] from -2.5 1 to -2.3 1
    \arrow <6pt> [.2,.67] from -1.5 1 to -1.3 1
    \arrow <6pt> [.2,.67] from -.5 1 to -.3 1
    \arrow <6pt> [.2,.67] from 1.5 1 to 1.3 1
    \arrow <6pt> [.2,.67] from 2.5 1 to 2.3 1
    \arrow <6pt> [.2,.67] from 4.5 1 to 4.3 1
    \arrow <6pt> [.2,.67] from 5.5 1 to 5.3 1
    \arrow <6pt> [.2,.67] from 6.5 1 to 6.3 1

    \arrow <6pt> [.2,.67] from 3.5 1.82 to 3.7 1.82
    \put{$s$} at 3.4 1.6
    \put{$t$} at 1 2.3

    \put{$r_1$} at -1.5 .7
    \put{$t$} at -.5 .7
    \put{$r_1$} at .5 .7
    \put{$s$} at 1.5 .7

    \put{$r_1$} at 6.5 .7
    \put{$s$} at 5.5 .7

    \put{$[r_1,s]^{e-1}$} at -3.3 .7

    \put {$\bullet$} at -5 1
    \put {$\bullet$} at -1 1
    \put {$\dots$} at -3.5 1
    \put {$\bullet$} at -2 1
    \put {$\bullet$} at -1 1

    \put {$\bullet$} at -1 1
    \put {$\bullet$} at 0 1
    \put {$\bullet$} at 1 1
    \put {$\bullet$} at 2 1

    \put {$\dots$} at 3.5 1

    \put {$\bullet$} at 5 1
    \put {$\bullet$} at 6 1
    \put {$\bullet$} at 7 1

     \circulararc 53 degrees from 7 1 center at 3.5 -6

     \setdots
     \setplotsymbol({\Large .})
     \circulararc -57 degrees from -5 1 center at 1 -10

     \plot 0 1 1 1 /

     \setplotsymbol({\tiny -})
     \setsolid

     \endpicture

\caption {\small Adapting the Hamiltonian cycle from Lemma \ref{le:G(2e,e,2)}}
\label{fig:flip3}
\end{center}
\end{figure}

From $t s r_1 r_2=(e-1,1,0\mid\sigma_2)$ we see that
$$\begin{aligned}
(t s r_1 r_2)^{2i} &= (i(2e-2),i,i\mid\sigma_0) \in H(i,3) \text{ and}\\
(t s r_1 r_2)^{2i+1} &= (i(2e-2)+e-1,i+1,i \mid\sigma_2) \in H(i+1,2).
  \end{aligned}
$$
It follows that
$tsr_1r_2$ has order $4e$ and the cycle $[t,s,r_1,r_2]^{4e}$ visits each coset of the form $H(k,2)$ or $H(k,3)$.
If each factor of $[t, s, r_1]$ is replaced by $Q$ the result is a cycle $C$ that spans $4e$ of the $6e$ different coset graphs.
We use the fact that $t$ and $r_2$ commute and complete the argument by showing that any component $\Gamma_l$ disjoint from $C$ contains a spanning cycle $C_l$
such that $C$ and $C_l$ have the commutative joining property with respect to $r_2$.

We first
establish that for any $k$ with $0 \leq k < 2e$ there is an edge $(v,vt)$ in $C$ with $vr_2 \in H(k,1)$.
To accomplish this we observe that
$$(a,b,c\mid\sigma_1) r_2 = (a,b,c\mid \sigma_5) \hbox{ and } (a,b,c\mid \sigma_4) r_2 = (a,b,c\mid \sigma_3)$$
and so it suffices to show that for any $k$ with $0 \leq k < 2e$ there
is an edge $(v,v t)$ in $C$  with $v$ of the form $(k,b,c\mid\sigma_1)$ or $(k,b,c\mid\sigma_4)$.

The path $Q$ contains exactly three edges of the form $(v,vt)$ and the vertex $v$ is one of
\[
(r_1s)^{e-1}r_1,\quad (r_1s)^{e-1}r_1ts(r_1s)^{e-1}r_1 \qquad \text{ or }\quad (r_1s)^{e-1}r_1ts(r_1s)^{e-1}r_1t(r_1s)^{e-1}r_1.
\]
Only the first two of these vertices are adjacent via $r_2$ to a vertex in some $H(k,1)$.
Using $(r_1s)^{e-1}r_1t = ts$ and the fact that all generators are of order two, the two useful vertices are $tst$ and $st$.
The complete collection of edges $(v,vt)$ in $C$ where $v r_2$ is not a vertex in $C$ corresponds to the set of vertices of one of the forms $(tsr_1r_2)^i tst$ or $(tsr_1r_2)^i st$ for $ 0  \leq i < 4e$.
It is convenient to split into the cases where $i$ is odd and where $i$ is even.
For $0 \leq j < 2e$, direct computations produce:
 \begin{align*}
      (tsr_1r_2)^{2j} tst &= (e-2j-1,e+j+1,j \mid \sigma_1),\\
      (tsr_1r_2)^{2j+1} tst &= (-2j-2,j+1,e+j+1 \mid \sigma_4),\\
      (tsr_1r_2)^{2j} st &= (-2j-1,e+j+1,j \mid \sigma_1), \hbox{ and } \\
      (tsr_1r_2)^{2j+1} st &= (e-2j-2,j+1,e+j+1 \mid \sigma_4).
 \end{align*}

The set $\{-2j-2,-2j-1
\mid 0 \leq j < 2e\}$ will contain a complete set of residues modulo $2e$ and, consequently, for any $k$ there is an edge $(v,vt)$ in $C$ where $vr_2 \in H(k,1)$.

We have shown that if $\Gamma_l$ is a coset graph disjoint from $C$ then there is an edge $(v,vt)$ in $C$ and $vr_2$ is a vertex in $\Gamma_l$.
The vertex set of $\Gamma_l$ is a left coset of $H$ so that the cycle $(v r_2)C_H$ is a spanning cycle in $\Gamma_l$.
Vertex transitivity can be used to alter this cycle to obtain a spanning cycle $C_l$ in $\Gamma_l$ containing the edge $(vr_2,vr_2t)$.
It follows that $C$ and $C_l$ have the
commutative joining property with respect to $r_2$ and Proposition \ref{prop:multi-join} applies to complete the proof.
\end{proof}

We have thus established Hamiltonicity in each of the required base cases. The remaining graphs under consideration can be handled by induction to establish our main result.
\begin{theorem}
\label{th:cximprimHam}
If $G=G(de,e,n)$ is an irreducible imprimitive complex reflection group and $S$ is a standard generating set for $G$ (as given in Section \ref{sec:background}), then the (undirected right) Cayley graph $\Gamma(G,S)$ has a Hamiltonian cycle.
\end{theorem}

\begin{proof}
Since $G=G(de,e,n)$ is an irreducible imprimitive complex reflection group, then $de\geq 2$, $n\geq 1$, and $(de,e,n)\neq (2,2,2)$.
When $n=1$ the group is cyclic so $\Gamma(G,S)$ is circulant and has a Hamiltonian cycle.
Lemmas~\ref{le:G(d,1,2)}-\ref{le:G(2e,e,3)} prove the statement for $n=2$ and $n=3$.
Proceed by induction on $n$.
The generating set for $G = G(de,e,n)$ being considered can be written as $S \cup \{r_n\}$ where the subgroup $H$ of $G$ generated by $S$ is isomorphic to $G(de,e,n-1)$, $r_n$ commutes with all but one of the elements of $S$ and that element is of order two.
By induction, there is a Hamiltonian cycle $C_H$ in
$\Gamma(H, S)$.
This cycle can contain no consecutive edge labels both of which fail to commute with $r_n$, i.e., $bad(C_H,r_n) = 0$.
Thus by Proposition~\ref{prop:lifting}, $\Gamma_G$ also contains a Hamiltonian cycle.
\end{proof}

\section*{Acknowledgements}
We thank Dave Morris for helpful conversations.

\section*{References}

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv


text:
R. Kelly Garrett
Associate Professor of Communication, The Ohio State University
Chapter Member: Central Ohio SSN
Media & Public Opinion
Connect with R. Kelly
About R. Kelly
Kelly studies the ways that people communicate and learn about controversial political issues, with an emphasis on online interactions. His research includes the study of "selective exposure", the way that attitudes shape the news individuals consume; "affective polarization", the idea that Americans view those with whom they disagree with increasing animosity; and the dissemination and correction of "misperceptions", views that do no align with the best available evidence.
Fake News is a Symptom— Not the Cause— of Americans' Growing Reluctance to Accept Shared Facts
Key Findings Brief, March 2018
"Facebook's Problem is More Complicated than Fake News," R. Kelly Garrett, The Conversation, November 16, 2016.
"Making Sense of the Scalia Conspiracy Theory," R. Kelly Garrett, The Conversation, February 22, 2016.
"Facebook May Be Biased Against Conservative Stories. But Conservatives May Also Be Biased Against Facebook.," R. Kelly Garrett, US Centre, London School of Economics, May 17, 2015.
"Our Partisan Brains: Exploring the Psychology Behind Denying Science," R. Kelly Garrett (with Erik C. Nisbet), The Conversation, March 12, 2015.
"Americans Don't Live in Partisan News Echo Chambers," R. Kelly Garrett (with Dustin Carnahan and Emily K. Lynch), US Centre, London School of Economics, October 14, 2013.
"A Turn Toward Avoidance? Selective Exposure to Online Political Information, 2004-2008" (with Dustin Carnahan and Emily K. Lynch). Political Behavior 35, no. 1 (2013): 113-134.
Disproves the conventional wisdom that Americans' online news consumption grows steadily more insular. Reveals that individuals who use pro-attitudinal news sites, the more likely they are to use counterattitudinal sites than those who don't.
"The Promise and Peril of Real-Time Corrections to Political Misperceptions" (with Brian E. Weeks). Proceedings of the 2013 Conference on Computer Supported Cooperative Work (2013): 1047-1058.
Shows that embedding factual corrections within an inaccurate news story is less effective than presenting them after a short delay among individuals predisposed to believe the falsehood.
"Driving a Wedge Between Evidence and Beliefs: How Online Ideological News Exposure Promotes Political Misperceptions" (with Brian E.Weeks and Rachel L. Neo). Journal of Computer-Mediated Communication 21, no. 5 (2016): 331-348.
Discusses how using partisan online news makes individuals more likely to believe political falsehoods, even when they know about evidence contradicting those untruths.
"Echo Chambers Online?: Politically Motivated Selective Exposure among Internet News Users" Journal of Computer-Mediated Communication 14, no. 2 (2009): 265-285.
Discusses that, when choosing among online news stories, people are more attracted to information that affirms their viewpoint than they are repelled by information that challenges that viewpoint.
"Partisan Paths to Exposure Diversity: Differences in Pro- and Counterattitudinal News Consumption" (with Natalie Jomini Stroud). Journal of Communication 64, no. 4 (2014): 680-701.
Shows that Democrats and Republicans exhibit different news preferences: Democrats are uniquely attracted to news stories that include pro-attitudinal content, while Republicans have a distinct aversion to one-sided counterattitudinal news. Examines that neither group exhibits a systematic one-sided pro-attitudinal news.
"Implications of Pro- and Counterattitudinal Information Exposure for Affective Polarization" (with Shira Dvir Gvirsman, Benjamin K. Johnson, Yariv Tsfati, Rachel Neo, and Aysenur Dal). Human Communication Research 40, no. 3 (2014): 309-332.
Illustrates that, using partisan news sites that affirm one's political affiliations promotes more polarized attitudes toward other citizens. Demonstrates that those sharing the individual's political orientation are seen more favorably, while those holding a different view are seen more negatively.

redpajama_set_name: RedPajamaCommonCrawl


text:
Heliophanus papyri är en spindelart som beskrevs av Wesolowska 2003. Heliophanus papyri ingår i släktet Heliophanus och familjen hoppspindlar. Inga underarter finns listade i Catalogue of Life.

Källor

Hoppspindlar
papyri

redpajama_set_name: RedPajamaWikipedia


6 Ways to Save Money - Winningback | Shopping and Finance Blog, Reclaim your finances today!
Saving money isn't difficult when you consider all the things that you spend money on. Figuring out what you can cut down on, cut out and negotiate can make the world of difference when it comes to reducing your outgoings.
This is the only real way to see how much you're spending and what you can reduce spending on. The worst bit of a budget is sticking to it, but the best bit is having resolve, sticking to it and then seeing the savings that you're making. If you write down everything you spend your money on, you'll see where you're spending too much or what you don't need any more.
From downgrading your mobile phone plan to switching off your lights when they're not in use, cutting down your bills can be relatively easy. Reconsider all of your providers, from internet to gas and everything in between. Get quotes from competitors. If you find something cheaper, tell your current provider when you call to cancel and you may be able to negotiate something even cheaper.
Being vigilant with your credit card. Pay it all off at the end of each month and you'll begin to build a good credit rating, which will mean good things if you're ever in need of a loan. They can be dangerous if you let yourself spend more than you actually have, as the interest rates on them can be killer.
Buying only the things that you need, as well as shopping at the cheapest supermarket, will mean that you can cut down on the money you spend on food. Stick to the list and you won't spend your money on things that you don't need and don't particularly want either. Shopping online can help enormously with this, as you're not wandering around trying to find the tinned tomatoes and picking up chocolate biscuits because they were on offer.
Just like with your household bills, finding the cheapest insurance deal could save you a great deal. Don't compromise on what you need cover for, but getting quotes from multiple providers such as www.towergateinsurance.co.uk, will mean that you're bound to find a cheaper deal. Using comparison sites can help you compare many providers at once, but remember to check those that aren't on there as they can often be even cheaper. Paying upfront for your insurance (as well as many other services) can save you money in the long run, as providers often add interest on to monthly payments.
While this sounds easier said than done, there are ways to increase your income without a lot of effort on your part. For instance, you could de-clutter your home and sell anything worth anything on eBay. If you can work freelance, then there are many sites on the web where you can earn extra on the side. Perhaps you have a hobby that you could turn into a business, or a talent you could teach.


text:
River Ave. Blues » Kelly Johnson
2014 Season Review: The Perfect Fit Who Didn't Fit
October 20, 2014 by Mike 124 Comments
(Brian Blanco/Getty)
On paper, signing Kelly Johnson to a one-year contract worth $3M last offseason made perfect sense for the Yankees. They had questions at both second and third bases, plus he's a dead pull left-handed hitter who figured to take advantage of Yankee Stadium's short right field porch. When Robinson Cano signed with the Mariners a week later and Alex Rodriguez was eventually suspended for the entire 2014 season, Johnson went from shrewd signing to essential piece.
Johnson, who turned 32 in Spring Training, hit an unsexy yet effective .235/.305/.410 (101 wRC+) with 16 homers and seven steals in 118 games for the Rays last year. He also saw time at the three non-shortstop infield positions as well as left field. That kind of production and versatility would be at an absolutely bargain at $3M. Given his 2012-13 spray chart …
… there was every reason to believe Johnson would hit a few cheap homers in the Bronx and see his offensive numbers tick up a bit. His struggles against left-handers were a concern but there were ways to minimize his exposure to southpaws. Add in the fact that he was very familiar with the AL East after spending part of 2011 and all of 2012 with the Blue Jays before joining the Rays 2013, and Johnson was a damn near perfect fit. The Yankees were wise to jump on him so relatively early in free agency.
Of course, as so many people are eager to point out, baseball is not played on paper or spreadsheets and things don't always go according to plan. It would be really boring if they did. Despite his versatility and left-handed pull power, Johnson did not work out as planned for the Yankees. It took all of three games for him to lose the starting third base job — that had more to do with Yangervis Solarte's early-season performance than Johnson's — and by midseason he had been relegated to full-time bench duty.
The first two weeks of the season actually went quite well for Johnson. He was able to stay in the lineup despite Solarte's dominance because Mark Teixeira's injury created an opening at first base, and he went 10-for-35 (.286) with two doubles, a triple, and three home runs in the team's first 12 games of the season. The three homers came in a five-game span against the Orioles and Red Sox. Johnson played as expected (better, really) for the first two weeks of the season. It was wonderful.
And then it all went south. Johnson went 3-for-26 (.115) in the team's next 12 games and it took a set of back-to-back 2-for-4 games at the end of May to get his season batting line to .217/.286/.409 (93 wRC+) on June 1st. That's not all that far off from his 2013 production, but he cooled off big time following the hot start and the move into Yankee Stadium hadn't help his production as hoped. By the time June rolled around, Johnson was playing sparingly at first and third bases with the occasional start at DH.
(Al Bello/Getty)
A strong two weeks in mid-July — 8-for-27 (.296) with a homer, four walks and zero strikeouts from July 6th through the 21st — wasn't enough to save Johnson's job with the Yankees, so, a few hours before the July 31st trade deadline, he was traded to the rival Red Sox for close friend Stephen Drew. Johnson finished his time in pinstripes with a .219/.304/.373 (91 wRC+) batting line and six homers in 77 games. That includes a .224/.300/.402 (94 wRC+) line with five homers at home and a .213/.308/.340 (86 wRC+) line with one homer on the road.
Johnson spent most of his time with the Yankees at first and third bases, though he see spot duty in both outfield corners and at second base. His defense on the infield corners was pretty terrible and that probably has a lot to do with inexperience. Coming into the season, Johnson had playing only 18 career innings at first base and 118 career innings at third base. All of them came with the Rays last season. The inexperience doesn't absolve him of blame, he misplayed some balls any big leaguer should make, but it's not something we can ignore either.
I do wonder if Johnson would have had more success with the Yankees if they had kept him at his natural second base position. That's where he has spent most of his career and is presumably the most comfortable. Maybe keeping him there would have helped his offense somehow. These guys are only human. Learning a new-ish position is demanding and his game could have suffered elsewhere. This stuff happens all the time all around the league. Oh well. I'm just thinking out loud.
Johnson playing sparingly for the Red Sox (-12 wRC+ in ten games) before being shipped to the Orioles (111 wRC+ in 19 games) in a late-August waiver trade. Baltimore was looking for some extra third base depth following Manny Machado's season-ending knee surgery. He did end up making their postseason roster but only got two at-bats in October. Johnson made a ton of sense for the Yankees coming into the season thanks to his versatility and left-handed pop, but it didn't work out for several reasons and the team moved on at the trade deadline. That's baseball.
Filed Under: Players Tagged With: 2014 Season Review, Kelly Johnson
Yankees send Kelly Johnson to Red Sox for Stephen Drew
July 31, 2014 by Mike 200 Comments
(Dilip Vishwanat/Getty)
For the first time since the Mike Stanley trade in 1997, the Yankees and Red Sox have hooked up for a trade. The Yankees have acquired Stephen Drew and $500k from their division rivals in exchange for Kelly Johnson, the team announced. Brian Cashman told reporters Drew will take over as the team's everyday second baseman.
Drew, 31, has hit a weak .176/.255/.328 (56 wRC+) with four homers in 145 plate appearances this year after signing at midseason. He has been much better of late, hitting .237/.341/.474 (126 wRC+) with two homers since the All-Star break. After the long layoff and the lack of a proper Spring Training, it took Drew a little while to get going with the bat. He is a dead pull left-handed hitter who might be able to take advantage of Yankee Stadium's short right field porch.
The Yankees had interest in Drew in each of the last two offseasons, though he declined to sign with them because of questions about how much he'd play as well as his position with Derek Jeter entrenched at short. Drew has never played a position other than shortstop — literally zero innings somewhere other than short (and DH) at both the big league and minor league level — so the second base experiment might be messy. He could always see time at short whenever Jeter needs a day off, of course.
Johnson, 32, is currently on the disabled list with a groin injury. He hit .219/.304/.373 (88 wRC+) with six homers in 227 plate appearances this season while playing mostly first and third bases. The Yankees signed him to be at least a platoon player at the hot corner, but Yangervis Solarte's season-opening hot streak and Mark Teixeira's injuries forced Johnson to spend a lot of time first base. The signing made perfect sense on paper but it just didn't work out.
Like Johnson, Drew will be a free agent after the season, so this is a swap of rental players and the rearranging of some furniture. Drew is a very good defender at short but we have no idea how he will fare at second base. Brian Roberts, who was designated for assignment today, was giving the team neither offense nor defense in recent weeks, so it won't take much for Drew to be an upgrade. As he did with his other trades this month, Cashman grabbed a potential upgrade at minimal cost. Hard to complain about that.
Filed Under: Transactions Tagged With: Kelly Johnson, Stephen Drew
Injury Updates: Pineda, Roberts, Johnson
(Rob Carr/Getty)
Mark Teixeira returned to the starting lineup and hit a homerun last night after being sidelined for eight days with a mild lower lat strain. That was good to see. Here is another round of injury updates, courtesy of Bryan Hoch, Chad Jennings, and George King.
Michael Pineda (shoulder) threw a 45-pitch simulated game yesterday and it went "really good." He'll begin an official minor league rehab assignment on Sunday. "He will make a start somewhere. Four innings and 60-65 pitches will be his next move. Not exactly sure where it's going to be — they were talking about that today — but it will be a regular game," said Joe Girardi.
Brian Roberts is worn down and will get the next few days off. The 36-year-old has played 91 games this year, his most since 2009. He averaged 48 games played from 2010-13. Being worn down at this point of the season isn't much of a surprise. "He's been beat up pretty good this year physically," said Girardi. "He's dealing with soreness that players have. Legs get beat up, you hit balls off your feet, shins. It's all part of it."
Kelly Johnson (groin) will play in a minor league rehab game or two and is expected to come off the disabled list when eligible next Thursday. Girardi said he may give Johnson more time at second base down the stretch. "It's something I could think about. If we feel there is a need to put him there we will put him there," said the skipper.
Filed Under: Injuries Tagged With: Brian Roberts, Kelly Johnson, Michael Pineda
Injury Updates: Tanaka, Sabathia, Pineda, Tex
July 24, 2014 by Mike 19 Comments
Like one of these guys is still healthy. (Presswire)
Here are some updates are various injured Yankees, courtesy of Chad Jennings, Dan Barbarisi, Bryan Hoch, Brendan Kuty, as well as the team itself.
Masahiro Tanaka (elbow) still has some pain after receiving his platelet-rich plasma injection. "He's improved, but he still feels it on a daily basis. It's not good that he's still feeling it at this stage. (We'll just) go day by day, week by week and adjust accordingly," said Brian Cashman.
CC Sabathia (knee) had his clean-up surgery as scheduled yesterday and everything went "as planned," the Yankees announced. "I don't know if we'll see him. Obviously he's not allowed to travel for a few days, so we'll probably see him when we get back from the road trip," said Joe Girardi.
Michael Pineda (shoulder) was scheduled to throw two innings and 30 pitches in a simulated game today, but it was rained out. He threw two innings inside and will stretch it out to 45-50 pitches in the coming days. If all goes well, Cashman said Pineda would return to the rotation "sometime in August."
The decision whether to place Mark Teixeira (lat) on the disabled list will be made tomorrow. "It's just seeing how he feels after three or four days, and then we'll decide if we think it's going to be in the near future that he would play, or if we're going to need the 15 days. If it's going to be 12, 13, 14 days, it probably make sense to get a player," said Girardi.
Kelly Johnson (groin) has a Grade I strain and is not expected to miss more than the minimum 15 days.
Filed Under: Injuries Tagged With: CC Sabathia, Kelly Johnson, Mark Teixeira, Masahiro Tanaka, Michael Pineda
Yankees place Kelly Johnson on 15-day DL, recall Chris Leroux
The Yankees have placed Kelly Johnson on the 15-day disabled list with a left groin strain, the team announced. Right-hander Chris Leroux was called up from Triple-A Scranton to replace him on the roster. Bruce Billings was designated for assignment to clear a 40-man spot for Leroux.
Johnson left last night's game with what was initially called a cramp, but he went for an MRI that showed the strain. Leroux was scheduled to start for the RailRiders today, so he'll be able to give the Yankees a bunch of innings out of the bullpen if needed following last night's 14-inning marathon. Hopefully the three-man bench, eight-man bullpen setup will only last a few days.
Filed Under: Asides, Injuries, Transactions Tagged With: Bruce Billings, Chris Leroux, Kelly Johnson
Update: Kelly Johnson heading for MRI on groin injury
12:37am: Johnson felt something in his groin and is heading for an MRI. That's never good. Sounds like he'll be out a few days at the very least.
10:20pm: Kelly Johnson exited tonight's game with some sort of injury. He took the field in the top of the 11th before Joe Girardi and the trainer came out to check on him. He tried to run before leaving the game. Replays showed Johnson pulling up lame running out a ground ball in the previous half-inning. Hopefully it's just a cramp. We'll find out soon enough.
Filed Under: Asides, Injuries Tagged With: Kelly Johnson
2014 Midseason Grades: The Infielders
Even though it is not really the halfway point of the season, there is no better time to review the first half than the All-Star break. This week we'll hand out some simple and straightforward grades, A through F, for the catchers, infielders, outfielders, rotation, and bullpen. These grades are totally subjective. We started yesterday with the catchers, now let's move on to the infielders.
Mark Teixeira — Grade B (A+ for Foul Territory)
There were a lot of questions about the infield coming into the season in general, but especially Teixeira. The Yankees' first baseman missed almost all of last season due to a tendon sheath injury in his wrist that eventually required surgery, and wrist surgery can be very problematic even after the player has been cleared to play. Remember, Teixeira started Spring Training late and has still felt soreness during the season. It has caused him to miss a game or two here and there. (His only DL stint was hamstring related.)
Despite that, Teixeira has been the team's most consistent and productive power hitter this summer, coming into the All-Star break with a .241/.341/.464 (120 wRC+) batting line with a team-leading 17 homers. His power output (.222 ISO) is right in line with his last full healthy season (.224 ISO in 2012), which is definitely encouraging after the wrist surgery. Most importantly, he's done most of his damage against right-handed pitchers (130 wRC+), who used to give him the most trouble. Is he Teixeira of old? No, of course not. That guy isn't coming back. But he's returned to his pre-surgery ways and been a much-needed force in the middle of the lineup.
Weirdly enough, the biggest issue for Teixeira this season has been his defense. He's already committed six errors this season, his most since 2004, and while errors are not the best way to evaluate defense, most of them were plays we're used to seeing Teixeira make. I think his scooping at first has been fine. It's the hard-hit balls he used to turn into outs that are now eating him up. I think it's a combination of rust from the lost 2013 season and a decline in his skills. Either way, Teixeira has definitely been a positive for the Yankees this year, especially when you consider he's coming off major surgery.
Brian Roberts — Grade C
There was no way the Yankees were not going to have a massive drop off in production at second base this year. Robinson Cano was the best player at the position last year and has been for several years running, so by definition he is irreplaceable. Roberts was not exactly a popular choice as Cano's replacement given his long injury history and the fact that he wasn't all that productive even when healthy ways. The Yankees love veterans though, especially AL East proven guys.
Roberts has remained remarkably healthy so far this year — he missed a handful of games with a back issue in April, but that's it — while being more than a total zero at the plate. His .241/.306/.376 (87 wRC+) batting line comes with the occasional homer (five), the occasional stolen bases (seven), the occasional walk (8.4%), and always a very long at-bat (4.04 pitches per plate appearance). Roberts has been fine defensively at second if not an asset. He's a perfectly capable stopgap and No. 9 hitter who has been asked to bear more responsibility. Will Roberts hit a wall later in the year after not playing a full season since 2009? I have a hard time thinking his second half will be better than his first, honestly.
Derek Jeter — Grade C
Like Teixeira, Jeter was coming off a major injury. He missed just about all of last season with a series of leg problems, including a twice-fractured ankle. Add in the fact that he is a 39-year-old shortstop — a demographic that is not well-represented throughout history — and things were definitely stacked against the Cap'n coming into 2014.
Jeter's season has been underwhelming statistically but I don't it's worst case scenario stuff. Like I said, a 39-year-old shortstop coming off a major leg injury could have been really, really ugly. Jeter is hitting .272/.324/.322 (80 wRC+) overall, so his power is non-existent, but he does rank third among qualified AL shortstops in OBP and is only five points away from leading. Is it vintage Jeter? Absolutely not. But relative to the league average shortstop (.308 OBP and 87 wRC+), he's been passable.
Defensive is another matter. Jeter's glovework has never been good and at this point he's barely mobile. The old "he makes the plays on the balls he gets to" rhetoric doesn't even apply anymore. He's booted more grounders and made more offline throws this season than I can ever remember. Inside Edge data says he has converted only 46.2% of "likely" plays into outs, which are defined as plays that would be make 60-90% of the time on average. He hasn't make anything tougher than an "even" play (40-60%) either. It's been ugly.
The total package, offense plus defense, has not been good for the Yankees this year. At the same time, I'm generously giving Jeter a C instead of a D or F because he has played better than I expected coming off the ankle injury at his age. Maybe I'm just a giant homer. The Cap'n has not been good this season though, certainly not by his standards, but it could have been much worse given everything that happened last year.
Kelly Johnson — Grade D
The Yankees have put Johnson in a tough spot for most of the year — playing once or twice a week, usually at an unfamiliar position like first or third base — but, at the same time, he knew what he was walking into when he signed as a free agent over the winter. He has hit .214/.299/.380 (87 wRC+) with six homers in 211 plate appearances, including a disappointing 83 wRC+ against righties and an even more disappointing 87 wRC+ at Yankee Stadium. Five of his six long balls have come in the Bronx.
Johnson's defense has been a problem, though again, he has mostly played out of position — he came into the season with only 18 innings at first base and 118 innings at third base. He has spent 199.2 innings at first and 255.1 innings at third this year, committing nine total errors and not looking particularly graceful either. Johnson was a shrewd signing and a wonderful fit for the roster on paper — left-handed hitter with power who can play the three non-shortstop infield positions as well as left field — but it just hasn't worked out halfway through the season.
Yangervis Solarte — Grade B
Man those first eight or so weeks were fun, weren't they? I like to think I'm well-versed in the minor leagues but even I had not heard of Solarte before the Yankees signed him as a minor league free agent over the winter. It goes without saying that no one expected to take over as the starting third baseman for the first eight weeks of the season, during which he hit .299/.368/.458 (128 wRC+) in 229 plate appearances. Solarte was a godsend for a beleaguered offense.
The Solarte Partay came to crashing halt after that, unfortunately. He has hit .111/.238/.130 (10 wRC+!) in 63 plate appearances since, earning him a demotion to Triple-A Scranton. Yangervis has owns a .255/.338/.382 (101 wRC+) line in 288 trips to the plate overall and holy crap, no one expected that. Even if he never hits again, those first eight weeks made the signing more than worth it. That's even considering Solarte's occasionally shaky defense. He was a great story and a tremendously productive player into early-June. His days as a useful MLB player may have already come to an end, but boy did Solarte contribute in a big way when given an opportunity early this season.
Brendan Ryan — Grade C
Giving Ryan two years plus a player option this past offseason definitely flies under the radar as a lolwtf offseason move. I mean, yeah, I get it. Jeter was a major question mark, but geez. Ryan spent the first five weeks of the season on the disabled list with a back injury, and he's nothing more than a no-bat (.235/.273/.255, 43 wRC+ in 55 PA), good but no longer elite glove infielder who plays maybe once a week. It's far from the best use of the roster spot, but the Yankees are stuck with him. It's just a weird fit. Even weirder are all those times Ryan played first base while Jeter manned short. He's fine as the 24th man on the roster. Just a pricey and not at all versatile (in terms of bringing different things to the table) insurance policy for Jeter in his final season.
Zelous Wheeler, Dean Anna, Scott Sizemore — incomplete
These three guys have combined for 61 total plate appearances — Anna has the most at 25 — and have hit a combined .232/.246/.438. Most of the power production comes from Wheeler, who has hit two homers in his 20 plate appearances. He is currently with the team in that revolving door 25th man spot while Sizemore is stashed in Triple-A awaiting an injury. Anna has already been designated for assignment (to make room on the roster for Zelous) and claimed off waivers from the Pirates. I wonder how many more guys will cycle through this role in the second half.
There were some serious concerns about the infield coming into the season. Teixeira and Jeter were huge question marks following their injuries and the same was true of Roberts given his history. Johnson was the sure thing on the infield at the start of camp. The defense has been hideous — Yankees' pitchers have a .258 BABIP on ground balls, the seventh highest in baseball (league average is .244), and even more grounders would sneak through for hits if not for the club's aggressive shifting — and that was fairly predictable.
The infield has, by and large, been more productive than I expected, mostly because Solarte was awesome for a while and Teixeira has shown no lingering issues with the wrist when it comes to raw production. Roberts is the new Lyle Overbay — the best of all the bad players and therefore giving off the appearance of being good — and Jeter's Jeter. He's untouchable. The Yankees have some internal options who may improve the infield, namely Triple-A Scranton second baseman Rob Refsnyder, but either way it's clear they could use some help in the second half. Beefing up third base is an obvious upgrade area.
Filed Under: Players Tagged With: Brendan Ryan, Brian Roberts, Dean Anna, Derek Jeter, Kelly Johnson, Mark Teixeira, Scott Sizmore, Yangervis Solarte, Zelous Wheeler


Files with ts4 file extension can be usually found as MPEG-2 videos recorded by several older DVD recorders.
What is ts4 file? How to open ts4 files?
The ts4 file extension is associated with the MPEG-2 video file format used by some DVD recorders and Home Theaters.
The ts4 file stores video captured in the TS4 file format.
TVersity Player is media player and media server. it is able to stream video to another devices, such as TV, smart-phones, game consoles etc.
TS4 format is viewable in the TVersity Player.
Some multimedia converters may be able to transform these files to other video formats.
and possible program actions that can be done with the file: like open ts4 file, edit ts4 file, convert ts4 file, view ts4 file, play ts4 file etc. (if exist software for corresponding action in File-Extensions.org's database).
Click on the tab below to simply browse between the application actions, to quickly get a list of recommended software, which is able to perform the specified software action, such as opening, editing or converting ts4 files.
Programs supporting the exension ts4 on the main platforms Windows, Mac, Linux or mobile. Click on the link to get more information about TVersity Player for play ts4 file action.
Programs supporting the exension ts4 on the main platforms Windows, Mac, Linux or mobile. Click on the link to get more information about listed programs for import ts4 file action.


text:
Q: I am using Intent.ACTION_OPEN_DOCUMENT_TREE for location . Does it require WRITE_EXTERNAL_STORAGE or any other storage permission?  Intent intent = new Intent(Intent.ACTION_OPEN_DOCUMENT_TREE);
            activity.startActivityForResult(intent,
 1);

I am using above code and letting my users to choose download location. File that user downloads gets stored in that download location. I am also using
DocumentFile.delete();
to delete that file.
In my use cases does WRITE_EXTERNAL_STORAGE permission is required? Does it requires any other storage permisson other than WRITE_EXTERNAL_STORAGE? Because as I can see Intent.ACTION_OPEN_DOCUMENT_TREE can be launched without any permission.

A: No, OPEN_DOCUMENT_TREE requires no runtime permissions - that's kind of the entire point. Since the user is explicitly involved with selecting the folder, the user is completely aware with what directory your app has read/write access to.

redpajama_set_name: RedPajamaStackExchange