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 of labelled vertices is a two-element subset of ; write for the set of potential edges.✦ A support graph on is a subset of , and denotes its number of edges. The nonisolated vertex set is the subset of consisting of vertices incident with an edge of . The degree of a vertex is the number of edges of containing , as in (1). (1)
The free edge set of a vertex block consists of every potential edge with at least one endpoint in , as in (2); only edges wholly outside are fixed. (2)
Definition 1. For a real cutoff , a vertex block detects a support when its number of free support edges satisfies (3). (3)✦
The uniform block probability is the probability of an event when a block is chosen uniformly among the -element subsets of a finite ambient set .✦
The Claim
Theorem 1. Every support graph satisfies (4). (4)✦
For a nonempty support , there is a vertex satisfying (5). (5)✦
If is a nonempty support and the real cutoff satisfies , then some vertex satisfies (6). (6)✦
Let be finite sets, let , and let be an integer with ; then the singleton capture bound is (7). (7)✦
Let satisfy , and let . Set and . For a nonempty support with , the detection bound is (8). (8)✦
In the paper, the result reads: a nonempty support graph with edges has and a vertex with ; if and , one can choose with , the event leaves exactly support edges free and, for a uniform -element block , has probability at least , while for , , and , the probability of retaining between and support edges is at least .
What Is Checked
The claims are stated over support graphs on labelled vertices and uniform -element subsets of finite ambient sets.