An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences