Generalizing the bounded kernel results of Borgs, Chayes, Lovász, Sós and Vesztergombi [2], we prove two Sampling Lemmas for unbounded kernels with respect to the cut norm. On the one hand, we show that given a (symmetric) kernel \(U\in L^p([0,1]^2)\) for some \(3<p<\infty\) , the cut norm of a random \(k\) -sample of \(U\) is with high probability within \(O(k^{-\frac14+\frac{1}{4p}})\) of the cut norm of \(U\) . The cut norm of the sample has a strong bias to being larger than the original, allowing us to actually obtain a stronger high probability bound of order \(O(k^{-\frac 12+\frac1p+\varepsilon})\) for how much smaller it can be (for any \(p>2\) here). These results are then partially extended to the case of vector valued kernels.
On the other hand, we show that with high probability, the \(k\) -samples are also close to \(U\) in the cut metric, albeit with a weaker bound of order \(O((\ln k)^{-\frac12+\frac1{2p}})\) (for any appropriate \(p>2\) ). As a corollary, we obtain that whenever \(U\in L^p\) with \(p>4\) , the \(k\) -samples converge almost surely to \(U\) in the cut metric as \(k\to\infty\) .
