Deviation inequality for monotonic Boolean functions with application to a number of k-cycles in a random graph

Simple item page
dc.creatorPanchenko, Dmitry
dc.date2004-05-18
dc.date.accessioned2026-07-07T05:08:23Z
dc.date.available2026-07-07T05:08:23Z
dc.descriptionUsing Talagrand's concentration inequality on the discrete cube {0,1}^m we show that given a real-valued function Z(x)on {0,1}^m that satisfies certain monotonicity conditions one can control the deviations of Z(x) above its median by a local Lipschitz norm of Z(x) at the point x. As one application, we give a simple proof of a nearly optimal deviation inequality for the number of k-cycles in a random graph.
dc.description11 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/math/0405355
dc.identifierhttp://arxiv.org/abs/math/0405355
dc.identifier2004 Rand. Structures Algorithms 24 No. 1
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/71237
dc.subjectProbability
dc.subjectCombinatorics
dc.subject60E15
dc.titleDeviation inequality for monotonic Boolean functions with application to a number of k-cycles in a random graph
dc.typetext

Files

Collections

arXiv