A natural barrier in random greedy hypergraph matching

DOI10.1017/S0963548319000051zbMATH Open1436.05079arXiv1210.3581OpenAlexW1809515066MaRDI QIDQ5222558FDOQ5222558

Authors: Patrick Bennett, Tom Bohman 

Publication date: 6 April 2020

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)