An ``average distance'' inequality for large subsets of the cube
type: Item
instance of: scholarly article
title: An ``average distance'' inequality for large subsets of the cube
zbMATH Open document ID: 0723.05055
DOI: 10.1016/0095-8956(92)90024-R
author: Ingo Althöfer
author: Torsten Sillke
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: For a subset \(A\subset \{0,1\}^ n\) the average distance in A is defined by \(dist(A)=\frac{1}{| A|^ 2}\sum_{x\in A}\sum_{y\in A}H(x,y)\), where \(H(x,y)=| \{i| x_ i\neq y_ i\}|\) is the Hamming distance between \((x_ 1,...,x_ n)\) and \((y_ 1,...,y_ n)\). We show that \(dist(A)\geq \frac{n+1}{2}-\frac{2^{n-1}}{| A|}\) for every \(A\subset \{0,1\}^ n\). This bound is good for large subsets of the cube. It is tight for \(| A| =2^{n-1}\), where the subcubes of dimension n-1 are the only extremal configurations.
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 4191684
zbMATH Keywords: average distance
zbMATH Keywords: Hamming distance
MaRDI profile type: Publication
cites work: Contributions to the geometry of Hamming spaces
cites work: Q3726125
cites work: Inequalities: theory of majorization and its applications
cites work: Q3772252
Recommended article: On average and typical values of sums of pairwise distances for subsets of vertices of the n-dimensional unit cube
Recommended article: Q3732558
Recommended article: The extremal average distance of cubic graphs
Recommended article: An isoperimetric inequality for antipodal subsets of the discrete cube
Recommended article: On the average volume of subsets in Euclidean \(d\)-space
Recommended article: Q4416146
Recommended article: The average distance property for subsets of Euclidean space
Recommended article: Minimum average distance subsets in the Hamming cube
Recommended article: Q3789573
description: scientific article; zbMATH DE number 4191684