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

DOI<29::AID-RSA4>3.0.CO;2-W 10.1002/1098-2418(200008)17:1<29::AID-RSA4>3.0.CO;2-WzbMath0953.05056OpenAlexW1988229094MaRDI QIDQ4500484

Van H. Vu

Publication date: 23 January 2001

Full work available at URL: https://doi.org/10.1002/1098-2418(200008)17:1<29::aid-rsa4>3.0.co;2-w

zbMATH Keywords

matchings in hypergraphspolynomial methodstrong concentrationcodegree sequenceRödl nibble

Mathematics Subject Classification ID

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

Related Items (13)

The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 ⋮ Concentration of non‐Lipschitz functions and applications ⋮ The infamous upper tail ⋮ Long gaps between primes ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ New bounds on the size of nearly perfect matchings in almost regular hypergraphs ⋮ Piercing random boxes ⋮ Note on asymptotically good packings ⋮ When almost all sets are difference dominated ⋮ 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

Cites Work

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

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