PreprintCC BY 4.0arXiv
Variance of random greedy independent sets in triangle-free graphs
Abstract
Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let XG be the number of accepted vertices. For every triangle-free graph with n≥2 vertices and e edges, we prove Var(XG)≤ e((n−2)/n)2, with equality precisely for edgeless graphs and connected stars. In particular, among trees of a given order, the star uniquely maximizes the variance, with value (n−1)(n−2)2/n2. Known expected vertex-deletion stability already yields the elementary baseline Var(XG)≤ e. We obtain the sharp finite-order refinement by combining a stronger centered first-choice estimate with a triangle-free edge-count identity in the law of total variance.
Related
- When are random regular triangle-free graphs bipartite?
- Degree Stability of Parallel Greedy Matching in Random Graphs
- The lower tail of triangle counts in sparse random graphs
- Random independent sets in triangle-free and linear Berge-C4-free hypergraphs
- Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
BibTeX
@misc{shaikh2026variance,
title = {{Variance of random greedy independent sets in triangle-free graphs}},
author = {Mubin Shaikh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14826},
eprint = {2609.14826},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14826},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Variance of random greedy independent sets in triangle-free graphs
AU - Mubin Shaikh
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14826
UR - https://arxiv.org/abs/2609.14826
AB - Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let X_G be the number of accepted vertices. For every triangle-free graph with n≥2 vertices and e edges, we prove Var(X_G)≤ e((n−2)/n)^2, with equality precisely for edgeless graphs and connected stars. In particular, among trees of a given order, the star uniquely maximizes the variance, with value (n−1)(n−2)^2/n^2. Known expected vertex-deletion stability already yields the elementary baseline Var(X_G)≤ e. We obtain the sharp finite-order refinement by combining a stronger centered first-choice estimate with a triangle-free edge-count identity in the law of total variance.
ER -