Name
Abstract | ||
|---|---|---|
Lov\'asz and Stein (independently) proved that any hypergraph satisfies $\tau\leq (1+\ln \Delta)\tau^{\ast}$, where $\tau$ is the transversal number, $\tau^{\ast}$ is its fractional version, and $\Delta$ denotes the maximum degree. We prove $\tau_f\leq 3.17\tau^{\ast}\max\{\ln \Delta, f\}$ for the $f$-fold transversal number $\tau_f$. Similarly to Lov\'asz and Stein, we also show that this bound can be achieved non-probabilistically, using a greedy algorithm. As a combinatorial application, we prove an estimate on how fast $\tau_f/f$ converges to $\tau^{\ast}$. As a geometric application, we obtain a bound on the minimal density of an $f$-fold covering of the $d$-dimensional space by translates of any convex body. |
Year | Venue | DocType |
|---|---|---|
2016 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1608.01292 | 0 | 0.34 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marton Naszodi | 1 | 21 | 7.87 |
| Alexandr Polyanskii | 2 | 0 | 0.34 |