PUB - Publikationen an der Universität Bielefeld

We present concentration inequalities on the multislice which are based on (modified) log-Sobolev inequalities. This includes bounds for convex functions and multilinear polynomials. As an application, we show concentration results for the triangle count in the G(n, M) Erdos-Renyi model resembling known bounds in the G(n, p) case. Moreover, we give a proof of Talagrand's convex distance inequality for the multislice. Interpreting the multislice in a sampling without replacement context, we furthermore present concentration results for n out of N sampling without replacement. Based on a bounded difference inequality involving the finite-sampling correction factor 1 - (n/ N), we present an easy proof of Serfling's inequality with a slightly worse factor in the exponent, as well as a sub-Gaussian right tail for theKolmogorov distance between the empirical measure and the true distribution of the sample.