Large Independent Sets in Recursive Markov Random Graphs

Akshay Gupte () and Yiran Zhu ()
Additional contact information
Akshay Gupte: School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, Edinburgh EH9 3FD, United Kingdom
Yiran Zhu: School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, Edinburgh EH9 3FD, United Kingdom

Mathematics of Operations Research, 2025, vol. 50, issue 3, 1611-1634

Abstract: 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 ) .

Keywords: 90C27; 60J10; 05C80; 05C69; independent sets; greedy algorithm; concentration inequalities; Turán’s theorem; dependent Bernoulli sequence (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0215 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:3:p:1611-1634

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().