The CW-inequalities for vectors in \(\ell_ 1\) (Q1813623): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the cut polytope / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4089444 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0195-6698(13)80049-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2003000354 / rank | |||
Normal rank |
Latest revision as of 10:52, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The CW-inequalities for vectors in \(\ell_ 1\) |
scientific article |
Statements
The CW-inequalities for vectors in \(\ell_ 1\) (English)
0 references
25 June 1992
0 references
Let \(G=(V,E)\) be a graph, where \(V\) is a set of vectors in the metric space \(\ell_ 1\), the space consisting of vectors \((x_ 1,x_ 2,\dots)\) such that \(\sum^ \infty_{i=1}| x_ i|<\infty\) with a distance function defined by \(d({\mathbf x},{\mathbf y})=\sum^ \infty_{i=1}| x_ i-y_ i|\), where \({\mathbf x}=(x_ 1,x_ 2,\dots)\) and \({\mathbf y}=(y_ 1,y_ 2,\dots)\). Define a parameter \(d(G)=\sum_{uv\in E}d(u,v)\). For any integers \(k>0\) and \(u\geq 0\), and vectors \(v_ 0,v_ 1,\dots,v_{k+2u}\), \(u_ 0,u_ 1,\dots,u_{k- 1}\in\ell_ 1\) (not necessary distinct), writing \(X=\{v_ 0,\dots,v_{k+2u}\}\), \(Y=\{u_ 0,\dots,u_{k-1}\}\), construct the following graphs: \(W=(X,E_ 1)\): \(v_ iv_ j\in E_ 1\), if there is an \(s\), \(-u\leq s\leq u\) such that \(i-j\equiv s\) \((\text{mod }k+2u-1)\); \(B=(X\cup Y,E_ 2)\): a complete bipartite graph with bipartition \((X,Y)\); \(K_ X=(X,E_ 3)\): a complete graph; \(K_ Y=(Y,E_ 4)\): a complete graph. The author proves: \(d(W)+d(B)\geq d(K_ X)+d(K_ Y)\). This inequality is known as the Clique-Web inequality conjectured by M. Deza and M. Laurent in 1988.
0 references
Clique-Web inequality
0 references