Wednesday, July 06, 2005

separating hyperplanes for unitary graphs

Taking the clue from CM-Z about the ZC problem into, (1) finding a hyperplane that separates and (2) partitioning the graph using the hyperplane, we solve the problem (1) in faster time, using an oracle.
--
Theorem on convex polytopes: Two closed, convex, disjoint sets can be separated by a hyperplane.
Yes, but how to find in fastly when the distances are in the range {-1,0,+1} ideas: do a recursive separation?
--
Important theorem on convex polytopes: A convex polytope is the sum of a polytope and a cone.
--
When we unitarize, we get some kind of patterns in the incidence matrix(top part of B). What is it?
--
Questions about KMW-EX-577: What is special about edges e2 and e4, the ones from v1 to v2 and back again? What makes them disappear? How are they weakly connected? What makes edges e1 and e3, the self loops, stay? When we draw the vectors on a 2-dim hypercube, which happens to be a square, e2 and e4 are parallel (anti parallel to be precise) and are the maximal number of vectors that can form a ZC. Is this because, we are maximizing the the set of vectors that can stay for next level of decomposition?
--
Construct an example where there are 2 edges which are antiparallel in one direction like {(1,-1),(-1,1)} and another set of edges (say 3) which are anti-parallel in another direction like {(1,1),(-1,-1)(1,1)}. What will the KMW return?
--
KMW notes: page 586-587, example 10, fig9 and page: 587, example 11, fig-10. KMW generate two schedules, the free schedule and smoothened schedule.
--
To do: Write the duals of the KMW-EX and get the polygons.
To-do: Prove Conjecture: get the hyperplane which passes through the origin and is parallel to the maximum number of hyperplane. This vectors that are not parallel to this hyperplane are weakly connected. So, It seems that a sort (bucket sort?? in linear time???) of the dependence vectors invariant to the a change of sign, which means that (1,-1) and (-1,1) map to the same bucket, is all is required.

To do: Verify conjecture for a two PRDGs: one that is easy to reason and one that is complicated that the algorithm finds one.
--
When we look at the columns of the matrix B and ask when are two columns linearly dependendent and how can you maximize the dependent edges?
--