Edge-isoperimetric inequalities and influences

Simple item page
dc.creatorFalik, D.
dc.creatorSamorodnitsky, A.
dc.date2005-12-29
dc.date.accessioned2026-07-07T06:55:52Z
dc.date.available2026-07-07T06:55:52Z
dc.descriptionWe give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the $n$-dimensional boolean cube has a variable with influence of at least Omega(\frac{log n}{n}). The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants. We also state some conjectures about optimal constants and discuss their possible implications
dc.identifierhttps://arxiv.org/abs/math/0512636
dc.identifierhttp://arxiv.org/abs/math/0512636
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/106425
dc.subjectCombinatorics
dc.titleEdge-isoperimetric inequalities and influences
dc.typetext

Files

Collections

arXiv