Transcript Document

Nonlinear methods in discrete
optimization
László Lovász
Eötvös Loránd University, Budapest
[email protected]
planar graph
Every simple planar graph can be drawn
in the plane with straight edges
Exercise 1: Prove this.
Fáry-Wagner
Rubber bands and planarity
Tutte (1963)
Every 3-connected planar graph can be drawn with
straight edges and convex faces.
Rubber bands and planarity
outer face fixed to
convex polygon
edges replaced by
rubber bands
Energy: E =
å
(ui - u j )2
ijÎ E
Equilibrium:
1
ui 
di

j N ( i )
uj
G 3-connected planar
Tutte
rubber band embedding is planar
Exercise 2. (a) Let L be a line intersecting the outer polygon P, and let U
be the set of nodes of G that fall on a given (open) side of L. Then U
induces a connected subgraph of G.
(b) There cannot exists a node and a line such that the node and all its
neighbors fall on this line.
(c) Let ab be an edge that is not an edge of P, and let F and F’ be the two
faces incident with ab. Prove that all the other nodes of F fall on one side
of the line through this edge, and all the other nodes of F’ are mapped on
the other side.
(d) Prove the theorem above.
Coin representation Koebe (1936)
Every planar graph can be represented by touching circles
Discrete Riemann Mapping Theorem
Can this be obtained from a rubber band representation?
Tutte representation  optimal circles
Want:
xi - x j = ri + rj
Minimize:
å
(ri + rj - | xi - x j |)2
ijÎ E
Optimum satisfies i:
å
j
ijÎ E
(ri + rj - | xi - x j |) = 0
Rubber bands and strengths
rubber bands have
strengths cij > 0
Energy:
E=
å
cij (ui - u j )2
ijÎ E
Equilibrium:
ui 
 cu
c
jN ( i )
jN ( i )
ij
ij
j
å
ijÎ E
cij (ui - u j ) = 0
Update strengths:
c 'ij = cij
| xi - x j |
ri + rj
The procedure converges to an equilibrium, where
xi - x j = ri + rj
Exercise 3. The edges of a simple planar map are 2-colored
with red and blue. Prove that there is always a node where the
red edges (and so also the blue edges) are consecutive.
There is a node where
“too strong” edges (and
“too weak” edges) are
consecutive.
A direct optimization proof [Colin de Verdiere]
x
Set j ( x) = 2
t
arctan(
e
) dt
ò
- ¥
From any Tutte representation
bip
p
i
Variables:
xÎ
V
, yÎ
F
log radii of circles
representing nodes
log radii of circles
inscribed in facets
minimize
å
iÎ V , pÎ F
iÎ p
j ( y p - xi ) - bip ( y p - xi )
Polar polytope
P
d
: polytope,
P*  { y 
d
0 P
: xT y  1 x  P}: polar polytope
Blocking polyhedra Fulkerson 1970
K
n

convex,
ascending
K *  {x 
n

: xT y  1 y  K}
Exercise 4. Let K be the dominant of the convex hull of edgesets of
s-t paths. Prove that the blocker is the dominant of the convex hull of
edge-sets of s-t cuts.
( K * )*  K ;
facets of K  vertices of K *
Energy
K
n

convex, ascending (recessive)
x K , y  x  y K
E( K ) = d 2 (0, K ) = min{| x |2: x Î K}
E( K )E( K * ) = 1
x: shortest vector in K
x*: shortest vector in K*
 x* x
Generalized energy
K
n

convex, ascending (recessive)
x K , y  x  y K
cÎ
n
+
E( K , c) = min { å ci xi 2 : x Î K }
L ( K , c) = min { å ci xi : x Î K }
æ1
ö
1
÷
÷
, c* = ç
,...,
ç
÷
ç
÷
c
c
è1
nø
1 £ L ( K , c)L ( K * , c* ) £ n
E( K , c)E( K * , c* ) = 1
x: shortest vector in K
 x*i  Cci xi
x*: shortest vector in K*
Exercise 5. Prove these inequalities. Also prove that they are sharp.
Example 1.
KÍ
E (G )
+
´
E (G )
+
, K = {( xi - x j : x1 = a1 , x2 = a2 , x3 = a3 )}
´ {( yi - y j : y1 = b1 , y2 = b2 , y3 = b3 )}
E( K ) = energy of rubber bands
Example 2.
KÍ
E (G )
+
, K = s-t flows of value 1 and “everything above”
E( K ) = electrical resistance between nodes s and t
Example 3
Traffic jams (directed) N cars from s to t
time to cross e ~ traffic through e = xeN
s
t
(xe): flow of value 1 from s to t
average travel time:  xe
Best average travel time = distance of 0 from
the directed flow polytope
2
Square tilings I
Brooks-Smith-Stone-Tutte 1940
10
0
3
3
4
1
3
2
4
3
5
2
6
7
5
3
2
9
10
10
3
3
4
1
2
3
2
5
2
3
10
10
Square tilings II
3
9
3
3
2
4
1
9
2
5
3
2
10
Every triangulation of a quadrilateral can be
represented by a square tiling of a rectangle.
Schramm
10
3
9
3
3
2
4
1
9
2
5
3
2
10
Every triangulation of a quadrilateral can be
represented by a square tiling of a rectangle.
Schramm
If the triangulation is 5-connected, then the
representing squares are non-degeenerate.
t
K=convex hull of
x: shortest vector in K
x*: shortest vector in K*
nodesets of
u-v paths + +n
x  Cx
*
u
v
Exercise 6. The blocker of K is the dominant of the convex
hull of s-t paths.
Exercise 7. (a) How to get the
position of the center of each square?
(b) Complete the proof.
s
x gives lengths of edges
of the squares.
Unit vector flows
" edge ij
vij = - v ji
å
vij = 0
vij Î
d
skew symmetric
vector flow
j
v ij = 1
Trivial necessary condition: G is 2-edge-connected.
Conjecture 1. For d=2, every 4-edge-connected graph has
a unit vector flow.
Conjecture 2. For d=3, every 2-edge-connected graph has
a unit vector flow.
Theorem. For d=7, every 2-edge-connected graph has
a unit vector flow.
Jain
It suffices to consider 3-edge-connected 3-regular graphs
Exercise 8. Prove conjecture 2 for planar graphs.
[Schramm]
" edge ij
aij Î
" node i
xi Î
d
skew symmetric (parameter)
d
(vector variable)
minimize å aij + xi - x j
ij
¶
¶ xk
å
ij
aij + xi - x j =
å
j
a kj + x k - x j
a kj + x k - x j
=0
unit vector flow?
Conjecture 2’.
$aij for which the minimizing xi satisfies aij + xi - x j ¹ 0
Exercise 9. Conjectures 2' and 2" are equivalent to Conjecture 2.
Conjecture 2’’. Every 3-regular 3-connected graph can be
drawn on the sphere so that every edge is an arc of a large
circle, and at every node, any two edges form 120o.
Antiblocking polyhedra
Fulkerson 1971
(polarity in the nonnegative orthant)
K
n

convex corner
(K * )*  K;
K *  {x 
n

: xT y  1 y  K}
facets of K  vertices of K *
The stable set polytope
 A : incidence vector of set A
STAB(G)  conv{ A : A stable set in G }
Graph entropy
Körner 1973
p: probability distribution on V(G)
H (G, p )  min{

iV (G )
 pi log xi : x STAB(G )}
  p log x
i
i
H ( Kn , p)  H ( p)   pi log pi
 const
t
1
H (G, p)  limt  minU V (Gt ) log  (G [U ])
t
Pt (U ) .99
connected iff distinguishable
Want: encode most of V(G)t by 0-1 words of min length,
so that distinguishable words get different codes.
(measure of “complexity” of G)
H ( F , p)  H (G, p)  H ( F  G, p)
H (G, p)  H (G, p)  H ( p)
p : H (G, p)  H (G, p)  H ( p)

G is perfect
Csiszár, Körner, Lovász, Marton, Simonyi