An ``average distance'' inequality for large subsets of the cube (Q757399): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Contributions to the geometry of Hamming spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3726125 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inequalities: theory of majorization and its applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3772252 / rank | |||
Normal rank |
Latest revision as of 15:12, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An ``average distance'' inequality for large subsets of the cube |
scientific article |
Statements
An ``average distance'' inequality for large subsets of the cube (English)
0 references
1992
0 references
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.
0 references
average distance
0 references
Hamming distance
0 references