Notes on polytope decomposition: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
(Throughout these notes, <math>x,y,z</math> are understood to be non-negative. | (Throughout these notes, <math>x,y,z</math> are understood to be non-negative. | ||
We partition R | We partition R six identical pieces, one of which is | ||
:<math>R_{xyz} := \{ (x,y,z) \in R: x+y \leq y+z \leq z+x \}.</math> | |||
We then partition <math>R_{xyz}</math> further into 10 pieces: | |||
{| border=1 | {| border=1 | ||
| Line 16: | Line 20: | ||
!Name!!Inequalities!!<math>x,y</math> inequalities !!<math>z</math> inequalities | !Name!!Inequalities!!<math>x,y</math> inequalities !!<math>z</math> inequalities | ||
|- | |- | ||
| | | <math>R_{xyz}</math> | ||
| <math>x,y,z \geq 0; x+y+z \leq 3/2</math> | | <math>x,y,z \geq 0; x+y+z \leq 3/2; x+y \leq y+z \leq z+x</math> | ||
| <math>x \geq y \geq 0; | | <math>x \geq y \geq 0; 2x+y \leq 3/2</math> | ||
| | | <math>x \leq z \leq 3/2-x-y</math> | ||
|- | |- | ||
| <math>A_{xyz}</math> | | <math>A_{xyz}</math> | ||
| <math> | | <math>z+x \leq 1-\varepsilon</math> | ||
| <math>2x \leq 1-\varepsilon</math> | | <math>2x \leq 1-\varepsilon</math> | ||
| <math> | | <math>z \leq 1-\varepsilon-x</math> | ||
|- | |- | ||
| <math>B_{xyz}</math> | | <math>B_{xyz}</math> | ||
| <math> | | <math>y+z \leq 1-\varepsilon \leq z+x \leq 1+\varepsilon </math> | ||
| <math>2x \leq 1+\varepsilon; x+y \leq 1-\varepsilon; y \leq 1/2+\varepsilon</math> | | <math>2x \leq 1+\varepsilon; x+y \leq 1-\varepsilon; y \leq 1/2+\varepsilon</math> | ||
| <math> | | <math>1-\varepsilon-x \leq z \leq \min(1+\varepsilon-x, 1-\varepsilon-y)</math> | ||
|- | |- | ||
| <math>C_{xyz}</math> | | <math>C_{xyz}</math> | ||
| <math>x+y \leq 1-\varepsilon \leq y+z | | <math>x+y \leq 1-\varepsilon \leq y+z; z+x \leq 1+\varepsilon </math> | ||
| <math>x+y \leq 1-\varepsilon; x \leq 1/2+\varepsilon</math> | | <math>x+y \leq 1-\varepsilon; x \leq 1/2+\varepsilon</math> | ||
| <math>1-\varepsilon-y \leq z \leq \min(1+\varepsilon-x | | <math>1-\varepsilon-y \leq z \leq \min(1+\varepsilon-x</math> | ||
|- | |- | ||
| <math>D_{xyz}</math> | | <math>D_{xyz}</math> | ||
| <math>1-\varepsilon \leq x+y | | <math>1-\varepsilon \leq x+y; z+x \leq 1+\varepsilon </math> | ||
| <math>x+y \geq 1-\varepsilon; 2x \leq 1+\varepsilon | | <math>x+y \geq 1-\varepsilon; 2x \leq 1+\varepsilon</math> | ||
| <math> | | <math>z \leq 1+\varepsilon-x</math> | ||
|- | |- | ||
| <math>E_{xyz}</math> | | <math>E_{xyz}</math> | ||
| <math> | | <math>y+z \leq 1-\varepsilon; 1+\varepsilon \leq z+x</math> | ||
| <math>x+y \leq 1-\varepsilon; y \leq 1/2-\varepsilon</math> | | <math>x+y \leq 1-\varepsilon; y \leq 1/2-\varepsilon</math> | ||
| <math> | | <math>1+\varepsilon-x \leq z \leq 1-\varepsilon-y</math> | ||
|- | |- | ||
| <math>S_{xyz}</math> | | <math>S_{xyz}</math> | ||
| <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x | | <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x</math> | ||
| | <math>z \leq 1/2+\varepsilon</math> | ||
| | | <math>x+y \leq 1-\varepsilon; x \geq 1/2; y \geq 1/2-2\varepsilon</math> | ||
| <math>\max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq \min(1/2+\varepsilon,1+\varepsilon-y) | |||
|- | |- | ||
| <math>T_{xyz}</math> | | <math>T_{xyz}</math> | ||
| <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x | | <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x</math> | ||
| | <math>z \geq 1/2+\varepsilon; x \geq 1/2-\varepsilon</math> | ||
| | | <math>x+y \leq 1-\varepsilon; x \geq 1/2-\varepsilon</math> | ||
| <math>\max(1-\varepsilon-y,1+\varepsilon-x,1/2-\varepsilon) \leq z \leq 1+\varepsilon-y</math> | |||
|- | |- | ||
| <math>U_{xyz}</math> | | <math>U_{xyz}</math> | ||
| <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x | | <math>x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x</math> | ||
| | <math> x \leq 1/2-\varepsilon</math> | ||
| | | <math>x \leq 1/2-\varepsilon</math> | ||
| <math>\max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq 1+\varepsilon-y </math> | |||
|- | |- | ||
| <math>G_{xyz}</math> | | <math>G_{xyz}</math> | ||
| <math>x+y \leq 1-\varepsilon | | <math>x+y \leq 1-\varepsilon; 1+\varepsilon \leq y+z</math> | ||
| | | <math>x+y \leq 1-\varepsilon; x \leq 1/2-\varepsilon</math> | ||
| <math>1+\varepsilon-y \leq z</math> | |||
|- | |- | ||
| <math>H_{xyz}</math> | | <math>H_{xyz}</math> | ||
| <math>1-\varepsilon \leq x+y | | <math>1-\varepsilon \leq x+y; y+z \leq 1+\varepsilon \leq z+x</math> | ||
| | | <math>x+y \geq 1-\varepsilon</math> | ||
| | | <math>1+\varepsilon-x \leq z \leq 1+\varepsilon-y</math> | ||
|} | |} | ||
Revision as of 18:32, 9 February 2014
The notes here are derived from these notes of Pace Nielsen.
Let [math]\displaystyle{ 1/4 \leq \varepsilon \leq 1/3 }[/math]. The problem here is to optimise the ratio J/I, where
- [math]\displaystyle{ J := 3 \int\int_{x+y \leq 1-\varepsilon} (\int_0^{3/2-x-y} F(x,y,z)\ dz)^2\ dx dy }[/math]
- [math]\displaystyle{ I := \int\int\int_{x+y+z \leq 3/2} F(x,y,z)^2\ dx dy dz }[/math]
for symmetric F supported on [math]\displaystyle{ R := \{ (x,y,z): x+y+z \leq 3/2 \} }[/math] subject to the vanishing marginal condition
- [math]\displaystyle{ \int_0^{3/2-x-y} F(x,y,z)\ dz = 0 }[/math] when [math]\displaystyle{ x+y \geq 1+\varepsilon }[/math].
(Throughout these notes, [math]\displaystyle{ x,y,z }[/math] are understood to be non-negative.
We partition R six identical pieces, one of which is
- [math]\displaystyle{ R_{xyz} := \{ (x,y,z) \in R: x+y \leq y+z \leq z+x \}. }[/math]
We then partition [math]\displaystyle{ R_{xyz} }[/math] further into 10 pieces:
| Name | Inequalities | [math]\displaystyle{ x,y }[/math] inequalities | [math]\displaystyle{ z }[/math] inequalities | |||
|---|---|---|---|---|---|---|
| [math]\displaystyle{ R_{xyz} }[/math] | [math]\displaystyle{ x,y,z \geq 0; x+y+z \leq 3/2; x+y \leq y+z \leq z+x }[/math] | [math]\displaystyle{ x \geq y \geq 0; 2x+y \leq 3/2 }[/math] | [math]\displaystyle{ x \leq z \leq 3/2-x-y }[/math] | |||
| [math]\displaystyle{ A_{xyz} }[/math] | [math]\displaystyle{ z+x \leq 1-\varepsilon }[/math] | [math]\displaystyle{ 2x \leq 1-\varepsilon }[/math] | [math]\displaystyle{ z \leq 1-\varepsilon-x }[/math] | |||
| [math]\displaystyle{ B_{xyz} }[/math] | [math]\displaystyle{ y+z \leq 1-\varepsilon \leq z+x \leq 1+\varepsilon }[/math] | [math]\displaystyle{ 2x \leq 1+\varepsilon; x+y \leq 1-\varepsilon; y \leq 1/2+\varepsilon }[/math] | [math]\displaystyle{ 1-\varepsilon-x \leq z \leq \min(1+\varepsilon-x, 1-\varepsilon-y) }[/math] | |||
| [math]\displaystyle{ C_{xyz} }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z; z+x \leq 1+\varepsilon }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon; x \leq 1/2+\varepsilon }[/math] | [math]\displaystyle{ 1-\varepsilon-y \leq z \leq \min(1+\varepsilon-x }[/math] | |||
| [math]\displaystyle{ D_{xyz} }[/math] | [math]\displaystyle{ 1-\varepsilon \leq x+y; z+x \leq 1+\varepsilon }[/math] | [math]\displaystyle{ x+y \geq 1-\varepsilon; 2x \leq 1+\varepsilon }[/math] | [math]\displaystyle{ z \leq 1+\varepsilon-x }[/math] | |||
| [math]\displaystyle{ E_{xyz} }[/math] | [math]\displaystyle{ y+z \leq 1-\varepsilon; 1+\varepsilon \leq z+x }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon; y \leq 1/2-\varepsilon }[/math] | [math]\displaystyle{ 1+\varepsilon-x \leq z \leq 1-\varepsilon-y }[/math] | |||
| [math]\displaystyle{ S_{xyz} }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math]
[math]\displaystyle{ z \leq 1/2+\varepsilon }[/math] |
[math]\displaystyle{ x+y \leq 1-\varepsilon; x \geq 1/2; y \geq 1/2-2\varepsilon }[/math] | [math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq \min(1/2+\varepsilon,1+\varepsilon-y) |- | \lt math\gt T_{xyz} }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math]
[math]\displaystyle{ z \geq 1/2+\varepsilon; x \geq 1/2-\varepsilon }[/math] |
[math]\displaystyle{ x+y \leq 1-\varepsilon; x \geq 1/2-\varepsilon }[/math] | [math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x,1/2-\varepsilon) \leq z \leq 1+\varepsilon-y }[/math] |
| [math]\displaystyle{ U_{xyz} }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon \leq y+z \leq 1+\varepsilon \leq z+x }[/math]
[math]\displaystyle{ x \leq 1/2-\varepsilon }[/math] |
[math]\displaystyle{ x \leq 1/2-\varepsilon }[/math] | [math]\displaystyle{ \max(1-\varepsilon-y,1+\varepsilon-x) \leq z \leq 1+\varepsilon-y }[/math] | |||
| [math]\displaystyle{ G_{xyz} }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon; 1+\varepsilon \leq y+z }[/math] | [math]\displaystyle{ x+y \leq 1-\varepsilon; x \leq 1/2-\varepsilon }[/math] | [math]\displaystyle{ 1+\varepsilon-y \leq z }[/math] | |||
| [math]\displaystyle{ H_{xyz} }[/math] | [math]\displaystyle{ 1-\varepsilon \leq x+y; y+z \leq 1+\varepsilon \leq z+x }[/math] | [math]\displaystyle{ x+y \geq 1-\varepsilon }[/math] | [math]\displaystyle{ 1+\varepsilon-x \leq z \leq 1+\varepsilon-y }[/math] |
