Regular induced subgraphs in bounded independent-edge arrays
Source: hexagonmath.org/abs/2611.00677v1
Let $G$ be a random graph whose edges are independent and whose edge probabilities lie in $[\xi,1-\xi]$ for a fixed $0<\xi<1/2$. With probability at least $1-n^{-1}$, $G$ contains a regular induced subgraph on at least $c_\xi(\log n)^2$ vertices. If all expected degrees are equal, each prescribed order $k$ up to a small multiple of $n^{2/3}$ occurs with failure probability at most $\exp(-cn/k^{3/2})$, for $k$ sufficiently large. The same probability estimate holds up to order $n^{2/(d+3)}$ for a Lipschitz kernel in dimension $d$, and up to order $n^{4/(r+7)}$ for an array admitting a bounded…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00677
curl -X POST /api/v1/records/hexagon/2611.00677/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00677/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'