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

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

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

• 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
• 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?)
• 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

(11)

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

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)