Large Independent Sets in Recursive Markov Random Graphs

Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well studied for various classes of graphs. When it comes to random graphs, the classic Erdős–Rényi–Gilbert random graph Formula: see text has been analyzed and shown to have the largest independent sets of size Formula: see text with high probability (w.h.p.) This classic model does not capture any dependency structure between edges that can appear in real-world networks. We define random graphs Formula: see text whose existence of edges is determined by a Markov process that is also governed by a decay parameter Formula: see text. We prove that w.h.p. Formula: see text has independent sets of size Formula: see text for arbitrary Formula: see text. This is derived using bounds on the terms of a harmonic series, a Turán bound on a stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Because Formula: see text collapses to Formula: see text when there is no decay, it follows that having even the slightest bit of dependency (any Formula: see text) in the random graph construction leads to the presence of large independent sets, and thus, our random model has a phase transition at its boundary value of r = 1. This implies that there are large matchings in the line graph of Formula: see text, which is a Markov random field. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most Formula: see text w.h.p. when the lowest degree vertex is picked at each iteration and also show that, under any other permutation of vertices, the algorithm outputs a set of size Formula: see text, where Formula: see text and, hence, has a performance ratio of Formula: see text. Funding: The initial phase of this research was supported by the National Science Foundation Grant DMS-1913294.