Interview with László Lovász

On November 28, 2011, Avi Wigderson interviewed László Lovász. A total of 27 short videos can be watched at the Simons Foundation website. I particularly liked the discussion on the LLL algorithm, and also on semidefinite relaxations.

__________

Related:

• The social construction of Hungarian genius

Digraphs in Haskell

A directed graph (or digraph) is an ordered pair , where is a non-empty finite set of elements called vertices, and is a finite set of elements called arcs, where an arc is an ordered pair of distinct vertices [1]. We call and the vertex set and the arc set, respectively. Note that . For an arc , we call the tail, and the head, and say that the arc leaves vertex and enters vertex .

For instance, consider the digraph depicted below

This digraph has 10 vertices and 15 arcs. How would we build this digraph in Haskell? A vertex could be represented by an integer, and an arc could be represented by an ordered pair of integers. However, in Mathematics we work with sets, whereas in Haskell we work with lists. Hence, we could represent the vertex set by a list of vertices, and the arc set by a list of edges.

Here is a simplistic implementation:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
      (4,5),(5,6),(7,6),(8,1),(8,2),
      (8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

We load this script in GHCi and perform some simple testing:

*Main> -- list of vertices
*Main> vs
[1,2,3,4,5,6,7,8,9,10]
*Main> length vs
10
*Main> -- list of arcs
*Main> as
[(1,4),(1,5),(1,6),(2,4),(3,4),(4,5),(5,6),(7,6),
(8,1),(8,2),(8,7),(9,8),(9,10),(10,2),(10,3)]
*Main> length as
15
*Main> -- digraph
*Main> digraph
([1,2,3,4,5,6,7,8,9,10],[(1,4),(1,5),(1,6),
(2,4),(3,4),(4,5),(5,6),(7,6),(8,1),(8,2),
(8,7),(9,8),(9,10),(10,2),(10,3)])

We have thus created a digraph. What can we do with it? Is there anything of interest that we could compute?

__________

Neighborhoods

Given a digraph , we call the following sets

the out-neighborhood of vertex and the in-neighborhood of vertex , respectively [1]. The vertices in and are called the out-neighbors and the in-neighbors of vertex , respectively.

In Haskell, we compute the out- and in-neighborhoods as follows:

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
                         where p v (t,h) | t == v = True
                                         | t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
                        where p v (t,h) | h == v = True
                                        | h /= v = False

Let us do some testing in GHCi:

*Main> -- list of all out-neighborhoods
*Main> map (outNeighbors digraph) vs
[[4,5,6],[4],[4],[5],[6],[],[6],[1,2,7],[8,10],[2,3]]
*Main> -- list of all in-neighborhoods
*Main> map (inNeighbors digraph) vs
[[8],[8,10],[10],[1,2,3],[1,4],[1,5,7],[8],[9],[],[9]]

 __________

Degrees

Given a digraph , we call the following cardinalities

the out-degree and the in-degree of vertex , respectively [1]. We compute the out- and in-degrees in Haskell as follows:

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

Let us do some testing in GHCi:

*Main> -- out-degrees of all vertices
*Main> map (outDegree digraph) vs
[3,1,1,1,1,0,1,3,2,2]
*Main> -- in-degrees of all vertices
*Main> map (inDegree digraph) vs
[1,2,1,3,2,3,1,1,0,1]

__________

Concluding remarks

Here is the whole Haskell script:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
      (4,5),(5,6),(7,6),(8,1),(8,2),
      (8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
                         where p v (t,h) | t == v = True
                                         | t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
                        where p v (t,h) | h == v = True
                                        | h /= v = False

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

We now know how to create digraphs in Haskell and compute simple things, like neighborhoods and degrees. What else would it be of interest to compute?

__________

References

[1] Jørgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications (2nd edition), Springer, 2009.

Deciding 2-colorability via quantifier elimination

A vertex coloring of a graph is a map that assigns a color to each vertex of . The coloring is proper if adjacent vertices are assigned distinct colors. The graph is 2-colorable if there exists a proper coloring whose color set has two elements.

For instance, consider a graph whose vertex set is and whose edge set is . A pictorial representation of this graph is depicted below

Note that this graph is complete. We can assign two distinct colors to any two vertices, but we cannot assign a color to the third vertex that will yield a proper coloring. Therefore, the graph is not 2-colorable. To illustrate, we use the color set and generate all possible vertex 2-colorings, as depicted below

Notice that none of these 2-colorings is proper, as expected.

As discussed by De Loera et alia [1], the graph vertex-coloring problem can be modeled using polynomial equations. We introduce variables , where if vertex is assigned the color , and if vertex is assigned the color . Given an edge , we have that:

• if both vertices are pink, we get .

• if both vertices are blue, we get .

• if the vertices have distinct colors, we get .

Thus, stating that adjacent vertices must be assigned distinct colors is equivalent to imposing the constraints for all . We thus obtain a system of three equations

where . This is still a combinatorial problem, though. We can transform it into an algebraic-geometric problem. Here is a truly beautiful trick [1]: the constraint can be encoded as with . How quaint!! We then obtain a system of six equations with polynomials in

whose solution set, which we denote by , is algebraic [2]. The given graph is 2-colorable if and only if the system of polynomial equations above is feasible, i.e., if set is nonempty [1]. The following REDUCE + REDLOG script uses quantifier elimination to decide if is nonempty:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
f1 := x1+x2;
f2 := x1+x3;
f3 := x2+x3;
f4 := x1^2-1;
f5 := x2^2-1;
f6 := x3^2-1;

% define existential formula
phi := ex({x1,x2,x3}, f1=0 and f2=0 and f3=0 and
                      f4=0 and f5=0 and f6=0);

% perform quantifier elimination
rlqe phi;

end;

This script produces the truth value false. Thus, the solution set is empty, which means that the system of polynomial equations is infeasible. We conclude that the given graph is not 2-colorable.

__________

References

[1] Jesús De Loera, Jon Lee, Susan Margulies, Shmuel Onn, Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz, 2007.

[2] Jacek Bochnak, Michel Coste, Marie-Françoise Roy, Real Algebraic Geometry, Springer, 1998.