2023/07/07 by Planken, Tim, Ueckerdt, Torsten · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.05757
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 Ω(nt/r1+1/t). Every r-uniform hypergraph with n vertices and minimum degree δr-1(H) ≥ 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 δ'r-1(H) ≥ 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.