Finding Large Independent Sets in Networks Using Competitive Dynamics

The paper’s Theorem 1 claims: for τ>1, almost all initial x0∈(0,1)^n yield limits that are binary and form a maximal independent set; each such indicator has a basin of non-zero measure, with [0,1]^n forward invariant. The Methods section proves this via (i) invariance, (ii) a replicator–Lotka–Volterra conjugacy plus a convergence theorem to show every trajectory converges to a single equilibrium, and (iii) Jacobian-based instability of non-binary equilibria and stability of MIS indicators . The candidate model solution proves the same result but via a different, self-contained route: a symmetric Lyapunov function W(x)=1^T x − ½ x^T(τA+I)x with dW/dt=∑_i x_i(1−(Mx)_i)^2≥0, LaSalle’s invariance principle, explicit classification of equilibria, and linearization showing MIS indicators are hyperbolic sinks while all other equilibria are saddles. Aside from a minor misstatement in the model write-up (it incorrectly asserts a global inequality Mx≤1 at equilibria, which is false on zero coordinates adjacent to the support), the arguments agree on all essential points, and both establish the same theorem. The paper’s proof leans on known replicator dynamics convergence, whereas the model’s proof gives a direct Lyapunov/linearization analysis; thus, both are correct with different proofs.