Phase transition homework

1.  Let  be a random subset of  of size k.  Consider the property P that  contains a 3-term arithmetic progression. Show that  is a threshold for property P.

2.  Create exercise on Su Doku

 1 2 4 6 3 6 9 2 6 4 5 [2] 7 5 2 4 8 3 7 4 8 6 9 8 2 8 6 4 3 5 1 6 9 3 7 1

Possible solution:  Fill in Su Doku  matrix with a completed solution.  Then starting with a blank Su Doku matrix randomly select a square and copy the number for that square from the completed solution.  No matter how many squares are filled in there is always a valid completion.  What is the expected number of squares until there exists a unique completion?  This is an increasing property hence there is a threshold.  What if you had enter the number at random, when would there be no valid solution?.

Generalize Su Doku to a , , and in general  table with  sub squares.

3.  Let  be the multi set formed by drawing pn integers from the set  with repetition.

a)  How large must p be in order to have some integers appear twice?

b)  Does a sharp transition occur?

c)  How large must p be in order for every integer to occur in ?

d)  How does the frequency of occurrences of integers evolve with increasing p?

4.  For a random CNF formula with n variables how many satisfying assignments are there as the number of variables increases?

5.  In  what is the threshold for a) perfect square, b) perfect cube, c) even number, d) three numbers such that x+y=z

6.  Modify the proof that every monotone property has a threshold for sets of integers to work for a) G(n,p)    b) 3-CNF SAT.

7.  The threshold property seems to be related to uniform distributions.  What if we considered other distributions.  Consider a model where i is selected with probability . Is there a threshold for perfect squares? Is there a threshold for arithmetic progressions?

8.  Explain why the property that  contains the integer 1 has a threshold.  What is the threshold?

9.  Birthday problem.  Consider the set of integers .  Fix a subset S of size s(n) by selecting elements of  uniformly at random.  What is probability that S will contain a duplicate?  Show that a phase transition occurs at .

10.  Consider G(n,p).

a) Where is phase transition for 3-colorability?

b) For vertex cover?

11.  Is there a condition for a sharp threshold?

12.  Select n points in .  For small n all points lie in some half space. For large n they do not.  What is the threshold?

13.   Think up some neat exercises.

14.  In class for N(n,p) we claimed that there were order n squared arithmetic progressions of length k.  Work this out carefully.  Likewise we claimed that there were n cubed pairs of arithmetic progression of length k that overlapped in one element and n squared that overlapped in two.  Work this out carefully

Projects

1.  Consider randomly generating a CNF formula with a fixed number of variables.  As the number of clauses increases the probability of there being a satisfying assignment decreases.  Non satisfiability is an increasing property and thus there is a threshold.  For small number of clauses there are efficient algorithms to find a satisfying assignment.  However, some time before the phase transition there is a region where the formula is almost surely satisfiable but no efficient algorithm for finding the assignment exists.  Apparently what happens is that early on the set of satisfiable assignments is a connected region.  Then there is a region where the set of satisfiable assignments fragments into many disconnect solutions.

a) Do a literature search and write an overview of this area.

b) Find a way to present this material that is understood by a bright high school student.

2.  Consider graph 3-colorability.  Randomly generate the edges of a graph and compute the number of solutions and the number of connected components of the solution set as a function of the number of edges generated.  What happens?

3.  Develop an intuitive understanding of why every monotonic property has a threshold.

References

Dimitris Achlioptas and Federico Ricci-Tersenghi, “On the Solution-Space Geometry of Random Constraint Satisfaction Problems”