Invariant covers of multipartite hypergraphs

Abstract

We prove the following ``symmetric analogue'' of Lovász's estimate (1975): if an $r$-partite hypergraph of rank $r⩾2$ has a cover of cardinality $n<\infty$, then it admits a cover of cardinality at most $nr/2$, which is invariant with respect to all automorphisms preserving the parts. We obtain also symmetric analogues of generalisations of Lovász's estimate due to Aharoni, Holzman, and Krivelevich (1996).

5 pages. A Russian version of this paper is at http://halgebra.math.msu.su/staff/klyachko/papers.htm . V2: minor changes