Fractional v. integral covers in hypergraphs of bounded edge size (Q1356038): Difference between revisions

The first author observed in [Extremal problems for finite sets, Bolyai Soc. Math. Stud. 3, 305-353 (1994; Zbl 0820.05050)] and [Random Struc. Algorithms 8, No. 2, 149-157 (1996; Zbl 0842.05066)] the fundamental results of \textit{V. Rödl} [Eur. J. Comb. 6, 69-78 (1985; Zbl 0565.05016)], \textit{P. Frankl} and \textit{V. Rödl} [Eur. J. Comb. 6, 317-326 (1985; Zbl 0624.05055)] and \textit{N. Pippenger} as giving asymptotic agreement of fractional and integral optima for matching and covering problems on hypergraphs of bounded edge size. In these results, the authors assume some local sparseness. In the present paper, relaxing such assumptions and using so-called hard-core distributions, the authors obtain the following very important theorem which generalizes all of the earlier work. A hypergraph \(H\) is a collection of subsets (edges) of some finite set \(V\) of vertices. If each of its edges contains at most \(k\) vertices, it is said to be \(k\)-bounded. The edge cover number, denoted by \(\rho(H)\), is the smallest size of edge covers of \(H\). A function \(t:H\to R^+\) is said to be a fractional edge cover if \(\sum_{x\in A\in H}t(A)\geq 1\) for all \(x\in V\). Define the total weight of \(t\) by \(t(H)=\sum_{A\in H}t(A)\). A function \(\overline t:2^V\to R^+\) is given by \(\overline t(A)=\sum_{A\subset B,\;B\in H}t(B)\) for \(A\subset V\), and for \(i\geq 2\), set \(\alpha_i(t)=\max_{W\in V,\;|W|=i}\overline t(W)\). Moreover, for \(X\subset V\), define \(t|_X:H\to R^+\) by \(t|_X(A)=\sum_{B\cap X=A,\;B\in H} t(B)\) for \(A\subset X\), \(|A|\geq 2\) and \(t|_X(A)=0\) for \(A\subset X\), \(|A|<2\). Denote by \(b(t)\) the largest \(b\) such that if \(X\subset V\) satisfies \(|X|\leq b\), then \(t|_X\in \text{MP} (2^V)\), where \(\text{MP}(2^V)\) is the matching polytope of \(2^V\). The main result of the present paper is the following: Let \(k\geq 2\) be fixed, \(H\) be a \(k\)-bounded hypergraph, and \(t:H\to R^+\) a fractional cover. Then \(\limsup\rho(H)/t(H)\leq 1\) as \(\alpha_3(t)\to 0\) and \(b(t)\to\infty\).