An Extremal Problem on Degree Sequences of Graphs |
| |
| Authors: | Nathan Linial Eyal Rozenman |
| |
| Institution: | (1) Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel e-mail: nati, IL;(2) Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel e-mail: eyalroz@cs.huji.ac.il, IL |
| |
| Abstract: | Let G=(I
n
,E) be the graph of the n-dimensional cube. Namely, I
n
={0,1}
n
and x,y]∈E whenever ||x−y||1=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
n−1
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 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
