lemthm lem skolemthm skolem factthm fact sublemthm sublem claimthm claim
subclaimthm subclaim obsthm obs propthm prop corthm cor quethm que oquethm
oque conthm con dfnthm dfn remthm rem egthm eg exercisethm exercise

# Shallow Hitting Edge Sets in Uniform Hypergraphs††thanks: The results
presented here are based on the Master’s thesis of the first author [22].

Tim Planken  University of Birmingham
<EMAIL_ADDRESS>Torsten Ueckerdt  Karlsruhe Institute of Technology
<EMAIL_ADDRESS>
###### Abstract

A subset $M$ of the edges of a graph or hypergraph is _hitting_ if $M$ covers
each vertex of $H$ at least once, and $M$ is _$t$ -shallow_ if it covers each
vertex of $H$ at most $t$ times. We consider the existence of shallow hitting
edge sets and the maximum size of shallow edge sets in $r$-uniform hypergraph
$H$ that are regular or have a large minimum degree. Specifically, we show the
following.

  * •

Every $r$-uniform regular hypergraph has a $t$-shallow hitting edge set with
$t=O(r)$.

  * •

Every $r$-uniform regular hypergraph with $n$ vertices has a $t$-shallow edge
set of size $\Omega(nt/r^{1+1/t})$.

  * •

Every $r$-uniform hypergraph with $n$ vertices and minimum degree
$\delta_{r-1}(H)\geq n/((r-1)t+1)$ has a $t$-shallow hitting edge set.

  * •

Every $r$-uniform $r$-partite hypergraph with $n$ vertices in each part and
minimum degree $\delta^{\prime}_{r-1}(H)\geq n/((r-1)t+1)+1$ has a $t$-shallow
hitting edge set.

We complement our results with constructions of $r$-uniform hypergraphs that
show that most of our obtained bounds are best-possible.

##  1 Introduction

Two of the most fundamental results in graph theory are the necessary and
sufficient conditions for the existence of perfect matchings in bipartite
graphs due to Hall’s “marriage theorem” [11] and in general graphs due to
Tutte’s “odd component count” [27]. However, the situation is less understood
and also more complicated in hypergraphs. For example, while we know how to
detect perfect matchings in graphs in polynomial time [9, 21] and in bipartite
graphs even in near-linear time [5], the problem is NP-complete already in
$3$-uniform $3$-partite hypergraphs [15], indicating that there is (in all
likelihood) no nice necessary and sufficient criterium for perfect matchings
in hypergraphs.

A simple application of Hall’s marriage theorem shows that every regular (all
vertices have the same degree) bipartite graph admits a perfect matching.
However, this does not hold for hypergraphs, as for example illustrated by the
$2$-regular hypergraph in Figure 1 which admits no perfect matching. For some
integer $r\geq 2$, a hypergraph $H=(V,E)$ is $r$-uniform if every edge $e\in
E$ consists of exactly $r$ vertices. That is, $2$-uniform hypergraphs are just
graphs, while the hypergraph in Figure 1 is $3$-uniform. Moreover, $H=(V,E)$
is $r$-partite if its vertices can be partitioned into $r$ parts such that
each edge contains exactly one vertex of each part. That is, $2$-uniform
$2$-partite hypergraphs are exactly the bipartite graphs, while the hypergraph
in Figure 1 is $3$-partite with the a $3$-partition indicated by the shapes of
the vertices. Evidently, as soon as $r\geq 3$, not all regular $r$-uniform
$r$-partite hypergraphs admit perfect matchings.

Figure 1: A $2$-regular $3$-uniform $3$-partite hypergraph with no perfect
matching.

We are concerned with a relaxation of perfect matchings, called shallow
hitting edge sets. While $M$ is a perfect matching if every vertex has exactly
one incident edge in $M$, an edge subset $M$ is a _$t$ -shallow hitting edge
set_ for a positive integer $t$ if every vertex has at least one incident edge
in $M$ (this is the “hitting” part) and at most $t$ incident edges in $M$
(this is the “$t$-shallow” part). For example, any set of three or four edges
in the hypergraph $H$ in Figure 1 is a $2$-shallow hitting edge set of $H$. In
this paper, we shall present sufficient conditions for $t$ and $r$ for which
every regular $r$-uniform hypergraph admits a $t$-shallow hitting edge set.

Of course, if a graph or hypergraph admits no perfect matching, it is
interesting to prove lower bounds on the size of its largest matchings, for
example for regular graphs [13]. In this paper, we shall present for regular
$n$-vertex $r$-uniform hypergraphs $H$ lower bounds for the size of their
maximum $t$-shallow edge sets in terms of $n$, $r$ and $t$.

Another simple application of Hall’s marriage theorem shows that every
bipartite graph with $n$ vertices in each part and minimum degree at least
$n/2$ admits a perfect matching. Rödl, Ruciński and Szemerédi [25], see also
Kühn and Osthus [19], extend this by showing that every $n$-vertex $r$-uniform
hypergraph $H$ with large enough $\delta_{r-1}(H)$ in terms of $n$ and $r$
(see Section 4 for the definition) admits a perfect matching. Similarly, every
$r$-uniform $r$-partite hypergraph with parts of size $n$ and large enough
$\delta^{\prime}_{r-1}(H)$ in terms of $n$ and $r$ admits a perfect matching
[19, 1]. In this paper, we extend these results to $t$-shallow hitting edge
sets.

###  1.1 Our results and organization of the paper

All hypergraphs considered in this paper are uniform and finite, but may have
parallel edges. We give the formal definitions of terms such as $r$-uniform,
$r$-partite, girth, near-regular, $t$-shallow edge sets, hitting edge sets,
etc. in Section 1.3.

In Section 2 we investigate the existence of shallow hitting edge sets in
regular uniform hypergraphs. We seek to prove that every $r$-uniform regular
hypergraph admits a $t$-shallow hitting edge set with $t$ being as small as
possible with respect to $r$. On the positive side, Theorem 2.1 in Section 2.1
gives that every $r$-uniform regular hypergraph has a $t$-shallow hitting edge
set with $t=O(r)$. In Theorem 2.2 in Section 2.2 we improve the upper bound on
$t$ to $t=O(\ln r)$ for the special case of $r$-uniform regular hypergraphs
whose girth is at least four. We complement this with lower bounds in Section
2.3. We present in Theorem 2.4 a construction of an $r$-uniform regular
hypergraph that admits $t$-shallow hitting edge sets only for $t=\Omega(\log
r)$.

In fact, we prove our upper bounds in Sections 2.1 and 2.2 for the more
general case of $r$-uniform near-regular hypergraphs. In a near-regular
hypergraph we only require that the quotient $\Delta/\delta$ of the maximum
degree over the minimum degree is bounded by some constant $\mu=O(1)$. On the
other hand, the lower bounds in Section 2.3 are provided in the more
restricted case of $r$-uniform regular hypergraphs, and which are additionally
restricted to be $r$-partite.

In Section 3 we investigate the maximum size of shallow edge sets in regular
uniform hypergraphs. Again, we consider $r$-uniform regular hypergraphs
$H=(V,E)$. But here we seek to find $t$-shallow edge sets $M\subseteq E$ that
are not necessarily hitting. Of course, $M=\emptyset$ is always a valid
choice, while the challenge here is to have $|M|$ as large as possible in
terms of $t$, $r$ and $n=|V|$. On the positive side, Theorem 3.1 in Section
3.1 gives that every $r$-uniform regular hypergraph with $n$ vertices admits a
$t$-shallow edge set $M$ of size

$|M|=\Omega\left(\frac{nt}{r^{1+1/t}}\right).$

We complement this with an asymptotically matching upper bound in Section 3.2.
We present in Theorem 3.4 a construction of $r$-uniform regular hypergraphs
with $n$ vertices that admit $t$-shallow edge sets $M$ only of size

$|M|=O\left(\frac{nt}{r^{1+1/t}}\right).$

In fact, we again prove our lower bound in Section 3.1 for the more general
case of near-regular hypergraphs, while our upper bound in Section 3.2 is
provided in the more restricted case of regular $r$-uniform $r$-partite
hypergraphs.

In Section 4 we investigate the existence of shallow hitting edge sets in
uniform hypergraphs of large minimum degree. The famous theorem of Dirac [8]
states that every graph on $n$ vertices with minimum degree at least $n/2$
contains a Hamiltonian cycle, while some graphs with minimum degree less than
$n/2$ do not. We consider the Dirac-type problem of finding a minimum degree
condition for uniform hypergraphs to contain a shallow hitting edge set. We
focus on two of the several possibilities to define the minimum degree of
$r$-uniform hypergraphs with $r>2$.

In Section 4.1 we consider $r$-uniform hypergraphs $H$ and define
$\delta_{r-1}(H)$ to be the smallest integer $d$ such that every $(r-1)$-set
of vertices of $H$ forms an edge with $d$ distinct vertices in $H$. We prove
in Theorem 4.3 that every $r$-uniform hypergraph $H$ with $n=|V|$ vertices has
a $t$-shallow hitting edge set, $t\geq 2$, provided

$\delta_{r-1}(H)\geq\frac{n}{(r-1)t+1}.$

We complement this with a construction in Theorem 4.2 of $r$-uniform
hypergraphs with $n$ vertices and

$\delta_{r-1}(H)\geq\frac{n}{(r-1)t+1}-1$

that have no $t$-shallow hitting edge sets.

In Section 4.2 we consider $r$-uniform $r$-partite hypergraphs $H$ and define
$\delta^{\prime}_{r-1}(H)$ to be the smallest integer $d$ such that every
$(r-1)$-set of vertices from pairwise distinct parts of $H$ forms an edge with
$d$ distinct vertices of the remaining part in $H$. We prove in Theorem 4.9
that every $r$-uniform $r$-partite hypergraph with parts of size $n$ has a
$t$-shallow hitting edge set, $t\geq 2$, provided

$\delta^{\prime}_{r-1}(H)\geq\frac{n}{(r-1)t+1}+1.$

We complement this with a construction in Theorem 4.7 of $r$-uniform
$r$-partite hypergraphs with parts of size $n$ and

$\delta^{\prime}_{r-1}(H)\geq\frac{n}{(r-1)t+1}-1$

that have no $t$-shallow hitting edge sets.

We end this paper with a brief discussion in Section 5.

###  1.2 Related work

Let us just briefly mention some further related work on matchings in
hypergraphs. Until now, there is no generalization of Hall’s Theorem or
Tutte’s Theorem to hypergraphs. There is an equivalence for the existence of
perfect matchings in so-called balanced hypergraphs, see [7] and [14]. On the
other hand, there are two ways to extend the sufficient condition of Hall’s
Theorem to uniform bipartite hypergraphs (here, a hypergraph $H=(V,E)$ is
bipartite if there exists a partition $V=A\dot{\cup}B$ such that every edge
has exactly one vertex in $A$). Haxell [12] gave a sufficient condition in
terms of minimum vertex covers while Aharoni and Haxell [2] gave a sufficient
condition in terms of maximum matchings. Both theorems are equivalent to
Hall’s Theorem in the case of bipartite graphs, but do not give a necessary
condition in general.

The concept of $t$-shallow hitting edge sets has been considered for graphs
implicitly under several names. Specifically, there is a lot of research on
subgraphs $G^{\prime}$ of a given graph $G$ such that for each vertex $v$ its
number of incident edges in $G^{\prime}$ lies in some predefined set $S_{v}$,
as introduced by Lovász [20]. (It would be $S_{v}=\\{1,\ldots,t\\}$ for
$t$-shallow hitting edge sets.) Let us just mention that Berge and Las Vergnas
[4] give a Hall-type characterization for the case of bipartite graphs, as
well as a Tutte-type characterization for general graphs.

Finally, hitting edge sets of a hypergraph $H$ are equivalent to “hitting
vertex sets” of the dual hypergraph $H^{*}$ of $H$. Such hitting vertex sets
are also known as vertex covers, transversals, or hitting sets in the
literature. Shallow hitting (vertex) sets are for example a standard tool for
coloring geometric hypergraphs [17].

###  1.3 Preliminaries

A hypergraph is a tuple $H=(V,E)$ consisting of a finite set $V$ of vertices
and a finite multiset $E$ of edges111Sometimes $e$ is called a _hyper_ edge if
$|e|\geq 3$, but let us call $e$ simply an _edge_ , independent of its size
$|e|$., where each edge $e\in E$ is a subset of $V$. For a vertex $v\in V$, we
denote the set of edges incident to $v$ in $H$ by $\operatorname{Inc}(v)$. For
$M\subseteq E$ and $v\in V$, the _degree $\operatorname{deg}_{M}(v)$ of $v$ in
$M$_ is the number of incident edges at $v$ that are in $M$, i.e.,
$\operatorname{deg}_{M}(v)=|\operatorname{Inc}(v)\cap M|$. The _degree
$\operatorname{deg}(v)$ of $v$_ is
$\operatorname{deg}(v)=\operatorname{deg}_{E}(v)=|\operatorname{Inc}(v)|$.

The maximum (respectively minimum) degree of $H$ is the largest (respectively
smallest) degree of a vertex in $H$. A hypergraph $H$ with maximum degree
$\Delta$ and minimum degree $\delta$ is _regular_ if $\Delta=\delta$, and
_$\mu$ -near-regular_ for a real number $\mu\in{\mathbb{R}}_{\geq 0}$ if
$\delta>0$ and $\Delta/\delta\leq\mu$. Thus, a hypergraph is $1$-near-regular
if and only if it is regular and has minimum degree at least $1$. Of course,
every hypergraph with minimum degree $\delta>0$ is $\mu$-near-regular for
every large enough $\mu$. When we later consider “near-regular hypergraphs”,
this refers to the class of all $\mu$-near-regular hypergraphs for some fixed
$\mu\in{\mathbb{R}}_{\geq 0}$.

For an integer $r\geq 1$, a hypergraph $H=(V,E)$ is _$r$ -uniform_ if we have
$|e|=r$ for each $e\in E$. That is, $2$-uniform hypergraphs are graphs (with
no loops but possibly parallel edges). In the literature, $r$-uniform
hypergraphs are sometimes simply called _$r$ -graphs_.

A hypergraph $H$ is called _$r$ -partite_ if there exists a partition
$V_{1},\ldots,V_{r}$ of $V$ into $r$ pairwise disjoint parts such that for
each $e\in E$ and $i\in\\{1,\ldots,r\\}$ we have $|e\cap V_{i}|\leq 1$.
Whenever we consider an $r$-partite hypergraph $H=(V,E)$, we fix one such
partition $V=V_{1}\dot{\cup}\cdots\dot{\cup}V_{r}$ and call each $V_{i}$,
$i=1,\ldots,r$, a _part_ of $H$. The smallest $r$ for which $H$ is $r$-partite
is the _chromatic number_ of $H$, but we shall not use this notion here.
Arguably, $r$-uniform $r$-partite hypergraphs are the most natural
generalization of bipartite graphs to larger uniformity.

We say that $H^{*}=(V^{*},E^{*})$ is the _dual hypergraph_ of $H$ if $V^{*}=E$
is the set of vertices and $E^{*}=\\{\operatorname{Inc}(v)\mid v\in V\\}$ is
the set of edges.

Let $H=(V,E)$ be a hypergraph. For an edge set $M\subseteq E$, a vertex $v\in
V$ is said to be _covered by $M$_ if $\operatorname{deg}_{M}(v)\geq 1$. An
edge set $M\subseteq E$ is _hitting_ if every vertex in $H$ is covered by $M$.
For an integer $t\geq 0$, an edge set $M\subseteq E$ is _$t$ -shallow_ if
$\operatorname{deg}_{M}(v)\leq t$ for each vertex $v$.

Finally, recall that $o_{r}(1)$ denotes the class of all functions
$f\colon{\mathbb{R}}_{\geq 0}\to{\mathbb{R}}_{\geq 0}$ for which $f(r)\to 0$
as $r\to\infty$. At several places in this paper we seek to describe the
asymptotic behavior of a function in terms of _two_ parameters: $r$ and $\mu$.
To this end, let $o_{\mu r}(1)$ be the class of all functions
$f\colon{\mathbb{R}}_{\geq 0}^{2}\to{\mathbb{R}}_{\geq 0}$ for which
$f(\mu,r)\to 0$ whenever $\mu r\to\infty$.

##  2 Shallow Hitting Edge Sets in Uniform Near-Regular Hypergraphs

###  2.1 Upper bound for the general case

Let $A_{1},\dots,A_{n}$ be events. A graph $G=(V,E)$ is a _dependency graph_
of these events if $V=\\{A_{1},\dots,A_{n}\\}$ and the following holds for all
$i$. For each event $A_{i}$ and each set $S$ of non-adjacent events with
$A_{i}\notin S$ it holds that
$\operatorname{Pr}\left[A_{i}\mid\bigwedge_{A_{j}\in
S}\overline{A}_{j}\right]\leq\operatorname{Pr}[A_{i}]$. The _degree of
dependence_ of the events $A_{1},\dots,A_{n}$ is the smallest possible maximum
degree of a dependency graph. If each “bad” event $A_{i}$ only occurs with
small probability and each bad event is dependent of a small amount of other
bad events, the Lovász Local Lemma is a tool to prove that it is possible that
no bad event occurs.

######  Lemma  (Lovász Local Lemma [26]).

Let $A_{1},\dots,A_{n}$ be events with $\operatorname{Pr}[A_{i}]\leq p$ and
let $d$ be their degree of dependence. If $\mathrm{e}p(d+1)\leq 1$, then
$\operatorname{Pr}[\overline{A}_{1}\overline{A}_{2}\cdots\overline{A}_{n}]>0$.

######  Remark .

In the original Lovász Local Lemma, the notion of a dependency graph is
replaced by a slightly stronger definition in which each event $A_{i}$ must be
mutually independent of all non-adjacent events $A_{j}$ with $i\neq j$. It can
be seen by the proof in [3] that the Lovász Local Lemma remains true if we use
the weaker notion of a dependency graph as defined above. In Lemma 2.1, we
will use the original version of the Lovász Local Lemma (which is included as
a special case in Lemma 2.1). In Lemma 2.2, we need the weaker notion of a
dependency graph and therefore the slightly stronger Lovász Local Lemma as in
Lemma 2.1.

In the next lemma, we want to find shallow hitting edge sets in uniform near-
regular hypergraphs. For this, we use a random experiment that generates a
hitting edge set $M$. Then, we only need to ensure the condition that $M$ is
also shallow which will be done using the Lovász Local Lemma.

######  Lemma .

Let $H=(V,E)$ be an $r$-uniform $\mu$-near-regular hypergraph and let $t$ be a
positive integer satisfying

$\frac{t!}{t+1}\geq\mathrm{e}\mu^{t+1}r^{t+3}~{}.$ (1)

Then, $H$ has a $t$-shallow hitting edge set.

###### Proof.

Let $\Delta$ be the maximum degree and $\delta$ be the minimum degree of $H$.
We build an edge set $M\subseteq E$ with the following random experiment. For
each vertex $v\in V$, we pick an incident edge $e\in\operatorname{Inc}(v)$
uniformly at random and add it to the edge set $M$. Clearly, $M$ is a hitting
edge set. Observe that for $t\geq\Delta$, $M$ is clearly $t$-shallow. Thereby,
assume that $t<\Delta$. We use the Lovász Local Lemma to prove that there
exists an edge set $M$ that also satisfies $\operatorname{deg}_{M}(v)\leq t$
for all vertices $v\in V$. For a set $F$ of edges, denote by $V(F)$ the set of
vertices $\bigcup_{e\in F}\,e$.

Define the set $\mathcal{F}$ to be the set of all edge sets $F\subseteq E$ of
size $t+1$ such that there exists a vertex $v\in V$ with
$F\subseteq\operatorname{Inc}(v)$, i.e.,

$\mathcal{F}=\\{F\subseteq
E\colon|F|=t+1,F\subseteq\operatorname{Inc}(v)\text{ for some }v\in V\\}~{}.$

For a set $F\in\mathcal{F}$, we denote the event that $F\subseteq M$ by
$A_{F}$. These are the bad events used in the Lovász Local Lemma.

To apply the Lovász Local Lemma, we have to find a bound $p$ such that
$\operatorname{Pr}[A_{F}]\leq p$ holds for all $F\in\mathcal{F}$. For a vertex
$v\in V$, we denote by $P_{v}$ the random variable with range
$\operatorname{Inc}(v)$ that describes which edge is picked at the vertex $v$.
Moreover, for $e\in E$ and $v\in e$, we define $B_{e,v}$ to be the event that
$P_{v}=e$ and $B_{e}$ to be the event that $e\in M$. Since every vertex has
degree at least $\delta$, it holds that
$\operatorname{Pr}[B_{e,v}]=\operatorname{Pr}[P_{v}=e]\leq 1/\delta$ for all
$e\in E$ and $v\in e$. For an edge $e\in E$, we can now bound the probability
for the event $B_{e}$ by

$\operatorname{Pr}[B_{e}]=\operatorname{Pr}\left[\bigvee_{v\in
e}B_{e,v}\right]\leq\sum_{v\in
e}\operatorname{Pr}[B_{e,v}]\leq\frac{r}{\delta}~{}.$

For $e\in E$ and $F\subseteq E$ with $e\notin F$, it holds that
$\operatorname{Pr}[B_{e}\mid\cap_{e^{\prime}\in
F}B_{e^{\prime}}]\leq\operatorname{Pr}[B_{e}]$ and hence
$\operatorname{Pr}[B_{e}\cap\left(\cap_{e^{\prime}\in
F}B_{e^{\prime}}\right)]\leq\operatorname{Pr}[B_{e}]\cdot\operatorname{Pr}[\cap_{e^{\prime}\in
F}B_{e^{\prime}}]$. Thus, for each $F\in\mathcal{F}$, the probability that the
event $A_{F}$ occurs can be bounded by

$\operatorname{Pr}[A_{F}]=\operatorname{Pr}\left[\bigwedge_{e\in
F}B_{e}\right]\leq\prod_{e\in
F}\operatorname{Pr}[B_{e}]\leq\left(\frac{r}{\delta}\right)^{t+1}~{}.$

We construct a dependency graph $G_{\text{D}}=(V_{\text{D}},E_{\text{D}})$
with $V_{\text{D}}=\\{A_{F}\mid F\in\mathcal{F}\\}$. Two events $A_{F}$ and
$A_{F^{\prime}}$ are adjacent in $G_{\text{D}}$ if and only if $V(F)\cap
V(F^{\prime})\neq\emptyset$. Note that the event $B_{e}$ is mutually
independent of all events $B_{e^{\prime}}$ with $e\cap e^{\prime}=\emptyset$.
Thus, each event $A_{F}$ for $F\in\mathcal{F}$ is mutually independent of all
non-adjacent events $A_{F^{\prime}}$.

In the next step, we have to bound the degree of dependence of these events.
For an edge $e\in E$ and a vertex $v\in e$, denote by
$\mathcal{F}_{e,v}\subseteq\mathcal{F}$ the set of edge sets $F\in\mathcal{F}$
with $e\in F$ and $F\subseteq\operatorname{Inc}(v)$. We bound the size of the
sets $\mathcal{F}_{e,v}$. The edge $e$ is contained in all sets
$F\in\mathcal{F}_{e,v}$ and the vertex $v$ has degree at most $\Delta$. Since
every edge set $F\in\mathcal{F}$ has size exactly $t+1$, there are at most
$\binom{\Delta-1}{t}$ ways to choose the remaining $t$ edges (which must be
incident with $v$). Thus,

$|\mathcal{F}_{e,v}|\leq\binom{\Delta-1}{t}\quad\text{for all }e\in E\text{
and }v\in e~{}.$

Let $F\in\mathcal{F}$ be an arbitrary but fixed set of edges. In order to
bound the degree of dependence, we count the number of edge sets
$F^{\prime}\in\mathcal{F}$ with $V(F)\cap V(F^{\prime})\neq\emptyset$. Let
$F^{\prime}\in\mathcal{F}$ be an arbitrary edge set with $A_{F^{\prime}}$
adjacent to $A_{F}$ in the dependency graph $G_{\text{D}}$. Since $V(F)\cap
V(F^{\prime})\neq\emptyset$, there must exist a vertex $\tilde{v}$ in
$V(F)\cap V(F^{\prime})$ with an edge $e^{\prime}$ in $F^{\prime}$ which is
incident to $\tilde{v}$. By definition of $\mathcal{F}$, there is a vertex
$v^{\prime}\in V$ with $F\subseteq\operatorname{Inc}(v^{\prime})$. As
$e^{\prime}\in F^{\prime}$, this vertex must be incident to $e^{\prime}$,
i.e., $v^{\prime}\in e^{\prime}$. Thus, $F^{\prime}$ is in the set
$\mathcal{F}_{e^{\prime},v^{\prime}}$. Since the set $F$ itself fulfills all
the described properties, it is also in a set $\mathcal{F}_{e,v}$ and we count
it too. We can now bound the degree of dependence $d$ by

$d+1\leq\max_{F\in\mathcal{F}}\left|\bigcup\limits_{\tilde{v}\in
V(F)}\bigcup\limits_{e^{\prime}\in\operatorname{Inc}(\tilde{v})}\bigcup\limits_{v^{\prime}\in
e^{\prime}}\mathcal{F}_{e^{\prime},v^{\prime}}\right|\leq(t+1)r\cdot\Delta\cdot
r\cdot\binom{\Delta-1}{t}~{}.$

Since we assumed $\Delta-1\geq t$, it holds that

$\binom{\Delta-1}{t}\leq\frac{(\Delta-1)^{t}}{t!}\leq\frac{\Delta^{t}}{t!}$

and thus

$d+1\leq\frac{t+1}{t!}r^{2}\Delta^{t+1}~{}.$ (2)

To apply the Lovász Local Lemma, we calculate $\mathrm{e}p(d+1)$. With
Equation (1), it follows that

$\mathrm{e}p(d+1)\leq\mathrm{e}\cdot\left(\frac{r}{\delta}\right)^{t+1}\cdot\frac{t+1}{t!}r^{2}\Delta^{t+1}\leq\mathrm{e}\frac{t+1}{t!}\mu^{t+1}r^{t+3}\leq
1~{}.$

By the Lovász Local Lemma, the probability that no event $A_{F}$ with
$F\in\mathcal{F}$ occurs is greater than zero. Thus, there exists an edge set
$M\subseteq E$ such that every vertex has degree
$1\leq\operatorname{deg}_{M}(v)\leq t$ in $M$. ∎

######  Theorem 2.1.

Every $r$-uniform $\mu$-near-regular hypergraph has a $t(\mu,r)$-shallow
hitting edge set, where $t(\mu,r)=\mathrm{e}\mu r(1+o_{\mu r}(1))$.

###### Proof.

We show that

$t=1+\left\lceil\mathrm{e}\mu
r\left(\mathrm{e}^{2}\mu^{2}r^{4}\right)^{1/(\mathrm{e}\mu
r)}\right\rceil=\mathrm{e}\mu r(1+o_{\mu r}(1))$

satisfies Equation (1). Indeed, with Stirling’s Formula $t!\geq\sqrt{2\pi
t}(t/\mathrm{e})^{t}$ and with $(t+1)/\sqrt{2\pi t}\leq t$ for $t\geq 1$ it
follows that

$\begin{split}\mathrm{e}\frac{t+1}{t!}\mu^{t+1}r^{t+3}&\leq\mathrm{e}\frac{t+1}{\sqrt{2\pi
t}}\mu r^{3}\cdot\left(\frac{\mathrm{e}\mu
r}{t}\right)^{t}\leq\mathrm{e}^{2}\mu^{2}r^{4}\left(\frac{\mathrm{e}\mu
r}{t-1}\right)^{t-1}\\\
&\leq\mathrm{e}^{2}\mu^{2}r^{4}\left(\mathrm{e}^{2}\mu^{2}r^{4}\right)^{-(\mathrm{e}^{2}\mu^{2}r^{4})^{1/(\mathrm{e}\mu
r)}}\leq 1~{}.\end{split}$

∎

###  2.2 Upper bound for girth at least four

In the next theorem, we show a better bound for uniform near-regular
hypergraphs without small cycles. Let $H=(V,E)$ be a hypergraph. A _cycle of
length $k$_ is a sequence $v_{1}e_{1}v_{2}e_{2}\dots v_{k}e_{k}v_{k+1}$ of
distinct vertices $v_{1},v_{2},\dots,v_{k}$ and distinct edges
$e_{1},e_{2},\dots,e_{k}$ such that $v_{1}=v_{k+1}$ and
$\\{v_{i},v_{i+1}\\}\subseteq e_{i}$ for $i=1,2,\dots,k$. The _girth_ of a
hypergraph $H$ is the smallest possible length of a cycle in $H$. In Lemma 2.2
and Theorem 2.2, we prove a better bound for uniform regular hypergraphs of
girth at least $4$.

For that, we need the following lemma. It says that if we have two events $A$
and $B$ that are independent by conditioning on the set
$\\{\tilde{C}_{1},\dots,\tilde{C}_{n}\\}$ of events for all
$\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}$, $i=1,\dots,n$, and each event
$C_{i}$ decreases the probability that $A$ occurs but raises the probability
that $B$ occurs, then $\operatorname{Pr}[A\mid B]\leq\operatorname{Pr}[A]$.
Moreover, we use the abbreviation

$\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,k\end{subarray}}f(\tilde{C}_{1},\dots,\tilde{C}_{k})=\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,k-1\end{subarray}}\;\sum_{\tilde{C}_{k}\in\\{C_{k},\overline{C}_{k}\\}}f(\tilde{C}_{1},\dots,\tilde{C}_{k})$

for $k\geq 1$ and with

$\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i\in\emptyset\end{subarray}}a=a~{}.$

######  Lemma .

Let $A$, $B$ and $C_{1},\dots,C_{n}$ be events such that the following holds
for all events $\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}$, $i=1,\dots,n$,

  1. 1.

$\operatorname{Pr}\left[A\mid
B,\bigwedge_{i=1}^{n}\tilde{C}_{i}\right]=\operatorname{Pr}\left[A\mid\bigwedge_{i=1}^{n}\tilde{C}_{i}\right]$,

  2. 2.

$\operatorname{Pr}\left[A\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\leq\operatorname{Pr}\left[A\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
for all $0\leq k<n$,

  3. 3.

$\operatorname{Pr}\left[B\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\geq\operatorname{Pr}\left[B\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
for all $0\leq k<n$.

Then, $\operatorname{Pr}[A\mid B]\leq\operatorname{Pr}[A]$.

###### Proof.

We show that the inequality

$\operatorname{Pr}\left[A\mid
B\right]\leq\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,k\end{subarray}}\operatorname{Pr}\left[\bigwedge_{i=1}^{k}\tilde{C}_{i}\mid
B\right]\operatorname{Pr}\left[A\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
(3)

holds for all $k=0,1,\dots,n$ by induction on $n-k$. Clearly, for $k=0$, it
follows that $\operatorname{Pr}[A\mid B]\leq\operatorname{Pr}[A]$. For the
base case $k=n$ it holds that

$\operatorname{Pr}\left[A\mid
B\right]=\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,n\end{subarray}}\operatorname{Pr}\left[\bigwedge_{i=1}^{n}\tilde{C}_{i}\mid
B\right]\operatorname{Pr}\left[A\mid
B,\bigwedge_{i=1}^{n}\tilde{C}_{i}\right]~{}.$

With Condition 1 of Lemma 2.2, the base case $k=n$ of Equation (3) follows.
Now, suppose that $0\leq k<n$ and that the inequality holds for $k+1$. Then,
we use the induction hypothesis to get

$\begin{split}\operatorname{Pr}\left[A\mid
B\right]&\leq\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,k+1\end{subarray}}\operatorname{Pr}\left[\bigwedge_{i=1}^{k+1}\tilde{C}_{i}\mid
B\right]\operatorname{Pr}\left[A\mid\bigwedge_{i=1}^{k+1}\tilde{C}_{i}\right]=\sum_{\begin{subarray}{c}\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}\\\
i=1,\dots,k\end{subarray}}\operatorname{Pr}\left[\bigwedge_{i=1}^{k}\tilde{C}_{i}\mid
B\right]\cdot X\end{split}$

with

$\displaystyle X$ $\displaystyle=$
$\displaystyle\operatorname{Pr}\left[C_{k+1}\mid
B,\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\operatorname{Pr}\left[A\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]+\operatorname{Pr}\left[\overline{C}_{k+1}\mid
B,\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\operatorname{Pr}\left[A\mid\overline{C}_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
$\displaystyle=$ $\displaystyle\operatorname{Pr}\left[C_{k+1}\mid
B,\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\underbrace{\left(\operatorname{Pr}\left[A\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]-\operatorname{Pr}\left[A\mid\overline{C}_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\right)}_{\leq
0}$
$\displaystyle+\operatorname{Pr}\left[A\mid\overline{C}_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]~{}.$

It follows from Condition 2 that $\operatorname{Pr}\left[A\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\leq\operatorname{Pr}\left[A\mid\overline{C}_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
and it follows from Condition 3 that $\operatorname{Pr}\left[C_{k+1}\mid
B,\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\geq\operatorname{Pr}\left[C_{k+1}\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$.
We use the second inequality and get

$\displaystyle X$ $\displaystyle\leq$
$\displaystyle\operatorname{Pr}\left[C_{k+1}\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\operatorname{Pr}\left[A\mid
C_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]+\operatorname{Pr}\left[\overline{C}_{k+1}\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]\operatorname{Pr}\left[A\mid\overline{C}_{k+1},\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$
$\displaystyle=$
$\displaystyle\operatorname{Pr}\left[A\mid\bigwedge_{i=1}^{k}\tilde{C}_{i}\right]$

and the induction step is proven. ∎

######  Lemma .

Let $H=(V,E)$ be an $r$-uniform hypergraph of girth at least $4$ with minimum
degree $\delta\geq\ln r+2$ and maximum degree $\Delta$. Let
$\eta=\Delta/(\delta-1)$ and let $t$ be a positive integer satisfying

$\frac{t!}{t+1}\geq\mathrm{e}r^{2}\eta^{t+1}(\ln
r+1+\mathrm{e}^{-1})^{t+1}~{}.$ (4)

Then $H$ has a $t$-shallow hitting edge set.

###### Proof.

We build an edge set $M$ with the following two-step random experiment. In the
first step, we pick each edge in $E$ independently at random with probability
$(\ln r+1)/(\delta-1)$. In the second step, we pick for every vertex $v$ that
is not covered after the first step an incident edge independently uniformly
at random. Clearly, $M$ is a hitting edge set. For an edge set $F$, we denote
by $V(F)$ the set of vertices $\bigcup_{e\in F}e$. For a set $\mathcal{F}$ of
edge sets, we denote by $V(\mathcal{F})$ the set of vertices
$\bigcup_{F\in\mathcal{F}}V(F)$.

For each edge $e\in E$, we define $X_{e}$ to be the event that $e$ is picked
in the first step. For _each_ vertex $v$ (independently of the results of the
first step), we pick an incident edge independently uniformly at random and
denote by $Y_{v}\in\operatorname{Inc}(v)$ the random variable that indicates
which edge is picked, and by $Y_{v,e}$ the event that $Y_{v}=e$. Then,

$W_{e}=\bigvee_{v\in
e}\left(Y_{v,e}\wedge\bigwedge_{e^{\prime}\in\operatorname{Inc}(v)}\overline{X}_{e^{\prime}}\right)$

denotes the event that $e$ is picked in the second step and $Z_{e}=X_{e}\vee
W_{e}$ is the event that $e$ is picked in the first or second step. Define the
set $\mathcal{F}$ to be the set of all edge sets $F\subseteq E$ of size $t+1$
such that there exists a vertex $v\in V$ with
$F\subseteq\operatorname{Inc}(v)$, i.e.,

$\mathcal{F}=\\{F\subseteq
E\colon|F|=t+1,F\subseteq\operatorname{Inc}(v)\text{ for some }v\in V\\}~{}.$

For a set $F\in\mathcal{F}$, we denote the event that $F\subseteq M$ by
$A_{F}$, i.e., $A_{F}=\bigwedge_{e\in F}Z_{e}$. These shall be the bad events
in the Lovász Local Lemma below.

We need the following observation, which easily follows from $H$ having girth
at least $4$.

######  Observation .

For any two distinct edges $e,e^{\prime}\in E$,

  1. 1.

$|e\cap e^{\prime}|\leq 1$ and

  2. 2.

if $e\cap e^{\prime}=\\{u\\}$ for some $u\in V$ then there exists no edge
$f\in E\setminus\\{e,e^{\prime}\\}$ with $e\cap f=\\{v\\}$ and $e^{\prime}\cap
f=\\{v^{\prime}\\}$ for $v,v^{\prime}\in E\setminus\\{u\\}$.

Now, we need to bound the probability that a bad event $A_{F}$ occurs.
Therefore, we show that
$\operatorname{Pr}\left[Z_{e}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\right]\leq\operatorname{Pr}[Z_{e}]$, which will be
done in the following two claims and using Observation 2.2.

######  Claim .

Let $F^{\prime}\neq\emptyset$ be an edge set with $\bigcap_{e^{\prime}\in
F^{\prime}}e^{\prime}\neq\emptyset$. Then,
$\operatorname{Pr}[\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}]\leq\operatorname{Pr}[\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}]$.

  * Proof of Claim.

Let $v$ be a vertex in $\bigcap_{e^{\prime}\in F^{\prime}}e^{\prime}$, which
is unique for $|F^{\prime}|\geq 2$ (Observation 2.2). First, we bound the
right-hand side:

$\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\right]\geq\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}X_{e^{\prime}}\right]=\prod_{e^{\prime}\in
F^{\prime}}\operatorname{Pr}[X_{e^{\prime}}]=\left(\frac{\ln
r+1}{\delta-1}\right)^{|F^{\prime}|}~{},$

where we used that the events $X_{e^{\prime}}$ are independent. Now, we bound
the left-hand side as follows:

$\displaystyle\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}\right]=\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}W_{e^{\prime}}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}\right]$ (5) $\displaystyle\leq$
$\displaystyle\operatorname{Pr}\left[Y_{v}\in
F^{\prime}\wedge\bigwedge_{g\in\operatorname{Inc}(v)\setminus
F^{\prime}}\overline{X}_{g}\right]\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}W_{e^{\prime}}\mid Y_{v}\in
F^{\prime},\bigwedge_{g\in\operatorname{Inc}(v)}\overline{X}_{g}\right]$
$\displaystyle+\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}W_{e^{\prime}}\mid\left(Y_{v}\notin
F^{\prime}\vee\bigvee_{g\in\operatorname{Inc}(v)\setminus
F^{\prime}}X_{g}\right),\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}\right]$

Then, we explicitly calculate the probabilities using Observation 2.2. First,
it holds that $\operatorname{Pr}\left[Y_{v}\in
F^{\prime}\wedge\bigwedge_{g\in\operatorname{Inc}(v)\setminus
F^{\prime}}\overline{X}_{g}\right]\leq\operatorname{Pr}\left[Y_{v}\in
F^{\prime}\right]\leq|F^{\prime}|/\delta$.

For the calculation of the other probabilities, we need the following bounds.
Let $e,e^{\prime}\in\operatorname{Inc}(v)$ be two distinct edges and
$v^{\prime}\in e^{\prime}\setminus\\{v\\}$. Then,

$\begin{split}&\operatorname{Pr}\left[Y_{v^{\prime},e^{\prime}}\wedge\bigwedge_{e^{\prime\prime}\in\operatorname{Inc}(v^{\prime})}\overline{X}_{e^{\prime\prime}}\mid\overline{X}_{e^{\prime}}\right]=\operatorname{Pr}\left[Y_{v^{\prime},e^{\prime}}\wedge\bigwedge_{e^{\prime\prime}\in\operatorname{Inc}(v^{\prime})\setminus\\{e^{\prime}\\}}\overline{X}_{e^{\prime\prime}}\right]\\\
&\leq\frac{1}{\delta}\left(1-\frac{\ln
r-1}{\delta-1}\right)^{\delta-1}\leq\frac{1}{\mathrm{e}\delta r}\end{split}$

and

$\operatorname{Pr}\left[W_{e^{\prime}}\mid
Y_{v}=e,\overline{X}_{e^{\prime}}\right]\leq\sum_{v^{\prime}\in
e^{\prime}\setminus\\{v\\}}\operatorname{Pr}\left[Y_{v^{\prime},e^{\prime}}\wedge\bigwedge_{e^{\prime\prime}\in\operatorname{Inc}{v^{\prime}}}X_{e^{\prime\prime}}\mid\overline{X}_{e^{\prime}}\right]\leq\frac{r-1}{\mathrm{e}\delta
r}\leq\frac{1}{\mathrm{e}\delta}~{}.$

Here we used $\left(1-(\ln r+1)/(\delta-1)\right)^{\delta-1}\leq
1/(\mathrm{e}r)$ for $\delta\geq\ln r+2$.

Finally, we can bound the other probabilities occurring in Equation 5. Let
$e\in F^{\prime}$ be fixed. Then,

$\begin{split}&\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}W_{e^{\prime}}\mid Y_{v}\in
F^{\prime},\bigwedge_{g\in\operatorname{Inc}(v)}\overline{X}_{g}\right]\leq\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}\setminus\\{e\\}}W_{e^{\prime}}\mid
Y_{v}=e,\bigwedge_{g\in\operatorname{Inc}(v)}\overline{X}_{g}\right]\\\
&=\prod_{e^{\prime}\in
F^{\prime}\setminus\\{e\\}}\operatorname{Pr}\left[W_{e^{\prime}}\mid
Y_{v}=e,\overline{X}_{e^{\prime}}\right]\leq\left(\frac{1}{\mathrm{e}\delta}\right)^{|F^{\prime}|-1}~{}.\end{split}$

Analogously, we bound using some fixed $e\in\operatorname{Inc}(v)\setminus
F^{\prime}$:

$\begin{split}&\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}W_{e^{\prime}}\mid\left(Y_{v}\notin
F^{\prime}\vee\bigvee_{g\in\operatorname{Inc}(v)\setminus
F^{\prime}}X_{g}\right),\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}\right]\\\ &\leq\prod_{e^{\prime}\in
F^{\prime}}\operatorname{Pr}\left[W_{e^{\prime}}\mid\left(Y_{v}=e\vee\bigvee_{g\in\operatorname{Inc}(v)\setminus
F^{\prime}}X_{g}\right),\overline{X}_{e^{\prime}}\right]\leq\left(\frac{1}{\mathrm{e}\delta}\right)^{|F^{\prime}|}~{}.\end{split}$

In total, we get

$\operatorname{Pr}\left[\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}\overline{X}_{e^{\prime}}\right]\leq(\mathrm{e}|F^{\prime}|+1)\left(\frac{1}{\mathrm{e}\delta}\right)^{|F^{\prime}|}\leq(\mathrm{e}|F^{\prime}|+1)\left(\frac{1}{\mathrm{e}(\delta-1)}\right)^{|F^{\prime}|}~{}.$

Hence, in order to show the claim, we only need to show that $(\mathrm{e}(\ln
r+1))^{|F^{\prime}|}\geq\mathrm{e}|F^{\prime}|+1$. Since $r\geq 2$, it
suffices to show that $(\mathrm{e}(\ln
2+1))^{|F^{\prime}|}\geq\mathrm{e}|F^{\prime}|+1$, which holds for all
$|F^{\prime}|\geq 1$. This finishes the proof of this claim. ∎

######  Claim .

For every edge set $F^{\prime}$ and every edge $e\notin F^{\prime}$ with
$e\cap(\bigcap_{e^{\prime}\in F^{\prime}}e^{\prime})\neq\emptyset$ it holds
that $\operatorname{Pr}\left[Z_{e}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\right]\leq\operatorname{Pr}[Z_{e}]$.

  * Proof of Claim.

For $F^{\prime}=\emptyset$, the claim obviously holds. Thus, let
$F^{\prime}\neq\emptyset$. Let $v$ be the vertex in
$e\cap(\bigcap_{e^{\prime}\in F^{\prime}}e^{\prime})$. By Observation 2.2, the
vertex $v$ is unique. We show that the conditions of Lemma 2.2 hold with
$A:=Z_{e}$, $B:=\bigwedge_{e^{\prime}\in F^{\prime}}Z_{e^{\prime}}$,
$C_{1}:=\bigvee_{e^{\prime}\in F^{\prime}}X_{e^{\prime}}$,
$C_{2}:=\overline{X}_{e}$ and $C_{3}:=\overline{Y}_{v,e}$.

First, we show that Condition 1 of Lemma 2.2 holds. Let
$\tilde{C}_{2}\in\\{C_{2},\overline{C}_{2}\\}$ and
$\tilde{C}_{3}\in\\{C_{3},\overline{C}_{3}\\}$ be arbitrary. First, note that
$\operatorname{Pr}[A\mid
B,C_{1},\tilde{C}_{2},\tilde{C}_{3}]=\operatorname{Pr}[A\mid
C_{1},\tilde{C}_{2},\tilde{C}_{3}]$ as if one edge in $F^{\prime}$ is picked
in the first step, then $A$ is independent of $B$. Secondly,
$\operatorname{Pr}[A\mid
B,\overline{C}_{1},\overline{C}_{2},\tilde{C}_{3}]=\operatorname{Pr}[A\mid\overline{C}_{1},\overline{C}_{2},\tilde{C}_{3}]$
as if $e$ is picked in the first step then $A$ is independent of $B$. Thirdly,
$\operatorname{Pr}[A\mid
B,\overline{C}_{1},C_{2},C_{3}]=\operatorname{Pr}[A\mid\overline{C}_{1},C_{2},C_{3}]$
as if $Y_{v}\neq e$ then $A$ is independent of $B$. And finally,
$\operatorname{Pr}[A\mid
B,\overline{C}_{1},C_{2},\overline{C}_{3}]=\operatorname{Pr}[A\mid\overline{C}_{1},C_{2},\overline{C}_{3}]$
as if none of the edges in $F^{\prime}\cup\\{e\\}$ is picked in the first step
and $Y_{v}=e$, then $A$ is independent of $B$. In each case we used that $H$
has girth at least $4$ and Observation 2.2. Therefore, Condition 1 of Lemma
2.2 is satisfied.

Now, we show that Condition 2 of Lemma 2.2 holds. First, note that
$\operatorname{Pr}[A\mid\tilde{C}_{1},\tilde{C}_{2},C_{3}]\leq\operatorname{Pr}[A\mid\tilde{C}_{1},\tilde{C}_{2}]$
and
$\operatorname{Pr}[A\mid\tilde{C}_{1},C_{2}]\leq\operatorname{Pr}[A\mid\tilde{C}_{1}]$
for all $\tilde{C}_{1}\in\\{C_{1},\overline{C}_{1}\\}$ and
$\tilde{C}_{2}\in\\{C_{2},\overline{C}_{2}\\}$ hold since $C_{2}$ and $C_{3}$
only have negative occurrences in $A$. Moreover, $\operatorname{Pr}[A\mid
C_{1}]\leq\operatorname{Pr}[A]$ since each $X_{e^{\prime}}$ for $e^{\prime}\in
F^{\prime}$ only has negative occurrences in $A$. This satisfies Condition 2
of Lemma 2.2.

Now, we show that Condition 3 of Lemma 2.2 holds. Note that $C_{2}$ and
$C_{3}$ only have positive occurrences in $B$ and therefore,
$\operatorname{Pr}[B\mid\tilde{C}_{1},\tilde{C}_{2},C_{3}]\geq\operatorname{Pr}[B\mid\tilde{C}_{1},\tilde{C}_{2}]$
and
$\operatorname{Pr}[B\mid\tilde{C}_{1},C_{2}]\geq\operatorname{Pr}[B\mid\tilde{C}_{1}]$
for all $\tilde{C}_{1}\in\\{C_{1},\overline{C}_{1}\\}$ and
$\tilde{C}_{2}\in\\{C_{2},\overline{C}_{2}\\}$. Hence, we only have to show
that $\operatorname{Pr}[B\mid C_{1}]\geq\operatorname{Pr}[B]$, which is
equivalent to
$\operatorname{Pr}[B\mid\overline{C}_{1}]\leq\operatorname{Pr}[B]$ and is done
in Claim 2.2.

Therefore, all Conditions of Lemma 2.2 are satisfied and we can conclude that
$\operatorname{Pr}[A\mid B]\leq\operatorname{Pr}[A]$, i.e.,
$\operatorname{Pr}\left[Z_{e}\mid\bigwedge_{e^{\prime}\in
F^{\prime}}Z_{e^{\prime}}\right]\leq\operatorname{Pr}[Z_{e}]$, which finishes
the proof of the claim. ∎

Using Claim 2.2, we can now bound the probability of the bad events $A_{F}$.
The probability that an edge $e$ is picked in the first or second step is
bounded by

$\operatorname{Pr}[Z_{e}]=\operatorname{Pr}[X_{e}]+\operatorname{Pr}[W_{e}]\leq\frac{\ln
r+1}{\delta-1}+\left(1-\frac{\ln
r+1}{\delta-1}\right)^{\delta}\cdot\frac{r}{\delta}\leq\frac{\ln
r+1+\mathrm{e}^{-1}}{\delta-1}~{}.$

Here, we used our assumption $\delta\geq\ln r+2$. By Claim 2.2, we can bound
the probability of a bad event $A_{F}$ by

$\operatorname{Pr}[A_{F}]=\operatorname{Pr}\left[\bigwedge_{e\in
F}Z_{e}\right]\leq\prod_{e\in F}\operatorname{Pr}[Z_{e}]\leq\left(\frac{\ln
r+1+\mathrm{e}^{-1}}{\delta-1}\right)^{t+1}=:p~{}.$

Now, we have to bound the degree of dependence of the events $A_{F}$ with
$F\in\mathcal{F}$. We use the same dependency graph as in the proof of Lemma
2.1, i.e., two bad events $A_{F}$ and $A_{F^{\prime}}$ are adjacent in the
dependency graph if and only if $V(F)\cap V(F^{\prime})\neq\emptyset$. To show
that this dependency graph satisfies the conditions of Remark 2.1, we use the
following claim.

######  Claim .

For every set $\mathcal{F}^{\prime}$ of edge sets in ${\cal F}$ and an edge
set $F\in{\cal F}$ with $V(F)\cap V(\mathcal{F}^{\prime})=\emptyset$ it holds
that
$\operatorname{Pr}\left[A_{F}\mid\bigwedge_{F^{\prime}\in\mathcal{F}^{\prime}}\overline{A}_{F^{\prime}}\right]\leq\operatorname{Pr}[A_{F}]$.

  * Proof of Claim.

Let $S\subseteq E$ be the set of edges $g\in E$ with $g\cap V(F)\neq\emptyset$
and $g\cap V(\mathcal{F}^{\prime})\neq\emptyset$. We show that the conditions
of Lemma 2.2 hold with $A:=A_{F}$,
$B:=\bigwedge_{F^{\prime}\in\mathcal{F}^{\prime}}\overline{A}_{F^{\prime}}$
and $\\{C_{1},\dots,C_{n}\\}:=\\{X_{g}\\}_{g\in S}$. Then, by Lemma 2.2, this
claim follows.

First of all, Condition 1 holds since by conditioning on
$\bigwedge_{i=1}^{n}\tilde{C}_{i}$ for
$\tilde{C}_{i}\in\\{C_{i},\overline{C}_{i}\\}$, $A$ is independent of $B$.
Secondly, Condition 2 and Condition 3 hold since $C_{j}=X_{g}$, for some $g\in
S$, only has negative occurrences in $A=A_{F}$ and only positive occurrences
in $B=\bigwedge_{F^{\prime}\in\mathcal{F}^{\prime}}\overline{A}_{F^{\prime}}$.
∎

It therefore follows that the graph constructed above satisfies the conditions
of Remark 2.1 and is a valid dependency graph. Analogous to the proof of Lemma
2.1, we can bound the degree of dependence $d$ by

$d+1\leq(t+1)\Delta
r^{2}\binom{\Delta-1}{t}\leq\frac{t+1}{t!}r^{2}\Delta^{t+1}~{}.$

To apply the Lovász Local Lemma, we calculate $\mathrm{e}p(d+1)$. With
Equation (4) and $\eta=\Delta/(\delta-1)$ it follows that

$\mathrm{e}p(d+1)\leq\mathrm{e}\cdot\left(\frac{\ln
r+1+\mathrm{e}^{-1}}{\delta-1}\right)^{t+1}\cdot\frac{t+1}{t!}r^{2}\Delta^{t+1}\leq\mathrm{e}r^{2}\eta^{t+1}\left(\ln
r+1+\mathrm{e}^{-1}\right)^{t+1}\frac{t+1}{t!}\leq 1~{}.$

By the Lovász Local Lemma, the probability that no event $A_{F}$ with
$F\in\mathcal{F}$ occurs is greater than zero. Thus, there exists an edge set
$M\subseteq E$ such that every vertex has degree
$1\leq\operatorname{deg}_{M}(v)\leq t$ in $M$. ∎

Using Lemma 2.2, we find an asymptotic upper bound for $t(\mu,r)$, i.e., the
largest integer such that every $r$-uniform $\mu$-near-regular hypergraph of
girth at least $4$ has a $t$-shallow hitting edge set. Let $W(x)$ be the
Lambert $W$-function, i.e., the unique function defined by $x=W(x)\exp(W(x))$
for all real numbers $x\geq-e^{-1}$.

######  Theorem 2.2.

Let $H$ be an $r$-uniform $\mu$-near-regular hypergraph of girth at least $4$.
Then, $H$ has a $t(\mu,r)$-shallow hitting edge set, where

$t(\mu,r)=c\mu\ln(r)(1+o_{\mu r}(1))=O(\mu\ln r)$

and $c=\mathrm{e}^{1+W(2/(\mathrm{e}\mu))}=\mathrm{e}+o_{\mu}(1)$.

###### Proof.

Let $\delta$ be the minimum degree and $\Delta$ be the maximum degree of
$H=(V,E)$. If $\delta\leq\ln r+2$ then $\Delta\leq\mu(\ln r+2)$ and the edge
set $E$ is a $t$-shallow hitting edge set. Thereby, assume that $\delta>\ln
r+2$. Let $\eta=\Delta/(\delta-1)$. Note that
$\mu\leq\eta=\mu\delta/(\delta-1)=(1+o_{r}(1))\mu$ for $\delta>\ln r+2$. We
show that

$\begin{split}t&=1+\left\lceil\mathrm{e}^{1+h(\eta,r)}\eta(\ln
r+1+\mathrm{e}^{-1})\right\rceil=\mathrm{e}^{1+W(2/(\mathrm{e}\eta))}\eta\ln(r)(1+o_{\eta
r}(1))\end{split}$ (6)

with

$h(\eta,r)=W\left(\frac{2}{\mathrm{e}}\cdot\left(\frac{1}{\eta}+\frac{\ln(\eta(\ln
r+1+\mathrm{e}^{-1}))}{\eta(\ln
r+1+\mathrm{e}^{-1})}\right)\right)=W\left(\frac{2}{\mathrm{e}\eta}\right)(1+o_{\eta
r}(1))$

satisfies Equation (4). Indeed, with Stirling’s Formula $t!\geq\sqrt{2\pi
t}(t/\mathrm{e})^{t}$ and with $(t+1)/\sqrt{2\pi t}\leq t$ for $t\geq 1$ it
follows that

$\mathrm{e}\frac{t+1}{t!}r^{2}\eta^{t+1}(\ln
r+1+\mathrm{e}^{-1})^{t+1}\leq\mathrm{e}\frac{t+1}{\sqrt{2\pi t}}r^{2}\eta(\ln
r+1+\mathrm{e}^{-1})\left(\frac{\eta(\ln
r+1+\mathrm{e}^{-1})}{t/\mathrm{e}}\right)^{t}\\\
\leq\mathrm{e}^{2}r^{2}\eta^{2}(\ln
r+1+\mathrm{e}^{-1})^{2}\left(\frac{\eta(\ln
r+1+\mathrm{e}^{-1})}{(t-1)/\mathrm{e}}\right)^{t-1}~{}.$

We define $s=\mathrm{e}\eta(\ln r+1+\mathrm{e}^{-1})$ and $a=(rs)^{2}$.
Observe that $h(\eta,r)=W((\ln a)/s)$. By using Equation (6), we get

$\mathrm{e}\frac{t+1}{t!}r^{2}\eta^{t+1}(\ln r+1+\mathrm{e}^{-1})^{t+1}\leq
a\exp\left(-s\cdot
h(\eta,r)\mathrm{e}^{h(\eta,r)}\right)=a\exp\left(-s\cdot\frac{\ln
a}{s}\right)=1~{}.$

Therefore, we have $t=\mathrm{e}^{1+W(2/(\mathrm{e}\eta))}\eta\ln(r)(1+o_{\eta
r}(1))$. With $\mu\leq\eta\leq(1+o_{r}(1))\mu$, the theorem follows. ∎

For $\mu=1$ we get the following corollary.

######  Corollary .

Every $r$-uniform regular hypergraph of girth at least $4$ has a
$t(r)$-shallow hitting edge set, where

$t(r)=c\ln(r)(1+o_{r}(1))=O(\ln r)$

and $c=\mathrm{e}^{1+W(2/\mathrm{e})}=4.319\dots$.

###  2.3 Lower bounds for uniform regular partite hypergraphs

For the lower bounds, we seek to find for infinitely many values of $r$, an
integer $t=t(r)$ (ideally large in terms of $r$) and an $r$-uniform
$r$-partite regular hypergraph $H_{t}$ with no $(t-1)$-shallow hitting edge
set. In fact, we shall construct $H_{t}$ to be $t$-regular, which translates
the absence of a $(t-1)$-shallow hitting edge set in $H_{t}$ to the absence of
a proper vertex $2$-coloring of its dual $H_{t}^{*}$. By using the
dualization, we can employ constructions of $t$-uniform non-$2$-colorable
hypergraphs with maximum degree $r$ (ideally small in terms of $t$), which are
a classical topic initiated by Erdős and Lovász [10]. The currently best bound
is due to Kostochka and Rödl, where we cite here only the case of two colors
and girth at least four.

######  Theorem 2.3 (Kostochka and Rödl [18]).

For any $t\geq 2$ there exists a $t$-uniform $r$-regular non-$2$-colorable
hypergraph $H$ of girth at least four, with $r=\lceil t2^{t-1}\ln 2\rceil$.
Moreover, $H$ is the union of $r$ perfect matchings.

######  Remark .

Kostochka and Rödl do not claim that $H$ is the union of $r$ perfect
matchings, but their construction is easily tweaked to admit this extra
property. In fact, they start with any $T$-uniform $r$-regular $H_{0}$ of
large enough girth (girth at least four is enough for us) for some specific
large value of $T$ of the form $T=m_{0}\cdot t$. Then, each hyperedge of
$H_{0}$ is replaced by a certain (randomly chosen) matching of $m_{0}$
hyperedges of size $t$ each. Now we can choose $H_{0}$ to be the union of $r$
perfect matchings (a random choice on a large enough vertex set will do),
which implies that also $H$ is the union of $r$ perfect matchings.

######  Corollary .

For any $t\geq 2$ there exists an $r$-uniform $r$-partite $t$-regular
hypergraph of girth at least four that has no $(t-1)$-shallow hitting edge
set, where $r=\lceil t2^{t-1}\ln 2\rceil$.

###### Proof.

Let $H_{t}$ be the dual of the hypergraph $H$ from Theorem 2.3. Then $H_{t}$
is $r$-partite (hence $r$-uniform) since $H$ is the union of $r$ perfect
matchings, $H_{t}$ is $t$-regular since $H$ is $t$-uniform, and $H_{t}$ has
girth at least four since $H$ has girth at least four. Finally, a
$(t-1)$-shallow hitting edge set $M$ in $H_{t}$ would correspond to a vertex
set $A$ of $H$ such that every edge of $H$ contains at least one vertex of $A$
(since $M$ is hitting) and at most $t-1$ vertices of $A$ (since $A$ is
$(t-1)$-shallow). Thus $(A,V_{H}-A)$ would be a proper vertex $2$-coloring of
$H$, which is a contradiction. ∎

In the next theorem, we construct an $r$-uniform $r$-partite regular
hypergraph which only has $t$-shallow hitting edge sets for
$t\geq\log_{2}(r+1)$.

Figure 2: The construction of the hypergraph $H^{\prime}$ of Theorem 2.4 with
$t=2$. The vertices are elements of $\mathbb{F}_{2}^{t+1}$. Two vertices $x$
and $x^{\prime}$ are in the same part if $x+x^{\prime}=x_{0}$ with
$x_{0}=(1,0,\dots,0)^{T}$. The set $L(a)$ is the set of all
$x\in\mathbb{F}_{2}^{t+1}\setminus\\{0\\}$ with $a^{T}x=0$. The set of edges
of $H^{\prime}$ is the set of all $L(a)$ that do not contain $x_{0}$.

######  Theorem 2.4.

Let $t\geq 2$ be an integer. There exists an $r$-uniform $r$-partite
$2^{t-1}$-regular hypergraph with two vertices per part that has no
$(t-1)$-shallow hitting edge set, where $r=2^{t}-1$, i.e., $t=\log_{2}(r+1)$.

###### Proof.

This construction is based on the construction of projective spaces of order
$2$.

Let $\mathbb{F}_{2}$ be the finite field of two elements and let
$V=\mathbb{F}_{2}^{t+1}\setminus\\{0\\}$ be the set of vertices. For a vector
$a\in\mathbb{F}_{2}^{t+1}$, we define $L(a)$ to be the set of vertices $x\in
V$ with $a^{T}x=0$. Then, we define the edge set to be $E=\\{L(a)\mid
a\in\mathbb{F}_{2}^{t+1}\setminus\\{0\\}\\}$ and define the hypergraph by
$H=(V,E)$. The vertices of $H$ correspond to the $1$-dimensional subspaces of
$\mathbb{F}_{2}^{t+1}$ and the edges correspond to the $t$-dimensional
subspaces of $\mathbb{F}_{2}^{t+1}$.

Let $L(a)$ be an edge. Since $a\neq 0$, there are exactly $2^{t}$ solutions to
the equation $a^{T}x=0$ for $x\in\mathbb{F}_{2}^{t+1}$ and thus, there are
$2^{t}-1$ solutions to $a^{T}x=0$ with
$x\in\mathbb{F}_{2}^{t+1}\setminus\\{0\\}$. Hence, each edge has size
$2^{t}-1$ and $H$ is $r$-uniform with $r=2^{t}-1$.

Let $x\in V$ be a vertex. Analogous, there are $2^{t}-1$ solutions of
$a^{T}x=0$ with $a\in\mathbb{F}_{2}^{t+1}\setminus\\{0\\}$ and thus, $H$ is
$(2^{t}-1)$-regular.

Observe that each $t$ edges have a common vertex. Indeed, let
$L(a_{1}),\dots,L(a_{t})$ be $t$ edges of $H$. Consider the matrix
$A:=(a_{1},a_{2},\dots,a_{t})\in\mathbb{F}_{2}^{(t+1)\times t}$. Then, $A^{T}$
has rank at most $t$ and the nullspace of $A^{T}$ has dimension at least $1$.
Thus, there is at least one nonzero solution $x\in V$ to $A^{T}x=0$. Then, $x$
clearly satisfies all equations $a_{i}^{T}x=0$ for $i=1,\dots,t$ and thus, $x$
is incident to all edges $L(a_{1}),\dots,L(a_{t})$.

From $H$, we construct an $r$-uniform $r$-partite $2^{t-1}$-regular hypergraph
$H^{\prime}$ by “truncating” the hypergraph $H$. Let
$x_{0}=(1,0,\dots,0)^{T}\in V$. To obtain $H^{\prime}=(V^{\prime},E^{\prime})$
from $H=(V,E)$, we remove the vertex $x_{0}\in V$ and all incident edges of
$x_{0}$. See also Figure 2 for the construction of $H^{\prime}$ with $t=2$.
Note that $H^{\prime}$ is $r$-uniform and every set of $t$ edges has a vertex
in common. Moreover, $H^{\prime}$ has $|V^{\prime}|=2^{t+1}-2=2r$ vertices. We
need to show that $H^{\prime}$ is $2^{t-1}$-regular and $r$-partite with parts
of size $2$. Since every $t$ edges have a vertex in common, it follows that
there exists no $(t-1)$-shallow hitting edge set.

We define that two vertices $x,x^{\prime}\in V$ are in the same part of
$H^{\prime}$ if $x+x^{\prime}=x_{0}$. Clearly, each edge $L(a)$ of $H$ which
is incident to both $x$ and $x^{\prime}$ is incident to $x_{0}$, since
$a^{T}x_{0}=a^{T}x+a^{T}x^{\prime}=0+0=0$. Thus, no edge of $H^{\prime}$
contains two vertices of the same part and $H^{\prime}$ is $r$-uniform
$r$-partite with parts of size $2$.

Moreover, for every vertex $x\in V\setminus\\{x_{0}\\}$ in $H$ there are
$2^{t-1}-1$ edges $L(a)$ which are incident to both $x_{0}$ and $x$, which can
be seen as follows. Since $x_{0}=(1,0,\dots,0)$ is a solution of
$a^{T}x_{0}=0$, it must hold that $a_{1}=0$. Then, there are $2^{t-1}-1$
solutions $a$ to $a^{T}x=0$ with $a_{1}=0$, since $x\in
V\setminus\\{x_{0}\\}$. Thus, we removed $2^{t-1}-1$ incident edges for each
vertex $x\in V\setminus\\{x_{0}\\}$ from $H$ to obtain $H^{\prime}$. Then, we
can conclude that $H^{\prime}$ is $d$-regular with
$d=2^{t}-1-(2^{t-1}-1)=2^{t-1}$. ∎

##  3 Maximum Shallow Edge Sets

In this section, we consider the maximum possible size of shallow edge sets in
$r$-uniform $\mu$-near-regular hypergraphs. In comparison to $t$-shallow
hitting edge sets, we relax the condition $1\leq\operatorname{deg}(v)\leq t$
to $\operatorname{deg}(v)\leq t$ for all vertices $v\in V$. Additionally, we
are not interested in minimizing $t$ for a given $r$ and $\mu$ (as for shallow
hitting edge sets) but in maximizing the size of a $t$-shallow edge set for
given $t$, $r$ and $\mu$ in $r$-uniform $\mu$-near-regular hypergraphs. We
show that every $r$-uniform $\mu$-near-regular hypergraph $H$ with $n$
vertices has a $t$-shallow edge set of size

$\Omega\left(\frac{nt}{\mu r^{1+1/t}}\right)~{},$

whenever $\Delta\geq t$ for the maximum degree $\Delta$ of $H$. Moreover, we
show in Section 3.2, that the lower bound above is tight for regular
$r$-uniform hypergraphs.

For this, we use the following framework. For a hypergraph $H$, let
$\nu_{t}(H)$ be the size of a maximum $t$-shallow edge set in $H$. Note that
$\nu_{1}(H)$ is the size of a maximum matching in $H$. Let $H$ be an
$r$-uniform hypergraph with $n$ vertices. Observe that $\nu_{t}(H)\leq nt/r$
is an upper bound on the size of a $t$-shallow edge set in $H$ since every
vertex can be covered at most $t$ times and every edge has size $r$. If $H$ is
an $r$-uniform hypergraph with $n$ vertices, we define by
$\eta_{t}(H)=\nu_{t}(H)/(nt/r)$. We are particularly interested in bounding
$\eta_{t}(H)$ for such hypergraphs $H$. For this, let $\mathcal{H}_{t}(r,\mu)$
be the set of all $r$-uniform $\mu$-near-regular hypergraphs with
$\Delta(H)\geq t$. We only consider such hypergraphs with $\Delta(H)\geq t$
since for $\Delta(H)<t$, the whole edge set is trivially a maximum $t$-shallow
edge set. We define

$\eta_{t}(r,\mu)=\inf_{H\in\mathcal{H}_{t}(r,\mu)}\eta_{t}(H)$

Moreover, we define $\eta_{t}(r)=\eta_{t}(r,1)$. Observe that
$0\leq\eta_{t}(H)\leq 1$ for every hypergraph $H\in\mathcal{H}_{t}(r,\mu)$ and
thus $0\leq\eta_{t}(r,\mu)\leq 1$ for every positive integer $r$ and every
real number $\mu\geq 1$.

We show in Section 3.1 that

$\eta_{t}(r,\mu)\geq\frac{1-o_{t}(1)}{\mathrm{e}}\cdot\mu^{-1}r^{-1/t}~{}.$

This result is tight for $\mu=1$ up to a constant factor. In fact, we show
that for every real number $\epsilon>0$ there exist infinitely many positive
integers $r$ such that

$\eta_{t}(r)\leq(1+\epsilon)\cdot r^{-1/t}$

by providing a construction through combinatorial designs.

###  3.1 A lower bound for near-regular hypergraphs

######  Lemma .

Let $r\geq 2$, $t$ and $k$ be positive integers. Let $H=(V,E)$ be an
$r$-uniform hypergraph of maximum degree $\Delta$. If

$\frac{t!}{t+1}\left(\frac{k}{\Delta}\right)^{t}\geq\mathrm{e}r$ (7)

then there exists a partition of $E$ into $k$ disjoint $t$-shallow edge sets
$M_{1},\dots,M_{k}$.

###### Proof.

We consider the following random experiment. For each edge $e\in E$, we pick a
color $\chi(e)\in\\{1,\dots,k\\}$ uniformly at random. The colors correspond
to the sets $M_{i}$, $i=1,\dots,k$. We use the Lovász Local Lemma to prove
that there exists an edge coloring such that no vertex has $t+1$ incident
edges of the same color. For this, we define $\mathcal{F}$ to be the set of
all edge sets $F\subseteq E$ of size $t+1$ such that there exists a vertex
$v\in V$ with $F\subseteq\operatorname{Inc}(v)$, i.e.

$\mathcal{F}=\\{F\subseteq
E\colon|F|=t+1,F\subseteq\operatorname{Inc}(v)\text{ for some }v\in V\\}~{}.$

For a set $F\in\mathcal{F}$, denote by $A_{F}$ the event that all edges in $F$
received the same color. Clearly,

$\operatorname{Pr}[A_{F}]=\frac{1}{k^{t}}=:p~{}.$

We construct a dependency graph $G_{\text{D}}=(V_{\text{D}},E_{\text{D}})$
with $V_{\text{D}}=\\{A_{F}\mid F\in\mathcal{F}\\}$ and two events $A_{F}$ and
$A_{F^{\prime}}$ adjacent if and only if $F\cap F^{\prime}\neq\emptyset$.
Then, each event $A_{F}$ is mutually independent of all non-adjacent events
$A_{F^{\prime}}$.

In the next step, we have to bound the degree of dependence $d$ of the events
$A_{F}$ for $F\in\mathcal{F}$. For an edge $e\in E$ and a vertex $v\in V$,
denote by $\mathcal{F}_{e,v}$ the set of all edge sets $F\in\mathcal{F}$ with
$e\in F$ and $F\subseteq\operatorname{Inc}(v)$. Note that the edge $e$ is
contained in all sets $F\in\mathcal{F}_{e,v}$. Since
$F\subseteq\operatorname{Inc}(v)$ for all $F\in\mathcal{F}_{e,v}$, there are
at most $\binom{\Delta-1}{t}$ ways to choose the remaining edges. Hence, the
size of each $\mathcal{F}_{e,v}$ can be bounded by

$|\mathcal{F}_{e,v}|\leq\binom{\Delta-1}{t}~{}.$

Let $A_{F}$ be an arbitrary but fixed event with $F\in\mathcal{F}$. For every
adjacent event $A_{F^{\prime}}$, it holds that $F\cap
F^{\prime}\neq\emptyset$. Thus, there must be an edge $e$ in $F\cap
F^{\prime}$. Moreover, by the definition of $\mathcal{F}$, there exists a
vertex $v$ such that $F\subseteq\operatorname{Inc}(v)$. Then, the degree of
dependence $d$ can be bounded by

$d+1\leq\max_{F\in\mathcal{F}}\left|\bigcup\limits_{e\in
F}\bigcup\limits_{v\in e}\mathcal{F}_{e,v}\right|\leq(t+1)\cdot
r\cdot\binom{\Delta-1}{t}\leq\frac{t+1}{t!}r\Delta^{t}~{}.$

To apply the Lovász Local Lemma, we calculate $\mathrm{e}p(d+1)$ and use
Equation 7:

$\mathrm{e}p(d+1)\leq\frac{\mathrm{e}}{k^{t}}\cdot\frac{t+1}{t!}r\Delta^{t}\leq
1~{}.$

By the Lovász Local Lemma, the probability that no event $A_{F}$ with
$F\in\mathcal{F}$ occurs is greater than zero. Thus, there exists an edge
coloring $\chi\colon E\to\\{1,\dots,k\\}$ such that no vertex has $t+1$
incident edges of the same color. For $i=1,\dots,k$, we define $M_{i}$ to be
the set of all edges of color $i$. Then, each set $M_{i}$ is $t$-shallow and
it holds that $M_{1}\dot{\cup}\cdots\dot{\cup}M_{k}=E$. ∎

######  Lemma .

Let $r\geq 2$ and $t$ be positive integers. Let $H=(V,E)$ be an $r$-uniform
hypergraph of maximum degree $\Delta\geq t$. Then, there exists a partition of
$E$ into $k$ disjoint $t$-shallow edge sets $M_{1},\dots,M_{k}$ for

$k=\frac{\mathrm{e}\Delta r^{1/t}}{t}\cdot(1+o_{t}(1))~{}.$

###### Proof.

We prove the lemma by showing that

$k=\left\lceil\frac{\mathrm{e}\Delta}{t}\left(\frac{t+1}{\sqrt{2\pi
t}}\mathrm{e}r\right)^{1/t}\right\rceil$

satisfies Equation 7. For that, we use Stirling’s Formula $t!\geq\sqrt{2\pi
t}(t/\mathrm{e})^{t}$ and the definition of $k$:

$\left(\frac{k}{\Delta}\right)^{t}\frac{t!}{t+1}\geq\left(\frac{tk}{\Delta\mathrm{e}}\right)^{t}\frac{\sqrt{2\pi
t}}{t+1}\geq\frac{t+1}{\sqrt{2\pi t}}\mathrm{e}r\cdot\frac{\sqrt{2\pi
t}}{t+1}\geq\mathrm{e}r~{}.$

By Lemma 3.1, there exist $k$ disjoint $t$-shallow edge sets
$M_{1},\dots,M_{k}$ with $M_{1}\dot{\cup}\cdots\dot{\cup}M_{k}=E$. With

$\left(\frac{t+1}{\sqrt{2\pi t}}\mathrm{e}\right)^{1/t}=1+o_{t}(1)$

it holds that

$k=\frac{\mathrm{e}\Delta r^{1/t}}{t}\cdot(1+o_{t}(1))~{}.$

∎

######  Theorem 3.1.

Let $n$, $t$ and $r\geq 2$ be positive integers and $\mu\geq 1$ be a real
number. Let $H=(V,E)$ be an $r$-uniform $\mu$-near-regular hypergraph with $n$
vertices and maximum degree $\Delta\geq t$. Then there exists a $t$-shallow
edge set of size at least

$\frac{nt}{\mathrm{e}\mu r^{1+1/t}}\cdot(1-o_{t}(1))~{}.$

###### Proof.

Let $\Delta$ be the maximum degree and $\delta$ be the minimum degree of $H$.
By Lemma 3.1, for

$k=\frac{\mathrm{e}\Delta r^{1/t}}{t}\cdot(1+o_{t}(1))$

there exist $k$ disjoint $t$-shallow edge sets $M_{1},\dots,M_{k}$ with
$M_{1}\dot{\cup}\cdots\dot{\cup}M_{k}=E$. It holds that

$|E|=|M_{1}|+\dots+|M_{k}|\geq n\delta/r~{}.$

By the pigeonhole principle, there exists an edge set $M_{i}$ of size

$\max_{i\in[k]}|M_{i}|\geq\frac{n\delta/r}{k}=\frac{n\delta
t}{\mathrm{e}\Delta r^{1+1/t}}\frac{1}{1+o_{t}(1)}=\frac{nt}{\mathrm{e}\mu
r^{1+1/t}}\cdot(1-o_{t}(1))~{}.$

∎

With Theorem 3.1, we obtain the following lower bound for $\eta_{t}(r,\mu)$.

######  Corollary .

Let $t$ and $r\geq 2$ be positive integers and let $\mu\geq 1$ be a real
number. Then,

$\eta_{t}(r,\mu)\geq\frac{1-o_{t}(1)}{\mathrm{e}}\cdot\mu^{-1}r^{-1/t}~{}.$

###  3.2 Upper bound via combinatorial designs

In this section, we show that there exist $r$-uniform ($r$-partite) regular
hypergraphs that only have $t$-shallow edge sets of small size. This result
follows from the existence of combinatorial designs, proved by Keevash [16].

######  Definition .

Let $t,v,k$ and $\lambda$ be positive integers. A set of _points_ $V$ with a
multiset $\mathcal{B}$ of subsets of $V$ (called _blocks_) is called a _$t$
-$(v,k,\lambda)$-design_ if

  1. 1.

$|V|=v$ and

  2. 2.

$|B|=k$ for each block $B\in\mathcal{B}$ and

  3. 3.

for each set $U\subseteq V$ of size $t$ there exist exactly $\lambda$ blocks
$B\in\mathcal{B}$ with $U\subseteq B$.

First, we state a well-known property of combinatorial designs. This theorem
gives a necessary condition for the existence of combinatorial designs.

######  Theorem 3.2 ([6]).

Let $(V,\mathcal{B})$ be a $t$-$(v,k,\lambda)$-design. If $I\subseteq V$ is a
set of size $0\leq|I|=i\leq t$, then the number of blocks containing $I$ is

$r_{i}=\lambda\binom{v-i}{t-i}\left/\binom{k-i}{t-i}\right.~{}.$

By Theorem 3.2, we obtain a necessary condition for the existence of a
$t$-$(v,k,\lambda)$-design: for all integers $i$ with $0\leq i\leq t-1$ it
must hold that $\binom{k-i}{t-i}$ divides $\lambda\binom{v-i}{t-i}$. Keevash
[16] recently showed that this condition is also sufficient for large enough
$v$. Here, a $t$-$(v,k,\lambda)$-design $(V,\mathcal{B})$ is called
_resolvable_ if the set $\mathcal{B}$ of blocks can be partitioned into
perfect matchings.

######  Theorem 3.3 (Keevash [16]).

Suppose $k\geq t\geq 1$ and $\lambda$ are fixed and $v>v_{0}(k,t,\lambda)$ is
sufficiently large such that $k\mid v$ and
$\binom{k-i}{t-i}\mid\lambda\binom{v-i}{t-i}$ for all integers $i$ with $0\leq
i\leq t-1$. Then there exists a resolvable $t$-$(v,k,\lambda)$-design.

It immediately follows from Theorem 3.3 that for any positive integers $t$ and
$k$ with $k\geq t\geq 1$ there exist $t$-$(nk,k,1)$-designs for infinitely
many $n>n_{0}(k,t)$.

######  Corollary .

Suppose $k\geq t\geq 1$ are fixed. Then there exist infinitely many positive
integers $n$ such that there exists a resolvable $t$-$(nk,k,1)$-design.

###### Proof.

We use Theorem 3.3 to prove this corollary. Clearly, $k\mid nk$ and thus, the
first condition is satisfied. Therefore, it suffices to show that there exist
infinitely many positive integers $n$ which satisfy
$\binom{k-i}{t-i}\mid\binom{nk-i}{t-i}$ for all integers $i$ with $0\leq i\leq
t-1$.

We claim that for all positive integers $\mu$,

$n=1+\mu\cdot k(k-1)(k-2)\cdots(k-t+1)$

satisfies the divisibility conditions. Indeed, for all integers $i$ with
$0\leq i\leq t-1$,

$\frac{nk-i}{k-i}=n+\frac{n-1}{k-i}i$

is a positive integer and therefore,

$\frac{\binom{nk-i}{t-i}}{\binom{k-i}{t-i}}=\frac{(nk-i)(nk-i-1)\cdots(nk-t+1)}{(k-i)(k-i-1)\cdots(k-t+1)}$

is a positive integer for all integers $i=0,1,\dots,t-1$. ∎

######  Theorem 3.4.

Let $t$ and $k$ be positive integers with $k>t\geq 1$. Then there exist
infinitely many positive integers $n$ such that there exists an $r$-uniform
$r$-partite $k$-regular hypergraph $H$ with parts of size $n$ and maximum
$t$-shallow edge set of size $t$, where $r=\binom{nk-1}{t}/\binom{k-1}{t}$.
This shows

$\eta_{t}(r)\leq\eta_{t}(H)\leq\frac{1}{1-t/k}\cdot r^{-1/t}$

for the specified values of $r$.

###### Proof.

Let $H=(V,\mathcal{B})$ be a resolvable $(t+1)$-$(nk,k,1)$-design. This exists
due to Corollary 3.2 for infinitely many positive integers $n$. That is,
$|V|=nk$, each block $B\in\mathcal{B}$ has size $|B|=k$ and each set of $t+1$
elements of $V$ is contained in exactly one block in $\mathcal{B}$. Then, the
hypergraph $H$ is $k$-uniform, $r$-regular (because of Theorem 3.2) and has
$nk$ vertices and $nr$ edges. Define $H^{*}=(V^{*},E^{*})$ to be the dual
hypergraph of $H$. Then, $H^{*}$ has $nr$ vertices and $nk$ edges. Moreover,
$H^{*}$ is $r$-uniform and $k$-regular. Since the design $H=(V,\mathcal{B})$
is resolvable, the hypergraph $H^{*}$ is $r$-partite with parts of size $n$.
Note that every set of $t+1$ edges in $H^{*}$ has a vertex that is incident to
all $t+1$ edges. Thus, the maximum $t$-shallow edge set has size $t$, i.e.
$\nu_{t}(H)=t$. With

$r=\frac{\binom{nk-1}{t}}{\binom{k-1}{t}}=\frac{(nk-1)(nk-2)\cdots(nk-t)}{(k-1)(k-2)\cdots(k-t)}\leq\left(\frac{nk}{k-t}\right)^{t}$

we obtain $n\geq r^{1/t}(1-t/k)$ and therefore

$\eta_{t}(r)\leq\eta_{t}(H)=\frac{t}{tn}=\frac{1}{n}\leq\frac{1}{1-t/k}\cdot
r^{-1/t}~{}.$

∎

For a fixed positive integer $t$, $k$ can be chosen arbitrarily large.
Therefore, the following corollary follows immediate.

######  Corollary .

Let $t$ be a fixed positive integer. For every real number $\epsilon>0$ there
exist infinitely many positive integers $r$ such that

$\eta_{t}(r)\leq(1+\epsilon)r^{-1/t}~{}.$

###### Proof.

We choose $k$ such that $t/k\leq\epsilon/(1+\epsilon)$ and apply Theorem 3.4.
∎

Thus, this upper bound asymptotically matches the lower bound obtained in
Section 3.1 up to a constant factor.

##  4 Minimum Degree Conditions

###  4.1 Uniform hypergraphs

In this section, we study sufficient conditions on the minimum degree of
uniform hypergraphs for the existence of $t$-shallow hitting edge sets. Let
$H=(V,E)$ be an $r$-uniform hypergraph. If $\hat{e}$ is an $(r-1)$-set of
vertices of $H$, the _neighborhood_ $N_{r-1}(\hat{e})$ of $\hat{e}$ is the set
of all vertices $v$ such that $\hat{e}\cup\\{v\\}$ is an edge in $H$. We
define the _minimum degree_ $\delta_{r-1}(H)$ of an $r$-uniform hypergraph to
be the minimum of $|N_{r-1}(\hat{e})|$ over all $(r-1)$-sets $\hat{e}$ of
vertices in $H$. This is also called the _minimum co-degree_ of $H$.

The problem of finding minimum degree thresholds for the existence of perfect
matchings in $r$-uniform hypergraphs is a classical topic in extremal graph
theory. These questions are referred to as Dirac-type problems as Dirac [8]
showed that every graph on $n$ vertices with minimum degree at least $n/2$
contains a Hamiltonian cycle (and therefore a perfect matching if $n$ is
even). Rödl, Ruciński and Szemerédi [23] started the study of Dirac-type
problems for $3$-uniform hypergraphs. Kühn and Osthus [19] and Rödl, Ruciński
and Szemerédi [24] improved the minimum degree conditions for $r$-uniform
hypergraphs until Rödl, Ruciński and Szemerédi [25] settled the problem by
proving a tight minimum degree condition for the existence of a perfect
matching in $r$-uniform hypergraphs, stated in Theorem 4.1. See also [28] for
a survey on Dirac-type problems in hypergraphs.

######  Theorem 4.1 (Rödl, Ruciński and Szemerédi [25]).

Let $r\geq 3$ be an integer and let $n$ be sufficiently large and divisible by
$r$. If $H$ is an $r$-uniform hypergraph with $n$ vertices of minimum degree

$\delta_{r-1}(H)\geq\begin{cases}n/2+3-r,&\text{if $r/2$ is even and $n/r$ is
odd}\\\ n/2+5/2-r,&\text{if $r$ is odd and $(n-1)/2$ is odd}\\\
n/2+3/2-r,&\text{if $r$ is odd and $(n-1)/2$ is even}\\\
n/2+2-r,&\text{otherwise}\end{cases}$

then $H$ has a perfect matching. Moreover, the minimum degree condition is
tight.

Recall that perfect matchings are exactly $1$-shallow hitting edge sets.
Generalizing this, we seek to find as tight as possible minimum degree
conditions for the existence of $t$-shallow hitting edge sets in $r$-uniform
hypergraphs for fixed $t$ and $r$. Let us start on the negative side by
constructing an $r$-uniform hypergraph $H$ with large minimum degree
$\delta_{r-1}(H)$ that has no $t$-shallow hitting edge set.

######  Theorem 4.2.

For all positive integers $r\geq 2$, $t\geq 2$ and $n$ there exists an
$r$-uniform hypergraph $H=(V,E)$ with $|V|=n$ vertices and

$\delta_{r-1}(H)\geq\frac{n}{(r-1)t+1}-1$

that has no $t$-shallow hitting edge set.

###### Proof.

Let $k=(r-1)t+1$ and $\delta=n/k-1$. We define an $r$-uniform hypergraph
$H=(V,E)$ with $V=A\dot{\cup}B$ where

$|A|=\lceil\delta\rceil\quad\text{and}\quad|B|=n-\lceil\delta\rceil~{}.$

Note that $|V|=|A|+|B|=n$ and $|A|<n/k$ and $|B|>(k-1)n/k$. We define that
$e\subseteq V$ is an edge in $H$ if and only if $|e|=r$ and $e$ has a vertex
in $A$, i.e., $e\cap A\neq\emptyset$. Clearly, $H$ has minimum degree
$\delta_{r-1}(H)\geq\delta$. Assume, for contradiction, that there exists a
$t$-shallow hitting edge set $M$ of $H$. Since every vertex in $A$ is covered
at most $t$ times, we have

$|M|\leq t|A|<\frac{tn}{k}~{}.$

On the other hand,

$|M|\geq\frac{|B|}{r-1}>\frac{(k-1)n}{(r-1)k}=\frac{tn}{k}~{},$

since every vertex in $B$ is covered at least once and at most $r-1$ vertices
of $B$ are covered by the same edge in $M$. Thus, $tn/k<|M|<tn/k$ is the
desired contradiction. ∎

On the positive side, if the minimum degree of $H$ is just one larger than the
bound in Theorem 4.2, then $t$-shallow hitting edge sets always exist. In
other words, the following theorem is best-possible.

######  Theorem 4.3.

Let $t\geq 2$ be an integer. If $H=(V,E)$ is an $r$-uniform hypergraph with
$|V|=n$ vertices which satisfies

$\delta_{r-1}(H)\geq\frac{n}{(r-1)t+1}~{},$

then $H$ has a $t$-shallow hitting edge set.

###### Proof.

Let $k=(r-1)t+1$. First of all, observe that $n\geq r$ as $\delta_{r-1}(H)=0$
for $1\leq n<r$, contradicting the assumption $\delta_{r-1}(H)\geq n/k>0$. Let
$M\subseteq E$ be a $t$-shallow edge set of $H$. For $i=0,1,\dots,t$, let
$n_{i}(M)$ be the number of vertices $v\in V$ with
$\operatorname{deg}_{M}(v)=i$. We define $M\subseteq E$ to be a $t$-shallow
edge set that minimizes $n_{0}(M)$ on condition that each edge $e\in M$
contains at most one vertex $v\in e$ with $\operatorname{deg}_{M}(v)\geq 2$,
i.e., $|\\{v\in e\mid\operatorname{deg}_{M}(v)\geq 2\\}|\leq 1$ for all $e\in
M$. Moreover, we set $n_{i}=n_{i}(M)$ for all $i=0,1,\dots,t$ and $M$ as
defined.

######  Claim .

If $n_{0}>0$ then $n_{t}<\left\lceil n/k\right\rceil$.

  * Proof of Claim.

Assume that $n_{t}\geq\lceil n/k\rceil$. Each vertex of degree $t$ in $M$ has
$(r-1)t$ neighbors of degree $1$ in $M$, all of them distinct. Thus,
$n_{1}\geq(r-1)tn_{t}$ and

$n\geq n_{0}+n_{1}+n_{t}>((r-1)t+1)n_{t}\geq k\lceil n/k\rceil\geq n~{},$

a contradiction. ∎

######  Claim .

$n_{0}\leq r-2$.

  * Proof of Claim.

Assume that $n_{0}\geq r-1$. Let $\hat{e}$ be an $(r-1)$-set of vertices that
is not covered by $M$. By Claim 4.1 it holds that $n_{t}<\lceil n/k\rceil$.
Since $\delta_{r-1}(H)\geq\lceil n/k\rceil$, there exists a vertex $v\in
N_{r-1}(\hat{e})$ with $\operatorname{deg}_{M}(v)<t$. We define
$e=\hat{e}\cup\\{v\\}$ and distinguish four cases.

First, assume that $v$ is not covered by $M$. Then, $M^{\prime}=M\cup\\{e\\}$
is a $t$-shallow edge set with $n_{0}(M^{\prime})<n_{0}(M)$ and each edge
$e^{\prime}\in M^{\prime}$ still has at most one vertex $v^{\prime}\in
e^{\prime}$ of degree at least two, a contradiction.

Secondly, assume that $\operatorname{deg}_{M}(v)=1$ and _the_ edge
$e^{\prime}\in M$ incident to $v$ has no vertex of degree at least two in $M$.
As in the first case, $M^{\prime}=M\cup\\{e\\}$ leads to the desired
contradiction.

Thirdly, assume that $\operatorname{deg}_{M}(v)=1$ and _the_ edge
$e^{\prime}\in M$ incident to $v$ has a vertex $v^{\prime}$ of degree at least
two in $M$. Then, define $M^{\prime}=(M\cup\\{e\\})-\\{e^{\prime}\\}$. Then,
$V(M^{\prime})=(V(M)-V(e^{\prime}))\cup V(e)\cup\\{v^{\prime}\\}$ since
$v^{\prime}$ has degree at least one in $M^{\prime}$. Thus,
$|V(M^{\prime})|=|V(M)|+1$ and $n_{0}(M^{\prime})<n_{0}(M)$. As we deleted the
edge $e^{\prime}$, every edge in $M^{\prime}$ still has at most one vertex of
degree at least two in $M^{\prime}$. This is the desired contradiction.

It remains the case that $\operatorname{deg}_{M}(v)\geq 2$. We define
$M^{\prime}=M\cup\\{e\\}$. It clearly holds that $n_{0}(M^{\prime})<n_{0}(M)$
and $M^{\prime}$ is $t$-shallow. The edge $e$ has exactly one vertex of degree
at least two in $M^{\prime}$. Moreover, for each edge $e^{\prime}\in M$ that
is incident to $e$ it holds that $e\cap e^{\prime}=\\{v\\}$. Therefore, each
edge $e^{\prime}\in M^{\prime}$ has at most one vertex of degree at least two.
∎

We are now able to prove the theorem. If $n_{0}=0$, we are done. Hence, assume
that $n_{0}>0$. By Claim 4.1 we have $n_{t}<\lceil n/k\rceil$ and by Claim 4.1
we have $n_{0}\leq r-2$. We build an $(r-1)$-set $\hat{e}$ of vertices of
degree less than $t$ that contains all vertices that are not covered by $M$.
This set $\hat{e}$ exists since $n\geq r$ and therefore
$n-n_{t}>(k-1)n/k=(r-1)tn/k\geq r-1$ for $t\geq 1$. Since $n_{t}<\lceil
n/k\rceil$ and $\delta_{r-1}(H)\geq\lceil n/k\rceil$, there is a vertex $v\in
N_{r-1}(\hat{e})$ with $\operatorname{deg}_{M}(v)<t$. We define
$e=\hat{e}\cup\\{v\\}$ and $M^{\prime}=M\cup\\{e\\}$. Then, $M^{\prime}$ is a
$t$-shallow hitting edge set. ∎

###  4.2 Uniform partite hypergraphs

Now, let us consider $r$-uniform $r$-partite hypergraphs. Recall that for
$r=2$ these are exactly the bipartite graphs. It is well-known that every
bipartite graph with parts of size $n$ has a perfect matching if
$\operatorname{deg}(v)\geq n/2$ for all vertices $v$. The definition of the
minimum degree of a bipartite graph is extendable to $r$-uniform $r$-partite
hypergraphs in the following way, see for example [19] and [1]. Let
$H=(V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an $r$-uniform $r$-partite
hypergraph. We say that a set $\hat{e}\subseteq V$ of vertices of $H$ is
_legal_ if $|\hat{e}\cap V_{i}|\leq 1$ for all parts $V_{i}$ of $H$. If
$\hat{e}\subseteq V$ is a set of vertices of $H$ with $|\hat{e}|=r-1$, the
_neighborhood_ $N_{r-1}(\hat{e})$ of $\hat{e}$ is the set of all vertices $v$
such that $\hat{e}\cup\\{v\\}$ is an edge in $H$. Given an $r$-uniform
$r$-partite hypergraph $H$, we define the _minimum degree_
$\delta^{\prime}_{r-1}(H)$ to be the minimum of $|N_{r-1}(\hat{e})|$ over all
legal sets $\hat{e}$ of vertices in $H$ with $|\hat{e}|=r-1$. The minimum
degree $\delta^{\prime}_{r-1}(H)$ is also called _minimum co-degree_ , but
observe the important difference between $\delta^{\prime}_{r-1}(H)$ for
$r$-uniform $r$-partite hypergraphs $H$ considered here and $\delta_{r-1}(H)$
for $r$-uniform hypergraphs $H$ from Section 4.1.

Kühn and Osthus [19] proved a sufficient bound on $\delta^{\prime}_{r-1}(H)$
for the existence of perfect matchings in $r$-uniform $r$-partite hypergraphs.
This bound was improved in [1] as stated below.

######  Theorem 4.4 (Aharoni, Georgakopoulos and Sprüssel [1]).

Let $r\geq 2$ and let $H=(V=V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an
$r$-uniform $r$-partite hypergraph with parts of size $n$ such that for every
legal $(r-1)$-set $\hat{e}$ contained in $V\setminus V_{1}$ we have
$|N_{r-1}(\hat{e})|>n/2$ and for every legal $(r-1)$-set $\hat{f}$ contained
in $V\setminus V_{r}$ we have $|N_{r-1}(\hat{f})|\geq n/2$. Then there exists
a perfect matching in $H$.

The upper bound in Theorem 4.4 is tight up to the condition
$|N_{r-1}(\hat{e})|>n/2$ for every legal $(r-1)$-set $\hat{e}$ contained in
$V\setminus V_{1}$. It is not known whether this condition can be replaced by
$|N_{r-1}(\hat{e})|\geq n/2$ for every legal $(r-1)$-set $\hat{e}$. On the
other hand, there exist $r$-uniform $r$-partite hypergraphs $H$ with
$\delta^{\prime}_{r-1}(H)\geq n/2-1$ that have no perfect matching, due to a
construction in [19], which shows that the minimum degree condition in Theorem
4.4 is essentially tight.

In this section, we seek to extend these results to $t$-shallow hitting edge
sets in $r$-uniform $r$-partite hypergraphs $H$ with parts of equal sizes and
large minimum degree $\delta^{\prime}_{r-1}(H)$. For a start, we show a
sufficient condition for the existence of $t$-shallow hitting edge sets in
bipartite graphs (that is, $2$-uniform $2$-partite hypergraphs) of large
minimum degree and show that our required lower bound on $\delta_{1}(H)$ is
tight. Afterwards, we extend this to $r$-uniform $r$-partite hypergraphs.

######  Theorem 4.5 (Berge and Las Vergnas [4]).

Let $G=(A\dot{\cup}B,E)$ be a bipartite graph and $t$ be a positive integer.
Then, $G$ has a $t$-shallow hitting edge set if and only if $|X|\leq t|N(X)|$
for all sets $X\subseteq A$ and $X\subseteq B$.

######  Theorem 4.6.

Let $G=(A\dot{\cup}B,E)$ be a bipartite graph with $|A|\leq|B|\leq t|A|$. Let
$\delta_{A}$ respectively $\delta_{B}$ be the minimum degree of the vertices
in $A$ respectively $B$. If $t\delta_{A}+\delta_{B}\geq|A|$ and
$\delta_{A}+t\delta_{B}\geq|B|$ then there exists a $t$-shallow hitting edge
set.

###### Proof.

By Theorem 4.5, we have to show that $|X|\leq t|N(X)|$ holds for all sets
$X\subseteq A$ and all sets $X\subseteq B$.

We show that every set $X\subseteq A$ satisfies $|X|\leq t|N(X)|$. First,
assume that $1\leq|X|\leq t\delta_{A}$. Since every vertex in $X$ has at least
$\delta_{A}$ neighbors, we have $|N(X)|\geq\delta_{A}$ and thus $|X|\leq
t|N(X)|$. Now assume that $|X|>t\delta_{A}$. It follows that $|A\setminus
X|<|A|-t\delta_{A}\leq\delta_{B}$. Since every vertex in $B$ has at least
$\delta_{B}$ neighbors in $A$, it must have a neighbor in $X$. Thus, $N(X)=B$
and $t|N(X)|=t|B|\geq t|A|\geq|X|$.

Now, we show that every set $X\subseteq B$ satisfies $|X|\leq t|N(X)|$. First,
assume that $1\leq|X|\leq t\delta_{B}$. Since every vertex in $X$ has at least
$\delta_{B}$ neighbors, we have $|N(X)|\geq\delta_{B}$ and thus $|X|\leq
t|N(X)|$. Now assume that $|X|>t\delta_{B}$. It follows that $|B\setminus
X|<|B|-t\delta_{B}\leq\delta_{A}$. Since every vertex in $A$ has at least
$\delta_{A}$ neighbors in $A$, it must have a neighbor in $X$. Thus, $N(X)=A$
and $t|N(X)|=t|A|\geq|B|\geq|X|$. ∎

As a special case of Theorem 4.6, assume that $|A|=|B|=n$. It follows that if
$G$ has minimum degree $\delta(G)\geq n/(t+1)$ then $G$ has a $t$-shallow
hitting edge set. Indeed,

$t\delta_{A}+\delta_{B}\geq\frac{tn}{t+1}+\frac{n}{t+1}=n=|A|$

and

$\delta_{A}+t\delta_{B}\geq\frac{n}{t+1}+\frac{tn}{t+1}=n=|B|~{}.$

To see that the condition $\delta(G)\geq n/(t+1)$ is tight, let
$G^{\prime}=(A\dot{\cup}B,E)$ be a bipartite graph with parts of size
$|A|=|B|=n$ such that $t+1$ divides $n-1$. Let $A=A_{1}\dot{\cup}A_{2}$ and
$B=B_{1}\dot{\cup}B_{2}$ where $|A_{1}|=|B_{2}|=(n-1)/(t+1)$ and
$|A_{2}|=|B_{1}|=(nt+1)/(t+1)$ and note that that $|A|=|B|=n$. The edges of
$G^{\prime}$ are exactly the pairs $\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$
with $a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2}$. The graph
$G^{\prime}$ has minimum degree $\delta(G^{\prime})=(n-1)/(t+1)\geq n/(t+1)-1$
but does not contain a $t$-shallow hitting edge set as

$t|N(B_{1})|=t|A_{1}|=t\cdot\frac{n-1}{t+1}=\frac{tn+1}{t+1}-1=|B_{1}|-1<|B_{1}|~{}.$

Now, let us turn to $t$-shallow hitting edge sets in $r$-uniform $r$-partite
hypergraphs for $r>2$. By extending a construction from [19], we obtain the
following construction of a hypergraph $H$ with large minimum degree
$\delta^{\prime}_{r-1}(H)$ but without a $t$-shallow hitting edge set.

######  Theorem 4.7.

For all positive integers $r\geq 2$, $t\geq 2$ and $n$ there exists an
$r$-uniform $r$-partite hypergraph $H$ with parts of size $n$ and

$\delta^{\prime}_{r-1}(H)\geq\frac{n}{(r-1)t+1}-1$

that has no $t$-shallow hitting edge set.

###### Proof.

Let $\delta^{\prime}=n/((r-1)t+1)-1$. We define the $r$-partite $r$-uniform
hypergraph $H=(V_{1}\dot{\cup}V_{2}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ with
$|V_{i}|=n$ for all $i=1,2,\dots,r$. Let $V^{\prime}_{i}$ be a subset of
$V_{i}$ of size $|V^{\prime}_{i}|=\lceil\delta^{\prime}\rceil$, for
$i=1,2,\dots,r$. Note that $|V^{\prime}_{1}\cup V^{\prime}_{2}\cup\cdots\cup
V^{\prime}_{r}|<r(\delta^{\prime}+1)$. We define that
$e=\\{v_{1},v_{2},\dots,v_{r}\\}$ is an edge in $H$ if and only if $v_{1}\in
V_{1},v_{2}\in V_{2},\dots,v_{r}\in V_{r}$ and there is at least one $v_{i}$
with $v_{i}\in V^{\prime}_{i}$. Clearly, $H$ has minimum degree
$\delta^{\prime}_{r-1}(H)\geq\delta^{\prime}$. Assume, for contradiction, that
there exists a $t$-shallow hitting edge set $M$ of $H$. Then,

$|M|\leq t|V^{\prime}_{1}\cup V^{\prime}_{2}\cup\cdots\cup
V^{\prime}_{r}|<tr(\delta^{\prime}+1)$

since every vertex in $V^{\prime}_{1}\cup V^{\prime}_{2}\cup\cdots\cup
V^{\prime}_{r}$ is covered at most $t$ times. On the other hand,

$\begin{split}|M|&\geq\frac{1}{r-1}\left|(V_{1}\setminus
V^{\prime}_{1})\cup(V_{2}\setminus
V^{\prime}_{2})\cup\cdots\cup(V_{r}\setminus
V^{\prime}_{r})\right|>\frac{rn-r(\delta^{\prime}+1)}{r-1}\\\
&=\frac{rnt}{(r-1)t+1}=tr(\delta^{\prime}+1)\end{split}$

since every vertex in $V_{i}\setminus V^{\prime}_{i}$ is covered at least once
and at most $r-1$ vertices of $(V_{1}\setminus
V^{\prime}_{1})\cup\cdots\cup(V_{r}\setminus V^{\prime}_{r})$ are covered by
the same edge in $M$. Thus, $tr(\delta^{\prime}+1)<|M|<tr(\delta^{\prime}+1)$
is the desired contradiction. ∎

To obtain a condition on $\delta^{\prime}_{r-1}(H)$ that is sufficient for the
existence of $t$-shallow hitting edge sets, we first state a theorem from
[19]. It says that if we relax the condition $\delta^{\prime}_{r-1}(H)>n/2$ to
$\delta^{\prime}_{r-1}(H)\geq n/r$, then there exists an almost perfect
matching, i.e., a matching that covers all but at most $r-2$ vertices from
each part of $H$. In [19] it is shown that this result is tight as the minimum
degree condition $\delta^{\prime}_{r-1}(H)\geq n/r$ cannot be reduced.

######  Theorem 4.8 (Kühn and Osthus [19]).

Let $H$ be an $r$-uniform $r$-partite hypergraph with parts of size $n$ and
$\delta^{\prime}_{r-1}(H)\geq n/r$. Then $H$ has a matching that covers all
but at most $r-2$ vertices in each part of $H$.

As mentioned before, we seek to generalize Theorem 4.4 to $t$-shallow hitting
edge sets (cf. Theorem 4.9 below). To this end, we first show in Lemma 4.2
below a generalization of Theorem 4.8 to $t$-shallow edge sets that are not
necessarily hitting but cover almost all vertices of each part. To show Lemma
4.2, we consider any $r$-uniform $r$-partite hypergraph $H$ with large minimum
degree $\delta^{\prime}_{r-1}(H)$ and a $t$-shallow edge set $M$ satisfying
certain properties, leaving as few vertices as possible uncovered. We then
deduce properties of such a hypergraph $H$ (cf. Lemma 4.2 below) and show that
these lead to a contradiction in Lemma 4.2. Using Lemma 4.2 and raising the
minimum degree condition by $1$, we can show that there exists a $t$-shallow
hitting edge set in hypergraphs with large minimum degree
$\delta^{\prime}_{r-1}(H)$. In the first step, we show some properties of
$t$-shallow hitting edge sets in $r$-uniform $r$-partite hypergraphs.

######  Lemma .

Let $r\geq 2$ and $t\geq 2$ be positive integers and
$H=(V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an $r$-uniform $r$-partite
hypergraph with parts of size $n$. Let $M$ be a $t$-shallow edge set that
satisfies the following properties. Here, let $n_{s,i}$ be the number of
vertices $v\in V_{i}$ with $\operatorname{deg}_{M}(v)=s$.

  1. (1)

There exists a non-negative integer $n_{0}$ with
$n_{0,1}=n_{0,2}=\cdots=n_{0,r}=n_{0}$.

  2. (2)

$|M|\leq\left\lceil n/k\right\rceil(t-1)+n-n_{0}$.

Then, with $k=(r-1)t+1$, all of the following holds.

  1. (A)

$n_{t,i}\leq\lceil n/k\rceil$ for all $i=1,2,\dots,r$.

  2. (B)

If there exists a vertex $v\in V_{i}$ with $2\leq\operatorname{deg}_{M}(v)<t$,
then $n_{t,i}\leq\lceil n/k\rceil-1$.

  3. (C)

If $|M|<\lceil n/k\rceil(t-1)+n-n_{0}$, then $n_{t,i}\leq\lceil n/k\rceil-1$
for all $i=1,2,\dots,r$.

  4. (D)

If $|M|=\lceil n/k\rceil(t-1)+n-n_{0}$ and $|\\{v\in
e\mid\operatorname{deg}_{M}(v)\geq 2\\}|\leq 1$ for all $e\in M$, then
$n_{t,i}=\lceil n/k\rceil$ for all $i=1,2,\dots,r$.

###### Proof.

  1. (A)

For all $i=1,2,\dots,r$, there exist $n-n_{0}-n_{t,i}$ vertices in $V_{i}$
that are covered at least once by $M$ but less than $t$ times. Thus, $|M|\geq
tn_{t,i}+(n-n_{0}-n_{t,i})=(t-1)n_{t,i}+n-n_{0}$. By comparing this inequality
with Property (2), we get $n_{t,i}\leq\lceil n/k\rceil$.

  2. (B)

Using the same argument, we have $|M|\geq
tn_{t,i}+(n-n_{0}-n_{t,i})+1=(t-1)n_{t,i}+n-n_{0}+1$. By comparing this
inequality with Property (2), we get $n_{t,i}\leq\lceil
n/k\rceil-1/(t-1)<\lceil n/k\rceil$ and thus $n_{t,i}\leq\lceil n/k\rceil-1$.

  3. (C)

Using the same argument, we have $|M|\geq(t-1)n_{t,i}+n-n_{0}$. Since
$|M|<\lceil n/k\rceil(t-1)+n-n_{0}$ it holds that $n_{t,i}<\lceil n/k\rceil$
and thus $n_{t,i}\leq\lceil n/k\rceil-1$.

  4. (D)

Let $n_{s}:=n_{s,i}$ for all $s=1,2,\dots,t$ and some arbitrary
$i\in\\{1,2,\dots,r\\}$, and let $n_{\geq 2}=n_{2}+n_{3}+\cdots+n_{t}$. Our
first goal is to upper-bound $n_{1}$ in the general case $n_{t}\leq\lceil
n/k\rceil$ and in the case $n_{t}\leq\lceil n/k\rceil-1$. For the general
case, we upper-bound the size of $M$ by $|M|\leq n_{1}+tn_{\geq
2}=(t-1)n_{\geq 2}+n-n_{0}$ and with $|M|=\lceil n/k\rceil(t-1)+n-n_{0}$ it
follows that $n_{\geq 2}\geq\lceil n/k\rceil$. Thus, we have
$n_{1}=n-n_{0}-n_{\geq 2}\leq n-n_{0}-\lceil n/k\rceil$.

In the next step, we show that if $n_{t}\leq\lceil n/k\rceil-1$ then $n_{\geq
2}\geq\lceil n/k\rceil+1$. First note that $t\geq 3$ since for $t=2$ it holds
that $\lceil n/k\rceil+n-n_{0}=|M|=n_{1}+2n_{2}=n-n_{0}+n_{2}<\lceil
n/k\rceil+n-n_{0}$, a contradiction. For $t\geq 3$, we have

$\begin{split}\left\lceil\frac{n}{k}\right\rceil(t-1)+n-n_{0}&=|M|=n-n_{0}+n_{2}+2n_{3}+\cdots+(t-1)n_{t}\\\
&\leq n-n_{0}+(t-2)(n_{2}+n_{3}+\cdots+n_{t-1})+(t-1)n_{t}\end{split}$

and thus

$(t-1)\left(\left\lceil\frac{n}{k}\right\rceil-
n_{t}\right)\leq(t-2)(n_{2}+n_{3}+\cdots+n_{t-1})~{}.$

It follows that

$n_{\geq 2}\geq n_{t}+\frac{t-1}{t-2}\left(\left\lceil\frac{n}{k}\right\rceil-
n_{t}\right)=\frac{1}{t-2}\left((t-1)\left\lceil\frac{n}{k}\right\rceil-
n_{t}\right)>\left\lceil\frac{n}{k}\right\rceil$

and therefore $n_{1}\leq n-n_{0}-\lceil n/k\rceil-1$ if $n_{t}\leq\lceil
n/k\rceil-1$.

Now, we prove the claim. Assume, for contradiction, that there exists a part
$V_{j}$ with $n_{t,j}\leq\lceil n/k\rceil-1$. Then, $n_{1,i}\leq
n-n_{0}-\lceil n/k\rceil$ for all $i=1,2,\dots,r$ and
$n_{1,j}=n-n_{0}-(n_{2,j}+n_{3,j}+\cdots+n_{t,j})\leq n-n_{0}-\lceil
n/k\rceil-1$ since $n_{t,j}\leq\lceil n/k\rceil-1$ and thus
$n_{2,j}+n_{3,j}+\cdots+n_{t,j}\geq\lceil n/k\rceil+1$. In the next step,
observe that

$(r-1)|M|\leq\sum_{i=1}^{r}n_{1,i}~{},$

since each edge in $M$ covers at least $(r-1)$ vertices that are covered once
by $M$. This follows since each edge $e\in M$ has at most one vertex $v\in e$
with $\operatorname{deg}_{M}(v)\geq 2$. We bound the $n_{1,i}$’s in the sum
and use $|M|=\lceil n/k\rceil(t-1)+n-n_{0}$ and obtain

$(r-1)\left(\left\lceil\frac{n}{k}\right\rceil(t-1)+n-n_{0}\right)\leq\sum_{i=1}^{r}n_{1,i}\leq
r\left(n-n_{0}-\left\lceil\frac{n}{k}\right\rceil\right)-1~{}.$

Simplifying this inequality and using $k=(r-1)t+1$ and we get

$\left\lceil\frac{n}{k}\right\rceil k+1\leq n-n_{0}~{},$

a contradiction since $\lceil n/k\rceil\cdot k\geq n$ and $n_{0}\geq 0$.∎

As the next step, we show some properties of $t$-shallow edge sets with
specific other properties that maximize the number of covered vertices. The
intuition for the next lemma is, if the hypergraph $H$ has large minimum
degree but no $t$-shallow edge set (with specific properties) that covers
almost all vertices of each part, then $H$ is not far from the hypergraph
constructed in Theorem 4.7. In the following, given a hypergraph $H=(V,E)$ and
a subset of edges $M\subseteq E$, we define $V(M)\subseteq V$ to be the union
of all edges in $M$.

######  Lemma .

Let $r\geq 2$ and $t\geq 2$ be positive integers and
$H=(V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an $r$-uniform $r$-partite
hypergraph with parts of size $n$ and minimum degree
$\delta^{\prime}_{r-1}(H)\geq\lceil n/k\rceil$ where $k=(r-1)t+1$. Let $M$ be
a $t$-shallow edge set that satisfies the following properties and maximizes
the number of covered vertices in $H$ with respect to these properties. Here,
let $n_{s,i}$ be the number of vertices $v\in V_{i}$ with
$\operatorname{deg}_{M}(v)=s$.

  1. (1)

There exists a non-negative integer $n_{0}$ such that
$n_{0,1}=n_{0,2}=\cdots=n_{0,r}=n_{0}$.

  2. (2)

$|M|\leq\left\lceil n/k\right\rceil(t-1)+n-n_{0}$.

If $n_{0}\geq r-1$ then each of the following holds.

  1. (E)

$N_{r-1}(\hat{e})\subseteq V(M)$ for each legal $(r-1)$-set $\hat{e}$ of
uncovered vertices of $H$.

  2. (F)

$|M|=\lceil n/k\rceil(t-1)+n-n_{0}$.

  3. (G)

For all edges $e\in M$ it holds that the number of vertices $v\in e$ that are
covered at least twice by $M$ is at most one, i.e., $|\\{v\in
e\mid\operatorname{deg}_{M}(v)\geq 2\\}|\leq 1$ for all edges $e\in M$.

###### Proof.

We define $U_{i}=V_{i}\setminus V(M)$ to be the set of all uncovered vertices
in $V_{i}$. Moreover, we define $U=U_{1}\cup U_{2}\cup\cdots\cup U_{r}$.

  1. (E)

Let $\hat{e}$ be a legal $(r-1)$-set of uncovered vertices, that is
$\hat{e}\subseteq U$. Assume that there exists a vertex $v\in U\cap
N_{r-1}(\hat{e})$. Let $e=\hat{e}\cup\\{v\\}$. Then, the edge set
$M^{\prime}=M\cup\\{e\\}$ is $t$-shallow. Let $U^{\prime}_{i}=V_{i}\setminus
V(M^{\prime})$ be the set of vertices of $V_{i}$ that are not covered by
$M^{\prime}$. The edge set $M^{\prime}$ satisfies Property (1) with
$n^{\prime}_{0}=|U^{\prime}_{1}|=\cdots=|U^{\prime}_{r}|=n_{0}-1$. Moreover,
$M^{\prime}$ satisfies Property (2) since
$|M^{\prime}|=|M|+1=|M|+n_{0}-n^{\prime}_{0}\leq\lceil
n/k\rceil(t-1)+n-n^{\prime}_{0}$. Since $M^{\prime}$ covers more vertices than
$M$ and satisfies all properties, we have the desired contradiction.

  2. (F)

In the next step, we show that $|M|=\lceil n/k\rceil(t-1)+n-n_{0}$. Assume,
for contradiction, that $|M|<\lceil n/k\rceil(t-1)+n-n_{0}$. By Lemma 4.2
Result (C), we have $n_{t,i}\leq\lceil n/k\rceil-1$ for all parts $V_{i}$.
Since $\delta^{\prime}_{r-1}(H)\geq\lceil n/k\rceil$ and by Result (E) of this
lemma, each legal $(r-1)$-set $\hat{e}$ of vertices has a neighboring vertex
that is covered at least once but less than $t$ times. For $i=1,2,\dots,r$, we
build an $(r-1)$-set $\hat{e}_{i}$ of vertices of $U\setminus U_{i}$, such
that no two sets $\hat{e}_{i}$ contain the same vertex. This is possible since
$n_{0}=|U_{i}|\geq r-1$ for all $i=1,2,\dots,r$. Let $v_{i}\in
N_{r-1}(\hat{e}_{i})$ be a vertex with $1\leq\operatorname{deg}_{M}(v_{i})<t$.
Observe that $v_{i}\in V_{i}$ for all $i=1,2,\dots,r$. Define
$e_{i}=\hat{e}_{i}\cup\\{v_{i}\\}$. We claim that

$M^{\prime}=M\cup\\{e_{i}\mid i=1,2,\dots,r\\}$

satisfies Property (1) and Property (2). Clearly, $M^{\prime}$ is $t$-shallow.
Denote by $U^{\prime}_{i}=V_{i}\setminus V(M^{\prime})$ the set of vertices in
$V_{i}$ that are not covered by $M^{\prime}$. Then,
$|U^{\prime}_{i}|=|U_{i}|-(r-1)=n_{0}-r+1$ since the edges in $\\{e_{j}\mid
j\neq i,j=1,2,\dots,r\\}$ cover $(r-1)$ vertices of $U_{i}$, but $e_{i}\cap
U_{i}=\emptyset$. To show Property (2), note that $|M^{\prime}|=|M|+r$ and
$n^{\prime}_{0}:=|U^{\prime}_{1}|=\cdots=|U^{\prime}_{r}|=n_{0}-r+1$. Thus,
$|M^{\prime}|=|M|+n_{0}-n^{\prime}_{0}+1\leq\lceil
n/k\rceil(t-1)+n-n^{\prime}_{0}$. Since $M^{\prime}$ covers more vertices than
$M$ and satisfies all properties, we have the desired contradiction.

  3. (G)

We show that there exists no edge $e\in M$ such that at least two vertices of
$e$ are covered at least twice by $M$. Assume that there exists an edge
$e=\\{u_{1},u_{2},\dots,u_{r}\\}\in M$, with $u_{i}\in V_{i}$ for
$i=1,2,\dots,r$, such that at least two vertices of $e$ are covered at least
twice by $M$. Denote by $I\subseteq\\{1,2,\dots,r\\}$ the set of indices such
that $\\{u_{i}\mid i\in I\\}$ is the set of vertices of $e$ that are covered
at least twice by $M$. Then, $|I|\geq 2$. For each $i\in I$, we build a legal
$(r-1)$-set $\hat{e}_{i}$ of vertices of $U\setminus U_{i}$, such that no two
sets $\hat{e}_{i}$ contain the same vertex. This is possible since
$n_{0}=|U_{i}|\geq r-1$ for all $i=1,2,\dots,r$ and $|I|\leq r$. By Result (A)
of this lemma, $N_{r-1}(\hat{e}_{i})\subseteq V_{i}\setminus U_{i}$. Denote by
$W_{i}\subseteq V_{i}$ the set of vertices in $V_{i}$ that are covered exactly
$t$ times by $M$. By Result (A) of Lemma 4.2, we have $|W_{i}|\leq\lceil
n/k\rceil$ if $u_{i}\in W_{i}$ and, by Result (B) of Lemma 4.2,
$|W_{i}|\leq\lceil n/k\rceil-1$ if $u_{i}\notin W_{i}$, for $i\in I$. Since
$|N_{r-1}(\hat{e}_{i})|\geq\lceil n/k\rceil$, there exists a vertex $v_{i}\in
N_{r-1}(\hat{e}_{i})$ with $v_{i}\in(V_{i}\setminus(U_{i}\cup
W_{i}))\cup\\{u_{i}\\}$. That is, $1\leq\operatorname{deg}_{M}(v_{i})<t$ or
$v_{i}=u_{i}$. Define $e_{i}=\hat{e}_{i}\cup\\{v_{i}\\}$. We claim that

$M^{\prime}=(M\setminus\\{e\\})\cup\\{e_{i}\mid i\in I\\}$

satisfies Property (1) and Property (2). Clearly, $M^{\prime}$ is $t$-shallow.
Since $|I|\geq 2$ it holds that $M^{\prime}$ covers more vertices than $M$.
Denote $U^{\prime}_{i}=V_{i}\setminus V(M^{\prime})$ to be the set of vertices
in $V_{i}$ that are not covered by $M^{\prime}$. If $i\in I$, then there exist
$|I|-1$ edges in $\\{e_{j}\mid j\in I\\}$ that cover distinct vertices of
$U_{i}$. Moreover, the edge $e_{i}$ does not cover a vertex of $U_{i}$. Thus,
$|U^{\prime}_{i}|=|U_{i}|-(|I|-1)=n_{0}-|I|+1$. If $i\notin I$, then all $|I|$
edges in $\\{e_{j}\mid j\in I\\}$ cover a vertex in $U_{i}$. But the vertex
$v\in e\cap V_{i}$ is covered exactly once by $M$ (by the definition of $I$)
and thus, $v$ is not covered by $M^{\prime}$. Then,
$|U^{\prime}_{i}|=|U_{i}|-|I|+1=n_{0}-|I|+1$. To prove Property (2), note that
$|M^{\prime}|=|M|+|I|-1$ and
$n^{\prime}_{0}:=|U^{\prime}_{1}|=\cdots=|U^{\prime}_{r}|=n_{0}-|I|+1$. Thus,
$|M^{\prime}|=|M|+(n_{0}-n^{\prime}_{0})\leq\lceil
n/k\rceil(t-1)+n-n_{0}+n_{0}-n^{\prime}_{0}=\lceil
n/k\rceil(t-1)+n-n^{\prime}_{0}$.∎

We can now prove that every $r$-uniform $r$-partite hypergraph $H$ with
minimum degree $\delta^{\prime}_{r-1}(H)\geq n/((r-1)t+1)$ has a $t$-shallow
edge set that covers all but at most $r-2$ vertices of each part. For $t=1$,
the result is proven by Theorem 4.8, so we consider the case $t\geq 2$. As we
need these later to deduce Theorem 4.9, we show the following lemma together
with some additional properties of the $t$-shallow edge set.

######  Lemma .

Let $r\geq 2$, $t\geq 2$ and $n$ be positive integers and
$H=(V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an $r$-uniform $r$-partite
hypergraph with parts of size $n$ and minimum degree
$\delta^{\prime}_{r-1}(H)\geq\lceil n/k\rceil$ where $k=(r-1)t+1$. Then, there
exists a $t$-shallow edge set $M$ with the following properties. Here, let
$n_{s,i}$ be the number of vertices $v\in V_{i}$ with
$\operatorname{deg}_{M}(v)=s$.

  1. (1)

There exists a non-negative integer $n_{0}$ with
$n_{0,1}=n_{0,2}=\cdots=n_{0,r}=n_{0}$.

  2. (2)

$|M|\leq\left\lceil n/k\right\rceil(t-1)+n-n_{0}$.

  3. (3)

$M$ covers all but at most $r-2$ vertices of each part of $H$, i.e.,
$n_{0}\leq r-2$.

###### Proof.

Let $M$ be a $t$-shallow edge set that satisfies Property (1) and Property (2)
and maximizes the number of covered vertices with respect to these both
properties. Assume, for contradiction, that $n_{0}\geq r-1$. Then, we can
apply Lemma 4.2. By Result (F) of Lemma 4.2, we have $|M|=\lceil
n/k\rceil(t-1)+n-n_{0}$. By Result (G) of Lemma 4.2, every edge $e\in M$ has
at most one vertex $v\in e$ with $\operatorname{deg}_{M}(v)\geq 2$. Then, by
Result (D) of Lemma 4.2, we have $n_{t,i}=\lceil n/k\rceil$ for all
$i=1,2,\dots,r$. We count the number of vertices in the part $V_{1}$. Note
that $n_{t,1}=\lceil n/k\rceil$. Since $n_{t,i}=\lceil n/k\rceil$ for all
$i=2,3,\dots,r$ and every edge in $M$ has at most one vertex $v$ with
$\operatorname{deg}_{M}(v)\geq 2$, we have $n_{1,1}\geq t(r-1)\lceil
n/k\rceil$. Thus,

$n\geq n_{0}+n_{1,1}+n_{t,1}\geq
n_{0}+t(r-1)\left\lceil\frac{n}{k}\right\rceil+\left\lceil\frac{n}{k}\right\rceil\geq
n_{0}+k\left\lceil\frac{n}{k}\right\rceil\geq n_{0}+n~{},$

a contradiction since we assumed $n_{0}\geq r-1>0$. ∎

We are now able to prove that every $r$-uniform $r$-partite hypergraph with
parts of size $n$ and minimum degree $\delta^{\prime}_{r-1}(H)\geq
1+n/((r-1)t+1)$ has a $t$-shallow hitting edge set. This condition is tight up
to the additive constant $1$, as shown in Theorem 4.7.

######  Theorem 4.9.

Let $r\geq 2$ and $t\geq 2$ be positive integers and
$H=(V_{1}\dot{\cup}\cdots\dot{\cup}V_{r},E)$ be an $r$-uniform $r$-partite
hypergraph with parts of size $n$ and minimum degree

$\delta^{\prime}_{r-1}(H)\geq\left\lceil\frac{n}{(r-1)t+1}\right\rceil+1~{}.$

Then, there exists a $t$-shallow hitting edge set in $H$.

###### Proof.

Let $k=(r-1)t+1$. By Lemma 4.2, there exists a $t$-shallow edge set $M$ that
satisfies Property (1), Property (2) and Property (3) of Lemma 4.2. Let $M$ be
such a $t$-shallow edge set that maximizes the number of covered vertices with
respect to all three properties. Let $U_{i}=V_{i}\setminus V(M)$ be the set of
uncovered vertices in $V_{i}$. Then, $|U_{1}|=\cdots=|U_{r}|=n_{0}$ for some
non-negative integer $n_{0}\leq r-2$, by Property (1) and Property (3).
Moreover, $|M|\leq\lceil n/k\rceil(t-1)+n-n_{0}$ by Property (2). Let
$n_{s,i}$ be the number of vertices $v\in V_{i}$ with
$\operatorname{deg}_{M}(v)=s$. By Lemma 4.2 Result (A), we have
$n_{t,i}\leq\lceil n/k\rceil$ for all $i=1,2,\dots,r$. For $n_{0}=0$, there is
nothing to show. Therefore, assume $n_{0}>0$. We construct a $t$-shallow
hitting edge set $M^{\prime}$ by adding edges to $M$.

For each $i=1,2,\dots,n_{0}+1$, we build a legal $(r-1)$-set $\hat{e}_{i}$ of
vertices of $U\setminus U_{i}$, such that each vertex in $U_{1}\cup
U_{2}\cup\cdots\cup U_{n_{0}+1}$ is contained in exactly one $\hat{e}_{i}$ and
each vertex in $\hat{U}_{n_{0}+2}\cup\cdots\cup U_{r}$ is contained in at
least one and at most two $\hat{e}_{i}$’s. Note that
$N_{r-1}(\hat{e}_{i})\subseteq V_{i}\setminus U_{i}$, since otherwise we can
build a $t$-shallow edge set $M^{\prime}$ that covers more vertices and
satisfies all three properties of Lemma 4.2, a contradiction. Since
$\delta^{\prime}_{r-1}(H)\geq\lceil n/k\rceil+1$ and $n_{t,i}\leq\lceil
n/k\rceil$ for all $i=1,2,\dots,r$, there exists a vertex $v_{i}\in
N_{r-1}(\hat{e}_{i})$ that is covered at least once but less than $t$ times by
$M$. We define $e_{i}=\hat{e}_{i}\cup\\{v_{i}\\}$. Let
$M^{\prime}=M\cup\\{e_{i}\mid i=1,2,\dots,n_{0}+1\\}$. Then, $M^{\prime}$ is
$t$-shallow and covers all vertices of $H$. ∎

##  5 Conclusions

Open problems include all cases in which our bounds are not tight yet. The
most intriguing is to determine the least integer $t=t(r)$ for which every
regular $r$-uniform hypergraph admits a $t$-shallow hitting edge set. Our
results give that $t(r)\geq\lfloor\log_{2}(r+1)\rfloor$ and
$t(r)\leq\mathrm{e}r(1+o(1))$, where we can improve the upper bound to $c\ln
r(1+o(1))$ for $c\approx 4.31$ (i.e., nearly matching the lower bound) for the
special case of regular $r$-uniform hypergraphs of girth at least four.

Let us also mention that in the first author’s Master’s thesis [22] it is
shown that it is NP-complete to determine whether an $r$-uniform $r$-partite
regular hypergraph has a $t$-shallow hitting edge set, provided
$t\leq\frac{1}{2}\log_{2}(r)-O(\log\log r)$, i.e., only slightly below the
smallest value for $t$ for which such $t$-shallow hitting edge sets _always_
exist.

## References

  * [1] Ron Aharoni, Agelos Georgakopoulos, and Philipp Sprüssel.  Perfect matchings in $r$-partite $r$-graphs.  European J. Combin., 30(1):39–42, 2009.  doi:10.1016/j.ejc.2008.02.011.
  * [2] Ron Aharoni and Penny Haxell.  Hall’s theorem for hypergraphs.  Journal of Graph Theory, 35(2):83–88, 2000.  URL: https://doi.org/10.1002/1097-0118(200010)35:2%3C83::AID-JGT2%3E3.0.CO;2-V.
  * [3] Noga Alon and Joel H. Spencer.  The probabilistic method.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.  doi:10.1002/9780470277331.
  * [4] Claude Berge and Michel Las Vergnas.  On the existence of subgraphs with degree constraints.  Indagationes Mathematicae (Proceedings), 81(2):165–176, 1978.  doi:10.1016/1385-7258(78)90034-3.
  * [5] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.  doi:10.1109/FOCS54457.2022.00064.
  * [6] Charles J. Colbourn and Jeffrey H. Dinitz, editors.  Handbook of combinatorial designs.  Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, second edition, 2007.  doi:10.1201/9781420010541.
  * [7] Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vuskovic.  Perfect matchings in balanced hypergraphs.  Combinatorica, 16(3):325–329, 1996.  doi:10.1007/BF01261318.
  * [8] Gabriel Andrew Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, 3(1):69–81, 1952\.  doi:10.1112/plms/s3-2.1.69.
  * [9] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449––467, 1965.  doi:10.4153/CJM-1965-045-4.
  * [10] Paul Erdős and László Lovász.  Problems and results on 3-chromatic hypergraphs and some related questions.  In Infinite and finite sets, volume 10 of Colloquia Math Soc János Bolyai, pages 609–627, 1973.
  * [11] Philip Hall.  On representatives of subsets.  Journal of the London Mathematical Society, s1-10(1):26–30, 1935\.  doi:10.1112/jlms/s1-10.37.26.
  * [12] Penny E. Haxell.  A condition for matchability in hypergraphs.  Graphs and Combinatorics, 11(3):245–248, 1995.  doi:10.1007/BF01793010.
  * [13] Michael A. Henning and Anders Yeo.  Tight lower bounds on the size of a maximum matching in a regular graph.  Graphs and Combinatorics, 23(6):647–657, 2007.  doi:10.1007/s00373-007-0757-5.
  * [14] Andreas Huck and Eberhard Triesch.  Perfect matchings in balanced hypergraphs - A combinatorial approach.  Combinatorica, 22(3):409–416, 2002.  doi:10.1007/s004930200020.
  * [15] Richard M. Karp.  Reducibility among Combinatorial Problems, pages 85–103.  Springer US, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [16] Peter Keevash.  The existence of designs II.  arXiv preprint arXiv:1802.05900, 2018.  URL: https://arxiv.org/abs/1802.05900.
  * [17] Balázs Keszegh and Dömötör Pálvölgyi.  An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes.  Journal of Computational Geometry, 10(1):1–26, 2019.  doi:10.20382/jocg.v10i1a1.
  * [18] Alexandr V. Kostochka and Vojtech Rödl.  Constructions of sparse uniform hypergraphs with high chromatic number.  Random Structures & Algorithms, 36(1):46–56, 2010.  doi:10.1002/rsa.20293.
  * [19] Daniela Kühn and Deryk Osthus.  Matchings in hypergraphs of large minimum degree.  J. Graph Theory, 51(4):269–280, 2006.  doi:10.1002/jgt.20139.
  * [20] László Lovász.  The Factorization of Graphs. II.  Acta Mathematica Academiae Scientiarum Hungarica, 23(1–2):223–246, 1972.  doi:10.1007/BF01889919.
  * [21] Silvio Micali and Vijay V. Vazirani.  An $O(\sqrt{|V|}|E|)$ algorithm for finding maximum matching in general graphs.  In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17–27. IEEE Computer Society, 1980.  doi:10.1109/SFCS.1980.12.
  * [22] Tim Planken.  Shallow edge sets in hypergraphs.  Master’s thesis, Karlsruhe Institute of Technology, Karlsruhe, Germany, 2022.  URL: https://i11www.iti.kit.edu/_media/teaching/theses/ma-planken-22.pdf.
  * [23] Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi.  A dirac-type theorem for 3-uniform hypergraphs.  Combinatorics, Probability and Computing, 15(1-2):229–251, 2006\.  doi:10.1017/s0963548305007042.
  * [24] Vojtech Rödl, Andrzej Ruciński, and Endre Szemerédi.  Perfect matchings in uniform hypergraphs with large minimum degree.  European Journal of Combinatorics, 27(8):1333–1349, 2006.  doi:10.1016/j.ejc.2006.05.008.
  * [25] Vojtech Rödl, Andrzej Ruciński, and Endre Szemerédi.  Perfect matchings in large uniform hypergraphs with large minimum collective degree.  Journal of Combinatorial Theory, Series A, 116(3):613–636, 2009\.  doi:10.1016/j.jcta.2008.10.002.
  * [26] Joel Spencer.  Asymptotic lower bounds for Ramsey functions.  Discrete Mathematics, 20:69–76, 1977.  doi:10.1016/0012-365x(77)90044-9.
  * [27] William T. Tutte.  The factorization of locally finite graphs.  Canadian Journal of Mathematics, 2:44––49, 1950.  doi:10.4153/CJM-1950-005-2.
  * [28] Yi Zhao.  Recent advances on Dirac-type problems for hypergraphs.  Recent Trends in Combinatorics, pages 145–165, 2016.  doi:10.1007/978-3-319-24298-9_6.