\section{Introduction}

Employee attrition is defined as the natural process by which employees leave the workforce – for example, through resignation for personal reasons or retirement – and are not immediately replaced{\color{blue}{\cite{{ref5}}}}. Employee turnover is regarded as
the key issue for all organizations these days, because of its
adverse effects on workplace productivity, and accomplishing
organizational objectives on time {\color{blue}{\cite{{ref6}}}}.  In order for an organization to continually have a higher competitive advantage over its competition, it should make it a duty to minimize employee
attrition Therefore, for the better development of corporation, it is essential for the leader of companies to know the main reasons why their employees choose to leave the company,then take relevant measures to  improve their company's productivity, overall workflow and business performance.

\textbf{Objectives.} In this paper, we aim to select the main
causes that contribute
to an employee’s decision to leave a company, and to be able to predict whether a particular employee
will leave the company  by utilizing machine learning models.

\textbf{Contributions.} Following are the main contributions of this paper:
\begin{itemize}
    \item We select the main factors affecting the employee attrition by using Random Forest, and classify which types of people are more likely to quit by utilizing the K-means Clustering
    \item We represent a given reality in terms of a numerical value  to compare the employee attrition in different categories by utilizing quantitative analysis.

\end{itemize}
The rest of the paper is described below. We present
some related work in Section 2. We interpret data and introduce methodologies in Section 3. We process the original data set and remove some  variables which  are not very correlated with other features in section 4. We implement our machine learning model in Section 5. Finally, we draw a conclusion in section 6.

\section{Related Work}

Alao et al.{\color{blue}{\cite{{ref111}}}} used  decision tree models and rule-sets to develop a predictive model
 that was used to predict new cases of employee attrition. Alduayj et al.{\color{blue}{\cite{{ref222}}}}utilized support victor machine
(SVM) with several kernel functions, random forest and Knearest neighbour (KNN) to predict employee attrition based on their
features and found quadratic SVM scored the highest results. Frye et al.{\color{blue}{\cite{{ref333}}}}applied Principal Component Analysis and classification methods K-Nearest Neighbors and
 Random Forest, finding that Logistic Regression predicts employee quits with the highest accuracy. Yadavet et al.{\color{blue}{\cite{{ref444}}}} provided a framework for predicting the employee churn by analyzing the
employee’s precise behaviors and attributes using classification techniques. Srivastava et al.{\color{blue}{\cite{{ref555}}}}provided a framework for predicting the employee churn by analyzing the
employee’s precise behaviors and attributes using classification
techniques. El-Rayes et al.{\color{blue}{\cite{{ref666}}}} presented a framework
for predicting the employee attrition with respect to voluntary termination employing predictive analytics. Setiawan et al.{\color{blue}{\cite{{ref777}}}} found that eleven variables that have a significant impact on employee attrition.

\section{Data and Methodology}
Employee attrition is the internal data of the company, which is difficult to obtain, and some data has a certain degree of confidentiality, therefore our paper used the data set disclosed by kaggle. The sample size of the data set is 1471, there are 34 feature variables,mainly divided into three types of variables: personal basic information, work experience, attendance rate.This paper explored the relationship between employee’s  characteristics and employee attrition, found Whether characteristics have a great influence on employee attrition. In addition, we used machine learning algorithms to select important features that influenced the employee attrition, and predicted the it. In this paper, we exploited three machine learning algorithms: Decision Tree, and Logistic Regression and k-means clustering.

\subsection{Random Forest}

Random forest is an  learning method used for classification, regression and other tasks, which combines multiple decision trees to select the best result. Random forest corrects the habit of decision trees that rely too much on the training set and improves the accuracy of the model.First, there are randomly selected sub-data sets that are replaced from the original data{\color{blue}{\cite{{ref7}}}}. The elements between the sub-datasets may have the same elements, and the content of each sub-data set is
1
 different. Then use the sub-dataset to construct the sub-decision tree, each decision tree will output a result, you can vote through the output result of the sub-decision tree, and finally get the output result. As shown in Figure {\color{blue}\ref{random forest}}, the data set extracts 4 sub-datasets to construct 4 sub-decision trees, 3 trees voted as A, one sub-decision tree voted as B, and the final output is A.

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Random.jpg}
  \caption{Decision-making process of random forest }
 \label{random forest}
\end{figure}

Random forest is one of the most popular machine learning algorithms. Random forest provides a unique combination of prediction accuracy and model
interpretability among popular machine learning methods. The random sampling
and ensemble strategies utilized in RF enable it to achieve accurate predictions as well as better generalizations {\color{blue}{\cite{{ref8}}}}. In addition, it has a strong explanatory nature. It can directly calculate the importance of each variable. In other words, it is easy to calculate how much each variable contributes to decision-making.
In our research, we build Random Forest model based on Employee Attrition Features.There are 34 employee attributes in the data set, we select randomly k(k<34)  employee attributes to build a decision tree, and create 100 random sub-samples of our dataset with replacement. Each node of each decision tree will be split according to predictor variables so that child nodes are more “pure” (i.e., Gender) in terms of the outcome variable. If the feature of the next child node has appeared in the parent node, the second child node will stop splitting. In the end, each decision tree outputs a result, and the result with the most votes is the final result.

\subsection{Binary Logistic Regression}

Logistic regression analysis can be used to estimate the probability of an event, and it can also analyze the influencing factors of the problem. In medical research, Logistic regression is often used to analyze the risk factors of a certain disease{\color{blue}{\cite{{ref99}}}}. Such as analyzing whether age, smoking, drinking, and diet are risk factors for diabetes. In questionnaire research, Logistic regression is often used to analyze non-scale questions, such as taking the basic background information of the sample as X and purchasing intention as Y to analyze whether gender, age, and  families' socioeconomic conditions affect purchase intention. Among them, binary logistic regression analysis is used most frequently.

\begin{equation}
 logit_(p)= \ln\dfrac {{p(y=1)}}{1-p(y=1)}={\beta}_0+{\beta_1}{x_1}+...+{\beta_n}{x_n}
\end{equation}

Here, employee attrition as the dependent variable y, 0 represents No, 1 represents Yes. Gender, EducationLevel, OverTime, JobLevel and so on as  predictor variables, n=34, ${x_1}$,${x_2}$,..., ${x_{34}}$. ${\beta_0}$, ${\beta_1}$,..., ${\beta_n}$ are coefficients, which represent the influence of the variable on the dependent variable. Whether it is positive or negative, it needs to be explained in conjunction with the corresponding regression coefficient value. If the regression coefficient value is greater than 0, it means a positive influence; otherwise, it means a negative influence for the dependent variable.

\subsection{k-means Clustering }

 The K-means Clustering algorithm is the most commonly used clustering algorithm. The main idea is: given K values and K initial cluster centers, assign each point  to the nearest cluster center, after all the points are allocated, the center point of the cluster is recalculated based on all the points in the cluster (take the average value), updates the center point of the cluster Steps until the center point of the cluster changes very little {\color{blue}{\cite{{ref10}}}}.
 The objective function is:
 \begin{equation}
   J=\sum_{j=1}^{k}\sum_{i=1}^{n}{||x^{(j)}_{i}-c_{j}||^{2}}
 \end{equation}
Where $||x^{(j)}_{i}-c_{j}||$ is the Euclidean distance between $x^{(j)}_{i}$ and $c_{j}$, n is the number of data points in $j^{th}$ cluster, k is the number of cluster centers.
Algorithmic steps for k-means clustering:
$X = {x_{1},x_{2},x_{3},...,x_{n}}$ is the set of data points, and $c={c_{1},c_{2},...,c_{k}}$ is the set of centers.
\begin{enumerate}
    \item Randomly select 'k' cluster centers
    \item Calculate the distance between each data point and cluster centers
    \item Assign the data point to the cluster center whose distance from the cluster center is minimum of all the cluster centers
    \item Recalculate the new cluster center using:

\begin{equation}
       c_{j}=\dfrac{1}{n}\sum_{i=1}^{n}x_{i}
\end{equation}

     \item Recalculate the distance between each data point and new obtained cluster centers
     \item  If no data point was reassigned then stop, otherwise repeat from step (3)

\end{enumerate}

The process of K-means Clustering is shown in Figure \ref{K}.

 \begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{K.jpg}
  \caption{ Clustering  process of K-means Clustering }
 \label{K}
\end{figure}

\section{data process}
In our studies, there are 34 variables, however, some features just have one data level that do not make sense for our research, such as
EmployeeCount, Over18 and StandardHours, and employee number does not have meaning in analyzing resulting so we also deleted these features. In addition, some features are not very correlated with other attributes, we need to remove them from our dataset to improve computing efficiency. We built correlation matrix, which is a table showing correlation coefficients between variables. Each cell in the table shows the correlation between two variables.
 \begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Correlation.png}
  \caption{Correlation Matrix}
 \label{correlation}
\end{figure}

  We can see from Figure {\color{blue} \ref{correlation}}, daily rate, hourly rate and monthly rate are barely correlated with other attributes, while Monthly Income and  job level (0.95), Job level and total working years(0.78), Monthly Income and total working years(0.77) are highly correlated. Therefore we delete  daily rate, hourly rate and monthly rate from dataset.

\section{Model Construction}
In this part, we build machine learning models to select important features that influence the employee attrition and  classify the features to  help us understand the main reason why people left the IBM company.And we will construct the model to predict the employee attrition according to the given data.
\subsection{Feature Selection}
We all may have faced this problem of identifying the related features from a set of data and removing the irrelevant or less important features with do not contribute much to our target variable in order to achieve better accuracy for our model and.Therefore, it is better for us to select important features that influence the employee attrition, and ignore the variables that are not significant in explaining such behavior.

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{feature.jpg}
  \caption{ Important Features }
 \label{feature}
\end{figure}

 From  Figure {\color{blue} \ref{feature}}, Monthly Income, Age, DisatnceFromHome are top 3 important features to indicate whether the employee has a tendency to leave, while marital status married, and female aged 40-50 are less likely to go. Indeed, income is the main cause that people choose to leave the company, which is highly related to people's life quality. More affluent people have more disposable
income and can more easily afford expensive service (such as medical care) and a healthy lifestyle—benefits.So people want to have more money that they intend to leave the current company and find other companies that offer high salaries. And also young people are more likely to want to try different jobs and finally find a job that suits them when they just graduated from universities. Whereas older people prefer a stable life because they already have own families and children, so it is not easy to leave the job. In addition, the distance between the company and home is also the main reason why people quit the current job, they would waste much time commuting. There's mass of social science and public health research on the negative effects of commuting on personal and societal well-being. Longer commutes are linked with increased rates of obesity, high cholesterol, high blood pressure, back and neck pain, divorce, depression and death.

Here, we need to train and test dataset to predict the employee attrition according to the features. We splited the data set into two sets: a training set and a testing set (80\% for training, and 20\% for testing). To better reflect the real situation and avoid the influence of extreme values, we  predicted the employee attrition  for 100 times by utilizing RandomForest Classifier, and recorded the average  accuracy of the test set.  Table {\color{blue} \ref{accuracy}} shows the average accuracy is 0.84561, which means our model fits well.

\begin{table}[hb
\setlength\tabcolsep{3.5pt}
\caption{Prediction Accuracy of Random Forest }
 \label{accuracy}
  \setlength{\tabcolsep}{9mm}{
  \begin{tabular}{cc}
    \toprule
    Times & Accuracy \\
    \midrule
  1& 0.85714 \\
2&0.83673\\
3&0.84353\\
4&0.84693\\
...&...\\
100& 0.85374\\
Average Accuracy&0.84561\\

 \bottomrule
\end{tabular}
}
\end{table}

\subsection{Classification of people}
To distinguish which types of people are more likely to resign, we use K-means clustering to divide the dataset into two categories. The first type is prone to leave, and the other is less likely to quit.

\begin{table}[hb
\setlength\tabcolsep{3.5pt}
\caption{Clustering}
 \label{clustering}
{
  \begin{tabular}{ccc}
    \toprule

  Cluster Type	&	0	&	1	\\
  \midrule
Age	&	44.215152	&	34.813158	\\
Attrition	&	0.1	&	0.178947	\\
DistanceFromHome	&	9.072727	&	9.227193	\\
Education	&	3.039394	&	2.876316	\\
EnvironmentSatisfaction	&	2.693939	&	2.729825	\\
JobInvolvement	&	2.690909	&	2.741228	\\
JobLevel	&	3.684848	&	1.594737	\\
JobSatisfaction	&	2.709091	&	2.734211	\\
MonthlyIncome	&	14060.49394	&	4315.215789	\\
NumCompaniesWorked	&	3.342424	&	2.505263	\\
OverTime	&	0.290909	&	0.280702	\\
...&...&...\\
...&...&...\\

PercentSalaryHike	&	15.066667	&	15.250877	\\
PerformanceRating	&	3.148485	&	3.155263	\\
RelationshipSatisfaction	&	2.781818	&	2.692105	\\
StockOptionLevel	&	0.80303	&	0.791228	\\
TotalWorkingYears	&	21.072727	&	8.444737	\\

 \bottomrule
\end{tabular}
}
\end{table}

We can see from Table {\color{blue}\ref{clustering}} (complete form in appendix table {\color{blue}\ref{coK-mean}}),cluster set 0  represents low attrition, cluster set 1 means high attrition, and older people, high job level, high job satisfaction,high monthly income, more number of companies worked and so forth are less likely to leave.These finding are in line with people's behavior in the real world and previous accounts in feature selection of RandomForest. In last section, we illustrated the relationship between age, monthly income, distance from the company and home, this section, we also find that the number of companies employees worked are related to the probability of  leaving the
corporation. People who have worked in 3-4 companies are less likely to quit because by this time, they have roughly found the direction of employment, and people who have more than four companies indicate that they are unstable and often change jobs. In addition, people who are in the higher the job level, enjoy the higher salary and respect , so they are less likely to leave. While those employees in lower-level positions are often not satisfied with the status quo and want to  seek better job chance. What is more, job satisfaction is also the main cause influencing the employee attrition rate.Intention
to stay on the job is clearly correlated with job satisfaction in such aspects as educational system and environment, income and welfare, leadership and administration.{\color{blue}{\cite{{ref4}}}}.

\subsection{Logistics Regression}
In this section, we exploited the binary logistics regression to predict the relationship between predictors (employee characteristics) and a predicted variable (employee attrition) where the dependent variable is binary (NO:0, YES:1). And we will  compare the differences between each category to help us understand which type of person is more likely to quit (complete regression table can be seen in appendix table {\color{blue}\ref{COlogistics}}).

\begin{table}[hb
\setlength\tabcolsep{3.5pt}
\caption{Regression Result}
 \label{regression}
 \setlength{\tabcolsep}{5mm}{
  \begin{tabular}{ccc}
     \toprule

\quad		&	OR(95\% CI)				&	P-value	\\
\cline{2-3}
Travel$\_$Rarely	&	1	&		\\
Non\-Travel	&	0.361	&		\\
Travel\_Frequently	&	2.411	&	<0.05	\\
\cline{2-3}
Male	&	1	&		\\
Female	&	0.659	&	<0.05	\\
\cline{2-3}
Sales Representative	&	1	&		\\
Healthcare	&	0.160	&		\\
Human Resource	&	4.060	&		\\
Laboratory	&	0.556	&		\\
Manager	&	0.347	&		\\
Manufacturing	&	0.200	&		\\
Research	&	0.200	&		\\
Sales Executive	&	0.484	&	<0.05	\\
\cline{2-3}
Single	&	1	&		\\
Divorced	&	0.304	&		\\
Married	&	0.427	&	<0.05	\\
\cline{2-3}
OverTime	&	0.138	&	<0.05	\\

 \bottomrule
\end{tabular}
}
\end{table}

From Table  {\color{blue}\ref{regression}}, we can see, taking people who rarely travel as the standard 1, employees who travel frequently are 0.361 times more than those to leave the company whereas people who never travel are more than twice. And Women are 0.659 times more than men to go. As for JobRole, taking Sales Representative as the standard 1, employee who who work about Research Science, Laboratory, Manufacturing, Healthcare are not likely to quit, while HumanResource Department has high employee attrition. Then single people are more likely to leave their jobs than married and divorced people.Finally,not surprised, people who usually work overtime would like to leave the company.
To evaluate the logistics regression model, we need to test the accuracy of model in Python, the test result is 0.8843, which means our model fitting is well.

\section{conclusion}
According the above model results, we can know that our finding are in line with people's behavior in the real world and previous studies other scholar did.
We utilized Random Forest and K-means Clustering to select important features that had obvious impact on the employee attrition. Firstly, according to Random Forest results, monthlyincome, age, the number of companies worked are the main reasons why people choose to resign. Then we found older people, high job level, high job satisfaction,high monthly income, more number of companies worked, these kinds of people are not likely to go based on the clustering result of K-means Clustering. However, different people have various intention, we need to do further and detailed research to find qualitative findings by using qualitative analysis. So we exploited the binary logistics regression to compare the difference between people. Our study found that females' attrition was 0.659 times than that of males, married and divorced people were 0.427 and 0.304 times than people who were single, respectively. Besides, the attrition of people who traveled frequently was 2.4 times higher than that of people who rarely traveled. And we also found that employees who work in Human Resource have a higher tendency to leave. Finally, there are other interesting findings in our study:in terms of number of companies worked, people who worked in 2 - 4 companies are less likely to leave, the female attrition rate is less than male after working for six companies , and people who earned Doctor's Degree are almost always having the lowest attrition rate.

To evaluate the model performance, we trained and tested the dataset to predict the employee attrition, split it into two parts(80\% for training, 20\% for testing ), and recorded the test set's accuracy. Random Forest and Logistics Regression accuracy were 0.8456 and 0.8843, respectively, which meant  Logistics Regression fitted better and was more suitable for prediction in our dataset.

We also want to make some suggestions to the company through this research, hoping that they will care more about their employees and improve their job satisfaction. Simultaneously, they must pay more attention to human resources employees because they have very low job satisfaction. Besides, the company should allow employees to have enough time to rest and spend time with their families.There is a general belief that employees who take regular breaks are more productive.


\section{Introduction}
\label{SecIntro}

\noindent
Lanier and Loving gave examples of
big mapping class groups that do not satisfy
the Tits Alternative, and asked whether
the same holds for every
big mapping class group
\cite[Question 6]{LL}.  We show that few if any big mapping
class groups satisfy it:

\begin{theorem}
    \label{ThmMain}
    Suppose $X$ is a surface, possibly nonorientable and
    possibly with boundary. Also suppose that it
     satisfies one of the following:
    \begin{enumerate}
    \item
        \label{CaseGenus}
        $X$ has infinite genus;
    \item
        \label{CasePunctures}
        $X$ has infinitely many punctures;
    \item
        \label{CaseCantor}
        $X$ contains a closed subset homeomorphic to $D^2-C$, where $C$ is
            a  Cantor set in the interior of the $2$-disk.
    \end{enumerate}
    Then its mapping class group $\mathrm{Map}(X)$ does not satisfy the
    Tits Alternative.  That is,

    $\mathrm{Map}(X)$
    has a finitely generated
    subgroup~$\tilde{G}$, which
    contains no nonabelian
    free group and no finite-index solvable
    subgroup.
\end{theorem}

\begin{corollary}
    \label{CorMain}
    Suppose $X$ is a surface of infinite type, with
    only finitely many boundary components.  Then  $\mathrm{Map}(X)$
    does not satisfy the Tits Alternative.
\end{corollary}

For us, every
surface $X$ is connected and second countable, and may have boundary.
When $X$ is non-orientable, its \emph{mapping class group} $\mathrm{Map}(X)$
is defined as the group of self-homeomorphisms of~$X$
that fix the boundary pointwise, modulo isotopies that
fix the boundary pointwise.  When $X$ is orientable we
use the same definition except that the self-homeomorphisms
are required to preserve orientation.
A surface~$X$ has \emph{finite
type} or \emph{infinite type} according to whether its fundamental
group is finitely generated or not.
A \emph{small} resp.\ \emph{big} mapping class group means the
mapping class group of a finite-type resp.\ infinite-type surface.
See \cite{FarbMargalit}
for general background on mapping class groups,
and \cite{AV} for a survey of recent work on big mapping class groups.
Although $\mathrm{Map}(X)$ is a topological group, its topology
will play no role in this paper.

The \emph{Tits Alternative} is a famous property of $\mathrm{GL}_n(k)$
over any field~$k$,
discovered
by Tits \cite{Tits}.
Namely, every finitely generated
subgroup  is either ``big''
(contains
a nonabelian free group)
or ``small'' (contains  a finite-index solvable
subgroup).
The point is that there is no ``medium''.
One expresses this by
saying that $\mathrm{GL}_n(k)$ satisfies the Tits Alternative.
The property makes sense with any
group in place of $\mathrm{GL}_n(k)$, and if it holds then
we say that group satisfies the Tits Alternative.

Determining whether various groups satisfy the Tits Alternative
 is a major
thread in geometric group theory.
For example, it holds
for the outer automorphism group of a finite-rank free group
\cite{BestvinaFeighnHandel1}\cite{BestvinaFeighnHandel2},
and for many Artin groups \cite{MartinPrzytycki}.
It also holds
for small mapping class groups,
in fact Ivanov \cite{Ivanov} and McCarthy \cite{McCarthy} independently
proved that
these groups satisfy a ``strong Tits alternative''.
This is
defined the same way except with solvable
replaced by abelian.

Lanier
and Loving \cite{LL} showed that the mapping class group
of an infinite-type open surface cannot have this stronger
property.  They also gave examples of big mapping
class groups that do not satisfy even the classical Tits alternative.
The first such example, not noted at the time,
is probably due to Funar and
Kapoudjian.  They exhibited a big mapping class
group that contains Thompson's
group \cite[Prop.~2.4]{FK}\cite[Prop.~5.30]{AV}.
Further examples come from the work of
Aougab, Patel and Vlamis \cite{APV}, who constructed
surfaces~$X$ such that  every countable
group embeds in~$\mathrm{Map}(X)$.

The key idea in the proof of  Theorem~\ref{ThmMain} is
to construct $\tilde{G}$
together with a surjection $\tilde{G}\to G$, where $G$ is
Grigorchuck's group.
We do this in such a way that the kernel is abelian, which
allows us
to transfer to~$\tilde{G}$ the fact
that $G$ does not satisfy the Tits
Alternative.
We review the essential properties of~$G$ in Section~\ref{SecGrigorchuk}.
Section~\ref{SecCantorSet} gives our
construction in case \eqref{CaseCantor} of the theorem, and Section~\ref{SecPuncturesOrHandles}
gives it for the other two cases.  Also see Section~\ref{SecPuncturesOrHandles} for
the definition of a puncture.  Section~\ref{SecMainTheorem}
shows that these three cases
are enough for Corollary~\ref{CorMain}, and makes a few remarks
about the cases left open.

We are grateful to Lanier and Loving for helpful correspondence
and discussions, for many references,
and for asking the question that inspired this work.

\section{Grigorchuk's group}
\label{SecGrigorchuk}

\noindent
In this section we recall Grigorchuk's famous group
and some of its many remarkable properties;
see \cite{Grigorchuk} for background.
The properties we need are that
it is a group of automorphisms of a rooted
binary tree, and is
finitely generated, infinite and torsion.
Sadly,
we do not use its most fascinating property, that it
has intermediate growth.

We define $T$ as the tree whose vertices are the finite
binary
words (sequences in $\{0,1\}$).
We indicate the empty
word by $\emptyset$.
The edges of $T$ are the following:
each word $w$ is joined to $w0$ and $w1$, which are called
the left and right \defn{children} of~$w$ respectively.
The $n$th
\defn{bit} of~$w$ means the $n$th term of the sequence~$w$.
This only makes sense when $w$ has at least~$n$ terms.

Grigorchuk's group $G$ is defined as the subgroup of $\mathop{\mathrm{Aut}}\nolimits(T)$
generated by four specific transformations $a,b,c,d$.  Each of these
fixes the root $\emptyset$ of~$T$.  At other vertices the definitions
are recursive, expressed in terms of an arbitrary word $w$
(possibly empty):
\begin{center}
    \setlength{\tabcolsep}{0pt}
    \begin{tabular}{rlrlrlrl}
        $a(0w)$&${}=1w$
        &
        \qquad
        $b(0w)$&${}=0a(w)$
        &
        \qquad
        $c(0w)$&${}=0a(w)$
        &
        \qquad
        $d(0w)$&${}=0w$
        \\
        $a(1w)$&${}=0w$
        &
        $b(1w)$&${}=1c(w)$
        &
        $c(1w)$&${}=1d(w)$
        &
        $d(1w)$&${}=0b(w)$
    \end{tabular}
\end{center}

Flipping a bit in a word means changing that bit from $0$ to~$1$
or vice-versa.  So  $a$ acts by flipping
the first bit of  each nonempty word.
We can also describe $b,c,d$ in terms of bit-flipping.  Namely, $b$ acts on a word~$w$ by
flipping the bit after the first $0$ in~$w$, just if the number of
initial $1$'s in~$w$ is $0$ or~$1$ mod~$3$.  (If $w$ has no
$0$'s, or no bits after its first~$0$, then $b$ fixes~$w$.)
For $c$ we use the same definition but with ``$0$ or~$1$'' replaced by
``$0$ or~$2$'', and similarly for $d$ using
``$1$ or~$2$''.
An induction justifies these descriptions,
pictured  in Figure~\ref{FigGrigorchuk}.

\def2{2}
\def.22{.22}
\definecolor{treegray}{gray}{.8}%
\def\shadedtriangle#1#2{%
    \fill[treegray](#1,#2
    --(-.22+#1,-2+#2
    --(.22+#1,-2+#2
    --cycle
    ;}
\def\noderadius{1.5pt}%
\def\leftsubtreefixed#1#2{%
    \fill(#1,#2)circle(\noderadius);
    \shadedtriangle{-1+#1}{-1+#2}

    \draw[thick](#1,#2)--(-1+#1,-1+#2)
    --(-1-.22+#1,-1-2+#2)
    --(-1+.22+#1,-1-2+#2)--(-1+#1,-1+#2)
    ;}
\def2{2}
\def.28{.28}
\def\swapheight{2}
\def6{6}
\def\swappedtriangles#1#2{%
    \shadedtriangle{-.28+#1}{-2+#2}
    \shadedtriangle{.28+#1}{-2+#2}

    \draw[->](#1,-\swapheight+#2) arc (-90:-90+6:\swapheight);
    \draw[->](#1,-\swapheight+#2) arc (-90:-90-6:\swapheight);

    \draw[thick](-.28+#1,-2+#2
    --(-.28+.22+#1,-2-2+#2
    --(-.28-.22+#1,-2-2+#2
    --(-.28+#1,-2+#2
    --(#1,#2
    --(.28+#1,-2+#2
    --(.28+.22+#1,-2-2+#2
    --(.28-.22+#1,-2-2+#2
    --(.28+#1,-2+#2
    ;}
\def\leftsubtreeswaps#1#2{%
    \fill(#1,#2)circle(\noderadius)
    \fill(-1+#1,-1+#2)circle(\noderadius)
    \draw[thick](0+#1,0+#2)--(-1+#1,-1+#2)
    \swappedtriangles{-1+#1}{-1+#2}%
    }
\def\rightedge{%
    \draw[thick](0,0)--(6.2,-6.2);
    \draw[thick,dashed](6.1,-6.1)--(7.2,-7.2);
    }
\def.44cm{.44cm}
\def.22cm{.22cm}
\begin{figure}%

    \begin{tikzpicture}[x=.44cm,y=.22cm]

        \draw[white](0,0)--(0,-7-2-2);
        \fill(0,0)circle(\noderadius);
        \swappedtriangles{0}{0}
        \node at (0,-6) {$a$};
    \end{tikzpicture}
    \kern10pt

    \begin{tikzpicture}[x=.44cm,y=.22cm]

        \draw[white](2,0)--(2,-7-2-2);
        \rightedge
        \leftsubtreeswaps{0}{0}%
        \leftsubtreeswaps{1}{-1}%
        \leftsubtreefixed{2}{-2}%
        \leftsubtreeswaps{3}{-3}%
        \leftsubtreeswaps{4}{-4}%
        \leftsubtreefixed{5}{-5}%
        \leftsubtreeswaps{6}{-6}%
        \node at (3,-1) {$b$};
    \end{tikzpicture}
    \kern-10pt

    \begin{tikzpicture}[x=.44cm,y=.22cm]

        \draw[white](2,0)--(2,-7-2-2);
        \rightedge
        \leftsubtreeswaps{0}{0}%
        \leftsubtreefixed{1}{-1}%
        \leftsubtreeswaps{2}{-2}%
        \leftsubtreeswaps{3}{-3}%
        \leftsubtreefixed{4}{-4}%
        \leftsubtreeswaps{5}{-5}%
        \leftsubtreeswaps{6}{-6}%
        \node at (3,-1) {$c$};
    \end{tikzpicture}
    \kern-10pt

    \begin{tikzpicture}[x=.44cm,y=.22cm]

        \draw[white](2,0)--(2,-7-2-2);
        \rightedge
        \leftsubtreefixed{0}{0}%
        \leftsubtreeswaps{1}{-1}%
        \leftsubtreeswaps{2}{-2}%
        \leftsubtreefixed{3}{-3}%
        \leftsubtreeswaps{4}{-4}%
        \leftsubtreeswaps{5}{-5}%
        \leftsubtreefixed{6}{-6}%
        \node at (3,-1) {$d$};
    \end{tikzpicture}
    \caption{Generators for Grigorchuk's group~$G$.  Each $2$-headed
    arrow represents the
    bodily exchange of the two indicated subtrees, drawn as shaded triangles.
    The other shaded triangles indicate pointwise-fixed subtrees.}
    \label{FigGrigorchuk}
\end{figure}

If $g\in\{a,b,c,d\}$ fixes a vertex~$v$ but exchanges the children
of~$v$, then we call $v$ a \defn{swap vertex} of~$g$.
One can also define the swap vertices
as the boundary points
of the fixed-point set
in~$T$.
The only swap vertex of~$a$ is $\emptyset$.  The swap vertices
of~$b$ are the words $1\cdots10$, where the number of $1$'s is $0$ or~$1$ mod~$3$.
And similarly
for $c$ resp.\ $d$, with ``$0$ or~$1$'' replaced by ``$0$ or~$2$'' resp.\ ``$1$ or $2$''.

\begin{lemma}
    \label{LemGrigorchuk}
$G$ is not virtually solvable, and contains no nonabelian free group.
\end{lemma}

\begin{proof}
    The second claim follows from the fact that $G$ is a torsion group.
    For the first, suppose $G$ contains a solvable subgroup~$F$ of finite
    index.  Having finite index in the finitely generated group~$G$,
    $F$ is also finitely generated.  Every finitely generated solvable torsion
    group is finite.  (The abelianization
    is finite, so
    the derived subgroup is finitely generated, hence finite
    by induction on solvable length.)  So $F$ is finite, which forces~$G$
    to be finite, which it is not.
\end{proof}

\section{If \texorpdfstring{$X$}{X} contains \texorpdfstring{$D^2-\hbox{(Cantor set)}$}{a disk minus a Cantor set}}
\label{SecCantorSet}

\noindent
In this section we suppose that $X$ has a closed subset
homeomorphic to $D^2-C$,
where $D^2$ is the $2$-disk and $C$ is a Cantor
set in the interior of $D^2$.
We will
construct a subgroup $\tilde{G}$ of $\mathrm{Map}(X)$, supported on~$D^2-C$,
which is not virtually solvable and contains no nonabelian free
group.
The idea is to interpret
the generators
of Grigorchuk's group~$G$ as
automorphisms
of~$X$,
and define $\tilde{G}$ as the subgroup of $\mathrm{Map}(X)$ generated by
the mapping classes represented by these automorphisms.

We will work with the following  description of $D^2-C$ as an identification
space, obtained by gluing pairs of pants together in the pattern of the
tree~$T$.
Fix
a pair of pants~$P$, meaning a sphere
minus the interiors of three pairwise disjoint closed disks.
We suppose that the components of $\partial P$
are called (in some order)
the waist and the left and right cuffs of~$P$.
We fix a self-homeomorphism $\sigma$ (for \emph{s}wap)
of $P$, which fixes the waist pointwise and exchanges the cuffs,
such that $\sigma^2$ is the identity on each cuff.
We choose a homeomorphism from the waist to~$S^1$.  We choose
homeomorphisms from the cuffs to~$S^1$
which are compatible with each other,
in the sense that
they are exchanged by~$\sigma$.

We define $W$ (for binary \emph{W}\kern-.15em ords) as the set of vertices of~$T$,
equipped with the discrete topology.  We equip $P\times W$ with the product topology.
For each $w\in W$ we abbreviate $P\times\{w\}$ as~$P_w$.
We transfer  our labeling (as waist or left/right cuff)
of the components of~$\partial P$
to those of~$\partial P_w$.

We define an equivalence relation~$\sim$ on $P\times W$ by
gluing the left resp.\ right cuff of each $P_w$ to the waist
of~$P_{w0}$ resp.\ $P_{w1}$.  Formally, we
declare that
for each $w\in W$ we have $(l,w)\sim(l',w0)$ and $(r,w)\sim(r',w1)$,
where $l$ resp.\ $r$ lies in the left resp.\ right cuff of~$P$,
and $l'$ resp.\ $r'$ is the corresponding point on the waist of $P$.
(We fixed homeomorphisms from the waist and  cuffs to~$S^1$.
Combining them
gives
homeomorphisms from the
cuffs to the waist, which we take as the definitions of $l\mapsto l'$
and $r\mapsto r'$.)
We write $X_\emptyset$ for $(P\times W)/{\sim}$, equipped with the
quotient space topology.  It is standard that $X_\emptyset\iso D^2-C$, so
we regard $X_\emptyset$ as a subsurface of~$X$.

The curious notation $X_\emptyset$ is a special case of the following more general
notation $X_w$, useful for
referring to subsurfaces.
If $w\in W$ then we define $W_{\!w}$ as the set of binary words
having $w$ as a prefix.  Equivalently, it consists of~$w$ and
the vertices of~$T$
that lie below~$w$.  We define $X_w$ as $(P\times W_{\!w})/{\sim}$.
If is easy to see that if $x\in W_{\!w}$ then $P_x\to P\times W_{\!w}\to X_w\to X_\emptyset$
is injective.  So we will regard all $P_x$ and $X_w$ as subsets
of~$X_\emptyset\subseteq X$.  In particular,
$X_w$ is a subsurface of~$X$
bounded by the waist of~$P_w$.

Now suppose $g\in\{a,b,c,d\}\subseteq G$.  We will define an
automorphism $\hat{g}$
of $X$ that is supported on~$X_\emptyset$.
We define it in terms of an automorphism of $P\times W$ that respects~$\sim$.
Namely, if $p\in P$ and $w\in W$, then
\begin{equation}
    \label{EqDefnOfghat}
    \hat{g}(p,w)=
    \begin{cases}
        (\sigma(p),w)&\hbox{if $w$ is a swap vertex of~$g$}
        \\
        (p,g(w))&\hbox{otherwise.}
    \end{cases}
\end{equation}
After checking that this
respects~$\sim$, we may regard $\hat{g}$ as an automorphism of~$X$.

\begin{figure}
\includegraphics[width=4.8in,trim=130 45 60 120,clip=true]{Basictrick.pdf}
    \caption{Our construction of~$\hat{g}$.  Here $g$ is one of
    Grigorchuk's generators $a,b,c,d$, and
    the surface shown represents $X_w\subseteq X$,
    where $w\in W$ is a swap vertex of~$g$.  We define $\hat{g}$ (on $X_w$) as
    the end result of the pictured isotopy in~$\mathbb{R}^3$.  See the text for details.}
    \label{FigTheTrick}
\end{figure}

A visual version of this construction, entirely optional, appears
in Figure~\ref{FigTheTrick}, which shows $X_w$ for $w$ a swap vertex of~$g$.
The same construction should be carried out simultaneously for every
swap vertex.
The figure shows four frames of an isotopy of $X_w$ inside~$\mathbb{R}^3$,
whose time~$1$ map we take as the definition of~$\hat{g}$.  Although
$X_w$ is the union of infinitely many pairs of pants, we have only
drawn enough of them to illustrate the idea.  You should imagine
attaching another $8$ pairs of pants on the left, then attaching
$16$ more pairs, then another~$32$, and so on,
limiting to the Cantor set which is the end space of $X_w$.
The top right pair of pants  is~$P_w$,
and we imagine it is
made of rubber, deforming as needed
to accomodate the motion
of  the surfaces $X_{w0}$
and $X_{w1}$ attached to its cuffs, which are made of steel.
The isotopy moves $X_{w0}$ and~$X_{w1}$ rigidly
(ie, by translations) until they trade places.
Strictly speaking,
$X_{w0}$ and $X_{w1}$ should appear identical, so that the time~$1$
map of the isotopy is a self-map of the pictured surface.
But we have drawn them slightly differently,
so the reader can follow their motions more easily.  It is easy
to see that the restriction of $\hat{g}^2$ to~$P_w$ is
(isotopic to) the product of
the left-handed Dehn twist around the waist and
the right-handed Dehn twists around the cuffs.

Now we return to the formal development.
We define $\tilde{a},\tilde{b},\tilde{c},\tilde{d}\in\mathrm{Map}(X)$
as the mapping classes of $\hat{a},\hat{b},\hat{c},\hat{d}$, and
\begin{align*}
    \hat{G}{}=\gend{\hat{a},\hat{b},\hat{c},\hat{d}}\subseteq\mathrm{Homeo}(X)
    \qquad
    \tilde{G}{}=\gend{\tilde{a},\tilde{b},\tilde{c},\tilde{d}}\subseteq\mathrm{Map}(X)
\end{align*}
By construction, $\hat{a},\hat{b},\hat{c},\hat{d}$
permute the $P_w\subseteq X$ in the
same way that $a,b,c,d\in G$
permute the vertices~$w$ of~$T$.
It follows that $\hat{a},\hat{b},\hat{c},\hat{d}$
permute the ends of $X_\emptyset$ the same way that $a,b,c,d$
permute the ends of $T$.  The same holds with
$\tilde{a},\ldots,\tilde{d}$ in place of $\hat{a},\dots,\hat{d}$,
because the action of $\mathrm{Homeo}(X)$ (or $\mathrm{Homeo}^+(X)$ if $X$ is orientable)
on the ends of~$X$ factors
through $\mathrm{Map}(X)$.
Also, $\tilde{G}$ fixes every end of $X$
not coming from~$X_\emptyset$.
We have shown that the image of~$\tilde{G}$, under the
action of $\mathrm{Map}(X)$ on the ends of~$X$, is isomorphic to~$G$.

\begin{lemma}
    \label{LemCantorAbelianKernel}
    The surjection $\tilde{G}\to G$ has abelian kernel.
\end{lemma}

\begin{proof}
    Let $U$ be the union of a family of mutually disjoint annular neighborhoods
    of the waists of the $P_w$, with $w$ varying over~$W$.
    We claim that every $\alpha\in\hat{G}$,
    that acts trivially on the end space of~$X$, is
    supported on~$U$ (up to isotopy).
    Given this, it follows that the
    kernel of $\tilde{G}\to G$ lies in the image of $\mathrm{Map}(U)\to\mathrm{Map}(X)$.
    Then the lemma follows from the fact
    that $\mathrm{Map}(U)$ is a direct product
    of copies of~$\mathbb{Z}$.

    Now we prove the claim.
    Because $\alpha$ permutes the $P_w$, and acts trivially on the ends
    of~$X_\emptyset$, it sends each $P_w$ to itself.
    Considering their intersections
    shows that $\alpha$
    preserves the waist of every~$P_w$.
    After an isotopy supported in~$X_\emptyset$
    and preserving every~$P_w$, we may
    suppose $\alpha$ fixes each waist pointwise.
    The mapping class group
    of a pair of pants is generated by the Dehn twists around its
    boundary components.
    Applying this separately to each~$P_w$ shows that $\alpha$
    is isotopic to an automorphism of~$X$ that is supported in~$U$.
\end{proof}

\begin{lemma}
    \label{LemSolvableKernel}
    Suppose $f:\tilde{G}\to G$ is a surjection of groups with solvable kernel.
    Then
    \begin{enumerate}
        \item
            \label{ItemVirtuallySolvable}
            $\tilde{G}$ is virtually solvable if and only if~$G$ is.
        \item
            \label{ItemContainsNonabelianFree}
            $\tilde{G}$ contains a nonabelian free group if and only if~$G$ does.

    \end{enumerate}
\end{lemma}

\begin{proof}
    \eqref{ItemVirtuallySolvable}
    Obvious.
    \eqref{ItemContainsNonabelianFree}
    First suppose $G$ contains a subgroup freely generated by two elements $x,y$,
     and choose any lifts $\tilde{x},\tilde{y}$ of them in~$\tilde{G}$.
     These lifts satisfy no nontrivial relations,
    because if they did then $x,y$  would also.
    So $\tilde{x},\tilde{y}$ generate a nonabelian free subgroup of~$\tilde{G}$.
    Now suppose $\tilde{G}$ contains a nonabelian free group~$\tilde{F}$.  Being nonabelian
    and free, $\tilde{F}$ lacks normal solvable subgroups, so it meets $\mathop{\mathrm{Ker}}\nolimits(f)$
    trivially.
    Therefore $f(\tilde{F})\iso\tilde{F}$ is a  nonabelian free subgroup of~$G$.
\end{proof}

\begin{lemma}
    \label{LemCantorTitsAlternativeFails}
    With $X$ as above, $\mathrm{Map}(X)$ does not satisfy the Tits alternative.
\end{lemma}

\begin{proof}
    It is enough to show that $\tilde{G}\subseteq\mathrm{Map}(X)$ is not virtually solvable
    and contains no nonabelian free group.  By
    Lemmas \ref{LemCantorAbelianKernel}
    and \ref{LemSolvableKernel} it is enough to
    prove this with $G$ in place of~$\tilde{G}$. We did this
    in Lemma~\ref{LemGrigorchuk}.
\end{proof}

\section{If \texorpdfstring{$X$}{X} has infinitely many handles or punctures}
\label{SecPuncturesOrHandles}

\noindent
In this section we consider a surface $X$ with infinite
genus, or infinitely many punctures.
Again we will build
a subgroup~$\tilde{G}$ of $\mathrm{Map}(X)$ that is not virtually solvable and
contains no nonabelian free group.
The method is a variation on the previous section.
We will focus on the
infinite-genus case, and then modify the
argument for the case of infinitely many punctures.

Suppose $X$ is a surface with infinite genus.  Take
$X_1$ to be a compact subsurface with genus~$2$ and one boundary component.
Then take $X_2$ to be a compact subsurface of $X-X_1$ with genus~$4$
and one boundary component.  Then  take
$X_3$ to be a compact subsurface of $X-(X_1\cup X_2)$ with genus~$8$
and one boundary component.  Continuing in this
fashion, we obtain an infinite
sequence $X_n$ of mutually disjoint compact subsurfaces
of~$X$, where
$X_n$ has genus~$2^n$ and one boundary component.
As suggested by Figure~\ref{FigPantsAndFeet},
we express each $X_n$ as
the union of $2^n-1$ pairs of pants, arranged like
a binary tree, and $2^n$ handles.

\begin{figure}
\includegraphics[width=4.8in,trim=330 420 200 420,clip=true]{manyfeet2.pdf}
    \caption{The subsurfaces $X_1,X_2,X_3,X_4,\dots$ of~$X$.}
    \label{FigPantsAndFeet}
\end{figure}

To express this precisely, recall
$W$, $P$ and $P_w$ (with $w\in W$) from
Section~\ref{SecCantorSet}.
For each integer~$n$ we write $W_n\subseteq W$ for the set of
binary words of length~$n$, $W_{\!<n}$ for those of length${}<n$,
and $W_{\!\leq n}$ for those of length${}\leq n$.

We also fix a compact surface $S$ (for \emph{S}hoe)
with genus~$1$
and one boundary component.  We will call $\partial S$ the rim of~$S$;
a shoemaker would say collar, but that already has
a meaning in topology.
We fix a homeomorphism from the rim to the circle~$S^1$.

For each~$n\geq1$, we identify $X_n$ with the quotient of
$(P\times W_{\!<n})\cup(S\times W_n)$ by the following equivalence
relation~$\sim$, similar to the one in
Section~\ref{SecCantorSet}.  We abbreviate $S\times\{w\}$
as $S_w$, for each $w\in W_n$.  We refer to the $S_w$ as the \defn{shoes}.  First,
for each $w\in W_{\!<n-1}$, we glue the cuffs of
$P_w$ to the waists of $P_{w0}$ and $P_{w1}$.  Formally,
we
declare that $(l,w)\sim(l',w0)$
and $(r,w)\sim(r',w1)$, where $l$ resp.\ $r$ lies in the left
resp.\ right cuff of~$P$, and $l'$ resp.\ $r'$ is the corresponding
point on the waist of~$P$.  Second, for each $w\in W_{n-1}$
we glue the cuffs of $P_w$ to the rims of $S_{w0}$ and $S_{w1}$.
Formally, we declare that
$(l,w)\sim(l',w0)$ and $(r,w)\sim(r',w1)$, where
$l,r$ are as before, but now $l',r'$ are the corresponding
points on the rim of~$S$.

For each $n\geq1$, and each $w\in W_{\!<n}$, we have introduced a
subsurface $P_w$ of~$X_n$.  Since all the $X_n$ lie in~$X$,
we have introduced infinitely many subsurfaces of~$X$, all called~$P_w$.
To distinguish them when necessary, we write $P_{n,w}$ for
the one that lies in~$X_n$.  The same issue does not arise for
the shoes $S_w$: if $w\in W$ has length~$n$,
then only $X_n$ contains $S_w$.

For $g\in\{a,b,c,d\}\subseteq G$, we now define an automorphism~$\hat{g}$
of~$X$.  It is the identity outside the $X_n$, and for each fixed $n$ we
define $\hat{g}$ on~$X_n$ as follows.  The idea is to act on $X_n$
``in the same way that $g$ acts on the top $n+1$ levels of the tree~$T$''.
Formally, we define $\hat{g}$ as an automorphism of
$(P\times W_{\!<n})\cup(S\times W_n)$ that respects~$\sim$.
For each $w\in W_{\!<n}$ we define $\hat{g}$ on $P_w$
by \eqref{EqDefnOfghat}.
And for $w\in W_n$ we define
$\hat{g}$ on $S_w$ by $\hat{g}(p,w)=(p,g(w))$.  After checking that
this respects~$\sim$, we may regard $\hat{g}$ as defined on~$X_n$.
This completes the construction of $\hat{g}\in\mathrm{Homeo}(X)$.
If $X$ is orientable then clearly $\hat{g}$ lies in $\mathrm{Homeo}^+(X)$.

We define $\tilde{a},\tilde{b},\tilde{c},\tilde{d}\in\mathrm{Map}(X)$
as the mapping classes of $\hat{a},\hat{b},\hat{c},\hat{d}$, and
\begin{align*}
    \hat{G}{}=\gend{\hat{a},\hat{b},\hat{c},\hat{d}}\subseteq\mathrm{Homeo}(X)
    \qquad
    \tilde{G}{}=\gend{\tilde{a},\tilde{b},\tilde{c},\tilde{d}}\subseteq\mathrm{Map}(X)
\end{align*}

\begin{lemma}
    \label{LemGenusSurjectionToG}
    The image of $\tilde{G}$ in $\mathop{\mathrm{Aut}}\nolimits(H_1(X))$ is isomorphic to~$G$.
\end{lemma}

\begin{proof}
    Because $\hat{G}$ fixes $X-\bigcup_n X_n$
    pointwise, it acts trivially on the homology classes
    supported there.  So it is enough to work out the action
    of~$\tilde{G}$ on
    \begin{equation*}
        H_1\bigl(\bigcup_{n\geq1} X_n\bigr)
        =
        \bigoplus_{n\geq1} H_1(X_n)
        =
        \bigoplus_{n\geq1}\, \bigoplus_{w\in W_n} H_1(S_w)
        =
        \bigoplus_{w\in W-\{\emptyset\}}\kern-.8em H_1(S_w)
    \end{equation*}
    By construction, $\hat{G}$ permutes the shoes, hence
    the summands on the right.  In particular, an element
    of $\hat{G}$ that preserves a summand $H_1(S_w)$ must carry
    the corresponding shoe $S_w$ to itself.
    Furthermore, the definition of the generators of~$\hat{G}$ on the shoes
    implies: an element of $\hat{G}$ that preserves some~$S_w$ must
    act trivially on it.  Therefore: any element of $\hat{G}$,
    that preserves every summand $H_1(S_w)$, must act trivially on
    every $S_w$, hence trivially on~$H_1(X)$.

    Another way to say this is that the image of $\hat{G}$ in $\mathop{\mathrm{Aut}}\nolimits(H_1(X))$
    is the same as the image of $\hat{G}$ in the group of permutations of

    the shoes.
    By construction, $\hat{a},\hat{b},\hat{c},\hat{d}$
    permute the shoes in the
    same way that $a,b,c,d\in G$ permute the words $w\in W-\{\emptyset\}$.
    So the image of $\hat{G}$ in $\mathop{\mathrm{Aut}}\nolimits(H_1(X))$ is a copy of~$G$.
    The action on $H_1(X)$ factors through $\mathrm{Map}(X)$, so the
    same is true with $\tilde{G}$ in place of $\hat{G}$.
\end{proof}

\begin{lemma}
    \label{LemGenusAbelianKernel}
    The surjection $\tilde{G}\to G$ has abelian kernel.
\end{lemma}

\begin{proof}
    We will write $f$ for the surjection $\hat{G}\to G$.
    We must show that the image of $\mathop{\mathrm{Ker}}\nolimits(f)$ in~$\tilde{G}$ is abelian.
    So suppose $\alpha\in\mathop{\mathrm{Ker}}\nolimits(f)$.  The previous proof shows that
    $\alpha$ acts trivially on every shoe~$S_w$.
    Together with the fact that $\alpha$ permutes the $P_{n,w}$,
    this shows that $\alpha$ preserves  every $P_{n,w}$.

    From here one can follow
    the proof of Lemma~\ref{LemCantorAbelianKernel}.  We take
    $U$ to be the union of disjoint annular neighborhoods of
    the waists of the $P_{n,w}$ (with $n\geq1$ and $w\in W_{\!<n}$) and
    the rims of the $S_w$ (with $w\in W-\{\emptyset\}$).
    Arguing as for Lemma~\ref{LemCantorAbelianKernel} shows that
     $\alpha$ is isotopic
    to a homeomorphism supported on~$U$.
    Because $\mathrm{Map}(U)$ is abelian, it follows that $\mathop{\mathrm{Ker}}\nolimits(f)$ has
    abelian image in~$\tilde{G}$.
\end{proof}

\begin{lemma}
    \label{LemGenusTitsAlternativeFails}
    The mapping class group of an infinite-genus surface
    does not satisfy the Tits Alternative.
\end{lemma}

\begin{proof}
    Mimic the proof of Lemma~\ref{LemCantorTitsAlternativeFails},
    using Lemma~\ref{LemGenusAbelianKernel} in
    place of Lemma~\ref{LemCantorAbelianKernel}.
\end{proof}

To deal with punctures in place of handles,
we first define punctures.  Let $E$ be the end space of~$X$;
we equip $X\cup E$ with
its standard topology.
For us, A \defn{puncture} of~$X$ means an end $e$ for which
there exists an embedding of the $2$-disk into $X\cup E$, that sends
the origin to~$e$ and sends no other point into~$E$.

\begin{lemma}
    \label{LemPuncturesTitsAlternativeFails}
    If $X$ has
 infinitely many
    punctures, then its mapping class group
    does not satisfy the Tits Alternative.
\end{lemma}

\begin{proof}[Proof sketch.]
    Choose an infinite sequence of distinct ends~$e_n$, and
    disks in~$X\cup E$ centered at them, as above.  By shrinking
    the $n$th disk, we may
    suppose it is disjoint from its predecessors.
    So any two of the disks are disjoint.
    With this preparation, it is easy to construct a sequence
    of disjoint closed sets $X_1,X_2,\dots$ in~$X$, such that $X_n$ is
    a disk with $2^n$ punctures.  We decompose $X_n$ as in the
    infinite-genus case, except that we use  once-punctured disks
    in place of the shoes.

    The surface
    automorphisms
    $\hat{a},\hat{b},\hat{c},\hat{d}$ and the group $\hat{G}$ they generate
    are defined as before.  One
    replaces Lemma~\ref{LemGenusSurjectionToG}
    by an analysis of how $\hat{G}$ permutes the ends of~$X$.  This is
    simpler than Lemma~\ref{LemGenusSurjectionToG}
    and similar to what we did in Section~\ref{SecCantorSet}.
    The only difference is that the ends of $\bigcup_n X_n$ are indexed
    by the vertices of~$T$, whereas there
    the ends of $X_\emptyset$ were indexed by
    the ends of~$T$.  The rest of the proof is the same as in the
    infinite-genus case.
\end{proof}

\section{The main results}
\label{SecMainTheorem}

\noindent
Theorem~\ref{ThmMain} is the union of Lemmas \ref{LemCantorTitsAlternativeFails},
\ref{LemGenusTitsAlternativeFails} and~\ref{LemPuncturesTitsAlternativeFails}.
For Corollary~\ref{CorMain}, suppose $X$ has
infinite type but only finitely many boundary
components. The
theorem below shows that $X$ has one of the features
\eqref{CaseGenus}--\eqref{CaseCantor}
in Theorem~\ref{ThmMain}.  Quoting that theorem shows that
$\mathrm{Map}(X)$ does not satisfy the Tits Alternative.
Lanier and Loving used the same trichotomy
to construct the surfaces
mentioned in the introduction, whose mapping class groups
fail to satisfy
the \emph{strong} Tits Alternative.

\begin{theorem}
    \label{ThmTrichotomy}
    Suppose $X$ is an infinite-type surface with only finitely
    many boundary components.  Then $X$ has infinite genus,
    or infinitely many punctures, or contains a closed subset
    homeomorphic to a disk with a Cantor set removed from its
    interior.
\end{theorem}

We call a surface~$X$ \defn{planar} if  every circle
embedded in $X-\partial X$
is separating.

\begin{lemma}
    \label{LemEndRecognition}
    Suppose $X$ is a planar surface and $E$ its space of ends.
    Suppose $e$ is an isolated point of~$E$ and lies outside the
    closure of $\partial X$ (in $X\cup E$).  Then $e$ is a puncture.
\end{lemma}

\begin{proof}
Straightforward.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{ThmTrichotomy}]
    The arguments
    are like those of Richards \cite{Richards} in his proof of Ker\'ekj\'art\'o's
    theorem classifying noncompact surfaces.  We would like to quote his results,
    but they do not allow boundary.  A generalization due to
    Prishlyak and Mischenko \cite{PrishlyakMischenko} allows boundary, but
    I could not follow it.

    If $X$ is nonorientable, then we can find an embedded M\"obius band $M_1$.
    If $X-M_1$ is nonorientable, then it contains an embedded M\"obius band
    $M_2$.  Repeating this process with $X-(M_1\cup M_2)$, and so on, we find
    a sequence of mutually disjoint embedded M\"obius bands. Suppose
    first that this construction does not terminate, so
    the sequence is infinite.    The
    connected sum of three crosscaps is the same as the connected sum of a
    torus and a single crosscap,  so $X$ has infinite genus.

    This leaves the case that the sequence terminates.
    Then $X$ is the connected sum of an orientable surface
    $X_1$ and finitely many crosscaps.  If the genus of
    $X_1$ is infinite
    then we are done, so suppose it is finite.
    Gathering the handles and crosscaps together, we see that
    $X$ is the connected sum of a planar surface $X_2$ and
    a closed surface.  Because $X$ has infinite type, $X_2$ does too.

    We write $E$ for the end space of~$X$, which is also the
    end space of~$X_2$.   It is infinite, or else
    $X_2$ would have finite type.
    Its intersection
    with $\overline{\partial X}$ (the closure taken in $X\cup E$) is
    finite, because $X$ has finitely many boundary
    components, each with at most two ends.  So $E-\overline{\partial X}$
    is infinite.   The finiteness of
    $E\cap\overline{\partial X}$ also shows that
    a point of $E-\overline{\partial X}$ is isolated in
    $E-\overline{\partial X}$ if and only if it is isolated in~$E$.
    So we may speak unambiguously of isolated ends.

    If there are infinitely many isolated points of $E-\overline{\partial X}$,
    then we are done because Lemma~\ref{LemEndRecognition} shows that
    each is a puncture.  So suppose otherwise.
    Because $E$ is infinite,  $E-\overline{\partial X}$ has a
    non-isolated point~$e$.  Choose an embedded
    circle $C\subseteq X_2$ that separates $e$ from
    $\partial X_2$ and the isolated ends.
    Of the two components of $X_2-C$, one has $e$ among its ends.
    Write $D$ for the union of that component and~$C$, and
    write $E_0$ for the end space of~$D$.
    Because $E_0$ has no isolated points, it
    is perfect and therefore a Cantor set.  Because $X_2$ is planar,
    a standard subdivision-into-pairs-of-pants argument shows that $D$ is a disk
    with a Cantor set removed from its interior.
\end{proof}

If $X$ has infinitely many boundary components, then our constructions
may fail.  The reason is that the homeomorphisms used to define
$\mathrm{Map}(X)$ must fix $\partial X$ pointwise, so that they cannot permute
the components of~$\partial X$.
But even if one allowed permutations in some way,
some surfaces would still escape our methods:

\begin{example}
    Let $D_{n\in\mathbb{Z}}$ be the closed disk in~$\mathbb{R}^2$ with radius~$1/3$
    and center $(n,0)$.  Let $C_n$ be a Cantor set in $\partial D_n$.
    Let $X$ be the plane, minus the union of the~$C_n$ and
    the interiors of the~$D_n$.  Then $X$ has countably many boundary
    components~$B_{k\geq1}$, each a copy of~$\mathbb{R}$.  From $X$ remove
    $k$ points from each~$B_k$, and write~$Y$ for what remains.  Then
    every self-homeomorphism of~$Y$ sends every component of~$\partial Y$
    to itself.
    (The key step is that every self-homeomorphism of~$Y$ sends
    every $B_k$ to itself.  To see this, say that two components
    of~$\partial Y$ \emph{abut} if some end of $Y$ lies in both
    their closures.  Under the equivalence relation this generates,
    two components of $\partial Y$ are equivalent if and only if they
    lie in the same~$B_k$.  Every self-homeomorphism preserves the
    unique equivalence class of each size~$k>1$, hence every $B_k$.)
    It seems likely that the central quotient of $\mathrm{Map}(Y)$ is the
    end-preserving subgroup of $\mathrm{Map}(Y-\partial Y)$, ie
    a version of the pure braid group on infinitely many strands.
\end{example}