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

independent process matching process random regular graph random regular hypergraphs

Mathematics Subject Classification ID

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

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.

Review text

The paper investigates natural random greedy processes for producing matchings and independent sets in hypergraphs. In both processes, a collection (a matching or an independent set) in a hypergraph \(H\) is built by picking objects one by one. In each step, we choose a random object (an edge or a vertex, respectively) that does not conflict with previous choices; and this is repeated until no further choice is possible. The output of the algorithm is always a maximal matching or independent set of \(H\). In many cases, it is known that the aforementioned random processes build a collection (matching or independent set) that is close to being of maximum size (and not just maximal). It is of interest to estimate, for example, the number of uncovered vertices left by the matching process in particular cases of hypergraphs. The authors consider the case where the \(r\)-uniform hypergraph is randomly chosen using a degree-constrained hypergraph model. In this model, given \(0 \leq i \leq \Delta\), the number of vertices \(n_i\) of degree \(i\) is fixed, and the hypergraph is chosen at random under that constraint. The authors obtain a formula for the asymptotic number of vertices which is uncovered after the matching process, and the precise formula depends on the choice of the numbers \((n_1, \dots, n_\Delta)\). In its full generality, the formula does not give a term that is easy to calculate, but in particular cases (e.g. when every vertex has degree \(\Delta\), and \(\Delta\) is constant) it yields an explicit function in terms of \(r\) and \(\Delta\). This result is generalised to other families of hypergraphs as well, as well as for the independent process. The main tool used to analyse the random process is the differential equation method of \textit{N. C. Wormald} [Lond. Math. Soc. Lect. Note Ser. 267, 239--298 (1999; Zbl 0935.05080)].

Recommendations

Cites work

Cited in

(7)

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)