\section{Introduction}
Supersymmetry (SUSY) extension is one of the most promising way
 to solve the gauge hierarchy problem in the standard model \cite{SUSY}.
However, since any superpartners have not been observed
 in current experiments, SUSY should be broken at low energies.
Furthermore, soft SUSY breaking terms are severely constrained
 to be almost flavor blind and CP invariant.
Thus, the SUSY breaking has to be mediated to the visible sector
 in some clever way not to induce too large CP and flavor violation effects.
Some mechanisms to achieve such SUSY breaking mediations
 have been proposed \cite{Luty:2005sn}.

On the other hand, in view of the LHC collider physics,
it is quite important to distinguish if the gauginos are Dirac or Majorana.
So far many studies have carried out based on the assumption
that the gauginos are Majorana particles as in the MSSM.
However, there exist some models which give rise to the gaugino
as Dirac particle which can naturally realized in models
with $U(1)_R$ symmetry \cite{Randall}.
For example, supersoft SUSY breaking scenario \cite{Fox:2002bu, Chacko:2004mi}
which has partly ${\cal N}=2$ supersymmetry in gauge sector
provide a model with Dirac gauginos.
Some other extensions of the model and the related phenomenology
can be found in the literature \cite{Nelson:2002ca, Nomura:2005rj}.
Supersoft SUSY breaking scenario also has some good features in
regards to the SUSY CP problems or the EDMs \cite{Hisano:2006mv}.

In this letter, we extend a model of the Dirac gauginos, which originate from
${\cal N} =2$ SUSY for the gauge sector,
such that the ${\cal N} =2$ SUSY is imposed also to the sfermion sector
but only for the 3rd generation squarks and sleptons.
By this extension, the dominant source of radiative correction
to the Higgs mass squared coming from the stop loop becomes controllable
based on the enhanced symmetry.
Then it becomes a viable model which provides a solution to
the little hierarchy problem in SUSY models.
Even in the original scenario, the Dirac gauginos can be superheavy,
of order $10$ TeV or so, while keeping the scalar masses at the weak scale.
This possibility is phenomenologically interesting because it can suppress
the unwanted flavor changing processes.
And in scope of the LHC, this scenario can have a very distinct signature
related to the exotic sfermions which are accompanied as the ${\cal N} =2$
superpartners as well as the Dirac gauginos.

\section{Dirac gaugino in a warped extra dimension}
\subsection{Introduction to the model of Dirac gaugino}
Here we give a brief description of the Dirac gaugino model based on the ${\cal N} = 2$ SUSY in gauge sector.
At first, an ${\cal N} = 2$ vector multiplet ${\cal V} = (V,~\Sigma)$ contains an ${\cal N} = 1$ vector multiplet,
$V= (A^\mu,~\lambda)$ and an $N = 1$ chiral multiplet in the adjoint representation, $\Sigma = (\phi,~\psi)$.
Basically, in the Dirac gaugino model, the gaugino ($\lambda$) has the Dirac mass terms together with
an adjoint fermion ($\psi$). Suppose the adjoint fermion has
mass term $m_\Sigma$, the mass matrix for these states are given by
\begin{equation}
{\cal L}
=
\left(
\begin{array}{cc}
\lambda & \psi
\end{array}
\right)
\left(
\begin{array}{cc}
0 & M_{D} \\
M_{D} & m_{\Sigma} \\
\end{array}
\right)
\left(
\begin{array}{c}
\lambda \\ \psi
\end{array}
\right) \;.
\end{equation}
Therefore, in the mass eigenstates, there are two copious
gauginos for each gauge group:
$(\tilde{g}_1,~\tilde{g}_2)$ for SU(3),
$(\tilde{W}_1,~\tilde{W}_2)$ for SU(2), and
$(\tilde{B}_1,~\tilde{B}_2)$ for U(1).
Many studies on the nature of the Dirac gauginos
in view of the collider physics have been performed.
Some studies on the Dirac nature of either charginos or neutralinos,
which are some mixed states of both $(\tilde{W}_1,~\tilde{W}_2)$ and $(\tilde{B}_1,~\tilde{B}_2)$,
are given in \cite{Choi:2001ww, Aguilar-Saavedra:2003hw, Choi:2003fs, Hagiwara:2005ym}
and a study on the exotic gluinos $(\tilde{g}_1,~\tilde{g}_2)$ having Dirac mass terms
in \cite{Nojiri:2007jm}.

\subsection{Dirac gaugino masses in a warped extra dimension}
We consider a SUSY model
 in the warped five dimensional brane world scenario.
The fifth dimension is compactified on the orbifold $S^1/Z_2$
 with two branes, ultraviolet (UV) and infrared (IR) branes,
 sitting on each orbifold fixed point.
With an appropriate tuning for cosmological constants
 in the bulk and on the branes,
 we obtain the warped metric,
\begin{eqnarray}
 d s^2 = e^{-2 k r_c |y|} \eta_{\mu \nu} d x^{\mu} d x^{\nu}
 - r_c^2 d y^2 \; ,
\end{eqnarray}
 for $-\pi\leq y\leq\pi$, where $k$ is the AdS curvature, and
 $r_c$ and $y$ are the radius and the angle of $S^1$, respectively.
The most important feature of the warped extra dimension model
 is that the mass scale of the IR brane is warped down to
 a low scale by the warp factor, $\omega = e^{-k r_c \pi}$,
 in four dimensional effective theory.
For simplicity, we take the cutoff of the original five dimensional theory
 and the AdS curvature as
 $M_5 \simeq k \simeq M_P=2.4 \times 10^{18}$ GeV,
 the four dimensional Planck mass,
 and so we obtain the effective cutoff scale
 as $\Lambda_{\rm IR}= \omega M_P$ in effective four dimensional theory.
Now let us take the warp factor so as for the GUT scale
 to be the effective cutoff scale
 $ M_{\rm GUT}= \Lambda_{\rm IR}=\omega M_P$,
 namely $\omega \simeq 0.01$.

When we start from the warped five dimensional setup,
and introduce an extra U(1) gauge multiplet
which is localized on the IR brane,
the ${\cal N}=2$ vector multiplet consists of
$(A_M,~\lambda_{1,2},~\Sigma)$ where
$\Sigma$ is an adjoint scalar multiplet.

In principle, it is always allowed
to have the following operator that generate the Dirac
gaugino masses:
\begin{equation}
{\cal L}
= \int d^2 \theta \frac{\Sigma}{M_5 \omega}
(W_{U(1)'})^\alpha (W_{\rm MSSM})_\alpha
+ h.c. \;,
\end{equation}
where the warp factor is assigned
for the rescaling of $\Sigma$, $\Sigma \to \Sigma/\omega$.
After developing the VEV of the D-term in $W_{U(1)'}$,
the resultant Dirac gaugino masses at the IR scale
or the GUT scale
after rescaling $\left< D' \right> \to \omega^2 \left< D' \right>$ are given by
\begin{equation}
M_{D_i}= \alpha_{\rm GUT}^{1/2}  \frac{\omega \left< D' \right>}{M_5} \;.
\end{equation}
Below the IR scale the Dirac gaugino masses at a given scale
$\mu$ are given by
\begin{equation}
M_{D_i} (\mu) = \left(\frac{\alpha_i(\mu)}{\alpha_{\rm GUT}}
\right)^{\frac{b_i - 2 c_i}{2 b_i}} M_{D_i} \;,
\label{RG}
\end{equation}
where $b_i$ is the beta function and
$c_i$ is the quadratic Casimir of the adjoint representation.

Given a gaugino mass $M_\lambda$, scalar masses
are arisen at the one loop level:
\begin{equation}
m^2_{\rm supersoft} = \frac{c_i \alpha_i}{\pi}
\ln \left(4
\right) M_{D_i}^2 \;,
\end{equation}
where we took a limit of $m_{\Sigma} \ll M_{D_i}$.
Hence the scalar masses are suppressed by
a factor of $\frac{\alpha_i}{\pi}$ compared to the gaugino masses.
For instance, in order to have scalar mass scale of order
$m_{\rm scalar} \sim 100$ GeV,
the corresponding gaugino masses need to be around $M_{D_i} \sim 10$ TeV.
Remarkable feature of the supersoft SUSY breaking scenario is that
the scalar masses generated by gaugino loops are finite, and it never
receive renormalization except for the gaugino mass itself,
though the gaugino masses are renormalized by the amount of gauge
couplings as in Eq. (\ref{RG}).

In additional to the above gaugino mass terms, there exist another
contribution to the gaugino masses from anomaly mediation,
which are the Majorana terms and not the Dirac mass terms.
\begin{equation}
M_i^{\rm AMSB} = \frac{b_i g_i^2}{16 \pi^2} F_\phi \;,
\end{equation}
where $F_{\phi}$ is the F-term of the conpensator multiplet,
$\phi = 1 + \theta^2 F_{\phi} \simeq 1 + \theta^2 m_{3/2}$.
Since the supersoft SUSY breaking contribution gives masses
of order $10$ TeV in order to have a scalar masses,
this contributions can be negligible in most cases.

Note that the gravitino mass is not an independent quantity it is fixed
so as to cancel the cosmological constant.
To obtain the vanishing cosmological constant, we need to have an appropriate
constant superpotential on the UV brane.
The condition for vanishing cosmological constant is described as
\begin{equation}
\left<V \right> = \omega^4 \left< D' \right>^2 - 3 \frac{|W|^2}{M_p^2} = 0 \;,
\end{equation}
where we took into account of the rescaling
$\left< D' \right> \to \omega^2 \left< D' \right>$,
the resultant superpotential is
$|W|^2 = \left(\omega^4 \left< D' \right>^2 M_p^2 \right)/3$,
and then the gravitino mass is given by
\begin{equation}
m_{3/2} = \frac{|W|}{M_p^2} = \frac{\omega^2 \left< D' \right>}{\sqrt{3} M_p}
\simeq \frac{\omega M_{D_i}}{\sqrt{3}}
\sim m_{\rm supersoft}\;,
\end{equation}
where we took a warp factor as $\omega \simeq 0.01$.
Hence the anomaly mediated contribution becomes well negligible.

\subsection{Radiative Electroweak Symmetry Breaking}
In the MSSM, the upper bound on the lightest Higgs mass
at one loop level is given by
\begin{equation}
m_{h}^2 \lesssim
m_Z^2 \cos^2 2\beta + \frac{3 v^2 y_t^4}{4 \pi^2}
\sin^4 \beta
\ln \left(\frac{m_{\tilde{t}}^2}{m_t^2} \right) \;.
\end{equation}
In order to satisfy the LEP-II experimental lower bound on
the Higgs mass $m_h \gtrsim 114$ GeV, we need to push up
the stop mass $m_{\tilde{t}} \gtrsim 1$ TeV which may cause
a destabilization of the gauge hierarchy, that is
the so called little hierarchy problem.

On the other hand, in the supersoft SUSY breaking scenario,
the leading contribution to the negative Higgs boson mass squared
comes from top quark and squark loop, which is given by
\begin{equation}
m_{H_u}^2 \simeq
m_{\tilde{\ell}}^2-  \frac{3 y_t^2}{4 \pi^2} m_{\tilde{t}}^2
\ln \left(\frac{M_{D_3}}{m_{\tilde{t}}}\right)\;,
~~m_{H_d}^2 \simeq m_{\tilde{\ell}}^2 \;.
\end{equation}
Hence, the mediation scale in this scenario is not high but just
$M_{\rm mess} = M_{D_3} \cong 10$ TeV, the fine-tuning is relaxed
compared to the minimal SUGRA or any other high scale SUSY breaking
scenario.
Putting the results all together, the negative Higgs boson mass squared
parameter is written by
\begin{equation}
m_{H_u}^2 \simeq
m_{\tilde{\ell}}^2-
\frac{3 y_t^2 \alpha_3^{35/18} \alpha_{\rm GUT}^{-4/9}\ln \left(4 \right)}
{4 \pi^3} \frac{\omega \left< D' \right>}{M_5}
\ln \left(\frac{M_{D_3}}{m_{\tilde{t}}}\right)\;,
~~m_{H_d}^2 \simeq m_{\tilde{\ell}}^2 \;.
\end{equation}
For a given Higgs boson mass squared parameter,
the electroweak symmetry breaking condition is described by
\begin{equation}
\frac{M_Z^2}{2} = - m_{H_u}^2 - |\mu|^2\;.
\end{equation}
So, if we take $|\mu| \cong m_{\tilde{\ell}}$,
the correct electroweak symmetry breaking can be achieved
without requiring fine-tuning of the Higgs mass parameters.

Therefore, the important point to solve the little hierarchy problem
in this scenario is to raise the stop mass
while keeping the slepton mass at the weak scale.
Indeed, there exists a mass hierarchy between the stop
and the slepton according to the gauge couplings or
the gauge quantum numbers.
\begin{equation}
\frac{m_{\tilde{t}}^2}{m_{\tilde{\ell}}^2}
\sim \frac{c_3 \alpha_3}{c_2 \alpha_2}
\times \frac{M_{D_3}^2}{M_{D_2}^2} \;.
\end{equation}
Hence, we can take $m_{\tilde{t}} \simeq 1$ TeV
and $m_{\tilde{\ell}} \simeq 100$ GeV at the same time,
which is needed to solve the little hierarchy problem.

\section{A partly ${\cal N}=2$ extension of the MSSM}
\subsection{Introduction to the model of partly ${\cal N}=2$ extended MSSM}
We extend a model of the Dirac gauginos, which originate from
${\cal N} =2$ SUSY for the gauge sector,
such that the ${\cal N} =2$ SUSY is imposed also to the sfermion sector
but only for the 3rd generation squarks and sleptons.
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
& 1st generation & 2nd generation & 3rd generation $\equiv$ $SU(2)_{\cal R}$ doublet \\
\hline \hline
quark doublet & $Q_1$ & $Q_2$ & ${\cal Q} = (q_3,~\overline{q}_3)$ \\
\hline
singlet quark & $u^c_1$ & $u^c_2$ &${\cal U}^c = (u^c_3,~\overline{u}^c_3)$ \\
\hline
singlet quark & $d^c_1$ & $d^c_2$ &${\cal D}^c = (d^c_3,~\overline{d}^c_3)$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{Chiral multiplets in the partly ${\cal N}=2$ extension of the MSSM}
\end{table}
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|}
\hline
 gauge group &  vector multiplet \\
\hline \hline
SU(3) & ${\cal V}^A = (V^A,~\Sigma^A)~(A=1,\cdots, 8)$ \\
\hline
SU(2) & ${\cal V}^a = (V^a,~\Sigma^a)~(a=1,2,3)$ \\
\hline
U(1) & ${\cal V} = (V,~\Sigma)$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{Vector multiplets in the partly ${\cal N}=2$ extension of the MSSM}
\end{table}
Now we evaluate the effects of the Yukawa interactions between the MSSM matter
in the 3rd generation and the exotic states added in the 3rd generation
to the Higgs mass squared.

In order to have Higgs doublet from the adjoint field, which is almost the same situation
as occurred in the Littlest Higgs Model, we have to extend the SM gauge group,
$SU(3)_c \times SU(2)_L \times U(1)_Y$ to $SU(3)_c \times SU(3)_L \times U(1)^\prime$,
and $SU(3)_L \times U(1)^\prime$ will be broken down to the Standard $SU(2)_L \times U(1)_Y$.
The adjoint field contains two Higgs doublet in addition to the triplet and singlet representations.
\begin{equation}
\Sigma =
\left(
\begin{array}{cc}
 T & H_u \\
\overline{H}_u & S \\
\end{array}
\right) \;,
\end{equation}
where $T$ is triplet, $H_u$ and $\overline{H}_u$ are doublet, and $S$ is singlet.
On the other hand, quark doublet is contained in the $SU(3)_L$ fundamental representation
such that
\begin{equation}
Q_3 = \left(
\begin{array}{c}
q_3 \\
u^c_3
\end{array}
\right) \;,
\end{equation}
and also we would have ${\cal N}=2$  partner of it:
\begin{equation}
\overline{Q}_3 = \left(
\begin{array}{c}
\overline{q}_3 \\
\overline{u}^c_3
\end{array}
\right)\;.
\end{equation}
The original interaction which provides a top Yukawa coupling is originated from
gauge interaction because of ${\cal N}=2$ supersymmetry.
\begin{eqnarray}
{\cal L} &=& \int d^4 \theta \,g  \left[
\overline{Q}_3^\dag \,\Sigma \,\overline{Q}_3
+ Q_3^\dag \, \Sigma \,Q_3
\right]
\nonumber\\
&=&  \int d^2 \theta \, g \,\left[
\left(
\overline{q}_3 H_u \overline{u}^c_3
+ \overline{q}_3 \overline{H}_u \overline{u}^c_3  + \cdots \right)
+ \left(
q_3 H_u u^c_3 + q_3 \overline{H}_u u^c_3  + \cdots \right) \right] \;.
\end{eqnarray}
The effective theory which we analyze below the GUT scale is the MSSM
with the right-handed neutrinos. The low energy effective superpotential in this model is given by
\begin{eqnarray}
W_{\rm eff} &=&  \sum_{i,j = 1,2} \left(
Y_{u}^{ij} u^c_i q_j H_u
+ Y_d^{ij} d^c_i q_j H_d
+ Y_{\nu}^{ij} \nu^c_i L_j H_u
+ Y_e^{ij} e^c_i L_j H_d
+ \frac{1}{2} M_{R_{ij}} \nu^c_i  \nu^c_j \right)
\nonumber\\
&+&  g \,\left[
\left(
\overline{q}_3 H_u \overline{u}^c_3
+ \overline{q}_3 \overline{H}_u \overline{u}^c_3  + \cdots \right)
+ \left(
q_3 H_u u^c_3 + q_3 \overline{H}_u u^c_3  + \cdots \right) \right]
\nonumber\\
&+& \mu H_d  H_u \;,
\label{Yukawa4}
\end{eqnarray}
where the 2nd line describes the new interactions which appear
only in the partly ${\cal N}=2$ extension of the MSSM.

Interestingly, in the model of partly ${\cal N}=2$ extension of the MSSM,
in contrast to the usual MSSM,  the lightest Higgs mass receives no divergent contribution
from the stops in the loop, and it becomes finite.
That is basically because ${\cal N} = 2$ partners of the top quarks,
$(\overline{q}_3,\,\overline{u}_3^c)$ can play the role to cancel the divergence
from the top quarks in the loop for the radiative corrections to the Higgs mass squared.
In this sense, the Higgs mass squared coming from the stop loop becomes controllable
based on the enhanced symmetry, and it can provides a natural solution to
the little hierarchy problem in the MSSM.

In this setup, the upper bound on the lightest Higgs mass
at one loop level is given by
\begin{equation}
m_{h}^2 \lesssim
m_Z^2 \cos^2 2\beta + \frac{3 v^2 g^2}{4 \pi^2}
\sin^4 \beta
\left[
\ln \left(\frac{m_{\overline{t}_L}^2}{m_{t_L}^2} \right)
+
\ln \left(\frac{m_{\overline{t}_R}^2}{m_{t_R}^2} \right)
\right] \;.
\end{equation}
So, in the limit of exact ${\cal N} = 2$ supersymmetry,
$m_{\overline{t}_L} = m_{t_L}$ and $m_{\overline{t}_R} = m_{t_R}$,
we end up with exactly the finite Higgs boson mass
as expected.

\newpage
\section*{Acknowledgments}
The work of T.K. is supported by the Research
Fellowship of the Japan Society for the Promotion of Science (\#1911329).


\section{Derivation of the Main Result}

We consider here an ensemble of $N$~independent copies of the
real system. In each copy, a different set of bonds forms between the
linkers (see Figure~\ref{fig:System}).  Let $N_i$ be the number of copies
where linker~$i$ is unbound, and let $N_{ij}$ be the number of copies
where $i$~and~$j$ are bound to each other.  Conversely, let $N_{-i,-j}$ be
the number of copies where both $i$~and~$j$ are unbound.  These quantities
are not independent: each linker $i$ is either unbound or unbound, so
\begin{equation}
N_i + \sum_j N_{ij} = N.
\end{equation}
The fraction of copies where $i$ is unbound ($f_i$), where $i$~and~$j$ are
bound to each other ($f_{ij}$), or where they are both unbound ($f_{-i,-j}$)
follow immediately:
\begin{align}
f_i &= N_i / N,\\
f_{ij} &= N_{ij} / N,\\
f_{-i,-j} &= N_{-i,-j} / N.
\end{align}
Let $Z(\{N_{ij}\})$ be the partition function of an ensemble under the constraint that
each pair of linkers $i$~and~$j$ is bound to each other in exactly $N_{ij}$ copies.
A closed-form expression for $Z(\{N_{ij}\})$ can be constructed
recursively, by adding each bond one by one.
For a given set of $\{N_{ij}\}$, we need to work out how $Z(\{N_{ij}\})$ changes upon
adding one more $i$-$j$ bond, which we do as follows.
We call the set of realisations of the ensemble with $\{N_{ij}\}$ bonds the \emph{old} ensemble, and that of realisations
with one more $i$-$j$ bond, the \emph{new} ensemble.
In the old ensemble, there are $N_{-i,-j}$ copies where an $i$-$j$ bond can be added.
In doing this, all the realisations of the new ensemble are generated, but not uniquely.
For example, given two realisations, one with an $i-j$ bond in copy X but not in Y or Z, and one with an $i-j$ bond in Y but not in X or Z,
the same final realisation can be obtained by adding an $i-j$ bond to Y in the former and X in the latter.
Conversely, in the new ensemble, we can generate a realisation of the old ensemble in $N_{ij}+1$ ways by
removing one of the $i$-$j$ bonds.
For example, the old realisation with an i-j bond in copy X but not Y or Z can be obtained by deleting the $i-j$ bond from a
new realisation with an $i-j$ bond in X and Y but not Z, or from one with an $i-j$ bond in X and Z but not Y.
Since the number of ways of going from the
old to the new ensemble is equal to the number of ways of going from the new to the old
ensemble, it follows that

\begin{align}
&Z(\cdots,N_{ij},\cdots) N_{-i,-j} e^{-\beta\Delta G_{ij}} \notag\\
&\qquad= Z(\cdots,N_{ij}+1,\cdots) (N_{ij}+1).
\label{eqn:balance}
\end{align}
The value of $N_{-i,-j}$ depends not just on the values of $\{N_{ij}\}$ but
on the details of how those bonds are distributed between copies (see Figure~\ref{fig:System}).  To
remove this complication, we approximate the probability of $j$ being unbound as independent of whether
or not $i$ is also bound. Hence,
\begin{equation}
N_{-i,-j} = N f_{-i,-j} \approx N f_i f_j = \frac{N_i N_j}{N}.
\label{eqn:NijApprox}
\end{equation}
Neatly, this approximation allows us to
treat $N_{-i,-j}$ as a function of only $\{N_{ij}\}$.
From the discussion above, we obtain an expression for the increase in
$Z(\{N_{ij}\})$ upon adding one $i$-$j$ bond to the system:
\begin{align}
\frac{Z(\cdots,N_{ij}+1,\cdots)}{Z(\cdots,N_{ij},\cdots)}
&\approx \frac{ e^{-\beta\Delta G_{ij}} N_i N_j}{N (N_{ij} + 1)}\notag\\
= &\frac{e^{-\beta\Delta G_{ij}}(N - \sum_k N_{ik}) (N - \sum_k N_{jk})}{N (N_{ij} + 1)}.
\end{align}
This recursion relation, and the fact that $Z=1$ when no bonds form, allows
us to write an approximate closed-form expression for $Z(\{N_{ij}\})$,
namely
\begin{equation}
Z(\{N_{ij}\}) \approx \prod_i \frac{N!}{(N - \sum_k N_{ik})!} \cdot
  \frac{1}{N^{\sum_{i<j} N_{ij}}} \cdot \prod_{i<j} \frac{e^{-\beta N_{ij}\Delta G_{ij}}}{N_{ij}!}.
\label{eqn:alexei}
\end{equation}
Using Stirling's approximation and Eq.~\eqref{eqn:alexei}, the free energy
per copy $\beta f_{\text{att}}^* = -(1/N) \ln Z(\{N_{ij}\})$
is then given by
\begin{widetext}
\begin{equation}
\betaf_{\text{att}}^*(\{f_{ij}\}) =
\sum\limits_{i<j} f_{ij} \beta\Delta G_{ij}
+ \sum\limits_i \bigl(1 - \sum\limits_j f_{ij}\bigr) \ln\bigl(1 - \sum_k f_{ik}\bigr)
 + \sum\limits_{i<j} f_{ij} \ln f_{ij} + \sum\limits_{i<j} f_{ij}.
\label{eqn:FattStarExpanded}
\end{equation}
\end{widetext}
Treating $\{f_{ij}\}$ as
continuous in the range $[0,1]$, the overall free energy per copy of the
ensemble, $F_{\text{att}}^*$, follows from a saddle-point approximation:
\begin{multline}
\betaF_{\text{att}}^* \equiv -\frac{1}{N}\ln\left[\int \Biggl(\prod_{i<j} N \text{d} f_{ij}\Biggr)\,
e^{-N\betaf_{\text{att}}^*(\{f_{ij}\})}\right]\\
 =
\betaf_{\text{att}}^*(\{\overline{f_{ij}}\}) + \mathcal{O}(\ln N / N) \approx
\betaf_{\text{att}}^*(\{\overline{f_{ij}}\}),
\label{eqn:saddle}
\end{multline}
where the integration is over all positive values of $\{f_{ij}\}$ satisfying
$\sum_j f_{ij} \leq 1$ for all~$i$ and the values $\{\overline{f_{ij}}\}$ are
obtained by minimising the free energy per copy,
\begin{equation}
\frac{\partial\betaf_{\text{att}}^*}{\partial f_{ij}}\biggr|_{\{\overline{f_{ij}}\}}
= 0.
\label{eqn:fijbar_defn}
\end{equation}
When $N\to\infty$, the values $\{\overline{f_{ij}}\}$ are precisely the
average values of $\{f_{ij}\}$.  Eq.~\eqref{eqn:fijbar_defn} implies that
$\{\overline{f_{ij}}\}$~and~$\{p_{ij}\}$ obey identical equations
(Eq.~\eqref{eqn:pij}), and so are equal:
\begin{equation}
\overline{f_{ij}} = p_{ij}.
\label{eqn:fij_is_pij}
\end{equation}
\subsection{Connection to thermodynamic integration}

The free energy $F_{\text{att}}^*$, defined in Eq.~\eqref{eqn:saddle}, is equal to
the free energy of the real system to the extent that the approximation in
Eq.~\eqref{eqn:NijApprox} is valid.  Since this is the same approximation
that we used previously\cite{VarillyEtAl:2012} to calculate the free energy in terms of a thermodynamic integral,
$F_{\text{att}}$, it is reasonable to suppose that $F_{\text{att}}^*$~and~$F_{\text{att}}$ are equal.  We now show this explicitly.

In our original paper, we calculated the exact attractive free energy for
the real system of linkers using thermodynamic integration. Specifically, we
replaced $\beta\Delta G_{ij}$ by $\beta\Delta G_{ij} + \lambda$, whereupon the
probabilities $\{p_i\}$~and~$\{p_{ij}\}$ become functions of~$\lambda$.  We
then integrated the appropriate free energy derivative over the range $0
\leq \lambda < \infty$, and obtained
\begin{equation}
\betaF_{\text{att}} = -\int_0^\infty \text{d}\lambda\,\frac{\text{d}\betaF_{\text{att}}}{\text{d}\lambda}
= -\int_0^\infty \text{d}\lambda\, \sum_{i<j} p_{ij}(\lambda).
\label{eqn:ThermoInt}
\end{equation}
The same replacement of $\beta\Delta G_{ij}$ with $\beta\Delta G_{ij} + \lambda$ can
be made in the ensemble of $N$~copies.  In that case, using
Eqs. \eqref{eqn:FattStarExpanded}~and~\eqref{eqn:saddle}, we find that
\begin{equation}
\frac{\text{d}\betaF_{\text{att}}^*}{\text{d}\lambda} =
\sum_{i<j}
\frac{\partial\betaf_{\text{att}}^*}{\partial f_{ij}}\Bigr|_{\{p_{ij}\}}
\frac{\text{d} p_{ij}}{\text{d}\lambda}
+ \frac{\partial\betaf_{\text{att}}^*}{\partial \lambda}\Bigr|_{\{p_{ij}\}}.
\end{equation}
The first term vanishes owing to
Eqs. \eqref{eqn:fijbar_defn}~and~\eqref{eqn:fij_is_pij}, and the second term
follows immediately from Eq.~\eqref{eqn:FattStarExpanded}.  We then have
\begin{equation}
\frac{\text{d}\betaF_{\text{att}}^*}{\text{d}\lambda} =
\sum_{i<j} p_{ij} = \frac{\text{d}\betaF_{\text{att}}}{\text{d}\lambda}.
\end{equation}
Moreover, both $F_{\text{att}}^*$~and~$F_{\text{att}}$ are zero when $\lambda$ is infinite, so
the two quantities are equal for all~$\lambda$.

The previous result, together with Eqs.~\eqref{eqn:FattStarExpanded}--\eqref{eqn:fij_is_pij}, yields the following
closed-form expression for $F_{\text{att}}$:
\begin{widetext}
\begin{equation}
\betaF_{\text{att}} = \sum_{i<j} p_{ij} \beta\Delta G_{ij}
+ \sum_i \bigl(1 - \sum_j p_{ij}\bigr) \ln\bigl(1 - \sum_k p_{ik}\bigr)
+ \sum_{i<j} p_{ij} \ln p_{ij} + \sum_{i<j} p_{ij}.
\label{eqn:final_Fatt}
\end{equation}
This expression is, in fact, equivalent to the much more compact
Eq.~\eqref{eqn:FattExact}.  Concretely,
\begin{subequations}
\begin{align}
\betaF_{\text{att}}
&= \sum_{i<j} p_{ij} \beta\Delta G_{ij}
+ \sum_i (1 - \sum_j p_{ij}) \ln p_i
+ \sum_{i<j} p_{ij} \ln(p_i p_j e^{-\beta\Delta G_{ij}}) + \sum_{i<j} p_{ij},\\
&= \sum_i (1 - \sum_j p_{ij}) \ln p_i
+ \frac12\sum_{i,j} p_{ij} \ln p_i + \frac12\sum_{i,j} p_{ij} \ln p_j + \sum_{i<j} p_{ij},\\
&= \sum_i (1 - \sum_j p_{ij}) \ln p_i
+ \sum_{i,j} p_{ij} \ln p_i + \sum_{i<j} p_{ij},\\
&= \sum_i \ln p_i + \sum_{i<j} p_{ij}.
\label{eq:compact}
\end{align}
\end{subequations}
\end{widetext}

\section{Discussion}

Figure~\ref{fig:speedup} reports the typical computational speedups obtained
by using Eq.~\eqref{eqn:FattExact} versus our original thermodynamic
integral, Eq.~\eqref{eqn:ThermoInt}, for systems of $M$~linkers.  The
speedup is higher for larger~$M$ and for stronger bonds because each
evaluation of the thermodynamic integrand involves solving a system of
$M$~equations, and the size of the integration domain scales linearly with
the bond strength.  Typically, experimentally relevant regimes deal with
hundreds to tens of thousands of strands, a regime that can now be treated
exactly with Eq.~\eqref{eqn:FattExact}.

\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{Fig-compare.eps}
\end{center}
\vspace{-0.5cm}
\caption{\label{fig:speedup}Computational speedups obtained
by using Eq.~\eqref{eqn:FattExact} vs. Eq.~\eqref{eqn:ThermoInt}, for a
system of parallel plates coated with complementary linkers.}
\end{figure}

In the limit of weak-bonds, where $p_{ij}$ is close to 0,
we find that
\begin{align}
\betaF_{\text{att}}
&= \sum_{i} \ln p_i + \sum_{i<j} p_{ij} =\sum_{i} \ln (1-\sum_j p_{ij}) + \sum_{i<j} p_{ij} ,\notag\\
&\approx - \sum_{i,j} p_{ij} + \sum_{i<j} p_{ij} = -\sum_{i<j} p_{ij}.\notag
\label{eqn:OldModel}
\end{align}
This approximate result has been widely used by previous
authors\cite{BiancanielloKimCrocker:2005, LicataTkachenko:2006,
  DreyfusEtAl:2010, RogersCrocker:2011} under the name of the ``Poisson
approximation'' or the ``weak binding regime''.  However, in experiments
with micron-sized DNA-coated colloids, this approximation can be
significantly inaccurate\cite{MognettiEtAl:2012}.  At the nanoscale, where
high bond strengths are commonly used, the Poisson approximation is expected
to break down (see Fig.~\ref{fig:CompareModels} for comparison).
Eq.~\eqref{eqn:FattExact} is instead quantitatively accurate for bonds of
any strength\cite{VarillyEtAl:2012}.

Eqs. \eqref{eqn:FattExact}, \eqref{eqn:pij}~and~\eqref{eqn:pi} also make
explicit the connection between our theory and previous treatments.  For
example, Dreyfus et al.\cite{DreyfusEtAl:2010} model the attraction between
two DNA-coated spheres by first estimating the maximum number~$N_p$ of
linkers on each sphere that could form a bond with a linker on the second
sphere, and then assuming that each such linker can independently bind any
of $k$ linkers with an average free energy $\Delta F_{\text{tether}}$.  For
later convenience, we define a small expansion parameter~$x$ as
\begin{equation}
x \equiv k e^{-\beta\Delta F_{\text{tether}}},
\end{equation}
and note that the experiments in Ref.~\onlinecite{DreyfusEtAl:2010} take place
mostly in what the author call the ``weak-binding regime'', where $x \ll 1$
and $N_p x \gg 1$.  In their model, the partition function of the system is
\begin{equation}
Z \approx (1 + x)^{N_p},
\end{equation}
from which the free energy~$F_{\text{att}}$ follows,
\footnote{In
  Ref.~\onlinecite{DreyfusEtAl:2010}, the free energy of attraction
  includes only states where at least one bond is formed, thus
  $\betaF_{\text{att}}$ there is $-\ln[(1 + x)^{N_p} - 1]$. Our definition of
  $F_{\text{att}}$ is the free energy of the system of linkers, and includes the
  configuration where no bonds are formed}
\begin{align}
\betaF_{\text{att}} &\approx -\ln[(1 + x)^{N_p}] = -N_p\ln(1+x)\\
&\approx -N_p (x - x^2/2 + \cdots).
\label{eqn:OurModel}
\end{align}
In the present framework, which does not treat the linkers as binding
independently, every linker has the same probability~$p$ of being bound,
given by the solution to
\begin{equation}
p = \frac{1}{1 + x p} \Rightarrow p = \frac{\sqrt{1 + 4 x} - 1}{2x}.
\end{equation}

The free energy then follows from Eqs.
\eqref{eqn:FattExact},\eqref{eqn:pij}:
\begin{align}
\betaF_{\text{att}} &= N_p p^2 x + 2 N_p \ln p\\
&\approx -N_p (x - x^2 + \cdots)
\end{align}
Thus, our theory recovers the results of Dreyfus et al.~in the weak binding
regime.  However, there is significant disagreement already at second order
in~$x$, where linkers begin to compete for binding partners.

\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{Fig-models.eps}
\end{center}
\vspace{-0.5cm}
\caption{\label{fig:CompareModels} Free energy per linker in the ``Poisson
  approximation'' and the present model. Higher values of $x = k
  \exp(-\beta\Delta F_{\text{tether}})$ lead to higher bonding probabilities,
  either because bonds are stronger or because linkers have more binding
  partners. The two models agree in the ``weak binding regime'' ($x \ll
  1$), but disagree when correlations between neighbouring strands become
  significant.}
\end{figure}

Finally,
using the same procedure as in our original paper, we
can directly write an attractive free energy density
for a pair of plates, treated at a more approximate, \emph{spatial} mean-field
level. In the notation
of Ref.~\onlinecite{VarillyEtAl:2012},
\begin{equation}
\beta f_{\text{att}} = \frac12 \sum_{\alpha,\beta} \sigma_\alpha p_\alpha K_{\alpha\beta} p_\beta \sigma_\beta +
\sum_\alpha \sigma_\alpha \ln p_\alpha.
\end{equation}
This result also follows from a large-area limit of
Eq.~\eqref{eqn:final_Fatt} with random grafting points ~\cite{VarillyEtAl:2012,BortoloSoftMatter}.
We expect the simplification provided in this communication will boost
the use of our model for calculating interactions free-energy for general
ligand-receptor mediated systems.

\section{Acknowledgments}
This work was supported by the ERC
Advanced Grant 227758, the Wolfson Merit Award 2007/R3 of the Royal Society of London
and the
EPSRC Programme
Grant EP/I001352/1.
P.V. has been supported by
the
Marie Curie International
Incoming Fellowship of the European Community's FP7
PIIF-GA-2011-300045, and by a Tizard JRF
from Churchill College. Research carried out in part at the Center for Functional Nanomaterials,
Brookhaven National Laboratory, which is supported by the U.S. Department of Energy, Office of Basic Energy Sciences, under Contract No. DE-AC02-98CH10886.


\section{Conclusions}\label{section:conclusions}

We have presented a set of matchings $\basis_n$,
which forms a basis of the \hamiltonianmatrix~$\HC_n$.
In particular we have obtained a factorization
theorem (Theorem~\ref{theorem:hmatrixfactorization})
which shows an explicit way of expressing any perfect
matching as a linear combination of matchings of $\basis_n$.
As a consequence we obtained deterministic algorithms
for computing the parity of the number of Hamiltonian
cycles in undirected graphs and directed bipartite graphs
in $\Oh(\hcconst^n)$, which together with the Isolation
Lemma lead to Monte Carlo algorithms solving the decision versions
of Hamiltonicity within the same running time.
Moreover, using the basis $\basis_n$,
we presented an algorithm which given an undirected graph
on $n$ vertices along with a path decomposition
of width at most $\pw$, decides Hamiltonicity in $(2+\sqrt{2})^{\pw}n^{\Oh(1)}$ time.
Somewhat surprisingly we use the same tool, i.e. the basis $\basis_n$,
to show by an involved reduction from CNF-Sat that our bounded pathwidth algorithm
is optimal under the Strong Exponential Time Hypothesis.

Our results lead to several natural open problems.
Can the basis $\basis_n$ be used to obtain a deterministic
$\Oh((2-\epsilon)^n)$ time algorithm for Hamiltonicity?
Can we handle directed graphs without the bipartiteness assumption?
Can we extend our bounded pathwidth algorithm to a bounded treewidth algorithm
with the same complexity?

Finally we would like to note that the row space of the
\hamiltonianmatrix~$\HC_n$ clearly has several different
bases. We have investigated a particular one, which
proved to have several interesting properties
and applications, however there might be different
ones which are also worth exploring.

\section*{Acknowledgements}

We would like to thank Marcin Pilipczuk, Micha\l{} Pilipczuk, Johan van Rooij and Jakub Onufry Wojtaszczyk for early discussions on Section~\ref{section:hamcycle:lowerbound}.
\section{Introduction}

The Hamiltonicity problem and its generalization to the traveling salesman problem are widely acknowledged to be two of the most famous NP-complete
problems. Many classical algorithms were invented to tackle these problems (and variants thereof), among them Cristofides' approximation algorithm~\cite{Chr76}, the
Lin-Kernighan heuristic~\cite{linkerheur73}, and a polynomial time approximation scheme for Euclidean TSP~\cite{Arora:1998:PTA:290179.290180}.

A very early and classical result belonging to this list is due to Bellman~\cite{bellman1958combinatorial,Bellman62} and, independently, Held and
Karp~\cite{Held:1961:DPA:800029.808532}; it demonstrates that the traveling salesman problem can be solved in $\Oh(n^22^n)$ time, where $n$ denotes the
number of vertices of the input graph. In order to get this result they introduced dynamic programming over subsets, which became a fundamental design paradigm for obtaining exact exponential time algorithms (see for example \cite{DreyfWagn} and \cite[Chapter 3]{Fominbook}). Considerable effort has been taken to improve these algorithms: More space efficient
algorithms were already given independently by several authors \cite{Bax1993203,KarpDynIncEx,Kohnetal}.

In his influential survey, Woeginger~\cite{DBLP:conf/aussois/Woeginger01} brought renewed attention to a question suggesting itself already from the 60's: Can
either the traveling salesman problem or the Hamiltonicity problem be solved in $(2-\epsilon)^n n^{\Oh(1)}$ for some $\epsilon > 0$? An affirmative answer
was given for the special cases of bounded degree~\cite{eppstein-tsp-cubic,DBLP:journals/mst/BjorklundHKK10,iwama-tsp-cubic,gebauer-tsp-bound} and claw-free
graphs~\cite{DBLP:conf/wg/BroersmaFHP09}. In a breakthrough result, Bj\"orklund~\cite{DBLP:conf/focs/Bjorklund10} partially resolved the open question by giving
an $1.66^n n^{\Oh(1)}$ time Monte Carlo algorithm deciding undirected Hamiltonicity, using as a first step a $2^{n/2} n^{\Oh(1)}$ time algorithm for bipartite graphs.
Unfortunately, it seems hard to derandomize this result or to extend it to the traveling
salesman problem without incurring a pseudo-polynomial dependence on the input weights.
The algorithm of~\cite{DBLP:conf/focs/Bjorklund10} instead of keeping track of all the vertices along the
so far constructed path (as Bellman, Held and Karp), labels only some vertices and some edges used on the path.
Bj\"orklund's algorithm uses counting modulo two as a tool for canceling unwanted self-crossing walks,
however it relies on the assumption that the Hamiltonian cycles under consideration satisfy
particular counting invariants concerning the number of vertices and edges used.
For this reason the algorithm of~\cite{DBLP:conf/focs/Bjorklund10}, to the best of our knowledge,
can not determine the parity of the number of all Hamiltonian cycles.

Recall that the algorithm of~\cite{bellman1958combinatorial,Bellman62,Held:1961:DPA:800029.808532} uses dynamic programming based on the observation
that if we have constructed a path from $v_a$ to $v_b$, then the only additional information needed is the set of vertices used along the way.
Hence the essential information required to store for all subpaths is their endpoints and the set of visited vertices, leading to $\Oh(n2^n)$ table entries. Recall that
for designing a fast dynamic programming algorithm, it is essential that one chooses the right strategy of decomposing a candidate solution. For example, if $G$
has a small balanced separator\footnote{A vertex set $X$ such after removing $X$, all connected components have size at most $|V|/2$.} of size $0.1|V|$ it seems
impossible to modify the above algorithm in order to exploit this fact.

In this work we study the following way to decompose a Hamiltonian cycle $H$: Consider an arbitrary ordering $e_1,\ldots,e_m$ of the edges $E$ and decompose
$H$ for every $i$ into $H_1=\{e_1,\ldots,e_i\} \cap H$ and $H_2=\{e_{i+1},\ldots,e_n\} \cap H$. This suggests another dynamic programming strategy
alternative to~\cite{bellman1958combinatorial,Bellman62,Held:1961:DPA:800029.808532} that was much less well-studied, mainly because it seemed a priori that the
essential information needed to store for a set of partial solutions $H_1$ is $2^{\theta(n \lg n)}$: The degrees (zero, one, or two) of each vertex with respect to~$H_1$ and the pairing in which vertices of degree one are connected by~$H_1$. The informed reader will notice that this way of
decomposing solutions is inherent to dynamic programming algorithms that operate on \emph{tree decompositions} or \emph{path decompositions}.

The notions of \emph{pathwidth}/\emph{treewidth} proved to be an excellent tool for dealing with many NP-hard problems on graphs. In the 1970s and 1980s,
several groups of researchers discovered the concept independently. In their fundamental work on graph minors, Robertson and Seymour \cite{Robertson84}
introduced the notions \emph{path/treewidth} and \emph{path/tree decomposition}, and these became the dominant terminology. A graph having small path/treewidth
means informally that it can be decomposed efficiently in a path/tree-like manner. Many problems can be solved using dynamic programming by decomposing a
solution according to the given path/tree decomposition. We refer to~\cite{bodlaendersurvey} for more information on these notions.

In early work, such as the influential result of Courcelle~\cite{DBLP:journals/iandc/Courcelle90}, algorithms with running times of the type $f(\pw)n$ were given\footnote{Assuming an input
graph $G$ on $n$ vertices along with a path decomposition of $G$ width $\pw$ is given.}. Later it was noticed that for many such algorithms the function $f(\pw)$
can be substantially improved, greatly improving the tractability as well. For example for many problems whose solutions can be verified by separately
considering its intersection with all neighborhoods of the vertices of the input graph (see~\cite{DBLP:conf/podc/GoosS11}), we can obtain
$2^{\Oh(\pw)}n^{\Oh(1)}$ by employing dynamic programming. For example the Independent Set, or equivalently, Vertex Cover, problem can be solved in $2^{\pw}n$
time~\cite{kleinberg-tardos, Niedermeier02invitationto}. From the work of \cite{ImpagliazzoPZ01}
and standard Karp-reduction it follows that this dependence cannot be improved to sub-exponential algorithms unless the Exponential Time Hypothesis fails, i.e., unless
CNF-SAT has a subexponential algorithm. In \cite{treewidth-lower} it was shown that under a stronger assumption (the so-called Strong Exponential
Time Hypothesis (SETH)), the current algorithms are optimal even with respect to polynomial jumps, that is, problems with current best
running time $f(\tw)n^{\Oh(1)}$ cannot be solved in $f(\tw)^{1-\epsilon}n^{\Oh(1)}$ for positive $\epsilon$ where $f(\tw)$ is $2^{\tw}$, $3^{\tw}$ for respectively Independent Set and
Dominating Set.

For the Traveling Salesman problem, or even the Hamiltonian cycle problem, the situation is different since they are not local problems (see for example \cite[Section
5]{DBLP:conf/podc/GoosS11}). In~\cite{Catalan}, the notion of a Catalan structure was introduced to give an algorithm that solves the $k$-path problems on
$H$-minor free graphs in $2^{\Oh(\tw)}$ time. To obtain this, their result works for `pairing-encodable' problems (i.e. problems where the connectivity properties
can be encoded by a matching/pairing) since it bounds the number of ways paths can intersect with a part of the tree decomposition. However, in~\cite{DBLP:conf/focs/CyganNPPRW11} it was shown that along with many other connectivity problems, Hamiltonian cycle can
be solved by a Monte Carlo algorithm in $4^{\Oh(\tw)}n^{\Oh(1)}$ time. For many of these algorithms with running time $f(\tw)n^{\Oh(1)}$, it was shown that
an algorithm running in time $f(\tw)^{1-\epsilon}n^{\Oh(1)}$ would violate SETH. Nevertheless, the exact complexity of the Hamiltonian cycle problem remained elusive.

Recently, a superset of the current authors, found a connection of the optimal substructure of a dynamic programming algorithm
with the rank of a certain matrix~\cite{deterministic}: Consider a matrix $\HC$ with rows and columns indexed by partial solutions, with a $1$ if and only if
the two partial solutions combined give a valid solution, then if we have more than $\rk(\HC)$ partial solutions, one will be redundant in the sense that we can
safely forget it. This leads to deterministic~$2^{\Oh(\tw)}n^{\Oh(1)}$ time algorithms for many connectivity problems, in a sense derandomizing the work of Cygan et al.~\cite{DBLP:conf/focs/CyganNPPRW11}, but the used techniques do not match their runtimes, e.g., the $4^{\tw}n^{\Oh(1)}$ time for Hamiltonian cycle.

\subsection*{Our contribution}
Inspired by the mentioned result from~\cite{deterministic}, we study a matrix that we call the \emph{\hamiltonianmatrix}.
We present a family of perfect matchings $\basis_t$,
which we show to be a basis of the \hamiltonianmatrix, therefore we establish its rank.
All further results of the paper use the basis $\basis_t$ and its properties as its key tool,
which we now elaborate on.

\paragraph{Determining rank of the \hamiltonianmatrix.} For an even integer $t \geq 2$, the \hamiltonianmatrix~$\HC_t$ is a matrix that has rows and columns both
labeled by all perfect matchings of the complete graph~$K_t$ on~$t$ vertices; an entry~$\HC_t[M_1,M_2]$ is~$1$ if~$M_1\cup M_2$ is a Hamiltonian cycle and~$0$
otherwise. The centerpiece of our work is that~$\HC_t$ has rank exactly $2^{t/2-1}$ over GF(2). To establish this result, we define an explicit family~$\basis_t$ of~$2^{t/2-1}$ perfect matchings on~$K_t$ and show that its columns (or rows) form a basis of~$\HC_t$ over GF(2): First, essentially by design, each matching~$M\in\basis_t$ has a unique partner~$M'\in\basis_t$ such that their union is a Hamiltonian cycle. Thus, the rows and columns labeled by~$\basis_t$ induce a permutation matrix, which implies the required rank lower bound. Second, we give an explicit factorization of $\HC_t$ into a product of two rectangular matrices with inner dimensions indexed by~$\basis_t$ in Theorem~\ref{theorem:hmatrixfactorization}. This proves that~$\basis_t$ is indeed a basis, provides an explicit formula for linear combinations, and completes the claimed rank bound (see Section~\ref{section:matchingbasis}).

In~\cite{DBLP:journals/combinatorica/RazS95} a matrix $\HC'_t$ is studied that is obtained by restricting $\HC_t$ to all perfect matchings of the complete \emph{bipartite} graph
with independent sets of size $t/2$. There it is shown that when taken over the reals, the rank of $\HC'_t$ is exactly $\binom{t-1}{t/2-1}$ using
group representation theory. Using this the authors disprove the original\footnote{A weakened version is still a standing open problem in communication
complexity~\cite[Section 13.2]{arora09}.} `log-rank conjecture' in communication complexity since they also showed that the non-deterministic communication
complexity of determining whether two such matchings give a Hamiltonian cycle is $\Omega(n \log \log n )$. In~\cite[Lemma 3.13]{deterministic} a factorization
of a matrix that contains~$\HC_t$ as submatrix into two matrices with inner dimension $2^{t-1}$ was given.

\paragraph{Exact algorithms for Hamiltonicity.}

By exploiting the peculiar form of the basis $\basis_n$ we show
that the number of distinct subsets of all the matchings of $\basis_n$ is $\Oh(\hcconst^n)$.
Together with Theorem~\ref{theorem:hmatrixfactorization} this allows us to show deterministic algorithms computing the parity of the
number of Hamiltonian cycles in undirected graphs and directed bipartite graphs (section~\ref{ssec:mainlemmaproofs}) in $\hcconst^n n^{\Oh(1)}$ time.
By combining those results with the Isolation Lemma
we obtain Monte Carlo algorithms solving the decision version of Hamiltonicity
in both undirected and directed bipartite graphs within the same running time.

Even though our algorithm for undirected graphs is slower than the algorithm of Bj\"orklund~\cite{DBLP:conf/focs/Bjorklund10}, we believe it is of interest
as it uses very much different tools and allows solving the problem also
in directed bipartite graphs. We would like to recall
that solving the Hamiltonicity problem on undirected bipartite graphs
in $\Oh((2-\epsilon)^n)$ time was the first step of Bj\"orklund
on the way to the algorithm for general undirected graphs.
For this reason we believe that studying directed bipartite graphs
is justified.

\paragraph{Algorithm for bounded pathwidth.} Using the set of perfect matchings~$\basis_t$ we obtain a faster algorithm for solving the Hamiltonian cycle problem
via a non-trivial pathwidth dynamic programming routine. Regarding the algorithm, already from the rank bound it can be argued that only~$(2+\sqrt{2})^{\pw}$
space is needed to solve Hamiltonian cycle on a graph with given path decomposition of width~$\pw$. The key idea is to replace memoization of all partial
solutions by storing only fingerprints of groups of solutions that encode how many partial solutions are consistent with a given basis matching. In fact, these numbers are stored only modulo two which requires only one bit per basis matching. To achieve also \emph{time}~$(2+\sqrt{2})^{\pw}n^{\Oh(1)}$ we show in Lemma~\ref{lemma:basischange} how to efficiently convert these fingerprints
from one basis to another, which permits us to perform the needed dynamic programming table computations (in particular insertion of edges into partial
solutions); this crucially depends on the structure of~$\basis_t$. Notably, Lemma~\ref{lemma:basischange} gives a second proof of the rank upper bound for $\HC_t$, but it does so in a more implicit way; in particular it does not provide an explicit factorization (see Section~\ref{section:hcalgorithm}).

Let us point out the main differences to the related algorithmic results obtained by Bodlaender et al.~\cite{deterministic}: The present faster algorithm for Hamiltonicity parameterized by pathwidth required a new dynamic programming strategy, unlike the results of~\cite{deterministic} that speed up existing formulations. Furthermore, we require randomization (for the Isolation Lemma~\cite{isolation}) to guarantee a unique solution, in order for the fingerprinting approach to work. Finally, achieving time~$(2+\sqrt{2})^{\pw}n^{\Oh(1)}$ depends crucially on the structure of our basis matchings~$\basis_t$ (to allow for Lemma~\ref{lemma:basischange}) and does not appear to follow directly from the rank. (Similarly, the subsequent lower bound requires the existence of a sufficiently large permutation/identity matrix in~$\HC_t$ and does not follow directly from the rank lower bound.)

\paragraph{Matching lower bound assuming SETH.} We show that if the running time of our algorithm can be significantly improved, then satisfiability of CNF-Sat formula's
of $m$ clauses and $n$ vertices can be determined in $(2-\epsilon)^{n}m^{\Oh(1)}$ time. The latter would contradict the \emph{Strong Exponential Time Hypothesis
(SETH)} introduced in~\cite{ImpagliazzoPZ01}. Although there is not consensus about it's truth, a number of results have been given assuming
SETH~\cite{patrascu10sat-lbs,DBLP:conf/coco/CyganDLMNOPSW12,treewidth-lower,DBLP:conf/focs/CyganNPPRW11}. As with previous results, this result should be interpreted that there is a boundary to significantly improving our algorithm, namely finding the so far elusive~$(2-\epsilon)^{n}m^{\Oh(1)}$ algorithm for CNF-Sat.

For the tight runtime lower bound we use our basis as a part of a gadget in a reduction from CNF-Sat. Although the basic setup is similar to previous lower bounds~\cite{treewidth-lower,DBLP:conf/focs/CyganNPPRW11} our reduction is different in the sense that we require a very generic gadget (the induced subgraph gadget, discussed in Subsection~\ref{subsection:lowerbound:gadgets}). Using this, we can exploit  the crucial property that the submatrix of the
\hamiltonianmatrix that is induced by the columns and rows of~$\basis_t$ is a permutation matrix, i.e., each basis matching has a unique partner in~$\basis_t$
such that their union is a Hamiltonian cycle. Then, in a similar but technically challenging vein to the reductions of~\cite{treewidth-lower,DBLP:conf/focs/CyganNPPRW11}, choices can be
transferred through a series of gadgets (see Section~\ref{section:hamcycle:lowerbound}).

\paragraph{Further algorithmic conclusions.}

As a corollary of our bounded pathwidth algorithm in Section~\ref{section:hcalgorithm} (Corollary~\ref{cor:hccub})
we also obtain a $(2+\sqrt{2})^{n/6}n^{\Oh(1)}=1.1583^{n}n^{\Oh(1)}$ time Monte Carlo algorithm for Hamiltonicity in cubic graphs,
which to the best of our knowledge is the fastest known algorithm in this class of graphs.


\section{Introduction and main results}\label{sec-1}

During the past three decades, the quasihyperbolic metric has become
an important tool in geometric function theory and in its
generalizations to metric spaces and Banach spaces \cite{Vai5}. Yet,
some basic questions of the quasihyperbolic geometry in Banach
spaces are open. For instance, only recently the convexity of
quasihyperbolic balls has been studied in \cite{krt,rt} in the setup
of Banach spaces.

Our study is motivated by V\"ais\"al\"a's theory of freely
quasiconformal maps  and other related maps in the setup of Banach
spaces \cite{Vai6-0, Vai6, Vai5}. Our goal is to study some of the
open problems formulated by him. We begin with some basic
definitions and the statements of our results. The proofs and
necessary supplementary notation terminology will be given
thereafter.

Throughout the paper, we always assume that $E$ and $E'$ denote real
Banach spaces with dimension at least $2$. The norm of a vector $z$
in $E$ is written as $|z|$, and for every pair of points $z_1$,
$z_2$ in $E$, the distance between them is denoted by $|z_1-z_2|$,
the closed line segment with endpoints $z_1$ and $z_2$ by $[z_1,
z_2]$. We begin with the following concepts following closely the
notation and terminology of \cite{TV, Vai2, Vai, Vai6-0, Vai6} or
\cite{Martio-80}.

We first recall some definitions.

\begin{defin} \label{def1.3} A domain $D$ in $E$ is called $c$-{\it
uniform} in the norm metric provided there exists a constant $c$
with the property that each pair of points $z_{1},z_{2}$ in $D$ can
be joined by a rectifiable arc $\alpha$ in $ D$ satisfying

 \begin{enumerate}
\item\label{wx-4} $\displaystyle\min_{j=1,2}\ell (\alpha [z_j, z])\leq c\,d_{D}(z)
$ for all $z\in \alpha$, and

\item\label{wx-5} $\ell(\alpha)\leq c\,|z_{1}-z_{2}|$,
\end{enumerate}

\noindent where $\ell(\alpha)$ denotes the length of $\alpha$,
$\alpha[z_{j},z]$ the part of $\alpha$ between $z_{j}$ and $z$, and
$d_D(z)$ the distance from $z$ to the boundary $\partial D$ of $D$.
\end{defin}

\begin{defin} \label{def1.7} Suppose $G\varsubsetneq E\,,$ $G'\varsubsetneq
E'\,,$ and $M \ge 1\,$. We say that a homeomorphism $f: G\to G'$ is
{\it $M$-bilipschitz} if
 $$\frac{1}{M}|x-y|\leq |f(x)-f(y)|\leq M|x-y|$$
for all $x$, $y\in G$,  and {\it $M$-QH} if
 $$\frac{1}{M}k_{G}(x,y)\leq k_{G'}(f(x),f(y))\leq Mk_{G}(x,y)$$
for all $x$, $y\in G$. \end{defin}

As for the extension of bilipschitz maps in ${\mathbb R}^2$, Ahlfors
\cite{Ahl} proved that if a planar curve through $\infty$ admits a
quasiconformal reflection, it also admits a bilipschitz reflection.
Furthermore, Gehring gave generalizations of Ahlfors' result in the
plane.

\begin{Thm}\label{xwm-8}$($\cite[Theorem 7]{Ger6}$)$
Suppose that $D$ is a $K$-quasidisk in ${\mathbb R}^2$, that $D'$ is
a Jordan domain in ${\mathbb R}^2$ and that $\phi: \partial D\to
\partial D'$ is $L_1$-bilipschitz. Then there exist
$L$-bilipschitz $f: \overline{D}\to \overline{D'}$ and
$f^{\star}:\overline{D^{\star}}\to \overline{D'^{\star}}$ such that
$f=f^{\star}=\phi$ on $\partial D$ and $L$ depends only on $K$ and
$L_1$, where $D^{\star}=\overline{{\mathbb R}}^2\backslash
\overline{D}$ and $D'^{\star}= \overline{{\mathbb R}}^2\backslash
\overline{D'}$.
\end{Thm}

Tukia and V\"{a}is\"{a}l\"{a} \cite{TV1} dealt with the curious
phenomenon that sometimes a quasiconformal property implies the
corresponding bilipschitz property.

\begin{Thm}\label{xwm-9}$($\cite[Theorem 2.12]{TV1}$)$
Suppose that $X$ is a closed set in ${\mathbb R}^n$, $n\not=4$, and
that $f:{\mathbb R}^n \to {\mathbb R}^n$ is a $K$-QC map such that
$f|_{X}$ is $L$-bilipschitz. Then there is an $L_1$-bilipschitz map
$g:{\mathbb R}^n \to {\mathbb R}^n$ such that

$(1)$ $g|_{X}=f|_{X}$;

$(2)$ $g(D)=f(D)$ for each component $D$ of ${\mathbb R}^n\backslash
X$;

$(3)$ $L_1$ depends only on $K$, $L$ and $n$.
\end{Thm}

In \cite{Ger5}, Gehring raised the following two related problems.

\begin{op}\label{Con2-m-1} Suppose that $D$ is a Jordan domain in
$\overline{{\mathbb R}}^2$, and that $f|_{\partial D}$ is
$M$-bilipschitz. Characterize mappings $f$  having $M'$-bilipschitz
 extension to $D$ with $M'=M'(c,M)$. \end{op}

 \begin{op}\label{Con2-m-2} Suppose that $D$ is a Jordan domain in
$\overline{{\mathbb R}}^2$. For which domains $D$ does each
$M$-bilipschitz $f$ in the $\partial D$ have $M'$-bilipschitz
 extension to $D$ with $M'=M'(c,M)$? \end{op}

 Gehring himself discussed these two problems and got the following two
 results.

\begin{Thm}\label{xw-9}$($\cite[Theorem 2.11]{Ger5}$)$
Suppose that $D$ and $D'$ are Jordan domains  in $\overline{{\mathbb
R}}^2$ and that $\infty\in D'$ if and only if $\infty\in D$. Suppose
also that $f: D\to D'$ is a $K$-quasiconformal mapping and that $f$
extends to a homeomorphism $f: \overline{D}\to \overline{D'}$ such
that $f|_{\partial D}$ is $M$-bilipschitz. Then there exists an
$M$-bilipschitz map $g: \overline{D}\to \overline{D'}$ with
$g|_{\partial D}=f|_{\partial D}$, where $M'=M'(M, K)$.
\end{Thm}

\begin{Thm}\label{xwm-11}$($\cite[Theorem 4.9]{Ger5}$)$
Suppose that $D$ and $D'$ are Jordan domains  in $\overline{{\mathbb
R}}^2$. Then each $M$-bilipschitz $f$ in $\partial D$ has an
$M'$-bilipschitz extension $g: D\to D'$ with $g|_{\partial
D}=f|_{\partial D}$ if and only if $D$ is a $K$-quasidisk, where
$M'=M'(M, K)$ and $K=K(M)$.
\end{Thm}

We remark that Theorem \Ref{xw-9} is a partial answer to Open
Problem \ref{Con2-m-1}, and Theorem \Ref{xwm-11} is an affirmative
answer to Open Problem \ref{Con2-m-2}. In the proof of Theorem
\Ref{xw-9}, the modulus of a path family, which is an important tool
in the quasiconformal theory in ${\mathbb R}^n$, was applied. In
general, this tool is no longer applicable in the context of Banach
spaces (see \cite{Vai6-0}). A natural problem is whether Theorem
\Ref{xw-9} is true or false in Banach spaces. In fact, this problem
was raised by V\"{a}is\"{a}l\"{a} in \cite{Vai5} in the following
form.

\begin{op}\label{Con2} Suppose that $D$ and $D'$ are bounded domains with
connected boundaries in $E$ and $E'$. Suppose also that $f: D\to D'$
is $M$-QH and that $f$ extends to a homeomorphism $f:
\overline{D}\to \overline{D'}$ such that $f|_{\partial D}$ is
$M$-bilipschitz.  Is it true that $f$  $M'$-bilipschitz with
$M'=M'(c,M)$? \end{op}

Our result is as follows.

\begin{thm}\label{xw-1}
Suppose that $D$ and $D'$ are bounded domains with connected
boundaries in $E$ and $E'$, respectively. Suppose also that $f: D\to
D'$ is $M$-QH and that $f$ extends to a homeomorphism $\overline{f}:
\overline{D}\to \overline{D'}$ such that $f|_{\partial D}$ is
$M$-bilipschitz. If $D'$ is a $c$-uniform domain, then $f$ is
$M'$-bilipschitz with $M'=M'(c,M)$.
\end{thm}

We see from Theorem \ref{xw-1} that the answer to Open Problem
\ref{Con2} is positive by replacing the hypothesis ``$D'$ being
bounded" in Open Problem \ref{Con2} with the one ``$D'$ being
bounded and uniform".\medskip

The organization of this paper is as follows. The proof of Theorem
\ref{xw-1} will be given in Section \ref{sec-4}. In Section
\ref{sec-2}, some preliminaries are stated including a new lemma and
its proof.

\section{Preliminaries}\label{sec-2}

The {\it quasihyperbolic length} of a rectifiable arc or a path
$\alpha$ in the norm metric in $D$ is the number (cf.
\cite{GP,Vai3}):

$$\ell_k(\alpha)=\int_{\alpha}\frac{|dz|}{d_{D}(z)}.
$$

For each pair of points $z_1$, $z_2$ in $D$, the {\it quasihyperbolic distance}
$k_D(z_1,z_2)$ between $z_1$ and $z_2$ is defined in the usual way:
$$k_D(z_1,z_2)=\inf\ell_k(\alpha),
$$
where the infimum is taken over all rectifiable arcs $\alpha$
joining $z_1$ to $z_2$ in $D$. For all $z_1$, $z_2$ in $D$, we have
(cf. \cite{Vai3})

\begin{eqnarray}\label{eq(0000)} k_{D}(z_1, z_2)\geq
\inf\left\{\log\Big(1+\frac{\ell(\alpha)}{\min\{d_{D}(z_1), d_{D}(z_2)\}}\Big)\right\}\geq
\Big|\log \frac{d_{D}(z_2)}{d_{D}(z_1)}\Big|,\end{eqnarray}
where the infimum is taken over all rectifiable curves $\alpha$ in $D$ connecting $z_1$ and $z_2$.

In \cite{Vai6},  V\"ais\"al\"a characterized uniform domains by the quasihyperbolic metric.

\begin{Thm}\label{thm0.1} {\rm (\cite[Theorem 6.16]{Vai6})}
For a domain $D$, the following are quantitatively equivalent: \begin{enumerate}

\item $D$ is a $c$-uniform domain;
\item $k_D(z_1,z_2)\leq c'\;
 \log\left(1+\frac{\displaystyle{|z_1-z_2|}}{\displaystyle\min\{d_{D}(z_1),d_{D}(z_2)\}}\right)$ for all $z_1,z_2\in D$;
\item $k_D(z_1,z_2)\leq c'_1\;
 \log\left(1+\frac{\displaystyle{|z_1-z_2|}}{\displaystyle\min\{d_{D}(z_1),d_{D}(z_2)\}}\right)+d$ for all $z_1,z_2\in D$.\end{enumerate}
\end{Thm}

Gehring and Palka \cite{GP} introduced the quasihyperbolic metric of
a domain in ${\mathbb R}^n$ and it has been recently used by many authors
 in the study of quasiconformal mappings and related questions \cite{HIMPS}.
 In the case of domains in $ {\mathbb R}^n \,,$ the equivalence
  of items (1) and (3) in Theorem D is due to Gehring and Osgood \cite{Geo} and the
  equivalence of items (2) and (3) due to Vuorinen \cite{Mvo1}. Many of the
  basic properties of this metric may be found in \cite{Geo,Vai6-0, Vai6}.

Recall that an arc $\alpha$ from $z_1$ to
$z_2$ is a {\it quasihyperbolic geodesic} if
$\ell_k(\alpha)=k_D(z_1,z_2)$. Each subarc of a quasihyperbolic
geodesic is obviously a quasihyperbolic geodesic. It is known that a
quasihyperbolic geodesic between every pair of points in $E$ exists if the
dimension of $E$ is finite, see \cite[Lemma 1]{Geo}. This is not
true in arbitrary spaces (cf. \cite[Example 2.9]{Vai4}).
In order to remedy this shortage, V\"ais\"al\"a introduced the following concepts \cite{Vai6}.

\begin{defin} \label{def1.4} Let $\alpha$ be an arc in $E$. The arc may be
closed, open or half open. Let $\overline{x}=(x_0,...,x_n)$, $n\geq
1$, be a finite sequence of successive points of $\alpha$. For
$h\geq 0$, we say that $\overline{x}$ is {\it $h$-coarse} if
$k_D(x_{j-1}, x_j)\geq h$ for all $1\leq j\leq n$. Let
$\Phi_k(\alpha,h)$ be the family of all $h$-coarse sequences of
$\alpha$. Set

$$s_k(\overline{x})=\sum^{n}_{j=1}k_D(x_{j-1}, x_j)$$ and
$$\ell_{k_D}(\alpha, h)=\sup \{s_k(\overline{x}): \overline{x}\in \Phi_k(\alpha,h)\}$$
with the agreement that $\ell_{k}(\alpha, h)=0$ if
$\Phi_k(\alpha,h)=\emptyset$. Then the number $\ell_{k}(\alpha, h)$
is the {\it $h$-coarse quasihyperbolic length} of $\alpha$.\end{defin}

In this paper, we shall use this concept in the case where $D $ is a
domain equipped with the quasihyperbolic metric $k_D$. We always use
$\ell_k(\alpha, h)$ to denote the $h$-coarse quasihyperbolic length
of $\alpha$.

\begin{defin} \label{def1.5} Let $D$ be a domain in $E$. An arc $\alpha\subset D$
is {\it $(\nu, h)$-solid} with $\nu\geq 1$ and $h\geq 0$ if
$$\ell_k(\alpha[x,y], h)\leq \nu\;k_D(x,y)$$ for all $x, y\in \alpha$.
A {\it $(\nu,0)$-solid arc} is said to be a {\it $\nu$-neargeodesic}, i.e.
an arc $\alpha\subset D$ is a $\nu$-neargeodesic if and only if $\ell_k(\alpha[x,y])\leq \nu\;k_D(x,y)$
for all $x, y\in \alpha$.\end{defin}

Obviously, a $\nu$-neargeodesic is a quasihyperbolic geodesic if and
only if $\nu=1$.

In \cite{Vai4}, V\"ais\"al\"a got the following property concerning
the existence of neargeodesics in $E$.

\begin{Thm}\label{LemA} $($\cite[Theorem 3.3]{Vai4}$)$
Let $\{z_1,\, z_2\}\subset D$ and $\nu>1$. Then there is a
$\nu$-neargeodesic in $D$ joining $z_1$ and $z_2$.
\end{Thm}

The following result due to V\"ais\"al\"a is from \cite{Vai6}.

\begin{Thm}\label{LemB2} {\rm (\cite[Theorem 4.15]{Vai6})} For domains
$D\not= E$ and $D'\not=E'$, suppose that $f: D\to D'$ is $M$-QH. If
$\gamma$ is a $c$-neargeodesic in $D$, then the arc $\gamma'$ is
$c_1$-negardesic in $D'$ with $c_1$ depending only on $c$ and
$M$.\end{Thm}
\medskip

For convenience, in the following, we always assume that $x$, $y$, $z$, $\ldots$
denote points in $D$ and $x'$, $y'$, $z'$, $\ldots$
the images in $D'$ of $x$, $y$, $z$, $\ldots$
under $f$, respectively. Also we assume that $\alpha$, $\beta$, $\gamma$, $\ldots$
denote curves in $D$ and $\alpha'$, $\beta'$, $\gamma'$, $\ldots$  the images in $D'$ of
$\alpha$, $\beta$, $\gamma$, $\ldots$
under $f$, respectively.
\medskip

\section{Bilipschitz mappings} \label{sec-4}

First we introduce the following Theorems.

\begin{Thm}\label{ThmA}$($\cite[Theorem 7.18]{Vai6}$)$
Let $D$ and $D'$ be domains in $E$ and $E'$, respectively. Suppose
that $D$ is a $c$-uniform domain and that $f:D\to D'$ is
$\varphi$-FQC $($see Section \ref{sec-2} for the definition$)$. Then
the following conditions are quantitatively equivalent:

$(1)$ $D'$ is a $c_1$-uniform domain;

$(2)$ $f$ is $\eta$-quasim\"obius.
\end{Thm}

\begin{Thm}\label{thm1.1} $($\cite[Theorem 1.1]{Ml-1}$)$
Suppose that $D$ is a $c$-uniform domain and that $f: D\to D'$ is
$(M,C)$-CQH, where $D\varsubsetneq E$ and $D'\varsubsetneq E'$. Then
the following conditions are quantitatively equivalent:

$(1)$ $D'$ is a $c_1$-uniform domain;

$(2)$  $f$ extends to a homeomorphism $\overline{f}: \overline{D}\to
\overline{D}'$ and $\overline{f}$ is $\eta$-QM rel $\partial D$.
\end{Thm}

The following theorem easily follows from Theorems \Ref{ThmA} and
\Ref{thm1.1}.

\begin{thm}\label{li-mz-1}
Suppose that $D\varsubsetneq E$ and $D'\varsubsetneq E'$, that $D$
is a $c$-uniform domain, and that $f:D\to D'$ is $\varphi$-FQC. Then
the following conditions are quantitatively equivalent:

$(1)$ $D'$ is a $c_1$-uniform domain;

$(2)$ $f$ is $\theta$-quasim\"obius;

$(3)$  $f$ extends to a homeomorphism $\overline{f}: \overline{D}\to
\overline{D}'$ and $\overline{f}$ is $\theta_1$-QM rel $\partial D$.
\end{thm}

Let us recall the following three theorems which are useful in the
proof of Theorem \ref{xw-1}.

\begin{Thm}\label{XT-0}$($\cite[Theorem 2.44]{Vai5}$)$
Suppose that $G\varsubsetneq E$ and $G'\varsubsetneq E'$ is a
$c$-uniform domain, and that $f: G\to G'$ is  $M$-QH. If $D\subset
G$  is a $c$-uniform domain, then $D'=f(D)$ is a $c'$-uniform domain
with $c'=c'(c,M)$
\end{Thm}

\begin{Thm}\label{XT-2}$($\cite[Theorem 6.19]{Vai6}$)$
Suppose that $D\varsubsetneq E$ is a $c$-uniform domain and that
$\gamma$ is a $c_1$-neargeodesic in $D$ with endpoints $z_1$ and
$z_2$. Then there is a constant $b=b(c,c_1)\geq 1$ such that

\begin{enumerate}
\item\label{xw-2-1} $\displaystyle\min_{j=1,2}\ell (\gamma [z_j, z])\leq b\,d_{D}(z)
$ for all $z\in \alpha$, and

\item\label{xw-2-2} $\ell(\gamma)\leq b\,|z_{1}-z_{2}|$.
\end{enumerate}
\end{Thm}

\begin{Thm}\label{lem-m-1} $($\cite[Theorem 1.2]{Yli}$)$ Suppose that $D_1$ and $D_2$ are convex domains in $E$,
where $D_1$ is bounded and $D_2$ is $c$-uniform for some $c>1$, and
that there exist $z_0\in D_1\cap D_2$ and $r>0$ such that
${\mathbb B}(z_0,r) \subset D_1\cap D_2$. If there exist constants $R_1>0$
and $c_0>1$ such that $R_1 \leq c_0r$ and $D_1\subset
\overline{{\mathbb B}}(z_0,R_1)$, then $D_1\cup D_2$ is a $c'$-uniform
domain with $c'=(c+1)(2c_0+1)+c$.\end{Thm}
\medskip

\noindent {\bf Basic assumption A}\quad In this paper, we always
assume that $D$ and $D'$ are bounded domains with connected
boundaries in $E$ and $E'$, respectively, that $f: D\to D'$ is
$M$-QH, that $f$ extends to a homeomorphism $\overline{f}:
\overline{D}\to \overline{D'}$ such that $\overline{f}|_{\partial
D}$ is $M$-bilipschitz, and that $D'$ is a $c$-uniform
domain.\medskip

Before the proof  of Theorem \ref{xw-1}, we prove a series of lemmas.

\begin{lem}\label{mz-1-0}
There is a constant $M_0=M_0(M)>M$ such that for all $z_1$, $z_2\in
D$ satisfying ${\operatorname{dist}}(z_1,
\partial D)\leq \varepsilon$ and ${\operatorname{dist}}(z_2,
\partial D)\leq \varepsilon$ with sufficient small
$\varepsilon>0$, $$\frac{1}{M_0}|z_1-z_2|\leq |z'_1-z'_2|\leq
M_0|z_1-z_2|.$$
\end{lem}

\begin{pf} Let $x_1$, $x_2\in \partial D$ be such that $|z_1-x_1|=
\frac{4}{3}{\operatorname{dist}}(z_1,
\partial D)$, $|z_2-x_2|\leq \frac{4}{3}{\operatorname{dist}}(z_2,
\partial D)$  and
$|x_1-x_2|\leq\max\{|z_1-x_1|, |z_2-x_2|\}<3|x_1-x_2|$ for
sufficient small $\varepsilon>0$. It follows from $``f$ being $M$-QH
in $D$ and homeomorphic in $\overline{D}$" that $H(x,f)\leq K$ (cf.
\cite{Vai5}) for each $x\in D$, where $K$ depends only on $M$.
Hence,

$$|z'_1-x'_1|<\frac{3}{2}K|x'_1-x'_2|\,\mbox{and}\,|z'_2-x'_2|<\frac{3}{2}K|x'_1-x'_2|.$$

If $|z_1-z_2|\leq \frac{1}{4K^2M}\max\{|z_1-x_1|, |z_2-x_2|\}$, then
for each $z\in [z_1,z_2]$, $$d_D(z)\geq
\frac{3K^2M-1}{4K^2M}\max\{|z_1-x_1|, |z_2-x_2|\},$$ and so we have
\begin{eqnarray*}
\frac{2|z'_1-z'_2|}{\min\{d_{D'}(z'_1),d_{D'}(z'_2)\}}&\leq&\log\Big(1+\frac{|z'_1-z'_2|}{\min\{d_{D'}(z'_1),d_{D'}(z'_2)\}}\Big)\\
\nonumber&\leq&
k_{D'}(z'_1,z'_2)\leq Mk_D(z_1,z_2)\\
\nonumber&\leq&M\int_{[z_1,z_2]}\frac{|dz|}{d_D(z)}
\\
\nonumber&\leq& \frac{4K^2M^2|z_1-z_2|}{(3K^2M-1)\max\{|z_1-x_1|,
|z_2-x_2|\}},\end{eqnarray*} which shows that $$|z'_1-z'_2|\leq
\frac{12K^3M^3}{3K^2M-1}|z_1-z_2|.$$

If $|z_1-z_2|> \frac{1}{4K^2M}\max\{|z_1-x_1|, |z_2-x_2|\}$, then by
the assumption $``f$ being $M$-bilipschitz in $\partial D$",
\begin{eqnarray*}|z'_1-z'_2|&\leq& |z'_1-x'_1|+|z'_2-x'_2|+|x'_1-x'_2|
\\ \nonumber&\leq& (3K+1)|x'_1-x'_2|
\\ \nonumber&\leq& (3K+1)M|x_1-x_2|\\ \nonumber&\leq& (12K+4)K^2M^2|z_1-z_2|.
\end{eqnarray*}
The same discussion as above shows that $$|z_1-z_2|\leq
(12K+4)K^2M^2|z'_1-z'_2|.$$\end{pf}

\begin{lem}\label{mz-1-1}
There is a constant $M_1=M_1(c,M)$ such that for all $x\in D$ and
$z\in \mathbb{S}(x, d_D(x))\cap \overline{D}$ satisfying ${\operatorname{dist}}(z,
\partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$, $$|z'-x'|\leq M_1d_{D}(x).$$
\end{lem}

\begin{pf} Let $x_0\in \mathbb{S}(x,d_{D}(x))\cap \overline{D}$ such that
${\operatorname{dist}}(x_0, \partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$, and let $x_2$ be the intersection point of
$\mathbb{S}(x_0, \frac{1}{2}d_{D}(x))$ with $[x_0, x]$. Then we have
$$k_{D}(x_2,x)\leq
\log\Big(1+\frac{|x-x_2|}{d_{D}(x)-|x-x_2|}\Big)\leq \log
\frac{d_{D}(x)}{d_{D}(x_2)}=\log 2,$$ which implies that

$$\log\frac{|x'_2-x'|}{|x'_2-x'_0|}\leq k_{D'}(x'_2,x')\leq Mk_{D}(x_2,x)=M\log 2.$$ Hence
\begin{equation}\label{mh-0}|x'_2-x'|\leq 2^M |x'_2-x'_0|,\end{equation} \noindent and so
\begin{equation}\label{mh-1}|x'-x'_0|\leq|x'-x'_2|+|x'_2-x'_0|
\leq(2^M+1)|x'_2-x'_0|.\end{equation}

Let $T$ be a $2$-dimensional linear subspace of $E$ which contains
$x_0$ and $x_2$, and we use $\tau$ to denote the circle $T\cap \mathbb{S}(x_0,
\frac{1}{2}d_{D}(x))$. Take $w_1\in \tau\cap
\partial D$ such that $\tau(x_2, w_1)\subset D$ and
$\ell(\tau[x_2,w_1])\leq 2d_D(x)$. Let $x_1\in \mathbb{S}(x,
d_{D}(x))\cap \tau[x_2,w_1]\cap \overline{D}$ and denote $\tau(x_1,
w_1)$ by $\tau_1$.

\begin{claim}\label{xt-1-1'} There must exist a $2^{32}$-uniform domain $D_1$
in $D$ and $x_3\in \partial D_1\cap \overline{D}$ satifying
${\operatorname{dist}}(x_3,
\partial D)\leq \varepsilon$ for sufficient small $\varepsilon>0$
such that $x_0$, $x\in \overline{D}_1$ and $\frac{1}{12}d_{D}(x)\leq
|x_3-x_0|\leq \frac{11}{12}d_{D}(x)$.\end{claim}

If $d_{D}(x_1)=0$, then we take $D_1=\mathbb{B}(x,d_{D}(x))$ and
$x_3=x_1$.  Obviously, $ |x_3-x_0|= \frac{1}{2}d_{D}(x)$. Hence
Claim \ref{xt-1-1'} holds true in this case.

If $d_{D}(x_1)>0$, we divide the proof of Claim \ref{xt-1-1'} into
two parts.

\begin{case}\label{li-1} $d_{D}(x_1)\leq \frac{5}{12}d_{D}(x)$.\end{case}

Then we take $D_1=\mathbb{B}(x, d_{D}(x))\cup \mathbb{B}(x_1,
d_{D}(x_1))$ and $x_3\in \mathbb{S}(x_1, d_{D}(x_1))\cap
\overline{D}$ such that ${\operatorname{dist}}(x_3, \partial D)\leq \varepsilon$ for
sufficient small $\varepsilon>0$. It follows from Theorem
\Ref{lem-m-1} that $D_1$ is a $29$-uniform domain and
$$\frac{1}{12}d_{D}(x)\leq |x_1-x_0|-|x_1-x_3|\leq|x_3-x_0|\leq |x_1-x_0|+|x_1-x_3|\leq\frac{11}{12}d_{D}(x),$$
from which we see that Claim \ref{xt-1-1'} is true.

\begin{case}\label{li-1'} $d_{D}(x_1)> \frac{5}{12}d_{D}(x)$.\end{case}

Obviously, $d_{D}(x_1)> \frac{5}{6}|x_1-x_0|$. We let $w_2\in
\tau_1$ be the first point along the direction from $x_1$ to $w_1$
such that \begin{equation}\label{mh-4}d_{D}(w_2)= \frac{5}{12}d_{D}(x).\end{equation}

If $|w_2-x_1|\leq \frac{1}{3}d_D(x)$, then we take
$D_1=\mathbb{B}(x, d_D(x))\cup \mathbb{B}(w_2, d_D(w_2))$, and
 let $x_3\in \mathbb{S}(w_2, d_{D}(w_2))\cap \overline{D}$ such that
${\operatorname{dist}}(x_3, \partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$.
 Then \begin{equation}\label{xv-1} \displaystyle d_D(w_2)+d_D(x)-|w_2-x|\ge d_D(w_2)-|w_2-x_1|\ge
\frac{1}{12}d_D(x)\end{equation}
 and \begin{equation}\label{xv-2}
 \frac{1}{12}d_{D}(x)\leq |x_3-x_0|\leq
 |w_2-x_0|+|w_2-x_3|\leq\frac{11}{12}d_{D}(x).\end{equation}

It follows from Theorem \Ref{lem-m-1} that $D_1$ is a $677$-uniform
domain, which shows that Claim \ref{xt-1-1'} is true.

If $|w_2-x_1|> \frac{1}{3}d_D(x)$, then we first prove the following
subclaim.

\begin{subclaim}\label{xm-1} There exists a simply connected domain
$D_1=\bigcup \limits_{i=0}^{t}B_i$ in $D$, where $t=1$ or $2$, such
that
\begin{enumerate}
\item  $x_0$, $x\in \overline{D}_1$;
\item  For each $i\in \{0,\cdots, t\}$,  $\frac{5}{12}\,d_D(x)\leq
r_i\leq d_D(x)$;
\item If $t=2$, then $\displaystyle |x-w_2|-r_0-r_2\ge
\frac{1}{144}d_D(x)$; and
\item  $\displaystyle r_i+r_{i+1}-|v_i-v_{i+1}|\ge
\frac{1}{144}d_D(x)$, where $i\in\{0,1\}$ if
$t=2$ or $i=0$ if $t=1$.
\end{enumerate}
Here $B_i=\mathbb{B}(v_i, r_i)$, $v_i\in \tau[x_2,w_2]$, $v_1\not\in
B_0$ and $v_2\not\in \tau[x_2,v_1]$.\end{subclaim}

To prove this subclaim, we let $y_2\in \tau_1$ be such that
$|x_1-y_2|=\frac{1}{3}d_D(x)$, and let $C_0=\mathbb{B}(x,d_D(x))$
and $C_1=\mathbb{B}(y_2, d_D(y_2))$. Since $d_D(y_2)>
\frac{5}{12}d_D(x)$, we have \begin{equation}\label{xv-3}\displaystyle
d_D(y_2)+d_D(x)-|y_2-x|\ge \frac{1}{12}d_D(x).\end{equation}

Next, we construct a ball denoted by $C_2$:

 If
$w_2\in \overline{C}_1$, then we let $C_2=\mathbb{B}(w_2,d_D(w_2))$.

If $w_2\not\in \overline{C}_1$, then we let $y_3$ be the
intersection of $\mathbb{S}(y_2, d_D(y_2))$ with $\tau_1[y_2, w_1]$.
Since $\ell(\tau_1)\leq 2d_D(x)$ and $d_D(z)\geq \frac{5}{12}d_D(x)$
for all $z\in \tau_1(x_1,x_2)$, we have
$$|w_1-w_2|+|w_2-y_3|+|y_3-y_2|+|y_2-x_1|+|x_2-x_1|\leq
 \ell(\tau_1) \leq  2d_D(x),$$ which implies that
\begin{equation}\label{xv-4}|w_2-y_3|\leq
 \frac{1}{3}d_D(x).\end{equation}  We take $C_2=\mathbb{B}(w_2,d_D(w_2))$.
Then (\ref{xv-4}) implies \begin{equation}\label{xv-5}
d_D(w_2)+d_D(x_2)-|x_2-w_2|\ge
d_D(w_2)-|w_2-y_3|\ge\frac{1}{12}d_D(x).\end{equation}

Now we are ready to construct the needed domain $D_1$. \medskip

If $d_{D}(w_2)+d_D(x)-|w_2-x|\geq \frac{1}{48}d_{D}(x)$, then we
take $B_0=C_0$, $B_1=C_2$ and $D_1=B_0\cup B_1$ with $v_0=x$,
$v_1=w_2$, $r_0=d_D(x)$ and $r_1=d_D(w_2)$. Obviously, $D_1$
satisfies all the conditions in Subclaim \ref{xm-1}. In this case,
$t=1$.

 If
$d_{D}(w_2)+d_D(x)-|w_2-x|< \frac{1}{48}d_{D}(x)$, then we take
$B_0=\mathbb{B}(x, \frac{35}{36}d_{D}(x))$ with
$r_0=\frac{35}{36}d_{D}(x)$ and $v_0=x$, $B_1=C_1$ with
$r_1=d_D(y_2)$ and $v_1=y_2$, and $B_2=C_2$ with $r_2=d_D(w_2)$ and
$v_2=w_2$. Then Inequalities (\ref{xv-3}) and (\ref{xv-5}) show that
$D_1=\bigcup_{i=0}^{2}B_i$ satisfies all the conditions in Subclaim
\ref{xm-1}. In this case, $t=2$.

Hence the proof of Subclaim \ref{xm-1} is complete. \medskip

 It follows from a similar argument as in the proof of
\cite[Theorem $1.1$]{Ml} that

\begin{cor}\label{cor-0}
The domain $D_1$ constructed in Subclaim \ref{xm-1} is a
$2^{32}$-uniform domain.
\end{cor}

Let $x_3\in \mathbb{S}(w_2, d_{D}(w_2)\cap\overline{D}$ such that
${\operatorname{dist}}(x_3, \partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$. Then \begin{equation}\label{mh-5}\frac{1}{12}d_{D}(x)\leq
|x_3-x_0|\leq \frac{11}{12}d_{D}(x).\end{equation} Then the proof of Claim
\ref{xt-1-1'} easily follows from (\ref{mh-5}), Subclaim \ref{xm-1}
and Corollary \ref{cor-0}.\medskip

We come back to the proof of Lemma \ref{mz-1-1}. It follows from
(\ref{mh-5}) and Lemma \ref{mz-1-0} that \begin{equation}\label{mh-6'}|x-x_3|\leq
|x-x_0|+|x_0-x_3|\leq \frac{23}{12}d_D(x)\end{equation} and
\begin{equation}\label{mh-6}\frac{1}{12M_0}d_{D}(x)\leq
\frac{1}{M_0}|x_3-x_0|\leq |x'_3-x'_0|\leq M_0|x_3-x_0|\leq
\frac{11M_0}{12}d_{D}(x).\end{equation} Then it follows from Theorem \Ref{XT-0}
that $D'_1$ is an $M'$-uniform domain, where $M'=M'(c,M)$.  Hence we
know from Theorem \ref{li-mz-1} that $f^{-1}$ is a
$\theta$-Quasim\"obius in $\overline{D}_1$, where
$\theta=\theta(c,M)$, and so (\ref{mh-0}), (\ref{mh-1}),
(\ref{mh-5}), (\ref{mh-6'}) and (\ref{mh-6}) imply that
$$\frac{1}{23}\leq\frac{|x_3-x_0|}{|x_2-x_0|}\cdot\frac{|x_2-x|}{|x-x_3|}\leq
\theta
\Big(\frac{|x'_3-x'_0|}{|x'_2-x'_0|}\cdot\frac{|x'_2-x'|}{|x'-x'_3|}\Big)\leq
\theta\Big(\frac{M_02^{M+1}d_D(x)}{|x'-x'_3|}\Big) ,$$  which,
together with (\ref{mh-1}), shows
$$|x'-x'_0|\leq |x'-x'_3|+|x'_3-x'_0|\leq (\frac{2^{M+1}}{\theta^{-1}(\frac{1}{23})}+\frac{11M_0}{12})d_D(x)< \frac{2^{M_0+2}}{\theta^{-1}(\frac{1}{23})}d_D(x).$$
Thus the proof of Lemma \ref{mz-1-1} is complete.\end{pf}

\begin{lem}\label{mz-1-1'}
For all $x\in D$, if $z\in \mathbb{S}(x, d_D(x))\cap \overline{ D}$
such that ${\operatorname{dist}}(x, \partial D)\leq \varepsilon$ for sufficient
small $\varepsilon>0$, then $|z'-x'|\geq \frac{1}{e^{4M_0M_1^2}}
d_{D}(x)$, where $M_1=M_1(c,M)$.
\end{lem}

\begin{pf}  Suppose on the contrary that there exist points $x_1\in D$ and
$y_1\in \mathbb{S}(x_1,d_{D}(x_1))\cap \overline{ D}$ with
${\operatorname{dist}}(y_1,\partial D)\leq \varepsilon$ for sufficient small $\varepsilon>0$
such that
\begin{equation}\label{li-xt-0'}|x'_1-y'_1|<
\frac{1}{e^{4M_0M_1^2}}|x_1-y_1|.\end{equation}

We take $y_2\in \mathbb{S}(y_1, d_D(x_1))\cap \overline{ D}$ such
that ${\operatorname{dist}}(y_2, \partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$. From Lemma \ref{mz-1-0} that we know
$$|y'_1-y'_2|\geq \frac{1}{M_0}|y_1-y_2|= \frac{1}{M_0}d_D(x_1).$$

 Let $T_1$ be a
$2$-dimensional linear subspace of $E$ determined by  $x_1$, $y_1$
and $y_2$, and  $\omega$ the circle $T_1\cap \mathbb{S}(y_1,
d_{D}(x_1))$. We take $y_3\in \omega\cap \partial D$ which satisfies
$\omega(x_1, y_3)\subset D$ and $\ell(\omega[x_1,y_3])\leq
4d_D(x_1)$. Let $\omega_1=\omega(x_1, y_3)$ and $w_1$ be the first
point along the direction from $x_1$ to $y_3$ such that $$d_D(w_1)=
\frac{1}{4M_0M_1}d_D(x_1).$$

Let $v_1\in \mathbb{S}(w_1,d_{D}(w_1))\cap \overline{ D}$ such that
${\operatorname{dist}}(w_1, \partial D)\leq \varepsilon$ for sufficient small
$\varepsilon>0$. Then it follows from Lemma \ref{mz-1-1} that
$$d_{D'}(w'_1)\leq|w'_1-v'_1|\leq M_1d_D(w_1)=\frac{1}{4M_0}d_D(x_1),$$ which,
together with  Lemmas \ref{mz-1-0} and \ref{mz-1-1} and
(\ref{li-xt-0'}),
 implies that
\begin{eqnarray*}
|x'_1-w'_1|&\geq& |y'_1-v'_1|-|x'_1-y'_1|-|v'_1-w'_1|\\ &\geq&
\frac{1}{M_0}|y_1-v_1|-\frac{1}{e^{4M_0M_1^2}}|x_1-y_1|-M_1|v_1-w_1|
\\ &\geq&
\frac{1}{M_0}(d_D(x_1)-d_D(w_1))-\frac{1}{e^{4M_0M_1^2}}|x_1-y_1|-M_1|v_1-w_1|\\
&>&\frac{1}{2M_0}d_D(x_1).\end{eqnarray*} Hence we infer from
(\ref{li-xt-0'}) that \begin{equation}\label{li-xt-4}k_{D'}(x'_1, w'_1)\geq \log
\Big(1+\frac{|x'_1-w'_1|}{d_{D'}(x'_1)}\Big)> M_1^2.\end{equation}

Since $\ell(\omega_1)\leq 4d_D(x_1)$, by the choice of $w_1$, we
have
$$k_D(x_1,w_1)\leq\int_{\omega_1[x_1,w_1]}\frac{|dx|}{d_D(x)}\leq 16M_0M_1,$$
whence $$k_{D'}(x'_1,w'_1)\leq Mk_D(x_1,w_1)\leq 16MM_0M_1,$$ which
contradicts with (\ref{li-xt-4}). The proof of Lemma \ref{mz-1-1'}
is complete.\end{pf}

\begin{lem}\label{mz-1-2}
For  $x_1\in D$ and $x_2\in \partial D$, we have
$$|x'_1-x'_2|\leq M_2|x_1-x_2|,$$ where $M_2=2M_0+M_1$.
\end{lem}

\begin{pf} For $x_1\in D$, we let $y_1\in \mathbb{S}(x_1,d_{D}(x_1))\cap
\overline{ D}$ such that ${\operatorname{dist}}(y_1, \partial D)\leq \varepsilon$
for sufficient small $\varepsilon>0$. Then it follows from Lemma
\ref{mz-1-1} that \begin{equation}\label{mh-7}|x'_1-y'_1|\leq M_1|x_1-y_1|.\end{equation}

For $x_2\in \partial D$, if $|y_1-x_2|\leq 2 |x_1-y_1|$, then by
Lemma \ref{mz-1-0}, we have
\begin{eqnarray*} |x'_1-x'_2|&\leq&
|x'_1-y'_1|+|y'_1-x'_2|\\ \nonumber &\leq& M_1|x_1-y_1|+M_0|y_1-x_2|\\ \nonumber &\leq&(2M_0+M_1)|x_1-y_1|\\
\nonumber &\leq& (2M_0+M_1)|x_1-x_2|.\end{eqnarray*}

If $|y_1-x_2|>2|y_1-x_1|$, then we have
$$|x_1-x_2|>|y_1-x_2|-|x_1-y_1|>\frac{1}{2}|y_1-x_2|.$$ Hence by
Lemma \ref{mz-1-0} and (\ref{mh-7}), \begin{eqnarray*}
|x'_1-x'_2|&\leq&
|x'_1-y'_1|+|y'_1-x'_2|\\ \nonumber &\leq& M_1|x_1-y_1|+M_0|y_1-x_2|\\
\nonumber &\leq& (2M_0+M_1)|x_1-x_2|,\end{eqnarray*} from which the
proof follows. \end{pf}

\begin{lem}\label{mz-1-3}
For  $x_1\in D$ and $x_2\in \partial D$, we have
$$|x'_1-x'_2|\geq \frac{1}{M_3}|x_1-x_2|,$$ where $M_3=2M_0M_1e^{(5MM_0+8M_0)M_1^2}$.
\end{lem}

\begin{pf} We begin with a claim.

\begin{claim}\label{li-xt-5} For all $z\in D$, we have $d_{D'}(z')\geq
\frac{1}{e^{(5MM_0+8M_0)M_1^2}} d_{D}(z).$\end{claim}

To prove this claim, we let $w_2\in [z,y_1]$ be such that
$|w_2-y_1|= \frac{1}{2M_1e^{4M_0M_1^2}}d_D(z)$. It follows from
\cite{Mvo1} that
$$k_D(w_2,z)\leq\log \Big(1+\frac{|w_2-z|}{d_D(z)-|w_2-z|}\Big)<5M_0M_1^2.$$
By Lemma \ref{mz-1-1}, we have
$$|w'_2-y'_1|\leq M_1 |w_2-y_1|= \frac{1}{2e^{4M_0M_1^2}}d_D(z).$$
Hence Lemma \ref{mz-1-1'} implies $|w'_2-z'|\geq
\frac{1}{2e^{4M_0M_1^2}}d_D(z),$ whence
$$\log \frac{|w'_2-z'|}{d_{D'}(z')}\leq k_{D'}(w'_2,z')\leq
Mk_D(w_2,z)\leq 5MM_0M_1^2,$$ which shows that Claim \ref{li-xt-5}
is true.
\medskip

Now we are ready to finish the proof of Lemma \ref{mz-1-3}. For $x_1\in D$ and
$x_2\in
\partial D$, if $|x_1-x_2|\leq 2M_0M_1d_D(x_1)$, then by Claim \ref{li-xt-5},
$$|x'_1-x'_2|\geq d_{D'}(x'_1)\geq\frac{1}{e^{(5MM_0+8M_0)M_1^2}}
d_{D}(x_1)\geq \frac{1}{2M_0M_1e^{(5MM_0+8M_0)M_1^2}}|x_1-x_2|.$$

If $|x_1-x_2|>  2M_0M_1d_D(x_1)$, then we take $w_3\in
\mathbb{S}(x_1, d_D(x_1))\cap \overline{ D}$ such that ${\operatorname{dist}}(w_3,
\partial D)\leq \varepsilon$ for sufficient small $\varepsilon>0$,
and so
$$|w_3-x_2|\geq |x_1-x_2|-|x_1-w_3|\geq \Big(1-\frac{1}{
 2M_0M_1}\Big)|x_1-x_2|$$
 and $$|w_3-x_2|\geq |x_1-x_2|-|x_1-w_3|\geq (2M_0M_1-1)|x_1-w_3|,$$
whence Lemmas \ref{mz-1-0} and \ref{mz-1-1} implies
 \begin{eqnarray*} |x'_1-x'_2|&\geq&|w'_3-x'_2|-|x'_1-w'_3|\\
 &\geq& \frac{1}{M_0}|w_3-x_2|-M_1|x_1-w_3|\\
 &\geq& \Big(\frac{1}{M_0}-\frac{M_1}{2M_0M_1-1}\Big)|w_3-x_2|
 \\
 &\geq& \frac{1}{3M_0}|x_1-x_2|,\end{eqnarray*}
from which the proof is complete. \end{pf}

By the above lemmas, we get the following result.

\begin{lem}\label{mz-1-4}
$D$ is a $c_1$-uniform domain, where $c_1=c_1(c,M)$.
\end{lem}

\begin{pf} We first prove that $f^{-1}$ is  $\theta_1$-Quasim\"obius rel
$\partial D'$, where $\theta_1(t)=(M_2M_3)^2t$, $M_2$ and $M_3$ are
the same as in Lemma \ref{mz-1-2} and Lemma \ref{mz-1-3},
respectively. By definition, it is necessary to prove that for
$x'_1$, $x'_2$, $x'_3$, $x'_4\in \overline{D'}$, \begin{eqnarray}\label{Fri-1}
\frac{|x_4-x_1|}{|x_4-x_2|}\cdot\frac{|x_2-x_3|}{|x_1-x_3|}
  &\leq& (M_2M_3)^2\frac{|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{|x'_2-x'_3|}{|x'_1-x'_3|},\end{eqnarray} where $x_1,x_2\in
\partial D'$. Obviously, to prove Inequality \ref{Fri-1}, we only
need to consider the following three cases.

\begin{case}\label{mz-li-xt-1-1''}$x'_1,x'_2,x'_3, x'_4\in
\partial D'$.\end{case}

Since $f$ is $M$-bilipschitz in $\partial D$, we have
\begin{eqnarray*}\frac{|x_4-x_1|}{|x_4-x_2|}\cdot\frac{|x_2-x_3|}{|x_1-x_3|}
  &\leq& M^4\frac{|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{|x'_2-x'_3|}{|x'_1-x'_3|}.\end{eqnarray*}

\begin{case}\label{mz-li-xt-1-1'}$x'_1$, $x'_2$, $x'_3\in \partial D'$ and
$x'_4\in D'$.\end{case}

It follows from Lemmas \ref{mz-1-2} and \ref{mz-1-3} that
\begin{eqnarray*}\frac{|x_4-x_1|}{|x_4-x_2|}\cdot\frac{|x_2-x_3|}{|x_1-x_3|}
 &\leq& \frac{M_2M_3|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{M^2|x'_2-x'_3|}{|x'_1-x'_3|}
  \\ &\leq& M^2M_2M_3\frac{|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{|x'_2-x'_3|}{|x'_1-x'_3|}.\end{eqnarray*}

\begin{case}\label{mz-li-xt-2} $x'_1$, $x'_2\in \partial D'$ and $x'_3,
x'_4\in D'$.\end{case}

We obtain from Lemmas \ref{mz-1-2} and \ref{mz-1-3} that
\begin{eqnarray*}\frac{|x_4-x_1|}{|x_4-x_2|}\cdot\frac{|x_2-x_3|}{|x_1-x_3|}
 &\leq& \frac{M_2M_3|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{M_2M_3|x'_2-x'_3|}{|x'_1-x'_3|}
  \\ &\leq& (M_2M_3)^2\frac{|x'_4-x'_1|}{|x'_4-x'_2|}\cdot\frac{|x'_2-x'_3|}{|x'_1-x'_3|}.\end{eqnarray*}

The combination of Cases \ref{mz-li-xt-1-1''} $\sim$
\ref{mz-li-xt-2} shows that Inequality \eqref{Fri-1} holds, which
implies that $f^{-1}$ is a $\theta_1$-Quasim\"obius rel $\partial
D'$. Hence Theorem \ref{li-mz-1} shows that $D$ is a $c_1$-uniform
domain, where $c_1$ depends only on $c$ and $M$. \end{pf}

\subsection{ The proof of Theorem \ref{xw-1}} For any $z_1$,
$z_2\in \overline{D}$, it suffices to prove that
\begin{eqnarray}\label{Sat-2} \frac{1}{M'}|z_1-z_2|\leq |z'_1-z'_2|\leq M'|z_1-z_2|,\end{eqnarray} where
$M'$ depends only on $c$ and $M$.

It follows from the hypothesis ``$f$ being $M$-bilipschitz in $\partial D$", Lemmas
\ref{mz-1-2} and \ref{mz-1-3} that we only need to consider the case
$z_1$, $z_2\in D$.

If $|z_1-z_2|\leq \frac{1}{2}\max\{d_D(z_1), d_D(z_2)\}$, then
$$k_D(z_1,z_2)\leq \int_{[z_1,z_2]}\frac{|dx|}{d_D(x)}\leq \frac{2|z_1-z_2|}{\max\{d_D(z_1), d_D(z_2)\}}\leq 1,$$
which shows that $$\log\Big(1+\frac{|z'_1-z'_2|}{\min\{d_{D'}(z'_1),
d_{D'}(z'_2)\}}\Big)\leq k_{D'}(z'_1,z'_2)\leq Mk_D(z_1,z_2)\leq
M,$$
and so \begin{eqnarray}\label{mh-12}\frac{|z'_1-z'_2|}{e^M\min\{d_{D'}(z'_1),
d_{D'}(z'_2)\}}&\leq&
\log\Big(1+\frac{|z'_1-z'_2|}{\min\{d_{D'}(z'_1),
d_{D'}(z'_2)\}}\Big)\\ \nonumber&\leq&
\frac{2M|z_1-z_2|}{\max\{d_D(z_1), d_D(z_2)\}}.\end{eqnarray} We see from
Lemma \ref{mz-1-1} that $$\min\{d_{D'}(z'_1), d_{D'}(z'_2)\}\leq
M_1\max\{d_D(z_1), d_D(z_2)\}.$$
Then (\ref{mh-12}) implies that \begin{equation}\label{mh-14}|z'_1-z'_2|\leq
2MM_1e^M|z_1-z_2|.\end{equation}

For the other case $|z_1-z_2|> \frac{1}{2}\max\{d_D(z_1),
d_D(z_2)\}$, we let $\beta$ be a $2$-neargeodesic joining $z_1$ and
$z_2$ in $D$. It follows from Theorem \Ref{LemB2} that $\beta'$ is a
$c_2$-neargeodesic, where $c_2$ depends only on $M$. Let
$z'\in\beta'$ such that
$$|z'_1-z'|=\frac{1}{2}|z'_1-z'_2|.$$ Then we know from
$|z'_2-z'|\geq \frac{1}{2}|z'_1-z'_2|$ and Theorem \Ref{XT-2} that
\begin{eqnarray}\label{li-x-1}|z'_1-z'_2|&\leq& 2\min\{|z'_1-z'|, |z'_2-z'|\}\\
\nonumber&\leq& 2\min\{{\operatorname{diam}}(z'_1,z'), {\operatorname{diam}}(z'_2,z')\}\\
\nonumber&\leq& 2\mu d_{D'}(z'),\end{eqnarray} where $\mu$ depends only on $c$
and $M$.

We claim that \begin{equation}\label{mh-13}d_D(z)\leq 3\ell(\beta).\end{equation} Otherwise,
$$\max\{d_D(z_1),
d_D(z_2)\}\geq d_D(z)-\max\{|z_1-z|, |z_2-z|\}> 2\ell(\beta)\geq
2|z_1-z_2|.$$ This is the desired contradiction.

By Theorem \Ref{XT-2} and Lemma \ref{mz-1-4}, we have $$d_{D}(z)\leq
3 \ell(\beta)\leq 3b|z_1-z_2|,$$ where $b=b(c_1)$. Hence Lemma
\ref{mz-1-1} and (\ref{li-x-1}) show that
\begin{equation}\label{mh-15}|z'_1-z'_2|\leq 2\mu d_{D'}(z')\leq
6bM_1\mu|z_1-z_2|.\end{equation}

By Lemma \ref{mz-1-4}, we see that $D$ is a $c_1$-uniform domain.
Hence a similar argument as in the proofs of Inequalities
(\ref{mh-14}) and (\ref{mh-15}) yields that \begin{eqnarray}
\label{Sat-1}|z_1-z_2|\leq M_4|z'_1-z'_2|,\end{eqnarray} where $M_4=M_4(c,M)$.

Obviously, the inequalities \eqref{mh-14}, \eqref{mh-15} and
\eqref{Sat-1} show that \eqref{Sat-2} holds, and thus the proof of
the theorem is complete. \qed