Discrete Math Puzzles - Second Set. July 2, 2003
Instructor: László Babai     Ry-164     e-mail: laci@cs.uchicago.edu

This sheet describes some exercises and projects for independent work. If you are stuck, feel free to send me email, describe your attempt at the problem, ask for a hint. Also, take advantage of the office hours held by the counselors TTh 7-8pm in the ``Theory Lounge,'' Ryerson 162.

procedure Lovász-toggle

1 		 Initialize by coloring each vertex arbitrarily  


2 		 Call a vertex ``bad'' if it has more than the permitted        number of neighbors of its own color 


3 		  BAD := set of bad vertices     


4 		 while BAD
$\neq \emptyset$ 


5 		 		  pick a bad vertex 


6 		 		  recolor it 


7 		 		  update BAD 


8 		 end(while) 

(a)

Prove that this algorithm will terminate in a finite number of steps. (Give a very simple and convincing argument, no more than 5 or 6 lines.) Give an upper bound on the number of cycles of the while loop in terms of the basic parameters $\vert V\vert, \vert E\vert$. Hint. Call the graph with a coloring a ``configuration.'' With each configuration, associate an integer (the ``potential'') in such a way that each round of the Lovász-toggle reduces the potential. This will give a bound on the number of rounds. Note that ``the number of bad vertices'' is NOT an appropriate potential function: it can increase.

(b)

Show that statement (a) becomes false if the degree bound is increased to $r+s+2$. Construct graphs where each vertex has degree $\le r+s+2$ and where

• the algorithm never terminates, regardless of the initial coloring and the choice of bad vertex made in line 5;
• for some initial colorings and some choices of the bad vertex the algorithm will terminate, for others it will not.