Name
Abstract | ||
|---|---|---|
Johnson and Lovász and Stein proved independently that any hypergraph satisfies τ≤(1+lnΔ)τ∗, where τ is the transversal number, τ∗ is its fractional version, and Δ denotes the maximum degree. We prove τf≤3.153τ∗max{lnΔ,f} for the f-fold transversal number τf. Similarly to Johnson, Lovász and Stein, we also show that this bound can be achieved non-probabilistically, using a greedy algorithm. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ejc.2017.08.001 | European Journal of Combinatorics |
DocType | Volume | ISSN |
Journal | 67 | 0195-6698 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marton Naszodi | 1 | 21 | 7.87 |
| Alexandr Polyanskii | 2 | 0 | 2.37 |