Probabilistic Method – 4

Q.1. Prove that there exists a tournament on n vertices having at least \frac{n!}{2^{n-1}} Hamiltonian paths.


A tournament is an orientation of a complete graph. Let each of the n \choose 2 edges be oriented, independently, in either direction with probability 1/2.

Take a random permutation, \sigma of the vertex set of the graph.

Pr[ \sigma \mbox{ represents a Hamiltonian path} ] = \frac {1}{ 2^{n-1}}.

Let X be a random variable denoting the number of Hamiltonian paths.

\therefore E [X] = \frac{n!}{ 2^{n-1}}.


Q.2. Independence number \alpha(G) is the size of a largest independent set of G = (V,E) . Prove that for any  graph G having n vertices, m edges and average degree d = \frac{2m}{n} \leq 1, \alpha(G) \geq \frac{n} {2d}.


Let S \subseteq V be formed by sampling each vertex of G, independently, with probability p. Let X denote the number of vertices in S, and Y, the number of edges in the subgraph G[S] induced by S.

\therefore E[X] = np \mbox{ and } E[Y] = m p^2 = \frac{1}{2} n d p^2.

\therefore E[X- Y] = np(1 - dp/2).

\therefore There exists a subset S \subseteq V such that the difference between the number of vertices in S and the number of edges in G[S] is at least np(1-dp/2).

Remove a vertex for each edge in G[S] until the resultant set is an independent set. (This procedure removes at least as many edges as vertices.)

Set p =1/d.

\therefore There exists an independent set of size at least \frac{nd}{2}.


One Response to Probabilistic Method – 4

  1. Pingback: Probabilistic Design ebook : Cars Blog | Everything You should Know about Cars

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: