Sunday, October 30, 2005

Terms and Tennis Court Link

Some Useful Terms

A Polytope is different from a Polygon, which is a 2-dim figure. A Polytope is defined by as a Convex Hull of a set of vertices or a Cone of a set of halfspaces.

There are two main objects: a H-Polyhedron and V-Polyhedron. The bounded versions are the H-Polytope and the V-polytope.

Of course, there is the cone, which is the homogenized version of a polyhedron.

More about cones:

A Convex Cone can come in many varieties. A Blunt Cone does not contain the origin, while the origin belongs to a Pointed Cone. If the lineality space of a cone has dimension zero, is said to be pointed.

Direct sum

A theorem: The polar of a pointed cone is blunt and vice versa. Surprise, Surprise, this is a Farkas Lemma!!!!

A course in McMaster's that has amazingly beautiful slides on introduction to Polyhedral theory. It is obviously based on Schrijver's book.

Lattices and stuff:

Matrix decompositions, also the the polylib-lattices link.

A paper on Hermite Normal form. One of the authors wrote the lattices-and-cryptography-book with Goldwasser.

An Affine function is a x --> cx - z for c \in R^d*.
A trace (or trace)
is the weighted sum of the eigen values of the matrix. The weight of an eigen value
being its multiplicity. It is also the sum of the diagonal elements of the matrix. A
graph eigen value
is the eigen value of a graph. This the defn. of graph spectrum .
This link also has some info about the eigen value of a graph.
The Caley hamilton theorem about the
characteristic equation.
Also look up the links from the Characteristic Polynomial
A Hadamard matrix is one that has elements from {-1,+1}.
A Hypergraph is a graph in which the edge set is any subset
from the powerset of the set of vertices (A usual graph is a 2-uniform hypergraph).
According to wolfram, a bigraph is the same as a bipartite graph, which
is possibly incorrect. A bigraph has signs on the edges. The proper definition is this?????? Google of bigraph returns bipartite graphs.
So, we need to check up on the definition.

This is a very good introduction to the Ellipsoid method (PDF link).

tennis court

No comments: