Probabilistic Method – 2

Q.1. Let n \geq 2k be positive integers. Let \mathcal{C} be a collection of pairwise intersecting k-element subsets of [n] = \{1, 2, \ldots, n\}  (i.e. if A, B \in \mathcal{C}, then A \cap B \neq \phi). Prove that |C| \leq { {n-1} \choose {k-1}}.

Solution.

Let A be a k-element subset of [n] selected uniformly at random from the {n} \choose {k} possible such subsets.

Now, Pr[A \in \mathcal{C}] \leq k/n \Rightarrow |C| \leq { {n} \choose {k} } . k/n = { {n-1} \choose {k-1}}.

We will try to prove that Pr[ A \in \mathcal{C}] \leq k/n.

Let A be selected as follows. Take a random permutation \sigma \in \mathcal{S}_n. Take a random index 1 \leq i \leq n, and let A = \{i, \ldots, i + k-1\} (wrapped around n).

Now, if given a fixed \sigma, Pr[ A \in \mathcal{C}| \sigma] \leq k/n, then Pr[ A \in \mathcal{C}] \leq k/n.

Further, since there are at most k possible indices for i such that \{\sigma(i), \ldots, \sigma(i+k-1)\} (wrapping around n) can be a part of \mathcal{C} (due to the property of pairwise intersection), Pr[ A \in \mathcal{C} | \sigma ] \leq k/n.

--

 

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: