This is the place for general Q&A (things that don't fit to the other pages).Edit


Q: What is the square root of 2?

A: 42.

What are you learning towards the exam:

Memorizing the Local Lovasz Lemma?

Learning proofs by heart?


Solutions for practice questions:

Q1. Polynomial time algorithm for finding MIS in a series parallel graph

A1. Maintain in each vertex in the TD a 6X2 matric:

column 1 - for all (TW=2 => |bag|<=3 => 6) options of vertices being in/out from the IS

column 2 - for the size of the IS using this vertex configuration

rest is like the coloring example given in class. (return the max size in the root, r)

which coloring example? can you specify more?

Q2. Give a poly time algorithm that given a graph G and an edge (i,j) in G returns a n-2Xn-2 matrix that its determinant is the amount of STs containg (i,j)

A2. ST = spanning tree

\#ST(G) - #ST(G\{(i,j)}) = amount of ST of G - amount of spanning trees without (i,j) = amount of ST containing (i,j).

Claculate the difference above => X

Return diagonal matrix M (n-2Xn-2), M(1,1)=X and M(x,x)=1 (x!=1) => |M| = X as requested.

Q3. ...

CORRECTION to the original problem: The cut should contain \alpha*d*(n/2) edges and not \alpha*d as written (Uri confirmed this as a mistake).

split the vertices of G to V1 and V2 according to the cut.

set x=(1,1,1,1...,1,-1,-1,-1,...-1) (amount of 1s is |V1| and amount of -1s is |V2|).

bound on lambda'n is really similar to the one in Hoffman's theorem.

Second part -

In the first part we got that if there is a large cut, \lambda_n < \epsilon-d. That means that if |\lambda_n| =O(\sqrt{d}), then there is no large cut in the graph.

Random graphs are "nearly regular" :)

That means |\lambda_n| =O(\sqrt{d}) (and in fact this holds for all eigenvalues except for the largest). So in "nearly regular" graphs there is no large cut.

A possible heuristic for a refutation is, given a random graph, approximating \lambda_n well enough.

Q4. ...

S = all rows of M

F = all subsets of elements from S that form together independent sets.

(S,F) is a matroid:

Heredetary - if X is in F then every subset of it is also an ind-set of rows => in F.

Matroid: if |X|>|Y| and X and Y in F -> due to linear algebra we can move at least one element from X to Y which is independent from all Y.

So a greedy algorithm in which you prder the items (rows in M) by their "amount of zeros" and consider them one by one should work.