The matching process and independent process in random regular graphs and hypergraphs

DOI10.37236/10698MaRDI QIDQ2111785zbMATH OpenOpenAlexFDO

Authors Deepak Bal, Patrick Bennett

Publication date 17 January 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random regular graphindependent processmatching processrandom regular hypergraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this note, we analyze two random greedy processes on sparse random graphs and hypergraphs with a given degree sequence. First we analyze the matching process, which builds a set of disjoint edges one edge at a time; then we analyze the independent process, which builds an independent set of vertices one vertex at a time. We use the differential equations method and apply a general theorem of Warnke. Our main contribution is to significantly reduce the associated systems of differential equations and simplify the expression for the final size of the matching or independent set.

Recommendations

• A natural barrier in random greedy hypergraph matching
• A note on the random greedy independent set algorithm
• Almost perfect matchings in random uniform hypergraphs
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Random hypergraph processes with degree restrictions

Cites work

• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• scientific article; zbMATH DE number 4099072 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A natural barrier in random greedy hypergraph matching
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Cliques in random graphs
• Controllability and matchings in random bipartite graphs
• Differential equations for random processes and random graphs
• Hamilton Cycles in Random Lifts of Directed Graphs
• Karp-Sipser on random graphs with a fixed degree sequence
• Large independent sets in regular graphs of large girth
• Local algorithms, regular graphs of large girth, and random regular graphs
• Matching theory
• Maximum matchings in regular graphs of high girth
• On colouring random graphs
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Random Sequential Adsorption on Graphs
• Random graphs.
• Random parking, sequential adsorption, and the jamming limit
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Randomized greedy matching
• The average performance of the greedy matching algorithm
• The cook-book approach to the differential equation method
• The greedy independent set in a random graph with given degrees

Cited in

(7)

• A stochastic matching model on hypergraphs
• A note on the random greedy independent set algorithm
• On the matching number and the independence number of a random induced subhypergraph of a hypergraph
• The random \(k\)-matching-free process
• Random hypergraph processes with degree restrictions
• On the random greedy \(F\)-free hypergraph process
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)

This page was built for publication: The matching process and independent process in random regular graphs and hypergraphs

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