观点

Lemma 9 ([Transfer to a finite simple host]). Suppose U is a symmetric [0,1] -valued kernel on a finite probability space, μ= U>0 , and τ=t(H,U), Δ=μ^ 66 -τ>0. For any integer n> 595+66μ^ 66 Δ , there is a finite simple graph G on n …

Lemma 9 ([Transfer to a finite simple host]). Suppose U is a symmetric [0,1] -valued kernel on a finite probability space, μ= U>0 , and τ=t(H,U), Δ=μ66 -τ>0. For any integer n> 595+66μ66 Δ , there is a finite simple graph G on n vertices with t(H,G)<p(G)66 .

证明 1证否 0作为观点被引用 2链条图发起推演

发起推演1

证明
Sample labels z_1,…,z_n independently from the probability space of U . Conditional on these labels, put an edge on each unordered pair of distinct vertices a,b independently with probability U(z_a,z_b) . No loops are drawn. This defines a random finite simple undirected graph G_n , and p(G_n)=(1-1/n)μ. For every injective map f:V(H)→1,…,n , its image vertices have independent labels, and its 66 source edges use distinct unordered host pairs. Its probability of being a homomorphism is exactly τ . Among all n^ 35 maps, the proportion that identify any two source vertices is at most 35 2 /n=595/n , by the union bound. Each such map has a homomorphism indicator between zero and one; a collision on a source edge gives zero, while any repeated host edges are counted by their actual single Bernoulli trials. No independence claim for these maps is needed. Comparing their contribution with τ times their proportion gives | t(H,G_n)-τ|≤(595)/(n). Thus the density still counts all homomorphisms, including every noninjective one. Using (1-1/n)^ 66 ≥1-66/n , Equations and give t(H,G_n) , ≤μ^ 66 -Δ+595/n; , <μ^ 66 -66μ^ 66 /n; , ≤((1-1/n)μ)^ 66 =( p(G_n))^ 66 ≤[p(G_n)^ 66 ]. The last inequality is convexity. Hence some realization has t(H,G_n)<p(G_n)^ 66 . Such a realization cannot be edgeless.