\section{Introduction}
\subsection{Dirac-type problems}
Arguably the two most studied objects in graph theory are \emph{perfect matchings} and \emph{Hamilton cycles}. A perfect matching in a graph $G=(V,E)$ is a collection of vertex-disjoint edges which covers $V$, and a Hamilton cycle is a cycle passing through all the vertices of $G$.
As opposed to the problem of finding a perfect matching (if one exists) in a graph $G$ which has efficient (polynomial-time) resolutions, the analogous problem for Hamilton cycles is listed as one of the NP-hard problems by Karp \cite{karp1972reducibility}.  Therefore, as one cannot hope to find a Hamilton cycle efficiently, it is natural to study sufficient conditions which guarantee its existence.

One of the first results of this type is the celebrated theorem by Dirac \cite{dirac1952some}, which states that every graph on $n\geq 3$ vertices with minimum degree $\frac{n}{2}$ is \emph{Hamiltonian}, that is, contains a Hamilton cycle (and in particular, if $n$ is even, then it also contains a perfect matching). While Dirac's theorem is sharp in general, one would like to find sufficient conditions for sparser graphs. A natural candidate to begin with is a typical graph sampled from the binomial random graph model $G(n,p)$. That is, a graph $G$ on vertex set $[n]$, where each (unordered) pair is being sampled as an edge with probability $p$, independently. In 1960, Erd\H{o}s and R\'enyi raised a question of what the threshold probability of Hamiltonicity in random graphs is. This question attracted a lot of attention in the past few decades. After a series of efforts by various researchers, including Korshunov \cite{korshunov1976solution} and P\'osa \cite{posa1976hamiltonian}, the problem was finally solved
by Koml\'os and Szemer\'edi \cite{komlos1983limit} and independently by Bollob\'as \cite{bollobas1984evolution}, who proved that if
$p \geq (\log_{} n + \log_{} \log_{} n + \omega(1))/n$, where $\omega(1)$ tends to infinity with $n$ arbitrarily slowly,
then the probability of the random graph $G(n, p)$ being Hamiltonian tends to~1 (we say such an event happens \emph{with high probability}, or \emph{whp} for brevity) . This result is best possible since for $p \leq (\log_{} n + \log_{} \log_{} n - \omega(1))/n$ whp there are vertices of
degree at most one in $G(n, p)$ (see, e.g. \cite{bollobas1998random}). An even stronger result was given by Bollob\'as \cite{bollobas1984evolution}. He showed that for the random graph process, the hitting time for Hamiltonicity
is exactly the same as the hitting time for having minimum degree 2, that is, whp the very
edge which increases the minimum degree to 2 also makes the graph Hamiltonian.

In this paper, we take advantage of the study of the local resilience in random graphs and random digraphs, which was first introduced by Sudakov and Vu \cite{sudakov2008local}.
Roughly speaking, the local resilience is the largest proportion of edges that one can delete from every vertex in a given graph $G$ satisfying a property $\mathcal P$, such that the resulting (sub)graph still satisfies $\mathcal P$.
We shall use resilience results on perfect matchings in random bipartite graphs due to Sudakov and Vu~\cite{sudakov2008local} and Hamiltonicity in random digraphs by Montgomery~\cite{montgomery2020hamiltonicity}, see Lemma \ref{lem:bip-matching} and Lemma \ref{thm:resilience}, respectively.

\subsection{A rainbow setting}

In recent years, rainbow structures in graph systems have received a lot of attention~\cite{aharoni2018rainbow, Howard2017A, bradshaw2020transversals, bradshaw2021one, Cheng1, Cheng2, cheng2019rainbow, joos2020rainbow, New, 2020A, LU, 2020B, Montgomery22}.
Formally, given a family of (hyper)graphs $\mathcal G=\{G_1,\dots, G_m\}$ defined on the same vertex set, a copy of an $m$-edge (hyper)graph $H$ is called \emph{rainbow} if $E(H)\subseteq \bigcup_{i\in [m]}E(G_i)$ and $|E(H)\cap E(G_i)|=1$ for every $i\in [m]$.

A rainbow version of the Dirac-type problems in systems of graphs was conjectured by Aharoni et al.\cite{aharoni2018rainbow}: let $G_1,\ldots, G_{n}$ be a system of graphs on the same vertex set $V=[n]$ with minimum degree $\delta(G_i)\ge n/2$ for each $i\in[n]$, there exists a rainbow Hamilton cycle. Cheng, Wang and Zhao \cite{cheng2019rainbow} verified the conjecture asymptotically and Joos and Kim \cite{joos2020rainbow} proved the full conjecture. Very recently, Bradshaw, Halasz, and Stacho \cite{bradshaw2021one} strengthened the result by showing that the system of graphs actually admit exponentially many rainbow Hamilton cycles under the same assumptions. Bradshaw \cite{bradshaw2020transversals} generalized the Dirac-type result for Hamiltonicity of bipartite graphs by Moon and Moser \cite{moon1963hamiltonian} to the rainbow setting

Another interesting structure to consider is the perfect matching. In the rainbow setting we are given $n/2$ graphs $G_1,\ldots,G_{n/2}$ on the same vertex set $[n]$, and we are seeking for a rainbow perfect matching, namely, a perfect matching that consists of exactly one edge from each~$G_i$.

In this note, we give Dirac-type results for rainbow perfect matchings and rainbow Hamilton cycles in random graphs.
Our main results read as follows.

\begin{thm}
\label{thm:dirac-rainbow-random-PM}
Let $\varepsilon>0$ and $p=\omega\left(\frac{\log n}{n}\right)$ where $n$ is even.
Suppose $G_1,\ldots, G_{n/2}$ are independent samples of $G(n,p)$ on the same vertex set $V=[n]$.
Then, whp we have that for every spanning subgraphs $H_i\subseteq G_i$, $1\leq i\leq n/2$, with $\delta(H_i)\geq (\frac{1}{2}+\varepsilon)np$, the family $\{H_1,\dots,H_{n/2}\}$ admits a rainbow perfect matching.
\end{thm}

\begin{thm}
\label{thm:dirac-rainbow-Hamilton-cycle}
Let $\varepsilon>0$ and $p=\omega\left(\frac{\log n}{n}\right)$.
Suppose $G_1,\ldots, G_{n}$ are independent samples of $G(n,p)$ on the same vertex set $V=[n]$.
Then, whp we have that for every spanning subgraphs $H_i\subseteq G_i$, $1\leq i\leq n$, with $\delta(H_i)\geq (\frac{1}{2}+\varepsilon)np$, the family $\{H_1,\dots,H_{n}\}$ admits a rainbow Hamilton cycle.
\end{thm}

\subsection{Notation}
Given a graph $G$ and
$X\subseteq V(G)$, let $N(X)=\bigcup_{x\in X}N(x)$.
For
two subsets $X,Y\subseteq V(G)$ we define $E_G(X,Y)$ to be the set of all edges $xy\in E(G)$ with $x\in X$ and $y\in Y$, and set $e_G(X,Y):=|E(X,Y)|$ (the subscript $G$ will be omitted whenever there is no risk of confusion). Moreover, $G[X,Y]$ is defined by a graph with vertex set $X\cup Y$ and edge set $E_G(X,Y)$.  When
$x \in V (G)$, $d_G(x)$ is the \emph{degree} of $x$ in $G$.
For a graph $H$, $X\subset V(H)$, and a vertex $v\in V(H)$, we define
$d_H(v,X)=|\{uv\in E(H):u\in X\}|$.
In particular, if $X=\{u\}$ for some vertex $u$, then we write $d(v,u):=d(v,\{u\})$.

For a graph $G$, we denote by $\delta(G)$ as its minimum degree. For a digraph $D$, we denote $\delta^+(D),\delta^-(D)$ as its minimum out-degree and minimum in-degree, respectively.
Moreover, let
\[
\delta^0(D)=\min\{\delta^+(D),\delta^-(D)\}.
\]

If $f(n)/g(n) \to 0$ as $n \to\infty$, then we say $g(n) = \omega(f(n))$ and $f(n) = o(g(n))$. If there exists a
constant $C$ for which $f(n) \leq Cg(n)$ for all $n$, then we say $f(n) = O(g(n))$ and $g(n) = \Omega(f(n))$. If
$f = O(g(n))$ and $f(n) = \Omega(g(n))$, then we say that $f(n) = \Theta(g(n))$. The
random graph $G(n, p)$
has vertex set $[n] = \{1, \dots , n\}$ and edges chosen independently at random with probability $p$.  The
random digraph $D(n, p)$
has vertex set $[n] = \{1, \dots , n\}$ and directed edges $(u,v)$, which is an ordered pair of vertices, chosen independently at random with probability $p$.

\section{Preliminary Results}

In this section we first present some useful tools for the proofs, and then introduce our key auxiliary graphs and how to use them.

\subsection{Chernoff’s inequalities}
We will use the following well-known bound on the upper and lower tails of the binomial distribution, which is given by Chernoff (see Appendix A in \cite{AS}).

\begin{lem}[Chernoff's inequality]\label{lem:Chernoff}
Let $X \sim \mathrm{Bin}(n, p)$ and let $\mathbb{E}[X] = \mu$. Then
\begin{itemize}
    \item $\Pr[X<(1-a)\mu]<e^{-a^2\mu/2}$ for every $a>0$;
    \item $\Pr[X>(1+a)\mu]<e^{-a^2\mu/3}$ for every $0<a<3/2$.
\end{itemize}
\end{lem}

\begin{rem}
Chernoff's inequalities also hold when $X$ is hypergeometrically distributed with mean $\mu$.
\end{rem}

The following simple bound is also useful in our proof.

\begin{lem}\label{lem:simple-inequality}
Let $X \sim \mathrm{Bin}(m, q)$. Then, for all $k$ we have
$$
\Pr[X\geq k]\leq \left(\frac{emq}{k}\right)^k.
$$
\end{lem}
\begin{proof}
Indeed, note that
$$
\Pr[X\geq k]\leq \binom{m}{k}q^k\leq \left(\frac{emq}{k}\right)^k
$$
as desired.
\end{proof}

\subsection{Talagrand-type inequality}
Our main probabilistic tool is the following concentration inequality of McDiarmid \cite{mcdiarmid2002concentration}.

\begin{thm}\label{thm:Talagrand}
Given a set $S$ of size $m$, we let ${\rm Sym}(S)$ denote the set of all $m!$ permutations of $S$. Let $\{B_1,\dots, B_k\}$ be a family of finite non-empty sets, and let $\Omega = \Pi_i {\rm Sym}(B_i)$. Let $\pi =\{\pi_1,\dots, \pi_k\}$ be a family of independent permutations, such that for $i$, $\pi_i \in {\rm Sym}(B_i)$ is chosen uniformly at random.

Let $c$ and $r$ be constants, and suppose that a nonnegative real-valued function $h$ on $\Omega$ satisfies the following conditions for each $\pi\in\Omega$.

\begin{enumerate}
    \item Swapping any two elements in any $\pi_i$ can change the value of $h$ by at most $2c$.
    \item If $h(\pi) = s$, there exists a set $\pi_{proof} \subseteq\pi$ of size at most $rs$, such that $h(\pi') \geq s$ for any $\pi'\in\Omega$ where $\pi'\supseteq \pi_{proof}$.
\end{enumerate}
Then for each $t\geq 0$ we have
$$
\Pr[h \leq M(h(\pi)) - t] \leq 2 \exp{\left(-\frac{t^2}{16rc^2M} \right)}.
$$
\end{thm}

\subsection{Typical properties of graphs}

In this section, we collect some useful properties of a typical sequence of independent samples of $G(n,p)$, which are regarded as ``colors'', on the same vertex set $V=[n]$. First, we show that the degrees are concentrated.

\begin{lem}\label{lem:similar-degrees}
Let $\varepsilon>0$ and let $N\leq n^2$. Let $G_1,\ldots, G_{N}$ be independent samples of $G(n,p)$ on the same vertex set $V=[n]$. Then, whp we have
$$
(1-\varepsilon)np\leq \delta(G_c)\leq \Delta(G_c) \leq (1+\varepsilon)np
$$
holds for all $c\in [N]$ provided that $p=\omega(\frac{\log_{}n}{n})$.
\end{lem}
\begin{proof}

Fix some vertex $u\in[n]$ and some color $c\in[N]$. Observe that $d_{G_c}(u) \sim Bin(n-1, p)$, and therefore $\mu := \mathbb{E}[d_{G_c}(u)] = (n -1)p$.
Hence, since $p=\omega(\frac{\log n}n)$, by Lemma \ref{lem:Chernoff} we obtain that
$$
\Pr[d_{G_c}(u) \notin(1 \pm \varepsilon)\mu] \leq 2\exp{\left(-\frac{\varepsilon^2\mu}{3}\right)}=o\left(\frac{1}{n^3}\right).
$$
Taking a union bound over all vertices $u\in[n]$ and all colors $c\in[N]$, we conclude that
$$
\Pr[\exists u \in[n] ,\exists c\in[N]\text{ s.t. }d_{G_c}(u)\notin  (1\pm\varepsilon)\mu]=o(1).
$$
This completes the proof.
\end{proof}

Next, we show that given $n/2$ graphs $H_1,\dots, H_{n/2}$, if we take a random equipartition of $[n]$, then whp the corresponding bipartite subgraphs of $H_i$ have the ``correct'' degrees.

\begin{lem}\label{lem:partition}
For every $\varepsilon>0$ there exists $C:=C(\varepsilon)$ for which the following holds. Let $m=n/2$. Let $H_1,\dots,H_m$ be graphs on the same vertex set $V=[n]$, where $n$ is a sufficiently large even integer. Suppose that $\delta(H_c)\geq C\log_{}n$ for all $c\in [m]$. Then, a $(1-o(1))$-fraction of the partitions $V=V_1\cup V_2$ into sets of size $m$ satisfy the following property: For every vertex $u\in V$ and $c\in[m]$, and for $i=1,2$ we have
$$
d_{H_c}(u,V_i)\in(1\pm\varepsilon)\cdot \frac{d_{H_c}(u)}{2}.
$$
\end{lem}

\begin{proof}
Consider a random partition $V=V_1\cup V_2$ into sets both of size $m$. For some fixed vertex $u\in[n]$ and some fixed $c\in[m]$,  note that $d_{H_c}(u)$ is hypergeometrically distributed with expected value $\frac{d_{H_c}(u)}{2}$. Therefore, by Lemma \ref{lem:Chernoff} we obtain that
$$
\Pr\left[d_{H_c}(u,V_i)\notin (1\pm \varepsilon)\cdot \frac{d_{H_c}(u)}{2}\right]\leq 2e^{-\varepsilon^2 \frac{d_{H_c}(u)}{2}/3}\leq 2e^{-3\log_{}n}=2n^{-3},
$$
where the last inequality holds for a large enough $C$.

By applying a union bound over all possible $u$'s and $i$'s, we obtain that the probability of having such a vertex $u$ and an index $i$ is at most $(n^2/2)\cdot 2n^{-3}=n^{-1}$.
This completes the proof.
\end{proof}

\subsection{Auxiliary graphs and proof ideas}
In this section we define some auxiliary graphs/digraphs that are going to play key roles in the proofs of our main theorems.

\subsubsection{Perfect matchings}
Our proof uses an auxiliary bipartite graph as follows.

\begin{defi}\label{def:auxiliary-graph}
Let $n$ be an even integer. Let $H_1',\dots,H_{n/2}'$ be bipartite graphs on the same vertex set $V=[n]$, each of which has the same bipartition $V=V_1 \cup V_2$ with $|V_1|=|V_2|=n/2$. By relabeling the vertices (if necessary), we may assume $V_1=[{n}/{2}]$. Given a permutation $\pi:V_1\to V_1$, the auxiliary bipartite graph $B_\pi:=B_\pi(H_1',\dots,H_{n/2}')$ is constructed as follows:
the parts of $B_{\pi}$ are $V_1$ and $V_2$; the edge set consists of all pairs $(i,j)\in V_1\times V_2$ such that $ij\in E(H_{\pi(i)}')$.
\end{defi}

\begin{rem}\label{rem:PM-implies-RM}
Observe that a perfect matching in $B_\pi$ corresponds to a rainbow perfect matching in the family $H_1', \dots, H_{n/2}'$. Indeed, every edge $\{i,j\}$ in $B_\pi$ with $i\in V_1$ and $j\in V_2$ corresponds to an edge $\{i,j\}$ in $H_{\pi(i)}'$, and since $\pi$ is a permutation of $V_1$, a perfect matching of $B_{\pi}$ uses exactly one edge from each $H'_i$.
\end{rem}

We also need the following result of Sudakov and Vu~\cite{sudakov2008local} on local resilience of perfect matchings in random bipartite graphs, whose proof can be found in the proof of~\cite[Theorem 3.1]{sudakov2008local}.
Let $V_1$ and $V_2$ be disjoint vertex sets each of size $n/2$, where $n\in 2\mathbb N$.
A random bipartite graph $B(n,p)$ defined on the partition $V_1\cup V_2$ is a bipartite graph such that given $(i,j)\in V_1\times V_2$, $ij\in E(B(n,p))$ with probability $p$ and all pairs $ij$ are chosen independent of each other.
\begin{lem}[Sudakov and Vu \cite{sudakov2008local}]
\label{lem:bip-matching}
Let $\varepsilon>0$ and $p=\omega\left(\frac{\log n}{n}\right)$ where $n$ is even.
Let $V_1$ and $V_2$ be disjoint vertex sets each of size $n/2$.
Then, whp a spanning subgraph $H\subseteq B(n,p)$ defined on $V_1\cup V_2$ such that $\delta(H)\geq (\frac{1}{2}+\varepsilon)\frac{np}{2}$ contains a perfect matching.
\end{lem}

We first demonstrate how to use the auxiliary bipartite graph to prove the following bipartition version of Theorem~\ref{thm:dirac-rainbow-random-PM}.

\begin{thm}
\label{thm:dirac-rainbow-random-PM2}
Let $\varepsilon>0$ and $p=\omega\left(\frac{\log n}{n}\right)$ where $n$ is even.
Suppose $G_1,\ldots, G_{n/2}$ are independent samples of $B(n,p)$ defined on $V_1\cup V_2$, each of size $n/2$.
Then, whp we have that for every spanning (bipartite) subgraphs $H_i\subseteq G_i$, $1\leq i\leq n/2$, with $\delta(H_i)\geq (\frac{1}{2}+\varepsilon)\frac{np}2$, the family $\{H_1,\dots,H_{n/2}\}$ admits a rainbow perfect matching.
\end{thm}

Here is an outline of our proof.
Given a set $V$ of $n\in 2\mathbb N$ vertices and a balanced bipartition $V=V_1\cup V_2$,  fix a permutation $\pi: V_1\to V_1$.
If we expose $n/2$ independent samples of $B(n,p)$ on $V_1\cup V_2$, denoted by $G_1,\dots, G_{n/2}$, then we have that the bipartite graph $G_\pi=B_\pi(G_1,\dots, G_{n/2})$ defined in Definition~\ref{def:auxiliary-graph} is also a random bipartite graph.

Then, given $(i,j)\in V_1\times V_2$,  $ij\in G_\pi$ if and only if $ij\in E(G_{\pi(i)})$, which happens with probability precisely $p$ and is independent with all other pairs in $V_1\times V_2$.
In particular, whp $G_\pi$ is resilient for perfect matching -- by Lemma~\ref{lem:bip-matching}. That is, whp every spanning subgraph $H$ of $G_\pi$ with $\delta(H)\geq (\frac{1}{2}+\frac\varepsilon 2)\frac{np}2$ contains a perfect matching. However, once the independent samples are exposed, there might be some "bad" permutations $\pi$ such that there exists $i\in V_1$ satisying $ij\notin E(G_{\pi(i)})$ for most $j\in V_2$. Fortunately, we can prove that almost every $\pi$ is not bad by Markov's inequality.
On the other hand, we shall show that (Lemma~\ref{lem:large-degrees}) if $\pi$ is a uniformly random permutation of $V_1$ and $H_1,\dots, H_{n/2}$ are graphs such that $H_i\subseteq G_i$ and $\delta(H_i)\ge (\frac{1}{2}+\varepsilon)\frac{np}2$, then whp the bipartite graph $B_\pi=B_\pi(H_1,\dots, H_{n/2})$ satisfies that $B_\pi\subseteq G_\pi$ and $\delta(B_\pi)\ge (\frac{1}{2}+\frac{\varepsilon}2)\frac{np}2$.
Therefore, by the resilience property of $G_\pi$ we conclude that $H_\pi$ has a perfect matching, which gives rise to a rainbow perfect matching of the family $H_1,\dots, H_{n/2}$.
This will prove Theorem~\ref{thm:dirac-rainbow-random-PM2}.

To derive Theorem~\ref{thm:dirac-rainbow-random-PM}, it suffices to show that there is a balanced bipartition of the vertex set such that the bipartite subgraphs of our graphs inherits the degree condition, which is proved in Lemma~\ref{lem:partition}.

\subsubsection{Directed Hamilton cycles}

For Hamiltonicity we will need to construct an auxiliary digraph as follows.

\begin{defi}\label{def:auxiliary-digraph}
Let $H_1',\dots,H_{n}'$ be graphs on the same vertex set $V=[n]$, Given a permutation $\pi:V\to V$, the auxiliary digraph ${D}_\pi:={D}_\pi(H_1',\dots,H_{n}')$ is constructed as follows: \\
$V$ is the vertex set of ${D}_\pi$ and for any vertex $i,j\in V$, $(i,j)\in E({D}_\pi)$ if and only if $ij\in E(H_{\pi(i)}')$.
\end{defi}

\begin{rem}\label{rem:auxiliary-digraph}
Observe that a directed Hamilton cycle in the auxiliary digraph ${D}_\pi$ corresponds to a rainbow Hamilton cycle in the family $H_1',\dots,H_{n}'$. Indeed, a directed Hamilton cycle in ${D}_\pi$ is a directed Hamilton cycle in $K_n$ whose edges $(i,j)$ belongs to distinct $H_{\pi(i)}'$ since $\pi$ is a permutation.
\end{rem}

We also need the following result on local resilience of Hamiltonicity in random digraphs due to Montgomery \cite{montgomery2020hamiltonicity} (in fact, Montgomery proved a way stronger result but the following is enough for our needs).

\begin{lem}\label{thm:resilience}
Let $\varepsilon>0$. Then whp a spanning subdigraph $D\sim D(n,p)$ defined on $V=[n]$ such that $\delta^0(D)\geq (\frac{1}{2}+\varepsilon)np$ contains a Hamilton cycle, provided that $p=\omega(\frac{\log_{}n}n)$.
\end{lem}

Similar to what we did in the previous subsection, we explain how this auxiliary digraph works. Given a set $V$ of $n$ vertices,  fix a permutation $\pi: V\to V$.
If we expose $n$ independent samples of $G(n,p)$ on $V$, denoted by $G_1,\dots, G_{n}$, then the digraph $G_\pi=D_\pi(G_1,\dots, G_{n})$ defined in Definition~\ref{def:auxiliary-digraph} is a random digraph.
Indeed, given $(i,j)\in V^2$, then $ij\in G_\pi$ if and only if $(i,j)\in E(G_{\pi(i)})$, which happens with probability precisely $p$ and is independent with all other pairs in $V^2$.
In particular, $G_\pi$ is resilient for Hamiltonicity -- by Lemma~\ref{thm:resilience}, whp any spanning subdigraph $H$ of $G_\pi$ with $\delta^0(H)\geq (\frac{1}{2}+\frac\varepsilon 2)np$ contains a directed Hamilton cycle.
On the other hand, we shall show that (Lemma~\ref{lem:large-degrees-digraphs}) if $\pi$ is a uniformly random permutation of $V$ and $H_1,\dots, H_{n}$ are graphs such that $H_i\subseteq G_i$ and $\delta(H_i)\ge (\frac{1}{2}+\varepsilon)np$, then whp the digraph $D_\pi=D_\pi(H_1,\dots, H_{n})$ satisfies that $D_\pi\subseteq G_\pi$ and $\delta(D_\pi)\ge (\frac{1}{2}+\frac{\varepsilon}2)np$.
Therefore, by the resilience property of $G_\pi$, we conclude that $D_\pi$ has a directed Hamilton cycle, which gives rise to a rainbow Hamilton cycle of the family $H_1,\dots, H_{n}$.
This will prove Theorem~\ref{thm:dirac-rainbow-Hamilton-cycle}.

\subsection{Most $B_{\pi}$'s have large minimum degree}

In this section we prove that given a balanced partition $[n]=V_1\cup V_2$ and bipartite graphs $H_1',\ldots,H'_m$ with a common bipartition $V_1\cup V_2$ (with $m=n/2$) and large minimum degrees, the resulting auxiliary graph $B_\pi$ also has large minimum degree whp where $\pi$ is a uniformly random permutation. The proof is a special case of Lemma 13 in \cite{FH}, but we include it for completeness.

\begin{lem}\label{lem:median}
Let $0<\alpha<\frac{1}{2}$ and let $n\in2\mathbb{N}$ be sufficiently large. Let $m=n/2$. Let $H_1',\dots,H_{m}'$ be bipartite graphs on the same vertex set $V=[n]$ with the same parts $V=V_1 \cup V_2$ of the same size $m$, where $V_1=[m]$. Suppose that $\delta^*(H_c')\geq \frac{200}{\alpha^2}$ for all $c\in [m]$.
Let $\pi$ be a uniformly random permutation on $V_1$ and $\mu_i=\mathbb{E}[d_{B_\pi}(i)]$.
Then, for every $j\in V_2$, we have
$$
M_j:=M(d_{B_\pi}(j))\in (1\pm\alpha)\mu_j.
$$
\end{lem}

\begin{rem}
The above lemma allows us to use $\mu_j$ instead of $M_j$ in Theorem \ref{thm:Talagrand} when it is applied to $d_{B_\pi}(j)$.
\end{rem}

\begin{proof}
Consider $B_\pi$, where $\pi$ is a uniformly random permutation on $V_1$. Let $j$ be some vertex in $V_2$. Let $\mu_j=\mathbb{E}[d_{B_\pi}(j)]$ and $\sigma^2= \mathrm{Var}(d_{B_\pi}(j))$. Moreover, for each $i\in V_1$, we define an indicator random variable $\mathds{1}_i$, where $\mathds{1}_i=1$ if $\{i,j\}\in E(H_{\pi(i)}')$. Observe that $d_{B_{\pi}}(j)=\sum_{i\in V_1} \mathds{1}_i.$

Applying Chebyshev's inequality, we have
$$
\Pr[|d_{B_\pi}(j)-\mu_j|\geq \alpha\mu_j]\leq \frac{\sigma^2}{\alpha^2\mu_j^2}.
$$
If we can show that $\sigma^2\leq \frac{\alpha^2\mu_j^2}{100}$, then the result follows. Indeed, with probability at least 99/100 we have that $d_{B_\pi}(j)\in (1\pm\alpha)\mu_j$ and thus we conclude that the median $M_j$ also lies in this interval. Now the remaining part is to prove the desired inequality by computing $\mu_j=\mathbb{E}[d_{B_\pi}(j)]$ and $\sigma^2= \mathrm{Var}(d_{B_\pi}(j))$.

Note that the event $\left(\mathds{1}_i=1\right)$ only depends on the value of $\pi(i)$. There are $m$ possible values in total for $\pi(i)$, and exactly the colors in which $ij$ is an edge contribute to $\mathds{1}$. Let $d_{H_c'}(i,j)=1$ if $ij\in E(H_c')$, and $d_{H_c'}(i,j)=0$ otherwise. So
$$
\Pr[\mathds{1}_i=1]=\frac{\sum_{c=1}^m d_{H_c'}(i,j)}{m}.
$$
By linearity of expectations, we have
$$
\mu_j=\sum_{i=1}^m \mathbb{E}[\mathds{1}_i]=\sum_{i=1}^m\frac{\sum_{c=1}^m d_{H_c'}(i,j)}{m} =\sum_{c=1}^m\frac{\sum_{i=1}^m d_{H_c'}(i,j)}{m}=\sum_{c=1}
^m \frac{d_{H_c'}(j)}{m}.
$$
To compute the variance, note that for each $i\neq k$ in $V_1$, we have
$$
\begin{aligned}
\mathbb{E}\left[\mathds{1}_i\mathds{1}_k\right]
&=\sum_{c=1}^m \Pr\left[\mathds{1}_i=\mathds{1}_k=1|\pi(i)=c\right] \Pr\left[\pi(i)=c\right]\\
&=\sum_{c=1}^m \frac{1}{m} d_{H_c'}(i,j)\Pr\left[\mathds{1}_k=1|\pi(i)=c\right]\\
&=\sum_{c=1}^m \frac{1}{m} d_{H_c'}(i,j)\frac{\sum_{c'\neq c} d_{H_{c'}'}(k,j)}{m-1}.
\end{aligned}
$$
Thus,
$$
\begin{aligned}
\mathrm{Var}\left(d_{B_\pi}\left(j\right)\right)&=\mathrm{Var}\left(\sum_{i=1}^m \mathds{1}_i\right)
=\sum_{i=1}^m \mathrm{Var}\left(\mathds{1}_i\right) + \sum_{i\neq k}\mathrm{Cov}\left(\mathds{1}_i,\mathds{1}_k\right)\\
&\leq \mu_j+\sum_{i\neq k}\left(\mathbb{E}\left[\mathds{1}_i\mathds{1}_k\right] - \mathbb{E}\left[\mathds{1}_i\right]\mathbb{E}\left[\mathds{1}_k\right]\right)\\
&=\mu_j + \sum_{i\neq k}\left(\sum_{c=1}^m \frac{1}{m} d_{H_c'}(i,j)\frac{\sum_{c\neq c'}d_{H_{c'}'}(k,j)}{m-1}-\frac{\sum_{c=1}^m d_{H_c'}(i,j)}{m}\frac{\sum_{c'=1}^m d_{H_{c'}'}(k,j)}{m}\right)\\
&=\mu_j + \sum_{i\neq k}\left(\left(\frac{1}{m(m-1)}-\frac{1}{m^2}\right)\sum_{c=1}^m d_{H_c'}(k,j)\sum_{c'=1}^m d_{H_{c'}'}(i,j)-\frac{1}{m(m-1)}\sum_{c=1}^m d_{H_c'}(k,j)d_{H_c'}(i,j)\right)\\
&\leq \mu_j + \frac{1}{m^2(m-1)}\sum_{i,k=1}^m\left(\sum_{c=1}^m d_{H_c'}(k,j)\sum_{c'=1}^m d_{H_{c'}'}(i,j)\right)\\
&=\mu_j+\frac{1}{m-1}\mu_j^2.
\end{aligned}
$$
To complete the proof, first observe that we have $\frac{1}{m-1}\mu_j^2\leq \frac{\alpha^2\mu_j^2}{200}$ since $m$ is sufficiently large. Also, we have $\mu_j\leq \frac{\alpha^2\mu_j^2}{200}$ since $\mu_j\geq \frac{200}{\alpha^2}$ by assumption.
Now we obtain $\sigma^2\leq \frac{\alpha^2\mu_j^2}{100}$ and the lemma follows.
\end{proof}

\begin{lem}\label{lem:large-degrees}
For every $\varepsilon>0$ there exists $C:=C(\varepsilon)$ for which the following holds for sufficiently large $m\in\mathbb{N}$ and $p=C\frac{\log m}m$. Let $H_1',\dots,H_m'$ be bipartite graphs on the same vertex set $V=[n]$ with the same parts $V=V_1 \cup V_2$ of the same size $m$, where $V_1=[m]$. Suppose that $\delta^*(H_c')\geq (\frac{1}{2}+\varepsilon)mp$ for every $c\in[m]$. Then for a uniformly random permutation $\pi:[m]\to [m]$,  whp we have $\delta(B_\pi)\geq (\frac{1}{2}+\frac{\varepsilon}{2})mp$.
\end{lem}

\begin{proof}
Consider $B_\pi$, where $\pi$ is a uniformly random permutation. As $\delta^*(H_c')\geq (\frac{1}{2}+\varepsilon)mp$ for every $c\in[m]$, it is guaranteed that for all $i\in V_1$ we have that $d_{B_\pi}(i)\geq (\frac{1}{2}+\varepsilon)mp$.
Now consider some $j\in V_2$ and observe from the proof of Lemma \ref{lem:median}, under the same notation, that $\mu_j:=\mathbb{E}[d_{B_\pi}(i)]\geq (\frac{1}{2}+\varepsilon)mp.$

In order to complete the proof, we want to show that the $d_{B_\pi}(j)$'s are ``highly concentrated'' using Theorem \ref{thm:Talagrand}. To this end, let $h(\pi):=d_{B_\pi}(j)$ and note that swapping any two elements of $\pi$ can change the value of $h$ by at most 2. Moreover, note that if $h(\pi) =d_{B_\pi}(j)= s$, then it is enough to choose $\pi_{proof}$ as the $s$ indices reflected in $N_{B_\pi}(j)$. Therefore, $h(\pi)$ satisfies the conditions of Theorem \ref{thm:Talagrand} with $c = 1$ and $r = 1$.

Now, let $\alpha=\frac{\varepsilon}{100}$, and observe that by Lemma \ref{lem:median} we have that the median $M$ of $d_{B_\pi}(j)$ lies in the interval $(1\pm\alpha)\mu_j$.
Therefore, we have
$$
\Pr \left[h\leq (\frac{1}{2}+\frac{\varepsilon}{2})mp\right]\leq \Pr\left[h\leq (1-\frac{\varepsilon}{2})\mathbb{E}[d_{B_\pi}(j)]\right]
$$
and the latter can be upper bounded by
$$
\Pr\left[h\leq (1-\frac{\varepsilon}{2})(1+\alpha)M\right]\leq \Pr\left[h\leq (1-\frac{\varepsilon}{4})M\right].
$$
Now, by Theorem \ref{thm:Talagrand} we obtain that
$$
\Pr\left[h\leq (\frac{1}{2}+\frac{\varepsilon}{2})mp\right]\leq 2\exp{\left\{-\frac{(\varepsilon M/4)^2}{16M}\right\}}.
$$
Next, using (again) the fact that $M\in (1\pm\alpha)\mu_j$ and that $\mu_j=\Theta(mp)\geq C\log_{}m$, we can upper bound the above right hand side by
$2\exp{ (-\Theta(mp))} \leq n^{-2}$.
Finally, in order to complete the proof, we take a union bound over all $j\in V_2$ and obtain that whp $\delta(B_\pi)\geq (\frac{1}{2}+\frac{\varepsilon}{2})mp$.
\end{proof}

\subsection{Most $D_{\pi}$'s have large minimum degree}

The following lemma says that given digraphs $H_1',\ldots,H'_m$ with large minimum semidegrees (minimum of out-degrees and in-degrees), the resulting auxiliary digraph $D_\pi$ also has large minimum degree whp where $\pi$ is a uniformly random permutation.

\begin{lem}
\label{lem:large-degrees-digraphs}
For every $\varepsilon>0$ there exists $C:=C(\varepsilon)$ for which the following holds for sufficiently large $n\in\mathbb{N}$ and $p=C\frac{\log_{}n}n$. Let $H_1',\dots,H_n'$ be graphs on the same vertex set $V=[n]$. Suppose that $\delta(H_c')\geq (\frac{1}{2}+\varepsilon)np$ for every $c\in[n]$. Then for a uniformly random permutation $\pi:V\to V$,  whp we have $\delta^0(D_\pi)\geq (\frac{1}{2}+\frac{\varepsilon}{2})np$.
\end{lem}

The proof of Lemma \ref{lem:large-degrees-digraphs} is very similar to that of Lemma \ref{lem:large-degrees} so we leave it to the appendix.

\section{Proof of main results}

We first give a proof of Theorem~\ref{thm:dirac-rainbow-random-PM2} and use it to derive Theorem~\ref{thm:dirac-rainbow-random-PM}.
\begin{proof}[Proof of Theorem~\ref{thm:dirac-rainbow-random-PM2}]
Let $\varepsilon > 0$ and $p \geq C \frac{\log_{}n}n$, for a sufficiently large $C$. Let $m=\frac{n}{2}$. Let $G_1,\ldots, G_{m}$ be independent samples of $B(n,p)$ on $V_1\cup V_2$.
Let $H_c\subseteq G_c$ be any (bipartite) subrgraphs with $\delta(H_c) \geq (1/2+\varepsilon)mp$. We wish to demonstrate that whp the family of graphs $H_1,\dots,H_m$ has a rainbow perfect matching.

Now, let $\pi$ be a permutation on $V_1$ chosen uniformly at random.
Therefore, Lemma \ref{lem:large-degrees} (with input graphs $H_1,\dots, H_m$) guarantees that for almost all permutation $\pi$, $H_\pi=B_\pi(H_1,\dots, H_m)$ (as defined in \ref{def:auxiliary-graph}) satisfies
\begin{enumerate}[label=$(\dagger)$]
\item $\delta(H_\pi)\geq (\frac{1}{2}+\frac{\varepsilon}{2})mp$.
\label{item:dagger}
\end{enumerate}
We focus on all $\pi$ satisfying above and  condition on~\ref{item:dagger}.

Note that the bipartite graph $G_\pi=B_\pi(G_1,\dots, G_m)$ is a random bipartite graph, where all pairs in $V_1\times V_2$ are present with probability $p$, and independent with other pairs of vertices.
Moreover, by definition, $H_\pi$ is a subgraph of $G_\pi$.
Thus, by~\ref{item:dagger}, we have that $H_\pi$ is a subgraph of $G_\pi$ with $\delta(H_\pi)\geq (\frac{1}{2}+\frac{\varepsilon}{2})mp$.
Therefore, by Lemma~\ref{lem:bip-matching}, whp $H_\pi$ contains a perfect matching, which by Remark \ref{rem:PM-implies-RM} implies that the family $H_1,\dots,H_m$ whp admits a rainbow perfect matching.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:dirac-rainbow-random-PM}]
Let $\varepsilon > 0$ and $p \geq C \frac{\log_{}n}n$, for a sufficiently large $C$. Let $m=\frac{n}{2}$. Let $G_1,\ldots, G_{m}$ be independent samples of $G(n,p)$ (on the same vertex set $V=[n]$).
Let $H_c\subseteq G_c$ be any subgraphs with $\delta(H_c) \geq (1/2+\varepsilon)np$. We wish to show that whp the family of graphs $H_1,\dots,H_m$ has a rainbow perfect matching.

Observe that by Lemma \ref{lem:similar-degrees}, whp the family of graphs $G_1,\ldots, G_{m}$ satisfies
\begin{enumerate}[label=$(\ddagger)$]
\item $(1-\varepsilon)np\leq \delta(G_c)\leq \Delta(G_c) \leq (1+\varepsilon)np$ for all $c\in[m]$. \label{item:ddag}
\end{enumerate}
For the rest of the proof, we condition on~\ref{item:ddag}.

Now, let $\alpha > 0$ such that $(1-\alpha)(1/2+\varepsilon) \geq 1/2+\varepsilon/2$.
By Lemma \ref{lem:partition} with $\alpha$ in place of $\varepsilon$, we obtain that most balanced bipartitions of $[n] = V_1\cup V_2$ satisfy the following: for every $u\in V_i$, $i=1,2$, and for every $c\in[m]$, we have
$$
d_{H_c}(u,V_{3-i})\ge (1-\alpha)\cdot \frac{d_{H_c}(u)}{2} \ge (1-\alpha)\cdot \left(\frac{1}{2}+\varepsilon\right)\frac{np}2 \ge \left(\frac{1}{2}+\frac\varepsilon 2 \right)\frac{np}2.
$$

Now for $i\in [m]$ and any given partition $[n]=V_1\cup V_2$, we let $G_i':=G_i[V_1, V_2]$ and $H_i':=H_i[V_1, V_2]$ be the spanning subgraphs of $G_i$ and $H_i$, respectively, induced by the bipartition $V_1\cup V_2$.
Observe that, for a given partition, all $G_i'$ are independent samples of $B(n,p)$ on $V_1\cup V_2$. Moreover, for most balanced bipartitions the graphs $H_i'\subseteq G_i'$ satisfy $\delta(H_i')\ge \left(\frac{1}{2}+\frac\varepsilon 2 \right)\frac{np}2$.
Therefore, by Theorem~\ref{thm:dirac-rainbow-random-PM2}, we obtain that by taking a random partition $[n]=V_1\cup V_2$, whp the family $\{H_1',\dots,H_{n/2}'\}$ admits a rainbow perfect matching. This completes the proof.
\end{proof}

Now we give a proof of Theorem \ref{thm:dirac-rainbow-Hamilton-cycle}.

\begin{proof}[Proof of Theorem~\ref{thm:dirac-rainbow-Hamilton-cycle}]

Let $\varepsilon > 0$ and $p \geq C \frac{\log_{}n}n$, for a sufficiently large $C$. Let $G_1,\ldots, G_{n}$ be independent samples of $G(n,p)$ (on the same vertex set $V=[n]$).
Let $H_c\subseteq G_c$ be any subgraphs with $\delta(H_c) \geq (1/2+\varepsilon)np$. We wish to show that whp the family of graphs $H_1,\dots,H_n$ has a rainbow Hamilton cycle.

Similar to above, whp the family of graphs $G_1,\ldots, G_{n}$ satisfies \ref{item:ddag} for $m=n$. For the rest of the proof, we condition on~\ref{item:ddag}.

Now, let $\pi$ be a permutation on $V$ chosen uniformly at random.
Therefore, Lemma \ref{lem:large-degrees-digraphs} (with input graphs $H_1,\dots, H_n$) guarantees that whp $D_\pi'=D_\pi(H_1,\dots, H_n)$ (as defined in \ref{def:auxiliary-digraph}) satisfies
\begin{enumerate}[label=$(*)$]
\item $\delta(D_\pi')\geq (\frac{1}{2}+\frac{\varepsilon}{2})np$. \label{item:dag}
\end{enumerate}
We condition on $(*)$.

Note that the digraph $D_\pi=D_\pi(G_1,\dots, G_n)$ is a random digraph, where all pairs are present with probability $p$, and independent with other pairs of vertices.
Moreover, by definition, $D_\pi'$ is a subdigraph of $D_\pi$.
Therefore, by Lemma~\ref{thm:resilience}, whp $D_\pi'$ contains a Hamilton cycle, which by Remark \ref{rem:auxiliary-digraph} implies that the family $H_1,\dots,H_n$ whp admits a rainbow Hamilton cycle. This completes the proof.
\end{proof}

\section{Concluding Remarks}

In this note we address the Dirac-type problems for rainbow perfect matching and Hamilton cycle in a family of random graphs.
Our method reduces the rainbow embedding problem to that in closely related contexts with a single host graph.
That is, we use appropriate auxiliary graphs that ``assemble'' the family of graphs to one graph, so that the rainbow subgraph problem is reduced to finding a single copy of the desired subgraph in this auxiliary graph.
For perfect matching and $F$-factors\footnote{Given graphs $F$ and $H$, an \emph{$F$-factor} in $H$ is a spanning subgraph of $H$ consisting of vertex-disjoint copies of $F$.}, the natural candidate for the auxiliary graph is the multi-partite graphs.
For connected objects such as Hamilton cycles, we show that directed graphs are helpful auxiliary graphs.

Our method is also applicable to the dense setting and to random hypergraphs.
We end by the following result for perfect matching in $k$-partite $k$-graphs.
For $k > d>0$ and a $k$-partite $k$-graph $H$, let $\delta_d^*(H)$ be the maximum integer $m$ such that every crossing\footnote{A set is called \emph{crossing} if it contains at most one vertex from each part of the partition.} $d$-set in $V(H)$ has degree at least $m$.
For $k > d> 0$, let $\delta_{k,d}$ be the smallest real number $\delta>0$ such that for every $\varepsilon>0$ there exists $n_0>0$ such that every $k$-partite $k$-graph $H$ with $n$ vertices in each part satisfying $\delta_d^*(H)\ge (\delta+\varepsilon)n^{k-d}$ contains a perfect matching.

\begin{thm}
Given integers $k>d>0$ and $\varepsilon>0$, there exists $n_0$ such that the following holds for integer $n\ge n_0$.
Let $H_1,\dots, H_{n}$ be a family of $k$-partite $k$-graphs on the same $k$-partition with $n$ vertices in each part.
Suppose $\delta_d^*(H_i)\ge (\delta_{k,d}+\varepsilon)n^{k-d}$ for every $i\in [n]$.
Then the family admits a rainbow perfect matching.
\end{thm}

\begin{proof}[Proof Sketch]
Let $V=V_1\cup V_2\cup \cdots \cup V_k$ be a $k$-partition with $n$ vertices in each part.
Given a permutation $\pi$ of $V_1=[n]$, define the auxiliary $k$-partite $k$-graph $H_\pi$ on $V_1\cup V_2\cup \cdots \cup V_k$ such that a crossing $k$-tuple $S=\{a_1,\dots, a_k\}$ with $a_i\in V_i$ belongs to $E(H_\pi)$ if and only if $S\in E(H_{\pi(a_1)})$.
Then for a random permutation $\pi$ of $V_1$, one can show that whp $\delta_d^*(H_\pi)\ge (\delta_{k,d}+\varepsilon/2)n^{k-d}$.
Take such a permutation $\pi$ and since $n$ is sufficiently large, $\delta_d^*(H_\pi)\ge (\delta_{k,d}+\varepsilon/2)n^{k-d}$ implies that $H_\pi$ contains a perfect matching $M$.
Since $M$ contains precisely one edge from each $H_i$, it is a rainbow perfect matching of the family.
\end{proof}

It follows from a result of Pikhurko~\cite{Pik} that $\delta_{k,d}=1/2$ for $d\ge k/2$.

\bibliographystyle{abbrv}


\subsection{Is privacy leakage through recourses inevitable?}\label{subsec:priv}
The attacks developed above and empirical results in Section~\ref{sec:experiments} suggest that recourses can be exploited to infer private information about the underlying training set. This raises a natural question: Is privacy leakage through recourses inevitable?

Over the last decade, differential privacy \cite{privacybook} has emerged as the canonical approach to provably preventing membership inference for a wide array of statistical tasks. Applying this to the recourse setting, results which have been folklore in the privacy community imply that if the recourse generation algorithm is DP in the training data, we can provably bound the success of \emph{any} adversary $\mathcal{A}$ in the Recourse-based MI Game. In Theorem~\ref{priv_thm} (proof deferred to Supplement) we state a variant of the folklore result tailored to our setting, showing that not only can we bound the excess accuracy of the adversary over random guessing,  we can also bound the balanced accuracy (BA). Since $\text{BA} = \frac{\text{TPR} + \text{TNR}}{2}$, this implies that for a small FPR $\alpha$, the TPR of $\mathcal{A}$ is also close to $\alpha$. Recent work advocates for evaluating the success of MI attacks at low FPR instead of just looking at the overall accuracy \cite{enhanced_mi, carlini2021}.

\begin{theorem}\label{priv_thm}
Let $\mathcal{T}: (\mathcal{X} \times \mathcal{Y})^{n} \to \Theta$ denote the training algorithm, draw $D_t \sim \mathcal{D}^n$ and  and $\mathcal{A}$ be an arbitrary adversary that receives $z = (x, y), s \sim \mathcal{R}(f_{\theta},x, D_t)$  from the recourse inference game, and produces a guess $G \in \{\text{MEMBER}, \text{NON-MEMBER}\}.$ Then, if $\mathcal{R}$ is $(\epsilon,0)$-differentially private, we have for all $\mathcal{A}$:
\vspace{-0.1in}
$$\text{BA}_{\mathcal{A}} \leq \frac{1}{2} + \frac{1-e^{-\epsilon}}{2}.$$
\end{theorem}
\vspace{-0.1in}
While Theorem~\ref{priv_thm} provides strong privacy guarantees, for several reasons both generic and specific to the recourse setting, \emph{differential privacy is not a silver bullet to defend recourses against membership inference attacks}. It is known that training with DP causes a significant drop in accuracy on even relatively simple benchmarks \cite{temp_sig}, and so when accuracy is a concern this defense may not be feasible. Moreover, model accuracy aside, private training could alter the distance between training points and the model boundary, potentially leading to costlier and less actionable recourses for individuals.

\subsection{Setup}
\paragraph{Datasets}
Our first data set is the \emph{Adult} (A) data set \cite{Dua:2019} that originates from the 1994 Census database, consisting of 14 attributes and 48,842 instances. The class label indicates whether an individual has an income greater than 50,000 USD/year. Second, we use the \emph{Home Equity Line of Credit} \emph{(Heloc)} (H) data set ($d=23$). Here, the target variable records a score indicating whether individuals will repay the Heloc account within a fixed time window. Across both tasks we consider individuals in need of recourse if their scores lies below the median score across the entire data set, thresholding the scores based on the median to obtain binary target labels.
Third, we use the \emph{Diabetes} (D) data set which contains information on diabetic patients from 130 different US hospitals \citep{strack2014impact}.
The patients are described using administrative (e.g., length of stay) and medical records (e.g., test results) ($d=42$), and the prediction task is concerned with identifying whether a patient will be readmitted within the next 30 days.
In line with \citep{shorki2021explanation}, we sub sampled smaller data sets of 10000 points from each of these datasets. 5000 points are left to the model owner to train the their private model, while another 5000 data points are used by the adversary to train their shadow models when applicable.

Additionally, we follow \citet{shorki2021explanation} and generate synthetic data sets from the sklearn library.
For $d$ features the method randomly chooses a vertex from the $d$-dimensional hypercube as a center for each of the classes, and samples Gaussian distributed random variables centered at the vertex with unit variance.
For the linear model experiments, we use $d\in \{100, 1000, 5000, 7000\}$ with $n=5000$ training and test samples.
For the non-linear models we use $d\in \{50, 150\}$.

\textbf{Recourse Algorithms and Predictive Models.}
We apply our techniques to three different methods which aim to generate low-cost recourses using different principles: \texttt{SCFE} is the method suggested by \citet{wachter2017counterfactual} and uses a gradient-based objective to find recourses, \texttt{GS} conducts a random search for recourse in the input space \citep{laugel2017inverse}, and \texttt{CCHVAE} \citep{pawelczyk2019} searches for recourse in a lower dimensional latent space using a generative model to encourage recourses to lie on the data manifold.
All methods use a $\ell_1$-regularizer to encourage sparse recourses.
We use implementations from the \texttt{CARLA} library \citep{pawelczyk2021carla}.
For all data sets, we trained a fully connected neural network with one hidden layer and 1000 nodes.
The network uses ReLU activation functions and are trained using the ADAM optimizer.
The network is trained for 250 epochs.
Across all tasks, we use a learning rate of 0.0001.
All recourses were generated with respect to this classifier.

\paragraph{Baseline Attacks.}
We implement several baseline attacks:
the baseline of random guessing that for a target FPR $\alpha$ predicts \texttt{MEMBER} with probability $\alpha$, and baselines based on the loss $\ell$.
The loss-based baselines are simple thresholding on the loss \cite{yeom2017privacy} (i.e., \texttt{Loss}), and the offline loss-based LRT \cite{carlini2021} (i.e., \texttt{Loss LRT}).

\paragraph{Evaluation Measures.} We use several well established measures to validate the efficacy of our proposed membership inference attacks. Consistent with with previous works \citep{yeom2017privacy,shokri2017membership,shorki2021explanation} we report balanced accuracy (BA) and receiver operating characteristic (ROC) area under the curve (AUC) scores.  Additionally, we follow \citep{carlini2021,enhanced_mi} and also report log-scale ROC curves, and true positive rates of the attacks at low false positive rates. The authors argue that, for membership inference attacks, average case metrics such as BA and AUC are not well suited.
The underlying idea is that if a membership inference attack can  identify even a very small subset of the training data with very high confidence, then the attack should be considered successful.
We follow this intuition and primarily report our findings using this metric.

\subsection{Evaluating the Attack Efficacy} \label{subsec:eval_attack_efficacy}
\vspace{-0.1in}
Inspecting Figure~\ref{fig:real_world_all_methods}, we see that for nearly all datasets across all methods, at sufficiently low FPR the \texttt{CFD LRT} curve lies above the diagonal, outperforming the random baseline; the one exception being the Adult dataset with recourses generated from \texttt{GS}. \texttt{CFD} also often outperforms the random baseline in most cases, but not on the Diabetes dataset with recourse method \texttt{SCFE} or the Heloc dataset with method \texttt{CCHVAE}. These trends are reflected in the metrics captured in Table~\ref{table:comparing_efficacy}, where \texttt{CFD LRT} achieves TPR $> .01$ at FPR $= .01$, and AUC $> .5$ in $7$ of the $8$ dataset-recourse settings. \texttt{CFD} achieves TPR $> .01$ at FPR $= .01$ in $4$ of the $8$ settings. Focusing on the metric of TPR at FPR $= .01$, we see that in the $7$ of $8$ settings where either method outperforms the random baseline, \texttt{CFD LRT} achieves higher TPR than \texttt{CFD} $5$ times. This difference is particularly evident on the Heloc dataset, where \texttt{CFD LRT} obtains TPR $35\%, 270\%$, and $413\%$ above the random baseline for \texttt{SCFE}, \texttt{GS}, \texttt{CCHVAE} respectively. In summary, both methods often outperform the random baseline across all metrics, showing substantial privacy leakage from algorithmic recourses, with \texttt{CFD LRT} generally outperforming \texttt{CFD}. The results also show that the Heloc dataset is particularly vulnerable to distance-based attacks across all recourse algorithms, with the Diabetes dataset being less susceptible. On the Adult and Diabetes datasets the distance-based attacks usually outperform random guessing, however, the improvement over the random baseline is less pronounced.

Perhaps most interesting, is that only in the case of \texttt{CCHVAE} do the \texttt{CFD LRT} attacks that outperform the random baseline and are plotted in Figure~\ref{fig:real_world_all_methods}(c), actually reverse the direction of the threshold. This means that for the \texttt{CFD LRT} curves in Figure~\ref{fig:real_world_all_methods}(c) and metrics in Table~\ref{table:comparing_efficacy} in column \texttt{CCHVAE}, rather than predicting \texttt{MEMBER} in Line $12$ of Algorithm~\ref{alg:thresh_lrt} if $c(x,x') > z_{1-\alpha}$, we predict \texttt{MEMBER} iff $c(x,x') < z_{\alpha}$. While these results stand in contrast to our findings for \texttt{SCFE} and \texttt{GS}, there is an intuitive explanation.   \texttt{CCHVAE} trains a VAE to model the data generating distribution, and performs sampling \emph{in the latent space} to find a point in latent space $z'$ that is close to the representation of $x$ in the latent space $\text{encode}(x) = z_{x}$. Then it outputs the recourse $x' = \text{decode}(z')$ in the input space. Regardless of the specific $z'$ found by the recourse algorithm, $\text{decode}(z')$ is still in the range of the generative model. It is a known property of generative models like VAEs and GANs that their generated samples tend to be closer to training points than to test points, a fact which has been exploited for MI \cite{gan_survey}. One explanation for the results in Figure~\ref{fig:real_world_all_methods}(c) is that this property of generative models is in some cases outweighing the effect of the optimization during model training.

\subsection{Towards Understanding Attack Success}
\label{subsec:understanding}
To better understand the factors underlying these impressive results, in this section we use experiments on synthetic data with $\mathcal{R} = \texttt{SCFE}$ to examine the role of model type, model size, and number of features in attack success.

\textbf{Linear Models.}
One potential confounding factor in assessing the results for \texttt{SCFE}, is that when $f_\theta(x)$ is non-convex so is the objective in Equation~\ref{eqn:generalrecourse_un}, and so there is no guarantee that the recourse output is close to globally optimal. In the case when $f_{\theta}$ is linear the objective is convex and has a closed form minimizer \cite{pawelczyk2022algorithmic, label-only}. In Figure~\ref{fig:linear_synth_experiments} we train logistic regression models on the synthetic data, varying the number of features, and plotting the distribution of the counterfactual distances for train and test points, as well as the log-scaled ROC curves. We observe that the training distance distribution starts moving away from the test distance distribution as the number of feature dimensions increases (see Figure \ref{fig:linear_distances}), and as expected the distance-based attack starts performing better as the number of features increases (see Figure \ref{fig:linear_tpr_fpr}).
Strikingly, the \texttt{CFD LRT} in particular not only outperforms the \texttt{CFD} and random baseline, but also thresholding based on the \texttt{Loss} and the \texttt{Loss LRT} --- attacks which have access to the full loss function and the label $y$. Figures~\ref{fig:linear_distances}, \ref{fig:linear_tpr_fpr} suggest two potential reasons why the results in Figure~\ref{fig:real_world_all_methods} for \texttt{SCFE} do not exhibit the same level of attack performance as on the synthetic data:
(i) Since the model classes are non-convex it could be due to our optimization failing to find the recourse that minimizes Equation~\ref{eqn:generalrecourse_un}, and (ii) Distance-based membership inference attacks are more effective in high dimensions, and the tabular datasets we experiment on are of relatively small dimension $d < 50$.

\input{figures/figures_linear_synth}
\textbf{Nonlinear models.}
\input{figures/figures_ann_synth}
So far we have studied the effect of the dimension on the attack success, which in the case of linear models is equal to the number of parameters.
To disentangle the effect that the number of features has from the effect that model capacity has on attack success, we use fully-connected neural networks for which we can control both factors independently.
We generate two synthetic data sets with $d =  50, 150$ respectively, and study to what extent an increase in model capacity, in this case the number of hidden nodes, impacts the performance of our attacks.
For $d=50$ the results in Figure \ref{fig:ann_synth_tpr_fpr_n10000_d50} suggest that increasing model capacity does not yield performance increases for our distance-based attacks.
On the other hand, when $d=150$ the results in Figure \ref{fig:ann_synth_tpr_fpr_n10000_d150} show that increasing model capacity drastically increases the attack success of the \texttt{CFD LRT}, while the simple \texttt{CFD} still does not work well.
For the model with the largest capacity, three layers of 1000 hidden nodes per layer, \texttt{CFD LRT} performs considerably better than even the \texttt{Loss LRT}.
Taken together these results suggest that a combination of high model capacity and high feature dimension increases the vulnerability of recourses to MI attacks, where feature dimension appears to play a  more important role.

\subsubsection*{\bibname}}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{hyperref}
\usepackage{url}
\usepackage{booktabs}
\usepackage{amsfonts}
\usepackage{nicefrac}
\usepackage{microtype}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{multirow}
\usepackage{xspace}
\usepackage{subcaption}

\usepackage{amssymb}
\usepackage{MnSymbol}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{bm}
\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}
\hypersetup{
colorlinks = true,
linkcolor = Brown,
anchorcolor = Brown,
citecolor = Mahogany,
filecolor = RoyalBlue,
menucolor = Green,
runcolor = cyan,
urlcolor = Green}
\newcommand{\sn}[1]{}
\newcommand{\map}[1]{\textcolor{pink}{[Martin: #1]}}
\newcommand{\hima}[1]{}
\newcommand{\hideh}[1]{}

\newcommand{\mathcal{A}^p\xspace}{\mathcal{A}^p\xspace}
\newcommand{\bx}[0]{\mathbf{x}}
\newcommand{\bz}[0]{\mathbf{z}}
\newcommand{\xc}[0]{\mathbf{x}'}
\newcommand{\bw}[0]{\mathbf{w}}
\newcommand{\bd}[0]{\mathbf{d}}
\newcommand{\mathcal{A}}{\mathcal{A}}
\newcommand{\mathcal{R}}{\mathcal{R}}
\newcommand{\mathcal{T}}{\mathcal{T}}
\newcommand{\mathcal{D}}{\mathcal{D}}
\newcommand{\mathcal{O}}{\mathcal{O}}
\newcommand{f_{\btheta}}{f_{\btheta}}

\newcommand{\bH}[0]{\mathbf{H}}
\newcommand{\bX}[0]{\mathbf{X}}
\newcommand{\bI}[0]{\mathbf{I}}

\newcommand{\bSigma}[0]{\mathbf{\Sigma}^{-1}}
\newcommand{\bdelta}[0]{\bm{\delta}}
\newcommand{\bomega}[0]{\bm{\omega}}
\newcommand{\btheta}[0]{\bm{\theta}}
\newcommand{\mathbf{o}}{\mathbf{o}}

\newcommand{\text{cost}}{\text{cost}}
\newcommand{\mathcal{M}\xspace}{\mathcal{M}\xspace}
\newcommand{c\xspace}{c\xspace}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{condition}{Condition}
\newtheorem{assumption}{Assumption}
\newtheorem{corollary}{Corollary}
\newtheorem{attack}{Attack}

\DeclareMathOperator*{\argmin}{arg\,min}
\title{On the Privacy Risks of Algorithmic Recourse}

\author{%
Martin Pawelczyk \\
University of Tübingen \\
\And
Himabindu Lakkaraju\thanks{Equal contribution} \\
Harvard University \\
\And
Seth Neel\footnotemark[1] \\
Harvard University\\
\\
}

\begin{document}
\maketitle

\begin{abstract}
\input{abstract.tex}
\end{abstract}

\section{Introduction}
\input{intro.tex}

\section{Related Work} \label{section:related_work}
\input{related_work.tex}

\section{Preliminaries} \label{section:preliminaries}
\input{prelims.tex}

\section{Our Framework}
\label{section:theory}
\input{method}
\input{diff_privacy}

\section{Experimental Evaluation}  \label{sec:experiments}
\input{experiments.tex}

\section{Conclusion}  \label{section:conlusion}
\input{conclusion.tex}

\subsection{Thresholding on Counterfactual Distance}\label{subsec:distance} \hima{TODO: Hima to take a pass on 4.1 to clean up.} In the recourse-based MI Game, all the adversary has access to is the original instance $x$ and its counterfactual $x'$ generated by recourse algorithm. Loss-based attacks perform well at determining whether a point is a \texttt{MEMBER} of the training set or not, because the model typically over-fits to the training points, leading to lower losses on these points than on the test set. One explanation for this loss-disparity that has been given in prior work \cite{shorki2021explanation}, is that during the training process, the decision boundary is forced away from training points. This suggests that points in the training set should be further from the boundary than points in the test set, motivating a distance-based attack that predicts a point is a \texttt{MEMBER} of the training set if its loss is below some threshold $\tau$. The distance of a point $x$ to the boundary can be computed as $c(x, x')$ where $x'$ is the solution to Equation~\ref{eqn:generalrecourse_un} with $\mathcal{A}^{p} = \mathbb{R}^d$.
So if we exactly optimize the objective function in Equation~\ref{eqn:generalrecourse_un} that underpins our recourse algorithms (with $\mathcal{A}^p\xspace = \mathbb{R}^d$), the counterfactual distance $c(x, x')$ is exactly the distance to the model boundary. While algorithms that focus on generating \emph{realistic} recourses~\cite{pawelczyk2019,karimi2021algorithmic} do not exactly optimize this objective in general, we can still view the distance to the recourse as a proxy for the distance of $x$ to the model boundary. Based on this intuition we have the following counterfactual distance (\texttt{CFD}) based attack:
\begin{align}
M_{\text{Distance}}(x) =
\begin{cases}
\emph{\texttt{MEMBER}} & \text{ if } c(x,x') \geq \tau_D \\
\emph{\texttt{NON-MEMBER}} & \text{ if } c(x,x') < \tau_D.
\end{cases}\label{eqn:threshold-dist}
\end{align}
Following \cite{carlini2021}, we assume for the first two attacks below that $\mathcal{A}$ knows apriori an optimal threshold $\tau_{\alpha}$ that maximizes a given TPR subject to a fixed FPR $\alpha$, as the purpose of these simple attacks is to illustrate the potential privacy leakage through the recourse output. In practice, we will be plotting the TPR vs. FPR curves over all values of the threshold $\tau_{\alpha}$ and so we will not need to pick a specific one.
\iffalse
In the case when the underling model is linear and the $\ell_2$ norm is used as the cost function there exists a closed-form expression for algorithmic recourse that simultaneously quantifies an input's distance to the decision boundary \citep{pawelczyk2021connections}:
\begin{equation}
x' = x - \frac{g_{\btheta}(x)}{\lambda + \lVert \btheta \rVert_2^2} \btheta,
\label{eq:closed_form}
\end{equation}
where $x'$ is the recourse, $\frac{g_{\btheta}(x)}{\lambda + \lVert \btheta \rVert_2^2} \btheta$ measures the distance from the input $x$ to the decision boundary, $g_{\btheta}: \mathcal{X} \to \mathbb{R}$ is the network's pre-sigmoid output, and $\lambda$ is the balance parameter.

\subsection{Approximate Loss-Based Attack}\label{subsec:attack_thresh}
Now assume we are in the PARA setting of the game, where $\mathcal{A}$ receives $z, x'$ and the predicted probability of a positive classification $(f_\theta(x'))_{y}$. Suppose further that our loss function $\ell(\theta, x, y)$ is $\lambda$-Lipschitz in $x$ with respect to our distance metric $c(\cdot, \cdot)$. By Lipschitzness we have:
\begin{equation}\label{eq:lip}
\ell(x', y, \theta) - \lambda c(x, x') \leq l(x, y, \theta) \leq l(x', y, \theta) + \lambda c(x, x').
\end{equation}
So $l(x', y, \theta)$ is a $\pm \lambda c(x, x')$ approximation to the true loss $l(x, y, \theta)$. Moreover, both of the upper and lower bounds on the RHS of Equation~\ref{eq:lip}  can be computed by $\mathcal{A}$ from the recourse algorithm's output itself. We know $x, x'$ and so we can compute $\lambda c(x, x')$, and $l(x', \theta, y)$ is a function of $(f_\theta(x'))_{y}$.
Hence $\mathcal{A}$ can use Equation~\ref{eq:lip} to compute an approximation to the true loss on the point $x, \; l(\theta, x, y)$. Algorithm~\ref{alg:thresh_lip} implements an approximate version of the loss-based threshold test using this recourse-based approximation.

\begin{algorithm}[H]
\begin{algorithmic}
\caption{Recourse Approximation to Loss-based Membership inference attack (\texttt{LipThresh}).}
\label{alg:thresh_lip}
\State \textbf{Inputs:} $\tau_{\alpha}, \lambda$
\State Receive point $(x, y)$, recourse $x'$, and estimated positive classification $f_{\btheta}(x')$.
\State Compute distance $\lambda \cdot c(x, x')$, and loss $l(x', y, \theta) = \log((1-f_{\btheta}(x'))^{1-y}(f_{\btheta}(x'))^{y})$.
\State Let $lb = l(x', y, \theta)-\lambda c(x,x'), ub = l(x', y, \theta) + \lambda \cdot c(x, x') $
\If{$lb > \tau_{\alpha}$}
    \State \textbf{Output:} $G$ = \texttt{\texttt{NON-MEMBER}}
\Else \If{$ub < \tau_{\alpha}$}
    \State \textbf{Output:} $G$ = \texttt{MEMBER}
\Else
    \State \textbf{Output:} UNKNOWN
\EndIf
\EndIf
\end{algorithmic}
\end{algorithm}

\fi

\subsection{Likelihood Ratio Test using Counterfactual Distance}\label{subsec:attack_thresh}
\begin{algorithm}[!ht]
\begin{algorithmic}[1]
\caption{One-sided Distance-based Likelihood Ratio Test (\texttt{CFD LRT})}
\label{alg:thresh_lrt}
\State \textbf{Inputs:} point $(x, y)$, recourse output $s = \texttt{GetRecourse}(x, f_{\btheta}), \mathcal{D}$; FP-Rate: $\alpha$, \# Shadow Models: $N$, $\mathcal{T} = \texttt{TrainClassifier}(\cdot)$
\State $\text{teststats} = []$
\State \textbf{Compute}: $t_0 = T(s) = c(x,x')$
\For{$i=1:N$}
\State Sample $\mathcal{D}_t^{(i)} \sim \mathcal{D}$
\State $f_{\btheta^{(i)}} = \texttt{TrainClassifier}(\mathcal{D}^{(i)})$
\State $s^{(i)} = \texttt{GetRecourse}(x, f_{\btheta^{(i)}})$
\State teststats $\xleftarrow{} T(s^{i}) = c(x, x'^{(i)})$
\EndFor
\State $\hat{\mu}_{\text{MLE}} = \frac{1}{N} \sum_{i=1}^N \big(\log c(x, \xc^{(i)}) \big)  \big)$
\State $\hat{\sigma}^2_{\text{MLE}}  = \frac{1}{N} \sum_{i=1}^N \big(\hat{\mu}_{\text{MLE}} - \log\big(c(x, \xc^{(i)})\big) \big)^2$
\If{$t_0$ > $z_{1-\alpha}$} \Comment{ $z_{1-\alpha}$ is the $1{-}\alpha$-quantile of $Z \sim \mathcal{LN}(\hat{\mu}_{\text{MLE}}, \hat{\sigma}^2_{\text{MLE}}$})
    \State \textbf{Output:} $G$ = \texttt{\texttt{NON-MEMBER}}
\Else
    \State \textbf{Output:} $G$ = \texttt{MEMBER}
\EndIf
\end{algorithmic}
\end{algorithm}
\citet{carlini2021} showed that \texttt{Loss LRT} attacks perform better than simple \texttt{Loss} thresholding. In Algorithm~\ref{alg:thresh_lrt} we present an LRT version of our counterfactual distance attack (\texttt{CFD LRT}).
As in prior work \cite{carlini2021, sablayrolles2019whitebox} since computing the LRT (Equation~\ref{eq:cfd_lrt}) exactly is intractable, we  make several modifications to the attack that allow us to compute it efficiently.
The full likelihood ratio given $c(x,x')$ is:
 \begin{equation}
 \label{eq:cfd_lrt}
     \Lambda =  \frac{ \Pr[c(x, x')|x \in D_t]} {\Pr[c(x, x')|x \not \in D_t]}.
 \end{equation}
 We model the distributions of our statistic $c(x, x')$ as log-Normal, and so in order to compute eqn.\ \eqref{eq:cfd_lrt}, we need to estimate $(\mu_{in}, \sigma_{in}), (\mu_{out}, \sigma_{out})$ where we assume that if $D_t\backslash \{x\} \sim \mathcal{D}, \theta \sim \mathcal{T}(\{x\} \cup D_t), x' \sim \mathcal{R}(x, \theta, D_t)$, then $\log c(x,x') \sim \mathcal{N}(\mu_{in}, \sigma_{in})$, and similarly when $x' \not \in D_t$, $\log c(x,x') \sim \mathcal{N}(\mu_{out}, \sigma_{out})$. Given access to $\mathcal{D}$ we can estimate the parameters $\mu, \sigma$ by drawing fresh datasets, training models $\theta$ -- with or without a given point $x$ -- and then computing the resulting counterfactual distances (Lines $5-8$). However, as in \cite{carlini2021} we note that to approximate the numerator, we have to perform this sampling and model training separately for each $x$ that we perform the attack on, which is computationally infeasible. Hence in Algorithm~\ref{alg:thresh_lrt} we present a one-sided version of the LRT, where in Lines $10-11$ we estimate $\mu_{out}, \sigma_{out}$, and our attack predicts $\texttt{MEMBER}$ if $c(x,x')$ has a sufficiently low likelihood under these parameters. Note that since $\mu_{out}, \sigma_{out}$ do not depend on $x$, we only need to perform the process of training Shadow models once, even if we are evaluating our attack on many different $x$'s.

\section{Proof of Theorem~\ref{priv_thm}}
\begin{proof}
Throughout the proof let the event that $\mathcal{A}$ recieves $(z, s)$ and outputs $G = \text{MEMBER}$ be denoted by $\mathcal{A}(z, s) =1$. First we prove the following simple lemma in the Appendix, which says that since the recourse is generated privately, the probability it takes on any value can't be changed by more than $e^{\epsilon}$ depending on whether a given point $z$ is in the training set.
\begin{lemma}\label{lem:sup_priv}
If $\mathbf{o}$ is any event, for any $z$:
$$ \Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o} | z \in D_t] \leq e^{\epsilon}\Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o}|z \not \in D_t]
$$
\end{lemma}

\begin{proof}
Fix arbitrary $D_t\backslash\{z\} = (z_2, \ldots z_n)$. Expanding
\begin{equation}
    \Pr_{s \sim \mathcal{R}, D_t \sim \mathcal{D}^n}[s \in \mathbf{o} | z \in D_t] = \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z, D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]
\end{equation}

By the definition of differential privacy, for arbitrary $z'$:
\begin{multline}
    \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z, D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)] \leq \\
    \int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} =  (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]
\end{multline}

Since this holds for arbitrary $z'$, we have:
\begin{multline}
\Pr[s \in \mathbf{o} | z \in D_t] \leq \inf_{z'}\left(\int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]\right) \leq \\
\mathbb{E}_{z' \sim \mathcal{D}}\left[\int_{(z_2, \ldots z_n) \sim \mathcal{D}^{n-1}}e^{\epsilon}\Pr_{s \sim \mathcal{R}}[s \in \mathbf{o} | z', D_t\backslash\{z\} = (z_2, \ldots z_n)]\Pr_{\mathcal{D}}[(z_2, \ldots z_n)]\right] = e^{\epsilon}Pr[s \in \mathbf{o}|z \not \in D_t],
\end{multline}

as desired.

\end{proof}

Recall that $\text{BA} = \frac{\text{FPR} + \text{TNR}}{2} = \frac{\Pr[\mathcal{A}(z, s) = 1 | z \in D_t] + \Pr[\mathcal{A}(z, s) = 0 | z \not \in D_t]}{2}$, and let $a^{1} = \Pr[\mathcal{A}(z, s) = 1 | z \in D_t]$, and $a^{0} = \Pr[\mathcal{A}(z, s) = 0 | z \not \in D_t]$. Then:
\begin{multline}
    a^1 = \Pr[\mathcal{A}(z, s) = 1 | z \in D_t] = \int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|z,s]\Pr[s|z \in D_{t}]\Pr_{\mathcal{D}}[z] \leq \\
\int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|x,s]\Pr_{\mathcal{D}}[x](e^{\epsilon}\Pr[s|z \not \in D_t]) = \\
\int_{s \in \mathcal{S}}\int_{z \in \mathcal{X} \times \mathcal{Y}}\Pr[\mathcal{A}(z, s) = 1|x,s]\Pr_{\mathcal{D}}[x](e^{\epsilon}\Pr[s]) = \\
e^{\epsilon}\Pr[A(x,s) = 1 | x \not \in D_t] = e^{\epsilon}(1-a_0),
\end{multline}
where the inequality follows from Lemma~\ref{lem:sup_priv}. Rearranging $a^1 \leq e^{\epsilon}(1-a_0)$  we get that $a_0 \leq 1-e^{-\epsilon}a_1$. Hence:
$$
\text{BA} \leq \frac{a^1 + (1-e^{-\epsilon}a^1)}{2} = \frac{1}{2} + \frac{a_1 ( 1-e^{-\epsilon})}{2}
$$
Since $a_1 \leq 1$ this gives the result, and we note that for small $\epsilon$ this can be improved to $\text{BA} \leq \frac{1}{2} + \frac{(2-e^{-\epsilon})(1-e^{-\epsilon})}{4}$.
\end{proof}

\section{TRAINING DETAILS}
\subsection{Classification Models}
\input{tables/linear_classification_accuracy}
\input{tables/ann_classification_accuracy_synthetic}
\input{tables/ann_classification_accuracy_realworld}

\subsection{Recourse methods}

\begin{itemize}
\item {\texttt{SCFE}}: As suggested in~\citet{wachter2017counterfactual}, an Adam optimizer is used to optimize the recourse objective.
We obtain recourses using an $\ell_1$ distance function, and the binary cross entropy loss between the counterfactual label and the target.

\item {\texttt{GS}}:
The explanation model uses a counterfactual search algorithm in the input space.
Particularly, instances are sampled within an $\ell_1$-norm ball with search radius search radius $r_i$ until recourse is successfully obtained.
The search radius of the norm ball is increased until recourse is found.

\item {\texttt{C-CHVAE}}: An autoencoder is additionally trained to model the data-manifold.
The explanation model uses a counterfactual search algorithm in the latent space of the AE.
Particularly, a latent sample within an $\ell_1$-norm ball with search radius $r_l$ is used until recourse is successfully obtained.
The search radius of the norm ball is increased until recourse is found.
All generative models use $8$ latent dimensions, and 20 nodes in the first and third hidden layer.
\end{itemize}

\section{ADDITIONAL EXPERIMENTAL RESULTS}
\begin{figure*}[h!]
\centering
\begin{subfigure}{\textwidth}
\centering
\scalebox{0.90}{%
\includegraphics[width=\textwidth]{plots/linear_thresholds_depth0.pdf}
}
\label{fig:linear_thresholds}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for logistic regression models trained on the synthetic data set by showing the attack accuracy as the threshold varies.
Both the LRT-Distance as well as the baseline distance attacks are the most competetive attacks.
The thresholds have been normalized to the range $[0,1]$.
}
\label{fig:linear_experiments}
\end{figure*}

\begin{figure*}[tb]
\centering
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features50_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=50, n=20000$}
\label{fig:ann_synth_tpr_fpr_n20000_d50}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features150_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=150, n=20000$}
\label{fig:fig:ann_synth_tpr_fpr_n20000_d150}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features50_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=50, n=30000$}
\label{fig:fig:ann_synth_tpr_fpr_n20000_d50}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features150_synthetic_ann_scfe_attacks_depth_all_width_all.pdf}
\caption{$d=150, n=30000$}
\label{fig:fig:ann_synth_tpr_fpr_n30000_d150}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for neural network models trained on the synthetic data set when \texttt{SCFE} is used for the attack. (a): two-layer network with 1000 hidden nodes. (b): three-layer neural network with 100 hidden nodes in each hidden layer. (c): three-layer neural networks with 333 hidden nodes in each hidden layer. (d): three-layer neural networks with 1000 hidden nodes in each hidden layer.
}
\label{fig:ann_synth_experiments_fpr_tpr_appendix}
\end{figure*}

\begin{figure*}[tb]
\centering
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features50_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=50, n=20000$}
\label{fig:ann_synth_thresholds_n20000_d50}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/40000_features150_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=150, n=20000$}
\label{fig:fig:ann_synth_thresholds_n20000_d150}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features50_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=50, n=30000$}
\label{fig:fig:ann_synth_thresholds_n20000_d50}
\end{subfigure}
\vfill
\begin{subfigure}{\textwidth}
\centering
\includegraphics[width=\textwidth]{plots/60000_features150_synthetic_ann_scfe_thresholds_depth_all_width_all.pdf}
\caption{$d=150, n=30000$}
\label{fig:fig:ann_synth_thresholds_n30000_d150}
\end{subfigure}
\caption{Demonstrating the efficacy of our proposed distance-based attack for neural network models trained on the synthetic data set when \texttt{SCFE} is used for the attack. (a): two-layer network with 1000 hidden nodes. (b): three-layer neural network with 100 hidden nodes in each hidden layer. (c): three-layer neural networks with 333 hidden nodes in each hidden layer. (d): three-layer neural networks with 1000 hidden nodes in each hidden layer.
The thresholds have been normalized to the range $[0,1]$ when necessary.
}
\label{fig:ann_synth_experiments_fpr_tpr_appendix}
\end{figure*}


\section{Introduction}
Let $n$ be a positive integer and $[n] \ceq \{1,\ldots,n\}$. Suppose that ${\mathcal{G}}=\bigl([n],E\bigr)$ is a simple graph. We associate an edge $e=\{i,j\} \in E$ with the transposition $\tau_e \ceq (i\,j) \in \mathfrak{S}_n$, where $\mathfrak{S}_n$ denotes the symmetric group of degree $n$.
D\'enes proved the following theorem.

\begin{theorem}[D\'enes \cite{denes1959representation-potmiothaos}. See also \cite{moszkowski1989solution-ejoc},  \cite{pawlowski2022chromatic-ac}]\label{t1}
\textit{Let $\mathcal{G}=\bigl([n],E\bigr)$ be a simple graph. The product $\tau_{e_m}\cdots\tau_{e_1}$ is an $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a tree.}
\end{theorem}

As a corollary, D\'enes also proved the following claim.

\begin{corollary}[D\'enes \cite{denes1959representation-potmiothaos}]
\textit{The number of representations of a $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$.}
\end{corollary}

We will extend Theorem $\ref{t1}$ for the hyperoctahedral group $\mathfrak{H}_n$. Since it is known that $\mathfrak{S}_n$ is a Weyl group of the root system of type $A_{n-1}$ and $\mathfrak{H}_n$ is a Weyl group of the root system of type $B_n$, It is a natural idea to consider this extension.

Let $I_n \ceq \{-n,\ldots,-1,1,\ldots,n\}$. The \textit{hyperoctahedral group} $\mathfrak{H}_n$ is a subgroup of the symmetric group $\mathfrak{S}_{I_n}$ of $I_n$, defined by
\[
\mathfrak{H}_n \ceq \bigset{\eta \in \mathfrak{S}_{I_n}}{\text{$\eta(-i)=-\eta(i)$ for all $i \in [n]$}}.
\]
An element $\eta \in \mathfrak{H}_n$, called a \textit{signed permutation}, is expressed as follows:
\[
\eta=\begin{pmatrix}
1&2&\cdots&n\\
\eta_1&\eta_2&\cdots&\eta_n
\end{pmatrix},
\]
where $\eta_1,\ldots,\eta_n \in I_n$ have different absolute values. In particular, given a permutation in $\mathfrak{S}_n$, the signed permutation in $\mathfrak{H}_n$ is naturally determined. Thus we can consider $\mathfrak{S}_n$ to be a subgroup of $\mathfrak{H}_n$.

There are three types of \textit{transpositions} in $\mathfrak{H}_n$. For $i,j$ be distinct numbers in $[n]$ and $\epsilon$ be a sign $+$ or $-$, we say that
\[
(i\ \epsilon j) \ceq \begin{pmatrix}
1&\cdots&i&\cdots&j&\cdots&n\\
1&\cdots&\epsilon j&\cdots&\epsilon i&\cdots&n
\end{pmatrix}
\]
is a \textit{positive transposition} if $\epsilon=+$ and a \textit{negative transposition} if $\epsilon=-$.  Note that we can consider a positive transposition as a transposition in $\mathfrak{S}_n$. For $i \in [n]$, we say that
\[
(i\,{-i}) \ceq \begin{pmatrix}
1&\cdots&i&\cdots&n\\
1&\cdots&{-i}&\cdots&n
\end{pmatrix}
\]
is an \textit{inversion transposition}.

A signed permutation is decomposed uniquely into a product of commuting signed cycles. For $i_1,\ldots,i_l$ be distinct numbers in $[n]$ and $\epsilon_1,\ldots,\epsilon_l \in \{+,-\}$, which we consider as a multiplicative group of order two in the natural way, given such a \textit{signed cycle} of size $l$
\[
\sigma=\begin{pmatrix}
i_1&i_2&\cdots&i_{l-1}&i_l\\
\epsilon_1i_2&\epsilon_2i_3&\cdots&\epsilon_{l-1}i_l&\epsilon_li_1
\end{pmatrix},
\]
we say that $\sigma$ is an \textit{even $l$-cycle} if $\epsilon_1\cdots\epsilon_l=+$ and an \textit{odd $l$-cycle} if $\epsilon_1\cdots\epsilon_l=-$. In addition, we denote
\[
\sigma=\bigl(i_1\ \epsilon_1i_2\ (\epsilon_1\epsilon_2)i_3\ \cdots\cdots\ (\epsilon_1\cdots\epsilon_{l-1})i_l\bigr)_{\epsilon_1\cdots\epsilon_l}.
\]
Sometimes, $\sigma$ is written as
\[
\sigma=\bigl({-}i_1\ {-}\epsilon_1i_2\ {-}(\epsilon_1\epsilon_2)i_3\ \cdots\cdots\ {-}(\epsilon_1\cdots\epsilon_{l-1})i_l\bigr)_{\epsilon_1\cdots\epsilon_l}.
\]
Note that we see that
\[
(i\,j)_+=(i\,j),\quad (i\,j)_- \neq (i\,{-j}),\quad (i)_-=(i\,{-i}).
\]

The \textit{cycle type} of the signed permutation $\eta$ is the pair of partitions $(\lambda,\mu)$, where
$\lambda$ (resp\priod $\mu$) is the integer partition consisting of the length of even (resp\priod odd) cycles appearing in the decomposition of $\eta$.
For example, if
\[
\eta \ceq \begin{pmatrix}
1&2&3&4&5&6&7&8\\
-5&4&-3&2&-8&7&-6&1
\end{pmatrix} \in \mathfrak{H}_8,
\]
then
\[
\eta = (1\ {-}5\  8)_+(2\ 4)_+(3)_-(6\ 7)_-
\]
and the cycle type of $\eta$ is $\bigl((3,2),\, (2,1)\bigr)$.

The cycle type of an even $n$-cycle is $\bigl((n),0\bigr)$ and that of an odd $n$-cycle is $\bigl(0,(n)\bigr)$. Note that two signed permutations have the same cycle type if and only if they are conjugate.

We introduce the signed graph to consider an analogy of D\'enes' results for $\mathfrak{H}_n$. Here, define a \textit{signed graph} as a quadruple $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$, where $E^+$ and $E^-$ are collections consisting of unordered pairs of elements in $[n]$, and $L$ is a subset of $[n]$. An element in $[n]$ is called a \textit{vertex}, an element in $E^+$ (resp\priod $E^-$) is called a \textit{positive} (resp\priod \textit{negative}) \textit{edge}, and an element in $L$ is called a \textit{loop}. A signed graph $\mathcal{G}$ is a \textit{signed tree} (resp\priod \textit{cycle}) if $E^+ \cap E^-=L=\emptyset$ and the underlying simple graph $\bigl([n],E^+ \cup E^-\bigr)$ is a tree (resp\priod cycle). Let $E \ceq E^+ \sqcup E^- \sqcup L$. For every $e \in E$, define a transposition $\tau_e \in \mathfrak{H}_n$ by
\[
\tau_e \ceq \begin{cases}
(i\ {j})&\text{if } e=\{i,j\} \in E^+,\\
(i\ {-j})&\text{if } e=\{i,j\} \in E^-,\\
(i\ {-i})&\text{if } e=i \in L.
\end{cases}
\]
The main results are as follows:

\begin{theorem}\label{t2}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a  signed graph. Then the following two claims hold:
\begin{enumerate}[(A)]
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an even number of loops;\label{t211}
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an odd number of loops.\label{t221}
\end{enumerate}}
\end{theorem}

\begin{corollary}\label{c4}
\textit{
\begin{enumerate}[(A)]
\item The number of representations of an even $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$;
\item The number of representations of an odd $n$-cycle by means of product of $n$ transpositions is $n^n$.
\end{enumerate}}
\end{corollary}

{For Corollary $\ref{c4}$, a more general claim is already known (see \cite[Theorem 7.5]{bessis2015finite-aom} and below for example). In this paper, we prove Corollary $\ref{c4}$ by counting the number of sequences consisting of $n-1$ (resp\priod $n$) of transpositions such that the product is an even (resp\priod odd) $n$-cycle. }

The organization of this paper is as follows.
In Section $\ref{sec2}$, we prove the special case of Theorem $\ref{t2}$.
In Section $\ref{sec3}$. we prove Theorem $\ref{t2}$ and Corollary $\ref{c4}$.

\section{Signed graphs without loops and 2-cycle graphs} \label{sec2}
First, we review the properties of transpositions and signed cycles in $\mathfrak{H}_n$ necessary for the proof of Theorem $\ref{t2}$. We do not prove the following two lemmas since their proofs are easy.

\begin{lemma}\label{l1}
\textit{Let $i,j,k \in [n]$ be distinct integers.  Then the following three claims hold:
\begin{enumerate}[(i)]
\item $(i\ {-j})=(i\ {-i})(j\ {-j})(i\ {j})$; \label{l11}
\item $(i\ {j})(j\ {-j})=(i\ {-i})(i\ {j})$; \label{l12}
\item $(i\ {j})(k\ {-k})=(k\ {-k})(i\ {j})$. \label{l13}
\end{enumerate}
In particular, every signed permutation in $\mathfrak{H}_n$ is represented by the product of some inversion transpositions and the product of some positive transpositions.}
\end{lemma}

\begin{lemma}\label{l2}
\textit{Suppose that $i_1,\ldots,i_l \in I_n$ have different absolute values and $\epsilon \in \{+,-\}$.  Then the following two claims hold:
\begin{enumerate}[(i)]
\item $(i_1\ i_2\ \cdots\ i_l)_\epsilon=(i_2\ \cdots\ i_l\ \epsilon i_1)_\epsilon$; \label{}
\item $(i_1\,{-i_1})(i_1\ \cdots\ i_l)_\epsilon=(i_1\ \cdots\ i_l)_{-\epsilon}$. \label{}
\end{enumerate}
In particular, the product of an even (resp\priod odd) $n$-cycle and an inversion transposition is an odd  (resp\priod even) $n$-cycle.}
\end{lemma}

Before the proof of Theorem $\ref{t2}$, as a special case, assume that a signed graph $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ has no 2-cycle graphs and $L=\emptyset$, where a 2-cycle graph is a signed graph on two vertices with a positive edge and a negative edge joining them.
{For $e \in E^+ \cup E^-$, define $\tau'_e \in \mathfrak{S}_n \subset \mathfrak{H}_n$ as the positive transposition exchanging the endvertices of $e$.}
\begin{lemma}\label{l23}
{\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a signed graph without 2-cycle graphs and $L=\emptyset$. Then
\begin{enumerate}[(i)]
\item For a linear order $(e_1,\ldots,e_m)$ on $E$, the product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle if and only if the product $\tau_{e_m}'\cdots\tau_{e_1}'$ is an even $n$-cycle; \label{i3}
\item For any linear order $(e_1,\ldots,e_m)$ on $E$, the product $\tau_{e_m}\cdots\tau_{e_1}$ is not an odd $n$-cycle.\label{ii3}
\end{enumerate}}}
\end{lemma}
\begin{proof}
{For a linear order $(e_1,\ldots,e_m)$ on $E$, let $\eta \ceq \tau_{e_m}\cdots\tau_{e_1}$ and $\eta' \ceq \tau_{e_m}'\cdots\tau_{e_1}'$. If $e_i \in E^-$, then the negative transposition $\tau_{e_i}$ is represented as the product of two invertion transpositions and the positive transposition $\tau_{e_i}'$ by Lemma $\ref{l1}$ $\eqref{l11}$. Then we get
\begin{align}
\eta =\nu_1\cdots \nu_s\cdot \eta' \label{ss1}
\end{align}
by Lemma $\ref{l1}$ $\eqref{l12}$ and $\eqref{l13}$, where $\nu_1,\ldots,\nu_s$ are inversion transpositions and $s=2|E^-|$. Hence $\eqref{i3}$ is true by Lemma $\ref{l2}$.}

{Assume that the product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for some linear order $(e_1,\ldots,e_m)$ on $E$. By Lemma $\ref{l2}$ and the equality $\eqref{ss1}$, we obtain that the product $\tau_{e_m}'\cdots\tau_{e_1}'$ is also an odd $n$-cycle, which is a contradiction to the fact that $\tau_{e_m}'\cdots\tau_{e_1}' \in \mathfrak{S}_n$. Therefore $\eqref{ii3}$ is true.}
\end{proof}

The proof in this case follows from Theorem $\ref{t1}$.

\begin{theorem}\label{t3}
\textit{Let $\mathcal{G}=\bigl( [n],E^+,E^-,L\bigr)$ be a signed graph without 2-cycle graphs and $L=\emptyset$. The product $\tau_{e_m}\cdots \tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree.}
\end{theorem}
\begin{proof}
Define a simple graph $\bar{\mathcal{G}}=\bigl([n],\bar{E}\bigr)$, where $\bar{E}=E^+ \cup E^-$. Since $\mathcal{G}$ has no loops and 2-cycle graphs, $\mathcal{G}$ is a signed tree if and only if $\bar{\mathcal{G}}$ is a tree. Since $\mathcal{G}$ has no 2-cycle graphs, a linear order on $\bar{E}$ determines naturally a linear order on $E$, and vice versa.

Suppose that the product $\tau_{e_m}\cdots \tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$. By Lemma $\ref{l23}$, the product $\tau_{e_m}'\cdots \tau_{e_1}'$ is an $n$-cycle for any linear order on $\bar{E}$. Therefore we get that $\bar{\mathcal{G}}$ is a tree by Theorem $\ref{t1}$. Thus $\mathcal{G}$ is a signed tree. The proof of the converse is similar.
\end{proof}

\section{Proof of Theorem 1.3 and Corollary 1.4}\label{sec3}

First, we prove the following a claim necessary for the proof of Theorem $\ref{t2}$.
\begin{lemma}\label{l3}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a signed graph. If $\mathcal{G}$ has a cycle (including 2-cycle graph), then there exists a linear order $(e_1,\ldots,e_m)$ on $E$ such that the product $\tau_{e_m}\cdots\tau_{e_1}$ is neither an even $n$-cycle nor an odd $n$-cycle.}
\end{lemma}
\begin{proof}
Let $\gamma$ be a minimal cycle of $\mathcal{G}$ with vertices $\{v_1,\ldots,v_r\}$, edges $\{c_1,\ldots,c_r\}$, where $c_i$ connects $v_i$ and $v_{i+1}$ for all $1 \leq i \leq r-1$ and $c_r$ connects $v_r$ and $v_1$.

Let $\{b_1,\ldots,b_s\}$ be the set of edges of $\mathcal{G}$ incident to $v_r$ except $c_r$ and $c_1$. Suppose that $d_1,\ldots,d_t$ are the other edges of $\mathcal{G}$. Then
\[
E =\{c_1,\ldots,c_r,b_1,\ldots,b_s,d_1,\ldots,d_t\}.
\]
Define
\[
\eta \ceq \tau_{b_1} \cdots \tau_{b_s}\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1}.
\]
We obtain
\begin{align}
(\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1)=\epsilon\cdot v_r, \label{s2}
\end{align}
where $\epsilon  \in \{+,-\}$. For all $1 \leq i \leq t$, since $d_i$ is not incident to $v_r$,
\begin{align}
\begin{aligned}
(\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1) &= (\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t})(\epsilon\cdot v_r)\\
&=\tau_{c_r}(\epsilon \cdot v_r)\\
&=\epsilon'\epsilon\cdot v_1
\end{aligned}\label{s3}
\end{align}
by $\eqref{s2}$, where $\epsilon'$ is a sign of the edge $c_s$.

Assume that there exists $j_0$ such that $b_{j_0}$ is an edge incident to $v_1$. Since edges $b_{j_0}$ and $c_r$ form a 2-cycle graph, $r=2$ by the minimality of $\gamma$. Then edges $c_1$ and $c_r$ form a 2-cycle graph. Thus we get $c_1=b_{j_0}$, which is a contradiction. Therefore we know that $b_j$ is not incident to $v_1$ for any $1 \leq j \leq s$. Hence
\begin{align}
\begin{aligned}
\eta(v_1) &= (\tau_{b_1} \cdots \tau_{b_s}\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1)\\
&= (\tau_{b_1} \cdots \tau_{b_s})(\epsilon'\epsilon\cdot v_1)\\
&= \epsilon'\epsilon\cdot v_1
\end{aligned}\label{s4}
\end{align}
by $\eqref{s3}$. The equality $\eqref{s4}$ indicates that $\eta$ is neither an even $n$-cycle nor an odd $n$-cycle.
\end{proof}

\begin{figure}[h]
\begin{tikzpicture}
\node (0) at (-8.3,0) {};
\node(00) at (0,0) {$\gamma$};
\node[v] (1) at (-1.3,1.3) {};
\node[v] (2) at (0,2.6) {};
\node[v] (3) at (1.3,1.3) {};
\node[v] (4) at (2.6,0) {};
\coordinate (5) at (1.3,-1.3) {};
\coordinate (7) at (-1.3,-1.3) {};
\node[v] (8) at (-2.6,0) {};
\draw[dashed] (5) -- (7) -- node[below left]{$c_{r-1}$} (8) (4) -- node[below right]{$c_4$} (5);
\draw (8) node[left]{$v_r$} -- node[above=5pt, left=-2pt]{$c_r$} (1) node[below=8pt,right=-4pt]{$v_1$} -- node[below right]{$c_1$} (2) node[above]{$v_2$} --node[above=5pt, right=-2pt]{$c_2$} (3) node[below left]{$v_3$} -- node[above=5pt, right=-2pt]{$c_3$} (4) node[below right]{$v_4$};
\node[v] (a) at (-3.2,1.8) {};
\node[v] (aa) at (-2,3) {};
\node[v] (b) at (-4,3.2) {};
\node[v] (c) at (4,1.3) {};
\draw (b) -- node[left]{$d_1$} (a) -- node[above]{$b_1$} (1) -- node[right]{$b_2$} (aa);
\draw (c) -- node[below=5pt, right=-2pt]{$d_2$} (4);
\end{tikzpicture}
\caption{A graph in Lemma $\ref{l3}$.}
\label{f1}
\end{figure}

Now, we are ready to prove Theorem $\ref{t2}$.
\begin{theorem}[Restatement of Theorem $\ref{t2}$]\label{t32}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a  signed graph. Then the following two claims hold:
\begin{enumerate}[(A)]
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an even number of loops;\label{t21}
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an odd number of loops.\label{t22}
\end{enumerate}}
\end{theorem}

\begin{proof}
We will show only $\eqref{t21}$ since $\eqref{t22}$ can be proved with a rewording of the proof of $\eqref{t21}$ slightly.

Assume that the product determined by any linear order on $E$ is an even $n$-cycle. Let $\mathcal{G}'=\bigl([n],E^+,E^-,\emptyset\bigr)$ be a  signed graph obtained by removing loops from $\mathcal{G}$ and $E' \ceq E^+ \sqcup E^-$. By Lemma $\ref{l3}$, $\mathcal{G}$ and $\mathcal{G}'$ have no 2-cycles. We need to show that $\mathcal{G}'$ is a signed tree.

Let $(e_1,\ldots,e_m)$ be a linear order on $E'$ and $\eta' \ceq \tau_{e_m}\cdots\tau_{e_1}$. Extending the linear order $(e_1,\ldots, e_m)$, we can obtain the linear order $C \ceq (e_1,\ldots, e_m, l_1,\ldots,l_s)$ on $E$, where $L=\{l_1,\ldots,l_s\}$. Suppose that $\eta$ is the product determined by $C$. Namely,
\begin{align}
\eta=\tau_{l_s} \cdots\tau_{l_1}\cdot \eta'. \label{ss5}
\end{align}
Note that $\tau_{l_1},\ldots,\tau_{l_s}$ are inversion transpositions. By Lemma $\ref{l2}$, Lemma $\ref{l23}$, and the equality $\eqref{ss5}$, we obtain that $\eta'$ is an even $n$-cycle and $s$ is even since $\eta$ is an even $n$-cycle. Therefore we get that $\mathcal{G}'$ is a signed tree by Theorem $\ref{t3}$. Thus $\mathcal{G}$ is a signed tree with an even number of loops. The proof of the converse is similar. Theorem $\ref{t2}$ $\eqref{t21}$ is presented now.
\end{proof}

Next, we prove Corollary $\ref{c4}$.
\begin{corollary}[Restatement of Corollary $\ref{c4}$]
\textit{
\begin{enumerate}[(A)]
\item The number of representations of an even $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$;
\item The number of representations of an odd $n$-cycle by means of product of $n$ transpositions is $n^n$.
\end{enumerate}}
\end{corollary}
\begin{proof}
Let $N_A$ (resp\priod $N_B$) be the number of representations of an even (resp\priod odd) $n$-cycle by means of product of $n-1$ (resp\priod $n$) transpositions. Suppose that $W_A$ (resp\priod $W_B$) be the number of sequences consisting of $n-1$ (resp\priod $n$) transpositions such that the product is an even (resp\priod odd) $n$-cycle. There are $(n-1)!\cdot 2^{n-1}$ even (resp\priod odd) $n$-cycles since a signed $n$-cycle is denoted by $(1\ i_2\ i_3\ \cdots\ i_n)_\epsilon$ and a signed $n$-cycle is determined by sequence consisting $2,\ldots,n$ without repetition and sequence consisting $n-1$ signs. Thus we get
\begin{align}\label{s5}
W_A=(n-1)!\cdot 2^{n-1}\cdot N_A,\quad W_B=(n-1)!\cdot 2^{n-1}\cdot N_B.
\end{align}
On the other hand, the number of vertex-labeled trees with $n$ vertices is $n^{n-2}$ by Cayley's fomula.  By Theorem $\ref{t2}$, we know
\begin{align}\label{s6}
W_A=n^{n-2}\cdot 2^{n-1}\cdot (n-1)!,\quad W_B=n^{n-2}\cdot 2^{n-1}\cdot n\cdot n!.
\end{align}
Therefore we obtain
\[
N_A=n^{n-2},\quad N_B=n^n
\]
by $\eqref{s5}$ and $\eqref{s6}$.
\end{proof}

\bibliographystyle{amsplain}