Fractional v. integral covers in hypergraphs of bounded edge size (Q1356038): Difference between revisions
From MaRDI portal
Latest revision as of 13:02, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fractional v. integral covers in hypergraphs of bounded edge size |
scientific article |
Statements
Fractional v. integral covers in hypergraphs of bounded edge size (English)
0 references
28 January 1998
0 references
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\).
0 references
hypergraph
0 references
covering of graphs
0 references
matching of graphs
0 references
fractional covers of graphs
0 references
0 references