\section{Introduction}

For an integer $k \geq 2$ and a $k$-uniform hypergraph $H$, the \emph{Ramsey number} $R(H)$ is the minimum $N \in \mathbb{N}$ such that every 2-coloring of the hyperedges of the complete $k$-uniform hypergraph $K^{(k)}_N$ on~$N$ vertices contains a monochromatic subhypergraph isomorphic to $H$.
Estimating Ramsey numbers is a notoriously difficult problem.
Despite many efforts in the last 70 years, no tight bounds are known even for the complete graph $K_n$ on $n$ vertices.
Apart from some smaller term improvements, essentially the best known bounds are $2^{n/2} \leq R(K_n) \leq 2^{2n}$ by Erd\H{o}s~\cite{erdosSzekeres35} and by Erd\H{o}s and Szekeres~\cite{erdos47}.
The Ramsey numbers $R(K^{(k)}_n)$ are even less understood for $k \geq 3$.
For example, it is only known that
\begin{equation}
\label{eq-hypergraphRamsey}
2^{\Omega(n^2)} \leq R(K^{(3)}_n) \leq 2^{2^{O(n)}},
\end{equation}
as shown by Erd\H{o}s, Hajnal, and Rado~\cite{erdosRado65}.
A famous conjecture of Erd\H{o}s, for whose proof Erd\H{o}s offered \$500 reward, states that there is a constant $c>0$ such that $R(K^{(3)}_n) \geq 2^{2^{cn}}$.

Recently, a variant of Ramsey numbers for hypergraphs with a fixed order on their vertex sets has been introduced~\cite{bckk13,clfs17}.
For an integer $k \geq 2$, an \emph{ordered $k$-uniform hypergraph} $\mathcal{H}$ is a pair $(H,<)$ consisting of a $k$-uniform hypergraph $H$ and a linear ordering $<$ of its vertex set.
An ordered $k$-uniform hypergraph $\mathcal{H}_1=(H_1,<_1)$ is an \emph{ordered subhypergraph} of another ordered $k$-uniform hypergraph $\mathcal{H}_2=(H_2,<_2)$, written $\mathcal{H}_1 \subseteq \mathcal{H}_2$, if $H_1$ is a subhypergraph of $H_2$ and $<_1$ is a suborder of $<_2$.
Two ordered hypergraphs $\mathcal{H}_1$ and $\mathcal{H}_2$ are \emph{isomorphic} if there is an isomorphism between their underlying hypergraphs that preserves the vertex orderings of $\mathcal{H}_1$ and $\mathcal{H}_2$.
Note that, up to isomorphism, there is a unique ordered complete $k$-uniform hypergraph $\mathcal{K}^{(k)}_n$ on $n$ vertices.

The \emph{ordered Ramsey number} $\overline{R}(\mathcal{H},\mathcal{G})$ of two ordered $k$-uniform hypergraphs $\mathcal{H}$ and $\mathcal{G}$ is the smallest $N \in \mathbb{N}$ such that every coloring of the hyperedges of $\mathcal{K}^{(k)}_N$ by colors red and blue contains a blue ordered subhypergraph isomorphic to $\mathcal{H}$ or a red ordered subhypergraph isomorphic to $\mathcal{G}$.
In the \emph{diagonal case} $\mathcal{H} = \mathcal{G}$, we just write $\overline{R}(\mathcal{G})$ instead of $\overline{R}(\mathcal{G},\mathcal{G})$.

The ordered Ramsey numbers are known to be finite and it is easy to see that they grow at least as fast as the standard Ramsey numbers.
Studying ordered Ramsey numbers has attracted a lot of attention lately (see the survey by Conlon, Fox, and Sudakov~\cite{cfsSurvey}), as there are various motivations coming from the field of discrete geometry.
It is known that ordered Ramsey numbers can behave quite differently than the standard Ramsey numbers, especially for sparse ordered graphs~\cite{bckk13,bjv16,clfs17}.
However, so far, the ordered Ramsey numbers have been studied mostly for ordered graphs only and very little is known about ordered Ramsey numbers of ordered $k$-uniform hypergraphs with $k \geq 3$.

In this paper, we focus on $3$-uniform hypergraphs and we prove some new bounds on the ordered Ramsey numbers of ordered tripartite $3$-uniform hypergraphs.
We also pose several new open problems in Section~\ref{sec-openProblems}.

\subsection{Preliminaries}

For an ordered $k$-uniform hypergraph $\mathcal{H}=(H,<)$ and two subsets $U$ and $V$ of vertices of~$\mathcal{H}$, we say that $U$ and $V$ are \emph{consecutive} if all vertices from $U$ precede all vertices of $V$ in~$<$.
An \emph{interval} in $\mathcal{H}$ is a subset $I$ of vertices of $\mathcal{H}$ such that for all vertices $u,v,w$ of $\mathcal{H}$ with $u<v<w$ and $u,w \in I$ we have $v \in I$.

For integers $k \geq 2$ and $\chi \geq k$, we use $K^{(k)}_\chi(n)$ to denote the \emph{complete $k$-uniform $\chi$-partite hypergraph}, that is, the vertex set of $K^{(k)}_\chi(n)$ is partitioned into $\chi$ sets of size $n$ and every $k$-tuple with at most one vertex in each of these parts forms a hyperedge.
The ordering of~$K^{(k)}_\chi(n)$, in which the color classes form consecutive intervals, is denoted by $\mathcal{K}^{(k)}_\chi(n)$.
We sometimes use $\mathcal{K}_{n,n}$ to denote $\mathcal{K}^{(2)}_2(n)$.

The \emph{degree} of a vertex $v$ in a hypergraph $H$ is the number of hyperedges of $H$ that contain~$v$.
For $d \in \mathbb{N}$, a $k$-uniform hypergraph $H$ is \emph{$d$-degenerate} if there is an ordering $v_1 \prec \cdots \prec v_t$ of vertices of $H$ such that each $v_i$ is contained in at most $d$ hyperedges of $H$ that contain a vertex from $v_1,\dots,v_{i-1}$.

For a positive integer $n$, we use $[n]$ to denote the set $\{1,\dots,n\}$.
We omit floor and ceiling sign whenever they are not crucial and we use $\log$ and $\ln$ to denote base $2$ logarithm and the natural logarithm, respectively.

\subsection{Previous results}
\label{subsec-previousResults}

The ordered Ramsey numbers of $k$-uniform ordered hypergraphs with $k \geq 3$ remain quite unexplored.
Only the ordered Ramsey numbers of so-called monotone hyperpaths are well understood due to their close connections to the famous Erd\H{o}s--Szekeres Theorem~\cite{erdosSzekeres35}; see~\cite{balko19,fpss12,moshShap14}.
A \emph{monotone hyperpath} $\mathcal{P}^{(k)}_n$ on $n$ vertices is an ordered $k$-uniform hypergraph where the hyperedges are formed by $k$-tuples of consecutive vertices.
Note that the maximum degree of a $k$-uniform monotone hyperpath is at most $k$.
Moshkovitz and Shapira~\cite{moshShap14} showed that $\overline{R}(\mathcal{P}^{(k)}_n) = {\rm tow}_{k-1}((2-o(1))n)$ for $k \geq 3$, where ${\rm tow}_h$ is the \emph{tower function} of height $h$ defined as ${\rm tow}_1(x)=x$ and ${\rm tow}_h(x) = 2^{{\rm tow}_{h-1}(x)}$ for $h \geq 2$.

Thus even for $3$-uniform hypergraphs $\mathcal{H}$ with bounded maximum degree the numbers $\overline{R}(\mathcal{H})$ can grow very fast.
We get an exponential lower bound on $\overline{R}(\mathcal{H})$ even for $3$-uniform ordered hypergraphs $\mathcal{H}$ with maximum degree $3$.
A similar result is known for ordered graphs, as for arbitrarily large values of $n$ there are ordered graphs $\mathcal{M}_n$ with $n$ vertices and maximum degree $1$ such that $\overline{R}(\mathcal{M}_n) \geq n^{\Omega(\log{n}/\log{\log{n}})}$~\cite{bckk13,clfs17}.
This superpolynomial growth rate is in sharp contrast with  the situation for unordered hypergraphs, where the Ramsey number $R(H)$ of every $k$-uniform hypergraph $H$ with bounded $k$ and with bounded maximum degree is at most linear in the number of vertices of~$H$~\cite{crst83,cfs09,cnko08,cnko09,ishingami07,nsrs08}.

Therefore, in order to obtain smaller upper bounds on the ordered Ramsey numbers, it is necessary to bound other parameter besides the maximum degree.
A natural choice is so-called interval chromatic number, which can be understood as an analogue of the chromatic number for ordered graphs due to a variant of the Erd\H{o}s--Stone--Simonovits theorem for ordered graphs proved by Pach and Tardos~\cite{pachTardos06}.
The \emph{interval chromatic number}
$\chi_<(\mathcal{H})$ of an ordered $k$-uniform hypergraph $\mathcal{H}$ is the minimum number of intervals the vertex set of $\mathcal{H}$ can be partitioned into so that each hyperedge of $\mathcal{H}$ has at most one vertex in each of the intervals.

For ordered graphs, bounding both parameters indeed helps, as the ordered Ramsey number $\overline{R}(\mathcal{G})$ of every ordered graph $\mathcal{G}$ with bounded maximum degree $d$ and bounded interval chromatic number $\chi$ is at most polynomial in the number of vertices~\cite{bckk13,clfs17}.
Since $\mathcal{G} \subseteq \mathcal{K}^{(2)}_\chi (n)$, this result follows from the following stronger estimate proved by Conlon, Fox, Lee, and Sudakov~\cite{clfs17}: for all $d, \chi \in \mathbb{N}$, every $d$-degenerate ordered graph $\mathcal{G}$ on $n$ vertices with interval chromatic number $\chi$ satisfies
\begin{equation}
\label{eq-degreeIntChrNumber}
\overline{R}(\mathcal{G},\mathcal{K}^{(2)}_\chi(n)) \leq n^{32 d \log{\chi}}.
\end{equation}

A natural question is whether we can also get some good upper bounds on ordered Ramsey numbers of similarly restricted classes of ordered hypergraphs.
If the interval chromatic number is bounded, then we can use a result of Conlon, Fox, and Sudakov~\cite{cfs11}, who showed that, for all positive integers $\chi \geq 3$ and $n$, \[R(K^{(3)}_\chi(n)) \leq 2^{2^{2R}n^2},\]
where $R = R(K_{\chi-1})$.
Since every ordering of $K^{(3)}_\chi(\chi n)$ contains an ordered subhypergraph isomorphic to $\mathcal{K}^{(3)}_\chi(n)$ and every ordered $3$-uniform hypergraph on $n$ vertices with interval chromatic number $\chi$ is an ordered subhypergraph of $\mathcal{K}^{(3)}_\chi(n)$, we obtain the following bound.

\begin{corollary}
\label{cor-3UnifBoundedIntChr}
For all positive integers $\chi \geq 3$ and $n$, every ordered $3$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with interval chromatic number $\chi$ satisfies
\[\overline{R}(\mathcal{H}) \leq 2^{2^{2R}\chi^2n^2},\]
where $R = R(K_{\chi-1})$.
In particular, if the interval chromatic number $\chi$ of $\mathcal{H}$ is fixed, we have
\[
\overline{R}(\mathcal{H}) \leq 2^{O(n^2)}.
\]
\end{corollary}

Note that the last bound is asymptotically tight for dense ordered hypergraphs, as a standard probabilistic argument shows that $\overline{R}(\mathcal{H}) \geq 2^{\Omega(n^2)}$ for every ordered $3$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with $\Omega(n^3)$ hyperedges.
In particular, we get $\overline{R}(\mathcal{K}^{(3)}_3(n)) \geq 2^{\Omega(n^2)}$.

\section{Our results}

Since the bounds on the ordered Ramsey numbers from Corollary~\ref{cor-3UnifBoundedIntChr} are asymptotically tight for dense ordered hypergraphs with bounded interval chromatic number, we consider the sparse case with bounded maximum degree and interval chromatic number.
The situation for ordered hypergraphs seems to be more difficult than for ordered graphs, so we focus on the first nontrivial case, which is for ordered $3$-uniform hypergraphs with interval chromatic number $3$.

Assuming the maximum degree of an ordered hypergraph $\mathcal{H}$ with $\chi_<(\mathcal{H})=3$ is sufficiently small, we obtain a better upper bound on $\overline{R}(\mathcal{H})$ than the estimate $2^{O(n^2)}$ we would get from Corollary~\ref{cor-3UnifBoundedIntChr}.
We can prove an estimate with  a subquadratic exponent even in the more general setting $\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n))$, where, additionally, the interval chromatic number of $\mathcal{H}$ is arbitrary.

\begin{theorem}
\label{thm-3UnifMaxDegIntChr}
Let $\mathcal{H}$ be an ordered 3-uniform hypergraph on $t$ vertices with maximum degree $d$ and let $s$ be a positive integer.
Then there are constants $C=C(d)$ and $c>0$ such that
\[\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(s)) \leq t \cdot 2^{C(s^{2-1/(1+cd^2)})}.\]
In particular, for $s=t=n$ and bounded $d$, we get the estimate
\begin{equation}
\label{eq-diagonal}
\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n)) \leq 2^{O(n^{2-1/(1+cd^2)})}.
\end{equation}
\end{theorem}

The main idea of the proof of Theorem~\ref{thm-3UnifMaxDegIntChr} is based on an embedding lemma from~\cite{cfs12}, where the authors study Erd\H{o}s--Hajnal-type theorems for $3$-uniform tripartite hypergraphs.
We prove a variant of this lemma, which works for ordered hypergraphs, does not consider induced copies, and uses the assumption that the maximum degree of $\mathcal{H}$ is bounded instead of assuming that the number of vertices of $\mathcal{H}$ is fixed.

Since every ordered $3$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with $\chi_<(\mathcal{H})=3$ is an ordered subhypergraph of~$\mathcal{K}^{(3)}_3(n)$, we immediately obtain the following corollary.

\begin{corollary}
\label{cor-3UnifMaxDegIntChr}
Let $\mathcal{H}$ be an ordered 3-uniform hypergraph on $n$ vertices with maximum degree $d$ and with interval chromatic number $3$.
Then there exists an $\varepsilon = \varepsilon(d)>0$ such that
\[
\overline{R}(\mathcal{H}) \leq 2^{O(n^{2-\varepsilon})}.
\]
\end{corollary}

It might seem wasteful to use Theorem~\ref{thm-3UnifMaxDegIntChr} in order to obtain Corollary~\ref{cor-3UnifMaxDegIntChr}, as the ordered hypergraph $\mathcal{H}$ is much sparser than $\mathcal{K}^{(3)}_3(n)$.
However, as noted in~\cite{clfs17}, this intuition is wrong already for ordered graphs, as there are ordered matchings $\mathcal{M}$ on $n$ vertices with $\chi_<(\mathcal{M})=2$ and ordered graphs $\mathcal{G}$ on $N=2^{n^c}$ vertices for some constant $c>0$ such that $\mathcal{G}$ has edge density at least $1-n^{-c}$ and does not contain $\mathcal{M}$ as an ordered subgraph.
In fact, the best known upper bounds on $\overline{R}(\mathcal{G})$ for $n$-vertex ordered graphs $\mathcal{G}$ with bounded maximum degree and $\chi_<(\mathcal{G})=\chi$ are derived from the bound~\eqref{eq-degreeIntChrNumber} on $\overline{R}(\mathcal{G},\mathcal{K}^{(2)}_\chi(n))$.

The upper bound~\eqref{eq-diagonal} is quite close to the truth, as even when $\mathcal{H}$ is fixed we get a superexponential lower bound on $\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n))$. We note that since the first version of this preprint we learned that independently Fox and He (Theorem 1.3 in~\cite{foxhe19}) proved the same lower bound for the unordered Ramsey number and that implies the result of Theorem \ref{thm-3UnifMaxDegLower}. However we leave this result here as our proof is much simpler.

\begin{theorem}
\label{thm-3UnifMaxDegLower}
For every $t \geq 3$ and every positive integer $n$, we have
\[\overline{R}(\mathcal{K}^{(3)}_{t+1},\mathcal{K}^{(3)}_3(n)) \geq 2^{\Omega(n \log{n})}.\]
\end{theorem}

We do not have any nontrivial lower bound in the diagonal case $\overline{R}(\mathcal{H})$ for $\mathcal{H}$ with bounded maximum degree and $\chi_<(\mathcal{H})=3$.
We note that even for ordered graphs $\mathcal{G}$ with bounded maximum degree $d$ and $\chi_<(\mathcal{G})=2$ the best known lower bound on $\overline{R}(\mathcal{G})$ (and also on $\overline{R}(\mathcal{H})$) is only of order $\Omega((n/\log{n})^2)$~\cite{bjv16}, while the upper bound on $\overline{R}(\mathcal{G})$ is of order $n^{O(d)}$~\cite{bckk13,clfs17}.

Concerning $k$-uniform hypergraphs with $k>3$, the following result is based on a modification of the proof from~\cite[Proposition~6.3]{cfs10} and gives an estimate on ordered Ramsey numbers of ordered $k$-uniform hypergraphs with bounded interval chromatic number.
In particular, this estimate shows that we do not have a tower-type growth rate for $\overline{R}(\mathcal{H})$ once the uniformity and the interval chromatic number of $\mathcal{H}$ are bounded.

\begin{proposition}
\label{prop-generalBound}
Let $\chi,k$ be integers with $\chi \geq k \geq 2$ and let $\mathcal{H}$ be an ordered $k$-uniform hypergraph on $n$ vertices with interval chromatic number $\chi$.
Then there is a constant $c$ such that
\[\overline{R}(\mathcal{H}) \leq 2^{R^{\chi(\chi-1)}  (c\chi  n)^{\chi-1}},\]
where $R=R(K^{(k)}_\chi)$.
In particular, if the uniformity $k$ and the interval chromatic number $\chi$ of~$\mathcal{H}$ are fixed, we have
\[
\overline{R}(\mathcal{H}) \leq 2^{O(n^{\chi-1})}.
\]
\end{proposition}

Our understanding of the ordered Ramsey numbers of ordered hypergraphs is still very limited.
Many interesting open problem arose during our study and we would like to draw attention to some of them in Section~\ref{sec-openProblems}.

\section{Proof of Theorem~\ref{thm-3UnifMaxDegIntChr}}

Here we prove Theorem~\ref{thm-3UnifMaxDegIntChr} by giving an upper bound on the ordered Ramsey numbers of ordered 3-uniform hypergraphs with bounded maximum degree versus $\mathcal{K}^{(3)}_3(n)$.
We prove the following slightly stronger result.

\begin{theorem}
\label{thm-3UnifMaxDegIntChrPrecise}
Let $\mathcal{H}$ be an ordered 3-uniform hypergraph on $t$ vertices with maximum degree $d$, let $s$ be a positive integer and $\rho \in (0,1/8)$ be a real number.
Then there is a constant $C'$ such that
\[\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(s)) \leq t \cdot 2^{C'(s^{3/2} \cdot \rho^{-30d^2} \cdot d^6 +s^2\log{(\frac{1}{1-4\rho})})}.\]
\end{theorem}

First, we show that Theorem~\ref{thm-3UnifMaxDegIntChrPrecise} implies Theorem~\ref{thm-3UnifMaxDegIntChr}.

\begin{proof}[Proof of Theorem~\ref{thm-3UnifMaxDegIntChr}]
We can assume that $s > 8^{2+60d^2}$ by choosing the constant $C=C(d)$ from the statement of Theorem~\ref{thm-3UnifMaxDegIntChr} sufficiently large.
We then choose $\rho = s^{-1/(2+60d^2)}$, which gives $\rho < 1/8$ by our assumption on $s$.
Since $1-z \geq e^{-2z}$ for every $z$ with $0\leq z \leq 1/2$, we obtain $(1-4\rho)^{-s^2} \leq e^{8\rho s^2}$ and thus $s^2\log{(\frac{1}{1-4\rho})}) \leq 8s^2\rho$.
By our choice of~$\rho$, we then get
\[s^{3/2}\rho^{-30d^2} = s^2\rho = s^{2-1/(2+60d^2)}.\]
Therefore we can rewrite the upper bound from Theorem~\ref{thm-3UnifMaxDegIntChrPrecise} as \[\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(s)) \leq t \cdot 2^{C'(d^6 + 8)s^2\rho} \leq 2^{Cs^{2-1/(2+60d^2)}}\]
for sufficiently large $C=C(d)$,
which concludes the proof.
\end{proof}

In the rest of the section, we prove Theorem~\ref{thm-3UnifMaxDegIntChrPrecise}, but we first state some definitions.
For a graph $G$ and two disjoint subsets $X$ and $Y$ of vertices of $G$, we use $d(X,Y)$ to denote the \emph{edge density} between $X$ and $Y$, that is, $d(X,Y) = \frac{e(X,Y)}{|X||Y|}$, where $e(X,Y)$ denotes the number of edges with one vertex in $X$ and with the other one in $Y$.

For positive real numbers $\varepsilon_1,\varepsilon_2$, and $\rho$, we say that an ordered bipartite graph $\mathcal{G}$ with consecutive color classes $U$ and $V$ is \emph{bi-$(\varepsilon_1,\varepsilon_2,\rho)$-dense between $U$ and $V$}, if for all sets $X\subseteq U$ and $Y \subseteq V$ with $|X| \geq \varepsilon_1 |U|$ and $|Y| \geq \varepsilon_2 |V|$ we have $d(X,Y) \geq \rho$.

For positive real numbers $\varepsilon$ and $\rho$ and a positive integer $m$, an ordered 3-uniform hypergraph $\mathcal{H}$ is \emph{tri-$(\varepsilon,\rho,m)$-dense}, if for all consecutive subsets $V_1,V_2,V_3$ of vertices of $\mathcal{H}$, each of size at most $m$, and for all bipartite graphs $G_{1,2},G_{1,3},G_{2,3}$, each $G_{i,j}$ between $V_i$ and $V_j$, for which there are at least $\varepsilon m^3$ triangles with one edge in each $G_{i,j}$, at least $\rho$-proportion of these triangles forms hyperedges in $\mathcal{H}$.

The following embedding lemma is based on a similar result from~\cite{cfs12}.

\begin{lemma}\label{lem-embedding}
Let $\mathcal{H}$ be an ordered 3-uniform hypergraph on $t$ vertices with maximum degree $d$.
Let $ \varepsilon >0$ and $\rho \in (0,1)$ be two real numbers with $ \varepsilon \leq 2^{-6} \cdot \rho^{15d^2} \cdot d^{-3}$.
If $\mathcal{G}$ is a tri-$(\varepsilon,\rho,n/t)$-dense ordered 3-uniform hypergraph on $n \geq t/\varepsilon$ vertices, then $\mathcal{H}$ is an ordered subhypergraph of~$\mathcal{G}$.
\end{lemma}
\begin{proof}
Let $v_1 \prec \cdots \prec v_t$ be the vertices of $\mathcal{H}=(H,\prec)$.
For a vertex $v_j$ of $\mathcal{H}$ with $j>i$, we use ${\rm deg}^{{\preceq}i}_\mathcal{H}(j)$ to denote the number $\sum_{e \in E(\mathcal{H}): v_j \in e} |e \cap \{v_1,\dots,v_i\}|$.
Similarly, for vertices $v_j$ and $v_k$ of $\mathcal{H}$ and $i<j,k$, we use ${\rm deg}^{{\preceq}i}_\mathcal{H}(j,k)$ to denote the number of hyperedges of $\mathcal{H}$ containing $v_j$, $v_k$, and a vertex from $\{v_1,\dots,v_i\}$.
Observe that ${\rm deg}^{{\preceq}i}_\mathcal{H}(j) \leq 2d$  and ${\rm deg}^{{\preceq}i}_\mathcal{H}(j,k) \leq d$ for all $j$ and $k$ with $i<j,k$, as the maximum degree of $\mathcal{H}$ is $d$ and each hyperedge is multiplied by at most $2$.

We partition the vertex set of $\mathcal{G}$ into consecutive intervals $U_1,\dots,U_t$, each of size $n/t$.
We embed a copy $f(\mathcal{H})$ of $\mathcal{H}$ in $\mathcal{G}$ one vertex at time, embedding each vertex $f(v_i)$ of $f(\mathcal{H})$ to~$U_i$.
We proceed by induction on $i=0,1,\dots,t-1$.
Assuming that the vertices $v_1,\dots,v_i$ have been embedded as $f(v_1),\dots,f(v_i)$, we show that there are sets $U^i_{i+1},\dots,U^i_t$ and \allowbreak graphs $G^i_{j,k}$ with $i<j<k\leq t$ such that the following three conditions are satisfied:
\begin{enumerate}[label=(\roman*)]
    \item\label{item-embed1} $|U^i_j| \geq C^i_j \cdot n/t$, where $C^i_j = \rho^{d \cdot {\rm deg}^{{\preceq}i}_\mathcal{H}(j)}$,
    \item\label{item-embed2} $G^i_{j,k}$ is a bipartite graph between $U^i_j$ and $U^i_k$, which is bi-$(\varepsilon^i_j,\varepsilon^i_k,\rho^i_{j,k})$-dense between $U^i_j$ and $U^i_k$ with $\varepsilon^i_j = \rho^{4d^2 - d \cdot {\rm deg}^{{\preceq}i}_\mathcal{H}(j)}/(4d)$, $\varepsilon^i_k = \rho^{4d^2 - d \cdot {\rm deg}^{{\preceq}i}_\mathcal{H}(k)}/(4d)$, and $\rho^i_{j,k} = \rho^{{\rm deg}^{{\preceq}i}_\mathcal{H}(j,k)}$, and

    \item\label{item-embed3} for every $h \leq i$, every edge of $G^i_{j,k}$ forms a hyperedge of $\mathcal{G}$ with $f(v_h)$ if $\{v_h,v_j,v_k\}$ is a hyperedge of $\mathcal{H}$. Also, for all $h_1$ and $h_2$ with $h_1 < h_2 \leq i$, every vertex $u \in U^i_j$ with $i<j$ forms a hyperedge $\{ f(v_{h_1}),f(v_{h_2}),u\}$ of $\mathcal{G}$ if $\{v_{h_1},v_{h_2},v_j\}$ is a hyperedge of $\mathcal{H}$.
\end{enumerate}

For the induction base, assume $i=0$ and set $U^0_j = U_j$ for every $j \in \{1,\dots,t\}$.
For all $j$ and $k$ with $1 \leq j<k\leq t$, we let $G^i_{j,k}$ be the complete bipartite graph between $U^0_j$ and $U^0_k$.
Then the three conditions are trivially satisfied.

For the induction step, assume that the vertices $v_1,\dots,v_i$ have been embedded for some $i \geq 0$ while maintaining conditions~\ref{item-embed1}, \ref{item-embed2}, and \ref{item-embed3}.
We show how to embed the vertex $v_{i+1}$.

We let $W_{i+1}$ be the set of vertices $w$ from $U^i_{i+1}$ such that the neighborhood $U^i_j(w)$ of $w$ in $G^i_{i+1,j}$ has size at least $\rho^i_{i+1,j} |U^i_j|$ for every $j \in \{i+2,\dots,t\}$ such that $v_{i+1}$ and $v_j$ are contained in a hyperedge of $\mathcal{H}$.
Since the graph $G^i_{i+1,j}$ is bi-$(\varepsilon^i_{i+1},\varepsilon^i_j,\rho^i_{i+1,j})$-dense, there are at most $\varepsilon^i_{i+1}|U^i_{i+1}| \leq  \varepsilon^i_{i+1} n/t$ vertices in $U_{i+1}$ that have less than $\rho^i_{i+1,j} |U^i_j|$ neighbors in $|U^i_j|$.
Using condition~\ref{item-embed1} and the fact that the maximum degree of $\mathcal{H}$ is $d$, we see that the size of~$W_{i+1}$ satisfies
\begin{align*}
|W_{i+1}| &\geq |U^i_{i+1}| - 2d\varepsilon^i_{i+1}|U^i_{i+1}| \geq |U^i_{i+1}| - 2d\varepsilon^i_{i+1} n/t \geq C^i_{i+1} n/t - 2d\varepsilon^i_{i+1} n/t \geq C^i_{i+1} n/(2t),
\end{align*}
where the last inequality follows from $\varepsilon^i_{i+1} \leq C^i_{i+1}/(4d)$, as ${\rm deg}^{{\preceq}i}_\mathcal{H}(i+1) \leq 2d$.

For a vertex $w \in W_{i+1}$ and indices $j$ and $k$ such that $i+1<j<k$ and $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$, we define the graph $H_{j,k}(w)$ as a subgraph of $G^i_{j,k}$ between $U^i_j(w)$ and $U^i_k(w)$ consisting of edges $\{x,y\}$ such that $\{w,x,y\} \in E(\mathcal{G})$.
We also let $W^{i+1}_{j,k}$ be the set of vertices $w \in W_{i+1}$ such that the graph $H_{j,k}(w)$ is not bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-dense between $U^i_j(w)$ and $U^i_k(w)$.

By the definition of bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-density, for every $w \in W^{i+1}_{j,k}$, there are sets $Y_j(w) \subseteq U^i_j(w)$ and $Y_k(w) \subseteq U^i_k(w)$ such that $|Y_j(w)| \geq \varepsilon^{i+1}_j|U^i_j(w)|$, $|Y_k(w)| \geq \varepsilon^{i+1}_k|U^i_k(w)|$, and $d(Y_j(w),Y_k(w)) < \rho^{i+1}_{j,k}$ in $H_{j,k}(w)$.
Since $w \in W_{i+1}$, we have
\[|Y_j(w)| \geq \varepsilon^{i+1}_j|U^i_j(w)| \geq \varepsilon^{i+1}_j\cdot \rho^i_{i+1,j} |U^i_j| \geq \varepsilon^i_j |U^i_j|,\]
where the last inequality follows from $\varepsilon^{i+1}_j\cdot \rho^i_{i+1,j} \geq \varepsilon^i_j$, as, since $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$, we have ${\rm deg}_{\mathcal{H}}^{{\preceq}i+1}(j) > {\rm deg}_{\mathcal{H}}^{{\preceq}i}(j)$ and ${\rm deg}^{{\preceq}i}_\mathcal{H}(i+1,j) \leq d$.
Analogously, we obtain $|Y_k(w)| \geq \varepsilon^i_k |U^i_k|$.

We let $J_{i+1,j}$ be the graph connecting each $w \in W^{i+1}_{j,k}$ to vertices from $Y_j(w)$ and we analogously define the graph $J_{i+1,k}$.
The graph $G^i_{j,k}$ is bi-$(\varepsilon^i_j,\varepsilon^i_k,\rho^i_{j,k})$-dense between $U^i_j$ and $U^i_k$ by condition~\ref{item-embed2}.
Thus, since $|Y_j(w)| \geq \varepsilon^i_j |U^i_j|$ and $|Y_k(w)| \geq \varepsilon^i_k |U^i_k|$, the number of triangles in the tripartite graph between $W^{i+1}_{j,k}$, $U^i_j$, and $U^i_k$ formed by $J_{i+1,j}$, $J_{i+1,k}$, and $G^i_{j,k}$ is at least $\rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}}|Y_j(w)||Y_k(w)|$.

Suppose for contradiction that $|W^{i+1}_{j,k}| \geq |W_{i+1}|/(2d)$ for some $j$ and $k$ with $i+1<j<k$ and $\{v_{i+1},v_j,v_k\}\in E(\mathcal{H})$.
Then, since $|Y_j(w)| \geq \varepsilon^i_j |U^i_j|$ and $|Y_k(w)| \geq \varepsilon^i_k |U^i_k|$ for every $w \in W^{i+1}_{j,k}$,
\[\rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}}|Y_j(w)||Y_k(w)| \geq \rho^i_{j,k}\varepsilon^i_j\varepsilon^i_k |W^{i+1}_{j,k}||U^i_j||U^i_k| \geq \rho^i_{j,k}\varepsilon^i_j\varepsilon^i_k C^i_jC^i_k |W^{i+1}_{j,k}| (n/t)^2,\]
where the last inequality follows from condition~\ref{item-embed1}.
Using the assumption $|W^{i+1}_{j,k}| \geq |W_{i+1}|/(2d)$ and the fact $|W_{i+1}| \geq C^i_{i+1}n/(2t)$, we can estimate the above expression from below by
\[\rho^i_{j,k}\varepsilon^i_j\varepsilon^i_k C^i_jC^i_k C^i_{i+1} n^3/(4dt^3)\]
Our choice of parameters then gives $\rho^i_{j,k}\varepsilon^i_j\varepsilon^i_k C^i_jC^i_k C^i_{i+1}/(4dt^3) \geq \varepsilon/t^3$.
Altogether, there are at least
\[\rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}}|Y_j(w)||Y_k(w)| \geq \varepsilon (n/t)^3\]
triangles in the tripartite graph between $W^{i+1}_{j,k}$, $U^i_j$, and $U^i_k$ formed by $J_{i+1,j}$, $J_{i+1,k}$, and $G^i_{j,k}$.
Thus, since the ordered hypergraph $\mathcal{G}$ is tri-$(\varepsilon,\rho,n/t)$-dense, at least $\rho$-proportion of these triangles forms hyperedges in $\mathcal{G}$.
Therefore there are at least $\rho \cdot \rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}}|Y_j(w)||Y_k(w)|$ hyperedges of $\mathcal{G}$ between $W^{i+1}_{j,k}$, $U^i_j$, and $U^i_k$.

On the other hand, the number of hyperedges of $\mathcal{G}$ containing a vertex $w \in W^{i+1}_{j,k}$ and having an edge in each of the graphs $J_{i+1,j}$, $J_{i+1,k}$, and $G^i_{j,k}$ is the number of edges of~$H_{j,k}(w)$ between $Y_j(w)$ and $Y_k(w)$.
This number of edges is less than $\rho^{i+1}_{j,k}|Y_j(w)||Y_k(w)|$, as we know that $d(Y_j(w),Y_k(w)) < \rho^{i+1}_{j,k}$ in $H_{j,k}(w)$.
Thus the number of the hyperedges of $\mathcal{G}$ is less than
\[\rho^{i+1}_{j,k}\sum_{w \in W^{i+1}_{j,k}} |Y_j(w)||Y_k(w)| \leq \rho \cdot \rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}} |Y_j(w)||Y_k(w)|,\]
where the least inequality follows from $\rho^{i+1}_{j,k} \leq \rho \cdot \rho^i_{j,k}$, as $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$ and thus we have ${\rm deg}_{\mathcal{H}}^{{\preceq}i+1}(j,k) > {\rm deg}_{\mathcal{H}}^{{\preceq}i}(j,k)$.
This contradicts the fact that there are at least $\rho~\cdot~ \rho^i_{j,k}\sum_{w \in W^{i+1}_{j,k}} |Y_j(w)||Y_k(w)|$ such hyperedges  of $\mathcal{G}$.

Thus $|W^{i+1}_{j,k}| < |W_{i+1}|/(2d)$.
In particular, the number of vertices $w \in W_{i+1}$ that do not lie in any set $W^{i+1}_{j,k}$ such that $i+1 < j <k \leq t$ and $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$ is at least
\[|W_{i+1}| - \sum_{j<k: \{v_{i+1},v_j,v_k\} \in E(\mathcal{H})} |W^{i+1}_{j,k}| > |W_{i+1}| - \frac{d |W_{i+1}|}{2d} = \frac{|W_{i+1}|}{2},\]
as we are summing over at most $d$ pairs $(j,k)$, because the maximum degree of $\mathcal{H}$ is $d$.
Since $|W_{i+1}| \geq C^i_{i+1}n/(2t)$, we have at least $C^i_{i+1}n/(4t)$ such vertices and we let $f(v_{i+1})$ be any of them.
Since $n \geq t/\varepsilon > 4t/C^i_{i+1}$, at least one such vertex indeed exists.
For every $j \in \{i+2,\dots,t\}$ such that $v_{i+1}$ and $v_j$ are contained in a hyperedge of $\mathcal{H}$, we let $U^{i+1}_j=U^i_j(f(v_{i+1}))$.
We keep $U^{i+1}_j=U^i_j$ for all other values $j$.
Let $j$ and $k$ be indices such that $i+1 < j < k \leq t$.
If $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$, we set $G^{i+1}_{j,k}=H_{j,k}(f(v_{i+1}))$.
For all other values of $j$ and $k$, we let $G^{i+1}_{j,k}$ be the subgraph of $G^i_{j,k}$ induced by $U^{i+1}_j$ and $U^{i+1}_k$.
In particular, if none of the vertices $v_j$ and $v_k$ lies in a hyperedge of $\mathcal{H}$ with $v_{i+1}$, we have $G^{i+1}_{j,k} = G^i_{j,k}$.

To finish the induction step, it remains to verify conditions~\ref{item-embed1}, \ref{item-embed2}, and~\ref{item-embed3}.
To verify condition~\ref{item-embed1}, first observe that if, for $j \in \{i+2,\dots,k\}$, the vertex $v_j$ is not in a hyperedge of $\mathcal{G}$ with $v_{i+1}$, then, by the choice of $C^i_j$ and $C^{i+1}_j$, $|U^{i+1}_j| = |U^i_j| \geq C^i_j n/t =C^{i+1}_j n/t$, as ${\rm deg}^{{\preceq}i}_\mathcal{H}(j) = {\rm deg}^{{\preceq}i+1}_\mathcal{H}(j)$.
Otherwise $|U^{i+1}_j| = |U^i_j(f(v_{i+1}))|$.
Since $f(v_{i+1}) \in W_{i+1}$, we have $|U^i_j(f(v_{i+1}))| \geq \rho^i_{i+1,j}|U^i_j|$.
Since ${\rm deg}^{{\preceq}i}_\mathcal{H}(j) < {\rm deg}^{{\preceq}i+1}_\mathcal{H}(j)$ and ${\rm deg}^{{\preceq}i}_\mathcal{H}(i+1,j) \leq d$, we have $\rho^i_{i+1,j}C^i_j \geq C^{i+1}_j$.
So we obtain $|U^{i+1}_j| \geq C^{i+1}_j n/t$.
Thus condition~\ref{item-embed1} is satisfied.

For condition~\ref{item-embed2}, let $j$ and $k$ be indices such that $i+1 < j<k\leq t$.
Consider first the case when $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$.
Then $G^{i+1}_{j,k} = H_{j,k}(f(v_{i+1}))$.
Since $f(v_{i+1})$ does not lie in any set $W^{i+1}_{j,k}$ such that $i+1<j<k$ and $\{v_{i+1},v_j,v_k\} \in E(\mathcal{H})$, the graph $H_{j,k}(f(v_{i+1}))$ is bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-dense between $U^i_j(f(v_{i+1}))$ and $U^i_k(f(v_{i+1}))$.
Thus $G^{i+1}_{j,k} = H_{j,k}(f(v_{i+1}))$ is bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-dense between $U^{i+1}_j=U^i_j(f(v_{i+1}))$ and $U^{i+1}_k=U^i_k(f(v_{i+1}))$, which verifies condition~\ref{item-embed2} in this case.
Now, assume $\{v_{i+1},v_j,v_k\} \notin E(\mathcal{H})$.
If none of the two vertices $v_j$ and $v_k$ is in a hyperedge of $\mathcal{H}$ with $v_{i+1}$, then ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(j) = {\rm deg}^{{\preceq}i}_\mathcal{H}(j)$, ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(k) = {\rm deg}^{{\preceq}i}_\mathcal{H}(k)$, and ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(j,k) = {\rm deg}^{{\preceq}i}_\mathcal{H}(j,k)$.
In particular, $\varepsilon^i_j = \varepsilon^{i+1}_j$, $\varepsilon^i_j = \varepsilon^{i+1}_j$, and $\rho^{i+1}_{j,k} = \rho^i_{j,k}$.
Since $U^{i+1}_j=U^i_j$, $U^{i+1}_k=U^i_k$, and $G^{i+1}_{j,k} = G^i_{j,k}$ is bi-$(\varepsilon^i_j,\varepsilon^i_k,\rho^i_{j,k})$-dense between $U^i_j$ and $U^i_k$, we see that $G^{i+1}_{j,k}$ is bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-dense between $U^{i+1}_j$ and $U^{i+1}_k$, which again verifies condition~\ref{item-embed2}.
It remains to consider the case when exactly one of the vertices $v_j$ and $v_k$ is in a hyperedge of $\mathcal{H}$ with $v_{i+1}$.
By symmetry, we can assume without loss of generality that $v_j$ and $v_{i+1}$ are in a hyperedge of~$\mathcal{H}$.
Then  ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(j) > {\rm deg}^{{\preceq}i}_\mathcal{H}(j)$, ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(k) = {\rm deg}^{{\preceq}i}_\mathcal{H}(k)$, and ${\rm deg}^{{\preceq}i+1}_\mathcal{H}(j,k) = {\rm deg}^{{\preceq}i}_\mathcal{H}(j,k)$.
In particular, $\varepsilon^i_j > \varepsilon^{i+1}_j$, $\varepsilon^i_k = \varepsilon^{i+1}_k$, and $\rho^{i+1}_{j,k} = \rho^i_{j,k}$.
By definition, we have $U^{i+1}_j=U^i_j(f(v_{i+1}))$ and $U^{i+1}_k=U^i_k$.
Let $X$ be a subset of $U^{i+1}_j$ of size at least $\varepsilon^{i+1}_j|U^{i+1}_j|$ and let $Y$ be a subset of $U^{i+1}_k$ of size at least $\varepsilon^{i+1}_k|U^{i+1}_k| = \varepsilon^i_k|U^i_k|$.
We want to show that $d(X,Y) \geq \rho^{i+1}_{j,k}$ in $G^{i+1}_{j,k}$.
The subset $X$ has size at least $\varepsilon^i_j |U^i_j|$, as $|U^{i+1}_j| = |U^i_j(f(v_{i+1}))| \geq \rho^i_{i+1,j}|U^i_j|$ and our choice of $\varepsilon^{i+1}_j$ together with the fact ${\rm deg}^{{\preceq}i}_\mathcal{H}(i+1,j) \leq d$ gives $\varepsilon^{i+1}_j|U^{i+1}_j| \geq \varepsilon^i_j |U^i_j|$.
Thus, since $G^i_{j,k}$ is bi-$(\varepsilon^i_j,\varepsilon^i_k,\rho^i_{j,k})$-dense between $U^i_j \supseteq U^{i+1}_j$ and $U^i_k \supseteq U^{i+1}_k$, the density between $X$ and $Y$ is at least $\rho^i_{j,k}=\rho^{i+1}_{j,k}$ in $G^i_{j,k}$.
Since $G^{i+1}_{j,k}$ is an induced subgraph of $G^i_{j,k}$, the density between $X$ and $Y$ is also at least $\rho^i_{j,k}=\rho^{i+1}_{j,k}$ in $G^{i+1}_{j,k}$.
Thus $G^{i+1}_{j,k}$ is bi-$(\varepsilon^{i+1}_j,\varepsilon^{i+1}_k,\rho^{i+1}_{j,k})$-dense between $U^{i+1}_j$ and $U^{i+1}_k$, which verifies condition~\ref{item-embed2}.

We show that Condition~\ref{item-embed3} is satisfied as well.
Let $j$ and $k$ be indices such that $i+2<j<k\leq t$.
If $\{v_h,v_j,v_k\}$ is a hyperedge of $\mathcal{H}$ for some $h \leq i+1$, then $\{f(v_h),x,y\}$ is a hyperedge of $\mathcal{G}$ for every edge $\{x,y\}$ of $G^{i+1}_{j,k}$.
This is true for $h \leq i$ by the induction assumption, as $G^{i+1}_{j,k} \subseteq G^i_{j,k}$.
For $h=i+1$ we have $G^{i+1}_{j,k} = H_{j,k}(f(v_{i+1}))$ and the claim holds by the definition of $H_{j,k}(f(v_{i+1}))$.
Similarly, for all $h_1$ and $h_2$ with $h_1 < h_2 \leq i+1$, every vertex $u \in U^{i+1}_j$ with $i+1<j$ forms a hyperedge $\{f(v_{h_1}),f(v_{h_2}),u\}$ of $\mathcal{G}$ if $\{v_{h_1},v_{h_2},v_j\}$ is a hyperedge of $\mathcal{H}$.
This is because if $h_2\leq i$, then the claim follows from the induction assumption and the fact $U^{i+1}_j \subseteq U^i_j$.
For $h_2=i+1$, the triple $\{f(v_{h_1}),f(v_{h_2}),x\}$ is a hyperedge of $\mathcal{G}$ for every $x \in U^{i+1}_j = U^i_j(f(v_{h_2}))$ by the inductive assumption.

Finally, after we find all vertices $f(v_1),\dots,f(v_t)$, condition~\ref{item-embed3} ensures that they determine a copy of $\mathcal{H}$ as an ordered subhypergraph of $\mathcal{G}$.
\end{proof}

We use the following result proved by Conlon, Fox, and Sudakov~\cite{cfs12}.
It says that if a graph $G$ contains many triangles, a 3-uniform hypergraph whose hyperedges form a dense subset of the set of triangles in $G$ contains a large copy of $K^{(3)}_3(n)$.

\begin{lemma}[\cite{cfs12}]
\label{lem-tripartite}
Let $V_1,V_2,V_3$ be pairwise disjoint sets of vertices, each of size at most $m$, and let $G_{i,j}$ be a bipartite graph between $V_i$ and $V_j$ for all $i$ and $j$ with $1 \leq i < j \leq 3$.
Assume there are at least $\delta m^3$ triangles in the tripartite graph formed by $G_{1,2}$, $G_{1,3}$, and $G_{2,3}$.
Let $G$ be a $3$-uniform hypergraph containing at least $(1-\eta)$-proportion of the triangles in the tripartite graph, where $0<\eta < 1/8$.
Then $G$ contains a copy of $K^{(3)}_3(s)$ provided that
\[e^{2^{10}\delta^{-2}s^{3/2}}(1-4\eta)^{-4s^2}\left(\frac{\delta}{16}\right)^{4s} \leq m.\]
\end{lemma}

We note that, although it is not explicitly stated in the above lemma, the copy of $K^{(3)}_3(s)$ has $V_i$ as the $i$th color class.
Thus if the set $V_1 \cup V_2 \cup V_3$ is ordered and $V_1,V_2,V_3$ are consecutive in this ordering, we actually get a copy of the ordered hypergraph $\mathcal{K}^{(3)}_3(s)$.

We now proceed with the proof of Theorem~\ref{thm-3UnifMaxDegIntChrPrecise}, which implies Theorem~\ref{thm-3UnifMaxDegIntChr}.

\begin{proof}[Proof of Theorem~\ref{thm-3UnifMaxDegIntChrPrecise}]
Let $\mathcal{H}$ be an ordered 3-uniform hypergraph on $t$ vertices with maximum degree $d$, let $s$ be a positive integer and $\rho \in (0,1/8)$ be a real number.
We choose $\varepsilon = 2^{-6} \cdot \rho^{15d^2} \cdot d^{-3}$ and we let $N$ be an integer such that
\[N \geq t \cdot 2^{2^{28}\cdot s^{3/2} \cdot \rho^{-30d^2} \cdot d^6 +12s^2\log{(\frac{1}{1-4\rho})}}.\]
Note that $N \geq t/\varepsilon$.
Consider a red-blue coloring $\chi$ of the hyperedges of~$\mathcal{K}^{(3)}_N$.
We use $\mathcal{G}$ to denote the ordered $3$-uniform hypergraph on $N$ vertices formed by the hyperedges of~$\mathcal{K}^{(3)}_N$ that are blue in~$\chi$.
Similarly, we let $\overline{\mathcal{G}}$ be the hypergraph determined by red hyperedges of~$\mathcal{K}^{(3)}_N$ in~$\chi$.

If $\mathcal{G}$ is tri-$(\varepsilon,\rho,N/t)$-dense, then, since $N \geq t/\varepsilon$, Lemma~\ref{lem-embedding} implies that there is a blue copy of~$\mathcal{H}$ in $\chi$ and we are done.
Thus we assume that $\mathcal{G}$ is not tri-$(\varepsilon,\rho,N/t)$-dense.
That is, there are three consecutive subsets $V_1,V_2,V_3$ of vertices of $\mathcal{G}$, each of size at most $N/t$, and three bipartite graphs $G_{1,2},G_{1,3},G_{2,3}$, each $G_{i,j}$ between $V_i$ and $V_j$, for which there are at least $\varepsilon (N/t)^3$ triangles with one edge in each $G_{i,j}$ and less than $\rho$-proportion of these triangles forms hyperedges in $\mathcal{G}$.
By the choice of $\mathcal{G}$, at least $(1-\rho)$-proportion of these triangles forms hyperedges in $\overline{\mathcal{G}}$.

We show that \begin{equation}
\label{eq-tripartite}
e^{2^{10}\varepsilon^{-2}s^{3/2}}\cdot (1-4\rho)^{-4s^2}\cdot \left(\frac{16}{\varepsilon}\right)^{4s} \leq N/t.
\end{equation}
Then, by Lemma~\ref{lem-tripartite} applied with $\delta = \varepsilon$, $\eta = \rho$, and $m=N/t$, the ordered hypergraph $\overline{\mathcal{G}}$ contains a copy of $K^{(3)}_3(s)$ as an ordered subhypergraph.
By the definition of $\overline{\mathcal{G}}$, all hyperedges of such copy are red in $\chi$, which then finishes the proof.

To estimate~\eqref{eq-tripartite},
we estimate each of the three terms in the above expression separately by $N^{1/3}$.
The exponent in the first term in~\eqref{eq-tripartite} is
\[\log{(e)}2^{10}\varepsilon^{-2}s^{3/2} \leq 2^{23}\cdot \rho^{-30d^2}\cdot d^6 \cdot s^{3/2} \leq \frac{\log{(N/t)}}{3}.\]
The second term can be estimated by
\[(1-4\rho)^{-4 s^2} = 2^{-4s^2\log{(1-4\rho)}} \leq (N/t)^{1/3}.\]
Finally, the the third term satisfies
\[\left(\frac{16}{\varepsilon}\right)^{4s} = \left(2^{10}\cdot \rho^{-15d^2} \cdot d^3 \right)^{4s} < 2^{26\cdot s \cdot \rho^{-15d^2} \cdot d^3} \leq (N/t)^{1/3},\]
as $(2^{10}x)^4 < 2^{26x}$ for $x \geq 2$.
Altogether, both inequalities in~\eqref{eq-tripartite} are satisfied.
\end{proof}

\section{Proof of Theorem~\ref{thm-3UnifMaxDegLower}}

Here we prove a superexponential lower bound on $\overline{R}(\mathcal{K}^{(3)}_t,\mathcal{K}^{(3)}_3(n))$ for any $t \geq 4$.
First, we prove the following result, which gives superexponential lower bounds on ordered Ramsey numbers of 3-uniform hypergraphs $\mathcal{K}^{(3)}_{t+1}$ and $\mathcal{K}^{(3)}_3(n)$ provided that we have a superlinear lower bound on the ordered Ramsey number $\overline{R}(\mathcal{K}_t,\mathcal{K}_{m,m})$ in $m$.
The proof is inspired by the approach from~\cite{cfs10}.

\begin{lemma}
\label{lem-3UnifMaxDegLowerPrecise}
For $t \in \mathbb{N}$, if for $m = \lceil n/4\rceil$ we have $2n < \overline{R}(\mathcal{K}^{(3)}_t,\mathcal{K}_{m,m})^\alpha$ for some $\alpha \in (0,1]$,
then, for each sufficiently large $n$,
\[\overline{R}(\mathcal{K}^{(3)}_{t+1},\mathcal{K}^{(3)}_3(n)) \geq \left(\frac{(\overline{R}(\mathcal{K}_t,\mathcal{K}_{m,m})-1)^{1-\alpha}}{e^4}\right)^{(n+2)/6}.\]
\end{lemma}
\begin{proof}
We set $m = \lceil n/4 \rceil$ and $\ell = \lceil n/2 \rceil$.
Let $R$ denote the number $\overline{R}(\mathcal{K}_t,\mathcal{K}_{m,m})-1$ and let $N = (R^{1-\alpha}/e^4)^{(n+2)/6}$.
Using a probabilistic argument, we find a red-blue coloring $\chi$ of the hyperedges of~$\mathcal{K}^{(3)}_N=(K^{(3)}_N,<)$ that does not contain a blue copy of $\mathcal{K}^{(3)}_{t+1}$ and with positive probability does not contain a red copy of~$\mathcal{K}^{(3)}_3(n)$.

We use the following two auxiliary colorings.
Let $\chi_1$ be a red-blue coloring of the edges of~$\mathcal{K}_R$ that does not contain a blue copy of $\mathcal{K}_t$ nor a red copy of $\mathcal{K}_{m,m}$.
Such a coloring exists by the choice of $R$.
Let $\chi_2$ be a coloring of the edges of $\mathcal{K}_N$ with colors $1,\dots,R$, where the color of each edge is chosen uniformly independently at random from~$[R]$.
For three vertices $u < v < w$ of $\mathcal{K}^{(3)}_N$, we then set $\chi(u,v,w) = \chi_1(\chi_2(u,v),\chi_2(u,w))$ if $\chi_2(u,v)\neq \chi_2(u,w)$ and we let $\chi(u,v,w)$ be red otherwise.

Suppose for contradiction that $\chi$ contains a blue copy of $\mathcal{K}^{(3)}_{t+1}$ on some vertices $v_0, \dots, v_t$ of~$\mathcal{K}^{(3)}_N$.
Since all hyperedges of the copy of $\mathcal{K}^{(3)}_{t+1}$ are blue, our choice of $\chi$ gives distinct colors $\chi_2(v_0,v_1),\dots,\chi_2(v_0,v_t)$ and each edge $\{\chi_2(v_0,v_i),\chi_2(v_0,v_j)\}$ such that $\{v_0,v_i,v_j\}$ is a hyperedge of the blue copy of $\mathcal{K}^{(3)}_{t+1}$ is blue in $\chi_1$.
These blue edges determine a blue copy of~$\mathcal{K}_t$ in~$\chi_1$, which contradicts our choice of~$\chi_1$.

We now show that with positive probability there is no red copy of $\mathcal{K}^{(3)}_3(n)$ in $\chi$ by estimating the expected number of such copies.
Consider $3n$ vertices $v_1 < \cdots < v_{3n}$ of~$\mathcal{K}^{(3)}_N$ and suppose that these vertices induce a red copy of $\mathcal{K}^{(3)}_3(n)$ in $\chi$.
We fix $i \in [n]$.
Then there cannot be $2\ell$ distinct colors with $\ell$ of them among the colors $\chi_2(v_i,v_j)$ for $n<j \leq 2n$ and with the remaining $\ell$ of them among $\chi_2(v_i,v_k)$ for $2n < k \leq 3n$.
Otherwise such colors form a red copy of some ordering of $K_{\ell,\ell}$ in $\chi_1$ and every such ordering contains a copy of $\mathcal{K}_{m,m}$, as $\ell \geq 2m-1$.
Thus either all the colors $\chi_2(v_i,v_j)$ with $n < j \leq 2n$ are contained in the union of the set $\{\chi_2(v_i,v_k) \colon 2n<k \leq 3n\}$ together with a set of at most $\ell-1$ additional colors or, similarly, all the colors $\chi_2(v_i,v_k)$ with $2n < k \leq 3n$ are contained in the union of the set $\{\chi_2(v_i,v_j) \colon n<j \leq 2n\}$ together with a set of at most $\ell-1$ additional colors.

In the first case, all colors $\chi_2(v_i,v_j)$ with $n<j \leq 2n$ are contained in the union of the set $\{\chi_2(v_i,v_k) \colon 2n<k \leq 3n\}$ together with a set of at most $\ell-1$ additional colors.
In particular, the colors $\chi_2(v_i,v_j)$ with $n<j \leq 2n$ and $\chi_2(v_i,v_k)$ with $2n<k \leq 3n$ are all contained in a set of $n+\ell-1$ colors from $[R]$, as $|\{\chi_2(v_i,v_k) \colon 2n<k \leq 3n\}| \leq n$.
There are $\binom{R}{n+\ell-1}$ sets for the possible colors.
The probability that each of the colors $\chi_2(v_i,v_j)$ with $n<j \leq 2n$ and $\chi_2(v_i,v_k)$ with $2n<k \leq 3n$ is contained in a fixed set of $n+\ell-1$ colors from $[R]$ is $\left(\frac{n+\ell-1}{R}\right)^{2n}$.
The other case is symmetric.
Considering this for every $i \in [n]$, we see that the expected number of red copies of $\mathcal{K}^{(3)}_3(n)$ in~$\chi$ is at most
\begin{align*}
    &\binom{N}{3n}\left(2\binom{R}{n+\ell-1}^n\left(\frac{n+\ell-1}{R}\right)^{2n^2}\right) \\
    &\leq N^{3n}\left(2\left(\frac{eR}{n+\ell-1}\right)^{n(n+\ell-1)}\left(\frac{n+\ell-1}{R}\right)^{2n^2}\right)\\
    &\leq \left(N^3\left(2 e^{n+\ell-1}\left(\frac{n+\ell-1}{R}\right)^{n-\ell+1}\right) \right)^n \\
    &< \left(N^3e^{2n}\left(R^{\alpha-1}\right)^{n-\ell+1}\right)^n\\
    &\leq \left(N^3\left(e^4R^{\alpha-1}\right)^{n/2+1}\right)^n = 1,
\end{align*}
where we used $n+\ell-1\leq 2n \leq R^\alpha$ and our choice of $\ell$ and $N$.
Since the expected number of red copies of $\mathcal{K}^{(3)}_3(n)$ is less than $1$, there is a red-blue coloring $\chi$ that does not contain a blue copy of~$\mathcal{K}^{(3)}_{t+1}$ nor a red copy of~$\mathcal{K}^{(3)}_3(n)$.
\end{proof}

We also use the following bounds on Ramsey numbers of complete graphs and complete bipartite graphs proved by Li and Zang~\cite{liZan03}.

\begin{theorem}[\cite{liZan03}]
\label{thm-ramCliqueBipartite}
For every fixed integer $t \geq 3$ and every integer $m \ge 2$, there is a constant $c>0$ such that
\[R(K_t,K_{m,m}) \geq c\left(\frac{m}{\log{m}}\right)^{(t+1)/2}.\]
\end{theorem}

To finish the proof, we now combine all the auxiliary results.

\begin{proof}[Proof of Theorem~\ref{thm-3UnifMaxDegLower}]
It suffices to consider $\mathcal{K}^{(3)}_4$, as ordered Ramsey numbers do not decrease by adding vertices.
Let $n$ be a sufficiently large integer and let $m = \lceil n/4 \rceil$.
By Theorem~\ref{thm-ramCliqueBipartite}, we have $\overline{R}(\mathcal{K}_3,\mathcal{K}_{m,m}) \geq \Omega\left(\left(\frac{m}{\log{m}}\right)^2\right)$.
In particular, $2n < \overline{R}(\mathcal{K}_3,\mathcal{K}_{m,m})^\alpha$ for some fixed $\alpha < 1$ and a sufficiently large $n$.
Lemma~\ref{lem-3UnifMaxDegLowerPrecise} thus implies that
\[\overline{R}(\mathcal{K}^{(3)}_4,\mathcal{K}^{(3)}_3(n)) \geq \left(\frac{m}{\log{m}}\right)^{\Omega(n)} \geq 2^{\Omega(n\log{n})},\]
which finishes the proof.
\end{proof}

\section{Proof of Proposition~\ref{prop-generalBound}}

For integers $\chi$ and $k$ with $\chi \geq k \geq 2$ and an ordered $k$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with interval chromatic number $\chi$, we show that there is a constant $c$ such that
\[\overline{R}(\mathcal{H}) \leq 2^{R^{\chi(\chi-1)}  (c\chi  n)^{\chi-1}},\]
where $R=R(K^{(k)}_\chi)$.

Let $N=2^{ R^{\chi(\chi-1)}  (4\chi  n)^{\chi-1}}$ and consider a red-blue coloring of the hyperedges of $\mathcal{K}^{(k)}_N$ on $[N]$.
Since the interval chromatic number of $\mathcal{H}$ is $\chi$, we have $\mathcal{H} \subseteq \mathcal{K}^{(k)}_\chi(n)$ and thus it suffices to show that there is a monochromatic copy of $\mathcal{K}^{(k)}_\chi(n)$ in our coloring.

Since $R=R(K^{(k)}_\chi)$, every ordered subhypergraph of $\mathcal{K}^{(k)}_N$ induced by an $R$-tuple of vertices contains a monochromatic copy of $\mathcal{K}^{(k)}_\chi$ in our coloring.
Each such copy is contained in $\binom{N-\chi}{R-\chi}$ $R$-tuples of vertices of $\mathcal{K}^{(k)}_N$ and thus there are at least
\[\frac{\binom{N}{R}}{\binom{N-\chi}{R-\chi}} = \binom{R}{\chi}^{-1}\binom{N}{\chi}\]
monochromatic copies of $\mathcal{K}^{(k)}_\chi$.
Without loss of generality, we can assume that at least half of these copies has all hyperedges red.

Let $\mathcal{G}$ be the ordered $\chi$-uniform hypergraph with the vertex set $[N]$, where a $\chi$-tuple of vertices forms a hyperedge if and only if it induces a red copy of $\mathcal{K}^{(k)}_\chi$ in our coloring.
We know that $\mathcal{G}$ has at least $\frac{1}{2}\binom{R}{\chi}^{-1}\binom{N}{\chi} \geq \varepsilon \frac{N^\chi}{\chi!}$ hyperedges, where $\varepsilon = \frac{1}{4}\binom{R}{\chi}^{-1}$.
It is well-known (see~\cite{erdos64,niki09}, for example) that every $\chi$-uniform hypergraph on $N$ vertices with at least $\varepsilon \frac{N^\chi}{\chi!}$ hyperedges, where $(\ln{N})^{-1/(\chi-1)} \leq \varepsilon \leq \chi^{-3}$, contains a copy of $K^{(\chi)}_\chi(\lfloor \varepsilon(\ln{N})^{1/(\chi-1)} \rfloor)$.
Since \[\lfloor\varepsilon(\ln{N})^{1/(\chi-1)} \rfloor = \left\lfloor\frac{4R^\chi \chi n}{4\binom{R}{\chi}}\right\rfloor \geq \chi n,\]
we have a copy of $K^{(\chi)}_\chi(\chi n)$ in $\mathcal{G}$ in some ordering.
Note that every ordering of $K^{(\chi)}_\chi(\chi n)$ contains a copy of $\mathcal{K}^{(\chi)}_\chi(n)$ and thus $\mathcal{G}$ also contains a copy of $\mathcal{K}^{(\chi)}_\chi(n)$.
By the definition of $\mathcal{G}$, the vertices of this copy induce a red copy of $\mathcal{K}^{(k)}_\chi(n)$ in the coloring of~$\mathcal{K}^{(k)}_N$, which finishes the proof.
\qed

\section{Open problems}
\label{sec-openProblems}

There is a plenty of open questions about ordered Ramsey numbers for ordered hypergraphs, as this area is still vastly unexplored.
Here we offer some of the open problems that we considered during our study.

We proved estimates on the ordered Ramsey numbers of ordered $3$-uniform hypergraphs with bounded maximum degree and with interval chromatic number $3$.
However, our bounds are not tight.
Recall that it follows from Theorem~\ref{thm-3UnifMaxDegIntChr} and Theorem~\ref{thm-3UnifMaxDegLower} that there are positive constants $c_1$, $c_2$, and $\varepsilon$, all depending on $d$, such that every ordered $3$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with maximum degree $d$ satisfies
\[\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n)) \leq 2^{c_1n^{2-\varepsilon}},\]
while there is a fixed $\mathcal{G}$ such that
\[\overline{R}(\mathcal{G},\mathcal{K}^{(3)}_3(n)) \geq 2^{c_2n\log{n}}.\]
Thus although the exponents in the bounds are reasonably close in this non-diagonal case, there is still a gap between them and it would be interesting to close it.

\begin{problem}
Let $d$ be a fixed positive integer and let $\mathcal{H}$ be an ordered $3$-uniform hypergraph on $n$ vertices with maximum degree $d$.
Close the gap between the lower and upper bounds on $\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n))$.
\end{problem}

Another interesting problem is to extend the upper bound from Corollary~\ref{cor-3UnifMaxDegIntChr} to ordered $3$-uniform hypergraphs with bounded maximum degree and fixed interval chromatic number that is larger than $3$.
We recall that their ordered Ramsey numbers are bounded from above by $2^{O(n^2)}$ by Corollary~\ref{cor-3UnifBoundedIntChr}.
In particular, one can ask if the exponent is still subquadratic in the number of vertices.

\begin{problem}
Let $d$ and $\chi$ be fixed positive integers.
Is there an $\varepsilon = \varepsilon(d,\chi)>0$ such that, for every ordered $3$-uniform hypergraph $\mathcal{H}$ on $n$ vertices with maximum degree $d$ and with interval chromatic number $\chi$, we have
\[\overline{R}(\mathcal{H}) \leq 2^{O(n^{2-\varepsilon})}?\]
\end{problem}

As we discussed in Subsection~\ref{subsec-previousResults}, the monotone hyperpaths are examples of ordered $3$-uniform hypergraphs with maximum degree $3$ and with an arbitrarily large interval chromatic number such that their ordered Ramsey numbers grow exponentially.
To our knowledge, this is the best lower bound on ordered Ramsey numbers of ordered $3$-uniform hypergraphs with bounded maximum degrees.
Can we obtain better lower bounds?

\begin{problem}
For a fixed $d$, is there an example of a family $\{\mathcal{H}_n\}$ of ordered $3$-uniform hypergraphs $\mathcal{H}_n$ on $n$ vertices with maximum degree $d$ such that the numbers $\overline{R}(\mathcal{H}_n)$ grow superexponentially in $n$?
\end{problem}

We note that even for $\mathcal{K}_n^{(3)}$ the best known lower bound on $\overline{R}(\mathcal{K}_n^{(3)})$ is of order $2^{\Omega(n^2)}$; see~\eqref{eq-hypergraphRamsey}.

The growth rate of Ramsey numbers of unordered $3$-uniform hypergraphs with bounded maximum degree is only linear in the number of vertices; see~\cite{cfs09}.
The situation is completely different for ordered $3$-uniform hypergraphs with bounded maximum degree, as we can, for example, see from the bounds for monotone hyperpaths.
In general, we are not aware of any nontrivial upper bounds on these ordered Ramsey numbers.

\begin{problem}
What is the upper bound on ordered Ramsey numbers of ordered $3$-uniform hypergraphs with bounded maximum degree?
\end{problem}

Finally, we proved all our upper bounds under the assumption that the maximum degree is bounded.
However, the corresponding bounds for ordered graphs such as~\eqref{eq-degreeIntChrNumber} hold for bounded degeneracy, which is a less restrictive assumption.
Thus one can also try to strengthen our results, in particular Theorem~\ref{thm-3UnifMaxDegIntChr} and Corollary~\ref{cor-3UnifMaxDegIntChr}, to ordered hypergraphs with bounded degeneracy instead of the maximum degree.


\section{Introduction}

In the {\sc Submodular Facility Location} problem (SFL), we are given a set $C$ of $n$ clients and set $F$ of $m$ facilities, with metric distances $d: (C\cup F)\times (C\cup F)\to \mathbb{R}_{\geq 0}$. Furthermore, we are given\footnote{As usual in this framework, we assume to have an oracle access to $g(\cdot)$: given $R\subseteq C$, we can obtain the value of $g(R)$ in polynomial time.} a monotone submodular (opening cost) function $g:2^{C}\to \mathbb{R}_{\geq 0}$ with $g(\emptyset)=0$. Notice that $g(\cdot)$ is non-negative. A feasible solution consists of an assignment $\varphi:C\to F$ of each client to some facility (we also say that $\varphi(c)$ \emph{serves} $c$). The opening cost of $f\in F$ in this solution is $g(\varphi^{-1}(f))$. The cost of the solution, that we wish to minimize, is the sum of the distances from each client to the corresponding facility plus the total opening cost of the facilities, in other words
$$
\cost(\varphi)=\sum_{c\in C}d(c,\varphi(c))+\sum_{f\in F}g(\varphi^{-1}(f)).
$$
SFL captures practical scenarios where the cost of opening a facility is a (non-linear, still ``tractable'') function of the set of served clients. As we will discuss, SFL is also closely related to certain stochastic optimization problems which recently attracted a lot of attention (see, e.g, \cite{AGLW17,GGLMSS13,GGLS08,GPRS11,IKMM04} and references therein). In particular, there are scenarios where one has to pay (a posteriori) the connection and opening costs related only to a random subset of \emph{activated} clients, and this naturally induces objective functions with submodular opening costs.

SFL is APX-hard since it includes the classical {\sc Facility Location} problem (with uniform facility costs) as a special case \cite{guha1999greedy}. Hence the best we can hope for, in terms of approximation algorithms, is a constant approximation. Finding such an approximation algorithm is explicitly posed as an open problem, e.g., by Svitkina and Tardos \cite{ST10}. The same authors present an $O(\log n)$ approximation for a generalization of SFL where each facility $f$ has a distinct submodular function $g_f(\cdot)$ (and this result is tight for this generalization due to a reduction from {\sc Set Cover} by Shmoys, Swamy and Levi \cite{SSL04}). Svitkina and Tardos also present a constant approximation for a rather restrictive (still practically motivated) special case of SFL where $g(\cdot)$ is induced by certain subtrees of a node-weighted tree over the clients.

\subsection{Our Results and Techniques}

We make some progress towards the resolution of the mentioned open problem by presenting an improved approximation algorithm for SFL.
\begin{theorem}\label{thr:main}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for SFL.
\end{theorem}
Our approach is surprisingly simple (modulo exploiting some non-trivial results in the literature). By standard reductions (see Section \ref{sec:preliminaries}) we can assume that $N=n+m$ is polynomial in $n$, hence it is sufficient to provide an $O(\log\log N)$ approximation. Our starting point is a natural (configuration) LP relaxation for the problem:
\begin{align}\label{eq:configuration-lp}\tag{Conf-LP}
        \min &\sum_{f \in F} \sum_{R \subseteq C} g(R) \cdot x_R^f
        + \sum_{c\in C} \sum_{f\in F} \sum_{R\ni c} d(c,f) \cdot x_R^f & \\
        %
        \text{s.t.} &
        \sum_{f\in F}\sum_{R\ni c} x_R^f= 1 &\forall c \in C;\nonumber \\
        & \sum_{R \subseteq C} x_R^f= 1 & \forall f \in F;\nonumber
        \\
        & x_R^f \geq 0 & \forall R\subseteq C,\ \forall f\in F.\nonumber
\end{align}
In an integral solution, we interpret $x^f_R=1$ as assigning exactly the set of clients $R$ to the facility $f$. Notice that we impose $\sum_{R \subseteq C} x_R^f = 1$. This is w.l.o.g. since $g(\emptyset)=0$ (intuitively, $x^f_\emptyset=1$ means that no client is assigned to $f$).
We can solve the above LP in polynomial time (see Section \ref{sec:omitted}).
\begin{lemma}\label{lem:solveConfLP}
  In $\poly(N)$ time one can find an optimal solution to \eqref{eq:configuration-lp} with $\poly(N)$ non-zero entries.
\end{lemma}

Given an optimal solution $\dot{x}=(\dot{x}^f_R)_{f\in F,R\subseteq C}$ to \eqref{eq:configuration-lp} of cost $\cost(\dot{x})$ as in Lemma \ref{lem:solveConfLP}, we proceed with two main stages. In the first stage (discussed in Section \ref{sec:reducingConnection}) we simply sample partial assignments of clients to facilities with the distribution induced by $\dot{x}$ for $\ln\ln N$ many times. This cost at most $\ln\ln N$ times the optimal LP cost in expectation, and leads to a partial solution that covers a random subset $C_1\subseteq C$ of clients.

In the second stage (discussed in Section \ref{sec:treeCase}) we take care of the remaining uncovered clients $C_2=C\setminus C_1$. Let us consider the restriction $\ddot{x}$ of $\dot{x}$ to $C_2$. The opening cost of $\ddot{x}$ might be as large as the opening cost of $\dot{x}$. However, in expectation, the connection cost of $\ddot{x}$ is only a $1/\ln N$ fraction of the connection cost of $\dot{x}$ (as we will show).

At this point, using the probabilistic tree embedding algorithm in \cite{FakcharoenpholRT04}, we embed the original metric $d$ into a (rooted) tree metric $d^T$ over a hierarchically well-separated tree (HST) $T$ (see Section \ref{sec:preliminaries} for the details). The opening cost of $\ddot{x}$ w.r.t.\ to the new tree instance does not change, while its connection cost grows by a factor at most $O(\log N)$ in expectation. Altogether we obtain a feasible fractional solution $\ddot{x}$ over the tree instance whose expected cost is at most $O(\cost(\dot{x}))$. Hence it is sufficient to develop an $O(\log\log N)$-approximate LP-rounding algorithm for the considered tree instance.

The next step is at the heart of our approach. Using the properties of HSTs and losing a constant factor in the approximation, we can further reduce our SFL tree instance to the following {\sc Descendant-Leaf Assignment} problem (DLA): the facilities are leaves of $T$ and the clients are arbitrary nodes of $T$. Each client $c$ must be served by a facility contained in the subtree $T_c$ rooted at $c$. The opening cost of each facility is given by $g(\cdot)$, and there are no connection costs at all. The latter problem is very similar to a problem recently studied by Bosman and Olver \cite{BO20} in the framework of {\sc Submodular Joint Replenishment} and {\sc Inventory Routing} problems. In particular, we can adapt their approach to achieve the desired $O(\log\log N)$ approximation for our DLA instance.

We remark that we do not know how to get an $O(1)$ approximation for SFL on trees (even on HSTs). Though such approximation would not imply an $O(1)$ approximation for SFL with our approach (due to the first stage), finding it seems to be a natural intermediate problem to address.

\subsection{Generalizations and Variants}

Our basic approach is rather flexible, and it can be applied to generalizations and variants of SFL. We next describe some other applications of our approach, and we expect to see a few more ones in the future. For example, we can handle the case where the opening cost of the facility $f$ is $g_f(S^f)=w_f\cdot g(S^f)$, where $w_f\geq 0$ is some input value: we call this the SFL {\sc with Multiplicative Opening Costs} problem ({\sc multSFL}).

\begin{theorem}\label{thr:mainMultiplicative}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for {\sc multSFL}.
\end{theorem}

Similarly, we can address the SFL {\sc with Additive Opening Costs} problem ({\sc addSFL}), where $g_f(S^f)=p_f+g(S^f)$ for $S^f\neq \emptyset$, $g_f(\emptyset)=0$, and $p_f\geq 0$ is some input value.
\begin{theorem}\label{thr:mainAdditive}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for {\sc addSFL}.
\end{theorem}
The above generalizations are discussed in \cref{sec:extensions}.
We remark that we do not know how to obtain an $O(\log\log n)$-approximation for the {\sc Affine} SFL case, where the opening costs are submodular functions of the form $g_f(S^f)=p_f+w_f\cdot g(S^f)$. Notice that this generalizes both {\sc addSFL} and {\sc multSFL}. This is left as an interesting and practically relevant open problem.

As mentioned earlier, SFL is closely related to stochastic variants of {\sc Facility Location}. In particular, our approach also extends to the following {\sc Universal Stochastic Facility Location} problem ({\sc univFL}). Here we are given clients $C$ and facilities $F$ with metric distances $d$ like in SFL, plus an opening cost $w_f$ for each $f\in F$. Furthermore, we have an oracle access to a probability distribution $\pi: 2^C\to \mathbb{R}_{\geq 0}$ specifying the probability $\pi(A)$ that a given subset of clients $A\subseteq C$ is activated. A feasible solution is an (universal) mapping $\varphi:C\to F$. The cost of $\varphi$ w.r.t.\ clients $A\subseteq C$ is $\cost_A(\varphi)=\sum_{c\in A}d(c,\varphi(c))+\sum_{f\in F:\varphi^{-1}(f)\cap A\neq \emptyset}w_f$. In words, this is the cost of connecting clients in $A$ to the corresponding facilities, plus the cost of opening the facilities that serve at least one client in $A$.
Our goal is to minimize $\mathbb{E}_{A\sim \pi}[\cost_A(\varphi)]$. The main motivation for \emph{universal} problems of this type is to allow a very quick (possibly distributed) reaction to requests that arrive over time. Let $\opt \colon C\to F$ minimize $\expected_{A\sim \pi}[\cost_A(\opt)]$, in other words $\opt$ is an optimal (universal) mapping. We say that an algorithm for {\sc univFL} is $\alpha$-approximate\footnote{In Section \ref{sec:related} we describe alternative ways to define the approximation ratio.} if it returns a universal mapping $\varphi$ satisfying $\mathbb{E}_{A\sim \pi}[\cost_{A}(\varphi)]\leq \alpha\cdot \mathbb{E}_{A\sim \pi}[\cost_A(\opt)]$.

Notice that the objective function of {\sc univFL} can be rewritten as
$$
  \sum_{c\in C}d(c,\varphi(c))\cdot \prob_{A\sim \pi}[\{c\}\cap A\neq \emptyset]+\sum_{f\in F}w_f\cdot \prob_{A\sim \pi}[\varphi^{-1}(f)\cap A\neq \emptyset].
$$
Hence {\sc univFL} is almost identical to SFL since $g(R) = \prob_{A\sim \pi}[R \cap A\neq \emptyset]$ is a monotone submodular function of $R$ which is $0$ for $R=\emptyset$. We can therefore adapt our techniques to achieve the following result (see \cref{sec:universal}). Let $\pi_{\min}\coloneqq \min_{c\in C}\{\prob_{A\sim \pi}[c\in A]\}$ be the smallest probability of any client to be activated. W.l.o.g. we will assume $\pi_{\min}>0$.
\begin{theorem}\label{thr:universalFL}
  There is a polynomial-time $O(\log\log \frac{n}{\pi_{\min}})$-approximation algorithm for the {\sc Universal Stochastic Facility Location} problem.
\end{theorem}
For a comparison, Adamczyk, Grandoni, Leonardi and W\l{}odarczyk \cite{AGLW17} obtain an $O(\log n)$ approximation which also holds for non-metric distances. In the case of metric distances, they obtain an $O(1)$ approximation but only in the \emph{independent activation case}, i.e., when the sampled set $A$ of active clients is obtained by independently sampling each client $c$ according to some input probability $\pi'(c)$ for $k$ times.

\subsection{Lower Bounds}

We believe that it is plausible that SFL admits a constant approximation. In particular, one might consider greedy algorithms. In \cref{app:lower-bound} we consider a natural set-cover type greedy algorithm {\tt GreedySFL} for SFL. The same algorithm gives a $1.861$-approximation when applied to the classical {\sc Facility Location} problem~\cite{JMMSV03}. We show that this algorithm does not produce $O(1)$ approximate solutions for SFL, and in fact, it is not better than our algorithm from Theorem~\ref{thr:main}.

\begin{theorem}\label{thm:lower-bound}
  {\tt GreedySFL} has an approximation ratio at least $\Omega(\log\log n)$.
\end{theorem}

The lower bound is based on the construction of a family of instances, parameterized by $\dime \in \mathbb{N}$, where the underlying metric is defined on a hypercube of dimension $\dime$.
We define $\dime \cdot 2^{\dime}$ clients and $O(\dime \cdot 2^{\dime})$ facilities.
The cost of a feasible solution is $2^{\dime}$, but the cost of the greedy algorithm is $\Theta(\log(\dime) \cdot 2^{\dime})$, hence the lower bound follows.
The main challenge in our construction is to define a submodular function $g(\cdot)$ on all subsets of clients.
We present a compact way of defining $g(\cdot)$: it is the expected value of a random process that depends on carefully designed distances (induced by edge weights) in the hypercube.

\subsection{Related Work}\label{sec:related}

In the {\sc (Metric Uncapacitated) Facility Location} problem (FL) we are given a set of clients and a set of facilities in a metric space $d$, where each facility has an opening cost $o_f$.
One has to select a subset of facilities $F'\subseteq F$ and assign each client $c$ to the closest facility $F'(c)$ in $F'$ so as to minimize $
\sum_{c\in C}d(c,F'(c))+\sum_{f\in F'}o_f$.
FL is a special case of both {\sc addSFL} and {\sc multSFL} (and of SFL in the case of uniform opening costs).
FL is among the best-studied problems in the literature from the point of view of approximation algorithms (see, e.g., \cite{CG05,MYZ06,STA97}). It is known to be APX-hard~\cite{guha1999greedy} and the current best-known 1.488-approximation algorithm~\cite{li20131} is a randomized combination of the greedy JMS algorithm~\cite{JMMSV03} with an LP-rounding algorithm from~\cite{byrka2010optimal}. Lagrangian-multiplier preserving algorithms for FL are at the heart of several approximation algorithms for fundamental clustering problems, including {\sc $k$-Median} \cite{ANSW20,BPRST17,CEMN22,CGLS23,GPST23,JMMSV03,JV01,LS16} and {\sc $k$-Means} \cite{ANSW20,CEMN22,GORSV22}.

Various variants of FL were studied in the literature and for most of them (at least with metric connection costs) a constant approximation was eventually discovered. A notable example is the {\sc Capacitated Facility Location} problem in which the number of clients that can be served from a facility is restricted by a location-specific bound. A local-search-based constant approximation for the latter problem is given in \cite{zhang2005multiexchange} (see also \cite{an2017lp} for a more recent LP-based result). SFL is one of the most natural generalizations of (metric) FL where a constant approximation is still not known.

Grandoni, Gupta, Leonardi, Miettinen, Sankowski, and Singh \cite{GGLMSS13}, among other universal stochastic problems, studied {\sc univFL} in the independent activation case. However, they compare the cost of their solution with $\expected_{A\sim \pi}[\cost_A(\opt(A))]$, where $\opt(A)$ is the optimal facility location solution restricted to clients $A$ (while we compare with $\expected_{A\sim \pi}[\cost_A(\opt)]$). For this setting they obtain a $O(\log n)$ approximation, which also holds for non-metric connection costs.

Gupta, P{\'a}l, Ravi, and Sinha \cite{GPRS11} consider a 2-stage stochastic version of FL. Here in a first stage, one buys some facilities, then a subset of active clients is sampled from a given distribution. Finally, one can buy some more facilities, however at an opening cost which is increased by a multiplicative \emph{inflation factor} $\sigma$. For this setting they present a constant approximation.

Universal stochastic problems have a natural online stochastic counterpart. For example, in the {\sc Online Stochastic Facility Location} problem clients are sampled one by one, and when client $c$ is sampled one has to connect $c$ to an already open facility or open a new facility $f$ and connect $c$ to $f$. Garg, Gupta, Leonardi and Sankowski \cite{GGLS08} consider this problem in the independent activation case, i.e. when the next client to be served is sampled from a probability distribution $\pi:C\to \mathbb{R}_{\geq 0}$. For this setting, they present an $O(1)$ approximation. Meyerson \cite{Meyerson01} studied a variant of the problem where an adversary chooses the set of input clients, and then a random permutation of them is presented in input (\emph{random order model}).

\subsection{Preliminaries and Notation}\label{sec:preliminaries}

We use $\ln$ and $\log$ for the logarithm with base 2 and $\ln$ for the natural logarithm.
Define $X = C \cup F$, and $N=|X|=|C \cup F|$. Given a metric $d$ over $X$, we let $d_{\min}$ be the smallest non-zero distance and $d_{\max}$ be the largest distance (that we assume to be positive w.l.o.g). We use $g(c)$ as a shortcut for $g(\{c\})$.

We sometimes express a feasible solution to SFL in the form $S=(S^f)_{f\in F}$, where $S^f\subseteq C$ specifies the clients $\varphi^{-1}(f)$ assigned to $f$. Notice that for each $c\in C$ there is precisely one $f\in F$ with $c\in S^f$. We define a \emph{partial assignment} as $S=(S^f)_{f\in F}$, where $S^f\subseteq C$. We say that $S$ covers the clients $C'=\cup_{f\in F}S^f\subseteq C$. Notice that, for technical reasons, in a partial assignment we allow $S^f\cap S^{f'}\neq \emptyset$ for two distinct $f,f'\in F$ (i.e. we allow to simultaneously assign a client to more than one facility). The cost of a (partial) assignment $S$ of the above type is defined as
$
  \cost(S)\coloneqq \conn(S)+\open(S),
$
where $\conn(S)\coloneqq \sum_{f\in F}\sum_{c\in S^f}d(c,f)$ is the connection cost of $S$ and $\open(S)\coloneqq \sum_{f\in F}g(S^f)$ is the opening cost of $S$. Given a (possibly infeasible) fractional solution $x$ for \eqref{eq:configuration-lp}, we analogously define $\cost(x)=\conn(x)+\open(x)$, where $\conn(x)=\sum_{c\in C} \sum_{f\in F} \sum_{R\ni c} d(c,f) \cdot x_R^f$, and $\open(x)=\sum_{f \in F} \sum_{R \subseteq C} g(R) \cdot x_R^f$.

It is convenient to define the merge $S=S_1+S_2$ of two partial assignments $S_1$ and $S_2$ naturally as follows: (1) for each facility $f\in F$, we initially set $S^f\coloneqq S^f_1\cup S^f_2$; (2) while there exist two distinct facilities $f$ and $f'$ with $S^{f}\cap S^{f'}\neq \emptyset$, replace $S^{f'}$ with $S^{f'}\setminus S^f$ (intuitively this second step guarantees that each client is assigned to no more than one facility). We observe that merging two partial assignments cannot increase the total cost.

\begin{lemma}\label{lem:merge}
  For any two partial assignments $S_1$ and $S_2$, $\cost(S_1+S_2)\leq \cost(S_1)+\cost(S_2)$.
\end{lemma}
\begin{proof}
Let $S=S_1+S_2$, and $S'$ be the intermediate value of $S$ obtained by executing only step (1) of the merge operation. One has $\conn(S')=\conn(S_1)+\conn(S_2)$. Furthermore, by the submodularity (hence subadditivity) of $g(\cdot)$, $\open(S')\leq \open(S_1)+\open(S_2)$.
Clearly $\conn(S)\leq \conn(S')$, and the monotonicity of $g(\cdot)$ implies that $\open(S)\leq \open(S')$. The claim follows.
\end{proof}
We will exploit the following fairly standard reductions (proofs in Section \ref{sec:omitted}), thanks to which in the following it will be sufficient to obtain an $O(\log\log N)$ approximation for SFL. In order to distinguish between distinct instances $J$ of the problem, we use $\cost_J(\varphi)$ to denote the cost of $\varphi$ w.r.t.\ $J$ and define similarly $\open_J(\varphi)$ etc.
\begin{lemma}\label{lem:reduceNumberFacilities}
  There is a $3$-approximate reduction from SFL to the special case where $m=n$.
\end{lemma}

\begin{lemma}\label{lem:reduceDistances}
  For any constant $\varepsilon>0$, There is a $(1+4\varepsilon)$-approximate reduction from SFL to the special case where the metric $d$ satisfies $d_{\min}=2$ and $d_{\max}\leq \frac{2nN}{\varepsilon}$.
\end{lemma}

One of the key tools that we use is the notion of probabilistic tree embedding, which we use to map the input metric into a metric on a \emph{hierarchically well-separated tree} (HST) while stretching the distances by a small enough factor. We recall that an HST is an edge weighted rooted tree where all the leaves are at the same distance from the root $r$. Furthermore, on every path from a leaf to $r$ the edge weights are $1,2,4,\dots$ In particular, edges at the same level have the same weight. We will use the following construction\footnote{We slightly and trivially extend their claim to consider nodes at distance $0$.} by Fakcharoenphol, Rao and Talwar~\cite{FakcharoenpholRT04}.

\begin{theorem}[FRT metric tree embedding~\cite{FakcharoenpholRT04}]\label{thm:frt-tree-embedding}
    For any finite metric space $(M,d)$ with $d_{\min}>1$, there exists a randomized polynomial-time algorithm returning an HST $T$ such that:
    \begin{enumerate}\itemsep0pt
        \item Every $a\in M$ is mapped to some leaf $v(a)$ of $T$ (with elements at distance zero being mapped to the same leaf);
        \item Let $d^T(v(a),v(b))$ be the length of the path between the leaves $v(a)$ and $v(b)$ of $T$. Then $d^T\left(v(a),v(b)\right) \geq d(a,b)$ and $\expected\left[d^T(v(a),v(b))\right] \leq 8 \log |M| \cdot d(a,b)$;
        \item $T$ has depth $O(\log d_{\max})$.
    \end{enumerate}
\end{theorem}

For a given set $C$, let $h\colon 2^C\to {\mathbb R}$ be a
monotone submodular function with $h(\emptyset)=0$. The \emph{Lov\'{a}sz extension} $\hat{h}\colon [0,1]^C \rightarrow {\mathbb R}$ of $h(\cdot)$ is defined as
\begin{equation}\label{eq:lovasz-extension}
  \hat h(y) \coloneqq \min\Big\{\;\sum_{R \subseteq C}h(R)\mu_R:\ \sum_{R\subseteq C}\sum_{R \ni c}\mu_R = y_c \ \forall c\in C,\ \sum_{R \subseteq C} \mu_R=1,\ \mu\geq0 \;\Big\}.
\end{equation}
The function $\hat h(\cdot)$ is convex. We remark that $\hat h(y)$ can be alternatively defined as
\begin{equation}\label{eq:lovasz-extension-bis}
    \hat h(y) \coloneqq
        \sum_{k=1}^{n-1} h\left(\{c_1, \dots, c_k\}\right)
        (y_{c_k} - y_{c_{k+1}}) + h(C) y_{c_{n}}
\end{equation}
where the components of $y$ are sorted in decreasing order, i.e. $y_{c_1} \geq y_{c_2} \geq \dots \geq y_{c_{n}}$ \cite[Section~6.3]{fujishige2005submodular}.
By the monotonicity of $h(\cdot)$, $\hat h(\cdot)$ is also non-decreasing in the sense that $\hat h(y) \geq \hat h(y')$ if $y\geq y'$.

\section{Reducing the Connection Cost}\label{sec:reducingConnection}

In this section, we show how to compute a random partial assignment $S_1=(S_1^f)_{f\in F}$ covering a random subset of clients $C_1\coloneqq \cup_{f\in F}S_1^f\subseteq C$ with the following high-level properties: the expected cost of $S_1$ is ``small enough'' and (2) each client belongs to $C_1$ with ``large enough'' probability. In the next section, we will describe a different partial assignment $S_2=(S_2^f)_{f\in F}$, again of small enough cost, covering the remaining clients $C_2\coloneqq C\setminus C_1$. By merging these two partial assignments we obtain a feasible solution for the input problem of small enough total cost.

Let $\dot{x}$ be an optimal solution to \eqref{eq:configuration-lp} with at most $\poly(N)$ non-zero entries that can be computed via Lemma \ref{lem:solveConfLP}. The basic idea behind the next lemma is fairly standard: we sample partial assignments according to the distribution induced by $\dot{x}$ for $\ln\ln N$ times, and merge them together.

\begin{lemma}\label{lem:sampling}
  In polynomial time one can compute a random partial assignment $S_1$ covering a random subset of clients $C_1$ such that: (1) $\expected\left[\cost(S_1)\right] \leq \ln\ln (N) \cdot \cost(\dot{x})$ and (2) For each $c\in C$, $\prob[c\in C_1]\geq 1-\frac{1}{\ln N}$.
\end{lemma}
\begin{proof}
For $i \in \{1,2,\dots,\ln\ln N\}$ and for every $R\subseteq C$, we define a partial assignment $S(i,R)$ by setting $S^f(i,R)=R$ independently with probability $\dot{x}_{R}^f$ and $S^f(i,R)=\emptyset$ otherwise. Let $S_1=\sum_{i=1}^{\ln\ln N}\sum_{R\subseteq C}S(i,R)$ be obtained by merging all these solutions, and let $C_1=\cup_{f\in F}S_1^f$. Observe that
$$
  \prob[c\notin C_1]=\prod_{f\in F}\prod_{R\ni c}(1-\dot{x}_R^f)^{\ln\ln N}\leq e^{-\ln\ln N\sum_{f\in F}\sum_{R\ni c}\dot{x}_S^f}\leq e^{-\ln\ln N}=\frac{1}{\ln N}.
$$
Furthermore, by \cref{lem:merge}, $\expected[\cost(S_1)]$ is upper-bounded by
$$
\sum_{i=1}^{\ln\ln N}\sum_{R\subseteq C}\expected[\cost(S(i,R))]=\ln\ln N\cdot \sum_{f\in F,R\subseteq C}\dot{x}^f_{R}\cdot \bigg(g(R)+\sum_{c\in R}d(c,f)\bigg)= \ln\ln N\cdot \cost(\dot{x}).\qedhere
$$
\end{proof}
Consider the partial assignment $S_1$ covering the random subset of clients $C_1$ as in the previous lemma. Let $C_2\coloneqq C\setminus C_2$ be the remaining (uncovered) clients.
Let also $\ddot{x}$ be $\dot{x}$ restricted to $C_2$, i.e. $\ddot x_R^f = \sum_{R' \subseteq C_1} \dot x_{R \cup R'}^f$ for $R \subseteq C_2$ and $f\in F$. The following lemma upper bounds the expected opening and connection cost of $\ddot{x}$.

\begin{lemma}\label{lem:costResidualClients}
  One has $\open(\ddot{x})\leq \open(\dot{x})$ and $\expected[\conn(\ddot{x})]\leq \frac{1}{\ln N}\conn(\dot{x})$.
\end{lemma}
\begin{proof}
    We have $\open(\ddot{x})\leq \open(\dot{x})$ by the monotonicity of $g(\cdot)$. For the connection cost, notice that the probability of a client $c$ being in $C_2$ is at most $1/\ln N$, and only in that case one has to pay the associated connection cost. Thus by linearity of expectation, the expected connection cost of $\ddot{x}$ is at most $\conn(\dot{x})/\ln N$. The claim follows.
\end{proof}
Notice that $\ddot{x}$ is a feasible fractional solution for~\eqref{eq:configuration-lp} limited to $C_2$.
In the following section, we show how to randomly round $\ddot{x}$ to a partial assignment $S_2$ which covers $C_2$ at expected cost $O(\log\log N) \cdot \cost(\ddot{x})$. It will then follow that $S_1+S_2$ is a feasible $O(\log\log N)$-approximate solution to the input SFL instance.

\section{Approximating SFL on an HST}\label{sec:treeCase}

We say that an instance $(C\cup F,d^T,g(\cdot))$ of SFL is of \emph{HST-type} if the metric $d^T$ is an HST metric over a tree $T$ of the type guaranteed by Lemma \ref{lem:sampling}. We remark that we allow multiple clients $C(v)$ and facilities $F(v)$ to be colocated at each leaf $v$ of $T$. In this section we will describe an $O(\log\log N)$-approximate LP-rounding algorithm for the considered instances w.r.t.\ \eqref{eq:configuration-lp}.
\begin{lemma}\label{lem:treeLProunding}
  Given a feasible fractional solution $x$ to \eqref{eq:configuration-lp} for an HST-type SFL instance, in polynomial time one can compute a feasible (integral) solution for the same instance with cost at most $O(\log\log N)\cdot \cost(x)$.
\end{lemma}
Theorem \ref{thr:main} directly follows.
\begin{proof}[Proof of Theorem \ref{thr:main}]
By Lemma \ref{lem:reduceNumberFacilities} it is sufficient to describe an $O(\log\log N)$-approximation. Furthermore by Lemma \ref{lem:reduceDistances}, we can assume that $d_{\min}=2$ and $d_{\max}\leq \frac{2nN}{\varepsilon}$.

By applying the construction of Section \ref{sec:reducingConnection} we compute a random partial assignment $S_1=(S^f_1)_{f\in F}$ covering the clients $C_1=\cup_{f\in F}S^f_1$ with expected cost at most $O(\log\log N)\cdot \cost(\dot{x})$, where $\dot{x}$ is an optimal solution to \eqref{eq:configuration-lp}. Furthermore, by Lemma \ref{lem:costResidualClients}, we obtain a feasible solution $\ddot{x}$ to \eqref{eq:configuration-lp} restricted to clients $C_2\coloneqq C\setminus C_1$ which satisfies $\open(\ddot{x})\leq \open(\dot{x})$ and $\expected[\conn(\ddot{x})]\leq \frac{1}{\ln N}\conn(\dot{x})$. By applying the probabilistic tree embedding from Theorem \ref{thm:frt-tree-embedding} to the metric $(C_2\cup F,d)$, we obtain an HST-type SFL instance $(C_2\cup F,d^T,g(\cdot))$ where the tree has depth $D=O(\log d_{\max})=O(\log N)$. Observe that $\ddot{x}$ is a feasible fractional solution for \eqref{eq:configuration-lp} restricted to $C_2$ on the HST-type instance. Furthermore, let $\conn_{T}(\ddot{x})$ denote the connection cost of $\ddot{x}$ w.r.t.\ the HST-type instance, and define similarly $\open_{T}(\ddot{x})$ and $\cost_{T}(\ddot{x})$. Then one has
$$
  \expected[\cost_{T}(\ddot{x})]=\open(\ddot{x})+\expected[\conn_{T}(\ddot{x})]\leq \open(\dot{x})+O(\log N)\cdot\expected[\conn(\ddot{x})] \leq O(\cost(\dot{x})).
$$
By applying the LP-rounding algorithm from Lemma \ref{lem:treeLProunding} to $\ddot{x}$ one obtains a partial assignment $(S^f_2)_{f\in F}$ covering the clients $C_2$ of cost at most $O(\log\log N)\cost(\dot{x})$. The same solution has no larger cost in the original problem (on a non-tree metric). Altogether $S_1+S_2$ is a feasible solution to the input SFL problem of expected cost at most $O(\log\log N)\cdot \cost(\dot{x})\leq O(\log\log N)\cdot\cost(\opt)$.
\end{proof}

In the rest of this section, we prove Lemma \ref{lem:treeLProunding}. To this aim, we will first present a reduction to a different problem that we call the {\sc Descendent-Leaf Assignment} problem (DLA) (see Section \ref{sec:reductionDLA}). Then, we will present a good-enough approximation algorithm for DLA (see Section \ref{sec:approximationDLA}).

\subsection{A Reduction to DLA}\label{sec:reductionDLA}

In the {\sc Descendent-Leaf Assignment} problem (DLA) we are given a rooted tree $\tilde{T}$ with depth $D$, a set of facilities $\tilde{F}$ and a set of clients $\tilde{C}$. Each $x\in \tilde{F}\cup \tilde{C}$ is mapped into some node $v(x)$ of $\tilde{T}$, with the restriction that facilities are mapped into leaves of $\tilde{T}$.
By $\tilde{F}_c$ we denote the facilities which are assigned to nodes that are descendants of $v(c)$ in $T$ ($v(c)$ included if it is a leaf).
A feasible solution consists of an assignment $\tilde{\varphi}:\tilde{C}\to \tilde{F}$ of each $c\in \tilde{C}$ to some $f\in \tilde{F}_c$. The cost of this solution is $\sum_{f\in \tilde{F}}h(\tilde{\varphi}^{-1}(f))$, where $h(\cdot)$ is a monotone submodular function over $\tilde{C}$ with $h(\emptyset)=0$. Similarly to SFL, we also express a feasible solution as $S=(S^f)_{f\in \tilde{F}}$, where $S^f=\tilde{\varphi}^{-1}(f)$, and let $\cost_{\DLA}(S)=\sum_{f\in \tilde{F}}h(S^f)$ be the associated cost. We define a convex-programming (CP) relaxation for DLA as follows:
\begin{align*}\label{eq:DLA-LP}\tag{DLA-CP}
        \min & \sum_{f \in \tilde{F}} \hat h(z^f) \\
        \text{s.t.} \quad
        &\sum_{f \in \tilde{F}_c} z_c^f = 1 \quad \forall c\in \tilde{C}. \\
        & z_c^f \geq 0 \quad \forall c\in \tilde{C},\ \forall f \in \tilde{F}.
\end{align*}
In a $0$-$1$ integral solution we interpret $z^f_c=1$ as $c$ being assigned to $f$. Recall that $\hat h(\cdot)$ is convex, which makes \eqref{eq:DLA-LP} a convex program. We also notice that each feasible assignment $S=(S^f)_{f\in \tilde{F}}$ corresponds to a feasible integral solution $z=(z^f)_{f\in \tilde{F}}$ to \eqref{eq:DLA-LP} with $\cost_{\DLA}(S)=\cost_{\DLA}(z)\coloneqq \sum_{f\in \tilde{F}}\hat{h}(z^f)$ and vice versa. Hence indeed \eqref{eq:DLA-LP} is a CP-relaxation of DLA.

The next lemma provides the claimed reduction from SFL on HST-type instances to DLA.
\begin{lemma}\label{lem:DLAreduction}
  Given a polynomial-time $O(\log D )$-approximate CP-rounding algorithm for DLA w.r.t.\ \eqref{eq:DLA-LP}, where $D$ is the depth of the tree, there is polynomial-time $O(\log\log N)$-approximate LP-rounding algorithm for SFL on HST-type instances with tree-depth $O(\log N)$ w.r.t.\ \eqref{eq:configuration-lp}.
\end{lemma}
\begin{proof}
Let $(C\cup F,d^T,g(\cdot))$ be the considered instance of SFL over an HST $T$, and $x$ be an input feasible fractional solution to \eqref{eq:configuration-lp} for this instance.

We build an instance of DLA as follows.
First, let $y^f_c\coloneqq \sum_{R\subseteq C:c\in R}x^f_R$: intuitively this is the fractional amount by which $c$ is assigned to $f$ in $x$. We set $h(\cdot)=g(\cdot)$ and $\tilde{T}=T$. Notice that $D=O(\log N)$. We set $\tilde{F}=F$ and map each $f\in \tilde{F}$ to the corresponding leaf of $T$ containing $f$. We also set $\tilde{C}=C$, and map each $c\in \tilde{C}$ to a node $v(c)$ as follows. Let $T_v$ be the subtree rooted at $v$ (containing $v$ and all its descendants) and $F_v$ be the facilities located in the leaves of $T_v$. Let also $\ell(c)$ be the leaf of $T$ containing $c$ in the mapping associated with $T$. We define $v(c)$ as the lowest ancestor of $\ell(c)$ such that $\sum_{f\in F_{v(c)}}y_c^f\geq 1/2$. Notice that $v(c)=\ell(c)$ is possible (in which case there is at least one facility $f$ colocated with $c$ at $l(c)$).

We next define a feasible fractional solution $z$ for \eqref{eq:DLA-LP} w.r.t this DLA instance as follows.
For each $c\in \tilde{C}$ we set $z^f_{v(c)}=y^f_c/(\sum_{f'\in F_{v(c)}}y^{f'}_c)$ if $f\in F_{v(c)}$, and otherwise $z^f_{v(c)}=0$. Let $\tilde{\varphi}$ be a solution to the DLA instance obtained with the CP-rounding algorithm in the claim w.r.t.\ $z$. We obtain a feasible solution $\varphi$ for the input instance by simply setting $\varphi(c)= \tilde{\varphi}(c)$.

It remains to analyze the cost of $\varphi$.
Define $\bar{z}^f_{v(c)}=y^f_c/(\sum_{f'\in F_{v(c)}}y^{f'}_c)$ for all $f\in F$. Notice that $\bar{z}\geq z$. By the definition of $\hat h(\cdot)$ and its monotonicity, $\hat{h}(z^f)\leq \hat{h}(\bar{z}^f)=\hat{h}(y^f/(\sum_{f'\in F_{v(c)}}y^{f'}_c))\leq 2\hat{h}(y^f)=2\hat{g}(y^f)$.
Notice that by plugging in $x_R^f$ for $\mu_R$ in the set in \eqref{eq:lovasz-extension} and by how $y$ is defined w.r.t.\ $x$ above, we get $\hat g(y^f) \leq \sum_{R \subseteq C}g(R)\cdot x_R^f$ and in particular $\sum_{f\in F}\hat g(y^f) \leq \open(x)$. Thus, we have $\cost_{\DLA}(z)\leq 2\open(x)$ and
\begin{equation}\label{eq:dlareduction-openingcosts}
  \open(\varphi)=\cost_{\DLA}(\tilde{\varphi})=O(\log D)\cdot\cost_{\DLA}(z)\leq O(\log \log N)\cdot 2\open(x).
\end{equation}
Consider next the connection cost. For each client $c\in C$, let $\Delta$ be the weight of the edge between $v(c)$ and its children in $T$. Observe that the distance between $v(c)$ and the leaves in $T_{v(c)}$ is exactly $2\Delta-1$.
Furthermore, both $c$ and $\varphi(c)$ are located in the leaves of $T_{v(c)}$ in the HST mapping. Hence
$
  d^T(c,\varphi(c))\leq 2(2\Delta-1).
$
We next compare the latter cost with the connection cost associated with $c$ in $x$, namely $\sum_{f\in F}d(c,f)y^f_c$. Let $\alpha=\sum_{f\in F_{v(c)}}y^f_c\geq \frac{1}{2}$. Suppose first that $\alpha\leq \frac{5}{6}$. Notice that for each $f\in F\setminus F_{v(c)}$, if any, the $f$-$c$ path in $T$ uses the edge, of weight $2\Delta$, between $v(c)$ and its parent. In particular, all such paths have length at least $2(4\Delta-1)$. Furthermore, $\sum_{f\in F\setminus F_{v(c)}}y^f_c=1-\alpha\geq \frac{1}{6}$. Thus
$$
  \sum_{f\in F}d(c,f)y^f_c\geq \sum_{f\in F\setminus F_{v(c)}}d(c,f)y^f_c\geq \frac{1}{6}2(4\Delta-1)\geq \frac{2}{3}(2\Delta-1).
$$
Consider next the complementary case where $\alpha\geq \frac{5}{6}$. Let $w(c)$ be the child of $v(c)$ along the $v(c)$-$c$ path in $T$. By the definition of $v(c)$, it must be the case that $\sum_{f\in F_{w(c)}}y^f_c< \frac{1}{2}$, and consequently $\sum_{f\in F_{v(c)}\setminus F_{w(c)}}y^f_c\geq \frac{1}{3}$. For each $f\in F_{v(c)}\setminus F_{w(c)}$, the $f$-$c$ path in $T$ has length exactly $2(2\Delta-1)$. Thus
$$
  \sum_{f\in F}d(c,f)y^f_c\geq \sum_{f\in F_{v(c)}\setminus F_{w(c)}}d(c,f)y^f_c\geq \frac{2}{3}(2\Delta-1).
$$
In both cases the connection cost of $c$ in $\varphi$ is at most $3$ times its connection cost in $x$. We conclude that $\conn(\varphi)\leq 3\conn(x)$. Altogether
$
  \cost(\varphi)\leq 3\conn(x)+O(\log\log N)\cdot 2\open(x)\leq O(\log\log N)\cdot \cost(x).
$
\end{proof}

\subsection{An Approximation Algorithm for DLA}\label{sec:approximationDLA}

In this section, we present a CP-rounding algorithm for DLA. Lemma \ref{lem:treeLProunding} follows by chaining Lemmas \ref{lem:DLAreduction} and \ref{lem:DLArounding}.
\begin{lemma}\label{lem:DLArounding}
  Given a feasible fractional solution $z$ to \eqref{eq:DLA-LP} on an instance of DLA with tree-depth $D$, in polynomial time one can compute a feasible (integral) solution to the same instance of cost at most $O(\log D)\cdot \cost_{\DLA}(z)$.
\end{lemma}
The CP-rounding algorithm from \cref{lem:DLArounding} is essentially the algorithm by Bosman and Olver \cite{BO20} with minor modifications that we introduced to simplify our correctness analysis. Also, the analysis of its approximation ratio is essentially identical to \cite{BO20}, but we reproduce it for the sake of completeness. In particular, we will exploit the following definitions and lemma from \cite{BO20}. Let $h:2^{\tilde{C}}\to \mathbb{R}_{\geq 0}$ be a monotone submodular function with $h(\emptyset)=0$. For a given $f\in \tilde{F}$ and a (possibly infeasible) solution $z$ to \eqref{eq:DLA-LP}, let $L_\theta(z^f)\coloneqq \{c\in \tilde{C}: z^f_c\geq\theta\}$ be the set of clients that are served fractionally by at least some value $\theta$ by $f$. Let also $z^{f|\theta}$ be obtained from $z^f$ by rounding down to $\theta$ the values larger than $\theta$, i.e. $z_c^{f|\theta}\coloneqq \min\{z^f_c,\theta\}$ for each $c\in \tilde{C}$. Given $\theta\in [0,1]$ and $z^f\in [0, 1]^{\tilde{C}}$, we say that the set $L_\theta(z^f)$ is $\alpha$-supported (w.r.t.\ $h$) if
$
  \hat h(z^f) - \hat h(z^{f|\theta}) \geq \alpha h(L_\theta(z^f)).
$
\begin{lemma}[{\cite[Lemma 5.2]{BO20}}]\label{lem:BO20}
  Given $z^f\in [0, 1]^{\tilde{C}}$ and $\alpha\in (0, 1]$, at least one of the following holds:
  (1) there exists $\theta\in [0, 1]$, which can be computed in polynomial time, such that $L_\theta(z^f)$ is $\frac{\alpha}{32}$-supported; (2) $2^{1/\alpha}h(L_1(z^f))\leq\hat h(z^f)$.
\end{lemma}

Our algorithm is Algorithm~\ref{alg:tree} in the figure. Recall that $\tilde{T}_v$ is the subtree rooted at node $v$, where $\tilde{T}_v$ includes $v$ and all its descendants. Furthermore, $\tilde{F}_v$ is the set of facilities mapped into the leaves of $\tilde{T}_v$. As usual the level of a node is its hop-distance from the root.
\begin{algorithm}
    \caption{}
    \footnotesize
    \textbf{Input:} Feasible solution $z$ to \eqref{eq:DLA-LP}
    \begin{algorithmic}[1]
        \State $S^f\gets \emptyset$ for all $f\in F$
        \For{$i=0,\dots, D$}
            \State For every node $v$ at level $D-i$, choose an arbitrary $f_v\in \tilde{F}_v$ and set $z^{f_v}\gets\sum_{f'\in \tilde{F}_v}z^{f'}$ and $z^{f'}\gets 0$

            for all $f'\in \tilde{F}_v\setminus \{f_v\}$\label{alg:merging}
            \If{there exists $\theta\in [0,1]$ such that $L_\theta(z^{f_v})$ is $\frac{1}{32\log (D+1)}$-supported}\label{alg:condition}
                \State For an arbitrary such $\theta$, set $S^{f_v}\gets S^{f_v}\cup L_\theta(z^{f_v})$ and $z^{f_v}_c\gets 0$ for all $c\in L_\theta(z^{f_v})$ \label{alg:choose-theta}
            \Else
                \State Set $S^{f_v}\gets S^{f_v}\cup L_1(z^{f_v})$ and $z^{f_v}_c\gets 0$ for all $c\in L_1(z^{f_v})$\label{alg:buying-integrals}
            \EndIf
        \EndFor
        \State For every $c\in \tilde{C}$ choose $f\in\tilde{F}_c$ such that $c\in S^{f}$ and set $S^{f'}\gets S^{f'}\setminus\{c\}$ for all $f'\in \tilde{F}\setminus\{f\}$ \label{alg:pruning}
        \State \textbf{return} $(S^f)_{f\in \tilde{F}}$
    \end{algorithmic}
    \label{alg:tree}
\end{algorithm}

Clearly Algorithm~\ref{alg:tree} runs in polynomial time.
The next two lemmas analyze the correctness and the approximation ratio of Algorithm \ref{alg:tree}, hence proving Lemma \ref{lem:DLArounding}.
\begin{lemma}\label{lem:DLAcorrectness}
  Algorithm \ref{alg:tree} computes a feasible DLA solution.
\end{lemma}
\begin{proof}
Consider a given client $c\in \tilde{C}$ such that $v(c)$ is at level $D-i$ in $\tilde{T}$. Let us show that the following invariant holds at the beginning of each iteration $j\leq i$: either $\sum_{f\in \tilde{F}_c}z^f_c=1$ or $c\in S^f$ for some $f\in \tilde{F}_c$. The invariant trivially holds for $j=0$. Assume that it holds up to the beginning of iteration $j<i$, and consider what happens during that iteration. Notice that for every node $v$ at level $D-j>D-i$, we either have that every $f \in\tilde{F}_v$ is a descendant of $v(c)$ or every $f \in\tilde{F}_v$ is not in $\tilde{F}_c$. Therefore, in Step \eqref{alg:merging} the value of $\sum_{f\in \tilde{F}_c}z^f_c$ does not change. In more detail, it remains $1$ by inductive hypothesis. The same value can decrease in Steps \eqref{alg:choose-theta} or \eqref{alg:buying-integrals}, however, this can only happen if $c$ is added to $S^{f_v}$ for some $f_v\in \tilde{F}_c$. Thus the invariant holds at the end of the $j$-th iteration, hence at the beginning of the next iteration $j+1$.

Due to the invariant, during the iteration $i$, when one considers the node $v=v(c)$, one has that either $c$ already belongs to some $S^f$ with $f\in \tilde{F}_c$, or $\sum_{f\in \tilde{F}_c}z^f_c=1$. In the latter case, after Step~\eqref{alg:merging}, $z_c^{f_{v}}=1$ where $f_{v}\in \tilde{F}_c$, so $c$ belongs to every set $L_\theta(z^{f_{v}})$ with $\theta\in [0,1]$. As a consequence, $c$ is added to $S^{f_v}$ either in Step \eqref{alg:choose-theta} or in Step \eqref{alg:buying-integrals}.

It might happen that a client $c$ is assigned \emph{also} to a facility not in $\tilde{F}_c$. Step~\eqref{alg:pruning} guarantees that the final assignment of $c$ is correct and unique.
\end{proof}

\begin{lemma}\label{lem:alg_cost}
  Algorithm~\ref{alg:tree} outputs a solution of cost at most $O(\log D)\cdot \cost_{\DLA}(z)$.
\end{lemma}
\begin{proof}
Recall that $\cost_{\DLA}(z)=\sum_{f\in\tilde{F}} \hat h(z^f)$.
We start by observing that the value of $\cost_{\DLA}(z)$ can not increase over time when $z$ changes during the execution of the algorithm. Indeed, Steps \eqref{alg:choose-theta} and \eqref{alg:buying-integrals} can only decrease the entries of $z$, hence $\cost_{\DLA}(z)$ by the monotonicity of $\hat{h}(\cdot)$. The only other changes of $z$ happen in Step \eqref{alg:merging}. Let us interpret this step as iteratively decreasing to zero $z^{f'}$ for each $f'\in \tilde{F}_v\setminus \{f_v\}$ and increasing $z^{f_v}$ by the same amount. The decrease of the cost at each step is $\hat{h}(z^{f_v})+\hat{h}(z^{f'})-\hat{h}(z^{f_v}+z^{f'})$. By the alternative definition of $\hat{h}(\cdot)$ as in \eqref{eq:lovasz-extension-bis} and its convexity, one has
$
  \hat{h}(z^{f_v}+z^{f'})=2\hat{h}\left(\frac{z^{f_v}+z^{f'}}{2}\right)\leq 2\left(\frac{1}{2}\hat{h}(z^{f_v})+\frac{1}{2}\hat{h}(z^{f'})\right)= \hat{h}(z^{f_v})+\hat{h}(z^{f'}).
$
Hence the decrease of the cost is non-negative as required.

For each facility $f$ and level $i$, let $\Delta^{\theta}_i (f)$ be the clients added to $S^f$ in Step \eqref{alg:choose-theta} during iteration $i$ (possibly $\Delta^{\theta}_i(f)=\emptyset$). We define similarly $\Delta^{1}_i (f)$ w.r.t.\ Step \eqref{alg:buying-integrals}. Notice that, by the submodularity (hence subadditivity) of $h(\cdot)$, the increase of the cost of the solution due to adding $\Delta$ to $S^f$ is at most $h(\Delta)$. Therefore we can upper bound the cost of the final solution $S=(S^f)_{f\in \tilde{F}}$ by
$$
  \cost_{\DLA}(S)\coloneqq \sum_{f\in \tilde{F}}h(S^f)\leq \sum_{i=0}^{D}\sum_{f\in \tilde{F}}\Big(h(\Delta^{\theta}_i (f))+h(\Delta^{1}_i (f))\Big).
$$
Let us upper bound the right-hand side of the above inequality. Let $z(i)$ denote the value of $z$ at the beginning of iteration $i$. From the previous observation, we have $\hat{h}(z(i))\leq \hat{h}(z)$ for every $i$. By Lemma \ref{lem:BO20} with $\alpha=\frac{1}{\log (D+1)}$, for any $\Delta^1_i(f)$ one has $h(\Delta^1_i(f))\leq \frac{1}{D+1}\hat{h}(z^f(i))$. Thus
\begin{equation}\label{eq:bound-delta-one}
  \sum_{i=0}^{D}\sum_{f\in \tilde{F}}h\big(\Delta^{1}_i (f)\big)\leq
  \sum_{i=0}^{D}\sum_{f\in \tilde{F}}\frac{1}{D+1}\hat{h}\big(z^f(i)\big)\leq
  \sum_{i=0}^{D}\frac{1}{D+1}\cost_{\DLA}(z(i))\leq
  \cost_{\DLA}(z).
\end{equation}

Let $z(D+1)$ be the value of $z$ at the end of the $D$-th iteration, hence in particular $\cost_{\DLA}(z(D+1))\geq 0$. Notice that $z=z(0)$. We can lower bound $\cost_{\DLA}(z)$ by
$$
  \cost_{\DLA}(z)\geq\sum_{i=0}^{D}\Big(\cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1))\Big).
$$
Let $z_1(i)$ be the value of $z$ obtained from $z(i)$ after applying Step \eqref{alg:merging} for all nodes of level $D-i$. Let also $z_2(i)$ be the value obtained from $z_1(i)$ if, for all the facilities $F'_i$ where Step \eqref{alg:choose-theta} is applied during iteration $i$, instead of setting $z^f_c=0$ one sets $z^f_c=\theta$ for the corresponding value of $\theta$. For the facilities not in $F'_i$ we simply let $z_2^f(i)=z_1^f(i)$. Observe that $z(i+1)\leq z_2(i)\leq z_1(i)\leq z(i)$. One has
\begin{align*}
  & \cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1))\\
  \geq & \cost_{\DLA}(z_1(i))-\cost_{\DLA}(z(i+1)) \geq
  \cost_{\DLA}(z_1(i))-\cost_{\DLA}(z_2(i))\\
  = & \sum_{f\in \tilde{F}}\hat{h}\Big(z_1^f(i)\Big)-\hat{h}\Big(z_2^f(i)\Big)=
  \sum_{f\in F'_i}\hat{h}\Big(z_1^f(i)\Big)-\hat{h}\Big(z_2^f(i)\Big)\geq
  \frac{\sum_{f\in F'_i}h\big(\Delta^{\theta}_i(f)\big)}{32\log(D+1)}=
  \frac{\sum_{f\in \tilde{F}}h\big(\Delta^{\theta}_i(f)\big)}{32\log(D+1)}.
\end{align*}
In the first two inequalities above we used the monotonicity of $\hat{h}(\cdot)$, while in the last inequality the definition of $\alpha$-supported. Altogether
\begin{equation}\label{eq:bound-delta-theta}
    \sum_{i=0}^{D}\sum_{f\in \tilde{F}}h\Big(\Delta^{\theta}_i (f)\Big)\leq 32\log(D+1)\cdot \sum_{i=0}^{D}\Big(\cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1)) \Big)\leq O(\log D)\cdot \cost_{\DLA}(z).
\end{equation}
By the monotonicity of $h(\cdot)$, Step~\eqref{alg:pruning} cannot increase the cost of the solution, hence the claim.
\end{proof}

\section*{Acknowledgements}

Fateme Abbasi and Jaros\l{}aw Byrka were supported by Polish National Science Centre (NCN) Grant 2020/39/B/ST6/01641.
Marek Adamczyk was supported by Polish National Science Centre (NCN) Grant 2019/35/D/ST6/03060.
Miguel Bosch Calvo, Fabrizio Grandoni, Krzysztof Sornat and Antoine Tinguely were supported by the SNSF Grant 200021\_200731/1.

\bibliographystyle{alpha}