New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help

DOI10.1002/1098-2418(200008)17:1%3C29::AID-RSA4%3E3.0.CO;2-WMaRDI QIDQ4500484zbMATHOpenAlexFDO

Authors Van Vu

Publication date 23 January 2001

Full work available at URL https://doi.org/10.1002/1098-2418(200008)17:1%3C29::aid-rsa4%3E3.0.co;2-w

zbMATH Keywords

polynomial methodmatchings in hypergraphsstrong concentrationcodegree sequenceRödl nibble

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Near perfect matchings in \(k\)-uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Nearly perfect matchings in regular simple hypergraphs
• On the number of nearly perfect matchings in almost regular uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 1380611 (Why is no real title available?)
• Asymptotic behavior of the chromatic index for hypergraphs
• Asymptotic packing via a branching process
• Asymptotically good list-colorings
• Asymptotically optimal covering designs
• Concentration of measure and isoperimetric inequalities in product spaces
• Near perfect coverings in graphs and hypergraphs
• Nearly perfect matchings in regular simple hypergraphs
• Nearly-perfect hypergraph packing is in NC
• On a packing and covering problem
• On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
• On the difference between asymptotically good packings and coverings
• Small complete arcs in projective planes

Cited in

(13)

• Note on asymptotically good packings
• Long gaps between primes
• A natural barrier in random greedy hypergraph matching
• Arboricity: an acyclic hypergraph decomposition problem motivated by database theory
• Computing the partition function for perfect matchings in a hypergraph
• On a refinement of Waring's problem
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Concentration of non‐Lipschitz functions and applications
• Graph and hypergraph colouring via nibble methods: a survey
• The infamous upper tail
• When almost all sets are difference dominated
• Piercing random boxes
• New bounds on the size of nearly perfect matchings in almost regular hypergraphs

This page was built for publication: New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500484)