Piico의 일상

The Probabilistic Method: An Introduction 본문

수학 (Mathematics)/이산확률 (Discrete Probability)

The Probabilistic Method: An Introduction

Piico 2025. 3. 19. 11:19

The motivation of the probabilistic method is to show the existence of an object. The basic idea is to show that there is greater than zero probability for that object in a probability space S. There are various methods such as the argument with expectation and derandomization. We will talk about them in future sections.
 

a complete graph Kn



In this post we explore how to make a basic argument about the existence of an object (using the concept that showing positive probability implies existence). The object we are about to existence of is the k-clique that has no monochromatic edge-coloring (i.e. its edges are not all of a single color). Recall that a complete graph Kn is a graph where all its vertices are connected to every other vertex.

a sketch of two-coloring of edges of K5, monochromatic K3 and non-monochromatic K3


Theorem 1: If \binom{n}{k}2^{-\binom{k}{2}+1}<1 then it is possible to two-color the edges of a complete graph K_n such that its subgraph K_k's edges have no monochromatic coloring.
 
Don't worry about this term \binom{n}{k}2^{-\binom{k}{2}+1}<1 for now, it will make sense very soon. First, let's begin with a quick warm-up:

  • How many edges does K_n have?
See answers \binom{n}{2} = \frac{n(n-1)}{2}

 
Here are some questions to think about to work toward the proof:

  • How many possible colorings are there for the \binom{n}{2} edges?
  • How many subgraphs K_k of K_n?
  • Let A_i be the event that i is monochromatic. What is the \mathbb{P}[A_i]?
See answers - 2^{\binom{n}{2}} possible colorings
- \binom{n}{k}
- \mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}

 


End of quiz time.
 
Putting all these together, we have:
\mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}
 
By union bound:
\mathbb{P}[ \cup_{i=1}^{\binom{n}{k}}A_i] \leq \sum_{i=1}^{ \binom{n}{k}}\mathbb{P}[A_i] = \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1}
 
By assumption of the theorem, 1- \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1} > 0._{\,⬜}
 
This proof shows the existence of a non-monochromatic K_k, given a two-coloring of the edges of K_n and \binom{n}{k}2^{-\binom{k}{2}+1}<1In the future, we will look at more sophisticated arguments using the Expectation Argument.
 


MU: 6.1