Probabilistic Method – 4
February 10, 2011 1 Comment
Q.1. Prove that there exists a tournament on vertices having at least Hamiltonian paths.
A tournament is an orientation of a complete graph. Let each of the edges be oriented, independently, in either direction with probability .
Take a random permutation, of the vertex set of the graph.
Let be a random variable denoting the number of Hamiltonian paths.
Q.2. Independence number is the size of a largest independent set of . Prove that for any graph having vertices, edges and average degree , .
Let be formed by sampling each vertex of , independently, with probability . Let denote the number of vertices in , and , the number of edges in the subgraph induced by .
There exists a subset such that the difference between the number of vertices in and the number of edges in is at least .
Remove a vertex for each edge in until the resultant set is an independent set. (This procedure removes at least as many edges as vertices.)
There exists an independent set of size at least .