Fractional v. integral covers in hypergraphs of bounded edge size
type: Item
instance of: scholarly article
title: Fractional v. integral covers in hypergraphs of bounded edge size
zbMATH Open document ID: 0884.05067
author: P. Mark Kayll
author: J. Kahn
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-01-28T00:00:00Z
review text: 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)…
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1016841
zbMATH Keywords: hypergraph
zbMATH Keywords: covering of graphs
zbMATH Keywords: matching of graphs
zbMATH Keywords: fractional covers of graphs
reviewed by: Toru Ishihara
MaRDI profile type: Publication
full work available at URL: jcta.1997.2761
OpenAlex ID: W2061632191
cites work: Extremal uncrowded hypergraphs
cites work: A dense infinite Sidon sequence
cites work: Q4004078
cites work: Nearly perfect matchings in regular simple hypergraphs
cites work: Percolation and the hard-core lattice gas model
cites work: Q3941433
cites work: Q3993087
cites work: Q3852212
cites work: Q4079613
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: On the combinatorial problems which I would most like to see solved
cites work: Q5734432
cites work: Q4074927
cites work: Near perfect coverings in graphs and hypergraphs
cites work: Matchings and covers in hypergraphs
cites work: More-than-nearly-perfect packings and partial designs
cites work: Theory of monomer-dimer systems
cites work: Q4326643
cites work: On a Problem of Erdos and Lovasz. II: n(r) = O(r)
cites work: Asymptotically good list-colorings
cites work: A linear programming perspective on the Frankl?R�dl?Pippenger theorem
cites work: Asymptotics of the chromatic index for multigraphs
cites work: Q4511485
cites work: A normal law for matchings
cites work: On the stochastic independence properties of hard-core distributions
cites work: Q4386088
cites work: On Brooks' Theorem for Sparse Graphs
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: A Lower Bound for Heilbronn'S Problem
cites work: Q5202862
cites work: Matching theory
cites work: Asymptotic behavior of the chromatic index for hypergraphs
cites work: Q4230353
cites work: On a packing and covering problem
cites work: Q4885222
cites work: Q3818127
cites work: Asymptotically good coverings
cites work: Asymptotic packing via a branching process
DOI: 10.1006/JCTA.1997.2761
Recommended article: A linear programming perspective on the Frankl?R�dl?Pippenger theorem
Recommended article: Optimal fractional matchings and covers in infinite hypergraphs: existence and duality
Recommended article: Partial covering of hypergraphs
Recommended article: On the number of copies of one hypergraph in another
Recommended article: Strong LP duality in weighted infinite bipartite graphs
Recommended article: Approximate Set Covering in Uniform Hypergraphs
Recommended article: Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
Recommended article: ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS
Recommended article: Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
Recommended article: Fractional matchings and covers in infinite hypergraphs
description: scientific article; zbMATH DE number 1016841