# Quantum Network Recovery from Multinode Failure using Network Encoding with
GHZ-States on Higher-Order Butterfly Networks

Mrittunjoy Guha Majumdar and Shayan Srinivasa Garani

###### Abstract

We propose a protocol to transmit three quantum states crossly in a butterfly
network with prior entanglement, in the form of GHZ states, between three
senders. The proposed protocol requires only one qubit transmission or two
classical bits transmission in each channel of the network. We generalize this
protocol to higher number of qubits with multiqubit GHZ states towards quantum
network operability using network coding with multiqubit GHZ states on higher-
order butterfly networks.

##  1 Introduction

Quantum correlations, particularly prior entanglement across quantum states,
can be harnessed for transmitting more classical information through quantum
communication links through teleportation and superdense coding schemes [GT07,
Mt96, Pt01, Ht04, Vai94]. The physical realization of quantum networked
systems at atomic scale distances using such entangled quantum states is key
towards realizing high-throughput quantum communications at such scales. The
ideas from classical network coding, such as coding over butterfly networks,
can be naturally extended to the quantum case, mindful of the quantum no-go
theorems [Ht07, At00]. In the butterfly network, two units of information can
sent crossly and the channels can transmit only one bit, with the bottleneck
being the central channel in the network. It was recently shown that perfect
quantum state transmission is impossible in the butterfly network and the
bottleneck, in the form of the central channel, cannot be resolved for a
quantum network [Ht07]. This was subsequently extended to different kinds of
networks with quantum network coding [It06]. Leung et al proposed network
coding using shared entanglement between two parties [Lt10] through quantum
teleportation and superdense coding. Hayashi demonstrated the impossibility of
transmitting quantum states over the butterfly network between two senders
without prior entanglement [Hay07]. In this Letter, we have formulated a non-
trivial extension of Hayashi’s results to the case of higher-order butterfly
networks using GHZ states. This extension is useful to realize polygon
tesselated higher-order butterfly networks for recovery of network operability
post detection of erased nodes.

##  2 Network Coding with GHZ States on higher-order Butterfly Networks

Our protocol is based on a network with prior entanglement shared between
three users. We fundamentally use teleportation for the proposed protocol.

Figure 1: Network for Quantum Butterfly Network comprising of three users with
three GHZ states and an arbitrary quantum state for each transmission,
alongwith four central channels: $E=(X_{1}^{(a)}\oplus X_{2}^{(a)}\oplus
X_{3}^{(a)},X_{1}^{(b)}\oplus X_{2}^{(b)}\oplus X_{3}^{(b)})$,
$E_{1}=(X_{1}^{(a)}\oplus X_{2}^{(a)},X_{1}^{(b)}\oplus X_{2}^{(b)})$,
$E_{2}=(X_{2}^{(a)}\oplus X_{3}^{(a)},X_{2}^{(b)}\oplus X_{3}^{(b)})$ and
$E_{3}=(X_{1}^{(a)}\oplus X_{3}^{(a)},X_{1}^{(b)}\oplus X_{3}^{(b)})$.

We assume that the three senders $A_{1}$, $A_{2}$ and $A_{3}$ share three
copies of maximally entangled (GHZ) states:
$|\phi_{i}\rangle=\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)_{(1,i),(2,i),(3,i)}$,
where $i=1,2,3$, denotes the $i^{\mathrm{th}}$ GHZ state, while the qubits
with the same first index in the subscript belong to the same physical
terminal. The senders prepare their states in:
$|\psi_{j}\rangle=\alpha_{j}|0\rangle+\beta_{j}|1\rangle$, where $j=1,2,3$
denotes the $j^{\mathrm{th}}$ user. In the first step, the sender $A_{i}$
performs a Bell state measurement $\\{\phi_{+},\phi_{-},\psi_{+},\psi_{-}\\}$
on the joint system $A_{i}\otimes A_{i,i}$. We can see the decomposition for
$A_{i}\otimes A_{i,i}\otimes A_{(i+1)\mathrm{mod}3,i}\otimes
A_{(i+2)\mathrm{mod}3,i},i=1,2,3$ in Table 1. Here $A_{i}$ represents the
arbitrary prepared state, while $A_{i,i},A_{(i+1)\mathrm{mod}3,i}$ and
$A_{(i+2)\mathrm{mod}3,i}$ are qubits from the three GHZ states at the
physical terminal $i$. After the first Bell state measurement, we undertake an
additional measurement on the single qubit component of the GHZ state at one
of the other two nodes. We denote this measurement as $X_{i}^{(b)}$, with the
first measurement being tagged as $X_{i}^{(a)}$. In this measurement, we
measure single qubits in the
$|\pm\rangle=\frac{1}{\sqrt{2}}(|0\rangle\pm|1\rangle$ basis.

The action of Bell state measurement leaves a state
$U(X_{3}^{a},X_{2}^{b})^{-1}|\psi_{3}\rangle$ or
$U(X_{2}^{a},X_{3}^{b})^{-1}|\psi_{2}\rangle$ depending on a sequence of
measurements at the first qubit. Then the first terminal applies
$U(X_{1}^{a},X_{1}^{b})$. The cumulative state can be represented by either of
the following two cases

$U(X_{1}^{a},X_{1}^{b})U(X_{3}^{a},X_{2}^{b})^{-1}|\psi_{3}\rangle=c_{1132}U((X_{1}^{a},X_{1}^{b})\oplus(X_{3}^{a},X_{2}^{b}))^{-1}|\psi_{3}\rangle$
(1)
$U(X_{1}^{a},X_{1}^{b})U(X_{2}^{a},X_{3}^{b})^{-1}|\psi_{2}\rangle=c_{1123}U((X_{1}^{a},X_{1}^{b})\oplus(X_{2}^{a},X_{3}^{b}))^{-1}|\psi_{2}\rangle$
(2)

where $|c_{1123}|=|c_{1132}|=1$, depending on whether terminal 2 or 3 measures
$(a)$ or $(b)$. If we are to consider the clockwise cyclicity and the indices
‘wrapping around’ (with $X_{4}=X_{1}$), we have the transformation
$U((X_{i}^{a},X_{i}^{b})\oplus(X_{i+1}^{a},X_{i+2}^{b}))^{-1}$. To be able to
recover the state at the receiving terminals, we formulate a combination of
classical bits $X_{1}^{a},X_{1}^{b},X_{2}^{a},X_{2}^{b},X_{3}^{a}$ and
$X_{3}^{b}$ to obtain an inverse unitary transformation for recovering the
states. For the scheme with three users and three 3-qubit GHZ states, we use
four central channels: $E=(\sum_{\oplus i=1}^{3}X_{i}^{(a)},\sum_{\oplus
i=1}^{3}X_{i}^{(b)})$ and $E_{j}=(\sum_{\oplus i=1\backslash
j}^{3}X_{i}^{(a)},\sum_{\oplus i=1\backslash j}^{3}X_{i}^{(b)})$. Classical
information is transmitted using these four central channels to the three
users, upon which the inverse transformation can be applied to the quantum
state received at the terminal to get the cross-transmitted states.

$X_{i}^{(a)}$ | $X_{i}^{(b)}$ | $A_{i}\otimes A_{i,i}$ | $A_{(i+1)\mathrm{mod}3,i}\otimes A_{(i+2)\mathrm{mod}3,i}$ | $U$
---|---|---|---|---
(0,0) | 0/1 | $|\psi_{+}\rangle$ | $\alpha_{1}|00\rangle+\beta_{1}|11\rangle$ |  $I$/$\sigma_{z}$
(0,1) | 0/1 | $|\psi_{-}\rangle$ | $\alpha_{1}|00\rangle-\beta_{1}|11\rangle$ |  $\sigma_{z}$/$I$
(1,0) | 0/1 | $|\phi_{+}\rangle$ | $\alpha_{1}|11\rangle+\beta_{1}|00\rangle$ |  $\sigma_{x}$/$\sigma_{x}\sigma_{z}$
(1,1) | 0/1 | $|\phi_{-}\rangle$ | $\alpha_{1}|11\rangle-\beta_{1}|00\rangle$ |  $\sigma_{x}\sigma_{z}$/$\sigma_{x}$
Table 1: Decomposition for $A_{i}\otimes A_{i,i}\otimes
A_{(i+1)\mathrm{mod}3,1}\otimes A_{(i+2)\mathrm{mod}3,1}\forall i=1,2,3$, and
truth values as well as associated unitary transformations for higher-order
butterfly network over three nodes

This proposal can be generalised to the case of $n$-qubits by considering an
$n$-qubit GHZ state: $|\xi\rangle=\frac{1}{\sqrt{2}}(|0^{\otimes
n}+|1^{\otimes n})$. In this case, there will be $n$+1 channels with
$E=(\sum_{\oplus i=1}^{n}X_{i}^{(a)},\sum_{\oplus i=1}^{n}X_{i}^{(b)})$ and
$E_{j}=(\sum_{\oplus i=1\backslash j}^{n}X_{i}^{(a)},\sum_{\oplus
i=1\backslash j}^{n}X_{i}^{(b)})$. As in the case of the two parties, perfect
transmission of quantum states is impossible without prior entanglement.
Following the analysis of Hayashi [Hay07] for the case of EPR state, we find
the bound on fidelity for a generalised case to be

$\sum_{i=1}^{d}f_{i}\leq\frac{2.8512d}{d+1}$ (3)

where $f_{i}$ is the average entanglement fidelity of the $i^{\mathrm{th}}$
channel and $d$ is the number of nodes in the quantum network. The operation
of this higher-order butterfly scheme cannot be undertaken without prior
entanglement.

##  3 Scheme for Quantum Network Recovery from Multinode Failure using
Tesselated GHZ-Butterfly Subnetworks

. The $n$-qubit GHZ states can be used for network recovery after multinode
failure for an arbitrary graph state using tesselation of such GHZ-states in
partitioned blocks of the graph, as shown in Figure 2 (a). The scheme for
undertaking network recovery using the higher-order GHZ state based network
coding, formulated in the previous section, comprises of two distinct steps:
Checking for operability of nodes and recovery of network operability. We
prepare the graph state that constitutes the quantum network by initialising
the states at the first terminal/node $|\phi\rangle$ and the other nodes with
the state $|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. We then operate
with the CPHASE operation: $CZ_{ij}=|0\rangle\langle
0|_{i}I_{j}+|1\rangle\langle 1|_{i}Z_{j}$, where $Z$ is the Pauli-z matrix,
between adjacent nodes. This gives us the entangled graph state which is the
primary resource in the quantum network being studied.

For checking for operability of nodes, we use a hybrid classical-quantum
approach. Classically, communication of node failure is done using ‘pings’
that are used in the ICMP echo protocol. However, this is not enough to
ascertain quantum accessibility and entanglement at the node. Additional to
the classical connection, we need an additional layer to enable possibility to
assess whether entanglement at the node is accessible and operative. This is
done using quantum non-destructive measurements on the nodes of the graph, and
any instance of node failure is relayed to the rest of the nodes in the
affected subgraph using classical infrastructure. For optical systems, we can
utilise non-destructive detection using an optical resonator containing a
single atom prepared in a superposition of two states [Rt14].

Figure 2: Illustrative example for scheme for recovery of network operability
from multinode failure: (a) The nodes begin with $|\phi\rangle$ at one node
and $|+\rangle$ at the others, and we apply C-Phase operations on all the
adjacent nodes. We then consider the possibility of two nodes failing (marked
in grey). The coloured lines represent the GHZ states shared between adjacent
nodes. (a)-(c) Mechanism for recovery upon multinode recovery of the network,
using GHZ-based network coding in segments of the composite network. Inset is
the detector unit comprising of an optical resonator with a three-level atom
in a single-sided cavity.

At each node, we position an optical resonator system with a three-level atom
in a single-sided cavity, where one of the two mirrors is perfectly reflecting
and there is a small transmission coefficient of the other mirror that allows
for in- and outcoupling of light, which is an optical photon. Let the three
states of the atom be tagged $|1_{a}\rangle$, $|2_{a}\rangle$ and
$|3_{a}\rangle$. The cavity is designed such that it is overcoupled and
resonant with the transition between the atomic states $|2_{a}\rangle$ and
$|3_{a}\rangle$. If we prepare the atom initially in the state
$\frac{|1_{a}\rangle+|2_{a}\rangle}{\sqrt{2}}$, an impinging photon makes it
transform to $\frac{|2_{a}\rangle-|1_{a}\rangle}{\sqrt{2}}$ while it remains
unchanged in the absence of an impinging photon. This is due to there being no
interaction between the atom and photon when the atom is in the state
$|1_{a}\rangle$ since any transition is far detuned, while when the atom is in
the state $|2_{a}\rangle$, the strong photon-atom coupling can lead to a
normal-mode splitting and the photon undergoes reflection without entering the
cavity. We can measure this phase flip using a $\frac{\pi}{2}$ rotation map to
map $\frac{|1_{a}\rangle+|2_{a}\rangle}{\sqrt{2}}\rightarrow|1_{a}\rangle$ and
$\frac{|1_{a}\rangle-|2_{a}\rangle}{\sqrt{2}}\rightarrow|2_{a}\rangle$, and
then cavity-enhanced fluorescence state detection can be used to distinguish
between the states $|2_{a}\rangle$ and $|1_{a}\rangle$ [Bt10].

Upon the non-destructive detection of a lost photon, the classical
infrastructure used for classical communication in our model for higher-order
butterfly networks is used to alert the other nodes in the subnetworks of
which the failed node(s) is(are) a part of. This is undertaken using a parity
code check. This comprises of $E=(\sum_{\oplus
i=1}^{n}X_{i}^{(a)},\sum_{\oplus i=1}^{n}X_{i}^{(b)})$ and
$E_{j}=(\sum_{\oplus i=1\backslash j}^{n}X_{i}^{(a)},\sum_{\oplus
i=1\backslash j}^{n}X_{i}^{(b)})$ for $n$ nodes of a subnetwork. However,
unlike in the case of the higher-order butterfly network, we do not send any
single- or two-qubit measurements over these channels but rather if the check
on each node yields a success (‘1’) or failure (‘0’). In this manner, each
node in the subnetwork can exactly know which node(s) is(are) non-operative.
Upon ascertaining the same, we operate with a $\sigma_{z}$ operate to remove
the particular failed node(s) from the graph state.

For recovery of network operability, we can use the network coding formalism
for higher-order butterfly networks developed and discussed in the previous
section. In this framework, the key point is to tesselate the complex
multiqubit network with subnetworks comprising of $n_{i}$ qubit GHZ state for
the $i^{\mathrm{th}}$ subnetwork comprising of $n_{i}$ nodes, along with the
requisite classical infrastructure, as highlighted in the model formulated for
higher-order butterfly networks. As soon as we ascertain which nodes are non-
operative, we can use the GHZ-state in the subnetwork to replace the failed
node, as shown in Figure 2 (a)-(c). Failure of all nodes that a subnetwork
shares with the rest of the network, along with both additional qubits on
either side of this set precipitates a point of criticality wherein the
network operability cannot be recovered using the formulated scheme. The
recovery of rate-optimal coded graph state networks can also be realised using
modified graph-state codes [NRS20].

##  4 Conclusion

In this Letter, we have formulated and constructed a higher-order butterfly
network using a multiqubit GHZ states. We studied the fidelity bounds of
transmission in such GHZ-based higher-order butterfly networks that scale as
$\frac{n}{n+1}$ for the number of terminals, which we use to construct a
scheme for quantum network recovery from multinode failure. This is
particularly useful for making quantum networks resilient against failures at
multiple nodes.

##  5 Acknowledgement

We would like to acknowledge Prof. Brian Josephson (University of Cambridge)
for his comments on the Letter.

## References

  * [At00] Rudolf Ahlswede et al.  Network information flow.  IEEE Trans. Inf. Theory, 46(4):1204–1216, 2000.
  * [Bt10] Joerg Bochmann et al.  Lossless state detection of single neutral atoms.  Phys. Rev. Lett., 104(20):203601, 2010.
  * [GT07] Nicolas Gisin and Rob Thew.  Quantum communication.  Nature photonics, 1(3):165–171, 2007.
  * [Hay07] Masahito Hayashi.  Prior entanglement between senders enables perfect quantum network coding with modification.  Phys. Rev. A, 76(4):040301, 2007.
  * [Ht04] Aram Harrow et al.  Superdense coding of quantum states.  Phys. Rev. Lett., 92(18):187901, 2004.
  * [Ht07] Masahito Hayashi et al.  Quantum network coding.  In Annual STACS, pages 610–621, 2007.
  * [It06] Kazuo Iwama et al.  Quantum network coding for general graphs.  arXiv preprint quant-ph/0611039, 2006.
  * [Lt10] Debbie Leung et al.  Quantum network communication—the butterfly and beyond.  IEEE Trans. Inf. Theory, 56(7):3478–3490, 2010.
  * [Mt96] Klaus Mattle et al.  Dense coding in experimental quantum communication.  Phys. Rev. Lett., 76(25):4656, 1996.
  * [NRS20] Priya Nadkarni, Ankur Raina, and Shayan Garani Srinivasa.  Modified graph-state codes for single-node recovery in quantum distributed storage.  2020\.
  * [Pt01] Jian-Wei Pan et al.  Entanglement purification for quantum communication.  Nature, 410(6832):1067–1070, 2001.
  * [Rt14] Andreas Reiserer et al.  A quantum gate between a flying optical photon and a single trapped atom.  Nature, 508(7495):237–240, 2014.
  * [Vai94] Lev Vaidman.  Teleportation of quantum states.  Physical Review A, 49(2):1473, 1994.


[1]N. K. Nisar 11footnotetext: On behalf of the Belle II Collaboration

# Precise measurements of $D$ meson lifetimes

###### Abstract

We report the result of $D^{0}$ and $D^{+}$ lifetime measurement using
$D^{0}\to K^{-}\pi^{+}$ and $D^{+}\to K^{-}\pi^{+}\pi^{+}$ decays
reconstructed using $72~{}{\rm fb^{-1}}$ of data collected by the Belle II
experiment at SuperKEKB asymmetric-energy $e^{+}e^{-}$ collider. The results,
$\tau(D^{0})=410.5\pm 1.1({\rm stat})\pm 0.8({\rm syst})~{}{\rm fs}$ and
$\tau(D^{+})=1030.4\pm 4.7({\rm stat})\pm 3.1({\rm syst})~{}{\rm fs}$, are the
most precise to date and are consistent with previous measurements.

##  1 Introduction

Accurate predictions of charm meson lifetimes are challenging due to the
contributions of strong-interaction to the decay amplitudes and it is an
important ingredient to many theoretical calculations as well as experimental
measurements. The predictions must resort to effective models, such as the
heavy-quark expansion [1, 2, 3, 4, 5, 6] and precise lifetime measurements
provide excellent tests of such models. The lifetime measurement with early
Belle II data will demonstrate the excellent vertexing capability of the Belle
II detector which is essential for future analyses of decay-time-dependent
effects.

In this paper, we report the measurement of $D^{0}$ and $D^{+}$ lifetimes by
reconstructing $D^{*+}\to(D^{0}\to K^{-}\pi^{+})\pi^{+}$ and
$D^{*+}\to(D^{+}\to K^{-}\pi^{+}\pi^{+})\pi^{0}$ decays using ${\rm
72~{}fb^{-1}}$ of data collected by Belle II detector [7](Charge-conjugate
decays are implied throughout). The $D^{*+}$ tagging is requested to suppress
the combinatoric background. In SuperKEKB [8], the $D^{*+}$ mesons are
produced with a boost that displace the $D^{0}$ and $D^{+}$ mesons. The decay
time is estimated from the projection of this displacement on to the direction
of momentum, $\vec{p}$, as $t=m_{D}\vec{L}\cdot\vec{p}/|\vec{p}|^{2}$, where
$m_{D}$ is the known mass of the relevant $D$ meson [9]. The uncertainty in
decay time, $\sigma_{t}$, is estimated by propagating the uncertainties in
$\vec{L}$ and $\vec{p}$, including their correlations.

##  2 Belle II detector

The Belle II detector is built around the interaction region of SuperKEKB
$e^{+}e^{-}$ collider. The inner most part is a two-layer silicon-pixel
detector (PXD) followed by a four-layer double-sided silicon-strip detector
(SVD) and a central drift chamber (CDC) together form the tracking system. A
time-of-propagation counter and an aerogel ring-imaging Cherenkov counter that
cover the barrel and forward end-cap regions of the detector, respectively,
are used for charged-particle identification. An electromagnetic calorimeter
is used to reconstruct photons and electrons. All these components are kept
inside a 1.5 T magnetic field. A dedicated system to identify $K^{0}_{L}$
mesons and muons is installed in the outermost part of the detector.

##  3 Reconstruction

$D^{0}\to K^{-}\pi^{+}$ and $D^{+}\to K^{-}\pi^{+}\pi^{+}$ candidates are
reconstructed using charged tracks identified as kaons and pions. Each track
is required to have at-least one hit in the first layer of PXD, one hit in the
SVD. Tracks from $D^{0}(D^{+})$ need to have at least 20 (30) hits in the CDC.
The low momentum $\pi^{+}$ from the $D^{*+}$ decay are tracks consistent with
originating from the interaction region that have at least one hit in the SVD
and one hit in the CDC. Low momentum $\pi^{0}$ is reconstructed from two
photons as $\pi^{0}\to\gamma\gamma$. The $D^{*+}$ momentum in $e^{+}e^{-}$
centre-of-mass frame is required to be greater than $2.5(2.6)~{}{\rm GeV}/c$
to suppress $D^{0}(D^{+})$ mesons coming from bottom mesons. A global decay-
chain vertex fit [10] constraining the tracks according to the decay topology
is applied and only candidates with fit $\chi^{2}$ probabilities larger than
0.01 are retained for further analysis. The mass of $D^{0}$ and $D^{+}$
candidate is required to be $1.75<m(K^{-}\pi^{+})<2.00~{}{\rm GeV}/c^{2}$. The
difference between the $D^{*+}$ and $D$ candidate masses, $\Delta M$, must
satisfy $144.94<\Delta M<145.90~{}{\rm MeV}/c^{2}$ and $138<\Delta
M<143~{}{\rm MeV}/c^{2}$ for $D^{0}$ and $D^{+}$ candidates, respectively. By
applying these selections, approximately $171\times 10^{3}$ signal $D^{0}$
candidates with signal purity of 99.8% is observed in the signal region,
defined as $1.815<m(K^{-}\pi^{+})<1.878~{}{\rm GeV}/c^{2}$. The signal region
in $m(K^{-}\pi^{+}\pi^{+})$ is defined as
$1.855<m(K^{-}\pi^{+}\pi^{+})<1.883~{}{\rm GeV}/c^{2}$ and contains
approximately $59\times 10^{3}$ signal candidates with a background
contamination of 9%. Mass distributions of $D^{0}\to K^{-}\pi^{+}$ and
$D^{+}\to K^{-}\pi^{+}\pi^{+}$ candidates are shown in Fig. 1.

Figure 1: Mass distributions of (top) $D^{0}\to K^{-}\pi^{+}$ and (bottom)
$D^{+}\to K^{-}\pi^{+}\pi^{+}$ candidates with fit projections overlaid. The
vertical dashed and (for the bottom plot) dotted lines indicate the signal
regions and the sideband, respectively.

##  4 Lifetime extraction

Lifetimes are extracted by using unbinned maximum-likelihood fits to the
$(t,\sigma_{t})$ distributions of candidates populating the signal regions.
The signal probability-density function (PDF) is the convolution of an
exponential function in $t$ with a resolution function that depends on
$\sigma_{t}$, multiplied by the PDF of $\sigma_{t}$. The time constant of the
exponential function will return the lifetime. The PDF of $\sigma_{t}$ is a
histogram template derived directly from the signal region of the data. In the
$D^{0}$ case, the PDF of $\sigma_{t}$ is obtained assuming that all candidates
in the signal region are signal decays. In the $D^{+}$ case, instead, the
template is obtained from the candidates in the signal region after having
subtracted the distribution of the sideband data. Simulation shows that a
double (single) Gaussian with common mean will describe the resolution
function for $D^{0}(D^{+})$. The mean of the resolution function is allowed to
float in the fit to account for a possible bias in the determination of the
decay time; the width is the per-candidate $\sigma_{t}$ scaled by a free
parameter $s$ to account for a possible misestimation of the decay-time
uncertainty.

In the $D^{0}$ case, the per-mille-level fraction of background candidates in
the signal region is neglected and a systematic uncertainty is assigned for
this. A sizable background contamination is accounted for in the $D^{+}$ case
using the data sideband:
$1.758<m(K^{-}\pi^{+}\pi^{+})<1.814,1.936<m(K^{-}\pi^{+}\pi^{+})<1.992~{}{\rm
GeV}/c^{2}$. The background PDF consists of a zero-lifetime component and two
exponential components, all convoluted with a Gaussian resolution function
having a free mean and a width corresponding to $s\sigma_{t}$. To better
constrain the background parameters, a simultaneous fit to the candidates in
the signal region and sideband is performed by constraining the background
fraction obtained from a fit to $m(K^{-}\pi^{+}\pi^{+})$.

The lifetime fits are tested on simulated samples and the returned lifetimes
are consistent with the true values. The decay-time distributions of the data,
with fit projections overlaid, are shown in Fig. 2. The $D^{0}$ and $D^{+}$
lifetimes are measured to be $410.5\pm 1.1(\rm stat)\pm 0.8(\rm syst)$ fs and
$1030.4\pm 4.7(\rm stat)\pm 3.1(\rm syst)$ fs, respectively [11]. The results
are consistent with their respective world average values [9]. The systematic
uncertainties are summarized in Table 1 and the total systematic uncertainty
is the sum in quadrature of the individual components.

Figure 2: Decay-time distributions of (top) $D^{0}\to K^{-}\pi^{+}$ and (bottom) $D^{+}\to K^{-}\pi^{+}\pi^{+}$ candidates in their respective signal regions with fit projections overlaid. Table 1: Systematic uncertainties. Source |  $\tau(D^{0}\to K^{-}\pi^{+})$ [fs] |  $\tau(D^{+}\to K^{-}\pi^{+}\pi^{+})$ [fs]
---|---|---
Resolution model | 0.16 | 0.39
Backgrounds | 0.24 | 2.52
Detector alignment | 0.72 | 1.70
Momentum scale | 0.19 | 0.48
Total | 0.80 | 3.10

##  5 Systematic Uncertainty

A small correlation between $t$ and $\sigma_{t}$ is neglected in our nominal
fitting model. In order to quantify the effect 1000 signal-only samples of
simulated events with same statistics as data are fitted with the nominal PDF.
Upper bounds of 0.16 fs and 0.39 fs on the average absolute deviation of
measured lifetimes from their true value is assigned as a systematic
uncertainty due to imperfect resolution for $D^{0}\to K^{-}\pi^{+}$ and
$D^{+}\to K^{-}\pi^{+}\pi^{+}$, respectively.

A background contamination of 0.2% is neglected in the signal region of
$D^{0}\to K^{-}\pi^{+}$. To estimate the effect on our result, 500 simulated
samples of $e^{+}e^{-}$ events with same size and signal-to-background ratio
as data are fitted with the nominal model. The average absolute deviation of
fitted lifetime, after subtracting the uncertainty due to resolution modeling,
from the true value is 0.24 fs and assigned as systematic uncertainty due to
background contamination.

The background in $D^{+}\to K^{-}\pi^{+}\pi^{+}$ signal region is modeled
using data sideband. A mismatch between data and simulation in the sideband
may be indicating an imperfect description of background components in signal
region by the sideband. 1000 samples prepared using pseudo experiments in
signal region and simulated data in sideband reproduce the same level of
disagreement is fitted and the absolute average difference between the
measured and simulated lifetime, 2.52 fs, is assigned as the systematic
uncertainty due to background modeling.

Misalignment of tracking detectors may cause bias in the decay-length
determination and hence the lifetime. Two sources of uncertainties associated
with the alignment are considered: the statistical precision and a possible
systematic bias. The day-to-day difference between alignments in real data is
used for the statistical contribution. Samples of same statistics as data are
simulated by introducing realistic misalignment effects and the difference in
lifetime residual for a given misalignment configuration and that from a
perfectly aligned sample is assigned as systematic uncertainty.

##  6 Conclusions

In conclusion, the $D^{0}$ and $D^{+}$ lifetimes are measured using the data
collected by the Belle II experiment corresponding to an integrated luminosity
of $72~{}{\rm fb}^{-1}$. The results are the most precise to date and are
consistent with previous measurements.

## References

  * [1] M. Neubert, Adv. Ser. Dir. High Energy Phys. 15, 239 (1998).
  * [2] N. Uraltsev, in At the Frontier of Particle Physics, edited by M. Shifman and B. Ioffe (World Scientific, Singapore, 2001), https://dx.doi.org/10.1142/9789812810458_0034.
  * [3] A. Lenz and T. Rauh, Phys. Rev. D 88, 034004 (2013).
  * [4] A. Lenz, Int. J. Mod. Phys. A 30, 1543005 (2015).
  * [5] M. Kirk, A. Lenz, and T. Rauh, J. High Energy Phys. 12 (2017) 068; 06 (2020) 162(E).
  * [6] H.-Y. Cheng, J. High Energy Phys. 11 (2018) 014.
  * [7] T. Abe (Belle II Collaboration), arXiv:1011.0352.
  * [8] K. Akai, K. Furukawa, and H. Koiso, Nucl. Instrum. Methods Phys. Res., Sect. A 907, 188 (2018).
  * [9] P. A. Zyla et al. (Particle Data Group), Prog. Theor. Exp. Phys. 2020, 083C01 (2020).
  * [10] J.-F. Krohn et al. (Belle II Analysis Software Group), Nucl. Instrum. Methods Phys. Res., Sect. A 976, 164269(2020).
  * [11] F. Abudinén et al. (Belle II Collaboration), Phys. Rev. Lett 127, 211801 (2021)


9

# On $k$-uniform tight cycles: the Ramsey number for $C_{kn}^{(k)}$ and an
approximate Lehel’s conjecture

Vincent Pfenninger Institute of Discrete Mathematics, Graz University of
Technology, Austria, E-mail<EMAIL_ADDRESS>
###### Abstract

A _$k$ -uniform tight cycle_ is a $k$-graph with a cyclic ordering of its
vertices such that its edges are precisely the sets of $k$ consecutive
vertices in that ordering. We show that, for each $k\geq 3$, the Ramsey number
of the $k$-uniform tight cycle on $kn$ vertices is $(1+o(1))(k+1)n$. This is
an extension to all uniformities of previous results for $k=3$ by Haxell,
Łuczak, Peng, Rödl, Ruciński, and Skokan and for $k=4$ by Lo and the author
and confirms a special case of a conjecture by the former set of authors.

Lehel’s conjecture, which was proved by Bessy and Thomassé, states that every
red-blue edge-coloured complete graph contains a red cycle and a blue cycle
that are vertex-disjoint and together cover all the vertices. We also prove an
approximate version of this for $k$-uniform tight cycles. We show that, for
every $k\geq 3$, every red-blue edge-coloured complete $k$-graph on $n$
vertices contains a red tight cycle and a blue tight cycle that are vertex-
disjoint and together cover $n-o(n)$ vertices.

##  1 Introduction

For a $k$-graph ($k$-uniform hypergraph) $H$, we denote by $r(H)$ the _Ramsey
number_ of $H$, that is, the smallest integer $N$ such that every $2$-edge-
colouring of the complete $k$-graph on $N$ vertices contains a monochromatic
copy of $H$.111For any $2$-edge-colouring we will assume that the colours are
red and blue.

The Ramsey number for cycles in graphs was determined in [3, 5, 15] to be, for
$n\geq 5$,

$\displaystyle r(C_{n})=\begin{cases}\frac{3}{2}n-1,\quad\text{ if $n\in
2\mathbb{N}$},\\\ 2n-1,\quad\text{ if $n\in 2\mathbb{N}+1$}.\end{cases}$

There are several possible extensions of cycles to $k$-graphs. Here we will
focus on _tight cycles_. For the Ramsey number of _loose cycles_ , we refer
the reader to [16] and the references therein. We denote by $C_{n}^{(k)}$ the
_$k$ -uniform tight cycle on $n$ vertices_, that is the graph with vertex set
$V(C_{n}^{(k)})=\\{v_{1},\dots,v_{n}\\}$ and edge set
$E(C_{n}^{(k)})=\\{v_{i}\dots v_{i+k-1}\colon i\in[n]\\}$ where the indices
are taken modulo $n$. For $k=3$, Haxell, Łuczak, Peng, Rödl, Ruciński, and
Skokan [7, 8] determined $r(C_{n}^{(3)})$ asymptotically.222All asymptotics in
this paper are considered as $n\rightarrow\infty$ (and all other parameters
are fixed).

######  Theorem 1.1 (Haxell, Łuczak, Peng, Rödl, Ruciński, and Skokan [7, 8]).

$\displaystyle r(C_{3n+i}^{(3)})=\begin{cases}(1+o(1))4n,\quad\text{ if
$i=0$},\\\ (1+o(1))6n,\quad\text{ if $i\in\\{1,2\\}$}.\end{cases}$

The same authors also made a conjecture for the asymptotics of
$r(C_{n}^{(k)})$ for all $k\geq 3$.

######  Conjecture 1.2 (Haxell, Łuczak, Peng, Rödl, Ruciński, and Skokan [7,
8]).

For $k\geq 3$, $0\leq i\leq k-1$, and $d\coloneqq\gcd(k,i)$,

$r(C_{kn+i}^{(k)})=(1+o(1))\frac{d+1}{d}kn.$

The lower bound for 1.2 is given by the following construction. Let
$N=\frac{d+1}{d}kn-2$ and colour the edges of $K_{N}^{(k)}$ as follows.333We
denote by $K_{N}^{(k)}$ the complete $k$-graph on $N$ vertices. Partition the
vertices into two sets $X$ and $Y$ with $|X|=\frac{k}{d}n-1$ and $|Y|=kn-1$.
Then colour all edges which intersect $X$ in an even number of vertices red
and all other edges blue. For this colouring, there is no monochromatic copy
of $C_{kn+i}^{(k)}$ (see [9, Proposition 7.2]).

Lo and the author [9] proved that $r(C_{4n}^{(4)})=(1+o(1))5n$, confirming 1.2
in the case where $k=4$ and $i=0$. In this paper, we prove 1.2 in the case
where $i=0$ for all $k\geq 3$.

######  Theorem 1.3.

For $k\geq 3$ and $\varepsilon>0$, there exists a positive integer
$n_{0}=n_{0}(k,\varepsilon)$ such that if $n\geq n_{0}$, then
$r(C_{kn}^{(k)})\leq(k+1+\varepsilon)n$.

We remark that, as a straightforward corollary from this, we also obtain the
asymptotics of the Ramsey number for the $k$-uniform tight path on $n$
vertices. We define the _$k$ -uniform tight path_ $P_{n}^{(k)}$ as the
$k$-graph with vertex set $\\{v_{1},\dots,v_{n}\\}$ and edge set
$\\{v_{i}\dots v_{i+k-1}\colon i\in[n-k+1]\\}$.

######  Corollary 1.4.

For $k\geq 3$, $r(P_{n}^{(k)})=(1+o(1))\frac{k+1}{k}n$.

Indeed, the upper bound follows immediately from Theorem 1.3, since
$P_{n}^{(k)}$ is a sub-$k$-graph of the $k$-uniform tight cycle on
$k\lceil\frac{n}{k}\rceil$ vertices. The lower bound is given by the same
extremal example as the one for 1.2 with $i=0$.

Essentially the same proof as the one for Theorem 1.3 also gives an
approximate Lehel’s conjecture for $k$-uniform tight cycles. Lehel conjectured
that the vertices of every $2$-edge-coloured complete graph can be partitioned
into a red cycle and a blue cycle (where any set of at most $2$ vertices is
also considered a cycle). This was proved for large $n$ by Łuczak, Rödl, and
Szemerédi [14]. The bound on $n$ was later improved by Allen [1].
Subsequently, Bessy and Thomassé [2] gave a proof for all $n$. The analogous
problem for tight cycles in hypergraphs was first considered by Bustamante,
Hàn, and Stein [4] who showed that an approximate Lehel’s conjecture holds for
$3$-uniform tight cycles.

######  Theorem 1.5 (Bustamante, Hàn, and Stein [4]).

Every $2$-edge-coloured complete $3$-graph contains a red tight cycle and a
blue tight cycle that are vertex-disjoint and together cover $n-o(n)$
vertices.

This was improved upon by Garbe, Mycroft, Lang, Lo, and Sanhueza-Matamala [6].

######  Theorem 1.6 (Garbe, Mycroft, Lang, Lo, and Sanhueza-Matamala [6]).

There exists $n_{0}\in\mathbb{N}$ such that for every $n\geq n_{0}$ and every
$2$-edge-coloured complete $3$-graph on $n$ vertices, we have the following.

  1. (i)

There are a red tight cycle and a blue tight cycle that are vertex-disjoint
and together cover at least $n-2$ vertices.

  2. (ii)

There are two monochromatic tight cycles (possibly of the same colour) that
are vertex-disjoint and together cover all the vertices.

An example was given in [6] which shows the necessity of allowing the two
monochromatic tight cycles in Theorem 1.6 (ii) to possibly have the same
colour. This example was generalised to all uniformities $k\geq 3$ in [11].
Therefore, for $k\geq 3$, partitioning the vertices of every $2$-edge-coloured
complete $k$-graph into a red tight cycle and a blue tight cycle is not
possible.

Lo and the author [11] showed that an approximate Lehel’s conjecture still
holds for $4$-uniform tight cycles and gave a weaker result for $5$-uniform
tight cycles.

######  Theorem 1.7 (Lo and Pfenninger [11]).

We have the following.

  1. (i)

Every $2$-edge-coloured complete $4$-graph on $n$ vertices contains a red
tight cycle and a blue tight cycle that are vertex-disjoint and together cover
$n-o(n)$ vertices.

  2. (ii)

Every $2$-edge-coloured complete $5$-graph on $n$ vertices contains $4$
monochromatic tight cycles that are vertex-disjoint and together cover
$n-o(n)$ vertices.

In subsequent work, Lo and the author [10] showed that for a $2$-edge-coloured
$k$-graph, $k$ vertex-disjoint monochromatic tight cycles suffice to cover
almost all vertices.

######  Theorem 1.8 (Lo and Pfenninger [10]).

Every $2$-edge-coloured complete $k$-graph on $n$ vertices contains $k$
vertex-disjoint monochromatic tight cycles covering $n-o(n)$ vertices.

In this paper, we improve on this result by showing that an approximate
Lehel’s conjecture holds for $k$-uniform tight cycles for all $k\geq 3$.

######  Theorem 1.9.

For $k\geq 3$ and $\varepsilon>0$, there exists a positive integer
$n_{0}\coloneqq n_{0}(k,\varepsilon)$ such that if $n\geq n_{0}$, then every
$2$-edge-coloured complete $k$-graph on $n$ vertices contains a red tight
cycle and a blue tight cycle that are vertex-disjoint and together cover at
least $(1-\varepsilon)n$ vertices.

###  1.1 Proof Sketch

We now give a sketch of the proof of Theorem 1.3 and Theorem 1.9.

We use a, by now standard, method called _Łuczak’s connected matching method_
(introduced in [13]). Roughly speaking, the idea of the method is to apply
Szemerédi’s Regularity Lemma (or a hypergraph version thereof) and then find a
matching in the reduced graph that is ‘connected’ (where the appropriate
notion of ‘connectivity’ depends on the application). This ‘connected
matching’ is then converted into a cycle in the original graph (or
hypergraph). This means that the problem of finding a cycle in the original
graph is reduced to the problem of finding a ‘connected matching’, that is a
matching using only edges from a ‘connected component’, in the reduced graph.
To make this more precise, we need to define the right notion of a ‘connected
component’ for our setting which is the notion of a _monochromatic tight
component_. This is defined as follows. Let $H$ be a $k$-graph. We say that a
sequence of edges $e_{1}\dots e_{t}$ in $H$ is a _tight pseudo-walk (from
$e_{1}$ to $e_{t}$)_ if for every $i\in[t-1]$, $|e_{i}\cap e_{i+1}|\geq
k-1$.444For technical reasons, we allow $|e_{i}\cap e_{i+1}|=k$, that is,
$e_{i}=e_{i+1}$. A $k$-graph $H$ is called _tightly connected_ if for any two
edges $f,f^{\prime}\in E(H)$, there exists a tight pseudo-walk from $f$ to
$f^{\prime}$ in $H$. A _tight component of $H$_ is a maximal _tightly
connected_ sub-$k$-graph of $H$. If $H$ is $2$-edge-coloured, then the
_monochromatic tight components of $H$_ are the tight components of
$H^{\operatorname{red}}$ and $H^{\operatorname{blue}}$ (which are also called
_red tight components_ and _blue tight components_), respectively.555We denote
by $H^{\operatorname{red}}$ the sub-$k$-graph of $H$ induced by the red edges
of $H$ and define $H^{\operatorname{blue}}$ analogously.

The hypergraph version of Łuczak’s connected matching method we use (see
Corollary 6.2) now states that in order to prove Theorem 1.3 it suffices to
show that every $2$-edge-coloured ‘almost complete’ $k$-graph $H$ on $n$
vertices contains a monochromatic tight component $T$ and a matching in $T$ of
size at least $\frac{n}{k+1}$ (in fact a fractional matching of the same
weight suffices).

We find this matching as follows. Assume for simplicity that $H$ is complete.
In actuality, we will have to work with a $k$-graph that is only ‘almost
complete’.666We will define later what exactly we mean by ‘almost complete’.
However, this will not complicate the argument much. We start by showing that
there is a monochromatic tight component in $H$ that contains a matching $M$
of size at least $c_{k}n$, for some small constant $c_{k}$ depending only on
$k$ (see Lemma 4.1). Let us assume that this monochromatic tight component is
red and denote it by $R$. If $M$ is not yet large enough, we show that a
larger (fractional) matching in a monochromatic tight component can be found.
We then iterate this process to find larger and larger (fractional) matchings
that are contained in monochromatic tight components. To avoid having to deal
with increasingly complex fractional matchings, we convert fractional
matchings back to integral ones by moving to a blow-up of $H$ (noting that a
matching in a blow-up of $H$ can be converted into a fractional matching in
$H$ of the corresponding weight, as we show in Proposition 3.3).

Since it is possible that there is no larger matching in a red tight
component, we might have to switch the colour of our matching. To that end, we
first show that we can either find a larger (fractional) matching in $R$ or we
can find a matching $M^{\prime}$ in a blue tight component with
$|M^{\prime}|=|M|$ (see Lemma 5.1). We assign each edge $e\in M$ a distinct
vertex $v_{e}$ not covered by $M$. If for some $e\in M$ all the edges in
$H[e\cup\\{v_{e}\\}]$ are red, then $H[e\cup\\{v_{e}\\}]\subseteq R$ and we
get a larger fractional matching by giving weight $1/k$ to each of the $k+1$
edges in $H[e\cup\\{v_{e}\\}]$. It follows that for all $e\in M$, there is a
blue edge in $H[e\cup\\{v_{e}\\}]$. This gives us a matching $M^{\prime}$ of
blue edges in $H$ with $|M^{\prime}|=|M|$. We would like to now conclude that
all the edges in $M^{\prime}$ are in the same blue tight component of $H$
(unless there is a larger (fractional) matching in $R$). To show that this is
indeed the case, we use a crucial lemma about the structure of the
monochromatic tight components in $H$ that Lo and the author introduced in
[10]. This lemma (see Lemma 3.1) implies that if there is a tight pseudo-walk
$e_{1}\dots e_{t}$ where $e_{1}$ and $e_{t}$ are in different blue tight
components and $e_{2},\dots,e_{t-1}$ are all in the red tight component $R$,
then any tight pseudo-walk from $e_{1}$ to $e_{t}$ contains an edge of $R$.
This gives us a powerful tool to find edges in particular monochromatic tight
components. Suppose there are two edges $f,f^{\prime}\in M^{\prime}$ that are
in different blue tight components of $H$. Let $e$ and $e^{\prime}$ be the
unique edges in $M$ such that $|e\cap f|=k-1$ and $|e^{\prime}\cap
f^{\prime}|=k-1$. Since $e$ and $e^{\prime}$ are both in the red tight
component $R$, there exists a tight pseudo-walk $P$ from $e$ to $e^{\prime}$.
Applying the lemma to the tight pseudo-walk $fPf^{\prime}$ gives us that every
tight pseudo-walk from $f$ to $f^{\prime}$ contains an edge of $R$. This
allows us to find a larger (fractional) matching in $R$. Thus if we assume
that no larger (fractional) matching in $R$ exists, we can conclude that all
edges in $M^{\prime}$ are in the same blue tight component $B$ of $H$.

We now enlarge one of $M$ and $M^{\prime}$ as follows (see Lemma 5.2). Pick an
edge $g$ of $H$ which is disjoint from $V(M)\cup V(M^{\prime})$. Note that
$|V(M)\cup V(M^{\prime})|=(k+1)|M|$, so assuming $|M|<\frac{n}{k+1}$ there are
just enough vertices to pick $g$. Assume without loss of generality that $g$
is red. We may assume that $g\notin R$ (else we get a larger matching in $R$
by adding $g$ to $M$). Let $e\in M$ and let $e^{\prime}\in M^{\prime}$ be the
unique edge with $|e\cap e^{\prime}|=k-1$. Consider a tight pseudo-walk
$P^{*}$ from $e$ to $g$ with $V(P^{*})\subseteq e\cup g$. Since $e$ and $g$
are in different red tight components of $H$, we have that $P^{*}$ contains a
blue edge. Let $f$ be the first blue edge on $P^{*}$. If $f\notin B$, then the
tight pseudo-walk obtained by starting with $e^{\prime}$ and then following
$P^{*}$ from $e$ to $f$ allows us to again apply Lemma 3.1 to get a larger
fractional matching in $R$. Hence we may assume that $f\in B$. Generating more
edges of $B$ in this way allows us to obtain a larger fractional matching in
$B$.

To prove Theorem 1.9, we proceed similarly by first constructing a large
matching $M$ in a monochromatic tight component in the same way. Assume
without loss of generality that $M$ is in a red tight component $R$. By the
argument above, we can now assume that $|M|\geq\frac{n}{k+1}$ (possibly
replacing $H$ by a blow-up of it). Let $W\coloneqq V(H)\setminus V(M)$ and
note that $|W|\leq\frac{n}{k+1}$. Assign each vertex $w\in W$ to a unique edge
$e_{w}\in M$. As before we can show that unless we can move to a larger
(fractional) matching in $R$, there exists a blue tight component $B$ of $H$
such that for each $w\in W$, $H[e_{w}\cup\\{w\\}]$ contains an edge of $B$.
Since $e_{w}\cup\\{w\\}$ is a set of $k+1$ vertices that contains a red edge
of $R$ and a blue edge of $B$, we have that any edge in $H[e_{w}\cup\\{w\\}]$
is in $R$ or $B$. We let $\varphi$ be the fractional matching which gives
weight $1/k$ to all $k+1$ edges of $H[e_{w}\cup\\{w\\}]$ for each $w\in W$ and
weight $1$ to each edge in $M\setminus\\{e_{w}\colon w\in W\\}$. We have that
$\varphi$ has weight $\frac{n}{k}$ and only gives non-zero weight to edges in
$R$ or $B$. The hypergraph version of Łuczak’s connected matching method we
use (Corollary 6.2) implies that this is enough to prove Theorem 1.9.

##  2 Preliminaries

For a positive integer $k$, we let $[k]=\\{1,\dots,k\\}$ and for a set $V$, we
let $\binom{V}{k}$ be the set of subsets of $V$ of size $k$. We sometimes
abuse notation by writing $x_{1}\dots x_{j}$ for $\\{x_{1},\dots,x_{j}\\}$.

A _$k$ -graph_ $H$, is a pair of sets $(V(H),E(H))$ such that
$E(H)\subseteq\binom{V(H)}{k}$. We call the elements of $V(H)$ _vertices_ and
the elements of $E(H)$ _edges_. We abuse notation and identify $H$ with its
edge set $E(H)$. In particular, by $|H|$ we mean the number of edges of $H$.
For $W\subseteq V(H)$, we denote by $H[W]$ the $k$-graph with $V(H[W])=W$ and
$E(H[W])=\\{e\in E(H)\colon e\subseteq W\\}$. For $S\subseteq V(H)$ with
$1\leq|S|\leq k-1$, we let
$N_{H}(S)\coloneqq\\{S^{\prime}\in\binom{V(H)}{k-|S|}\colon S^{\prime}\cup
S\in H\\}$ and $d_{H}(S)\coloneqq|N_{H}(S)|$.

A _matching_ in a $k$-graph is a set $M$ of pairwise disjoint edges of $H$.
For a matching $M$ in $H$, we denote by $V(M)$ the set of vertices covered by
$M$, that is, $V(M)\coloneqq\bigcup M$. A _fractional matching_ in $H$ is a
function $\varphi\colon H\rightarrow[0,1]$ such that for each $v\in V(H)$,
$\sum_{e\in H,\,v\in e}\varphi(e)\leq 1$. For each edge $e\in H$, we call
$\varphi(e)$ the _weight of $e$ given by $\varphi$_. The _weight of $\varphi$_
is $\sum_{e\in H}\varphi(e)$. For a matching $M$ in $H$, the _fractional
matching induced by $M$_ is the fractional matching $\varphi\colon
H[V(M)]\rightarrow[0,1]$ with $\varphi(e)=1$ if $e\in M$ and $\varphi(e)=0$
otherwise. For $r\in\mathbb{N}$, $\varphi$ is called _$1/r$ -fractional_, if
$\varphi(e)\in\\{0,1/r,2/r,\dots,(r-1)/r,1\\}$ for all $e\in H$. Let $H_{1}$
and $H_{2}$ be $k$-graphs with $V(H_{1})\cap V(H_{2})=\varnothing$. We define
$H_{1}\cup H_{2}$ to be the $k$-graph with $V(H_{1}\cup H_{2})=V(H_{1})\cup
V(H_{2})$ and $E(H_{1}\cup H_{2})=E(H_{1})\cup E(H_{2})$. Let $\varphi_{1}$
and $\varphi_{2}$ be fractional matchings in $H_{1}$ and $H_{2}$,
respectively. Then we define $\varphi_{1}+\varphi_{2}\colon H_{1}\cup
H_{2}\rightarrow[0,1]$ to be the fractional matching in $H_{1}\cup H_{2}$ with
$(\varphi_{1}+\varphi_{2})(e)=\varphi_{1}(e)$ if $e\in H_{1}$ and
$(\varphi_{1}+\varphi_{2})(e)=\varphi_{2}(e)$ if $e\in H_{2}$. Let $H$ be a
$k$-graph and $H^{\prime}$ be a sub-$k$-graph of $H$. For a fractional
matching $\varphi$ in $H^{\prime}$, we define the _completion of $\varphi$
with respect to $H$_ to be the fractional matching $\varphi^{H}$ in $H$ with
$\varphi^{H}(e)=\varphi(e)$ for $e\in H^{\prime}$ and $\varphi^{H}(e)=0$ for
$e\in H\setminus H^{\prime}$. If $H$ is a $2$-edge-coloured $k$-graph and $T$
is a monochromatic tight component of $H$, then we abuse notation and do not
distinguish between fractional matchings in $T$ and fractional matchings in
$H$ which give non-zero weight only to edges in $T$. We call both of these
_fractional matchings in $T$_.

We use the _hierarchy notation_ , that is when we say that a statement holds
for $0<a\ll b\leq 1$ this is a short form of stating that there exists a non-
decreasing function $a_{0}\colon(0,1]\rightarrow(0,1]$ such that the statement
holds for all $a,b\in(0,1]$ with $a\leq a_{0}(b)$ (so the statement holds
provided that $a$ is sufficiently small in terms of $b$). Hierarchies with
more variables are defined similarly. Moreover, if $1/a$ appears in a
hierarchy we implicitly assume that $a$ is a positive integer.

We omit floors and ceilings whenever doing so does not affect the argument.

##  3 The Structure of Monochromatic Tight Components and Blow-ups

The following lemma is a result from earlier work of Lo and the author [10].
It gives crucial structural information about the monochromatic tight
components in a $2$-edge-coloured ‘almost complete’ $k$-graph. To state the
lemma, we define a _closed tight pseudo-walk_ in a $k$-graph $H$ as a tight
pseudo-walk $e_{1}\dots e_{t}$ with $|e_{1}\cap e_{t}|\geq k-1$.

######  Lemma 3.1 ([10, Lemma 3.6]).

Let $1/n\ll\varepsilon\ll 1/k\leq 1/2$. Let $H$ be a $2$-edge-coloured
$(1-\varepsilon,\varepsilon)$-dense $k$-graph on $n$ vertices. Let
$Q=e_{1}\dots e_{m}$ be a closed tight pseudo-walk in $H$ such that for some
$1<i<m$, we have that $e_{1}$ and $e_{i}$ are edges in different blue tight
components of $H$. Then there exists a red edge in $\\{e_{2}\dots,e_{i-1}\\}$
that is in the same red tight component as a red edge in
$\\{e_{i+1},\dots,e_{m}\\}$. The statement also holds with colours reversed.

We will make use of Lemma 3.1 several times to find more edges of a given
monochromatic tight component. To define the closed tight pseudo-walks to
apply Lemma 3.1, it will be convenient to use the notion of a _tight pseudo-
walk induced by a vertex sequence_. For a sequence $x_{1}\dots x_{t}$ of
vertices in a $k$-graph $H$, we define the _tight pseudo-walk induced by the
vertex sequence $x_{1}\dots x_{t}$_ as the tight pseudo-walk $e_{1}\dots
e_{t-k+1}$ where for $i\in[t-k+1]$, $e_{i}=x_{i}\dots x_{i+k-1}$.

As we mentioned in the proof sketch, we use blow-ups to avoid some of the
difficulties of dealing with fractional matchings. We make sure that our
factional matchings always give rational weights to edges. So they are
$1/r$-fractional matchings, for some $r\in\mathbb{N}$, which means they
correspond to matchings in an $r$-blow-up of the original $k$-graph. To that
end, let us define $r$-blow-ups formally.

######  Definition 3.2 ($r$-blow-up).

For $k$-graphs $H_{*}$ and $H$, we say that $H_{*}$ is an $r$-blow-up of $H$
if there exists a partition $\\{V_{x}\colon x\in V(H)\\}$ of $V(H_{*})$ into
parts of size $r$ such that

$H_{*}=\bigcup_{x_{1}\dots x_{k}\in H}K_{V_{x_{1}},\dots,V_{x_{k}}},$

where $K_{V_{x_{1}},\dots,V_{x_{k}}}$ is the complete $k$-partite $k$-graph
with parts $V_{x_{1}},\dots,V_{x_{k}}$. Moreover, if $H$ is $2$-edge-coloured,
we require that $H_{*}$ is $2$-edge-coloured and

$H_{*}^{\operatorname{red}}=\bigcup_{x_{1}\dots x_{k}\in
H^{\operatorname{red}}}K_{V_{x_{1}},\dots,V_{x_{k}}}\quad\text{ and }\quad
H_{*}^{\operatorname{blue}}=\bigcup_{x_{1}\dots x_{k}\in
H^{\operatorname{blue}}}K_{V_{x_{1}},\dots,V_{x_{k}}}.$

Denote by $\pi\colon H_{*}\rightarrow H$, the map such that for $e_{*}\in
H_{*}$, $\pi(e_{*})=x_{1}\dots x_{k}\in H$ is the unique edge such that
$e_{*}\in K_{V_{x_{1}},\dots,V_{x_{k}}}$. Note that, if $H$ is $2$-edge-
coloured, then $\pi$ induces a map $\pi_{\mathrm{MTC}}$ from the set of
monochromatic tight components $\mathcal{C}(H_{*})$ of $H$ to the set of
monochromatic tight components $\mathcal{C}(H)$ of $H$, where for
$T\in\mathcal{C}(H_{*})$, $\pi_{\mathrm{MTC}}(T)=\\{\pi(e)\colon e\in
T\\}\in\mathcal{C}(H)$. In fact, it is easy to see that $\pi_{\mathrm{MTC}}$
is a bijection and for each $T\in\mathcal{C}(H_{*})$, $T$ and
$\pi_{\mathrm{MTC}}(T)$ have the same colour.

The following proposition gives the fact that having a
$1/(rr^{\prime})$-fractional matching in a $k$-graph $H$ of weight $\mu|V(H)|$
is equivalent to having a $1/r^{\prime}$-fractional matching in the $r$-blow-
up $H_{*}$ of $H$ of weight $\mu|V(H_{*})|$. Moreover, this equivalence
behaves well with respect to monochromatic tight components.

######  Proposition 3.3 (see also [9, Proposition 3.3]).

Let $r,r^{\prime}\geq 1$ and $k\geq 2$. Let $H$ be a $2$-edge-coloured
$k$-graph and let $H_{*}$ be an $r$-blow-up of $H$. Let $\mathcal{C}_{*}$ be a
set of monochromatic tight components in $H_{*}$ and let
$\mathcal{C}\coloneqq\\{\pi_{\mathrm{MTC}}(T_{*})\colon
T_{*}\in\mathcal{C}_{*}\\}$ be the corresponding set of monochromatic tight
components in $H$. Then the following are equivalent.

  1. (F1)

There exists a $1/r^{\prime}$-fractional matching $\varphi_{*}$ in $H_{*}$ of
weight $\mu|V(H_{*})|$ such that $\\{e\in
H_{*}\colon\varphi_{*}(e)>0\\}\subseteq\bigcup\mathcal{C}_{*}$.

  2. (F2)

There exists a $1/(rr^{\prime})$-fractional matching $\varphi$ in $H$ of
weight $\mu|V(H)|$ such that $\\{e\in
H\colon\varphi(e)>0\\}\subseteq\bigcup\mathcal{C}$.

###### Proof.

We show that (F1) implies (F2). We omit the proof of the other direction as it
is analogous. Given $\varphi_{*}$, we let $\varphi\colon H\rightarrow[0,1]$ be
the fractional matching with

$\displaystyle\varphi(e)\coloneqq\frac{1}{r}\sum_{f\in\pi^{-1}(e)}\varphi_{*}(f).$

To check that $\varphi$ indeed takes values in $[0,1]$, fix $e\in H$ and $x\in
e$. We have

$\displaystyle\varphi(e)=\frac{1}{r}\sum_{f\in\pi^{-1}(e)}\varphi_{*}(f)=\frac{1}{r}\sum_{y\in
V_{x}}\sum_{f\in\pi^{-1}(e),\,y\in f}\varphi_{*}(f)\leq\frac{1}{r}\sum_{y\in
V_{x}}\sum_{f\in H_{*},\,y\in f}\varphi_{*}(f)\leq 1,$

since $|V_{x}|=r$ and for each $y\in V_{x}$, $\sum_{f\in H_{*},\,y\in
f}\varphi_{*}(f)\leq 1$ as $\varphi_{*}$ is a fractional matching in $H_{*}$.
To check that $\varphi$ is indeed a fractional matching in $H$, note that, for
$x\in V(H)$, we have

$\displaystyle\sum_{\begin{subarray}{c}e\in H,\,x\in
e\end{subarray}}\varphi(e)=\frac{1}{r}\sum_{\begin{subarray}{c}e\in H,\,x\in
e\end{subarray}}\sum_{f\in\pi^{-1}(e)}\varphi_{*}(f)=\frac{1}{r}\sum_{f\in
H_{*},\,f\cap V_{x}\neq\varnothing}\varphi_{*}(f)=\frac{1}{r}\sum_{y\in
V_{x}}\sum_{f\in H_{*},\,y\in f}\varphi_{*}(f)\leq 1.$

Since $\varphi_{*}$ is a $1/r^{\prime}$-fractional matching, $\varphi$ is a
$1/(rr^{\prime})$-fractional matching. Note that the weight of $\varphi$ is

$\displaystyle\sum_{e\in H}\varphi(e)=\frac{1}{r}\sum_{e\in
H}\sum_{f\in\pi^{-1}(e)}\varphi_{*}(f)=\frac{1}{r}\sum_{f\in
H_{*}}\varphi_{*}(f)=\frac{1}{r}\mu|V(H_{*})|=\mu|V(H)|.$

If $\varphi_{*}$ only gives non-zero weight to edges in
$\bigcup\mathcal{C}_{*}$, then by the definition of $\varphi$, we have that
$\varphi$ only gives non-zero weight to edges in $\bigcup\mathcal{C}$. ∎

We now define our notion of ‘almost complete’. We say that a $k$-graph is
_$(\mu,\alpha)$ -dense_ if for every $i\in[k-1]$ and all but at most
$\alpha\binom{n}{i}$ sets $S\in\binom{V(H)}{i}$, we have
$d_{H}(S)\geq\mu\binom{n}{k-i}$ and $d_{H}(S)=0$ for all other
$S\in\binom{V(H)}{i}$. We think of a $k$-graph $H$ that is
$(1-\varepsilon,\varepsilon)$-dense, for some small $\varepsilon>0$, as
‘almost complete’. One reason this is a convenient notion of ‘almost complete’
is that if we have an edge $e\in H$, then this means that any subset
$S\subsetneq e$ is contained in almost as many edges as if $H$ was complete
(since $S$ is contained in $e$, we have $d_{H}(S)>0$ and thus
$d_{H}(S)\geq(1-\varepsilon)\binom{n}{k-|S|}$ since $H$ is
$(1-\varepsilon,\varepsilon)$-dense).

The following proposition states that being ‘almost complete’ is preserved
under taking a blow-up.

######  Proposition 3.4 ([9, Proposition 3.2]).

Let $1/n\ll\varepsilon,\alpha,1/r,1/k$ and $k\geq 2$. Let $H$ be a
$(1-\varepsilon,\alpha)$-dense $k$-graph on $n$ vertices and let $H_{*}$ be an
$r$-blow-up of $H$. Then $H_{*}$ is $(1-2\varepsilon,2\alpha)$-dense.

##  4 The Initial Monochromatic Tight Component

In this section, we show that a $2$-edge-coloured ‘almost complete’ $k$-graph
$H$ has a monochromatic tight component which contains a matching of linear
size. This will be the starting point from which we will then show that we can
construct larger and larger matchings.

######  Lemma 4.1.

Let $1/n\ll\varepsilon\ll 1/k\leq 2$. Let $H$ be a $2$-edge-coloured
$(1-\varepsilon,\varepsilon)$-dense $k$-graph on $n$ vertices. Then $H$
contains a monochromatic tight component $T$ that contains a matching of size
at least $\frac{n}{2k^{2}15^{k}}$.

We derive this from the fact that every $k$-graph which has a constant
fraction of all possible edges, contains a tight component which still has a
constant fraction of all possible edges.

######  Proposition 4.2.

Let $1/n\ll\alpha,1/k<1$. Let $H$ be a $k$-graph on $n$ vertices with
$|H|\geq\alpha\binom{n}{k}$. Then $H$ contains a tight component $T$ with
$|T|\geq\left(\frac{\alpha}{5}\right)^{k}\binom{n}{k}$.

To prove this, it is convenient to introduce the notion of the ‘shadow’ of a
$k$-graph. For a $k$-graph $H$, we define its shadow $\partial H$ as the
$k$-graph with $V(\partial H)=V(H)$ and $E(\partial
H)=\\{e\in\binom{V(H)}{k-1}\colon e\subseteq f\text{ for some }f\in E(H)\\}$.
We use the following theorem which is called the Lovász version of the
Kruskal-Katona theorem and gives a lower bound on the size of the shadow.

######  Theorem 4.3 (Lovász 1979 [12]).

Let $k\geq 2$ and let $H$ be a $k$-graph with $|H|\geq\binom{x}{k}$ for some
$x\geq 0$, then $|\partial H|\geq\binom{x}{k-1}$.777Here we define
$\binom{x}{k}=\frac{1}{k!}\prod_{i=1}^{k}(x-i+1)$ for any $x\in\mathbb{R}$ and
$k\in\mathbb{N}$.

We are now ready to prove Proposition 4.2.

###### Proof of Proposition 4.2.

Let $\beta\coloneqq(\alpha/5)^{k}$. Suppose for a contradiction that all tight
components in $H$ have size less than $2\beta\binom{n}{k}$. Then we can
partition $H=H_{0}\dot{\cup}H_{1}\dot{\cup}\dots\dot{\cup}H_{\ell}$ such that
$|H_{0}|<\beta\binom{n}{k}$, and for each $i\in[\ell]$, $H_{i}$ is a union of
tight components of $H$ with
$\beta\binom{n}{k}\leq|H_{i}|<2\beta\binom{n}{k}$.888Indeed, such a partition
can be obtained as follows. Start with each tight component as its own set.
Then, as long as there are two sets of size less than $\beta\binom{n}{k}$,
replace those two sets by their union. Note that

$\displaystyle\partial H_{i}\cap\partial H_{j}=\varnothing\quad\text{ for all
}\quad 1\leq i<j\leq\ell$ (4.1)

since $H_{i}$ and $H_{j}$ consist of distinct tight components. Let
$i\in[\ell]$. Note that
$|H_{i}|\geq\beta\binom{n}{k}\geq\binom{\beta^{1/k}n}{k}$. By Theorem 4.3,
$|\partial H_{i}|\geq\binom{\beta^{1/k}n}{k}$. Hence, by 4.1, we have

$\displaystyle\binom{n}{k-1}\geq\sum_{i\in[\ell]}|\partial
H_{i}|\geq\ell\binom{\beta^{1/k}n}{k-1}\geq\frac{\ell\beta^{\frac{k-1}{k}}}{2}\binom{n}{k-1}.$

Thus $\ell\leq 2\beta^{-\frac{k-1}{k}}$. It follows that

$\displaystyle(\alpha-\beta)\binom{n}{k}<|H|-|H_{0}|\leq\sum_{i\in[\ell]}|H_{i}|\leq
2\ell\beta\binom{n}{k}<4\beta^{1/k}\binom{n}{k}<(5\beta^{1/k}-\beta)\binom{n}{k}.$

Since $\beta=(\alpha/5)^{k}$, this is a contradiction. ∎

We can now derive Lemma 4.1 from Proposition 4.2.

###### Proof of Lemma 4.1.

Note that since $H$ is $(1-\varepsilon,\varepsilon)$-dense, we have

$\displaystyle|H|\geq\frac{1}{k}\sum_{S\in\binom{V(H)}{k-1}}d_{H}(S)\geq\frac{1}{k}(1-\varepsilon)^{2}\binom{n}{k-1}n\geq(1-\varepsilon)^{2}\binom{n}{k}.$

Hence we may assume without loss of generality that

$\displaystyle|H^{\operatorname{red}}|\geq\frac{1}{2}(1-\varepsilon)^{2}\binom{n}{k}\geq\frac{1}{3}\binom{n}{k}.$

By Proposition 4.2, we have that $H^{\operatorname{red}}$ contains a tight
component $T$ with $|T|\geq\frac{1}{15^{k}}\binom{n}{k}$. Since $T$ is a red
tight component in $H$, it now suffices to show that $T$ contains a matching
of size at least $\frac{n}{2k^{2}15^{k}}$. Let $M$ be a maximal matching in
$T$. Since every edge of $T$ intersects at least one edge in $M$, we have

$\displaystyle\frac{1}{15^{k}}\binom{n}{k}\leq|T|\leq|M|\,k\binom{n-1}{k-1}.$

It follows that $|M|\geq\frac{n}{2k^{2}15^{k}}$. ∎

##  5 Larger and Larger Matchings

In this section, we show how to find successively larger (fractional)
matchings in a $2$-edge-coloured ‘almost complete’ $k$-graph that are
contained in monochromatic tight components.

We first show that given a matching $M$ in a red tight component $R$ (that is
not yet large enough), we can either find a larger (fractional) matching in
$R$ or we can find a blue tight component that contains a matching which is
about as large as $M$ and intersects $M$ in a ‘simple’ way.

######  Lemma 5.1.

Let $1/n\ll\varepsilon\ll\gamma\ll\eta\ll 1/k$ with $k\geq 3$ and let $r=k!$.
Let $H$ be a $2$-edge-coloured $(1-\varepsilon,\varepsilon)$-dense $k$-graph
on $n$ vertices. Let $M$ be a matching in a red tight component $R$ of $H$
with $\eta n\leq|M|\leq(1-\eta)n/k$. Then at least one of the following holds.

  1. (M1)

There is a $1/r$-fractional matching in $R$ of weight at least $|M|+\gamma n$.

  2. (M2)

There is a matching $M^{\prime}$ in a blue tight component of $H$ with

$|M^{\prime}|\geq\min(|M|,n-|V(M)|)-\sqrt{\gamma}n$

such that each edge $e\in M^{\prime}$ intersects exactly one edge $f(e)\in M$
and $|e\cap f(e)|=k-1$ and $H[e\cup f(e)]\cong K_{k+1}^{(k)}$.

The same statement holds with colours reversed.

The next lemma shows that if our matchings are not yet large enough and we are
in the situation arising from (M2), then we can extend either the red matching
or the blue matching to get a larger (fractional) matching.

######  Lemma 5.2.

Let $1/n\ll\varepsilon\ll\delta\ll\eta\ll 1/k$ with $k\geq 3$ and let $r=k!$.
Let $H$ be a $2$-edge-coloured $(1-\varepsilon,\varepsilon)$-dense $k$-graph
on $n$ vertices. Let $R$ and $B$ be a red and a blue tight component of $H$,
respectively. Let $\eta n\leq t\leq\left(1-\eta\right)\frac{n}{k+1}$. Let $M$
be a matching in $R$ and let $M^{\prime}$ be a matching in $B$ with
$|M|=|M^{\prime}|=t$ such that there exists a bijection $g\colon M\rightarrow
M^{\prime}$ such that for each $f\in M$, $f\cap V(M^{\prime})\subseteq g(f)$,
$|f\cap g(f)|=k-1$, and $H[f\cup g(f)]\cong K_{k+1}^{(k)}$. Then there exists
a $1/r$-fractional matching in $R$ or in $B$ of weight at least $t+\delta n$.

###  5.1 Proof of Lemma 5.1

###### Proof of Lemma 5.1.

Let $W\coloneqq V(H)\setminus V(M)$. Since $|M|\leq(1-\eta)n/k$, we have
$|W|\geq\eta n$. Let $M^{*}\subseteq M$ with $|M^{*}|=\min(|M|,|W|)-\gamma n$.
Let $e\in M^{*}$ and note that, since $H$ is
$(1-\varepsilon,\varepsilon)$-dense, we have

$\left\lvert
W\cap\bigcap_{S\in\binom{e}{k-1}}N_{H}(S)\right\rvert\geq|W|-k\varepsilon
n\geq|M^{*}|.$

Hence we may choose distinct vertices $w_{e}\in
W\cap\bigcap_{S\in\binom{e}{k-1}}N_{H}(S)$ for each $e\in M^{*}$. Let
$M_{0}\coloneqq\\{e\in M^{*}\colon H^{\operatorname{red}}[e\cup w_{e}]\cong
K^{(k)}_{k+1}\\}$. Note that if $|M_{0}|\geq k\gamma n$, then we are done
since the $1/r$-fractional matching $\varphi\colon R\rightarrow[0,1]$ with
$\varphi(e)=1$ for each $e\in M\setminus M_{0}$, $\varphi(f)=1/k$ for each
$f\in\bigcup_{e\in M_{0}}H[e\cup w_{e}]$, and $\varphi(f)=0$ otherwise has
weight at least $|M|+\gamma n$ (and thus satisfies (M1)). Thus we may assume
that $|M_{0}|\leq k\gamma n$.

Let $M^{**}\coloneqq M^{*}\setminus M_{0}$. Note that

$\displaystyle\eta n/2\leq\min(|M|,|W|)-(k+1)\gamma
n\leq|M^{**}|\leq|M^{*}|=\min(|M|,|W|)-\gamma n.$ (5.1)

For each $e\in M^{**}$, choose a blue edge $f_{e}\in
H^{\operatorname{blue}}[e\cup w_{e}]$ (which exists since $e\notin M_{0}$).
Let $M_{1}\coloneqq\\{f_{e}\colon e\in M^{**}\\}$. Consider the auxiliary
graph $G$ with $V(G)=M_{1}$ and for $f,f^{\prime}\in M_{1}$, $ff^{\prime}\in
E(G)$ if and only if $f$ and $f^{\prime}$ are in different blue tight
components of $H$.

  1. Case A:

The graph $G$ contains a matching $M_{G}$ of size $k\gamma n$. If follows from
the fact that $H$ is $(1-\varepsilon,\varepsilon)$-dense and $|W|\geq\eta n$
that we can choose disjoint sets $W_{F}\in\binom{W}{k-1}$ for each
$F=f_{1}f_{2}\in M_{G}$ such that $H[f_{1}\cup W_{F}]\cong H[f_{2}\cup
W_{F}]\cong K_{2k-1}^{(k)}$. Let $F=f_{1}f_{2}\in M_{G}$. We denote by $e_{1}$
and $e_{2}$ the unique edges in $M^{*}\setminus M_{0}$ such that $|e_{1}\cap
f_{1}|=|e_{2}\cap f_{2}|=k-1$.

######  Claim 5.3.

There exists a $1/r$-fractional matching $\varphi_{F}\colon R[e_{1}\cup
f_{1}\cup e_{2}\cup f_{2}\cup W_{F}]\rightarrow[0,1]$ of weight at least
$2+1/k$.

###### Proof of Claim.

Let $W_{F}=\\{w_{1},\dots,w_{k-1}\\}$. Let $(x_{1},x_{2})\in f_{1}\times
f_{2}$ and fix arbitrary orders $f_{1}\setminus x_{1}=u_{1}\dots u_{k-1}$ and
$f_{2}\setminus x_{2}=v_{1}\dots v_{k-1}$. Let $P_{x_{1},x_{2}}$ be the tight
pseudo-walk induced by the vertex sequence $x_{1}u_{1}\dots u_{k-1}w_{1}\dots
w_{k-1}v_{1}\dots v_{k-1}x_{2}$ (note that $P_{x_{1},x_{2}}$ starts in $f_{1}$
and ends in $f_{2}$). Observe that since $e_{1},e_{2}\in R$, there exists a
tight pseudo-walk $P^{*}$ in $R$ from $e_{2}$ to $e_{1}$. Since $f_{1}$ and
$f_{2}$ are in different blue tight components, by applying Lemma 3.1 to the
closed tight pseudo-walk obtained by concatenating $P_{x_{1},x_{2}}$ and
$P^{*}$, we deduce that $P_{x_{1},x_{2}}$ contains an edge $f_{x_{1},x_{2}}\in
R$. Note that for each $(x_{1},x_{2})\in f_{1}\times f_{2}$, the edge
$f_{x_{1},x_{2}}$ intersects either $f_{1}$ or $f_{2}$ but not both and
moreover

$\displaystyle f_{x_{1},x_{2}}\cap\\{x_{1},x_{2}\\}=\varnothing.$ (5.2)

Let $x_{1}\in f_{1}$ and consider the set of edges
$E_{x_{1}}=\\{f_{x_{1},x_{2}}\colon x_{2}\in f_{2}\\}$. If all edges in
$E_{x_{1}}$ intersect $f_{2}$, then we obtain the desired $1/r$-fractional
matching $\varphi_{F}$ by setting $\varphi_{F}(e_{1})=1$,
$\varphi_{F}(f)=1/|E_{x_{1}}|$ for all $f\in\\{e_{2}\\}\cup E_{x_{1}}$, and
$\varphi_{F}(f)=0$ otherwise. Note that $\bigcap(\\{e_{2}\\}\cup
E_{x_{1}})=\varnothing$ by 5.2 which implies that $\varphi_{F}$ is indeed a
fractional matching as no vertex is contained in all $|E_{x_{1}}|+1$ edges in
$\\{e_{2}\\}\cup E_{x_{1}}$. Hence we may assume that for every $x_{1}\in
f_{1}$ there exists $x_{2}(x_{1})\in f_{2}$ such that $f_{x_{1},x_{2}(x_{1})}$
intersects $f_{1}$ (and thus does not intersect $f_{2}$). Let
$E=\\{f_{x_{1},x_{2}(x_{1})}\colon x_{1}\in f_{1}\\}$. We obtain the desired
$1/r$-fractional matching $\varphi_{F}$ by setting $\varphi_{F}(e_{2})=1$,
$\varphi_{F}(f)=1/|E|$ for each $f\in\\{e_{1}\\}\cup E$ and $\varphi_{F}(f)=0$
otherwise (noting that $\bigcap(\\{e_{1}\\}\cup E)=\varnothing$ by 5.2). ∎

Now let $\widetilde{M}\coloneqq(M\setminus M^{**})\cup\\{e\in M^{**}\colon
f_{e}\notin V(M_{G})\\}$. Let $\varphi_{0}$ be the fractional matching induced
by the matching $\widetilde{M}$. Now the completion of $\varphi_{0}+\sum_{F\in
M_{G}}\varphi_{F}$ with respect to $R$ is a $1/r$-fractional matching in $R$
of weight at least $|M|+|M_{G}|/k=|M|+\gamma n$ (and thus satisfies (M1)).

  2. Case B:

The graph $G$ does not contain a matching of size $k\gamma n$.

It follows that $G$ contains an independent set $M^{\prime}$ of size at least
$|V(G)|-2k\gamma n$. Note that $M^{\prime}\subseteq M_{1}$ is a matching in
$H^{\operatorname{blue}}$ and since it is an independent set in $G$ it is
contained in a blue tight component $B$ of $H$ (by the definition of $G$).
Observe that $|M^{\prime}|\geq|V(G)|-2k\gamma n=|M^{**}|-2k\gamma
n\geq\min(|M|,|W|)-(3k+1)\gamma n\geq\min(|M|,n-|V(M)|)-\sqrt{\gamma}n$ by 5.1
and the definition of $W$. Hence we are done since $M^{\prime}$ satisfies
(M2).∎

###  5.2 Proof of Lemma 5.2

###### Proof of Lemma 5.2.

Let $W\coloneqq V(H)\setminus(V(M)\cup V(M^{\prime}))$ and note that $|W|\geq
n-(k+1)t\geq\eta n$. Since $H$ is $(1-\varepsilon,\varepsilon)$-dense, it
follows that there exists a matching $M_{0}$ in $H[W]$ of size $8k\delta n$
and an injection $f\colon M_{0}\rightarrow M$ such that for each $e\in M_{0}$,
$H[e\cup f(e)\cup g(f(e))]\cong K_{2k+1}^{(k)}$. Indeed, it is easy to see
that for an edge $f\in M$, we can greedily choose vertices
$w_{1},\dots,w_{k}\in W$ one by one such that for each $i\in[k]$,
$H[w_{1}\dots w_{i}\cup f\cup g(f)]\cong K_{k+1+i}^{(k)}$ (so that we can then
set $f(e)=f$ for $e=w_{1}\dots w_{k}$). Doing this for $8k\delta n$ many
different edges in $M$ (using new vertices in $W$ each time) gives the desired
matching $M_{0}$ in $H[W]$ and the desired injection $f\colon M_{0}\rightarrow
M$. Let $M_{1}\subseteq M_{0}$ be a monochromatic matching of size $4k\delta
n$. Assume without loss of generality that $M_{1}$ is red. If there exists
$M_{2}\subseteq M_{1}$ such that $M_{2}\subseteq R$ and $|M_{2}|=2k\delta n$,
then we are done since the $1/r$-fractional matching induced by $M_{2}\cup M$
has weight $t+2k\delta n\geq t+\delta n$. Hence we may assume that there
exists $M_{3}\subseteq M_{1}$ with $|M_{3}|=2k\delta n$ such that no edge of
$M_{3}$ is in $R$. For $e\in M_{3}$, recall that $g(f(e))\in
M^{\prime}\subseteq B$ is the unique edge that intersects $f(e)\in M\subseteq
R$. Let $e\in M_{3}$. We fix arbitrary orders $e=w_{1}(e)\dots
w_{k}(e)\eqqcolon w_{1}\dots w_{k}$ and $f(e)\cap g(f(e))=z_{1}(e)\dots
z_{k-1}(e)\eqqcolon z_{1}\dots z_{k-1}$. Let $x\coloneqq x(e)$ be the unique
vertex in $f(e)\setminus g(f(e))$ and let $y\coloneqq y(e)$ be the unique
vertex in $g(f(e))\setminus f(e)$. For each $i\in[k-1]$, consider the tight
pseudo-walk $P_{i}(e)$ induced by the vertex sequence $z_{i}xz_{1}\dots
z_{i-1}z_{i+1}\dots z_{k-1}w_{1}\dots w_{k}$. Since $e=w_{1}\dots w_{k}$ and
$f(e)=xz_{1}\dots z_{k-1}$ are in different red tight components of $H$,
$P_{i}(e)$ contains a blue edge. Let $g_{i}(e)$ be the first blue edge on
$P_{i}(e)$. For each $e\in M_{3}$, we have either

  1. (1)

$g_{i}(e)\in B$ for all $i\in[k-1]$ or

  2. (2)

$g_{i^{*}}(e)\notin B$ for some $i^{*}\in[k-1]$.

Let $M_{4}\subseteq M_{3}$ with $|M_{4}|=k\delta n$ be such that every $e\in
M_{4}$ satisfies (1) or every $e\in M_{4}$ satisfies (2).

  1. Case A:

Every $e\in M_{4}$ satisfies (1). Let $e\in M_{4}$ and let
$F_{e}=\\{g_{i}(e)\colon i\in[k-1]\\}\subseteq B$ and note that
$\bigcap(\\{g(f(e))\\}\cup F_{e})=\varnothing$ since
$g_{i}(e)\cap\\{y(e),z_{i}(e)\\}=\varnothing$ for all $i\in[k-1]$. Let
$\varphi_{e}\colon B[e\cup f(e)\cup g(f(e))]\rightarrow[0,1]$ be the
$1/r$-fractional matching with $\varphi_{e}(h)=1/|F_{e}|$ for each
$h\in\\{g(f(e))\\}\cup F_{e}$ and $\varphi_{e}(h)=0$ otherwise. Note that
$\varphi_{e}$ has weight at least $1+1/(k-1)$. Let $\varphi_{0}$ be the
$1/r$-fractional matching induced by the matching
$M^{\prime}\setminus\\{g(f(e))\colon e\in M_{4}\\}$. Note that the completion
of $\varphi_{0}+\sum_{e\in M_{4}}\varphi_{e}$ with respect to $B$ is a
$1/r$-fractional matching in $B$ of weight at least $t+k\delta n/(k-1)\geq
t+\delta n$, so we are done.

  2. Case B:

Every $e\in M_{4}$ satisfies (2). Let $e\in M_{4}$ and let $i^{*}\in[k-1]$ be
such that $g_{i^{*}}(e)\notin B$. Let $P^{*}$ be the tight pseudo-walk
starting in $g(f(e))$ and then following $P_{i}(e)$ from $f(e)$ until
$g_{i^{*}}(e)$. Note that $V(P^{*})\subseteq e\cup f(e)\cup g(f(e))$ and all
edges of $P^{*}$ except its endpoints $g(f(e))$ and $g_{i^{*}}(e)$ are in $R$
(since they are all red by the definition of $g_{i^{*}}(e)$ and one of them is
$f(e)\in R$). Moreover, $g(f(e))$ and $g_{i^{*}}(e)$ are in different blue
tight components of $H$. For each $v\in f(e)$, construct a tight pseudo-walk
$P_{v}$ from $g_{i^{*}}(e)$ to $g(f(e))$ such that $V(P_{v})\subseteq
g(f(e))\cup g_{i^{*}}(e)$ and no edge of $P_{v}$ except $g(f(e))$ and
$g_{i^{*}}(e)$ contains $v$.999It is easy to see that $P_{v}$ exists. Let
$g(f(e))\cap g_{i^{*}}(e)=u_{1}\dots u_{s}$, $g_{i^{*}}(e)\setminus
g(f(e))=x_{1}\dots x_{k-s}$, and $g(f(e))\setminus g_{i^{*}}(e)=y_{1}\dots
y_{k-s}$. If $v=u_{j}$ for some $j\in[s]$, then we may take $P_{v}$ to be the
tight pseudo-walk induced by the vertex sequence $vx_{1}\dots
x_{k-s-1}u_{1}\dots u_{j-1}u_{j+1}\dots u_{s}y_{1}\dots y_{k-s-1}v$. And if
$v=x_{j}$ for some $j\in[k-s]$, then we may take $P_{v}$ to be the tight
pseudo-walk induced by the vertex sequence $vx_{1}\dots x_{j-1}x_{j+1}\dots
x_{k-s}u_{1}\dots u_{s}y_{1}\dots y_{k-s}$. Finally, if $v=y_{j}$ for some
$j\in[k-s]$, then we may take $P_{v}$ to be tight pseudo-walk induced by the
vertex sequence $x_{1}\dots x_{k-s}u_{1}\dots u_{s}y_{1}\dots
y_{j-1}y_{j+1}\dots y_{k-s}v$. By applying Lemma 3.1 to the closed tight
pseudo-walk obtained by the concatenation of $P^{*}$ and $P_{v}$, we deduce
that $P_{v}$ contains an edge $f_{v}\in R$. Let $F=\\{f_{v}\colon v\in
f(e)\\}$ and note that $\bigcap(F\cup\\{f(e)\\})=\varnothing$ since $v\notin
f_{v}$ for each $v\in f(e)$. Let $\varphi_{e}\colon R[e\cup f(e)\cup
g(f(e))]\rightarrow[0,1]$ be the $1/r$-fractional matching with
$\varphi_{e}(h)=1/|F|$ for each $h\in\\{f(e)\\}\cup F$ and $\varphi_{e}(h)=0$
otherwise. Note that $\varphi_{e}$ has weight at least $1+1/k$. Let
$\varphi_{0}$ be the $1/r$-fractional matching induced by the matching
$M\setminus\\{f(e)\colon e\in M_{4}\\}$. Now observe that the completion of
$\varphi_{0}+\sum_{e\in M_{4}}\varphi_{e}$ with respect to $R$ is a
$1/r$-fractional matching in $R$ of weight at least $t+|M_{4}|/k=t+\delta n$,
so we are done. ∎

###  5.3 Combining Lemma 5.1 and Lemma 5.2

Finally, we combine Lemma 5.1 and Lemma 5.2 to derive the following lemma
which states that any $(1-\varepsilon,\varepsilon)$-dense $2$-edge-coloured
$k$-graph on $n$ vertices contains the desired fractional matchings. This
lemma together with Corollary 6.2 (a hypergraph version of Łuczak’s connected
matching method) then implies Theorem 1.3 and Theorem 1.9.

######  Lemma 5.4.

Let $1/n\ll\varepsilon\ll\beta\ll\eta\ll 1/k$. Let $H$ be a
$(1-\varepsilon,\varepsilon)$-dense $2$-edge-coloured $k$-graph on $n$
vertices. Then there exist fractional matchings $\varphi_{1}$ and
$\varphi_{2}$ in $H$ and a red tight component $R$ and a blue tight component
$B$ of $H$ such that the following hold.

  1. (i)

$\varphi_{1}$ has weight at least $(1-3\eta)n/(k+1)$ and $\varphi_{2}$ has
weight at least $(1-3\eta)n/k$.

  2. (ii)

All edges of non-zero weight for both $\varphi_{1}$ and $\varphi_{2}$ have
weight at least $\beta$.

  3. (iii)

We have $\\{e\in H\colon\varphi_{1}(e)>0\\}\subseteq R$ or $\\{e\in
H\colon\varphi_{1}(e)>0\\}\subseteq B$.

  4. (iv)

We have $\\{e\in H\colon\varphi_{2}(e)>0\\}\subseteq R\cup B$.

###### Proof.

Let $r=k!$. Let $\gamma$ and $\delta$ be new constants with
$\beta\ll\gamma\ll\delta\ll\eta\ll 1/k$. Let $L$ be the largest integer such
that the $r^{L}$-blow-up $H_{*}$ of $H$ contains a matching $M_{*}$ contained
in a monochromatic tight component $T_{*}$ of $H_{*}$ with
$|M_{*}|\geq(\frac{1}{2k^{2}15^{k}}+L\gamma)|V(H_{*})|$. Note that trivially
$L\leq 1/(k\gamma)$. By Lemma 4.1, we have that $L\geq 0$.

If $L>\frac{1}{\gamma}(\frac{1-2\eta}{k}-\frac{1}{2k^{2}15^{k}})$, then
$|M_{*}|\geq\frac{(1-2\eta)}{k}|V(H_{*})|$. Let $\varphi_{*}$ the completion
with respect to $H_{*}$ of the fractional matching induced by $M_{*}$. By
Proposition 3.3 with $r^{L}$, $1$, $k$, $H$, $H_{*}$, $\\{T_{*}\\}$,
$\varphi_{*}$ playing the roles of $r$, $r^{\prime}$, $k$, $H$, $H_{*}$,
$\mathcal{C}_{*}$, $\varphi_{*}$ respectively, we get that $H$ contains a
$1/r^{L}$-fractional matching $\varphi$ with weight at least $(1-2\eta)n/k$
such that all its non-zero edges are contained in a single monochromatic tight
component of $H$. Since $L\leq 1/(k\gamma)$, we have

$\displaystyle 1/r^{L}\geq 1/r^{1/(k\gamma)}\geq\beta.$

Thus we are done since $\varphi$ satisfies the conditions for both
$\varphi_{1}$ and $\varphi_{2}$.

Hence we may assume that
$L\leq\frac{1}{\gamma}(\frac{1-2\eta}{k}-\frac{1}{2k^{2}15^{k}})$. Let $M_{*}$
be a matching in the $r^{L}$-blow-up $H_{*}$ of $H$ such that $M_{*}$ is
contained in the monochromatic tight component $T_{*}$ of $H_{*}$ and
$|M_{*}|=(\frac{1}{2k^{2}15^{k}}+L\gamma)|V(H_{*})|\leq(1-\eta)\frac{|V(H_{*})|}{k}$.
Assume without loss of generality that $T_{*}$ is a red tight component
$R_{*}$. Since $H$ is $(1-\varepsilon,\varepsilon)$-dense, by Proposition 3.4,
$H_{*}$ is $(1-2\varepsilon,2\varepsilon)$-dense. We apply Lemma 5.1, with
$|V(H_{*})|$, $2\varepsilon$, $\gamma$, $\eta$, $k$, $H_{*}$, $M_{*}$,
$R_{*}$, playing the roles of $n$, $\varepsilon$, $\gamma$, $\eta$, $k$, $H$,
$M$, $R$, respectively, to obtain that at least one of the following holds.

  1. (MB1)

There is a $1/r$-fractional matching in $R_{*}$ of weight at least
$|M_{*}|+\gamma|V(H_{*})|$.

  2. (MB2)

There is a matching $M^{\prime}$ in a blue tight component $B_{*}$ of $H_{*}$
with

$|M^{\prime}|\geq\min(|M_{*}|,|V(H_{*})|-|V(M_{*})|)-\sqrt{\gamma}|V(H_{*})|,$

such that each edge $e\in M^{\prime}$ intersects exactly one edge $f(e)\in
M_{*}$ and $|e\cap f(e)|=k-1$ and $H_{*}[e\cup f(e)]\cong K_{k+1}^{(k)}$.

Note that
$|M_{*}|+\gamma|V(H_{*})|=(\frac{1}{2k^{2}15^{k}}+(L+1)\gamma)|V(H_{*})|$. If
(MB1) holds, then by Proposition 3.3, we have that in the $r$-blow-up $H_{**}$
of $H_{*}$ there is a matching $M_{**}$ in a red tight component of $H_{**}$
with $|M_{**}|\geq(\frac{1}{2k^{2}15^{k}}+(L+1)\gamma)|V(H_{**})|$, a
contradiction to the maximality of $L$, since $H_{**}$ is an $r^{L+1}$-blow-up
of $H$. So (MB2) holds. We distinguish the following two cases.

  1. Case A:

$L\leq\frac{1}{\gamma}(\frac{1-2\eta}{k+1}-\frac{1}{2k^{2}15^{k}})$. In this
case, we have that

$\displaystyle|M_{*}|$
$\displaystyle=\left(\frac{1}{2k^{2}15^{k}}+L\gamma\right)|V(H_{*})|\leq(1-\eta)\frac{|V(H_{*})|}{k+1}\leq|V(H_{*})|-\frac{k}{k+1}|V(H_{*})|$
$\displaystyle\leq|V(H_{*})|-|V(M_{*})|.$

So

$\displaystyle|M^{\prime}|\geq\min(|M_{*}|,|V(H_{*})|-|V(M_{*})|)-\sqrt{\gamma}|V(H_{*})|=|M_{*}|-\sqrt{\gamma}|V(H_{*})|.$

By Lemma 5.2, we have that there exists a $1/r$-fractional matching in $R_{*}$
or $B_{*}$ of weight at least

$\displaystyle|M^{\prime}|+\delta|V(H_{*})|$
$\displaystyle\geq|M_{*}|-\sqrt{\gamma}|V(H_{*})|+\delta|V(H_{*})|\geq|M_{*}|+\gamma|V(H_{*})|$
$\displaystyle=\left(\frac{1}{2k^{2}15^{k}}+(L+1)\gamma\right)|V(H_{*})|$

By Proposition 3.3, we have that in the $r$-blow-up $H_{**}$ of $H_{*}$ there
is a matching $M_{**}$ in a monochromatic tight component of $H_{**}$ with

$\displaystyle|M_{**}|\geq\left(\frac{1}{2k^{2}15^{k}}+(L+1)\gamma\right)|V(H_{**})|,$

a contradiction to the maximality of $L$, since $H_{**}$ is an $r^{L+1}$-blow-
up of $H$.

  2. Case B:

$L>\frac{1}{\gamma}(\frac{1-2\eta}{k+1}-\frac{1}{2k^{2}15^{k}})$. Recall that
$L\leq\frac{1}{\gamma}(\frac{1-2\eta}{k}-\frac{1}{2k^{2}15^{k}})$. Hence, we
have that

$\displaystyle(1-2\eta)\frac{|V(H_{*})|}{k+1}\leq|M_{*}|\leq(1-\eta)\frac{|V(H_{*})|}{k}.$
(5.3)

By Proposition 3.3, we have that $\varphi_{1}$ exists. We now show that
$\varphi_{2}$ exists. We define a $1/r$-fractional matching
$\widetilde{\varphi}_{2}$ as follows. Let $M_{0}=\\{f(e)\colon e\in
M^{\prime}\\}$ and

$\displaystyle\widetilde{\varphi}_{2}(f)\coloneqq\begin{cases}1/k&\text{ if
$f\in H[e\cup f(e)]$ for some $e\in M^{\prime}$,}\\\ 1&\text{ if $f\in
M_{*}\setminus M_{0}$,}\\\ 0&\text{ otherwise}.\end{cases}$

Note that $M_{*}\setminus M_{0}\subseteq R_{*}$. Moreover, note that for each
$e\in M^{\prime}$, $e\cup f(e)$ is a set of size $k+1$ that contains the red
edge $f(e)\in R_{*}$ and the blue edge $e\in B_{*}$. Hence, for each $e\in
M^{\prime}$, $H[e\cup f(e)]\subseteq R_{*}\cup B_{*}$. Thus
$\widetilde{\varphi}_{2}$ gives non-zero weight only to edges in $R_{*}\cup
B_{*}$. By (MB2), for every $e\in M^{\prime}$, we have $H[e\cup f(e)]\cong
K_{k+1}^{(k)}$. It follows that $\widetilde{\varphi}_{2}$ has weight
$\frac{k+1}{k}|M^{\prime}|+|M_{*}|-|M_{0}|=|M_{*}|+|M^{\prime}|/k$. By 5.3, we
have

$\displaystyle\begin{split}|M_{*}|+|M^{\prime}|/k&\geq|M_{*}|+\frac{1}{k}\min(|M_{*}|,|V(H_{*})|-|V(M_{*})|)-\sqrt{\gamma}\frac{|V(H_{*})|}{k}\\\
&=\min\left(\frac{k+1}{k}|M_{*}|,|V(H_{*})|-(k-1)|M_{*}|\right)-\sqrt{\gamma}\frac{|V(H_{*})|}{k}\\\
&\geq\min\left((1-2\eta)\frac{|V(H_{*})|}{k},(1-\eta)\frac{|V(H_{*})|}{k}\right)-\sqrt{\gamma}\frac{|V(H_{*})|}{k}\\\
&\geq(1-3\eta)\frac{|V(H_{*})|}{k}.\end{split}$

Thus $\widetilde{\varphi}_{2}$ has weight $(1-3\eta)\frac{|V(H_{*})|}{k}$.
Hence by Proposition 3.3 with $r$, $k$, $k$, $H$, $H_{*}$,
$\\{R_{*},B_{*}\\}$, $\widetilde{\varphi}_{2}$ playing the roles of $r$,
$r^{\prime}$, $k$, $H$, $H_{*}$, $\mathcal{C}_{*}$, $\varphi_{*}$,
respectively, we have that $\varphi_{2}$ exists. ∎

##  6 Proof of the Main Theorems

Theorems 1.3 and 1.9 now follow straightforwardly from [11, Corollary 20] (a
hypergraph version of Łuczak’s connected matching method). To state this
result, we need the following definition.

######  Definition 6.1 ([11, Definition 19]).

Let $\mu_{k}^{1}(\beta,\varepsilon,n)$ be the largest $\mu$ such that every
$2$-edge-coloured $(1-\varepsilon,\varepsilon)$-dense $k$-graph on $n$
vertices contains a fractional matching with weight $\mu$ such that all edges
with non-zero weight have weight at least $\beta$ and lie in a single
monochromatic tight component. Let $\mu_{k}^{1}(\beta)=\liminf_{\varepsilon\to
0}\liminf_{n\to\infty}\mu_{k}^{1}(\beta,\varepsilon,n)/n$. Similarly, let
$\mu_{k}^{*}(\beta,\varepsilon,n)$ be the largest $\mu$ such that every
$2$-edge-coloured $(1-\varepsilon,\varepsilon)$-dense $k$-graph on $n$
vertices contains a fractional matching with weight $\mu$ such that all edges
with non-zero weight have weight at least $\beta$ and lie in one red and one
blue tight component. Let $\mu_{k}^{*}(\beta)=\liminf_{\varepsilon\to
0}\liminf_{n\to\infty}\mu_{k}^{*}(\beta,\varepsilon,n)/n$.

We now state the hypergraph version of Łuczak’s connected matching method that
we use.

######  Corollary 6.2 ([11, Corollary 20]).

Let $1/n\ll\eta,\beta,1/k$ with $k\geq 3$. Let $K$ be a $2$-edge-coloured
complete $k$-graph on $n$ vertices. Then the following hold.

  1. (i)

$K$ contains two vertex-disjoint monochromatic tight cycles of distinct
colours covering at least $(\mu_{k}^{*}(\beta)-\eta)kn$ vertices and

  2. (ii)

$K$ contains a monochromatic tight cycle of length $\ell$ for any
$\ell\leq(\mu_{k}^{1}(\beta)-\eta)kn$ divisible by $k$.

We are now ready to prove Theorems 1.3 and 1.9.

###### Proof of Theorem 1.3.

Let $1/n\ll\beta\ll\eta\ll\varepsilon,1/k<1$ with $k\geq 3$. Let $K$ be a
$2$-coloured complete $k$-graph on $N=(k+1+\varepsilon)n$ vertices. We show
that $K$ contains a monochromatic tight cycle of length $kn$. Note that by
Lemma 5.4, we have that $\mu_{k}^{1}(\beta)\geq(1-3\eta)/(k+1)$. By Corollary
6.2, we have that $K$ contains a monochromatic tight cycle of length $\ell$
for any $\ell\leq(\mu_{k}^{1}(\beta)-\eta)kN$ divisible by $k$. Since

$\displaystyle(\mu_{k}^{1}(\beta)-\eta)kN\geq(1/(k+1)-4\eta)(k+1+\varepsilon)kn\geq
kn,$

$K$ contains a monochromatic tight cycle of length $kn$, as desired. ∎

###### Proof of Theorem 1.9.

Let $1/n\ll\beta\ll\eta\ll\varepsilon,1/k<1$ with $k\geq 3$. Let $K$ be a
$2$-coloured complete $k$-graph on $n$ vertices. We show that $K$ contains a
red and a blue tight cycle that are vertex-disjoint and together cover at
least $(1-\varepsilon)n$ vertices. Note that by Lemma 5.4, we have that
$\mu_{k}^{*}(\beta)\geq(1-3\eta)/k$. By Corollary 6.2, we have that $K$
contains a red and a blue tight cycle that are vertex-disjoint and together
cover at least $(\mu_{k}^{*}(\beta)-\eta)kn$ vertices. Since

$\displaystyle(\mu_{k}^{*}(\beta)-\eta)kn\geq((1-3\eta)/k-\eta)kn\geq(1-\varepsilon)n,$

we are done. ∎

##  7 Concluding Remarks

In this paper, we have proved the $i=0$ case of 1.2. For the remaining cases,
it is no longer sufficient to just find a large enough (fractional) matching
in a monochromatic tight component of the reduced $k$-graph. Indeed, for these
cases, we need some way of adjusting the parity of the length of the tight
cycle we obtain in the original $k$-graph. The natural approach for doing this
is to find in the monochromatic tight component not just a large enough
(factional) matching, but also a gadget that allows one to change the parity
of the resulting tight cycle. Such a gadget could, for example, be a short
tight cycle of an appropriate length. Indeed, this approach was successfully
implemented for $3$-graphs in [8, 7]. Some of our ideas here may be useful to
proving the remaining cases of 1.2, however, a lot of our arguments revolve
around the fact that larger and larger matchings get us closer to our goal.
This is no longer the case if $i>0$, as for those cases, a large fractional
matching in a monochromatic tight component of the reduced $k$-graph is no
longer enough if we cannot also find a gadget to fix the parity.

We also proved an approximate Lehel’s conjecture for $k$-uniform tight cycles.
Indeed, we showed that, for $k\geq 3$, every $2$-edge-coloured complete
$k$-graph contains a red and a blue tight cycle that are vertex-disjoint and
together cover $n-o(n)$ vertices. Due to a counterexample (see [11,
Proposition 1]), we know that the $o(n)$-term cannot be replaced by $0$. In
[6], it was proved that in the case of $k=3$, the $o(n)$-term can be replaced
by a constant. We conjecture that it can also be replaced by a constant for
all $k\geq 4$.

######  Conjecture 7.1.

For every $k\geq 3$, there exist $c_{k}\geq 1$ and $n_{0}(k)\in\mathbb{N}$
such that for all $n\geq n_{0}(k)$ the following holds. Every $2$-edge-
coloured complete $k$-graph on $n$ vertices contains a red tight cycle and a
blue tight cycle that are vertex-disjoint and together cover at least
$n-c_{k}$ vertices.

We remark that it is possible that allowing the two tight cycles to possibly
have the same colour might allow us to cover more vertices (as has been shown
to be the case for $k=3$ in [6]).

## Acknowledgements

The author thanks Alexandru Malekshahian for helpful discussions. This project
has received partial funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant
agreement no. 786198) and was also supported in part by the Austrian Science
Fund (FWF) [10.55776/I6502].

For the purpose of open access, the author has applied a CC BY public
copyright licence to any Author Accepted Manuscript version arising from this
submission.

## References

  * [1] P. Allen.  Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles.  Combin. Probab. Comput., 17(4):471–486, 2008.
  * [2] S. Bessy and S. Thomassé.  Partitioning a graph into a cycle and an anticycle, a proof of lehel’s conjecture.  J. Combin. Theory Ser. B, 100(2):176–180, 2010.
  * [3] J. A. Bondy and P. Erdős.  Ramsey numbers for cycles in graphs.  J. Combin. Theory Ser. B, 14:46–54, 1973.
  * [4] S. Bustamante, H. Hàn, and M. Stein.  Almost partitioning 2-colored complete 3-uniform hypergraphs into two monochromatic tight or loose cycles.  J. Graph Theory, 91(1):5–15, 2019.
  * [5] R. J. Faudree and R. H. Schelp.  All Ramsey numbers for cycles in graphs.  Discrete Math., 8:313–329, 1974.
  * [6] F. Garbe, R. Mycroft, R. Lang, A. Lo, and N. Sanhueza-Matamala.  Partitioning $2$-coloured complete $3$-uniform hypergraphs into two monochromatic tight cycles.  In preparation.
  * [7] P. E. Haxell, T. Łuczak, Y. Peng, V. Rödl, A. Ruciński, and J. Skokan.  The Ramsey number for hypergraph cycles II.  CDAM Research Report, LSE-CDAM-2007-04, 2007.
  * [8] P. E. Haxell, T. Łuczak, Y. Peng, V. Rödl, A. Ruciński, and J. Skokan.  The Ramsey number for 3-uniform tight hypergraph cycles.  Combin. Probab. Comput., 18(1-2):165–203, 2009.
  * [9] A. Lo and V. Pfenninger.  The Ramsey number for 4-uniform tight cycles.  arXiv e-prints, arXiv:2111.05276, 2021.
  * [10] A. Lo and V. Pfenninger.  Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles.  arXiv e-prints, arXiv:2309.04218, 2023.
  * [11] A. Lo and V. Pfenninger.  Towards Lehel’s conjecture for 4-uniform tight cycles.  Electron. J. Combin., 30(1):Paper No. 1.13, 36, 2023.
  * [12] L. Lovász.  Combinatorial Problems and Exercises.  North Holland Publishing Co., 1979.
  * [13] T. Łuczak.  ${R(C_{n},C_{n},C_{n})}\leq(4+o(1))n$.  J. Combin. Theory Ser. B, 75(2):174 – 187, 1999.
  * [14] T. Łuczak, V. Rödl, and E. Szemerédi.  Partitioning two-coloured complete graphs into two monochromatic cycles.  Combin. Probab. Comput., 7(4):423–436, 1998.
  * [15] V. Rosta.  On a Ramsey-type problem of J. A. Bondy and P. Erdős. I, II.  J. Combin. Theory Ser. B, 15:94–104; ibid. 15 (1973), 105–120, 1973.
  * [16] M. Shahsiah.  Ramsey numbers of 5-uniform loose cycles.  Graphs Combin., 38(1):Paper No. 5, 23, 2022.