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

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/jcta.1997.2761 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2061632191 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Extremal uncrowded hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A dense infinite Sidon sequence / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4004078 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nearly perfect matchings in regular simple hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Percolation and the hard-core lattice gas model / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3941433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3993087 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3852212 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4079613 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum matching and a polyhedron with 0,1-vertices / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the combinatorial problems which I would most like to see solved / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5734432 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4074927 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Near perfect coverings in graphs and hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Matchings and covers in hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: More-than-nearly-perfect packings and partial designs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Theory of monomer-dimer systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4326643 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Problem of Erdos and Lovasz. II: n(r) = O(r) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotically good list-colorings / rank
 
Normal rank
Property / cites work
 
Property / cites work: A linear programming perspective on the Frankl?R�dl?Pippenger theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotics of the chromatic index for multigraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4511485 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A normal law for matchings / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the stochastic independence properties of hard-core distributions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4386088 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Brooks' Theorem for Sparse Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Ramsey number <i>R</i>(3, <i>t</i>) has order of magnitude <i>t</i><sup>2</sup>/log <i>t</i> / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Lower Bound for Heilbronn'S Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5202862 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Matching theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotic behavior of the chromatic index for hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4230353 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a packing and covering problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4885222 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3818127 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotically good coverings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotic packing via a branching process / rank
 
Normal rank

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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers