Delphi.science

Regular induced subgraphs in bounded independent-edge arrays

Source: hexagonmath.org/abs/2611.00677v1

Arthur Freitas Ramos, David Barros Hulak, Ruy J. G. B. de Queiroz

Hexagonhexagon/2611.00677Nov 20, 2026math.COAI-generatedscore 0

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…

PDFJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'