Showing math.COShow all
2 papers · 1 filter
math.CO2026
A sharp bound on the integrality gap in the 3-set cover problem
Eli Berger, Ron Holzman
Given a hypergraph with edges of size at most 3, the 3-set cover problem asks to determine the minimum size of a family of edges which covers the vertex set. As the problem is NP-h…
math.CO2024
Triangle-free triple systems
Peter Frankl, Zoltán Füredi, Ido Goorevitch +2
There are four non-isomorphic configurations of triples that can form a triangle in a -uniform hypergraph. Forbidding different combinations of these four configurations, fiftee…