A natural barrier in random greedy hypergraph matching

DOI10.1017/S0963548319000051zbMath1436.05079arXiv1210.3581OpenAlexW1809515066MaRDI QIDQ5222558

Tom Bohman, Patrick Bennett

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.3581

zbMATH Keywords

random greedy algorithmrandom greedy hypergraph matching process

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

A gentle introduction to the differential equation method and dynamic concentration ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ Unnamed Item ⋮ Coloured and Directed Designs ⋮ Greedy matching: guarantees and limitations ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ The matching process and independent process in random regular graphs and hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the random greedy triangle-packing algorithm
• Asymptotic behavior of the chromatic index for hypergraphs
• The triangle-free process
• On a packing and covering problem
• Nearly perfect matchings in regular simple hypergraphs
• On random greedy triangle packing
• Random triangle removal
• SIR epidemics on random graphs with a fixed degree sequence
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• Asymptotic packing via a branching process
• Hamiltonicity of random graphs produced by 2‐processes

This page was built for publication: A natural barrier in random greedy hypergraph matching