A natural barrier in random greedy hypergraph matching

DOI10.1017/S0963548319000051MaRDI QIDQ5222558zbMATH OpenOpenAlexFDO

Authors Patrick Bennett, Tom Bohman

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

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05) Hypergraphs (05C65) 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)

Abstract: Let $rge2$ be a fixed constant and let $mathcalH$ be an $r$-uniform, $D$-regular hypergraph on $N$ vertices. Assume further that $Doinfty$ as $Noinfty$ and that degrees of pairs of vertices in $mathcalH$ are at most $L$ where $L=D/(logN{)}^{omega(1)}$. We consider the random greedy algorithm for forming a matching in $mathcalH$. We choose a matching at random by iteratively choosing edges uniformly at random to be in the matching and deleting all edges that share at least one vertex with a chosen edge before moving on to the next choice. This process terminates when there are no edges remaining in the graph. We show that with high probability the proportion of vertices of $mathcalH$ that are not saturated by the final matching is at most $(L/D{)}^{frac12(r-1)+o(1)}$. This point is a natural barrier in the analysis of the random greedy hypergraph matching process.

Recommendations

• Greedy matching in bipartite random graphs
• scientific article; zbMATH DE number 1033855
• A Fast Perfect-Matching Algorithm in Random Graphs
• Pseudorandom hypergraph matchings
• On a hypergraph matching problem
• A stochastic matching model on hypergraphs
• An algorithmic framework for the matching problem in some hypergraphs
• A greedy algorithm for finding a large 2‐matching on a random cubic graph

Cites work

• scientific article; zbMATH DE number 1380611 (Why is no real title available?)
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 3198027 (Why is no real title available?)
• A note on the random greedy triangle-packing algorithm
• Asymptotic behavior of the chromatic index for hypergraphs
• Asymptotic packing via a branching process
• Hamiltonicity of random graphs produced by 2‐processes
• Nearly perfect matchings in regular simple hypergraphs
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• On a packing and covering problem
• On random greedy triangle packing
• Random triangle removal
• SIR epidemics on random graphs with a fixed degree sequence
• The triangle-free process

Cited in

(9)

• A note on the random greedy independent set algorithm
• Graph and hypergraph colouring via nibble methods: a survey
• A sharp threshold for bootstrap percolation in a random hypergraph
• On the random greedy linear uniform hypergraph packing
• Coloured and directed designs
• Perfect matchings in random s‐uniform hypergraphs
• A gentle introduction to the differential equation method and dynamic concentration
• Greedy matching: guarantees and limitations
• The matching process and independent process in random regular graphs and hypergraphs

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

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