The largest $K_r$-free set of vertices in a random graph
For $r \ge 2$ and a graph $G$, let $α_{r}(G)$ be the maximum number of vertices in a $K_r$-free subgraph of $G$. We investigate the value $α_{r}(G)$ when $G$ is the random graph $G \sim G_{n, 1/2}$ and discover the following phenomenon: with high probability, $α_r(G)$ lies in an interval of constant length that varies in a non-monotonic fashion from $1$ to $\lfloor r/2\rfloor+1$ depending on the value of $n$. The special case $r=2$ corresponds to the independence number of random graphs which is well-known to have two-point concentration; our results therefore extend and generalize this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.16454
curl -X POST /api/v1/records/arxiv/2603.16454/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.16454/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'