OctoInformBeta

OpenAI preprint, September 2026 · §3. Restricting to the edges incident with a vertex block

§3: A small positive degree and one-vertex capture: Small positive degrees and singleton capture give detection bounds for square-root block size and a logarithmic cutoff

Capturing support edges with a random vertex block.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

For a fixed set of support edges, how often does a uniformly chosen vertex block leave a positive number of them free without exceeding a prescribed cutoff?

A potential edge on a set [n][n] of nn labelled vertices is a two-element subset of [n][n]; write En=([n]2)E_n=\binom{[n]}{2} for the set of potential edges.✦ A support graph SS on [n][n] is a subset of EnE_n, and s=|S|s=|S| denotes its number of edges. The nonisolated vertex set V(S)V(S) is the subset of [n][n] consisting of vertices incident with an edge of SS. The degree dS(u)d_S(u) of a vertex u∈[n]u\in[n] is the number of edges of SS containing uu, as in (1). V(S)=⋃e∈Se,dS(u)=|{e∈S:u∈e}|.V(S)=\bigcup_{e\in S}e, \qquad d_S(u)=|\{e\in S:u\in e\}|.(1)

The free edge set FBF_B of a vertex block B⊆[n]B\subseteq[n] consists of every potential edge with at least one endpoint in BB, as in (2); only edges wholly outside BB are fixed. FB={e∈En:e∩B≠⌀}.F_B=\{e\in E_n:e\cap B\ne\varnothing\}.(2)

Definition 1. For a real cutoff kk, a vertex block B⊆[n]B\subseteq[n] detects a support S⊆EnS\subseteq E_n when its number of free support edges satisfies (3). 1≤|S∩FB|≤k.1\le |S\cap F_B|\le k.(3)✦

The uniform block probability ℙU,m(P)\mathbb P_{U,m}(P) is the probability of an event PP when a block BB is chosen uniformly among the mm-element subsets of a finite ambient set UU.✦

The Claim

Theorem 1. Every support graph S⊆EnS\subseteq E_n satisfies (4). |V(S)|≤2s.|V(S)|\le 2s.(4)✦

For a nonempty support SS, there is a vertex u∈V(S)u\in V(S) satisfying (5). 1≤dS(u),dS(u)2≤2s.1\le d_S(u), \qquad d_S(u)^2\le 2s.(5)✦

If SS is a nonempty support and the real cutoff k≥0k\ge0 satisfies s≤k2/2s\le k^2/2, then some vertex u∈V(S)u\in V(S) satisfies (6). 1≤dS(u)≤k.1\le d_S(u)\le k.(6)✦

Let W⊆UW\subseteq U be finite sets, let u∈Wu\in W, and let mm be an integer with 2≤m≤|U|2\le m\le |U|; then the singleton capture bound is (7). ℙU,m{B∩W={u}}≥m|U|(1−(|W|−1)(m−1)|U|−1).\mathbb P_{U,m}\{B\cap W=\{u\}\} \ge \frac{m}{|U|} \left(1-\frac{(|W|-1)(m-1)}{|U|-1}\right).(7)✦

Let n≥2n\ge2 satisfy log⁡n≥16\log n\ge16, and let 0≤σ≤1/20\le\sigma\le1/2. Set m=⌊n⌋m=\lfloor\sqrt n\rfloor and k=σlog⁡m/64k=\sigma\log m/64. For a nonempty support S⊆EnS\subseteq E_n with s≤k2/2s\le k^2/2, the detection bound is (8). ℙ[n],m{1≤|S∩FB|≤k}≥m2n.\mathbb P_{[n],m}\{1\le |S\cap F_B|\le k\} \ge \frac{m}{2n}.(8)✦

In the paper, the result reads: a nonempty support graph SS with ss edges has |V(S)|≤2s|V(S)|\le2s and a vertex u∈V(S)u\in V(S) with 1≤dS(u)≤2s1\le d_S(u)\le\sqrt{2s}; if s≤k2/2s\le k^2/2 and k≥0k\ge0, one can choose uu with dS(u)≤kd_S(u)\le k, the event B∩V(S)={u}B\cap V(S)=\{u\} leaves exactly dS(u)d_S(u) support edges free and, for a uniform mm-element block B⊆[n]B\subseteq[n], has probability at least mn[1−(|V(S)|−1)(m−1)/(n−1)]\frac mn[1-(|V(S)|-1)(m-1)/(n-1)], while for t=log⁡n≥16t=\log n\ge16, m=⌊n⌋m=\lfloor\sqrt n\rfloor, 0≤σ≤1/20\le\sigma\le1/2 and k=σlog⁡m/64k=\sigma\log m/64, the probability of retaining between 11 and kk support edges is at least m/(2n)m/(2n).

What Is Checked

The claims are stated over support graphs on nn labelled vertices and uniform mm-element subsets of finite ambient sets.