# Extremal Problem for Matchings and Rainbow Matchings on Direct Products

Jian Wang1, Jie You2
1Department of Mathematics
Taiyuan University of Technology
Taiyuan 030024, P. R. China
2Center for Applied Mathematics
Tianjin University
Tianjin 300072, P. R. China
E-mail<EMAIL_ADDRESS>2yj<EMAIL_ADDRESS>
###### Abstract

Let $n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers and let
$V_{1},\dots,V_{\ell}$ be disjoint sets with $|V_{i}|=n_{i}$ for
$i=1,\dots,\ell$. Define $\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ as the
collection of all subsets $F$ of $\cup_{i=1}^{\ell}V_{i}$ with $|F\cap
V_{i}|=k_{i}$ for each $i=1,\dots,\ell$. In this paper, we show that if the
matching number of
$\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ is at most $s$
and $n_{i}\geq 4\ell^{2}k_{i}^{2}s$ for all $i$, then
$|\mathcal{F}|\leq\max_{1\leq
i\leq\ell}[\binom{n_{i}}{k_{i}}-\binom{n_{i}-s}{k_{i}}]\prod_{j\neq
i}\binom{n_{j}}{k_{j}}$. Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$
with $n_{i}\geq 8\ell^{2}k_{i}^{2}s$ for all $i$. We also prove that if
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ are rainbow matching
free, then there exists $t$ in $[s]$ such that
$|\mathcal{F}_{t}|\leq\max_{1\leq
i\leq\ell}\left[\binom{n_{i}}{k_{i}}-\binom{n_{i}-s+1}{k_{i}}\right]\prod_{j\neq
i}\binom{n_{j}}{k_{j}}.$

##  1 Introduction

Let $[n]=\\{1,2,\dots,n\\}$ and $\binom{[n]}{k}$ be the collection of all its
$k$-subsets. For a $k$-graph $\mathcal{F}\subset{[n]\choose k}$, the matching
number of $\mathcal{F}$, denote by $\nu(\mathcal{F})$, is the maximum number
of pairwise disjoint members of $\mathcal{F}$. Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\binom{[n]}{k}$.
We say that $\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ contain a
rainbow matching if there exist $s$ pairwise disjoint sets
$F_{1}\in\mathcal{F}_{1},F_{2}\in\mathcal{F}_{2},\dots,F_{s}\in\mathcal{F}_{s}$.

One of the most important open problems in extremal set theory is to determine
the maximum of $|\mathcal{F}|$ subject to $\nu(\mathcal{F})\leq s$, which is
known as the celebrated Erdős matching conjecture.

######  Conjecture 1.1 (Erdős Matching Conjecture [5]).

Let $n\geq(s+1)k$ and $\mathcal{F}\subseteq\binom{[n]}{k}$. If
$\nu(\mathcal{F})\leq s$, then

$\displaystyle|\mathcal{F}|\leq\max\left\\{\binom{k(s+1)-1}{k},\binom{n}{k}-\binom{n-s}{k}\right\\}.$
(1.1)

The two simple constructions showing that (1.1) is best possible (if true) are

$\mathcal{E}(n,k,s)=\left\\{E\in{[n]\choose k}\colon
E\cap[s]\neq\emptyset\right\\}\text{ and }{[(s+1)k-1]\choose k}.$

The case $s=1$ is the classical Erdős-Ko-Rado Theorem [15]. Erdős and Gallai
[6] proved (1.1) for $k=2$. The $k=3$ case is settled in [10]. For general
$k$, Erdős proved that (1.1) is true and up to isomorphic $\mathcal{E}(n,k,s)$
is the only optimal family provided that $n>n_{0}(k,s)$. The bounds for
$n_{0}(k,s)$ were subsequently improved by Bollobás, Daykin and Erdős [3],
Huang, Loh and Sudakov [14]. The current best bounds establish (1.1) for
$n>(2s+1)k$ ([9]) and for $s>s_{0}$, $n>\frac{5}{3}sk$ ([11]).

A rainbow version of Erdős matching conjecture was proposed by Aharoni,
Howardand [1] and independently Huang, Loh, Sudakov [14].

######  Conjecture 1.2 ([1, 14]).

Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\binom{[n]}{k}$.
If

$\displaystyle|\mathcal{F}_{i}|>\max\left\\{\binom{ks-1}{k},\binom{n}{k}-\binom{n-s+1}{k}\right\\},$
(1.2)

for all $1\leq i\leq s$, then
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ contain a rainbow
matching.

Using a junta method, Keller and Lifshitz [16] showed the validity of (1.2)
for $n>f(s)k$, where $f(s)$ is an unspecified and a very quickly growing
function of $s$. In [12], Frankl and Kupavskii improved the bound to
$12sk(2+\log s)$. By using the absorbing method, Lu, Wang and Yu [19] proved
(1.2) for $n\geq 2k(s+1)$ and $s>s_{0}(k)$. By applying the concentration
inequality for random matchings developed in [11], Kupavskii[17] proved (1.2)
for $n\geq 3e(s+1)k$ and $s>10^{7}$.

Let $n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$n_{1}/k_{1}\leq\dots\leq n_{\ell}/k_{\ell}$ and let $V_{1},\dots,V_{\ell}$ be
pairwise disjoint sets with $|V_{i}|=n_{i}$. Define the direct product
$\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ as the collection of all subsets $F$
of $\cup_{i=1}^{\ell}V_{i}$ with $|F\cap V_{i}|=k_{i}$ for $i=1,\dots,\ell$.
By the algebraic method, Frankl[8] proved an Erdős-Ko-Rado theorem for direct
products as follows:

######  Theorem 1.1 ([8]).

Suppose that $\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ is
intersecting and $2\leq n_{1}/k_{1}\leq\dots\leq n_{\ell}/k_{\ell}$. Then

$|\mathcal{F}|\leq\frac{k_{1}}{n_{1}}\prod_{i=1}^{\ell}\binom{n_{i}}{k_{i}}.$

In this paper, we mainly consider a direct product version of Erdős matching
conjecture. We determine the maximum number of edges in a subfamily of the
direct product with matching number at most $s$ for each $n_{i}$ sufficiently
large.

######  Theorem 1.2.

Let $\ell,s,n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$n_{i}\geq 4\ell^{2}k_{i}^{2}s$ for $i=1,\dots,\ell$. Let
$\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ with
$|V_{i}|=n_{i}$. If $\nu(\mathcal{F})\leq s$, then

$\displaystyle|\mathcal{F}|\leq\max_{1\leq
i\leq\ell}\left[\binom{n_{i}}{k_{i}}-\binom{n_{i}-s}{k_{i}}\right]\prod_{j\neq
i\atop 1\leq j\leq\ell}\binom{n_{j}}{k_{j}}.$ (1.3)

Let $S_{i}$ be an $s$-subset of $V_{i}$. Set
$\vec{n}=(n_{1},n_{2},\dots,n_{\ell})$ and
$\vec{k}=(k_{1},k_{2},\dots,k_{\ell})$. Define

$\mathcal{E}_{i}(\vec{\mathstrut n},\vec{\mathstrut
k},s)=\left\\{E\in\bigsqcup_{j=1}^{\ell}\binom{V_{j}}{k_{j}}\colon E\cap
S_{i}\neq\emptyset\right\\}.$

The constructions $\mathcal{E}_{i}(\vec{\mathstrut n},\vec{\mathstrut k},s)$
show that (1.3) is best possible.

By the random matching technique developed by Frankl and Kupavskii[11], we
obtain a condition on the number of edges for a family of direct products to
contain a rainbow matching for each $n_{i}$ sufficiently large.

######  Theorem 1.3.

Let $\ell,s,n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$n_{i}\geq 8\ell^{2}k_{i}^{2}s$ for $i=1,\dots,\ell$. Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$
with $|V_{i}|=n_{i}$. If
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ are rainbow matching
free, then there exists $1\leq t\leq s$ such that

$\displaystyle|\mathcal{F}_{t}|\leq\max_{1\leq
i\leq\ell}\left[\binom{n_{i}}{k_{i}}-\binom{n_{i}-s+1}{k_{i}}\right]\prod_{j\neq
i\atop 1\leq j\leq\ell}\binom{n_{j}}{k_{j}}.$ (1.4)

The constructions
$\mathcal{F}_{1}=\mathcal{F}_{2}=\dots=\mathcal{F}_{s}=\mathcal{E}_{i}(\vec{\mathstrut
n},\vec{\mathstrut k},s)$ show that (1.4) is best possible.

##  2 Extremal problem for matchings on direct products

Frankl and the first author [13] proved an upper bound on the sum of sizes of
overlapping families. In this section, by a probabilistic argument we transfer
it to an upper bound on the size of
$\mathcal{F}\subset\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ with matching
number at most $s$. By using this upper bound, we prove Theorem 1.2.

Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{m}\subset\binom{[n]}{k}$
and $m\geq s+1$. If one cannot choose pairwise disjoint edges from $s+1$
distinct families of $\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{m}$,
we say these families are $s$-overlapping.

######  Lemma 2.1 ([13]).

Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{m}\subset\binom{[n]}{k}$
be $s$-overlapping families with $n\geq(s+1)k$ and $m\geq s+1$. Then

$\sum_{i=1}^{m}|\mathcal{F}_{i}|\leq\max\left\\{s\binom{n}{k},ms\binom{n-1}{k-1}\right\\}.$

By Lemma 2.1, we prove the following lemma via a probabilistic argument.

######  Lemma 2.2.

Let $\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ with
$|V_{i}|=n_{i}$ for $i=1,\dots,\ell$ and $s+1\leq n_{1}/k_{1}\leq\dots\leq
n_{\ell}/k_{\ell}$. If $\nu(\mathcal{F})\leq s$, then

$|\mathcal{F}|\leq\frac{(s+1)k_{1}}{n_{1}}\prod_{i=1}^{\ell}\binom{n_{i}}{k_{i}}.$

###### Proof.

Let $m=\lfloor\frac{n_{2}}{k_{2}}\rfloor$ and let $B_{1},B_{2},\dots,B_{m}$ be
an $m$-matching chosen from $\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$
uniformly at random. Define

$\mathcal{F}(B_{i})=\left\\{A\in\binom{V_{1}}{k_{1}}\colon A\cup
B_{i}\in\mathcal{F}\right\\}$

for $i=1,\dots,m$. Since $\nu(\mathcal{F})\leq s$,
$\mathcal{F}(B_{1}),\dots,\mathcal{F}(B_{m})$ are $s$-overlapping. Note that
$m\geq s+1$. By Lemma 2.1, we have

$\sum_{i=1}^{m}|\mathcal{F}(B_{i})|\leq\max\left\\{s\binom{n_{1}}{k_{1}},ms\binom{n_{1}-1}{k_{1}-1}\right\\}.$

$n_{1}/k_{1}\leq n_{2}/k_{2}$ implies that $n_{1}/k_{1}\leq\lfloor
n_{2}/k_{2}\rfloor+1=m+1$. It follows that

$\displaystyle\sum_{i=1}^{m}|\mathcal{F}(B_{i})|\leq(m+1)s\binom{n_{1}-1}{k_{1}-1}.$
(2.1)

Taking the expectation on both sides of $\eqref{eq-1}$, we obtain that

$\displaystyle\sum_{i=1}^{m}\mathcal{\mathbb{E}}|\mathcal{F}(B_{i})|\leq(m+1)s\binom{n_{1}-1}{k_{1}-1}.$
(2.2)

Since $B_{1},B_{2},\dots,B_{m}$ are chosen from
$\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$ uniformly, we have

$\displaystyle\mathcal{\mathbb{E}}|\mathcal{F}(B_{i})|=\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}|\mathcal{F}(B)|\cdot\frac{1}{\prod_{i=2}^{\ell}\binom{n_{i}}{k_{i}}}=\frac{|\mathcal{F}|}{\prod_{i=2}^{\ell}\binom{n_{i}}{k_{i}}}.$
(2.3)

By (2.2) and (2.3), we have

$|\mathcal{F}|\leq\left(1+\frac{1}{m}\right)s\binom{n_{1}-1}{k_{1}-1}\prod_{i=2}^{\ell}\binom{n_{i}}{k_{i}}.$

Since $m=\lfloor\frac{n_{2}}{k_{2}}\rfloor>s$, it follows that

$\left(1+\frac{1}{m}\right)s<s+1$

and the lemma follows.

The following operation, called shifting, was invented by Erdős, Ko and Rado
[4] and further developed by Frankl [7]. Let $1\leq i<j\leq n$,
$\mathcal{F}\subset{[n]\choose k}$. Define

$S_{ij}(\mathcal{F})=\\{S_{ij}(F)\colon F\in\mathcal{F}\\},$

where

$S_{ij}(F)=\left\\{\begin{array}[]{ll}(F\setminus\\{j\\})\cup\\{i\\},&j\in
F,i\notin F\text{ and
}(F\setminus\\{j\\})\cup\\{i\\}\notin\mathcal{F};\\\\[5.0pt]
F,&\hbox{otherwise.}\end{array}\right.$

It is well known (cf. [7]) that shifting does not increase the matching
number.

Let us recall some properties of the shifting operator. Let
$\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ with
$V_{i}=\\{v_{i,1},v_{i,2},\dots,v_{i,n_{i}}\\}$ for $i=1,\dots,\ell$. Define a
partial order $\prec$ on $\cup_{i=1}^{\ell}V_{i}$ such that

$v_{i,1}\prec v_{i,2}\prec\dots\prec v_{i,n_{i}}$

for each $i$ and vertices from different parts are incomparable. A family
$\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ is called
shifted if $S_{ab}(\mathcal{F})=\mathcal{F}$ for all
$a,b\in\cup_{i=1}^{\ell}V_{i}$ with $a\prec b$. Frankl[7] proved that repeated
application of shifting to any family eventually produces a shifted family.

Let $k=k_{1}+k_{2}+\dots+k_{\ell}$. For two different edges
$A=\\{a_{1},a_{2},\dots,a_{k}\\}$ and $B=\\{b_{1},b_{2},\dots,b_{k}\\}$ in
$\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$, define $A\prec B$ iff there exists
a permutation $\sigma_{1}\sigma_{2}\dots\sigma_{k}$ of $[k]$ such that
$a_{j}\prec b_{\sigma_{j}}$ or $a_{j}=b_{\sigma_{j}}$ for $j=1,\dots,k$. It is
shown in [7] that if $\mathcal{F}$ is a shifted family, $A\prec B$ and
$B\in\mathcal{F}$ then $A\in\mathcal{F}$ as well.

In the proof of the following lemma, we need the following inequality, which
were already used in [3]. For $n\geq(2s+1)k$,

$\displaystyle\binom{n-s}{k}/\binom{n}{k}\geq\left(1-\frac{s}{n-k}\right)^{k}\geq
1-\frac{ks}{n-k}\geq\frac{1}{2}.$ (2.4)

######  Lemma 2.3.

Let $\ell,s,n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$n_{i}\geq 4\ell^{2}k_{i}^{2}s$ for $i=1,\dots,\ell$. If
$\mathcal{F}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$ has matching
number at most $s$, then

$|\mathcal{F}|\leq\prod_{i=1}^{\ell}\binom{n_{i}}{k_{i}}-\min_{x_{1}+\dots+x_{\ell}=s}\prod_{i=1}^{\ell}\binom{n_{i}-x_{i}}{k_{i}}$

###### Proof.

Without loss of generality, we may assume that $n_{1}/k_{1}\leq\dots\leq
n_{\ell}/k_{\ell}$ and $\mathcal{F}$ is shifted. We prove the lemma by
induction on $s$. The case $s=1$ is verified in Theorem 1.1. Assume that the
lemma holds for the case $s-1$. Let $V_{i}=\\{v_{i,j}\colon j\in[n_{i}]\\}$.
For each $x\in\cup_{i=1}^{\ell}V_{i}$, define

$\mathcal{F}(x)=\\{F\setminus\\{x\\}\colon x\in F\in\mathcal{F}\\}\mbox{ and
}\mathcal{F}(\overline{x})=\\{F\colon x\notin F\in\mathcal{F}\\}.$

We distinguish two cases.

Case 1. $\nu(\mathcal{F}(\overline{v_{i,1}}))\leq s-1$ for some $i\in[\ell]$.

By the induction hypothesis, we have

$|\mathcal{F}(\overline{v_{i,1}})|\leq\binom{n_{i}-1}{k_{i}}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}.$

Then,

$\displaystyle|\mathcal{F}|$
$\displaystyle=|\mathcal{F}(\overline{v_{i,1}})|+|\mathcal{F}({v_{i,1}})|$
$\displaystyle\leq\binom{n_{i}-1}{k_{i}}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}+\binom{n_{i}-1}{k_{i}-1}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}$
$\displaystyle=\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}$
$\displaystyle\leq\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}-\min_{x_{1}+x_{2}+\dots+x_{\ell}=s}\prod_{j=1}^{\ell}\binom{n_{j}-x_{j}}{k_{j}}$

and the lemma holds.

Case 2. $\nu(\mathcal{F}(\overline{v_{i,1}}))=s$ for all $i\in[\ell]$.

Let $M$ be an $s$-matching in $\mathcal{F}(\overline{v_{i,1}})$ and let $U$ be
the set of vertices covered by $M$. Since $\nu(\mathcal{F})\leq s$, each edge
in $\mathcal{F}(v_{i,1})$ intersects $U$. It follows that

$\displaystyle|\mathcal{F}({v_{i,1}})|\leq\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}-\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}-sk_{j}}{k_{j}^{\prime}},$

where $n_{j}^{\prime}=n_{j},k_{j}^{\prime}=k_{j}$ for all $j\neq i$ and
$n_{i}^{\prime}=n_{i}-1,k_{i}^{\prime}=k_{i}-1$. Then, we have

$\displaystyle|\mathcal{F}({v_{i,1}})|$
$\displaystyle\leq\sum_{p=1}^{\ell}\left[\binom{n_{p}^{\prime}}{k_{p}^{\prime}}-\binom{n_{p}^{\prime}-sk_{p}}{k_{p}^{\prime}}\right]\prod_{j\leq
p-1}\binom{n_{j}^{\prime}-sk_{j}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}sk_{p}\binom{n_{p}^{\prime}-1}{k_{p}^{\prime}-1}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}-sk_{j}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}sk_{p}\binom{n_{p}^{\prime}-1}{k_{p}^{\prime}-1}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}\frac{sk_{p}k_{p}^{\prime}}{n_{p}^{\prime}}\binom{n_{p}^{\prime}}{k_{p}^{\prime}}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle=$
$\displaystyle\left(\sum_{p=1}^{\ell}\frac{sk_{p}k_{p}^{\prime}}{n_{p}^{\prime}}\right)\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}.$

Note that
$\frac{k_{i}^{\prime}}{n_{i}^{\prime}}=\frac{k_{i}-1}{n_{i}-1}\leq\frac{k_{i}}{n_{i}}$
and
$\binom{n_{i}^{\prime}}{k_{i}^{\prime}}=\frac{k_{i}}{n_{i}}\binom{n_{i}}{k_{i}}$.
It follows that

$\displaystyle|\mathcal{F}({v_{i,1}})|\leq\frac{k_{i}}{n_{i}}\left(\sum_{p=1}^{\ell}\frac{sk_{p}^{2}}{n_{p}}\right)\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}.$
(2.5)

Let $M^{\prime}$ be an $s$-matching in $\mathcal{F}$ and let $U^{\prime}$ be
the set of vertices covered by $M^{\prime}$. Since $\mathcal{F}$ is shifted,
we may assume that

$U^{\prime}=\bigcup_{i=1}^{\ell}\\{v_{i,1},\dots,v_{i,sk_{i}}\\}.$

For each $i\in[\ell]$ and $j\in[sk_{i}]$, define

$\mathcal{F}[v_{i,j}]=\left\\{T\in\bigsqcup_{p=1}^{\ell}\binom{V_{p}^{\prime}}{k_{p}^{\prime}}\colon
T\cup\\{v_{i,j}\\}\in\mathcal{F}\right\\},$

where $V_{p}^{\prime}=V_{p},\ k_{p}^{\prime}=k_{p}$ for $p\neq i$ and
$V_{i}^{\prime}=V_{i}\setminus\\{v_{i,1},\dots,v_{i,j}\\},\
k_{i}^{\prime}=k_{i}-1$. By shiftedness, we have

$\displaystyle\mathcal{F}[v_{i,1}]\supseteq\mathcal{F}[v_{i,2}]\supseteq\dots\supseteq\mathcal{F}[v_{i,sk_{i}}]$
(2.6)

for $i=1,2,\dots,\ell$.

We claim that $\nu(\mathcal{F}[v_{i,s+1}])\leq s$ for $i=1,2,\dots,\ell$.
Otherwise, let $E_{1},E_{2},\dots,E_{s+1}$ be a matching of size $s+1$ in
$\mathcal{F}[v_{i,s+1}]$. By (2.6),
$E_{1}\cup\\{v_{i,1}\\},E_{2}\cup\\{v_{i,2}\\},\dots,E_{s+1}\cup\\{v_{i,s+1}\\}$
is a matching of size $s+1$ in $\mathcal{F}$, a contradiction. Thus
$\nu(\mathcal{F}[v_{i,s+1}])\leq s$ for $i=1,2,\dots,\ell$. Note that
$n_{i}\geq(s+1)k_{i}$ implies that
$\frac{n_{i}-s-1}{k_{i}-1}\geq\frac{n_{i}}{k_{i}}\geq\frac{n_{1}}{k_{1}}$. By
Lemma 2.2, we get for each $i$

$\displaystyle|\mathcal{F}[v_{i,s+1}]|\leq\frac{(s+1)k_{1}}{n_{1}}\binom{n_{i}-s-1}{k_{i}-1}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}\leq\frac{(s+1)k_{1}k_{i}}{n_{1}n_{i}}\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}.$
(2.7)

Since $M^{\prime}$ is a largest matching in $\mathcal{F}$, $U^{\prime}$ is a
vertex cover of $\mathcal{F}$. By (2.6), it follows that

$\displaystyle|\mathcal{F}|\leq\sum_{i=1}^{\ell}\sum_{j=1}^{sk_{i}}|\mathcal{F}[v_{i,j}]|\leq\sum_{i=1}^{\ell}\left(s|\mathcal{F}[v_{i,1}]|+(sk_{i}-s)|\mathcal{F}[v_{i,s+1}]|\right).$
(2.8)

Substitute (2.5) and (2.7) into (2.8), we arrive at

$\displaystyle|\mathcal{F}|$
$\displaystyle\leq\sum_{i=1}^{\ell}\left(s\frac{k_{i}}{n_{i}}\left(\sum_{p=1}^{\ell}\frac{sk_{p}^{2}}{n_{p}}\right)\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}+s(k_{i}-1)\frac{(s+1)k_{1}k_{i}}{n_{1}n_{i}}\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}\right)$
$\displaystyle\leq
s\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}\sum_{i=1}^{\ell}\left(\frac{k_{i}}{n_{i}}\cdot\sum_{p=1}^{\ell}\frac{sk_{p}^{2}}{n_{p}}+\frac{2sk_{1}k_{i}^{2}}{n_{1}n_{i}}\right).$

Since $n_{i}\geq 4\ell^{2}k_{i}^{2}s$, we have

$\sum_{p=1}^{\ell}\frac{sk_{p}^{2}}{n_{p}}\leq\frac{1}{4\ell},\mbox{ and
}\frac{2sk_{i}^{2}}{n_{i}}\leq\frac{1}{2\ell^{2}}\leq\frac{1}{4\ell}.$

Moreover, $\frac{k_{i}}{n_{i}}\leq\frac{k_{1}}{n_{1}}$. Hence, by inequality
(2.4) we obtain that

$|\mathcal{F}|\leq\frac{s}{2}\binom{n_{1}-1}{k_{1}-1}\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}}\leq
s\binom{n_{1}-s}{k_{1}-1}\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}}\leq\left(\binom{n_{1}}{k_{1}}-\binom{n_{1}-s}{k_{1}}\right)\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}}$

and this completes the proof.

###### Proof of Theorem 1.2..

By Lemma 2.3, we are left to show that

$\min_{x_{1}+\dots+x_{\ell}=s}\prod_{i=1}^{\ell}\binom{n_{i}-x_{i}}{k_{i}}=\min_{1\leq
i\leq\ell}\binom{n_{i}-s}{k_{i}}\prod_{j\neq i}\binom{n_{j}}{k_{j}}.$

Set

$f(x)=\binom{n_{i}-x}{k_{i}}\binom{n_{j}-c+x}{k_{j}}.$

Computing its derivative, we have

$f^{\prime}(x)=\binom{n_{i}-x}{k_{i}}\binom{n_{j}-c+x}{k_{j}}\left[\sum_{q=0}^{k_{j}-1}\frac{1}{n_{j}-c+x-q}-\sum_{p=0}^{k_{i}-1}\frac{1}{n_{i}-x-p}\right].$

Set

$g(x)=\sum_{q=0}^{k_{j}-1}\frac{1}{n_{j}-c+x-q}-\sum_{p=0}^{k_{i}-1}\frac{1}{n_{i}-x-p}.$

It is easy to see that $g(x)$ is a decreasing function in the range
$[k_{j}-n_{j}+c,n_{i}-k_{i}]$. Moreover,

$g(k_{j}-n_{j}+c)=\sum_{q=0}^{k_{j}-1}\frac{1}{k_{j}-q}-\sum_{p=0}^{k_{i}-1}\frac{1}{n_{i}-p+n_{j}-k_{j}-c}>1-\frac{k_{i}}{n_{i}-k_{i}}>0$

and

$g(n_{i}-k_{i})=\sum_{q=0}^{k_{j}-1}\frac{1}{n_{j}-c+n_{i}-k_{i}-q}-\sum_{p=0}^{k_{i}-1}\frac{1}{k_{i}-p}<\frac{k_{j}}{n_{j}-k_{j}}-1<0.$

Let $x_{0}$ be the unique zero of $g(x)$ in the range
$[k_{j}-n_{j}+c,n_{i}-k_{i}]$. It follows that $f(x)$ is increasing in the
range $[k_{j}-n_{j},x_{0}]$ and decreasing in the range $[x_{0},n_{i}-k_{i}]$.
Then we have

$\min_{0\leq x\leq
c}f(x)=\min\left\\{\binom{n_{i}-c}{k_{i}}\binom{n_{j}}{k_{j}},\binom{n_{i}}{k_{i}}\binom{n_{j}-c}{k_{j}}\right\\}.$

Thus,

$\min_{x_{1}+\dots+x_{\ell}=s}\prod_{i=1}^{\ell}\binom{n_{i}-x_{i}}{k_{i}}=\min_{1\leq
i\leq\ell}\binom{n_{i}-s}{k_{i}}\prod_{j\neq i}\binom{n_{j}}{k_{j}}$

and the theorem follows.

##  3 Extremal problem for rainbow matchings on direct products

Frankl and Kupavskii [11] proved a concentration inequality for the
intersections of a $k$-uniform hypergraph and a random matching. In this
section, by the concentration property of the bipartite graph defined on two
random matchings, we establish a condition on the number of edges for a family
of direct products to contain a rainbow matching.

Aharoni and Howard [1] provided a tight condition on the number of edges for a
family of bipartite graphs to contain a rainbow matching.

######  Lemma 3.1 ([1]).

Let $G_{1},G_{2},\dots,G_{s}$ be bipartite graphs with the same partite sets
$L$ and $R$ such that $|L|=|R|=m\geq s$. If $e(G_{i})>(s-1)m$ for every
$i\in[s]$, then $G_{1},G_{2},\dots,G_{s}$ contain a rainbow matching.

We recall that the Kneser graph $KG(n,k)$ is the graph on the vertex set
$\binom{[n]}{k}$ and with the edge set formed by pairs of disjoint sets.
Lovasz [18] determined all the eigenvalues of the adjacent matrix of
$KG(n,k)$.

######  Lemma 3.2 ([18]).

The eigenvalues of the adjacent matrix of $KG(n,k)$ are
$(-1)^{i}\binom{n-k-1}{k-i}$ with multiplicity $\binom{n}{i}-\binom{n}{i-1}$,
$i=0,1,\dots,k$. (Here $\binom{n}{-1}=0$.)

We also need the following result due to Alon and Chung [2].

######  Lemma 3.3 ([2]).

Let $G$ be a $d$-regular graph on $n$ vertices and $A$ be its adjacent matrix.
Let $d=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-d$ be the
eigenvalue of $A$ and let $\lambda=\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$. For
$S\subseteq V(G)$ with $|S|=\alpha n$, we have

$\left|e(G[S])-\frac{d}{n}\cdot\frac{(\alpha
n)^{2}}{2}\right|\leq\frac{1}{2}\lambda\alpha(1-\alpha)n.$

By considering the bipartite graph defined on two random matchings, we prove
the following lemma, which is key to the proof of Theorem 1.3.

######  Lemma 3.4.

Let $\ell,s,n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$3s\leq n_{1}/k_{1}\leq\dots\leq n_{\ell}/k_{\ell}$. Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$
with $|V_{i}|=n_{i}$ for $i=1,\dots,\ell$. If
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ are rainbow matching
free, then there exists $1\leq t\leq s$ such that

$|\mathcal{F}_{t}|<\frac{6sk_{1}}{n_{1}}\prod_{1\leq
j\leq\ell}\binom{n_{j}}{k_{j}}.$

###### Proof.

Suppose that

$|\mathcal{F}_{t}|=\frac{6sk_{1}}{n_{1}}\prod_{1\leq
j\leq\ell}\binom{n_{j}}{k_{j}}$

for all $1\leq t\leq s$. Set $m=\lfloor n_{1}/k_{1}\rfloor$. Let
$\mathcal{A}=\\{A_{1},\dots,A_{m}\\}$ be an $m$-matching chosen from
$\binom{V_{1}}{k_{1}}$ uniformly at random and
$\mathcal{B}=\\{B_{1},\dots,B_{m}\\}$ be an $m$-matching chosen from
$\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$ uniformly at random. For each
$t=1,\dots,s$, we construct a bipartite graph $G_{t}$ with partite sets
$\mathcal{A}$, $\mathcal{B}$ where we have an edge $(A_{i},B_{j})$ iff
$A_{i}\cup B_{j}\in\mathcal{F}_{t}$. Note that a rainbow matching in
$G_{1},G_{2},\dots,G_{s}$ gives a rainbow matching in
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$. Thus, by Lemma 3.1
and the union bound, it suffices to show that

$\displaystyle\Pr(e(G_{t})\leq(s-1)m)<\frac{1}{s}$

for each $1\leq t\leq s$. Let $X=e(G_{t})$ and $X_{ij}$ be the indicator
function of the event that $A_{i}\cup B_{j}\in\mathcal{F}_{t}$. Clearly, we
have

$X=\sum_{1\leq i,j\leq m}X_{ij}.$

Set $\alpha=|\mathcal{F}_{t}|/\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}$. Take
expectation on both sides, we obtain that

$\mathcal{\mathbb{E}}(X)=\sum_{1\leq i,j\leq m}\Pr[A_{i}\cup
B_{j}\in\mathcal{F}_{t}]=\sum_{1\leq i,j\leq
m}\frac{|\mathcal{F}_{t}|}{\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}}=\alpha
m^{2}.$

Since $n_{1}/k_{1}\geq 3s$, we have

$\displaystyle\alpha
m=\frac{6sk_{1}}{n_{1}}\cdot\left\lfloor\frac{n_{1}}{k_{1}}\right\rfloor\geq\frac{6sk_{1}}{n_{1}}\cdot\frac{n_{1}-k_{1}}{k_{1}}\geq
6s\left(1-\frac{k_{1}}{n_{1}}\right)\geq 6s-2.$ (3.1)

By the Chebyshev inequality, it follows that

$\displaystyle\Pr(X\leq(s-1)m)\leq\Pr\left(X\leq\frac{\mathcal{\mathbb{E}}(X)}{6}\right)\leq\Pr\left(|X-\mathcal{\mathbb{E}}(X)|\geq\frac{5}{6}\mathcal{\mathbb{E}}(X)\right)\leq\frac{36}{25}\cdot\frac{\mathrm{Var}(X)}{\alpha^{2}m^{4}}.$
(3.2)

Now we need to give an upper bound for $\mathrm{Var}(X)$. For $1\leq
i,i^{\prime},j,j^{\prime}\leq m$, define

$\theta(i,j,i^{\prime},j^{\prime})=\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)-\alpha^{2}.$

Then,

$\displaystyle\mathrm{Var}(X)$
$\displaystyle=\mathcal{\mathbb{E}}(X^{2})-\mathcal{\mathbb{E}}(X)^{2}$
$\displaystyle=\sum_{i,j,i^{\prime},j^{\prime}\in[m]}\left(\mathcal{\mathbb{E}}[X_{ij}X_{i^{\prime}j^{\prime}}]-\mathcal{\mathbb{E}}[X_{ij}]\mathcal{\mathbb{E}}[X_{i^{\prime}j^{\prime}}]\right)$
$\displaystyle=\sum_{i,j,i^{\prime},j^{\prime}\in[m]}\left(\Pr\left(A_{i}\cup
B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)-\Pr\left(A_{i}\cup
B_{j}\in\mathcal{F}_{t}\right)\Pr\left(A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)\right)$
$\displaystyle=\sum_{i,j,i^{\prime},j^{\prime}\in[m]}\theta(i,j,i^{\prime},j^{\prime}).$
(3.3)

We derive upper bounds on $\theta(i,j,i^{\prime},j^{\prime})$ for
$i,j,i^{\prime},j^{\prime}\in[m]$ by distinguishing four cases.

Case 1. $i\neq i^{\prime}$ and $j\neq j^{\prime}$.

Let $H$ be a graph on the vertex set $\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$
and with the edge set formed by pairs of disjoint sets in
$\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$. Let $\lambda$ be the second largest
absolute eigenvalue of adjacent matrix of $H$. Frankl [8] observed that the
adjacency matrix of $H$ is the Kronecker product of the adjacency matrices of
the Kneser graphs. By Lemma 3.2, it follows that

$\lambda=\frac{k_{1}}{n_{1}-k_{1}}\prod_{1\leq
p\leq\ell}\binom{n_{p}-k_{p}}{k_{p}}.$

Since $i\neq i^{\prime}$ and $j\neq j^{\prime}$, we have $(A_{i}\cup
B_{j})\cap(A_{i^{\prime}}\cup B_{j^{\prime}})=\emptyset$. Note that
$A_{1},\dots,A_{m}$ and $B_{1},\dots,B_{m}$ are chosen uniformly at random.
The probability that $A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}$ equals to the probability that a uniform
chosen edge from $E(H)$ is an edge of the induce subgraph
$H[\mathcal{F}_{t}]$, that is,

$\displaystyle\Pr\Big{(}A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\Big{)}=\frac{e(H[\mathcal{F}_{t}])}{e(H)}.$

Let $D$ be the degree of $H$ and $N$ be the number of vertices of $H$. It is
easy to see that $D=\prod_{1\leq p\leq\ell}\binom{n_{p}-k_{p}}{k_{p}}$ and
$N=\prod_{1\leq p\leq\ell}\binom{n_{p}}{k_{p}}$. Since $H$ is $D$-regular, we
have $e(H)=\frac{DN}{2}$. By Lemma 3.3, we have

$\displaystyle\theta(i,j,i^{\prime},j^{\prime})\leq\left|\frac{e(H[\mathcal{F}_{t}])}{e(H)}-\alpha^{2}\right|\leq\frac{\lambda}{D}\alpha(1-\alpha)\leq\frac{k_{1}}{n_{1}-k_{1}}\alpha.$
(3.4)

Case 2. $i\neq i^{\prime}$ and $j=j^{\prime}$.

For $B\in\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$, define
$\mathcal{F}_{t}(B)=\left\\{K\in\binom{V_{1}}{k_{1}}\colon K\cup
B\in\mathcal{F}_{t}\right\\}$. Let $H$ be the Kneser graph on the vertex set
$\binom{V_{1}}{k_{1}}$. Since $i\neq i^{\prime}$ and $j=j^{\prime}$, the event
that $A_{i}\cup B_{j},A_{i^{\prime}}\cup B_{j^{\prime}}\in\mathcal{F}_{t}$ is
equivalent to the event that a uniform chosen edge of $H$ is an edge in
$H[\mathcal{F}_{t}(B_{j})]$. Thus,

$\displaystyle\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)$
$\displaystyle=\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}\Pr\left(A_{i},A_{i}^{\prime}\in\mathcal{F}_{t}(B)|B_{j}=B\right)\Pr\left(B_{j}=B\right)$
$\displaystyle=\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}\frac{e(H[\mathcal{F}_{t}(B)])}{e(H)}\cdot\Pr\left(B_{j}=B\right).$
(3.5)

Set $\alpha(B)=|\mathcal{F}_{t}(B)|/|\binom{n_{1}}{k_{1}}|$. Let $D$ be the
degree of $H$ and $N$ be the number of vertices in $H$. Clearly,
$D=\binom{n_{1}-k_{1}}{k_{1}}\mbox{ and }N=\binom{n_{1}}{k_{1}}$. Let
$\lambda$ be the second largest absolute eigenvalue of adjacent matrix of $H$.
By Lemma 3.2, we have $\lambda=\binom{n_{1}-k_{1}-1}{k_{1}-1}$. By lemma 3.3,
it follows that

$\displaystyle\left|\frac{e(H[\mathcal{F}_{t}(B)])}{e(H)}-\alpha^{2}(B)\right|\leq\frac{\lambda}{D}\alpha(B)(1-\alpha(B))\leq\alpha(B)(1-\alpha(B)).$
(3.6)

By (3) and (3.6), we obtain that

$\displaystyle\theta(i,j,i^{\prime},j^{\prime})$
$\displaystyle=\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)-\alpha^{2}$
$\displaystyle\leq\frac{1}{\prod_{2\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}\left(\alpha(B)(1-\alpha(B))+\alpha^{2}(B)\right)-\alpha^{2}$
$\displaystyle\leq\frac{1}{\prod_{2\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}\alpha(B)$
$\displaystyle\leq\frac{1}{\prod_{2\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}\frac{|\mathcal{F}_{t}(B)|}{\binom{n_{1}}{k_{1}}}$
$\displaystyle\leq\frac{1}{\prod_{1\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}\sum_{B\in\bigsqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}}|\mathcal{F}_{t}(B)|$
$\displaystyle\leq\frac{|\mathcal{F}_{t}|}{\prod_{1\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}$ $\displaystyle=\alpha$ (3.7)

Case 3. $i=i^{\prime}$ and $j\neq j^{\prime}$.

Similarly, let $H$ be a graph on the vertex set
$\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$ and with the edge set formed by
pairs of disjoint sets in $\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}$. Let
$\lambda$ be the second largest absolute eigenvalue of adjacent matrix of $H$.
Since the adjacency matrix of $H$ is the Kronecker product of the adjacency
matrices of the Kneser graphs. By Lemma 3.2, it follows that

$\lambda=\frac{k_{2}}{n_{2}-k_{2}}\prod_{2\leq
p\leq\ell}\binom{n_{p}-k_{p}}{k_{p}}.$

For each $A\in\binom{V_{1}}{k_{1}}$, define
$\mathcal{F}_{t}(A)=\left\\{K\in\sqcup_{i=2}^{\ell}\binom{V_{i}}{k_{i}}\colon
A\cup K\in\mathcal{F}_{t}\right\\}$. Set
$\alpha(A)=|\mathcal{F}_{t}(A)|/\prod_{2\leq p\leq\ell}\binom{n_{p}}{k_{p}}$.
Let $D$ be the degree of $H$ and let $N$ be the number of vertices in $H$.
Clearly, $D=\prod_{2\leq p\leq\ell}\binom{n_{p}-k_{p}}{k_{p}}$ and
$N=\prod_{2\leq p\leq\ell}\binom{n_{p}}{k_{p}}$. Then,

$\displaystyle\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)=\sum_{A\in\binom{V_{1}}{k_{1}}}\frac{e(H[\mathcal{F}_{t}(A)])}{e(H)}\cdot\Pr\left(A_{i}=A\right).$

By Lemma 3.3, we have for $A\in\binom{V_{1}}{k_{1}}$

$\left|\frac{e(H[\mathcal{F}_{t}(A)])}{e(H)}-\alpha^{2}(A)\right|\leq\frac{\lambda}{D}\alpha(A)(1-\alpha(A))\leq\alpha(A)(1-\alpha(A)).$

Thus,

$\displaystyle\theta(i,j,i^{\prime},j^{\prime})$
$\displaystyle\leq\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)-\alpha^{2}$
$\displaystyle\leq\frac{1}{\binom{n_{1}}{k_{1}}}\sum_{A\in\binom{V_{1}}{k_{1}}}\left(\alpha(A)(1-\alpha(A))+\alpha^{2}(A)\right)$
$\displaystyle\leq\frac{1}{\binom{n_{1}}{k_{1}}}\cdot\sum_{A\in\binom{V_{1}}{k_{1}}}\alpha(A)$
$\displaystyle\leq\frac{1}{\binom{n_{1}}{k_{1}}}\sum_{A\in\binom{V_{1}}{k_{1}}}\frac{|\mathcal{F}_{t}(A)|}{\prod_{2\leq
p\leq\ell}\binom{n_{p}}{k_{p}}}$ $\displaystyle=\alpha.$ (3.8)

Case 4. $i=i^{\prime}$ and $j=j^{\prime}$.

In this case, $\Pr\left(A_{i}\cup B_{j},A_{i^{\prime}}\cup
B_{j^{\prime}}\in\mathcal{F}_{t}\right)=\Pr\left(A_{i}\cup
B_{j}\in\mathcal{F}_{t}\right)=\alpha$. Hence,

$\displaystyle\theta(i,j,i^{\prime},j^{\prime})=\alpha-\alpha^{2}\leq\alpha.$
(3.9)

Substitute (3.4), (3.7), (3.8) and (3.9) into (3), we have

$\mathrm{Var}(X)=\sum_{i,j,i^{\prime},j^{\prime}\in[m]}\theta(i,j,i^{\prime},j^{\prime})\leq\frac{k_{1}}{n_{1}-k_{1}}\alpha
m^{2}(m-1)^{2}+2\alpha m^{3}+\alpha m^{2}.$

Note that $m=\lfloor\frac{n_{1}}{k_{1}}\rfloor\leq\frac{n_{1}}{k_{1}}$ implies
$\frac{k_{1}}{n_{1}-k_{1}}\leq\frac{1}{m-1}$. It follows that

$\displaystyle\mathrm{Var}(X)\leq\frac{1}{m-1}\alpha m^{2}(m-1)^{2}+2\alpha
m^{3}+\alpha m^{2}=3\alpha m^{3}.$ (3.10)

Substitute (3.10) into (3.2), we arrive at

$\Pr(X\leq(s-1)m)\leq\frac{36}{25}\cdot\frac{3\alpha
m^{3}}{\alpha^{2}m^{4}}=\frac{36\cdot 3}{25\alpha m}.$

Moreover, (3.1) implies that $\alpha m\geq 6s-2\geq 5s$. Thus, we obtain that

$\Pr(X\leq(s-1)m)\leq\frac{36\times 3}{25\alpha m}\leq\frac{36\times
3}{25\times 5}\cdot\frac{1}{s}<\frac{1}{s},$

and the lemma follows.

The following lemma shows that the shifting operator preserves the rainbow
matching free property of a family of uniform hypergraphs, which is due to
Huang, Loh and Sudakov [14].

######  Lemma 3.5 (Huang-Loh-Sudakov [14]).

If the families $\mathcal{F}_{1},\dots,\mathcal{F}_{s}\subseteq\binom{[n]}{k}$
are rainbow matching free and $i,j\in[n]$ with $i<j$, then
$S_{ij}(\mathcal{F}_{1}),...,S_{ij}(\mathcal{F}_{s})$ are still rainbow
matching free.

######  Lemma 3.6.

Let $\ell,s,n_{1},\dots,n_{\ell},k_{1},\dots,k_{\ell}$ be integers with
$n_{i}\geq 8\ell^{2}k_{i}^{2}s$ for $i=1,\dots,\ell$. Let
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}\subseteq\sqcup_{i=1}^{\ell}\binom{V_{i}}{k_{i}}$
with $|V_{i}|=n_{i}$. If
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ are rainbow matching
free, then there exists $1\leq t\leq s$ such that

$|\mathcal{F}_{t}|\leq\prod_{i=1}^{\ell}\binom{n_{i}}{k_{i}}-\min_{x_{1}+\dots+x_{\ell}=s-1}\prod_{i=1}^{\ell}\binom{n_{i}-x_{i}}{k_{i}}.$

###### Proof.

Without loss of generality, we may assume that $n_{1}/k_{1}\leq
n_{2}/k_{2}\leq\dots\leq n_{\ell}/k_{\ell}$. By Lemma 3.5, we may assume that
$\mathcal{F}_{i}$ is shifted for all $i=1,\dots,s$. We prove the theorem by
induction on $s$. The case $s=1$ is trivial. Assume that the lemma holds for
the case $s-1$ and we have to show the lemma holds for the case $s$.

Let $V_{i}=\\{v_{i,j}\colon j\in[n_{i}]\\}$. For every
$x\in\cup_{i=1}^{\ell}V_{i}$ and $1\leq t\leq s$, define

$\mathcal{F}_{t}(x)=\\{F\setminus\\{x\\}\colon x\in
F\in\mathcal{F}_{t}\\}\mbox{ and }\mathcal{F}_{t}(\overline{x})=\\{F\colon
x\notin F\in\mathcal{F}_{t}\\}.$

We distinguish into two cases.

Case 1. There exist $r\in[s]$ and $i\in[\ell]$ such that
$\mathcal{F}_{1}(\overline{v_{i,1}}),\dots,\mathcal{F}_{r-1}(\overline{v_{i,1}}),\mathcal{F}_{r+1}(\overline{v_{i,1}}),\dots,$
$\mathcal{F}_{s}(\overline{v_{i,1}})$ are rainbow matching free.

By the induction hypothesis, there exists $t\in[s]\setminus\\{r\\}$ such that

$|\mathcal{F}_{t}(\overline{v_{i,1}})|\leq\binom{n_{i}-1}{k_{i}}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}.$

Then,

$\displaystyle|\mathcal{F}_{t}|$
$\displaystyle=|\mathcal{F}_{t}(\overline{v_{i,1}})|+|\mathcal{F}_{t}({v_{i,1}})|$
$\displaystyle\leq\binom{n_{i}-1}{k_{i}}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}+\binom{n_{i}-1}{k_{i}-1}\prod_{j\neq
i}\binom{n_{j}}{k_{j}}$
$\displaystyle=\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}-\min_{y_{1}+\dots+y_{\ell}=s-1}\binom{n_{i}-1-y_{i}}{k_{i}}\prod_{j\neq
i}\binom{n_{j}-y_{j}}{k_{j}}$
$\displaystyle\leq\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}-\min_{x_{1}+x_{2}+\dots+x_{\ell}=s}\prod_{j=1}^{\ell}\binom{n_{j}-x_{j}}{k_{j}}$

and the lemma holds.

Case 2.
$\mathcal{F}_{1}(\overline{v_{i,1}}),\dots,\mathcal{F}_{r-1}(\overline{v_{i,1}}),\mathcal{F}_{r+1}(\overline{v_{i,1}}),\dots,\mathcal{F}_{s}(\overline{v_{i,1}})$
contain a rainbow matching for all $r\in[s]$ and $i\in[\ell]$.

Let $M$ be a rainbow matching in
$\left\\{\mathcal{F}_{1}(\overline{v_{i,1}}),\dots,\mathcal{F}_{r-1}(\overline{v_{i,1}}),\mathcal{F}_{r+1}(\overline{v_{i,1}}),\dots,\mathcal{F}_{s}(\overline{v_{i,1}})\right\\}$
and let $U$ be the set of vertices covered by $M$. Since
$\mathcal{F}_{1},\mathcal{F}_{2},\dots,\mathcal{F}_{s}$ are rainbow matching
free, each edge of $\mathcal{F}_{r}(v_{i,1})$ intersects $U$. It follows that

$\displaystyle|\mathcal{F}_{r}({v_{i,1}})|\leq\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}-\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}-(s-1)k_{j}}{k_{j}^{\prime}},$

where $n_{j}^{\prime}=n_{j},k_{j}^{\prime}=k_{j}$ for all $j\neq i$ and
$n_{i}^{\prime}=n_{i}-1,k_{i}^{\prime}=k_{i}-1$. Then,

$\displaystyle|\mathcal{F}_{r}({v_{i,1}})|$
$\displaystyle\leq\sum_{p=1}^{\ell}\left[\binom{n_{p}^{\prime}}{k_{p}^{\prime}}-\binom{n_{p}^{\prime}-(s-1)k_{p}}{k_{p}^{\prime}}\right]\prod_{j\leq
p-1}\binom{n_{j}^{\prime}-(s-1)k_{j}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}(s-1)k_{p}\binom{n_{p}^{\prime}-1}{k_{p}^{\prime}-1}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}-(s-1)k_{j}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}(s-1)k_{p}\binom{n_{p}^{\prime}-1}{k_{p}^{\prime}-1}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle\leq$
$\displaystyle\sum_{p=1}^{\ell}\frac{(s-1)k_{p}k_{p}^{\prime}}{n_{p}^{\prime}}\binom{n_{p}^{\prime}}{k_{p}^{\prime}}\prod_{j\leq
p-1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}\prod_{j\geq
p+1}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}$ $\displaystyle=$
$\displaystyle\left(\sum_{p=1}^{\ell}\frac{(s-1)k_{p}k_{p}^{\prime}}{n_{p}^{\prime}}\right)\prod_{j=1}^{\ell}\binom{n_{j}^{\prime}}{k_{j}^{\prime}}.$

Note that
$\frac{k_{i}^{\prime}}{n_{i}^{\prime}}=\frac{k_{i}-1}{n_{i}-1}\leq\frac{k_{i}}{n_{i}}$
and
$\binom{n_{i}^{\prime}}{k_{i}^{\prime}}=\frac{k_{i}}{n_{i}}\binom{n_{i}}{k_{i}}$.
It follows that for every $i\in[\ell]$ and $r\in[s]$

$\displaystyle|\mathcal{F}_{r}({v_{i,1}})|\leq\frac{(s-1)k_{i}}{n_{i}}\left(\sum_{p=1}^{\ell}\frac{k_{p}^{2}}{n_{p}}\right)\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}.$
(3.11)

For $j\in[\ell]$, let $S_{j}=\\{v_{j,1},\dots,v_{j,s}\\}$ and let
$V_{j}^{\prime}=V_{j}\setminus S_{j}$. For every $r\in[s]$ and $i\in[\ell]$,
define

$\mathcal{F}_{r}[v_{i,s}]=\left\\{E\in\bigsqcup_{j=1}^{\ell}\binom{V_{j}^{\prime}}{k_{j}^{\prime}}\colon
E\cup\\{v_{i,s}\\}\in\mathcal{F}_{r}\right\\},$

where $k_{j}^{\prime}=k_{j}$ for all $j\neq i$ and $k_{i}^{\prime}=k_{i}-1$.
Define

$\mathcal{F}_{r}^{*}[v_{i,s}]=\left\\{E\cup\\{u\\}\colon
E\in\mathcal{F}_{r}[v_{i,s}],\ u\in V_{i}^{\prime}\setminus E\right\\}.$

Claim 1. There exists $t\in[s]$ such that for all $i\in[\ell]$

$\displaystyle|\mathcal{F}_{t}^{*}[v_{i,s}]|\leq\frac{6sk_{1}}{n_{1}}\prod_{1\leq
j\leq\ell}\binom{n_{j}-s}{k_{j}}.$ (3.12)

###### Proof.

Suppose to the contrary that for every $t\in[s]$ there is an $i_{t}\in[\ell]$
such that

$|\mathcal{F}_{t}^{*}[v_{i_{t},s}]|>\frac{6sk_{1}}{n_{1}}\prod_{1\leq
j\leq\ell}\binom{n_{j}-s}{k_{j}}.$

Note that

$\mathcal{F}_{t}^{*}[v_{i_{t},s}]\subseteq\bigsqcup_{j=1}^{\ell}\binom{V_{j}^{\prime}}{k_{j}}.$

By Lemma 3.4, we conclude that
$\mathcal{F}_{1}^{*}[v_{i_{1},s}],\dots,\mathcal{F}_{s}^{*}[v_{i_{s},s}]$
contain a rainbow matching. Let
$F_{1}\in\mathcal{F}_{1}^{*}[v_{i_{1},s}],\dots,F_{s}\in\mathcal{F}_{s}^{*}[v_{i_{s},s}]$
be such a matching. By the definition of $\mathcal{F}_{t}^{*}[v_{i_{t},s}]$,
we see that there exist $E_{1}\subset F_{1},\dots,E_{s}\subset F_{s}$ such
that
$E_{1}\cup\\{v_{i_{1},s}\\}\in\mathcal{F}_{1},E_{2}\cup\\{v_{i_{2},s}\\}\in\mathcal{F}_{2}\dots,E_{s}\cup\\{v_{i_{s},s}\\}\in\mathcal{F}_{s}$.
Note that $\mathcal{F}_{1},\dots,\mathcal{F}_{s}$ are all shifted. It follows
that
$E_{1}\cup\\{v_{i_{1},1}\\}\in\mathcal{F}_{1},E_{2}\cup\\{v_{i_{2},2}\\}\in\mathcal{F}_{2},\dots,E_{s}\cup\\{v_{i_{s},s}\\}\in\mathcal{F}_{s}$
is a rainbow matching, which contradicts the fact that
$\mathcal{F}_{1},\dots,\mathcal{F}_{s}$ are rainbow matching free.

By Claim 1, there exists $t\in[s]$ such that (3.12) holds for all
$i\in[\ell]$. By the definition of $\mathcal{F}_{t}^{*}[v_{i,s}]$, we see that
for each $E\in\mathcal{F}_{t}[v_{i,s}]$ there are $|V_{i}^{\prime}\setminus
E|=(n_{i}-s)-(k_{i}-1)$ choices of $u$ such that
$E\cup\\{u\\}\in\mathcal{F}_{t}^{*}[v_{i,s}]$. Moreover, for each
$F\in\mathcal{F}_{t}^{*}[v_{i,s}]$ we have $|F\cap V_{i}^{\prime}|=k_{i}$. It
follows that at most $k_{i}$ sets in $\mathcal{F}_{t}[v_{i,s}]$ are contained
in $F$. Thus, we have

$\displaystyle|\mathcal{F}_{t}^{*}[v_{i,s}]|\geq\frac{n_{i}-s-k_{i}+1}{k_{i}}\cdot|\mathcal{F}_{t}[v_{i,s}]|.$
(3.13)

By (3.12) and (3.13), we obtain that for all $i=1,2,\ldots,\ell$,

$\displaystyle|\mathcal{F}_{t}[v_{i,s}]|\leq\frac{6sk_{1}k_{i}}{n_{1}(n_{i}-s-k_{i}+1)}\prod_{1\leq
j\leq\ell}\binom{n_{j}}{k_{j}}.$ (3.14)

Note that
$\mathcal{F}_{1},\dots,\mathcal{F}_{t-1},\mathcal{F}_{t+1},\dots,\mathcal{F}_{s}$
contain a rainbow matching. Let $M^{\prime}$ be such a matching and let
$U^{\prime}$ be the set of vertices covered by $M^{\prime}$. By shiftedness,
we may assume that

$U^{\prime}=\bigcup_{i=1}^{\ell}\left\\{v_{i,1},\dots,v_{i,(s-1)k_{i}}\right\\}.$

Since $\mathcal{F}_{1},\dots,\mathcal{F}_{s}$ are rainbow matching free, it
follows that every edge of $\mathcal{F}_{t}$ intersects $U^{\prime}$. Thus,

$\mathcal{F}_{t}=\sum_{i=1}^{\ell}\sum_{j=1}^{(s-1)k_{i}}\mathcal{F}_{t}[v_{i,j}].$

By shiftedness, we have

$\displaystyle\mathcal{F}_{t}[v_{i,1}]\supseteq\mathcal{F}_{t}[v_{i,2}]\supseteq\dots\supseteq\mathcal{F}_{t}[v_{i,(s-1)k_{i}}]$

for $i=1,2,\dots,\ell$. Then

$\displaystyle|\mathcal{F}_{t}|\leq\sum_{i=1}^{\ell}(s-1)|\mathcal{F}_{t}[{v_{i,1}}]|+\sum_{i=1}^{\ell}(k_{i}-1)(s-1)|\mathcal{F}_{t}[v_{i,s}]|.$
(3.15)

Substitute (3.11) and (3.14) into (3.15), we arrive at

$\displaystyle|\mathcal{F}_{t}|\leq\sum_{i=1}^{\ell}\Bigg{(}(s-1)^{2}\Big{(}\sum_{p=1}^{\ell}\frac{k_{p}^{2}}{n_{p}}\Big{)}\frac{k_{i}}{n_{i}}\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}+6s(s-1)\frac{k_{i}(k_{i}-1)}{n_{i}-s-k_{i}+1}\frac{k_{1}}{n_{1}}\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}\Bigg{)}.$

Since $\frac{k_{i}}{n_{i}}\leq\frac{k_{1}}{n_{1}}$, we have

$|\mathcal{F}_{t}|\leq\frac{k_{1}}{n_{1}}\prod_{j=1}^{\ell}\binom{n_{j}}{k_{j}}\sum_{i=1}^{\ell}\Bigg{(}(s-1)^{2}\sum_{p=1}^{\ell}\frac{k_{p}^{2}}{n_{p}}+6s(s-1)\frac{k_{i}(k_{i}-1)}{n_{i}-s-k_{i}+1}\Bigg{)}.$

Since $n_{i}\geq 8\ell^{2}k_{i}^{2}s$ and $\ell\geq 2$, we have

$\sum_{i=1}^{\ell}\Big{(}(s-1)^{2}\sum_{p=1}^{\ell}\frac{k_{p}^{2}}{n_{p}}\Big{)}=\frac{(s-1)^{2}\ell^{2}}{8\ell^{2}s}\leq\frac{s-1}{8},$

and

$\sum_{i=1}^{\ell}\frac{6s(s-1)k_{i}(k_{i}-1)}{n_{i}-s-k_{i}+1}\leq\sum_{i=1}^{\ell}\frac{6s(s-1)k_{i}(k_{i}-1)}{16\ell
k_{i}(k_{i}-1)s+16\ell k_{i}s-s-k_{i}+1}\leq\frac{3(s-1)}{8}.$

Moreover, $\frac{k_{i}}{n_{i}}\leq\frac{k_{1}}{n_{1}}$. Hence, by inequality
(2.4) we obtain that

$\displaystyle|\mathcal{F}_{t}|$
$\displaystyle\leq\frac{(s-1)}{2}\binom{n_{1}-1}{k_{1}-1}\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}}$
$\displaystyle\leq(s-1)\binom{n_{1}-s+1}{k_{1}-1}\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}}$
$\displaystyle\leq\left(\binom{n_{1}}{k_{1}}-\binom{n_{1}-s+1}{k_{1}}\right)\prod_{j=2}^{\ell}\binom{n_{j}}{k_{j}},$

and this completes the proof.

###### Proof of Theorem 1.3..

As the same to the proof of Theorem 1.2, we have

$\min_{x_{1}+\dots+x_{\ell}=s}\prod_{i=1}^{\ell}\binom{n_{i}-x_{i}}{k_{i}}=\min_{1\leq
i\leq\ell}\binom{n_{i}-s}{k_{i}}\prod_{j\neq i}\binom{n_{j}}{k_{j}}.$

Thus, Lemma 3.6 implies the theorem.

## References

  * [1] R. Aharoni and D. Howard.  A rainbow $r$-partite version of the Erdős–Ko–Rado theorem.  Combinatorics, Probability and Computing, 26(3):321–337, 2017.
  * [2] N. Alon and F. R. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Mathematics, 72(1-3):15–19, 1988.
  * [3] B. Bollobás, D. E. Daykin, and P. Erdős.  Sets of independent edges of a hypergraph.  The Quarterly Journal of Mathematics, 27(1):25–32, 1976.
  * [4] P. Erdős, C. Ko, and R. Rado.  Intersection theorems for systems of finite sets.  The Quarterly Journal of Mathematics, 12:313–320, 1961.
  * [5] P. Erdős.  A problem on independent $r$-tuples.  Annales Universitatis Budapestinensis, 8:93–95, 1965.
  * [6] P. Erdős and T. Gallai.  On maximal paths and circuits of graphs.  Acta Mathematica Academiae Scientiarum Hungarica, 10(3-4):337–356, 1959.
  * [7] P. Frankl.  The shifting technique in extremal set theory.  Surveys in combinatorics, 123:81–110, 1987.
  * [8] P. Frankl.  An Erdős–Ko–Rado theorem for direct products.  European Journal of Combinatorics, 17(8):727–730, 1996.
  * [9] P. Frankl.  Improved bounds for Erdős matching conjecture.  Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013\.
  * [10] P. Frankl.  On the maximum number of edges in a hypergraph with given matching number.  Discrete Applied Mathematics, 216:562–581, 2017.
  * [11] P. Frankl and A. Kupavskii.  The Erdős matching conjecture and concentration inequalities.  arXiv preprint arXiv:1806.08855, 2018.
  * [12] P. Frankl and A. Kupavskii.  Simple juntas for shifted families.  Discrete Analysis, (14):18 pp, 2020.
  * [13] P. Frankl and J. Wang.  On the sum of sizes of overlapping families.  arXiv preprint arXiv:2105.00481, 2021.
  * [14] H. Huang, P.-S. Loh, and B. Sudakov.  The size of a hypergraph and its matching number.  Combinatorics, Probability and Computing, 21(3):442–450, 2012.
  * [15] G. Katona.  Intersection theorems for systems of finite sets.  Acta Mathematica Academiae Scientiarum Hungaricae, 15(3-4):329–337, 1964.
  * [16] N. Keller and N. Lifshitz.  The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture.  Advances in Mathematics, 392:107991, 2021.
  * [17] A. Kupavskii.  Rainbow version of the Erdős matching conjecture via concentration.  arXiv preprint arXiv:2104.08083, 2021.
  * [18] L. Lovász.  On the shannon capacity of a graph.  IEEE Transactions on Information theory, 25(1):1–7, 1979.
  * [19] H. Lu, Y. Wang, and X. Yu.  A better bound on the size of rainbow matchings.  arXiv preprint arXiv:2004.12561, 2020.


the embedding could be arbitrarily large due to long paths in $\mathbb{T}$.
Cohen-Addad et al. [CFKL20] resolved this issue by “shortcutting” long paths
via centroids999A centroid of a tree $T$ is a vertex $v$ such that every
subtree of $T\setminus v$ has at most $|V(T)|/2$ vertices. Specifically, they
apply the following steps: (a) find a centroid piece $G_{c}$ of $\mathbb{T}$,
(b) recursively construct the embedding for each subgraph $K$ obtained by
removing the centroid piece from $\mathbb{T}$, (c) glue the embedding of
$G_{c}$ and $K$ via clique-sum, and (d) add (the image of) the adhesion $J$
between $K$ and $G_{c}$ to every bag in the tree decomposition of the host
graph of $K$. Step (d) helps “shortcut” the shortest path, say $Q_{uv}$,
between any two vertices $u$ and $v$ between two different subgraphs $K_{i}$
and $K_{j}$ of $\mathbb{T}\setminus G_{c}$ in the following way: there is a
pair of vertices $x\in Q_{uv}\cap J_{i}$ and $y\in Q_{uv}\cap J_{j}$ such that
the distances between $u$ and $x$, and between $v$ and $y$ are preserved
_exactly_. Thus, the final embedding only incurs an additive distortion
$+\epsilon D$ for the distance between $x$ and $y$ (in the embedding of
$G_{c}$). However, step (d) increases the treewidth of the embedding
additively by $O(h(r)\log n)$, since each adhesion has size $O(h(r))$ and the
recursion has depth $O(\log n)$—by using the centroids for shortcutting—where
each recursive step adds one adhesion to the embedding a piece in
$\mathbb{T}$.

Our idea to remove the $\log n$ factor is as follows. We first root the tree
$\mathbb{T}$. Then for each piece $G_{i}$, we simply add the adhesion $J_{0}$
between $G_{i}$ and its parent bag $G_{0}$ to every bag in the tree
decomposition of the host graph $H_{i}$ in the embedding of $G_{i}$; this
increases the treewidth of $G_{0}$ by only $+O(h(r))$, and the overall
treewidth of the final embedding is also increased only by $+O(h(r))$. For the
stretch, we show by induction that for every vertex $u\in G_{a}$ and $v\in
G_{b}$ for any two pieces $G_{a},G_{b}$ such that $G_{i}$ is their lowest
common ancestor, there is a vertex $x\in Q_{uv}\cap G_{i}$ and $y\in
Q_{uv}\cap G_{i}$, the distances between $u$ and $x$, and between $v$ and $y$
are preserved _exactly_. Thus, the distortion for $d_{G}(u,v)$ is just
$+\epsilon D$. Since we apply this construction to _every_ piece of
$\mathbb{T}$, $+\epsilon D$ is also the distortion of the final embedding.

We are now ready to prove Lemma 17, which we restate below. See 17

###### Proof.

We apply Theorem 12 to obtain a decomposition of $G$ into a tree $\mathbb{T}$
of pieces $\\{G_{1},\ldots,G_{\ell}\\}$. Since every adhesion involved in a
clique-sum operation is a clique, $G_{i}$ has a diameter at most $D$ for every
$i\in[\ell]$. Root $\mathbb{T}$ at a piece $G_{rt}$ for some $rt\in[\ell]$.
For each $G_{i}$, let $f_{i}$ be the clique-preserving embedding $G_{i}$ into
$H_{i}$ with treewidth $t(h(r),\epsilon,|V(G_{i})|)\leq t(h(r),\epsilon,n)$
and expected additive distortion $+\epsilon D$. Let $\mathcal{T}_{i}$ be the
tree decomposition of $H_{i}$ with width at most $t(h(r),\epsilon,n)$.

For each pair of pieces $G_{i}$ and $G_{j}$ where $G_{j}$ is the parent piece
of $G_{i}$ in $\mathbb{T}$. Let $J_{ij}$ be the adhesion involving the clique
sum of $G_{i}$ and $G_{j}$. Let $Q^{i}_{ij}$ and $Q^{j}_{ij}$ be the clique
copies of $J_{ij}$ in $H_{i}$ and $H_{j}$. We apply the following two steps:

  * •

(Step 1).  We add to $H_{i}$ the edge set $Q^{i}_{ij}\times V(H_{i})$ and set
the weight of each edge to be the distance between the pre-images of its
endpoints in $G$; recall that $f_{i}(V(G_{i}))=V(H_{i})$. We then add
$Q^{i}_{ij}$ to every bag of the tree decomposition $\mathcal{T}_{i}$ so that
it remains a valid tree decomposition of $H_{i}$ after adding edges.

  * •

(Step 2).  We identify $Q^{i}_{ij}$ and $Q^{j}_{ij}$ into a single clique copy
$Q^{\prime}_{ij}$. This effectively connects $H_{i}$ and $H_{j}$. We then
replace the vertices of $Q^{i}_{ij}$ and $Q^{j}_{ij}$ in $\mathcal{T}_{i}$ and
$\mathcal{T}_{j}$, respectively, by the vertices of $Q^{\prime}_{ij}$. We then
take a pair of arbitrary two bags $B_{i}$ and $B_{j}$ of $\mathcal{T}_{i}$ and
$\mathcal{T}_{j}$, respectively, that contain $Q^{\prime}_{ij}$, and add an
edge $(B_{i},X_{j})$ to connect $\mathcal{T}_{i}$ and $\mathcal{T}_{j}$ into a
single tree decomposition. $X_{i}$ and $X_{j}$ exist since $f_{i}$ and $f_{j}$
are clique-preserving.

Let $H$ and $\mathcal{T}$ be the host graph and the tree decomposition
obtained by applying the above two steps to every pair of pieces $G_{i}$ and
$G_{j}$ where $G_{j}$ is the parent piece of $G_{i}$ in $\mathbb{T}$. For each
vertex $\tilde{v}\in V(H)$, we add $\tilde{v}$ to $f(v)$, which is initially
empty, if $\tilde{v}$ is the image of $v$ in the embedding of some piece in
the decomposition of $G$. This completes our construction of the embedding of
$G$.

Observe that $\mathcal{T}$ is a valid tree decomposition of $H$ since every
time we add an edge $(\tilde{u},\tilde{v})$ to $E(H)$ that is not present in
any $\\{H_{i}\\}_{i=1}^{\ell}$ (in Step 1), we guarantee that $\tilde{u}$ and
$\tilde{v}$ are in the same bag. Additionally, the construction in Step 1 only
increases the treewidth of $H_{i}$ by at most $h(r)$, which is the upper bound
on the size of $J_{ij}$ (this happens only once per piece). The width of the
resulting tree in Step 2 is bounded by the maximum width of $\mathcal{T}_{i}$
and $\mathcal{T}_{j}$. Thus, the width of $\mathcal{T}$ is
$t(h(r),\epsilon,n)+h(r)$.

Observe that $f$ is a dominating embedding since $\\{f_{i}\\}_{i}$ are
dominating. Thus, it is left to show that the expected distortion of the
embedding is $+\epsilon D$. To that end, we show the following claim.

######  Claim 4.

Let $G_{a}$ and $G_{b}$ be two pieces of $\mathbb{T}$ such that $G_{a}$ is a
proper ancestor of $G_{b}$. Let $J^{\downarrow}_{ab}$ be the adhesion in the
clique-sum between $G_{a}$ and its child on the path from $G_{a}$ to $G_{b}$.
For any two vertices $u\in J^{\downarrow}_{ab}$ and $v\in G_{b}$, there exists
a copy $\tilde{u}\in f_{a}(u)$ such that for every $\tilde{v}\in f_{b}(v)$:

$d_{H}(\tilde{u},\tilde{v})=d_{G}(u,v)\leavevmode\nobreak\ .$

###### Proof.

We prove by induction. The base case is when $G_{a}$ is a parent of $G_{b}$.
Then $J^{\downarrow}_{ab}=J_{ab}$. Let $Q^{a}_{ab}$ and $Q^{b}_{ab}$ be two
clique copies of $J^{ab}$ in $H_{a}$ and $H_{b}$, respectively, that are
identified into a single clique copy $Q^{\prime}_{ab}$ in the construction of
Step 2. Let $\tilde{u}$ be the copy of $u$ in $Q^{\prime}_{ab}$. By the
construction in Step 1, there is an edge from $\tilde{u}$ to every vertex in
$f(V(G_{b}))$. Thus for every $\tilde{v}\in f_{b}(v)$,
$d_{H}(\tilde{u},\tilde{v})=d_{G}(u,v)$.

For the inductive case, let $G_{c}$ be the parent piece of $G_{b}$. Let
$S_{uv}$ be a shortest path between $u$ and $v$ in $G$. Since
$G_{c}\in\mathbb{T}[G_{a},G_{b}]$, there must be a vertex $x\in J_{cb}\cap
S_{uv}$. By the induction hypothesis, there exists a copy $\tilde{x}\in
f_{c}(x)$ such that for every $\tilde{v}\in f_{b}(v)$,
$d_{H}(\tilde{x},\tilde{v})=d_{G}(x,v)$. Also by induction, there exists a
copy $\tilde{u}\in f_{a}(u)$ such that
$d_{H}(\tilde{u},\tilde{x})=d_{G}(u,x)$. By the triangle inequality, for every
$\tilde{v}\in f_{b}(v)$:

$d_{H}(\tilde{u},\tilde{v})\leq
d_{H}(\tilde{u},\tilde{x})+d_{H}(\tilde{x},\tilde{v})=d_{G}(u,x)+d_{G}(x,v)=d_{G}(u,v)\leavevmode\nobreak\
.$

As $f$ is dominating, we conclude that
$d_{H}(\tilde{u},\tilde{v})=d_{G}(u,v)$. ∎

We now show that for every $u,v$,

$\mathbb{E}\left[\max_{\tilde{u}\in f(u),\tilde{v}\in
f(v)}d_{H}(\tilde{u},\tilde{v})\right]\leq d_{G}(u,v)+\epsilon
D\leavevmode\nobreak\ .$ (13)

Let $G_{a}$ and $G_{b}$ be the two pieces closest to the root of $\mathbb{T}$,
containing $u$ and $v$ respectively. If $G_{a}=G_{b}$, then
$d_{G_{a}}(u,v)=d_{G}(u,v)$, and by the assumption that $f_{a}$ has expected
additive distortion $+\epsilon D$, we have that $\mathbb{E}[\max_{\tilde{u}\in
f_{a}(u),\tilde{v}\in f_{a}(v)}d_{H}(\tilde{u},\tilde{v})]\leq
d_{H}(u,v)+\epsilon D$. By 4, for any copy $\tilde{u}\in f(u)$ (resp.
$\tilde{v}\in f(v)$) coming from a decedent piece of $G_{a}$ (resp. $G_{b}$),
there is a copy $\hat{u}\in f_{a}(u)$ (resp. $\hat{v}\in f_{a}(v)$) such that
$d_{H}(\hat{u},\tilde{u})=d_{G}(u,u)=0$ (resp. $d_{H}(\hat{v},\tilde{v})=0$).
It follows that

$\displaystyle\mathbb{E}\left[\max_{\tilde{u}\in f(u),\tilde{v}\in
f(v)}d_{H}(\tilde{u},\tilde{v})\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{\tilde{u}\in f(u),\tilde{v}\in
f(v)}d_{H}(\tilde{u},\hat{u})+d_{H}(\hat{u},\hat{v})+d_{H}(\hat{v},\tilde{v})\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{\hat{u}\in f_{a}(u),\hat{v}\in
f_{a}(v)}d_{H}(\hat{u},\hat{v})\right]\leavevmode\nobreak\
\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \leavevmode\nobreak\
d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$ (14)

Otherwise ($G_{a}\neq G_{b}$), let $G_{c}$ be the least common ancestor of
$G_{a}$ and $G_{b}$ in $\mathbb{T}$. Let $S_{uv}$ be the shortest path between
$u$ and $v$ in $G$. Then, there must exist two vertices $x\in
J^{\downarrow}_{ca}\cap S_{uv}$ and $y\in J^{\downarrow}_{cb}\cap S_{uv}$. By
4, there exist $\hat{x}\in f_{c}(x)$ and $\hat{y}\in f_{c}(y)$ such that for
every two copies $\tilde{u}\in f_{a}(u)$ and $\tilde{v}\in f_{b}(v)$,

$d_{H}(\hat{x},\tilde{u})=d_{G}(x,u)\qquad\&\qquad
d_{H}(\hat{y},\tilde{v})=d_{G}(y,v).$

By the triangle inequality, linearity of expectation, the fact that $f_{c}$
has expected distortion $+\epsilon D$, and the fact that $x$ and $y$ lie on a
shortest $u$-$v$ path, it holds that:

$\displaystyle\mathbb{E}\left[\max_{\tilde{u}\in f_{a}(u),\tilde{v}\in
f_{b}(v)}d_{H}(\tilde{u},\tilde{v})\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{\tilde{u}\in f_{a}(u),\tilde{v}\in
f_{b}(v)}d_{H}(\tilde{u},\hat{x})+d_{H}(\hat{x},\hat{y})+d_{H}(\hat{y},\tilde{v})\right]$
$\displaystyle\leq d_{G}(u,x)+\mathbb{E}\left[\max_{\tilde{x}\in
f_{c}(x),\tilde{y}\in f_{c}(y)}d_{H}(\tilde{x},\tilde{y})\right]+d_{G}(y,v)$
$\displaystyle=d_{G}(u,x)+d_{G}(x,y)+d_{G}(y,v)+\epsilon D\leavevmode\nobreak\
\leavevmode\nobreak\ =\leavevmode\nobreak\ \leavevmode\nobreak\
d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$

For any copy $\tilde{u}\in f(u)$ (resp. $\tilde{v}\in f(v)$) coming from a
decedent piece of $G_{a}$ (resp. $G_{b}$), by Equation 14, we conclude that
Equation 13 holds, as desired. ∎

###  6.2 An Efficient PTAS for the Bounded-capacity VRP (Proof of Theorem 2)

In this section, we show that the embedding in Theorem 1 can be used to obtain
an efficient PTAS for the bounded-capacity VRP in $K_{r}$-minor-free graphs as
claimed in Theorem 2. Our result significantly improves the previous result by
Cohen-Addad et al.  [CFKL20] who showed an approximation scheme with _quasi-
polynomial time_ for this problem.

The algorithm for minor-free graphs closely resembles the algorithm for planar
graphs in Section 4.3.2. The following lemma is similar to Lemma 8.

######  Lemma 20.

Let $G(V,E,w)$ be an $n$-vertex $K_{r}$-minor-free graph and $r$ be a
distinguished vertex in $V$. For any given parameter
$\epsilon\in(0,\frac{1}{4})$, we can construct in $O_{\epsilon,r}(1)\cdot
n^{O(1)}$ time an $(r,\epsilon)$-rooted stochastic embedding of $G$ into
graphs $H$ of treewidth $O_{r,\epsilon}((\log\log n)^{2})$.

###### Proof.

Our construction follows exactly the same steps as the construction of Lemma
8; the only difference is that we use Theorem 1 instead of Theorem 3 (and the
standard shortest path algorithm instead of [HKRS97]). The running time is
clearly polynomial.

For the distortion analysis, consider a pair of vertices $u,v\in V$, and let
$i$ be the index such that $u\in B_{i}$, and let $f_{i}$ be the embedding of
$G_{i}$ to the low treewidth graph $H_{i}$. Recall that the vertex $u$ is
successful with probability $1-2\epsilon$. If $u$ is successful and the
shortest path $P$ between $u$ and $v$ is not fully contained in $B_{i}$, then
by the case analysis in Lemma 8, $d_{H}(v,u)\leq
d_{G}(v,u)+2\cdot\epsilon\cdot d_{G}(r,u)$ (as that argument used only edges
incident to $r$, which are present in our embedding as well). Otherwise,
$P\subseteq B_{i}$, and hence $d_{G_{i}}(u,v)=d_{G}(u,v)$. Following the
calculation in Equation 4, we have

$\mathbb{E}\left[d_{H}(f(u),f(v))\mid d_{G_{i}}(u,v)=d_{G}(u,v)\right]\leq
d_{G}(u,v)+\delta\cdot 2U_{i}\leq d_{G}(u,v)+2\epsilon\cdot
d_{G}(r,u)\leavevmode\nobreak\ .$

Thus, conditioning on $u$ being successful, we have

$\mathbb{E}[d_{H}(f(u),f(v))\mid u\text{ is successful}]\leq
d_{G}(v,u)+O(\epsilon)\cdot\left(d_{G}(r,v)+d_{G}(r,u)\right)\leavevmode\nobreak\
,$

and it follows that:

$\displaystyle\mathbb{E}[d_{H}(f(u),f(v))]$ $\displaystyle\leq\Pr\left[v\text{
is successful}\right]\cdot\mathbb{E}[d_{H}(f(u),f(v))\mid u\text{ is
successful}]$ $\displaystyle\qquad+\Pr\left[v\text{ is
unsuccessful}\right]\cdot\left(d_{G}(v,r)+d_{G}(r,u)\right)$
$\displaystyle\leq
d_{G}(v,u)+O(\epsilon)\cdot\left(d_{G}(r,v)+d_{G}(r,u)\right)\leavevmode\nobreak\
.$

∎

We are now ready to prove Theorem 2, which we restate below for convenience.
See 2

###### Proof.

Following exactly the same steps in the proof of Theorem 6 in Section 4.3.2,
we plug Lemma 20 and Lemma 12 into Lemma 13 to obtain a
$(1+\epsilon)$-approximate solution. Following Equation 11, the running time
hence is:

$(Q\epsilon^{-1}\log n)^{O_{\frac{\epsilon}{9Q}}(Q\cdot\log\log n)^{2}}\cdot
n+O_{\epsilon,r}(1)\cdot n^{O(1)}=O_{\epsilon,r}(1)\cdot
n^{O(1)}\leavevmode\nobreak\ .$

∎

##  7 Ramsey Type and Clan Embeddings of Minor-free Graphs and their
Applications

###  7.1 Ramsey Type and Clan Embeddings (Proofs of Theorems 8 and 7)

In this section, we prove Theorem 7 and Theorem 8. A key idea in the
construction of the authors [FL21] is that one can construct a clan/Ramsey
type embedding from a deterministic one-to-one embedding of $h$-multi-vortex-
genus graphs with an $O(\log n)$ loss in the treewidth. Lemma 21 below is a
reinterpretation of Lemma 15 and Lemma 16 for Ramsey type embedding and Lemma
18 and Lemma 19 for clan embedding in [FL21].

######  Lemma 21 (Lemmas 15,16, 18 and 19 [FL21], adapted).

Suppose that every $n$-vertex $h$-multi-vortex-genus graph of diameter $D$ can
be deterministically embedded into a graph with treewidth $t(h,\epsilon,n)$
and additive distortion $+\epsilon D$ via a clique-preserving embedding. Then
for every parameter $\delta\in(0,1)$, and every $n$-vertex $K_{r}$-free graph
$G=(V,E,w)$ of diameter $D$, there exist an $(\epsilon D,\delta)$-Ramsey type
embedding and an $(\epsilon D,\delta)$-clan embedding, both with treewidth
$t(O_{r}(1),O(\frac{\delta\epsilon}{\log(n)}),n)+O_{r}(\log n)$.

To obtain their treewidth bound $O_{r}(\frac{\log^{2}}{\delta\epsilon})$, the
authors[FL21] used the embedding of $h$-multi-vortex-genus graphs with
treewidth $O_{r}(\frac{\log(n)}{\epsilon})$ by Cohen-Addad et al.  [CFKL20].

We show below that Lemma 21 and Lemma 14 provide a reduction from _$h$ -vortex
planar graphs_ to $K_{r}$-minor-free graphs.

######  Lemma 22.

Suppose that every $h$-vortex planar graph of $n$ vertices and diameter $D$
can be deterministically embedded into a graph with treewidth
$t(h,\epsilon,n)$ and additive distortion $+\epsilon D$ via a clique-
preserving embedding. Then for every parameter $\delta\in(0,1)$ and every
$K_{r}$-free graph $G=(V,E,w)$ of $n$ vertices and diameter $D$, there exist
an $(\epsilon D,\delta)$-Ramsey type embedding and an $(\epsilon
D,\delta)$-clan embedding, both with treewidth
$O_{r}(t(O_{1}(r),O_{r}(\frac{\delta\epsilon}{\log n}),n)+\log(n))$.

###### Proof.

By Lemma 14, any $h$-multi-vortex-genus graph $G$ of $n$ vertices and diameter
$D$ can be deterministically embedded into a graph with treewidth
$\hat{t}(h,\epsilon,n)=O_{h}(t(O_{h}(1),O_{h}(\epsilon),n))$ via a clique-
preserving embedding. This embedding and Lemma 21 give a $(\epsilon
D,\delta)$-Ramsey type embedding and a $(\epsilon D,\delta)$-clan embedding
with treewidth:

$\begin{split}\hat{t}(O_{r}(1),O(\frac{\delta\epsilon}{\log(n)}),n)+O_{r}(\log
n)&=O_{r}(t(O_{r}(1),O_{r}(\frac{\delta\epsilon}{\log
n}),n)+O_{r}(\log(n)))\\\ &=O_{r}(t(O_{1}(r),O_{r}(\frac{\delta\epsilon}{\log
n}),n)+\log(n))\leavevmode\nobreak\ ,\end{split}$

as claimed. ∎

We are now ready to prove Theorem 7 and Theorem 8.

###### Proof of Theorem 7 and Theorem 8.

By Lemma 16, any $h$-vortex planar graph of $n$ vertices and diameter $D$ has
a clique-preserving embedding with additive distortion $+\epsilon D$ and
treewidth:

$t(h,\epsilon,n)=O(\frac{h(\log\log n)^{2}}{\epsilon}).$

It follows from Lemma 22 that $K_{r}$-free graphs of $n$ vertices and diameter
$D$ has an $(\epsilon D,\delta)$-Ramsey type embedding and an $(\epsilon
D,\delta)$-clan embedding, both with treewidth:

$O_{r}(t(O_{1}(r),O_{r}(\frac{\delta\epsilon}{\log
n}),n)+\log(n))=O_{r}\left(O_{r}\left(\frac{(\log\log
n)^{2}}{(\delta\epsilon)/\log(n)}\right)+\log(n)\right)=O_{r}\left(\frac{\log
n(\log\log n)^{2}}{\epsilon\delta}\right)\leavevmode\nobreak\ ,$

as desired. ∎

###  7.2 Applications to Metric Baker’s Problems (Proof of Theorem 9)

Given a clan embedding, one could obtain a bicriteria approximation scheme for
the $\rho$-dominating set problem by dynamic programming on the host graph.
Similarly, given a Ramsey type embedding, one could obtain a bicriteria
approximation scheme for the $\rho$-independent set problem, also by dynamic
programming. Lemma 9 provides efficient dynamic programs for both problems in
graphs with low treewidth. The following lemmas specify the running time of
the resulting algorithms.

######  Lemma 23 (Theorems 7 and 8 [FL21], adapted).

Suppose that for every parameters $\epsilon,\delta\in(0,1)$, and every
$K_{r}$-free graph $G=(V,E,w)$ of diameter $D$ and $n$ vertices, there are
$(\epsilon D,\delta)$-clan and $(\epsilon D,\delta)$-Ramsey type embeddings,
both with treewidth $\mathsf{tw}(\epsilon,\delta)$. Then given an $n$-vertex
$K_{r}$-minor-free graph $G(V,E,w)$, two parameters $\epsilon\in(0,1)$ and
$\rho>0$, and a vertex weight function $\mu:V\rightarrow\mathbb{R}^{+}$, one
can find in
$2^{O(\mathsf{tw}(\Theta(\epsilon),\Theta(\epsilon))\cdot\log\frac{\mathsf{tw}(\Theta(\epsilon),\Theta(\epsilon))}{\epsilon})}\cdot\mathrm{poly}(n)$
time:
(1) a $(1-\epsilon)\rho$-independent set $I$ such that for every
$\rho$-independent set $\tilde{I}$, $\mu(I)\geq(1-\epsilon)\mu(\tilde{I})$,
and
(2) a $(1+\epsilon)\rho$-dominating set $S$ such that for every
$\rho$-dominating set $\tilde{S}$, $\mu(S)\leq(1+\epsilon)\mu(\tilde{S})$.

We are now ready to prove Theorem 9.

###### Proof of Theorem 9.

By Theorem 7 and Theorem 8, $K_{r}$-minor-free graphs of diameter $D$ and $n$
vertices have $(\epsilon D,\delta)$-clan and $(\epsilon D,\delta)$-Ramsey type
embeddings, both with treewidth $\mathsf{tw}(\epsilon,\delta)=O_{r}(\frac{\log
n(\log\log n)^{2})}{\epsilon\delta})$. Thus, by Lemma 23, we obtain a
bicriteria approximation scheme for $\rho$-independent set and
$\rho$-dominating set problems in time:

$\begin{split}2^{O(\mathsf{tw}(\Theta(\epsilon),\Theta(\epsilon))\cdot\log\frac{\mathsf{tw}(\Theta(\epsilon),\Theta(\epsilon))}{\epsilon})}\cdot\mathrm{poly}(n)&=2^{O(O_{r}(\frac{\log
n(\log\log n)^{2}}{\epsilon^{2}}\log(\frac{\log n(\log\log
n)^{2}}{\epsilon^{3}})}\\\
&=n^{\tilde{O}_{r}(\epsilon^{-2}(\log\log(n))^{3})}\leavevmode\nobreak\
,\end{split}$

as claimed. ∎

##  8 Treewidth Lower Bounds

###  8.1 Additive Distortion (Proof of Theorem 4)

In this section, we prove a lower bound on the treewidth of the embedding
planar graphs with additive distortion. For a given graph $J=(V_{J},E_{J})$,
we denoted by $J_{k}$ a $k$-subdivision of $J$. That is, $J_{k}$ is obtained
from $J$ by replacing each edge with a path of length $k$. See the
illustration on the right for a $4$-subdivision. Our lower bound uses the
following lemma by Carrol and Goel [CG04].

######  Lemma 24 (Lemma 1 [CG04]).

Let $H$ be a (possibly weighted) graph that excludes $J$ as a minor. Every
dominating embedding from $J_{k}$ to $H$ has a multiplicative distortion at
least $\frac{k-3}{6}$.

See 4

###### Proof.

W.l.o.g, we assume that $\epsilon$ is sufficiently smaller than $1$ since
otherwise, the theorem trivially holds. Set
$n^{\prime}=\frac{1}{42\epsilon}+1$. Let $Q$ be an $n^{\prime}\times
n^{\prime}$-grid. The diameter of $Q$ is
$2\cdot\frac{1}{42\epsilon}=\frac{1}{21\epsilon}$. Let $Q_{k}$ be a
$k$-subdivision of $Q$ for $k=21$. Observe that the diameter of $Q_{k}$ is
$21\cdot\frac{1}{21\epsilon}=\frac{1}{\epsilon}$. Furthermore,
$|V(Q_{k})|=O(1/\epsilon^{2})$. Finally, we add $n-|V(Q_{k})|$ dummy vertices
and connect all of them to some vertex of $Q_{k}$ in a star-like way. Let $G$
be the resulting graph; $G$ is planar by construction. Furthermore, the
diameter of $G$ is $D=1/\epsilon+1$.

Suppose that there is a deterministic, dominating embedding $f$ of $G$ with an
additive distortion at most $\epsilon D$ into a treewidth $o(1/\epsilon)$
graph $H$. Observe that $\epsilon
D=\epsilon(\frac{1}{\epsilon}+2)=1+2\epsilon\leq 2$ when $\epsilon\leq 1/2$.
It follows that $f$ has multiplicative distortion at most $2$. As $H$ has
treewidth $o(1/\epsilon)$ (see e.g. [RST94]), it excludes $Q$ as a minor. Thus
by Lemma 24, any embedding of $Q_{k}$ into $H$, including $f_{Q_{k}}$, must
have a multiplicative distortion at least $\frac{k-3}{6}=3$, a contradiction.
Thus, the treewidth of $H$ must be $\Omega(1/\epsilon)$ as claimed. ∎

###  8.2 Multiplicative Distortion (proof of Theorem 13)

In this section, we follow the lower bound constructions of Carroll and Goel
[CG04] and Chakrabarti, Jaffe, Lee, and Vincent [CJLV08] (which by itself is
based on [GNRS04]) to derive lower bounds on the multiplicative distortion for
stochastic embeddings of planar graphs into low-treewidth graphs. Chakrabarti
et al. [CJLV08] showed that there exists an infinite family of graphs such
that for any graph $G$ in the family with $n$ vertices, any embedding of $G$
into a distribution over graphs of _constant_ treewidth must have an expected
(multiplicative) distortion $\Omega(\log n)$. By carefully adapting the
parameters of the construction of Chakrabarti et al.  [CJLV08], we obtain a
quantitative lower bound w.r.t. the treewidth. The rest of the section is
devoted to proving Theorem 13.

######  Theorem 13.

There exists an infinite family of planar graphs $\mathcal{G}$ such that for
any graph $G_{n}\in\mathcal{G}$ of $n$ vertices for a sufficiently large $n$,
any embedding of $G_{n}$ into a distribution over graphs of treewidth
$O(\frac{\log^{\nicefrac{{1}}{{3}}}n}{\log\log n})$ must have expected
multiplicative distortion $\Omega(\frac{\log^{\nicefrac{{1}}{{3}}}n}{\log\log
n})$.

Given an edge-weighted graph $G=(V,E,w)$ and two vertices $s\neq t$ in $G$, we
say that $G$ is _$(s,t)$ -geodesic_ if we can partition the edge set of $G$
into a set of edge-disjoint shortest $s$-to-$t$ paths.

Denote by $Q$ the $(n+1)\times(n+1)$ unweighted grid, and by $Q_{p}$ the
$p$-subdivision of $Q$. Denote by $\mathcal{X}_{n}$ the family of graphs with
treewidth at most $n$. As every graph of treewidth at most $n$ excludes $Q$ as
a minor [RS86], by Lemma 24 we observe:

######  Observation 4.

For every $p\in\mathbb{N}$, every _deterministic_ embedding of $Q_{p}$ into a
graph in $\mathcal{X}_{n}$ must incur multiplicative distortion
$\frac{p-3}{6}$.

Next we construct a geodesic version of the grid graph $Q$. Metric embedding
$f:X\rightarrow Y$ between two metric spaces $(X,d_{X}),(Y,d_{Y})$ is called
isometric if for every $x,y\in X$, $d_{X}(x,y)=\alpha\cdot d_{Y}(f(x),f(y))$
for some constant $\alpha$.

######  Lemma 25.

There is an unweighted $(s,t)$-geodesic planar graph $\hat{Q}$ with $<8n^{2}$
edges, and $2n+2$ disjoint $s-t$ shortest paths $\mathcal{P}$ of length $2n$,
such that $Q$ embeds isometrically into $\hat{Q}$.

###### Proof.

Denote by $s,t$ the upper-left, and lower-right vertices of the grid $Q$,
respectively. There is a set of $2(n+1)$ shortest paths
$\\{P_{i}\\}_{i=1}^{2(n+1)}$ from $s$ to $t$ such that every edge of $Q$
belongs to some path in $Q$ (each path can “cover” all the edges in a single
row/column). By duplicating edges, we can obtain a planar multi-graph $Q^{M}$,
such that the edges of $Q^{M}$ can be partitioned into disjoint paths
$\\{P_{i}^{M}\\}_{i=1}^{2(n+1)}$, while the shortest path distance of $Q$ and
$Q^{M}$ is the same. $Q^{M}$ has $|E(Q^{M})|=2n\cdot 2(n+1)$ edges (as it a
collection of $2(n+1)$ paths of length $2n$). The graph $Q^{M}_{2}$ (where
each edge is subdivided to two edges) is a simple graph, with
$|E(Q^{M}_{2})|=2|E(Q^{M})|=4n\cdot 2(n+1)$ edges, and
$|\mathcal{P}(Q^{M}_{2})|=2(n+1)$ disjoint $s-t$ shortest paths of length
$2n$. Note that $Q$ indeed embeds isometrically into $Q^{M}_{2}$, as all
distances are increased by a factor of $2$. See Figure 1 for an illustration.
∎

Figure 1: The $3\times 3$ grid $Q$ is illustrated in the first figure on the
left. In the second figure, all $Q$ edges are covered by $6$ paths. In the
third figure, we obtain an isometric multi-graph whose edges can be
partitioned into disjoint shortest paths. In the right figure, we obtain a
simple graph by subdividing each edge. Figure 2: On the left illustrated the
geodesic version $\hat{Q}$ of the $3\times 3$ grid $Q$, also denoted by
$H_{1}$. On the right the graph $H_{2}$ is illustrated, where we replaced each
edge of $H_{1}$ with a copy of $H_{1}$.

Note that as $Q$ embeds isometrically into $\hat{Q}$, every $p$-subdivision of
$Q$, denoted $Q_{p}$, embeds isometrically into the $p$-subdivision of
$\hat{Q}$, denoted $\hat{Q}_{p}$. In particular, every deterministic embedding
of $\hat{Q}_{p}$ into $\mathcal{X}_{n}$ incurs a multiplicative distortion at
least $\frac{p-3}{6}$.

Let $H_{1}$ by the graph $\hat{Q}$. For $k\geq 2$, we construct $H_{k}$, by
replacing every edge in $H_{k-1}$ with a copy of $H_{1}$, identifying $s,t$
with the endpoints of the edge arbitrarily. Note that $H_{k}$ is a planar
graph. See Figure 2 for an illustration. Following a mini-max argument in
[GNRS04], in order to show that every stochastic embedding of $H_{k}$ into
graphs of $\mathcal{X}_{n}$ has expected multiplicative distortion $\alpha$,
it is enough to show that for every deterministic embedding, the average
distortion over the edges is $\alpha$. More formally, it is enough to show
that for every dominating embedding $f$ into $G\in\mathcal{X}_{n}$ it holds
that $\sum_{\\{u,v\\}\in E(H_{k})}d_{G}(f(u),f(v))\geq\alpha\cdot|E(H_{k})|$.

Denote $m=|E(H_{1})|=|E(\hat{Q})|$. The following claim follows by a simple
induction:

######  Claim 5.

For all $1\leq i\leq k$, $H_{k}$ contains $m^{k-i}$ disjoint copies of
$H_{i}$.

$H_{1}$ contains $\rho=2(n+1)$ shortest paths, all of length $\ell=2n$. Note
that $\ell\cdot\rho=m$. By another induction, for $i\geq 1$ it follows:

######  Claim 6.

$H_{i}$ contains $\rho^{i-1}$ edge-disjoint $\ell^{i-1}$-subdivisions of
$H_{1}$ (that is $\hat{Q}_{(2n)^{i-1}}$).

Fix some embedding $f$ of $H_{k}$ into a graph in $\mathcal{X}_{n}$. By 4,
each such subdivision $\hat{Q}_{\ell^{i-1}}$ has distortion
$\frac{\ell^{i-1}-3}{6}\geq\frac{\ell^{i-1}}{7}$ w.r.t. $f$ (we assume $n$ is
large enough, and for $i=1$ the distortion is at least $1\geq\frac{1}{7}$). In
particular, some edge $\\{u,v\\}$ in each subdivision has
$d_{G}(f(u),f(v))\geq\frac{1}{7}\cdot\ell^{i-1}$. Let
$C_{i}=\left\\{\\{u,v\\}\in E(H_{k})\mid
d_{G}(f(u),f(v))\geq\frac{1}{7}\cdot\ell^{i-1}\right\\}$ be the set of of all
edges that are distorted by at least $\frac{1}{7}\cdot\ell^{i-1}$. By
combining 5 and 6, $|C_{i}|\geq m^{k-i}\cdot\rho^{i-1}$. For an edge
$\\{u,v\\}\in E(H_{k})$, let $C_{\\{u,v\\}}=\left\\{i\mid\\{u,v\\}\in
C_{i}\right\\}$. It holds that $\sum_{i\in
C_{\\{u,v\\}}}\frac{1}{7}\cdot\ell^{i-1}\leq\frac{2}{7}\cdot\ell^{\max
C_{\\{u,v\\}}-1}\leq 2\cdot d_{G}(f(u),f(v))$. We conclude:

$\displaystyle\sum_{\\{u,v\\}\in E(H_{k})}d_{G}(f(u),f(v))$
$\displaystyle\geq\sum_{\\{u,v\\}\in E(H_{k})}\sum_{i\in
C_{\\{u,v\\}}}\frac{1}{14}\cdot\ell^{i-1}=\frac{1}{14}\cdot\sum_{i=1}^{k}|C_{i}|\cdot\ell^{i-1}$
$\displaystyle=\frac{1}{14}\cdot\sum_{i=1}^{k}m^{k-i}\cdot\rho^{i-1}\cdot\ell^{i-1}=\frac{1}{14}\cdot\sum_{i=1}^{k}m^{k-i}\cdot
m^{i-1}=\frac{k}{14m}\cdot
m^{k}=\frac{k}{14m}\cdot|E(H_{k})|\leavevmode\nobreak\ .$

Set $k=n^{3}$. Then $H_{k}$ has
$N=|V(H_{k})|\leq|E(H_{k})|=m^{k}<(8n)^{2k}=2^{O(n^{3}\log n)}$ vertices, and
every stochastic embedding into a graphs of treewidth
$n=O(\frac{\log^{\nicefrac{{1}}{{3}}}N}{\log\log N})$, will have expected
distortion at least
$\frac{k}{14m}=\Omega(n)=\Omega(\frac{\log^{\nicefrac{{1}}{{3}}}N}{\log\log
N})$. Theorem 13 now follows.

######  Remark 1.

It is interesting to understand the exact trade-off between the treewidth of
the host graphs, and the expected distortion. [FRT04] implies that one can
embed every $N$-vertex planar graph (actually general graph) into a
distribution over treewidth-$1$ graphs with expected distortion $O(\log N)$,
while Theorem 13 states that one cannot obtain expected distortion smaller
that $\Omega(\frac{\log^{\nicefrac{{1}}{{3}}}N}{\log\log N})$ for embedding
planar graphs into
treewidth-$\Omega(\frac{\log^{\nicefrac{{1}}{{3}}}N}{\log\log N})$ graphs. By
choosing $k=n^{2+\alpha}$ in the proof of Theorem 13 for constant $\alpha>0$,
we derive that one cannot obtain distortion smaller than
$\Omega\left(\frac{\log^{\frac{\alpha}{2+\alpha}}N}{\log\log N}\right)$ for
embedding planar graphs into
treewidth-$O\left(\frac{\log^{\frac{1}{2+\alpha}}N}{\log\log N}\right)$
graphs.

## Acknowledgments

The authors are grateful to Philip Klein and Vincent Cohen-Addad for helpful
conversations.

## References

  * [ACE+20] I. Abraham, S. Chechik, M. Elkin, A. Filtser, and O. Neiman.  Ramsey spanning trees and their applications.  ACM Trans. Algorithms, 16(2):19:1–19:21, 2020.  preliminary version published in SODA 2018.  doi:10.1145/3371039.
  * [ACL09] A. Adamaszek, A. Czumaj, and A. Lingas.  PTAS for $k$-tour cover problem on the plane for moderately large values of $k$.  In International Symposium on Algorithms and Computation, ISAAC ‘09, pages 994–1003, 2009.  doi:10.1007/978-3-642-10631-6_100.
  * [AFGN18] I. Abraham, A. Filtser, A. Gupta, and O. Neiman.  Metric embedding via shortest path decompositions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 952–963, 2018.  full version: https://arxiv.org/abs/1708.04073.  doi:10.1145/3188745.3188808.
  * [AGG+19] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  SIAM J. Comput., 48(3):1120–1145, 2019.  preliminary version published in STOC 2014.  doi:10.1137/17M1112406.
  * [AGK+98] S. Arora, M. Grigni, D. R. Karger, P. N. Klein, and A. Woloszyn.  A polynomial-time approximation scheme for weighted planar graph TSP.  In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA, pages 33–41, 1998.  see here.
  * [AHLT05] S. Alstrup, J. Holm, K. D. Lichtenberg, and M. Thorup.  Maintaining information in fully dynamic trees with top trees.  ACM Transactions on Algorithms, 1(2):243–264, 2005.  doi:10.1145/1103963.1103966.
  * [AKTT97] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama.  Covering points in the plane by $k$-tours: Towards a polynomial time approximation scheme for general $k$.  In Proceedings of the 29thh Annual ACM Symposium on Theory of Computing, STOC ‘97, page 275–283, 1997.  doi:10.1145/258533.258602.
  * [AMS99] N. Alon, Y. Matias, and M. Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.  preliminary version published in STOC 1996.  doi:10.1006/jcss.1997.1545.
  * [AS87] N. Alon and B. Schieber.  Optimal preprocessing for answering on-line product queries.  1987\.  see here.
  * [AS03] V. Athitsos and S. Sclaroff.  Database indexing methods for 3d hand pose estimation.  In Gesture-Based Communication in Human-Computer Interaction, 5th International Gesture Workshop, GW 2003, Genova, Italy, April 15-17, 2003, Selected Revised Papers, pages 288–299, 2003.  doi:10.1007/978-3-540-24598-8\\_27.
  * [Bak94] B. S. Baker.  Approximation algorithms for NP-complete problems on planar graphs.  Journal of the ACM, 41(1):153–180, 1994.  preliminary version published in FOCS 1983.  doi:10.1145/174644.174650.
  * [Bar96] Y. Bartal.  Probabilistic approximations of metric spaces and its algorithmic applications.  In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193, 1996\.  doi:10.1109/SFCS.1996.548477.
  * [Bar98] Y. Bartal.  On approximating arbitrary metrices by tree metrics.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161–168, 1998\.  doi:10.1145/276698.276725.
  * [Bar04] Y. Bartal.  Graph decomposition lemmas and their role in metric embedding methods.  In Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pages 89–97, 2004.  doi:10.1007/978-3-540-30140-0\\_10.
  * [Bar21] Y. Bartal.  Advances in metric ramsey theory and its applications.  CoRR, abs/2104.03484, 2021.  arXiv:2104.03484.
  * [BBM06] Y. Bartal, B. Bollobás, and M. Mendel.  Ramsey-type theorems for metric spaces with applications to online problems.  J. Comput. Syst. Sci., 72(5):890–921, 2006.  Special Issue on FOCS 2001.  doi:10.1016/j.jcss.2005.05.008.
  * [BCL+18] S. Bubeck, M. B. Cohen, Y. T. Lee, J. R. Lee, and A. Madry.  k-server via multiscale entropic regularization.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3–16, 2018.  doi:10.1145/3188745.3188798.
  * [Bec18] A. Becker.  A tight 4/3 approximation for capacitated vehicle routing in trees.  In 118, editor, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), pages 3:1–3:15, 2018.  doi:10.4230/LIPIcs.APPROX-RANDOM.2018.3.
  * [BFC00] M. A. Bender and M. Farach-Colton.  The LCA problem revisited.  In Latin American Symposium on Theoretical Informatics, LATIN ’00, pages 88–94, 2000.  doi:10.1007/10719839_9.
  * [BFM86] J. Bourgain, T. Figiel, and V. Milman.  On Hilbertian subsets of finite metric spaces.  Israel J. Math., 55(2):147–152, 1986.  doi:10.1007/BF02801990.
  * [BGS16] G. E. Blelloch, Y. Gu, and Y. Sun.  A new efficient construction on probabilistic tree embeddings.  CoRR, abs/1605.04651, 2016.  https://arxiv.org/abs/1605.04651.  arXiv:1605.04651.
  * [BKS17] A. Becker, P. N. Klein, and D. Saulpic.  A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs.  In 25th Annual European Symposium on Algorithms, volume 87 of ESA ‘17, pages 12:1–12:15, 2017.  doi:10.4230/LIPIcs.ESA.2017.12.
  * [BKS19] A. Becker, P. N. Klein, and A. Schild.  A PTAS for bounded-capacity vehicle routing in planar graphs.  In Algorithms and Data Structures, WADS ‘19, pages 99–111, 2019\.  doi:10.1007/978-3-030-24766-9_8.
  * [BL16] G. Borradaile and H. Le.  Optimal dynamic program for r-domination problems over tree decompositions.  In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, pages 8:1–8:23, 2016.  doi:10.4230/LIPIcs.IPEC.2016.8.
  * [BLMN05] Y. Bartal, N. Linial, M. Mendel, and A. Naor.  On metric ramsey-type phenomena.  Annals of Mathematics, 162(2):643–709, 2005.  doi:10.4007/annals.2005.162.643.
  * [BLW17] G. Borradaile, H. Le, and C. Wulff-Nilsen.  Minor-free graphs have light spanners.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS ’17, pages 767–778, 2017.  doi:10.1109/FOCS.2017.76.
  * [BM04] J. M. Boyer and W. J. Myrvold.  On the cutting edge: Simplified o(n) planarity by edge addition.  J. Graph Algorithms Appl., 8(3):241–273, 2004.  doi:10.7155/jgaa.00091.
  * [BTS94] H. L. Bodlaender, G. Tel, and N. Santoro.  Trade-offs in non-reversing diameter.  Nord. J. Comput., 1(1):111–134, 1994.  See: here.
  * [CAdVK+16] V. Cohen-Addad, É. C. de Verdière, P. N. Klein, C. Mathieu, and D. Meierfrankenfeld.  Approximating connectivity domination in weighted bounded-genus graphs.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 584–597. ACM, 2016.
  * [CFKL20] V. Cohen-Addad, A. Filtser, P. N. Klein, and H. Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  In 61th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 589–600, 2020.  See: conference version, arXiv version,.
  * [CG04] D. E. Carroll and A. Goel.  Lower bounds for embedding into distributions over excluded minor graph families.  In Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pages 146–156, 2004.  doi:10.1007/978-3-540-30140-0\\_15.
  * [CG08] T.-H. H. Chan and A. Gupta.  Small hop-diameter sparse spanners for doubling metrics.  Discrete & Computational Geometry, 41(1):28–44, 2008.  doi:10.1007/s00454-008-9115-5.
  * [CG12] T. H. Chan and A. Gupta.  Approximating TSP on metrics with bounded global growth.  SIAM J. Comput., 41(3):587–617, 2012.  preliminary version published in SODA 2008.  doi:10.1137/090749396.
  * [Cha87] B. Chazelle.  Computing on a free tree via complexity-preserving mappings.  Algorithmica, 2(1-4):337–361, 1987.  doi:10.1007/bf01840366.
  * [CJLV08] A. Chakrabarti, A. Jaffe, J. R. Lee, and J. Vincent.  Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 761–770, 2008.  doi:10.1109/FOCS.2008.79.
  * [CZ00] S. Chaudhuri and C. D. Zaroliagis.  Shortest paths in digraphs of small treewidth. part I: sequential algorithms.  Algorithmica, 27(3):212–226, 2000.  doi:10.1007/s004530010016.
  * [DFHT05] E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos.  Fixed-parameter algorithms for (_k_ , _r_)-center in planar graphs and map graphs.  ACM Trans. Algorithms, 1(1):33–47, 2005.  preliminary version published in ICALP 2003.  doi:10.1145/1077464.1077468.
  * [DH05] E. D. Demaine and M. Hajiaghayi.  Bidimensionality: New connections between FPT algorithms and PTASs.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’05, pages 590–601, 2005.
  * [DHK05] E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi.  Algorithmic graph minor theory: Decomposition, approximation, and coloring.  In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 637–646, 2005.  doi:10.1109/SFCS.2005.14.
  * [DHK11] E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi.  Contraction decomposition in h-minor-free graphs and algorithmic applications.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 441–450, 2011\.  doi:10.1145/1993636.1993696.
  * [DHM07] E. D. Demaine, M. Hajiaghayi, and B. Mohar.  Approximation algorithms via contraction decomposition.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, pages 278–287, 2007.
  * [DM15] A. Das and C. Mathieu.  A quasipolynomial time approximation scheme for euclidean capacitated vehicle routing.  Algorithmica, 73(1):115–142, 2015.  doi:10.1007/s00453-014-9906-4.
  * [DR59] G. B. Dantzig and J. H. Ramser.  The truck dispatching problem.  Management science, 6(1):80–91, 1959.  doi:10.1287/mnsc.6.1.80.
  * [EKM14] D. Eisenstat, P. N. Klein, and C. Mathieu.  Approximating _k_ -center in planar graphs.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 617–627, 2014.  doi:10.1137/1.9781611973402.47.
  * [ELS10] D. Eppstein, M. Löffler, and D. Strash.  Listing all maximal cliques in sparse graphs in near-optimal time.  In International Symposium on Algorithms and Computation, pages 403–414, 2010.  doi:10.1007/978-3-642-17517-6_36.
  * [Epp00] D. Eppstein.  Diameter and treewidth in minor-closed graph families.  Algorithmica, 27(3):275–291, 2000.  doi:10.1007/s004530010020.
  * [FFKP18] A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post.  A (1+$\epsilon$)-embedding of low highway dimension graphs into bounded treewidth graphs.  SIAM J. Comput., 47(4):1667–1704, 2018.  preliminary version published in ICALP 2015.  doi:10.1137/16M1067196.
  * [Fil20a] A. Filtser.  A face cover perspective to $\ell_{1}$ embeddings of planar graphs.  In S. Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1945–1954. SIAM, 2020.  doi:10.1137/1.9781611975994.120.
  * [Fil20b] A. Filtser.  Scattering and sparse partitions, and their applications.  In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 47:1–47:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.47.
  * [Fil21] A. Filtser.  Hop-constrained metric embeddings and their applications.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 492–503. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00056.
  * [Fis95] M. Fisher.  Chapter 1 vehicle routing.  In Handbooks in Operations Research and Management Science, pages 1–33. Elsevier, 1995.  doi:10.1016/s0927-0507(05)80105-7.
  * [FKM15] K. Fox, P. N. Klein, and S. Mozes.  A polynomial-time bicriteria approximation scheme for planar bisection.  In Proceedings of the 47th annual ACM symposium on Theory of Computing, 2015.  doi:10.1145/2746539.2746564.
  * [FKS19] E. Fox-Epstein, P. N. Klein, and A. Schild.  Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘19, page 1069–1088, 2019.  doi:10.1137/1.9781611975482.66.
  * [FL21] A. Filtser and H. Le.  Clan embeddings into trees, and low treewidth graphs.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 342–355. ACM, 2021.  Full version at https://arxiv.org/abs/2101.01146.  doi:10.1145/3406325.3451043.
  * [FL22] A. Filtser and H. Le.  Reliable spanners: Locality-sensitive orderings strike back.  In A. Gupta, editor, STOC ’22: 54rd Annual ACM SIGACT Symposium on Theory of Computing, June 20-24, 2022. ACM, 2022.  to appear, see full version.
  * [FLRS11] F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh.  Bidimensionality and eptas.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 748–759, 2011.
  * [FLSZ18] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Kernelization.  Cambridge University Press, December 2018.  doi:10.1017/9781107415157.
  * [FRT04] J. Fakcharoenphol, S. Rao, and K. Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, November 2004.  preliminary version published in STOC 2003.  doi:10.1016/j.jcss.2004.04.011.
  * [GKK17] L. Gottlieb, A. Kontorovich, and R. Krauthgamer.  Efficient regression in metric spaces via approximate lipschitz extension.  IEEE Trans. Inf. Theory, 63(8):4838–4849, 2017.  preliminary version published in SIMBAD 2013.  doi:10.1109/TIT.2017.2713820.
  * [GKP95] M. Grigni, E. Koutsoupias, and C. H. Papadimitriou.  An approximation scheme for planar graph TSP.  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 640–645, 1995.  doi:10.1109/SFCS.1995.492665.
  * [GNRS04] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair.  Cuts, trees and l${}_{\mbox{1}}$-embeddings of graphs.  Comb., 24(2):233–269, 2004.  doi:10.1007/s00493-004-0015-x.
  * [HBK+03] E. Halperin, J. Buhler, R. M. Karp, R. Krauthgamer, and B. Westover.  Detecting protein sequence conservation via metric embeddings.  Bioinformatics, 19(suppl 1):i122–i129, 07 2003.  doi:10.1093/bioinformatics/btg1016.
  * [HHZ21a] B. Haeupler, D. E. Hershkowitz, and G. Zuzic.  Deterministic tree embeddings with copies for algorithms against adaptive adversaries.  CoRR, abs/2102.05168, 2021.  arXiv:2102.05168.
  * [HHZ21b] B. Haeupler, D. E. Hershkowitz, and G. Zuzic.  Tree embeddings for hop-constrained network design.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 356–369. ACM, 2021.  doi:10.1145/3406325.3451053.
  * [HK85] M. Haimovich and A. H. G. R. Kan.  Bounds and heuristics for capacitated routing problems.  Mathematics of Operations Research, 10(4):527–542, 1985.  doi:10.2307/3689422.
  * [HKRS97] M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian.  Faster shortest-path algorithms for planar graphs.  Journal of Computer and System Sciences, 55(1):3–23, 1997.  doi:10.1006/jcss.1997.1493.
  * [HT84] D. Harel and R. E. Tarjan.  Fast algorithms for finding nearest common ancestors.  SIAM J. Comput., 13(2):338–355, 1984.  doi:10.1137/0213024.
  * [JS22] A. Jayaprakash and M. R. Salavatipour.  Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’22, pages 877–893. 2022.  doi:10.1137/1.9781611977073.37.
  * [KKM+12] M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar.  Efficient distributed approximation algorithms via probabilistic tree embeddings.  Distributed Comput., 25(3):189–205, 2012.  preliminary version published in PODC 2008.  doi:10.1007/s00446-012-0157-9.
  * [KKR12] K. Kawarabayashi, Y. Kobayashi, and B. Reed.  The disjoint paths problem in quadratic time.  Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012\.  doi:10.1016/j.jctb.2011.07.004.
  * [KKS11] K. Kawarabayashi, P. N. Klein, and C. Sommer.  Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs.  In The 38th International Colloquium on Automata, Languages and Programming, ICALP ‘11, pages 135–146, 2011.  doi:10.1007/978-3-642-22006-7_12.
  * [Kle02] P. N. Klein.  Preprocessing an undirected planar network to enable fast approximate distance queries.  In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 820–827, 2002.  See: here.
  * [Kle05] P. N. Klein.  A linear-time approximation scheme for planar weighted TSP.  In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’05, pages 647–657, 2005.  doi:10.1109/SFCS.2005.7.
  * [KLMN05] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor.  Measured descent: a new embedding method for finite metrics.  Geometric and Functional Analysis, 15(4):839–858, 2005.  preliminary version published in FOCS 2004.  doi:10.1007/s00039-005-0527-6.
  * [KLP19] I. Katsikarelis, M. Lampis, and V. T. Paschos.  Structural parameters, tight bounds, and approximation for (k, r)-center.  Discret. Appl. Math., 264:90–117, 2019.  preliminary version published in ISAAC 2017.  doi:10.1016/j.dam.2018.11.002.
  * [KLP20] I. Katsikarelis, M. Lampis, and V. T. Paschos.  Structurally parameterized d-scattered set.  Discrete Applied Mathematics, 2020.  preliminary version published in WG 2018.  doi:10.1016/j.dam.2020.03.052.
  * [Kos82] A. V. Kostochka.  The minimum Hadwiger number for graphs with a given mean degree of vertices.  Metody Diskret. Analiz., (38):37–58, 1982.  doi:10.1090/trans2/132.
  * [LLR95] N. Linial, E. London, and Y. Rabinovich.  The geometry of graphs and some of its algorithmic applications.  Comb., 15(2):215–245, 1995.  preliminary version published in FOCS 1994.  doi:10.1007/BF01200757.
  * [MN07] M. Mendel and A. Naor.  Ramsey partitions and proximity data structures.  Journal of the European Mathematical Society, 9(2):253–275, 2007\.  preliminary version published in FOCS 2006.  doi:10.4171/JEMS/79.
  * [MP15] D. Marx and M. Pilipczuk.  Optimal parameterized algorithms for planar facility location problems using voronoi diagrams.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 865–877, 2015.  doi:10.1007/978-3-662-48350-3\\_72.
  * [MZ21] C. Mathieu and H. Zhou.  A PTAS for capacitated vehicle routing on trees, 2021.  doi:10.48550/ARXIV.2111.03735.
  * [NPSW22] J. Nederlof, M. Pilipczuk, C. M. F. Swennenhuis, and K. Wegrzycki.  Isolation Schemes for Problems on Decomposable Graphs.  In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:20, 2022.  Full version at https://arxiv.org/abs/2105.01465.
  * [NS07] G. Narasimhan and M. H. M. Smid.  Geometric spanner networks.  Cambridge University Press, 2007.  doi:10.1017/CBO9780511546884.
  * [NT12] A. Naor and T. Tao.  Scale-oblivious metric fragmentation and the nonlinear dvoretzky theorem.  Israel Journal of Mathematics, 192(1):489–504, 2012.  doi:10.1007/s11856-012-0039-7.
  * [PY93] C. H. Papadimitriou and M. Yannakakis.  The Traveling Salesman Problem with distances one and two.  Mathematics of Operations Research, 18(1):1–11, 1993.  doi:10.2307/3690150.
  * [Rao99] S. Rao.  Small distortion and volume preserving embeddings for planar and Euclidean metrics.  In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, Miami Beach, Florida, USA, June 13-16, 1999, pages 300–306, 1999.  doi:10.1145/304893.304983.
  * [RS86] N. Robertson and P. Seymour.  Graph minors. v. excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.  doi:https://doi.org/10.1016/0095-8956(86)90030-4.
  * [RS03] N. Robertson and P. D. Seymour.  Graph minors. XVI. Excluding a non-planar graph.  Journal of Combinatoral Theory Series B, 89(1):43–76, 2003.  doi:10.1016/S0095-8956(03)00042-X.
  * [RST94] N. Robertson, P. Seymour, and R. Thomas.  Quickly excluding a planar graph.  62(2):323–348, 1994.  doi:10.1006/jctb.1994.1073.
  * [Sol11] S. Solomon.  An optimal-time construction of sparse euclidean spanners with tiny diameter.  In D. Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 820–839. SIAM, 2011.  doi:10.1137/1.9781611973082.65.
  * [SV88] B. Schieber and U. Vishkin.  On finding lowest common ancestors: Simplification and parallelization.  SIAM Journal on Computing, 17(6):1253–1262, 1988.  doi:10.1137/0217079.
  * [Tal04] K. Talwar.  Bypassing the embedding: algorithms for low dimensional metrics.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 281–290, 2004.  doi:10.1145/1007352.1007399.
  * [Tho84] A. Thomason.  An extremal function for contractions of graphs.  Mathematical Proceedings of the Cambridge Philosophical Society, 95(2):261–265, 1984.  doi:10.1017/s0305004100061521.
  * [Tho97] M. Thorup.  Parallel shortcutting of rooted trees.  Journal of Algorithms, 23(1):139–159, 1997.  doi:10.1006/jagm.1996.0829.
  * [Tho04] M. Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  Journal of the ACM, 51(6):993–1024, 2004.  doi:10.1145/1039488.1039493.
  * [You12] On classes of summable functions and their fourier series.  Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 87(594):225–229, 1912.  doi:10.1098/rspa.1912.0076.