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 G n , p has been analyzed and shown to have the largest independent sets of size Θ ( log n ) 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 G n , p r whose existence of edges is determined by a Markov process that is also governed by a decay parameter r ∈ ( 0 , 1 ] . We prove that w.h.p. G n , p r has independent sets of size ( 1 − r 2 + ε ) n log n for arbitrary ε > 0 . 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 G n , p r collapses to G n , p when there is no decay, it follows that having even the slightest bit of dependency (any r < 1 ) 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 G n , p r , 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 1 + log n ( 1 − r ) 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 Ω ( n 1 / 1 + τ ) , where τ = 1 / ( 1 − r ) and, hence, has a performance ratio of O ( n 1 2 − r ) .