# Colourful matchings

Andrii Arman  Department of Mathematics, Emory University, Atlanta, GA 30322,
USA<EMAIL_ADDRESS>,  Vojtěch Rödl  Department of Mathematics, Emory
University, Atlanta, GA 30322, USA<EMAIL_ADDRESS>and  Marcelo Tadeu
Sales  Department of Mathematics, Emory University, Atlanta, GA 30322, USA
<EMAIL_ADDRESS>
###### Abstract.

Suppose a committee consisting of three members has to match $n$ candidates to
$n$ different positions. Each member of the committee proposes a matching,
however the proposed matchings totally disagree, i.e., every candidate is
matched to three different positions according to three committee members. All
three committee members are very competitive and want to push through as many
of their suggestions as possible. Can a committee always find a compromise — a
matching of candidates to positions such that for every committee member a
third of all candidates are assigned according to that committee member
suggestion?

We will consider an asymptotic version of this question and several other
variants of similar problem. As an application we will consider an embedding
problem — in particular which configurations large Steiner systems always need
to contain.

The second author was supported by NSF grant DMS 1764385

##  1\. Introduction

In this paper we study the following question.

######  Question 1.1.

Let $G$ be a graph on $2n$ vertices that is a union of $k$ edge-disjoint
perfect matchings $M_{1},\ldots,M_{k}$. For which sequences
$a_{1},\ldots,a_{k}$ with $\sum_{i=1}^{k}a_{i}\leq n$ we can always find a new
matching $M$ in $G$ such that $|M\cap M_{i}|\geq a_{i}$ for all $i\in[k]$?

Question 1.1, in particular, is related to the famous Ryser conjecture, which
is equivalent to asking if in every proper edge-colouring of $K_{n,n}$ there
is a rainbow matching, i.e. if for any $n$ disjoint perfect matchings
$M_{1},...,M_{n}$ of $K_{n,n}$ there is a matching $M$, such that $|M\cap
M_{i}|=1$ for all $i\in[n]$.

Keevash, Pokrovskiy, Sudakov and Yepremyan [KPSY] proved that if $K_{n,n}$ is
decomposed into $n$ perfect matchings $M_{1},\ldots,M_{n}$, then there is a
matching $M$ (a rainbow matching) such that $|M\cap M_{i}|\leq 1$ for all
$i\in[n]$ and $M$ has size at least $n-O(\frac{\log n}{\log\log n})$.

Note that the result of Keevash et.al. [KPSY] implies that relaxed version of
Question 1.1 with $a_{1}=\ldots=a_{n}=1$ has affirmative answer: if $K_{n,n}$
is decomposed into $n$ disjoint perfect matchings, then there are
$k=n-O(\frac{\log n}{\log\log n})$ of them, say $M_{1},\ldots,M_{k}$ and a
matching $M$ such that $|M\cap M_{i}|\geq 1$ for all $i\in[k]$.

The following is a central definition for this paper that formalizes a
relaxation of Question 1.1 that we are considering.

######  Definition 1.2.

We say that a sequence of integers $a_{1},\ldots,a_{k}$ is
$(\varepsilon,n)$-happy if there is an integer $\ell\in[k,(1+\varepsilon)k]$
such that for any $\ell$ disjoint perfect matchings of $K_{2n}$ there are $k$
of them $M_{1},\ldots,M_{k}$ and a matching $M$ such that $|M\cap M_{i}|\geq
a_{i}$ for all $i\in[k]$.

We show that a relaxed version of Question 1.1 has an affirmative answer for a
wide variety of sequences, namely we prove the following theorem.

######  Theorem 1.3.

For any $\varepsilon\in(0,1)$ there is $n_{0}$, such that for all integers
$n\geq n_{0}$ the following holds. Let $\\{a_{i}\\}_{i=1}^{k}$ be a sequence
of positive integer such that $\sum a_{i}<(1-\varepsilon)n$ and either

  * (i)

$a_{i}\leq n^{1-\varepsilon}$ for all $i$, or

  * (ii)

$a_{i}\geq n^{\varepsilon}$ for all $i$.

Then sequence $\\{a_{i}\\}_{i=1}^{k}$ is $(\varepsilon,n)$-happy.

While the proof of case (i) of Theorem 1.3 is based on the probabilistic
argument the proof of case (ii) of Theorem 1.3 relies on Alon’s necklace
theorem[Alon].

We will find convenient to divide the proof of Theorem 1.3 by formulating two
separate statements.

######  Theorem 1.4.

For any $\varepsilon\in(0,1)$ there is $n_{1}$ such that for any $n\geq n_{1}$
any sequence $a_{1},\ldots,a_{k}$ with each term at most $n^{1-\varepsilon}$
and such that $\sum_{i=1}^{k}a_{i}<(1-\varepsilon)n$ is
$(\varepsilon,n)$-happy.

We deduce Theorem 1.4 from a slightly more technical Theorem 3.1 in Section 3.

######  Theorem 1.5.

For any $\varepsilon\in(0,1)$ there is $n_{2}$ such that for any $n\geq n_{2}$
any sequence $a_{1},\ldots,a_{k}$ with each term at least $n^{\varepsilon}$
and such that $\sum_{i=1}^{k}a_{i}<(1-\varepsilon)n$ is
$(\varepsilon,n)$-happy.

The proof of Theorem 1.5 relies on Theorem 1.4 and Alon’s necklace theorem
[Alon] and is presented in Section 4.

For sequence $\mathcal{A}=\\{a_{1},\ldots,a_{k}\\}$ such that $a_{i}\geq\alpha
n$ for some real $\alpha$, it can be deduced from Theorem 1.5 that
$\mathcal{A}$ is $(0,n)$-happy (see Corollary 5.1). In particular for the
problem stated in the abstract, Corollary 5.1 of Theorem 1.5 implies that for
any $\varepsilon>0$ and large enough $n$, if disjoint perfect matchings
$M_{1},M_{2},M_{3}$ of $K_{n,n}$ are given, then there is a matching $M$ such
that $|M\cap M_{i}|\geq(\frac{1}{3}-\varepsilon)n$.

In Section 5 we show how Theorem 1.3 is related to a problem of finding large
hypertree in a Steiner triple system. A hypertree is a connected, simple
$3$‐uniform hypergraph in which every two vertices are joined by a unique
path. A Steiner triple system is a $3$‐uniform hypergraph in which every pair
of vertices is contained in exactly one edge. Easy greedy-type argument shows
that any hypertree with at most $n$ vertices can be embedded into any Steiner
triple system with $2n+1$ vertices. Elliot and the second author [ER]
conjectured that the same is true even for larger hypertrees.

######  Conjecture 1.6.

Given $\varepsilon>0$ there is $n_{0}$, such that for any $n\geq n_{0}$, any
hypertree $T$ of order $n$ and any Steiner triple system of order at least
$(1+\varepsilon)n$, $S$ contains $T$ as a subhypergraph.

In [ER] authors proved Conjecture 1.6 for subdivision hypertree. With the
proof based on Corollary 5.1, in Section 5 we will verify the Conjecture 1.6
for another infinite family of hypertrees, which we call “turkeys”.

##  2\. Preliminaries

For positive integer $k$ let $[k]=\\{1,\ldots,k\\}$ and
$[0,k]=\\{0,\ldots,k\\}$. We write $x=y\pm z$ if $x\in[y-z,y+z]$.

We use the following version of Chernoff’s bound (this is a corollary of
Theorem 2.1 of Janson, Łuczak, Rucinski [JLR]).

######  Theorem 2.1.

Let $X\sim\text{Bi}(n,p)$ be a binomial random variable with the expectation
$\mu$, then for $t\leq 3\mu$

$\mathbb{P}(|X-\mu|>t)\leq 2e^{-t^{2}/(4\mu)}.$

The proof of Theorem 1.4 relies on the application of a result by Alon, Kim
and Spencer [AKS] on existence of almost perfect matching in 3-uniform simple
hypergraphs. We use a version of this result stated by Kostochka and Rödl
[KR]***We refer to Theorem 3 from that paper. There is a typo in the
conclusion part of that theorem, where instead of $O(ND^{1/2}\ln^{3/2}D)$
there should be $O(ND^{-1/2}\ln^{3/2}D)$.

######  Theorem 2.2.

For any $K>0$ there exists $D_{0}$ such that the following holds. Let $H$ be a
3-uniform simple hypergraph on $N$ vertices and $D\geq D_{0}$ be such that
$deg(x)=D\pm K\sqrt{D\ln D}$ for all $x\in V(H)$. Then $H$ contains a matching
on $N-O(ND^{-1/2}\ln^{3/2}D)$ vertices.

Here the constant in $O$-notation is depending on $K$ only an is independent
of $N$ and $D$.

The following lemma is the main tool used for the proof of Theorem 1.4. In
Lemma 2.3 the constant in $O$-notation is depending on $K$ and $\delta$ only
an is independent of $m$ and $D$.

######  Lemma 2.3.

For any constant $K$ and $\delta$ there is $D_{0}$ such that the following
holds for any $D\geq D_{0}$, $\Delta=K\sqrt{D\ln D}$ and an integer $m$. Let
$G$ be a graph that is a union of edge disjoint matchings $M_{1},\ldots,M_{b}$
such that:

  * (a)

$deg(v)=D\pm\Delta$ for all $v\in V(G)$.

  * (b)

$|M_{i}|=Dm\pm\Delta m/2$ for all $i\in[b]$.

Then among matchings $M_{1},\ldots,M_{b}$ there are at least
$b^{{}^{\prime}}=b\left(1-O(\frac{\ln^{3/2}D}{D^{1/2}})\right)$ of them, say
$M_{1},\ldots,M_{b^{{}^{\prime}}}$ and a matching $M$ in $G$ such that $|M\cap
M_{i}|\geq\frac{m}{1+\delta}$ for all $i\in[b^{\prime}]$.

###### Proof.

We start with proving the following quick consequence of Theorem 2.2.

######  Claim 2.4.

For any constant $K$ there is $D_{0}$ such that the following holds for any
$D\geq D_{0}$, $\Delta=K\sqrt{D\ln D}$ and integer $m$. Let $G$ be a graph
that is a union of edge disjoint matchings $M_{1},\ldots,M_{b}$ such that:

  * (a)

$deg(v)=D\pm\Delta$ for all $v\in V(G)$.

  * (b)

$|M_{i}|=Dm\pm\Delta m/2$ for all $i\in[b]$

Then there are is a matching $M$ in $G$ containing at least
$mb\left(1-O(\frac{\ln^{3/2}D}{D^{1/2}})\right)$ edges such that $|M\cap
M_{i}|\leq m$ for all $i\in[b]$.

###### Proof of Claim 2.4.

Let $D_{0}$ be provided by Theorem 2.2 with a constant $K$ as input. Assume
$D_{0}$ is large enough so that $D>4\Delta$. Let $G$ be a graph with vertex
set that is a union of edge disjoint matchings $M_{1},\ldots,M_{b}$. Number of
edges in $G$ is equal to $|X|(D\pm\Delta)/2$ (by assumption (a)) and to
$\sum_{i=1}^{b}|M_{i}|=mb(D\pm\Delta/2)$ (by (b)). Hence we may conclude that
$|X|=2mb\pm mb$.

For a given $G$ construct a 3-uniform hypergraph $H$ by arbitrarily splitting
edges of each $M_{i}$ into $m$ groups $C_{i}^{1},\ldots,C_{i}^{m}$ with
$(D\pm\Delta)$ edges in each group (recall (b)). Note, that splitting
$Dm\pm\Delta m/2$ edges into $m$ groups of size $(D\pm\Delta/2)$ might not be
possible, as it may be the case that $|M_{i}|=Dm-\frac{\Delta m}{2}$ is an
integer, but $D-\Delta/2$ is not.

For each such group $C^{j}_{i}$ add a new vertex $y^{j}_{i}$ and construct
$C^{j}_{i}$ hyperedges (triples) by extending each edge in $C^{j}_{i}$ by the
vertex $y_{i}^{j}$. Let $Y$ be a set of new vertices, then $|Y|=mb$ (as each
$M_{i}$ produces $m$ new vertices). The hypergraph $H$ constructed in this way
has $N=|X|+|Y|=\Theta(mb)$ vertices, is linear and each hyperedge has nonempty
intersection with $Y$. Degree of each vertex of $H$ is $D\pm\Delta$, as every
$y_{i}^{j}$ has degree $|C_{i}^{j}|=D\pm\Delta$ and degrees of vertices of $X$
in $H$ are same as in $G$.

Apply Theorem 2.2 to hypergraph $H$ (with $N=\Theta(mb)$) to obtain a
3-uniform matching $M^{\prime}$ that misses at most $O(mbD^{-1/2}\ln^{3/2}D)$
vertices. In particular $M^{\prime}$ misses at most $O(mbD^{-1/2}\ln^{3/2}D)$
vertices in $Y$. Recall that $|Y|=mb$ and each hyperedge of $H$ uses only one
vertex of $Y$, so $M^{\prime}$ has at least $mb-O(mbD^{-1/2}\ln^{3/2}D)$
edges. Let $M$ be a (2-uniform) matching obtained from $M^{\prime}$ by
deleting a vertex in $Y$ from each hyperedge of $M^{\prime}$. Then

$|M|=|M^{\prime}|=mb-O(mbD^{-1/2}\ln^{3/2}D).$

For each $i\in[b]$, matching $M$ intersects $M_{i}$ in at most $m$ edges, as
edges of $M_{i}$ are extended to a union of $m$ stars in $H$ centered at
vertices $y_{i}^{j}$. Therefore, $M$ is a matching such that contains at least
$mb-O(mbD^{-1/2}\ln^{3/2}D)$ edges and such that $|M\cap M_{i}|\leq m$ for all
$i\in[b]$. ∎

Now, to prove Lemma 2.3 we first apply Claim 2.4 to the graph $G$ and obtain a
matching $M$ such that $|M|=mb\left(1-O(\frac{\ln^{3/2}D}{D^{1/2}})\right)$and
$|M\cap M_{i}|\leq m$.

Let $A_{i}=M\cap M_{i}$, and for each $A_{i}$ we define a “deficit” to be
$d_{i}=m-|A_{i}|$. The total deficit of $A_{1},\ldots,A_{b}$ is

$\sum_{i=1}^{b}d_{i}=\sum_{i}^{b}\left(m-|A_{i}|\right)=mb-|M|=O\left(mb\frac{\ln^{3/2}D}{D^{1/2}}\right).$

We now will find many sets $A_{i}$ with small deficit.

We say that set $A_{i}$ is “bad” if it has size smaller than $m/(1+\delta)$,
or in other words if its deficit $d_{i}$ is more than $\delta m/(1+\delta)$.
Since the total deficit is $O(mb\frac{\ln^{3/2}D}{D^{1/2}})$, the number of
“bad” $A_{i}$’s is at most

$\left.O\left(mb\frac{\ln^{3/2}D}{D^{1/2}}\right)\middle/\frac{\delta
m}{1+\delta}\right.=O\left(b\frac{\ln^{3/2}D}{D^{1/2}}\right).$

Finally, we deduce that there is a collection of at least
$b^{{}^{\prime}}=b-O(b\frac{\ln^{3/2}D}{D^{1/2}})$ “good” sets $A_{i}$, say
$A_{1},\ldots,A_{b^{{}^{\prime}}}$, such that $A_{i}\geq m/(1+\delta)$ for
$i\in[b^{{}^{\prime}}]$. This means that for matching $M$ and matchings
$M_{1},\ldots,M_{b^{\prime}}$ we have $|M\cap M_{i}|\geq\frac{m}{1+\delta}$,
finishing the proof of the Lemma. ∎

##  3\. Proof of Theorem 1.4

Theorem 1.4 follows from a slightly more technical Theorem 3.1.

######  Theorem 3.1.

For any $\varepsilon<\frac{1}{10}$ there is $n_{0}$ such that for any $n\geq
n_{0}$ the following holds. Let $\\{a_{i}\\}_{i=1}^{k}$ be a sequence such
that

  * (a)

$\sum_{i=1}^{k}a_{i}<\left(1-\frac{\varepsilon}{2}\right)n$,

  * (b)

$a_{i}\leq n^{1-\varepsilon}$ for all $i\in[k]$,

  * (c)

$k\geq\frac{1}{3}n^{\varepsilon}$,

and additionally, if $k<n^{1/2+\varepsilon}$

  * (d)

$a_{i}\geq k^{-1}n^{1-\varepsilon/400}$ for all $i\in[k]$.

Then sequence $\\{a_{i}\\}_{i=1}^{k}$ is $(\varepsilon,n)$-happy.

We now show how to deduce Theorem 1.4 from Theorem 3.1.

###### Proof of Theorem 1.4.

Assume $\varepsilon$ is given, we will specify $n_{1}$ implicitly. Let
$a_{1},\ldots,a_{k}$ be a sequence of integers such that each $a_{i}\leq
n^{1-\varepsilon}$ and $\sum_{i=1}^{k}{a_{i}}<(1-\varepsilon)n$. We start by
noticing that if a sequence is $(\varepsilon_{0},n)$-happy then it is also
$(\varepsilon,n)$-happy for all $\varepsilon\geq\varepsilon_{0}$. Consequently
it is sufficient to prove Theorem 1.4 for $\varepsilon<\frac{1}{10}.$

We may also assume that $k\geq\frac{1}{3}n^{\varepsilon},$ otherwise
$\sum_{i=1}^{k}a_{i}<\frac{1}{3}n$ and it is not hard to observe that we can
choose desired sets $A_{i}$ greedily from any collection of $k$ matchings.

All together, we may assume that $\varepsilon$ and a sequence
$\\{a_{i}\\}_{i=1}^{k}$ satisfy the following conditions

$a_{i}\leq n^{1-\varepsilon}\text{ for all
}i\in[k],\qquad\varepsilon<\frac{1}{10},\qquad
k\geq\frac{1}{3}n^{\varepsilon},\qquad\sum_{i=1}^{k}{a_{i}}<(1-\varepsilon)n.$

So, sequence $\\{a_{i}\\}_{i=1}^{k}$ satisfies assumptions (a),(b),(c) of
Theorem 3.1.

Therefore, if $k\geq n^{1/2+\varepsilon}$, by Theorem 3.1, sequence
$\\{a_{i}\\}_{i=1}^{k}$ is $(\varepsilon,n)$-happy.

For the rest of the proof assume $k<n^{1/2+\varepsilon}$. The sequence
$\\{a_{i}\\}_{i=1}^{k}$ might not satisfy condition (d) of Theorem 3.1, so we
will construct a new sequence $\\{a_{i}^{{}^{\prime}}\\}_{i=1}^{k}$ that
satisfies assumptions (a)-(d) of Theorem 3.1 and such that
$a_{i}^{{}^{\prime}}\geq a_{i}$ for all $i\in[k]$. Define

$\delta=\varepsilon/100,\qquad\lambda=\varepsilon/400.$

Let

(1) $a=\left\lceil k^{-1}n^{1-\lambda}\right\rceil.$

Now $k\geq\frac{1}{3}n^{\varepsilon}$ by (3), and we have
$k^{-1}n^{1-\lambda}<n^{1-\varepsilon}-1$ for sufficiently large $n$, so

(2) $a\leq n^{1-\varepsilon}.$

Consider a new sequence $\\{a^{\prime}_{i}\\}_{i=1}^{k}$, that is obtained
from $\\{a_{i}\\}_{i=1}^{k}$ by setting for all $i\in[k]$

$a^{\prime}_{i}=\max\\{a_{i},a\\}.$

Note that according to this definition, for all $i\in[k]$ we have

$a_{i}^{\prime}\geq
a\stackrel{{\scriptstyle(\ref{ineq:a1})}}{{\geq}}k^{-1}n^{1-\lambda},$

so sequence $\\{a^{\prime}_{i}\\}_{i=1}^{k}$ satisfies assumption (d) of
Theorem 3.1. The sequence $\\{a^{\prime}_{i}\\}_{i=1}^{k}$ also satisfies
condition (c) of Theorem 3.1, as we assumed $k\geq\frac{1}{3}n^{\varepsilon}$.

######  Claim 3.2.

Sequence $\\{a^{{}^{\prime}}_{i}\\}_{i=1}^{k}$ satisfies the following
properties:

  * (a)

$\sum_{i=1}^{k}a^{\prime}_{i}<(1-\frac{\varepsilon}{2})n.$

  * (b)

$a^{\prime}_{i}\leq n^{1-\varepsilon}\text{ for all }i\in[t].$

  * (c)

If the sequence $\\{a^{{}^{\prime}}_{i}\\}_{i=1}^{k}$ is
$(\varepsilon,n)$-happy, then the sequence $\\{a_{i}\\}_{i=1}^{k}$ is also
$(\varepsilon,n)$-happy.

###### Proof.

Part (a). Since $\sum a_{i}<(1-\varepsilon)n$ and $k<n^{1/2+\epsilon}$, for
large $n$ we have

$\sum_{i=1}^{k}a^{\prime}_{i}\leq\sum_{i=1}^{k}(a+a_{i})=ka+\sum_{i=1}^{k}a_{i}\stackrel{{\scriptstyle\text{(\ref{ineq:a1})}}}{{<}}n^{1-\lambda}+k+\sum_{i=1}^{k}a_{i}<\left(1-\frac{\varepsilon}{2}\right)n.$

Part (b). For each $i\in[k]$ we have $a_{i}\leq n^{1-\varepsilon}$, so

$a^{\prime}_{i}=\max\\{a_{i},a\\}\stackrel{{\scriptstyle(\ref{ineq:a1.5})}}{{\leq}}n^{1-\varepsilon}.$

Part (c). Since $a_{i}^{{}^{\prime}}\geq a_{i}$ for all $i\in[k]$, the
Definition 1.2 ensures that $(\varepsilon,n)$-happiness of
$\\{a_{i}^{\prime}\\}_{i=1}^{k}$ implies $(\varepsilon,n)$-happiness of
$\\{a_{i}\\}_{i=1}^{k}$. ∎

Finally, by Claim 3.2, sequence $\\{a_{i}^{\prime}\\}_{i=1}^{k}$ satisfies
assumptions (a), (b) of Theorem 3.1, so it is $(\varepsilon,n)$-happy.
Therefore, by Claim 3.2(c), sequence $\\{a_{i}\\}_{i=1}^{k}$ is also
$(\varepsilon,n)$-happy.

This finishes the proof of Theorem 1.4. ∎

For the rest of this section we concentrate on proving Theorem 3.1

###  3.1. Choice of constants

Assume $\varepsilon<\frac{1}{10}$ is given, we will specify $n_{1}$
implicitly. Define auxiliary constants

$\delta=\frac{\varepsilon}{100},\qquad\lambda=\frac{\varepsilon}{400}=\frac{\delta}{4},\qquad
K=\frac{4}{\lambda}.$

Let sequence $\\{a_{i}\\}_{i=1}^{k}$ satisfy assumptions of Theorem 3.1, that
is

(3) $\sum_{i=1}^{k}{a_{i}}<\left(1-\frac{\varepsilon}{2}\right)n,\qquad
a_{i}\leq n^{1-\varepsilon}\text{ for all }i\in[k],\qquad
k\geq\frac{1}{3}n^{\varepsilon},$

and in case $k<n^{1/2+\varepsilon}$ additionally

(4) $a_{i}\geq k^{-1}n^{1-\lambda}\text{ for all }i\in[k].$

For the rest of the proof whenever we use $O$-notation, the implicit constant
is dependent on $\varepsilon$ only.

###  3.2. Proof plan of Theorem 3.1.

In order to obtain desired sets $A_{i}=M\cap M_{i}$ for $i\in[k]$ we are going
to apply Lemma 2.3. To illustrate this we first consider following simple case
when sequence $\\{a_{i}\\}_{i=1}^{k}$ is almost regular, that is such that for
all $i\in[k]$

$a_{i}\in\left(\frac{n^{1-\varepsilon}}{1+\delta},n^{1-\varepsilon}\right]$

and $\sum_{i=1}^{k}a_{i}<(1-\varepsilon/2)n$. Let $\ell=(1+\varepsilon)k$ and
assume that $X$ is a set of size $2n$, and $\ell$ disjoint perfect matchings
$M_{1},\ldots,M_{\ell}$ on $X$ are given. Let $G$ be a graph formed by
matchings $M_{1},\ldots,M_{\ell}$. Our goal is to find $k$ matchings, say
$M_{1},\ldots M_{k}$ and sub-matchings $A_{i}\subseteq M_{i}$ such that
$|A_{i}|\geq a_{i}$ and $\bigcup_{i=1}^{k}A_{i}$ is a matching.

We will apply Lemma 2.3 to a subgraph $G^{\prime}$ of $G$ with a large
constant $K$, given $\delta$ and $m=(1+\delta)n^{1-\varepsilon}$. To this end
let $G^{\prime}$ be a random induced subgraph of $G$, where each vertex of $G$
is chosen to be in $G^{\prime}$ independently with probability
$p=\frac{m\ell}{n}$ (note that $p<1$).

Since $deg_{G}(v)=\ell$ for any $v\in V(G)$ we expect the degree of $x$ in
$G^{\prime}$ to be $p\ell$. Let $M_{i}^{\prime}=M_{i}\cap E(G^{\prime})$, then
we expect $|M_{i}^{\prime}|$ to be $p^{2}n=p\ell m$. Therefore for $D=p\ell$,
$\Delta=K\sqrt{D\ln D}$ and $b=\ell$, as an easy consequence of Chernoff
bound, we infer that with a positive probability all of the following
properties hold for $G^{\prime}$:

  * •

$deg_{G^{\prime}}(v)=D\pm\Delta$ for all $v\in V(G^{\prime})$.

  * •

$|M^{\prime}_{i}|=Dm\pm\Delta m/2$ for all $i\in[b]$.

Now, apply Lemma 2.3 to $G^{\prime}$ to obtain a collection of
$b^{\prime}=\ell(1-O(\frac{\ln^{3/2}D}{D^{1/2}}))$ vertex disjoint matchings,
say $A_{1},\ldots,A_{b^{\prime}}$ such that $A_{i}\subseteq M_{i}$ and
$|A_{i}|\geq m/(1+\delta)$ for $i\in[b^{\prime}]$. It remains to notice that
$\ell\geq k\geq\frac{1}{3}n^{\varepsilon}$, $p\geq\frac{1}{3}$ and so
$D=p\ell\geq\frac{1}{9}n^{\varepsilon}$. So for large enough $n$ we have
$b^{\prime}\geq k$. Therefore matchings $A_{1},\ldots,A_{k}$ are such that
$|A_{i}|\geq n^{1-\varepsilon}\geq a_{i}$ for all $i$ and
$\bigcup_{i=1}^{k}A_{i}$ is a matching.

For a general sequence $\\{a_{i}\\}_{i=1}^{k}$ we want to adopt the approach
of the previous “simple” case when all the $a_{i}$’s are almost equal. To this
end we will group $a_{i}$’s in $t=O(\ln n)$ sets $I_{1},\ldots I_{t}$, so that
inside each set $I_{j}$ the elements do not differ much (this is done in Step
1 of formal proof). This way we will have for each group similar starting
position as in the “simple” case. Let $n_{j}$ be the number of elements of
sequence $\\{a_{i}\\}_{i=1}^{k}$ in $I_{j}$. For notation convenience let the
elements of $\\{a_{i}\\}_{i=1}^{k}$ in $I_{j}$ form a sequence
$\\{a^{i}_{j}\\}_{i=1}^{n_{j}}$.

Next, we define two sequences $m_{1},\ldots,m_{t}$ (in Step 1) and
$b_{1},\ldots,b_{t}$ (in Step 2) that will be used as an input values for $m$
and $b$ in Lemma 2.3. Some technical but crucial properties of those sequences
are:

  * (a)

$\lceil m_{j}/(1+\delta)\rceil\geq\max\\{x:x\in I_{j}\\}$ for all $j$.

  * (b)

$b_{j}\geq n_{j}+m_{j}^{-1/2}n^{\lambda+1/2}$ if $n_{j}\neq 0$.

Here we also choose $\ell=\sum b_{j}$ and in Claim 3.8 we show that
$\ell\leq(1+\varepsilon)k$.

Finally in Step 3 of the proof, for $G$ that is a union of $\ell$ matchings on
set $X$ we construct subgraphs $G_{1},\ldots,G_{t}$ of $G$ in the following
way. We first partition collection of matchings $M_{1},\ldots,M_{\ell}$ into
sub-collections $\mathcal{M}_{1},\ldots,\mathcal{M}_{t}$ so that each
$|\mathcal{M}_{j}|=b_{j}$. We also set, after relabeling,
$\mathcal{M}_{j}=\\{M_{j}^{1},\ldots,M_{j}^{b_{j}}\\}$. Then we partition
vertex set $X$ into sets $X_{0},\ldots,X_{t}$ (vertices of $X_{0}$ are
leftover vertices that will not be used). Finally $G_{j}$ is a defined to be a
graph induced by edges of $\mathcal{M}_{j}$ on $X_{j}$.

In Claim 3.11 it is shown that we can find partition $X$ so that every $G_{j}$
satisfies all conditions necessary to apply Lemma 2.3. Claim 3.11 is proved by
considering a random partition of $X$. We then apply Lemma 2.3 to a graph
$G_{j}$ with $m=m_{j}$, $b=b_{j}$ and $D=D_{j}=b_{j}^{2}m_{j}/n$.

An application of Lemma 2.3 to each $G_{j}$ yields the following: there are at
least
$b_{j}^{\prime}=b_{j}\left(1-O(\frac{\ln^{3/2}D_{j}}{D_{j}^{1/2}})\right)$
matchings, say $M^{1}_{j},\ldots,M^{b_{j}^{\prime}}_{j}$ and sets
$A^{i}_{j}\subseteq M^{i}_{j}$ for $i\in[b_{j}^{\prime}]$ such that
$|A^{i}_{j}|\geq\frac{m_{j}}{1+\delta}$ fo all $i\in[b_{j}^{\prime}]$ and that
$\bigcup_{i=1}^{b_{j}^{\prime}}A^{i}_{j}$ is a matching in $G_{j}$.

We will prove, that our choice of $b_{j}$ (see (b) above) will guarantee for
large enough $n$, that $b^{\prime}_{j}\geq n_{j}$ for each $j\in[t]$. As
mentioned above there are $b^{\prime}_{j}$ sets $A_{j}^{i}$’s. On the other
hand, $n_{j}$ is equal to the number of elements of sequence
$\\{a_{i}\\}_{i=1}^{k}$ in set $I_{j}$ (also recall that those elements were
labeled as $\\{a^{1}_{j},\ldots,a_{j}^{n_{j}}\\}$). So every element
$a^{i}_{j}\in I_{j}$ with $i\in[n_{j}]$ can be put in correspondence with the
matching $A_{j}^{i}$.

By Lemma 2.3 we have that $|A_{j}^{i}|\geq m_{j}/(1+\delta)$. Since
$a_{j}^{i}\in I_{j}$, it follows from property (a) that $|A_{j}^{i}|\geq
a^{i}_{j}$ for all $j\in[t]$, $i\in[n_{j}]$. Finally,
$M=\bigcup_{j=1}^{t}\bigcup_{i=1}^{n_{j}}A_{j}^{i}$ is a desired matching
since all $A_{j}^{i}$’s are vertex disjoint.

###  3.3. Formal proof of Theorem 3.1.

Recall that the proof of Theorem 3.1 is divided into three steps: construction
of sets $I_{1},\ldots,I_{t}$ and sequence $\\{m_{j}\\}_{j=1}^{t}$;
construction of sequence $\\{b_{j}\\}_{j=1}^{t}$; and construction of
subgraphs $G_{1},\ldots,G_{t}$ with a subsequent application of Lemma 2.3 to
each of $G_{j}$.

Step 1: In this step we will construct sets $I_{1},\ldots,I_{t}$ and a
sequence $\\{m_{1},\ldots,m_{t}\\}$. Let $I$ be the set of integers in
$[1,n^{1-\varepsilon}]$, we cover $I$ by sets $I_{1},\ldots,I_{t}$. Recall
that $\delta=\varepsilon/100$, $\lambda=\delta/4$ and choose an integer

$C=\left\lceil\frac{1}{\delta}\right\rceil.$

There will be a special treatment of integers that are smaller than $C$.

######  Definition 3.3.

Define the sets

$I_{j}=\\{j\\}\text{ for }j\in[C]$

and for $j\in{\mathbb{N}}$ define

$I_{C+j}=\left(C(1+\delta)^{j-1},C(1+\delta)^{j}\right]\cap\mathbb{N}.$

Define $t$ to be the smallest integer such that $C(1+\delta)^{t-C}\geq
n^{1-\varepsilon}$. Notice that the choice of $C$ guarantees that every
$I_{j}$ for $j\in[t]$ is nonempty. Choice of $t$ guarantees that
$I_{1},\ldots,I_{t}$ cover $I=[1,n^{1-\varepsilon}]$ and that $t=O(\ln n)$.

######  Definition 3.4.

Define $m_{j}=j$ if $j\leq C$. If $j>C$ define

$m_{j}=\min\\{x\in\mathbb{N}:x\in I_{j+2}\\}.$

Notice that $\\{m_{j}\\}_{j=1}^{t}$ is an increasing sequence. We also need
the following observation about sequence $\\{m_{j}\\}_{j=1}^{t}$.

######  Claim 3.5.

If $j\in[C+1,t]$ and $x\in I_{j}$, then

$m_{j}\in[(1+\delta)x,(1+\delta)^{3}x].$

If $x\in I_{j}$ with $j\leq C$, then $m_{j}=x=j$.

###### Proof.

If $x\in I_{j}$ with $j>C$, then

$C(1+\delta)^{j-C-1}\leq x\leq C(1+\delta)^{j-C},$ $C(1+\delta)^{j-C+1}\leq
m_{j}\leq C(1+\delta)^{j-C+2}.$

So if $x\in I_{j}$ for $j>C$ then

$(1+\delta)x\leq m_{j}\leq(1+\delta)^{3}x.$

The second statement of the Claim is trivial since $I_{j}=\\{j\\}$ and
$m_{j}=j$ when $j\leq C$. ∎

Step 2: The second step of the proof consists of constructing sequences
$n_{1},\ldots,n_{t}$ and $b_{1},\ldots,b_{t}$.

######  Definition 3.6.

Define $n_{j}$ to be the number of elements of $\\{a_{i}\\}_{i=1}^{k}$ in set
$I_{j}$ for all $j\in[t]$. In other words

$n_{j}=|\\{i\in[k]:a_{i}\in I_{j}\\}|.$

Define a sequence $\\{a^{i}_{j}\\}_{i=1}^{n_{j}}$ to consist of all elements
of $\\{a_{i}\\}_{i=1}^{k}$ that are in $I_{j}$.

Notice that according to this definition, a sequence $\\{a_{i}\\}_{i=1}^{k}$
is partitioned into $t$ sequences $\\{a^{i}_{j}\\}_{i=1}^{n_{j}}$ with
$j\in[t]$. Additionally we have

(5) $k=\sum_{j=1}^{t}n_{j}.$

Now we define sequence $b_{1},\ldots,b_{t}$. Recall that $\lambda=\delta/4$.

######  Definition 3.7.

For $j\in[t]$, set $b_{j}=n_{j}+\lceil m_{j}^{-1/2}n^{\lambda+1/2}\rceil$ if
$n_{j}\neq 0$, and set $b_{j}=0$ if $n_{j}=0$.

Finally, we set

(6) $\ell=\sum_{j=1}^{t}b_{j}.$

The following Claim proves that $\ell$ is at most $(1+\varepsilon)k$.

######  Claim 3.8.

We have $\ell-k\leq\varepsilon k$.

###### Proof.

First, $\ell-k$ is equal to $\sum_{j=1}^{t}(b_{j}-n_{j})$ by (5) and (6). For
all $j\in[t]$, according to Definition 3.7,

$b_{j}-n_{j}\leq m_{j}^{-1/2}n^{\lambda+1/2}+1.$

Case 1. Consider the case $k\geq n^{1/2+\varepsilon}$ first. Since each
$m_{j}$ is a positive integer,

$\ell-k=\sum_{j=1}^{t}{b_{j}-n_{j}}\leq\sum_{j=1}^{t}1+n^{\lambda+1/2}m_{j}^{-1/2}\leq
t+tn^{\lambda+1/2}.$

Recall that $t=O(\ln n)$ and $\lambda<\varepsilon$, so for large enough $n$,

$\ell-k=O(\ln n)n^{\lambda+1/2}\leq\varepsilon
n^{1/2+\varepsilon}\leq\varepsilon k.$

This finishes the proof of the Claim for case $k\geq n^{1/2+\varepsilon}$.

Case 2. Now we consider the case $k<n^{1/2+\varepsilon}$. In this case,
$k^{-1}n^{1-\lambda}\geq n^{1/2-\varepsilon-\lambda}$ and sequence
$\\{a_{i}\\}_{i=1}^{k}$ satisfies property (4), so for all $i\in[k]$ we have

(7) $a_{i}\geq n^{1/2-\varepsilon-\lambda}.$

Next we will define an integer $j_{0}$ and show that $n_{j}=0$ for all
$j<j_{0}$.

To this end consider the smallest $j_{0}\in[t]$, such that

(8) $m_{j_{0}}\geq(1+\delta)k^{-1}n^{1-\lambda}.$

In order to observe that such $j_{0}$ exists we notice that
$k\geq\frac{1}{3}n^{\varepsilon}$ (by (3)) and so by Definition 3.4 we have
for sufficiently large $n$

$m_{t}\geq n^{1-\varepsilon}\geq(1+\delta)k^{-1}n^{1-\lambda}.$

Therefore there is $j_{0}\leq t$ that satisfies (8).

For $i\in[k]$, by (7) we have $a_{i}\geq n^{1/2-\varepsilon-\lambda}$, so for
large enough $n$, if $a_{i}\in I_{j}$, then $j>C$ (see Definition 3.3).

Therefore if $a_{i}\in I_{j}$, by applying Claim 3.5 with $x=a_{i}$, we get

$m_{j}\geq(1+\delta)a_{i}\stackrel{{\scriptstyle\text{(\ref{ineq:scase})}}}{{\geq}}(1+\delta)k^{-1}n^{1-\lambda}.$

Comparing this inequality with definition of $j_{0}$ (8) we get that if
$a_{i}\in I_{j}$ for some $i\in[k]$, then $j\geq j_{0}$.

Therefore for all $j<j_{0}$ there are no elements of $\\{a_{i}\\}_{i=1}^{k}$
in sets $I_{j}$, which implies that $n_{j}=0$ and therefore $b_{j}=0$ (by
Definition 3.7) for all $j<j_{0}$.

Finally, since $\\{m_{j}\\}_{j=1}^{t}$ is increasing, provided $n$ is large
enough

$\ell-k=\sum_{j=1}^{t}b_{j}-n_{j}=\sum_{j=j_{0}}^{t}b_{j}-n_{j}\stackrel{{\scriptstyle\text{Def
}\ref{def:bj}}}{{\leq}}\sum_{j=j_{0}}^{t}1+n^{\lambda+1/2}m_{j}^{-1/2}\leq
t+tn^{\lambda+1/2}m_{j_{0}}^{-1/2}.$

Using $t=O(\ln n)$ and inequality (8), for large enough $n$

$\ell-k=O(\ln n)n^{\lambda+1/2}(k^{1/2}n^{\lambda/2-1/2})=O(\ln
n)k^{1/2}n^{3\lambda/2}\leq k^{1/2}n^{3\varepsilon/8}.$

Now, recall that by (3) we have $k\geq\frac{1}{3}n^{\varepsilon}$, so

$\ell-k\leq 3k^{1/2}k^{3/8}<\varepsilon k$

for large enough $n$. So $\ell-k\leq\varepsilon k$ in both cases.

∎

The next Claim will be used in Step 3 of the proof.

######  Claim 3.9.

For large enough $n$,

$\sum_{j=1}^{t}b_{j}m_{j}\leq\left(1-\frac{\varepsilon}{4}\right)n.$

###### Proof.

According to Definition 3.7

$\sum_{i=1}^{t}b_{j}m_{j}\leq\sum_{i=1}^{t}n_{j}m_{j}+\sum_{j=1}^{t}\left(1+n^{\lambda+1/2}m_{j}^{-1/2}\right)m_{j}.$

Let $S_{1}=\sum_{i=1}^{t}n_{j}m_{j}$ and
$S_{2}=\sum_{j=1}^{t}\left(1+n^{\lambda+1/2}m_{j}^{-1/2}\right)m_{j}$.

We now estimate $S_{1}$. Claim 3.5 implies that if for some $i\in[k]$ we have
$a_{i}\in I_{j}$, then $m_{j}\leq(1+\delta)^{3}a_{i}$. Since each $I_{j}$
contains exactly $n_{j}$ elements of sequence $\\{a_{i}\\}_{i=1}^{k}$ (by
Definition 3.6), we infer

$n_{j}m_{j}=\sum_{i\in[t],\;a_{i}\in I_{j}}m_{j}\leq\sum_{i\in[t],\;a_{i}\in
I_{j}}(1+\delta)^{3}a_{i}.$

Since every member of $\\{a_{i}\\}_{i=1}^{k}$ is in some $I_{j}$, we have

$S_{1}=\sum_{j=1}^{t}n_{j}m_{j}\leq\sum_{i=1}^{k}(1+\delta)^{3}a_{i}\stackrel{{\scriptstyle(\ref{ineq:many})}}{{\leq}}(1+\delta)^{3}\left(1-\frac{\varepsilon}{2}\right)n\leq\left(1-\frac{3\varepsilon}{8}\right)n.$

Now we estimate $S_{2}$. Recall that sequences $\\{m_{j}\\}_{j=1}^{t}$ is
increasing. We also have $n^{1-\varepsilon}\in I_{t}$, so Claim 3.5 implies
that $m_{t}\leq(1+\delta)^{3}n^{1-\varepsilon}$. So for all $j\in[t]$, we have
$m_{j}\leq(1+\delta)^{3}n^{1-\varepsilon}$. Therefore

$S_{2}=\sum_{j=1}^{t}\left(1+n^{\lambda+1/2}m_{j}^{-1/2}\right)m_{j}=\sum_{j=1}^{t}m_{j}+\sum_{j=1}^{t}n^{\lambda+1/2}m_{j}^{1/2}=O(tn^{1-\varepsilon})+O(tn^{\lambda+1/2}n^{1/2-\varepsilon/2}).$

Recall that $t=O(\ln n)$, so for large enough $n$ we have

$S_{2}=o(n)\leq\frac{\varepsilon}{8}n.$

Finally, combining the upperbounds on both sums we get

$\sum_{j=1}^{t}b_{j}m_{j}\leq
S_{1}+S_{2}\leq\left(1-\frac{3\varepsilon}{8}\right)n+\frac{\varepsilon}{8}n=\left(1-\frac{\varepsilon}{4}\right)n.$

∎

Step 3. Now, let $M_{1},\ldots,M_{\ell}$ be disjoint perfect matchings on
$K_{2n}$. Assume that $G$ is a graph formed by $\ell$ disjoint perfect
matchings $M_{1},\ldots,M_{\ell}$ on vertex set $X$ of size $2n$.

######  Definition 3.10.

For a collection of matchings $\mathcal{M}\subseteq\\{M_{1},\ldots,M_{b}\\}$
and a set $X^{\prime}\subseteq X$ define $G[X^{\prime},\mathcal{M}]$ to be the
subgraph of $G$ formed by the edges $e=xy$, where $x,y\in X^{\prime}$ and
$xy\in M$ for some $M\in\mathcal{M}$.

Let $\mathcal{M}_{1},\ldots,\mathcal{M}_{t}$ be a partition of a set
$\\{M_{1},\ldots,M_{k}\\}$ such that $|\mathcal{M}_{j}|=b_{j}$ for all
$j\in[t]$. Recall that elements of $\mathcal{M}_{j}$ were also labeled by
$M_{j}^{i}$, so that $\mathcal{M}_{j}=\\{M^{1}_{j},\ldots,M^{b_{j}}_{j}\\}$
for all $j\in[t]$.

The following Claim allows us to construct vertex disjoint subgraphs
$G_{1},\ldots,G_{t}$ of $G$, to which we will subsequently apply Lemma 2.3.

To this end, for $j\in[t]$ let

$D_{j}=b_{j}^{2}m_{j}/n\;\;\;\;\text{and}\;\;\;\;\Delta_{j}=K\sqrt{D_{j}\ln
D_{j}}.$

######  Claim 3.11.

There is partition of $X$ into parts $X_{0},X_{1},\ldots,X_{t}$, such that for
graphs $G_{1},\ldots,G_{t}$, defined by $G_{j}=G[X_{j},\mathcal{M}_{j}]$, the
following holds for all $j\in[t]$

  * •

$deg_{G_{j}}(v)=D_{j}\pm\Delta_{j}$ for all $v\in V(G_{j})$.

  * •

$|M_{j}^{i}\cap E(G_{j})|=D_{j}m_{j}\pm\frac{\Delta_{j}m_{j}}{2}$ for all
$i\in[b_{j}]$.

###### Proof.

Define $p_{j}=m_{j}b_{j}/n$ for $j\in[t]$. Then $D_{j}=p_{j}b_{j}$ for all
$j\in[t]$. Note that Claim 3.9 implies that $\sum_{j=1}^{t}p_{j}\leq
1-\varepsilon/4$, so each $p_{j}\in[0,1)$. Set $p_{0}=1-\sum_{j=1}^{t}p_{j}$.
Consider random partition of $X$ into parts $X_{0},X_{1},\ldots,X_{t}$ such
that each vertex $x\in X$ ends up in set $X_{j}$ with probability $p_{j}$
independently of other vertices.

For all $j\in[t]$ and $v\in V(G_{j})$, degree of $v$ in $G[X,\mathcal{M}_{j}]$
is equal to $|\mathcal{M}_{j}|=b_{j}$. So $deg_{G_{j}}(v)\sim Bi(b_{j},p_{j})$
for all $j\in[t]$ and $v\in V(G_{j})$.

Now, for any edge, probability that both of its end point belong to $V(G_{j})$
is equal to $p_{j}^{2}$. So $|M\cap E(G_{j})|\sim Bi(n,p_{j}^{2})$ for all
$j\in[t]$ and $M\in\mathcal{M}_{j}$.

Notice that if $b_{j}=0$ (in this case $n_{j}=0$), then $p_{j}=0$,
$|X_{j}|=0$, so in this case $G_{j}$ is an empty graph and it satisfies both
conclusions of the Claim. From now on we may assume that all graphs $G_{j}$
are such that $b_{j}\neq 0$.

Calculating the expectation of binomial random variable gives for all
$j\in[t],$ $v\in V(G_{j})$ and $i\in[b_{j}]$:

  * •

$\mathbb{E}(deg_{G_{j}}(v))=b_{j}p_{j}=b_{j}^{2}m_{j}/n=D_{j}$

  * •

$\mathbb{E}(M^{i}_{j}\cap E(G_{j}))=np_{j}^{2}=m_{j}(b_{j}p_{j})=m_{j}D_{j}.$

Recall that if $b_{j}\neq 0$, then $b_{j}\geq m_{j}^{-1/2}n^{\lambda+1/2}$ by
Definition 3.7, so

(9) $D_{j}=\frac{b_{j}^{2}m_{j}}{n}\geq n^{2\lambda}.$

So for any $j\in[t]$ and $v\in V(G_{j})$ applying Chernoff bound to
$deg_{G_{j}}(v)$ gives that for large enough $n$

$\mathbb{P}(|deg_{G_{j}}(x)-D_{j}|>\Delta_{j})\leq 2e^{-K^{2}\ln
D_{j}/4}\stackrel{{\scriptstyle(\ref{ineq:Dj})}}{{\leq}}2n^{-\frac{K^{2}\lambda}{2}}.$

Similarly, for all $j\in[t]$ and $i\in[b_{j}]$

$\mathbb{P}(||M_{j}^{i}\cap E(G_{j})|-m_{j}D_{j}|>\Delta_{j}m_{j}/2)\leq
2e^{-K^{2}m_{j}\ln D_{j}/16}.$

Recall that $m_{j}\geq 1$ for all $j\in[t]$, so

$\mathbb{P}(||M_{j}^{i}\cap E(G_{j})|-m_{j}D_{j}|>\Delta_{j}m_{j}/2)\leq
2e^{-K^{2}\ln
D_{j}/16}\stackrel{{\scriptstyle(\ref{ineq:Dj})}}{{\leq}}2n^{-\frac{K^{2}\lambda}{8}}.$

Finally, let $p$ be the probability that a random partition satisfies the
conclusion of the Claim for all graphs $G_{j}$ with $j\in[t]$. There are at
most $2tn$ random variables $deg_{G_{j}}(v)$ and at most $tn$ random variables
$|M_{j}^{i}\cap E(G_{j})|$. So by union bound

$p\geq 1-t(2n)2n^{-\frac{K^{2}\lambda}{2}}-t(n)2n^{-\frac{K^{2}\lambda}{8}}.$

Recall that $K=4/\lambda$ and $t=O(\ln n)$, so for $n$ large enough we have
$p=1-o(1)$.

Therefore the random partion above satisfies the conclusion of Claim 3.11 with
high probability. ∎

Let $X$ be partitioned as in Claim 3.11, then the corresponding graphs $G_{j}$
with $j\in[t]$ satisfy the assumptions of the Lemma 2.3.

So, for each $j\in[t]$ we can apply Lemma 2.3 with $G=G_{j}$, $D=D_{j}$,
$b=b_{j}$, matchings $\mathcal{M}_{j}\cap E(G_{j})$ and $m=m_{j}$. We obtain
at least
$b_{j}^{{}^{\prime}}=b_{j}\left(1-O(\frac{\ln^{3/2}D_{j}}{D_{j}^{1/2}})\right)$
matchings, say $M^{1}_{j},\ldots,M_{j}^{b_{j}^{{}^{\prime}}}$ and sets
$\\{A^{i}_{j}\\}_{i=1}^{b^{{}^{\prime}}_{j}}$ such that

  * (L1)

$A_{j}^{i}\subseteq M_{j}^{i}\bigcap E(G_{j})$ for all
$i\in[b^{{}^{\prime}}_{j}]$,

  * (L2)

$|A^{i}_{j}|\geq\frac{m_{j}}{1+\delta}$ for $i\in[b^{{}^{\prime}}_{j}]$,

  * (L3)

$\bigcup_{i=1}^{b_{j}^{\prime}}A^{i}_{j}$ is a matching.

Next, we show the for each $j\in[t]$ there are more matchings $A_{j}^{i}$ than
there are elements of $\\{a_{i}\\}_{i=1}^{k}$ in $I_{j}$.

######  Claim 3.12.

For all $j\in[t]$ and large enough $n$, we have $b^{\prime}_{j}\geq n_{j}$.

###### Proof.

Recall that,

$b^{{}^{\prime}}_{j}=b_{j}\left(1-O\left(\frac{\ln^{3/2}D_{j}}{D_{j}^{1/2}}\right)\right)=b_{j}-O\left(\frac{b_{j}\ln^{3/2}D_{j}}{D_{j}^{1/2}}\right).$

So by Definition 3.7 and since $D_{j}=b_{j}^{2}m_{j}/n$ we have

$b^{{}^{\prime}}_{j}\geq
n_{j}+m_{j}^{-1/2}n^{\lambda+1/2}-O\left(\frac{n^{1/2}\ln^{3/2}D_{j}}{m_{j}^{1/2}}\right).$

Now, by Claim 3.9, $b_{j}m_{j}\leq n$, and since $m_{j}\geq 1$, we have

$D_{j}=b_{j}^{2}m_{j}/n\leq b^{2}_{j}m_{j}^{2}/n\leq n.$

So for large enough $n$, we have

$b^{\prime}_{j}\geq
n_{j}+m_{j}^{-1/2}n^{\lambda+1/2}-O\left(m_{j}^{-1/2}n^{1/2}\ln^{3/2}n\right)\geq
n_{j}.$

∎

Recall that $n_{j}$ is equal to the number of elements of sequence
$\\{a_{i}\\}_{i=1}^{k}$ in set $I_{j}$ and those elements were also labeled as
$\\{a^{1}_{j},\ldots,a_{j}^{n_{j}}\\}$.

We proved that for all $j\in[t]$ there are $b_{j}^{{}^{\prime}}$ sets
$\\{A_{j}^{1},\ldots A_{j}^{b_{j}^{{}^{\prime}}}\\}$ that satisfy (L1), (L2),
(L3). Consequently, by Claim 3.12, for any $j\in[t]$ and $i\in[n_{j}]$ set
$A_{j}^{i}$ exists.

######  Claim 3.13.

For every $j\in[t]$ and $i\in[n_{j}]$ we have $|A_{j}^{i}|\geq a_{j}^{i}$.

###### Proof.

By (L2) we have $|A_{j}^{i}|\geq m_{j}/(1+\delta),$ so

$|A_{j}^{i}|\geq\left\lceil\frac{m_{j}}{1+\delta}\right\rceil.$

Also recall that $a_{j}^{i}\in I_{j}$.

If $j\geq C+1$, since $a_{j}^{i}\in I_{j}$, Claim 3.5 yields that
$\frac{m_{j}}{1+\delta}\geq a^{i}_{j}$. Hence $|A_{j}^{i}|\geq a^{i}_{j}$ in
this case.

If $j\leq C$, then $m_{j}=j=a_{j}^{i}$. In Step 1 we defined
$C=\lceil\frac{1}{\delta}\rceil$, so due to $j\leq C$ we have
$\frac{j}{1+\delta}>j-1$. Therefore in case $j\leq C$ we have
$\lceil\frac{j}{1+\delta}\rceil=j$, and so

$|A_{j}^{i}|\geq\left\lceil\frac{m_{j}}{1+\delta}\right\rceil=\left\lceil\frac{j}{1+\delta}\right\rceil=j=a_{j}^{i}.$

∎

To summarize our steps toward the proof of Theorem 3.1, for a given sequence
$\\{a_{i}\\}_{i=1}^{k}$ we split it into $t$ sub-sequences
$\\{a_{j}^{i}\\}_{i=1}^{n^{j}}$ with $j\in[t]$. Then, for given $\ell$
disjoint perfect matchings $M_{1},\ldots,M_{\ell}$ on set $X$ of size $2n$ we
found $k$ perfect matchings, labeled $\\{M_{j}^{i}\\}_{j=1,i=1}^{t,n_{j}}$,
and submatchings $A_{j}^{i}\subseteq M_{j}^{i}$.

From Claim 3.13 it follows that for all $j\in[t]$ and $i\in[n_{j}]$ we have
$|A_{j}^{i}|\geq a_{j}^{i}$.

Notice that for a given $j\in[t]$, $\bigcup_{i=1}^{n_{j}}A_{j}^{i}$ is a
matching (guaranteed by (L3) and Claim 3.12) so any two $A_{j}^{i}$ and
$A_{j}^{i^{\prime}}$ are vertex disjoint. Also all vertices of each
$A_{j}^{i}$ belong to $V(G_{j})$ by (L1). Since $G_{1},\ldots,G_{t}$ are
vertex disjoint we get that $A_{j}^{i}$ and $A_{j^{\prime}}^{i^{\prime}}$ are
also vertex disjoint for $j\neq j^{\prime}$. Therefore, all $A_{j}^{i}$’s are
vertex disjoint matchings and so
$M=\bigcup_{j=1}^{t}\bigcup_{i=1}^{n_{j}}A_{j}^{i}$ is a matching. This
finishes the proof of Theorem 3.1.

##  4\. Proof of Theorem 1.5

Proof of Theorem 1.5 relies on Theorem 1.4 and an application of the following
Necklace Theorem by Alon [Alon].

######  Theorem 4.1.

Consider an open necklace (a string of beads) in which beads are of $\ell$
different colors and the number of beads of each color is divisible by $q$.

Then a group of $q$ thieves can cut the necklace between the beads in at most
$\ell(q-1)$ places and distribute the obtained interval pieces between
themselves in such a way that each thieve will get the same number of beads of
each color.

For $\varepsilon>0$ and sufficiently large $n$, let $a_{1},\ldots,a_{k}$ be a
sequence of integers such that $\sum a_{i}<(1-\varepsilon)n$ and $a_{i}\geq
n^{\varepsilon}$ for all $i\in[k]$.

We may assume that $\\{a_{i}\\}_{i=1}^{k}$ is non-decreasing, and that

(10) $\sum_{i=1}^{k}a_{i}\geq\frac{n}{3},$

Indeed, in case $\sum_{i=1}^{k}a_{i}<\frac{n}{3}$, for any $k$ matchings
$M_{1},\ldots,M_{k}$ we can find desired subsets $A_{1},\ldots,A_{k}$
greedily.

The goal of this section is to show that sequence $\\{a_{i}\\}_{i=1}^{k}$ is
$(\varepsilon,n)$-happy. Note that Theorem 1.4 implies that for any
$\delta>0$, provided $n$ is large, every positive sequence
$\\{b_{i}\\}_{i=1}^{\ell}$ that satisfies $\sum b_{i}\leq(1-\delta)n$ and
$b_{i}\leq n^{1-\delta}$ is $(\delta,n)$-happy.

###  4.1. Proof plan

The proof idea Therorem 1.5 is to modify initial sequence
$\\{a_{i}\\}_{i=1}^{k}$ by a series of ‘non-happiness’ preserving operations
until we obtain a happy sequence, this would imply that initial sequence
$\\{a_{i}\\}_{i=1}^{k}$ is also happy. More specifically, let
$\mathcal{A}_{0}=\\{a_{i,0}\\}_{i=1}^{k}$ be $\\{a_{i}\\}_{i=1}^{k}$, we
recursively define new non-decreasing sequences
$\mathcal{A}_{1},\ldots,\mathcal{A}_{s}$ (here $s<k$) such that each sequence
$\mathcal{A}_{j}$ consists of $k-j$ elements for $j\in[0,s]$ and the last
sequence $\mathcal{A}_{s}$ is $(\varepsilon,n)$-happy.

The recursive definition goes as follows: assume that non-decreasing sequence
$\mathcal{A}_{j}=\\{a_{i,j}\\}_{i=1}^{k-j}$ for some $j\in[0,s-1]$ is
constructed with the sum of elements at most $(1-\varepsilon/2)n$. In what
follows, $\delta$ is a constant much smaller than $\varepsilon$.

If $a_{k-j,j}$ is at most $n^{1-\delta}$, then we stop the construction and
set $s=j$. The sequence $\mathcal{A}_{s}$ is $(\delta,n)$-happy by Theorem
1.4. For that, we assume that $n$ is at least $n^{\prime}$, where $n^{\prime}$
is the number guaranteed by Theorem 1.4 for $\delta$. Finally, as
$\delta<\varepsilon$, sequence $\mathcal{A}_{s}$ is also
$(\varepsilon,n)$-happy.

If $a_{k-j,j}$ is larger than $n^{1-\delta}$, we construct new sequence
$\mathcal{A}_{j+1}$ such that the elements of $\mathcal{A}_{j+1}$ are taken to
be all but the last element of $\mathcal{A}_{j}$ rescaled by some factor (see
(14)).

This rescaling factor is chosen so that the sum of elements of
$\mathcal{A}_{j+1}$ is larger then sum of elements of $\mathcal{A}_{j}$ by
roughly a factor of $(1+\lambda)$, independent of $j$ (Claim 4.2(c)). In turn,
$\lambda$ is chosen so that the constructed sequences
$\mathcal{A}_{0},\ldots,\mathcal{A}_{s}$ all have a sum at most
$(1-\varepsilon/2)n$ (Claim 4.3(a)).

Construction of sequences $\mathcal{A}_{0},\ldots,\mathcal{A}_{s}$ stops when
the last sequence $\mathcal{A}_{s}$ is $(\delta,n)$-happy, which will happen
eventually as the sequence consisting of single element $\\{b\\}$ with $b<n$
is $(\varepsilon,n)$-happy by definition.

Finally, Claim 4.6 shows that if $\mathcal{A}_{j}$ is $(\varepsilon,n)$-happy
then $\mathcal{A}_{j-1}$ is also $(\varepsilon,n)$-happy. Since the
construction ends with a sequence $\mathcal{A}_{s}$ that is
$(\varepsilon,n)$-happy, this implies, by repeated application of Claim 4.6,
that all previous sequences $\mathcal{A}_{j}$ with $j\in[0,s-1]$, in
particular $\mathcal{A}_{0}$, are also $(\varepsilon,n)$-happy. Claim 4.6 is a
corollary of a rather general Lemma 4.4 that allows us to verify that a
sequence is $(\varepsilon,n)$-happy, provided some other sequence is
$(\varepsilon,n)$-happy, and the main ingredient of proof of Lemma 4.4 is
Theorem 4.1.

###  4.2. Formal proof

Define the auxiliary variables

(11)
$\delta=\frac{\varepsilon}{10},\qquad\mu=\frac{\varepsilon}{2(1-\varepsilon)},\qquad
S=\lceil 2(1+\mu)n^{\delta}\ln n\rceil,\qquad\lambda=\frac{\ln(1+\mu)}{S}.$

To explain the choice of variables, $(1+\lambda)$ will determine how much
$\sum_{i=1}^{k-j+1}a_{i,j-1}$ is smaller than $\sum_{i=1}^{k-j}a_{i,j}$ for
all $j\in[s]$ (Claim 4.2(c)). Constant $\mu$ is chosen to guarantee that

(12) $(1+\lambda)^{S}\leq(1+\mu)=\frac{1-\varepsilon/2}{1-\varepsilon}.$

Inequality (12) follows easily from inequality $1+x\leq e^{x}$ and is used in
proving Claim 4.3(a). Finally, $S$ will be shown to be an upper bound on $s$
in Claim 4.3(c)

Provided $n$ is large enough, the following inequalities hold:

(13) $n^{-2\delta}\leq\lambda\leq 1,\qquad\qquad n^{\delta}\leq S\leq
n^{2\delta}.$

Construction of sequences $\mathcal{A}_{j}$. Recall that we assumed that
$\\{a_{i}\\}_{i=1}^{k}$ is non-decreasing. We now construct $s+1$ non-
decreasing sequences $\mathcal{A}_{j}=\\{a_{i,j}\\}_{i=1}^{k-j}$ with
$j\in[0,s]$. Set $\mathcal{A}_{0}=\\{a_{i}\\}_{i=1}^{k}$ and assume that
sequence $\mathcal{A}_{j}=\\{a_{i,j}\\}_{i=1}^{k-j}$ was constructed for some
integer $j$. Set

$\sigma_{j}=\sum_{i=1}^{k-j}a_{i,j}.$

If $a_{k-j,j}>n^{1-\delta}$, then define

$m_{j}=\frac{a_{k-j,j}}{\sigma_{j}},$

and for $i\in[k-j-1]$ define the terms of sequence
$\mathcal{A}_{j+1}=\\{a_{i,j+1}\\}_{i=1}^{k-j-1}$ by

(14) $a_{i,j+1}=\left\lfloor\frac{(1+\lambda)}{1-m_{j}}a_{i,j}\right\rfloor.$

If $a_{k-j,j}\leq n^{1-\delta}$ or $j=k-1$, the construction stops and we set
$s=j$.

We start with proving a few straightforward, but slightly technical
observations about constructed sequences.

######  Claim 4.2.

For the sequences $\mathcal{A}_{0},\ldots,\mathcal{A}_{s}$ we have the
following:

  * (a)

$a_{i,j}\leq a_{i,j+1}$ for all $j\in[0,s-1]$ and $i\in[k-j-1]$.

  * (b)

For each $j\in[0,s]$ sequence $\mathcal{A}_{j}$ is non-decreasing.

  * (c)

For each $j\in[0,s-1]$

$\left(1+\frac{\lambda}{2}\right)\sigma_{j}\leq\sigma_{j+1}\leq(1+\lambda)\sigma_{j}.$

###### Proof of Claim.

The proof is straightforward and uses equation (14) and the fact that $n$ is
sufficiently large.

Part (a). The proof is by induction on $j$. The base case $j=0$ and inductive
step are proved simultaneously. Assume that for some $h\in[0,s-1]$ we proved
the statement for all values of $j<h$, that is assume that for all $j\in[h]$
we have $a_{i,j}\leq a_{i,j+1}$ for all $i\in[k-j+1]$. Then for all
$i\in[k-h]$ we have

$a_{i,h}\geq a_{i,h-1}\geq\ldots\geq a_{i,0}\geq n^{\varepsilon}$

and so

$a_{i,h+1}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\geq}}\frac{(1+\lambda)}{1-m_{h}}a_{i,h}-1\geq(1+\lambda)a_{i,h}-1\geq
a_{i,h}+(\lambda n^{\varepsilon}-1).$

Then, by inequality (13) and provided $n$ is sufficiently large

$a_{i,h+1}\geq a_{i,h}+(n^{\varepsilon-2\delta}-1)>a_{i,h}.$

Part (b). Again, the proof is by induction on $j$. The base case $j=0$ holds
because $\mathcal{A}_{0}=\\{a_{i,0}\\}_{i=1}^{k}$ is assumed to be non-
decreasing. For some $j\in[s]$, assume that $a_{i,j-1}\leq a_{i+1,j-1}$ holds
for all $i\in[k-j]$.

Our goal is to show that $a_{i,j}\leq a_{i+1,j}$ for all $i\in[k-j-1]$. If for
some $i\in[k-j-1]$ we have that $a_{i,j-1}=a_{i+1,j-1}$, then
$a_{i,j}=a_{i+1,j}$ by (14).

So we may assume that $a_{i+1,j-1}\geq a_{i,j-1}+1$. Then

$a_{i+1,j}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\geq}}\frac{(1+\lambda)}{1-m_{j}}a_{i+1,j-1}-1\geq\frac{(1+\lambda)}{1-m_{j}}(a_{i,j-1}+1)-1\geq\frac{(1+\lambda)}{1-m_{j}}a_{i,j-1}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\geq}}a_{i,j}.$

Therefore for all $i\in[k-j-1]$ we have $a_{i,j}\leq a_{i+1,j}$.

Part (c). Note that $\frac{1}{1-m_{j}}\sum_{i=1}^{k-j-1}a_{i,j}$ is equal to
$\sigma_{j}$ by definition of $m_{j}$. Then,

$\sigma_{j+1}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\leq}}\sum_{i=1}^{k-j-1}\frac{(1+\lambda)}{1-m_{j}}a_{i,j}=(1+\lambda)\sigma_{j}.$

Similarly, for the lower bound,

$\sigma_{j+1}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\geq}}\sum_{i=1}^{k-j-1}\left(\frac{(1+\lambda)}{1-m_{j}}a_{i,j}-1\right)=\left(1+\frac{\lambda}{2}\right)\sigma_{j}+\frac{\lambda}{2}\sigma_{j}-(k-j-1).$

Now, Claim 4.2(a) implies that $a_{i,j}\geq a_{i,0}\geq n^{\varepsilon}$ for
all $j\in[0,s]$, $i\in[k-j]$. Using inequality (13), provided $n$ is
sufficiently large, we get

$\sigma_{j+1}\geq\left(1+\frac{\lambda}{2}\right)\sigma_{j}+\frac{n^{-2\delta}}{2}(k-j)n^{\varepsilon}-(k-j-1)\geq\left(1+\frac{\lambda}{2}\right)\sigma_{j}.$

∎

The next Claim, in particular, shows that the construction of sequences
$\mathcal{A}_{j}$’s ends after at most $S$ steps.

######  Claim 4.3.

Let the sequences $\mathcal{A}_{0},\ldots,\mathcal{A}_{s}$ and auxiliary
$m_{0},\ldots,m_{s-1}$ be constructed as described above, then

  * (a)

$\sigma_{j}\leq(1-\frac{\varepsilon}{2})n$ for all $j\in[0,s]$.

  * (b)

$m_{j}\geq n^{-\delta}$ for all $j\in[0,s-1]$.

  * (c)

$s<S$.

###### Proof.

We start with proving parts (a) and (b) with additional assumption that $j\leq
S$. Then we prove part (c), which in turn implies parts (a), (b) for all
$j\leq s$.

Part (a). Assume $j\leq S$, then by repeatedly applying Claim 4.2(c) and
inequality (12) we get

$\sigma_{j}\leq(1+\lambda)^{j}\sigma_{0}=(1+\lambda)^{S}\sum_{i=1}^{k}{a_{i,0}}\leq\frac{1-\varepsilon/2}{1-\varepsilon}(1-\varepsilon)n=\left(1-\frac{\varepsilon}{2}\right)n.$

Part (b). Assume $j\leq S$. If $m_{j}$ is defined, then $a_{k-j,j}\geq
n^{1-\delta}$ so by Claim 4.3(a)

$m_{j}=\frac{a_{k-j,j}}{\sigma_{j}}\geq\frac{n^{1-\delta}}{n}\geq
n^{-\delta}.$

Part (c). Assume contrary, that is that the sequence
$\mathcal{A}_{S}=\\{a_{i,S}\\}_{i=1}^{k-S}$ is defined. For $h\in[0,S-1]$ and
$j\in[0,h]$ define

$f_{h,j}=\frac{a_{k-h,j}}{\sum_{i=1}^{k-h}a_{i,j}}.$

Note that $f_{h,h}=m_{h}$. In what follows we will show that
$f_{h,h}\leq(1+\mu)f_{h,0}$ for all $h\in[0,S-1]$ and will use this to show
that $a_{k}>n$, deriving a contradiction.

We will make use of a lower bound for each $a_{i,j}$ with $j\in[S]$,
$i\in[k-j]$. Claim 4.2(a) implies that $a_{i,j}\geq a_{i,0}\geq
n^{\varepsilon}$ and so

$a_{i,j}\stackrel{{\scriptstyle\text{(\ref{eq:ii4})}}}{{\geq}}\frac{1+\lambda}{1-m_{j-1}}a_{i,j-1}-1\geq\frac{1+\frac{\lambda}{2}}{1-m_{j-1}}a_{i,j-1}+\frac{\lambda}{2}a_{i,j}-1\stackrel{{\scriptstyle\text{(\ref{ineq:ii3})}}}{{\geq}}\frac{1+\frac{\lambda}{2}}{1-m_{j-1}}a_{i,j-1}+\frac{n^{-2\delta}}{2}n^{\varepsilon}-1.$

Therefore, for large $n$,

(15) $a_{i,j}\geq\frac{1+\frac{\lambda}{2}}{1-m_{j-1}}a_{i,j-1}.$

Then for any $h\in[0,S-1]$, $i\in[0,h]$ by (15) and definition of $a_{k-h,j}$
(14),

$f_{h,j}=\frac{a_{k-h,j}}{\sum_{i=1}^{k-h}a_{i,j}}\leq\frac{\frac{1+\lambda}{1-m_{j-1}}a_{k-h,j-1}}{\sum_{i=1}^{k-h}\frac{1+\frac{\lambda}{2}}{1-m_{j-1}}a_{i,j-1}}=\frac{1+\lambda}{1+\frac{\lambda}{2}}f_{h,j-1}.$

Therefore, $f_{h,j}\leq(1+\lambda)f_{h,j-1}$ for all $h\in[0,S-1]$ and
$j\in[h]$. Applying this inequality $h$ times we get,

$m_{h}=f_{h,h}\leq(1+\lambda)^{h}f_{h,0}.$

Now, for $h\in[0,S-1]$, by inequality (12),

$m_{h}\leq(1+\mu)f_{h,0}.$

Therefore, $f_{h,0}\geq\frac{1}{1+\mu}m_{h}$ and by Claim 4.3(b) we get that
$f_{h,0}\geq\frac{n^{-\delta}}{1+\mu}$ for all $h\in[0,S-1]$. This means that
for all $h\in[0,S-1]$,

(16) $a_{k-h}\geq\frac{n^{-\delta}}{1+\mu}\left(a_{1}+\ldots+a_{k-h}\right).$

Thus by successive application of (16) for $h\in[0,S-1]$ we obtain a lower
bound on $a_{k}$,

$\displaystyle a_{k}$
$\displaystyle\geq\frac{n^{-\delta}}{1+\mu}(a_{1}+\ldots+a_{k})$
$\displaystyle\geq\frac{n^{-\delta}}{1+\mu}\left(1+\frac{n^{-\delta}}{1+\mu}\right)(a_{1}+\ldots+a_{k-1})$
$\displaystyle\geq\frac{n^{-\delta}}{1+\mu}\left(1+\frac{n^{-\delta}}{1+\mu}\right)^{2}(a_{1}+\ldots+a_{k-2})$
$\displaystyle\vdots$
$\displaystyle\geq\frac{n^{-\delta}}{1+\mu}\left(1+\frac{n^{-\delta}}{1+\mu}\right)^{S}(a_{1}+\ldots+a_{k-S})$

Now, by using inequality $1+x\geq e^{x/2}$ for $x\in(0,2)$ and the fact that
each $a_{i}$ is at least $n^{\varepsilon}$, for $n$ large enough

$a_{k}\geq\frac{n^{-\delta}}{1+\mu}e^{n^{-\delta}S/(2+2\mu)}n^{\varepsilon}\stackrel{{\scriptstyle\text{(\ref{eq:constants})}}}{{\geq}}\frac{n^{\varepsilon-\delta}}{1+\mu}e^{\ln
n}>n,$

contradicting the assumption that $s\geq S$. ∎

We now show that if $\\{a_{i,j}\\}_{i=1}^{k-j}$ is happy, than the preceding
sequence $\\{a_{i,j-1}\\}_{i=1}^{k-j+1}$ is also happy. To show that we prove
a rather more general lemma that allows to verify that sequence of length
$t+1$ is happy, provided a certain sequence of length $t$ is happy.

######  Lemma 4.4.

Assume that a sequence $\\{b_{i}\\}_{i=1}^{t}$ is $(\varepsilon,n)$-happy and
that $\frac{p}{q}$ is a positive proper fraction. If $\\{a_{i}\\}_{i=1}^{t+1}$
is a sequence of integers that satisfies $a_{i}\leq(1-\frac{p}{q})b_{i}-q$ for
$i\in[t]$ and $a_{t+1}\leq\frac{p}{q}(\sum_{i=1}^{t}b_{i})-3(t+1)q$, then
$\\{a_{i}\\}_{i=1}^{t+1}$ is also $(\varepsilon,n)$-happy.

###### Proof.

Let $\ell\in[t,(1+\varepsilon)t]$ be the number of disjoint perfect matchings
provided by the definition of $\\{b_{i}\\}_{i=1}^{t}$ being
$(\varepsilon,n)$-happy. We will show that $\\{a_{i}\\}_{i=1}^{t+1}$ is
$(\varepsilon,n)$-happy with
$\ell^{\prime}=\ell+1\in[t+1,(1+\varepsilon)(t+1)]$.

In order to show that sequence $\\{a_{i}\\}_{i=1}^{t+1}$ is
$(\varepsilon,n)$-happy, we need to show that for any $\ell^{\prime}$ disjoint
perfect matchings there are $t+1$ of them $M_{1},\ldots M_{t+1}$ and vertex-
disjoint matchings $A_{i}\subseteq M_{i}$ such that $|A_{i}|\geq a_{i}$ for
all $i\in[t+1]$ (then matching $M$ can be taken to be $M=\bigcup A_{i}$).

Let $\ell^{\prime}$ disjoint perfect matchings of $K_{2n}$ be given and
$M_{t+1}$ be one of the matchings. Among $\ell=\ell^{\prime}-1$ remaining
matchings, due to $\\{b_{i}\\}_{i=1}^{t}$ being $(\varepsilon,n)$-happy, there
are $t$ of them $M_{1},\ldots,M_{t}$ and subsets $B_{i}\subseteq M_{i}$ for
$i\in[t]$ such that all $B_{i}$’s are vertex disjoint and $|B_{i}|\geq b_{i}$
for all $i\in[t]$.

In what follows we will find vertex disjoint matchings $A_{1},\ldots,A_{t+1}$
such that $A_{t+1}\subseteq M_{t+1}$, $A_{i}\subseteq B_{i}$ for $i\in[t]$ and

(17) $|A_{i}|\geq\left(1-\frac{p}{q}\right)b_{i}-q\;\text{for
all}\;i\in[t],\;\text{and}\;|A_{t+1}|\geq\frac{p}{q}\left(\sum_{i=1}^{t}b_{i}\right)-3(t+1)q.$

Existence of such sets $A_{1},\ldots,A_{t+1}$ implies that the sequence
$\\{a_{i}\\}_{i=1}^{t+1}$ is $(\varepsilon,n)$-happy. Indeed, if
$A_{1},\ldots,A_{t+1}$ are such that (17) holds, then $|A_{i}|\geq a_{i}$ for
all $i\in[t+1]$.

In order to satisfy divisibility condition in Theorem 4.1, for all $i\in[t]$
let $B^{\prime}_{i}$ be a largest subset of $B_{i}$ such that $q$ divides
$|B^{\prime}_{i}|$, and $B^{\prime}_{t+1}$ be a largest subset of $M_{t+1}$
such that $q$ divides $|B^{\prime}_{t+1}|$. Let
$b^{\prime}_{i}=|B^{\prime}_{i}|$ for $i\in[t+1]$, then

(18) $b^{\prime}_{i}\geq
b_{i}-(q-1)\;\text{for}\;i\in[t]\;\text{and}\;b^{\prime}_{k+1}\geq n-(q-1).$

We want to find sets $A_{i}\subseteq B_{i}^{\prime}$ such that $|A_{i}|\geq
a_{i}$ for all $i\in[t+1]$ and $\bigcup_{i=1}^{t+1}A_{i}$ forms a matching.
Since $\bigcup_{i=1}^{t}B_{i}^{\prime}\subseteq\bigcup_{i=1}^{t}B_{i}$ is a
matching by our assumption, we only need to take care of incidences between
edges of $B_{t+1}^{\prime}$ and $\bigcup_{i=1}^{t}B_{i}^{\prime}$. In what
follows we will call the edges of $\bigcup_{i=1}^{t}B_{i}^{\prime}$ old and
edges of $B_{t+1}^{\prime}$ new.

The necklace needed to apply Theorem 4.1 is constructed in the following four
steps.

Step 1. Let $G$ be a graph that is formed by a union of all
$B^{\prime}_{i}$’s, $i\in[t+1]$. Then $G$ is a union of two matchings
$\bigcup_{i=1}^{t}B^{\prime}_{i}$ and $B^{\prime}_{t+1}$, and hence each
component of $G$ is either a cycle or a path. Colour edge $e$ of $G$ in colour
$i$ if $e\in B^{\prime}_{i}$. We say that colours in $[t]$ are old and colour
$t+1$ is new.

Step 2. Let $L(G)$ be a line graph of $G$. The colouring of edges of $G$
induces a colouring of vertices of $L(G)$, vertices of $L(G)$ are properly
$[t+1]$ coloured, and all neighbours of a new vertex are coloured with the old
colour. Each component of $L(G)$ is also either a path or a cycle.

Step 3. Let $G^{\prime}$ be a subgraph of $L(G)$ obtained from $G$ by deleting
an edge from each cycle component. Then $G^{\prime}$ is a union of paths
$P_{1},\ldots,P_{h}$.

Step 4. Construct a necklace $N$ by concatenating paths $P_{1},\ldots,P_{h}$
(this creates $h-1$ new links/edges in the necklace). The necklace contains
$t+1$ types of beads and there are exactly $b^{\prime}_{i}$ beads of colour
$i$. Note that each bead is identified with a vertex of $L(G)$ and an edge of
$G$.

$G:$$L(G):$$N:$ Figure 1. Graph $G$ with edges of $B^{\prime}_{t+1}$ coloured
red, line graph $L(G)$ and necklace $N$. Dotted edges were removed from
$L(G)$, zigzag links were added to $L(G)$ to form a necklace.

By Theorem 4.1, applied with $\ell=t+1$, it is possible to split necklace $N$
between $q$ thieves with at most $(q-1)(t+1)$ cuts so that every thief gets
exactly $b^{\prime}_{i}/q$ beads of colour $i$.

With intention to avoid incidences between old and new edges, split the
thieves in two groups: one of size $p$ (called new thieves) and the other of
size $q-p$ (called old thieves). For $i\in[t]$ let $A_{i}$ be the collection
of edges of colour $i$ that belong to old thieves. Similarly let
$A_{t+1}^{\prime}$ be the collection of edges of colour $t+1$ that belong to
new thieves. Since each thieve has has exactly $b_{i}^{\prime}/q$ edges of
colour $i$, then for $i\in[t]$

(19)
$|A_{i}|=(q-p)\frac{b^{\prime}_{i}}{q}\stackrel{{\scriptstyle\text{(\ref{eq:b_iprime})}}}{{\geq}}\left(1-\frac{p}{q}\right)(b_{i}-q)\geq\left(1-\frac{p}{q}\right)b_{i}-q.$

and

(20) $|A^{\prime}_{t+1}|=p\frac{b_{t+1}^{\prime}}{q}.$

As mentioned above, the sets $A_{1},\ldots,A_{t}$ are vertex disjoint
matchings, however it is possible that $A^{\prime}_{t+1}$ is not vertex
disjoint from some or all $A_{i}$ with $i\in[t]$.

We say that an edge $e\in A^{\prime}_{t+1}$ forms a _conflict pair_ with
$f\in\bigcup_{i=1}^{t}A_{i}$ if $e$ and $f$ share a vertex. Let $A_{t+1}$ be
obtained from $A_{t+1}^{\prime}$ by deleting edges $e$ that are in some
conflict pair. Then $A_{t+1}$ is vertex disjoint from $A_{1},\ldots,A_{t}$.

In order to estimate the size of $A_{t+1}$ it remains to estimate the number
of conflict pairs.

######  Claim 4.5.

There are at most $2(q-1)(t+1)$ conflict pairs.

###### Proof.

Assume that a pair $(e,f)$ is a conflict pair and $e$ is a new edge that
belongs to new thieve $T$, while $f$ is an old edge that belong to an old
thieve $T^{\prime}$. We say a conflict pair is of type 1 if $ef$ is an edge in
$G^{\prime}$ (see Figure 2(A)), and of type 2 if $ef$ is not an edge in
$G^{\prime}$ but is an edge in $L(G)$ (see Figure 2(B)).

$e$$f$ (a) Type 1, cut is through $ef$

$e$$f$ (b) Type 2, cut is made on a path $P_{i}$

Figure 2. Two types of conflict pairs.

If $(e,f)$ is type 1 conflict pair, since $e$ and $f$ belong to different
thieves, one of the cuts on the necklace was made between $e$ and $f$. So
there are at most $(q-1)(t+1)$ type 1 conflict pairs.

If $(e,f)$ is type 2 conflict pair, then $e$ and $f$ are endpoints of some
path $P_{i}$ in $G^{\prime}$. Since $e$ and $f$ belong to different thieves,
one of the cuts in the necklace was made somewhere on the path $P_{i}$. There
were at most $(q-1)(t+1)$ cuts made, and each cut corresponds to at most one
path $P_{i}$. So there are at most $(q-1)(t+1)$ conflict pairs of type 2.

Therefore there are at most $2(q-1)(t+1)$ conflict pairs in total.∎

In view of (20) and Claim 4.5,

$|A_{t+1}|\geq
p\frac{b^{\prime}_{t+1}}{q}-2(t+1)(q-1)\stackrel{{\scriptstyle\text{(\ref{eq:b_iprime})}}}{{\geq}}\frac{p}{q}(n-q)-2(t+1)(q-1).$

Now, since $\\{b_{i}\\}_{i=1}^{t}$ is an $(\varepsilon,n)$-happy sequence,
then $\sum_{i=1}^{t}b_{i}\leq n$ and so

(21) $|A_{t+1}|\geq\frac{p}{q}\left(\sum_{i=1}^{t}b_{i}\right)-3(t+1)q.$

Finally, (21) and (19) imply (17), establishing that a sequence
$\\{a_{i}\\}_{i=1}^{t+1}$ is $(\varepsilon,n)$-happy. ∎

The following Claim shows that if a sequence $\mathcal{A}_{j}$ is happy, then
so is sequence $\mathcal{A}_{j-1}$.

######  Claim 4.6.

If for $j\in[s]$ the constructed sequence
$\mathcal{A}_{j}=\\{a_{i,j}\\}_{i=1}^{k-j}$ is $(\varepsilon,n)$-happy, then
sequence $\mathcal{A}_{j-1}=\\{a_{i,j-1}\\}_{i=1}^{k-j+1}$ is also
$(\varepsilon,n)$-happy.

###### Proof.

In view of Lemma 4.4 it will be sufficient to verify the following
inequalities for appropriate $\frac{p}{q}$ in order to show that the sequence
$\mathcal{A}_{j-1}$ is $(\varepsilon,n)$-happy:

$a_{i,j-1}\leq\left(1-\frac{p}{q}\right)a_{i,j}-q\qquad\text{for all
}i\in[k-j],\qquad\text{and}$
$a_{k-j+1,j-1}\leq\frac{p}{q}\sigma_{j}-3(k-j+1)q.$

Recall that $m_{j-1}=a_{k-j+1,j-1}/\sigma_{j-1}$. Choose an integer
$q\in[\frac{1}{4}n^{4\delta},\frac{1}{2}n^{4\delta}]$. Let $p=p(j)$ be an
integer such that

(22) $0\leq m_{j-1}-\frac{p}{q}\leq\frac{1}{q}.$

Then, by the construction of sequence $\\{a_{i,j}\\}_{i=1}^{k-j}$, for any
$i\in[k-j]$

$a_{i,j}\geq\frac{1+\lambda}{1-m_{j-1}}a_{i,j-1}-1,$

which in turn implies

$\displaystyle
a_{i,j-1}\leq\frac{1-m_{j-1}}{1+\lambda}a_{i,j}+\frac{1-m_{j-1}}{1+\lambda}\leq\left(1-\frac{p}{q}\right)\frac{a_{i,j}}{1+\lambda}+1\leq\left(1-\frac{p}{q}\right)a_{i,j}-\frac{\lambda}{1+\lambda}\left(1-\frac{p}{q}\right)a_{i,j}+1.$

By Claim 4.2(a), $a_{i,j}\geq a_{i}\geq n^{\varepsilon}$. Therefore by
inequality (13), for large enough n,

$\displaystyle
a_{i,j-1}\leq\left(1-\frac{p}{q}\right)a_{i,j}-\frac{n^{-2\delta}}{2}\frac{1}{q}n^{\varepsilon}+1\leq\left(1-\frac{p}{q}\right)a_{i,j}-n^{\varepsilon-6\delta}+1\leq\left(1-\frac{p}{q}\right)a_{i,j}-q,$

proving the first set of inequalities sufficient to use Lemma 4.4.

Now, by inequality (22) and Claim 4.2(c),

$\displaystyle
a_{k-j+1,j-1}=m_{j-1}\sigma_{j-1}\leq\left(\frac{p}{q}+\frac{1}{q}\right)\frac{\sigma_{j}}{1+\lambda/2}$

which after expanding gives

$\displaystyle
a_{k-j+1,j-1}\leq\frac{p}{q}\sigma_{j}-\frac{p}{q}\frac{\lambda/2}{1+\lambda/2}\sigma_{j}+\frac{\sigma_{j}}{q(1+\lambda/2)}$

Now $m_{j-1}\geq n^{-\delta}$ by Claim 4.3(b), so for $n$ large enough

$\frac{p}{q}\geq m_{j-1}-\frac{1}{q}\geq
n^{-\delta}-4n^{-4\delta}\geq\frac{1}{2}n^{-\delta}.$

By inequality (13), $n^{-2\delta}\leq\lambda\leq 1$ and so for large enough
$n$,

$\displaystyle
a_{k-j+1,j-1}\leq\frac{p}{q}\sigma_{j}-\frac{1}{2}n^{-\delta}\frac{n^{-2\delta}/2}{2}\sigma_{j}+\frac{4\sigma_{j}}{n^{4\delta}}\leq\frac{p}{q}\sigma_{j}-\frac{1}{16}n^{-3\delta}\sigma_{j}.$

Now, $\sigma_{j}\geq\frac{n}{3}$ by Claim 4.2(c) and inequality (10), so

$a_{k-j+1,j-1}\leq\frac{p}{q}\sigma_{j}-\frac{1}{48}n^{1-3\delta}.$

Finally, notice that $k\leq n^{1-\varepsilon}$, as $\sum_{i=1}^{k}a_{i}<n$ and
$a_{i}\geq n^{\varepsilon}$ for $i\in[k]$. Also, recall that
$\epsilon=10\delta$, so for large enough $n$,

$a_{k-j+1,j-1}\leq\frac{p}{q}\sigma_{j}-3n^{1-\varepsilon}n^{4\delta}\leq\frac{p}{q}\sigma_{j}-3(k-j+1)q.$

Hence, Lemma 4.4 applied to a sequence $\\{a_{i,j-1}\\}_{i=1}^{k-j+1}$ implies
that sequence $\\{a_{i,j}\\}_{i=1}^{k-j}$ is $(\epsilon,n)$-happy. ∎

By construction, the last sequence $\mathcal{A}_{s}$ is either such that
$a_{k-s,s}\leq n^{1-\delta}$ and hence $a_{i,s}\leq n^{1-\delta}$ for all
$i\in[k-s]$ (by Claim 4.2(b)), or such that $\mathcal{A}_{s}=\\{a_{1,k-1}\\}$
is one element sequence with $a_{1,k-1}\leq(1-\frac{\varepsilon}{2})n$ (by
Claim 4.2(a)). In the former case, by Claim 4.2(a), $\sigma_{s}<(1-\delta)n$,
so the sequence $\mathcal{A}_{s}$ satisfies assumptions of Theorem 1.4 and is
$(\delta,n)$-happy. In the latter case $\mathcal{A}_{s}$ is
$(\varepsilon,n)$-happy by Definition 1.2

In any case, the sequence $\mathcal{A}_{s}=\\{a_{i,s}\\}_{i=1}^{k-s}$ is
$(\varepsilon,n)$-happy, which in turn, by repeatedly applying Claim 4.6,
implies that $\\{a_{i,0}\\}_{i=1}^{k}=\\{a_{i}\\}_{i=1}^{k}$ is also
$(\varepsilon,n)$-happy. This finishes the proof of Theorem 1.5.

##  5\. Trees in Steiner Triple System

We start with noticing that for $\varepsilon,\alpha>0$ and integer $k$ and
$n\geq n_{0}(\varepsilon,\alpha,k)$, if each element of a sequence
$a_{1},\ldots,a_{k}$ is at least $\alpha n$ and
$\sum_{i=1}^{n}a_{i}\leq(1-\varepsilon)n$, then we can improve Theorem 1.5. In
particular we show that such sequence $a_{1},\ldots,a_{k}$ is
$(\varepsilon,n)$-happy with $\ell=k$ (recall Definition 1.2).

######  Corollary 5.1.

For any $\varepsilon,\alpha>0$ there is $n_{0}$ such that the following holds
for all $n\geq n_{0}$. Let sequence $a_{1},\ldots,a_{k}$ be such that
$\sum_{i=1}^{k}a_{i}\leq(1-\varepsilon)n$ and $a_{i}\geq\alpha n$ for all
$i\in[k]$. Then for any $k$ disjoint perfect matchings $M_{1},\ldots,M_{k}$ of
$K_{2n}$ there is a matching $M$ such that $|M\cap M_{i}|\geq a_{i}$.

###### Proof.

We choose $n_{0}$ implicitly and let $n\geq n_{0}$ be sufficiently large.

For $\delta=\min\\{1/(\frac{1}{\alpha}+1),\varepsilon\\}$ and $n$ sufficiently
large we have $a_{i}\geq n^{\delta}$ for all $i\in[k]$. Then, Theorem 1.5
implies that sequence $\\{a_{i}\\}_{i=1}^{k}$ is $(\delta,n)$-happy, provided
$n$ is large enough.

Notice that $k\leq\frac{1}{\alpha}$ because $\sum_{i=1}^{k}a_{i}\leq n$ and
$a_{i}\geq\alpha n$ for all $i\in[k]$. Then $\delta\leq 1/(k+1)$ and
$a_{1},\ldots,a_{k}$ is $(\delta,n)$-happy, so Definition 1.2 implies that
$\ell=k$ and consequently that for any $k$ disjoint perfect matchings
$M_{1},\ldots,M_{k}$ of $K_{2n}$ there is a matching $M$ such that for all
$|M\cap M_{i}|\geq a_{i}$ for all $i\in[k]$ ∎

We now define a $(c,a_{1},\ldots,a_{k})$-turkey. Recall that a hypertree is a
simple $3$-uniform hypergraph in which every two vertices are joined by a
unique path. Also notice that a hypertree with $n$ hyperedges has $2n+1$
vertices. A size of hypertree is the number of hyperedges in it. A hyperstar
$S$ of size $a$ centered at $v$ is a hypergraph on vertex set
$v,v_{1},v_{2},\ldots,v_{2a}$ with edge set
$E(S)=\\{\\{v,v_{2i-1},v_{2i}\\}:i\in[a]\\}$. For integers
$c,a_{1},\ldots,a_{k}$ we now define a class of trees which we will call
$(c,a_{1},\ldots,a_{k})$-turkeys.

######  Definition 5.2.

Let $C$ be an arbitrary hypertree on $c$ vertices with $k$ specified vertices
$v_{1},\ldots,v_{k}$. We say that a 3-uniform simple hypertree $T$ is a
$(c,a_{1},\ldots,a_{k})$-turkey if $T$ is a union of $C$ with vertex disjoint
hyperstars $S_{1},\ldots,S_{k}$ which are centered at $v_{1},\ldots,v_{k}$ and
of size $a_{1},\ldots,a_{k}$.

$S_{1}$$S_{2}$$S_{3}$$S_{4}$$C$ Figure 3. A $(7,2,2,3,4)$-turkey on 29
vertices, red hyperedges represent hyperstars $S_{1},\ldots,S_{4}$.

Now we use Corollary 5.1 to verify the Conjecture 1.6 for turkeys.

######  Theorem 5.3.

For any $\varepsilon,\alpha,c>0$ there is $n_{0}$ such that the following
holds for all $n\geq n_{0}$. If integers $a_{1},\ldots,a_{k}$ are such
$\sum_{i=1}^{k}a_{i}\leq n$ and $a_{i}\geq\alpha n$ for all $i\in[k]$, and $T$
is a $(c,a_{1},\ldots,a_{k})$-turkey on $2n+1$ vertices, then any Steiner
triple system $S$ on at least $2(1+\varepsilon)n$ vertices contains $T$ as a
subhypergraph.

###### Proof.

Since $T$ is $(c,a_{1},\ldots,a_{k})$-turkey, there is a hypertree $C$ on $c$
vertices, vertices $v_{1},\ldots,v_{k}\in V(C)$ and vertex disjoint hyperstars
$S_{1},\ldots,S_{k}$, such that size of $S_{i}$ is $a_{i}$ for all $i\in[k]$
and such that $T$ is obtained by identifying centers of stars
$S_{1},\ldots,S_{k}$ with $v_{1},\ldots,v_{k}$.

Let $S$ be a Steiner triple system of order at least $2(1+\varepsilon)n$. We
can find a copy $C^{\prime}$ of $C$ in $S$ greedily, provided $n\geq c$. Let
vertices $v_{1},\ldots,v_{k}$ of $C$ correspond to $u_{1},\ldots,u_{k}$ in
$C^{\prime}$. It remains to embed stars $S_{1},\ldots,S_{k}$ into $S$.

Let $X=V(S)\cup\\{w\\}$, where $w$ is a new “fake” vertex. Then $|X|$ is even,
since $|V(S)|$ is always odd (in any Steiner triple system $|V(S)|\equiv
1,3\;(\text{mod }6)$ ). For $i\in[k]$ let $M_{i}$ be a matching on $X$ defined
by

$M_{i}=\\{\\{u,v\\}:\\{u_{i},u,v\\}\in E(S)\\}\cup\\{\\{u_{i},w\\}\\}.$

We say that for $i\in[k]$ an edge $\\{u,v\\}\in M_{i}$ is “fake” if
$\\{u,v\\}=\\{w,u_{i}\\}$ or $|\\{u,v\\}\cap V(C^{\prime})|\neq 0$. Notice
that there are at most $c$ fake edges in each $M_{i}$, since $M_{i}$ is a
matching and every fake edge contains at least one vertex from $C^{\prime}$.

We now have edge disjoint perfect matchings $M_{1},\ldots,M_{k}$ on
$|X|=2n^{\prime}$ vertices with $n^{\prime}\geq(1+\varepsilon)n$. For all
$i\in[k]$ let

$a_{i}^{\prime}=\frac{(1+\varepsilon/2)n^{\prime}}{(1+\varepsilon)n}a_{i}.$

Then for $\varepsilon^{\prime}=\frac{\varepsilon}{2(1+\varepsilon)}$, since
$\sum_{i=1}^{k}a_{i}\leq n$ we have

$\sum_{i=1}^{k}a_{i}^{\prime}\leq\frac{1+\frac{\varepsilon}{2}}{1+\varepsilon}n^{\prime}=(1-\varepsilon^{\prime})n^{\prime}.$

Moreover for $\alpha^{\prime}=\frac{1+\varepsilon/2}{1+\varepsilon}\alpha$ and
all $i\in[k]$, we have

$a_{i}^{\prime}\geq\frac{(1+\varepsilon/2)n^{\prime}}{(1+\varepsilon)n}\alpha
n=\alpha^{\prime}n^{\prime}.$

Therefore, provided $n$ is sufficiently large, by Corollary 5.1 applied to
$\varepsilon^{\prime},\alpha^{\prime}$ and sequence
$a_{1}^{\prime},\ldots,a_{k}^{\prime}$, there is a matching $M$ such that
$|M\cap M_{i}|\geq a_{i}^{\prime}$ for all $i\in[k]$.

For $i\in[k]$ let $A_{i}$ be obtained from $M\cap M_{i}$ by deleting fake
edges. Then for all $i\in[k]$, provided $n$ is large enough,

$|A_{i}|\geq
a_{i}^{\prime}-c\geq\left(1+\frac{\varepsilon}{2}\right)a_{i}-c\geq
a_{i}+\frac{\varepsilon}{2}\alpha n-c\geq a_{i}.$

Finally, for each $i\in[k]$ let

$S_{i}^{\prime}=\\{\\{u_{i},u,v\\}:\\{u,v\\}\in A_{i}\\}$

be the stars centered at $u_{1},\ldots,u_{k}$. For each $i\in[k]$, size of
$S^{\prime}_{i}$ is at least $a_{i}$. By construction, $A_{i}$’s have no fake
edges, so $V(S_{i}^{\prime})\cap V(H)=\\{v_{i}\\}$ for all $i\in[k]$. Since
$\bigcup_{i=1}^{k}A_{i}\subseteq M$ forms a matching, stars
$S_{1}^{\prime},\ldots S_{k}^{\prime}$ are vertex disjoint.

Therefore $C^{\prime}\bigcup\left(\bigcup_{i=1}^{k}S^{\prime}_{i}\right)$ is a
copy of $T$ in $S$. ∎

##  6\. Concluding remarks

Note that one may modify the proof of Theorem 1.5 allowing to prove a stronger
form of Corollary 5.1, namely that for any rational
$\alpha_{1},\ldots,\alpha_{k}\in(0,1)$ such that $\sum_{i=1}^{k}\alpha_{i}\leq
1$ there are integers $K$ and $n_{0}$ such that for any $n\geq n_{0}$ and any
$k$ disjoint perfect matchings $M_{1},\ldots,M_{k}$ of $K_{2n}$ there is a
matching $M$ such that $|M_{i}\cap M|\geq\alpha_{i}n-K$.

Finally, some of the authors of this paper believe that for any $\epsilon>0$
there is $n_{0}$, such that if $n\geq n_{0}$, then any sequence
$a_{1},\ldots,a_{k}$ that satisfies $\sum_{i=1}^{k}a_{i}<(1-\epsilon)n$ is
$(\epsilon,n)$-happy. The only sequences for which we know this to be true are
covered by Theorem 1.3.

## References