Shallow Hitting Edge Sets in Uniform Hypergraphs

MaRDI QIDQ6443400zbMATH OpenFDO

Authors Tim Planken, Torsten Ueckerdt

Publication date 7 July 2023

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 $delt{a}_{r-1}(H)geqn/((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{\text{'}}_{r-1}(H)geqn/((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.

This page was built for publication: Shallow Hitting Edge Sets in Uniform Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443400)