Probabilistic Alterations

Probabilistic methods are extremely useful in combinatorial problems to prove an existence of certain configurations. The general approach is to take a finite probability space of configurations then to apply linearity of expectations to find the expected value of some random variable. This likely non-integral expected value is used to come up with configurations with or without certain probability. In particular, the method of alterations are used to remove blemishes that originate from the uniform choice of configuration by removing some elements from the chosen set according to some prescribed rule. We demonstrate this idea via a simple lower bound on off-diagonal Ramsey numbers.

Proposition 1.

$R(k, l) \ \geq \ n - \binom n k p^{-\binom k 2} - \binom n l p^{-\binom l 2}$ for any integer $n$ .

proof. Choose an arbitrary coloring of $K_n$ where each edge is colored red by a probability $p$ and blue by probability $1 - p$ . Let $R_A, B_B$ be indicator random variables for vertex subsets $A, B$ each of size $k, l$ respectively. The variable $R_A$ is 1 if the subgraph induced by $A$ is a red $K_k$ and zero otherwise. Same goes for $B_B$ . Define the random variable $X$ as the number of monochrome red $K_k$ s or $K_l$ s in an arbitrary coloring. Using linearity of expectation, it is straighforward to deduce

$\mathbb E[X] \ = \ n - \binom{n}{ k} p^{-\binom {k} 2} - \binom n l p^{-\binom l 2}\)$

for any integer $n$ . From this expected value, extract some coloring with $\mathbb E[X]$ number of monochrome $K_k, K_l$ then remove a single vertex from each complete monochrome subgraph. The resulting graph has a coloring that has no monochrome $K_k, K_l$ and has at least

$n - \binom n k p^{-\binom k 2} - \binom n l p^{-\binom l 2}$

verticies, which concludes the proof. □

Applications of alterations need not be confined in discrete probability spaces. We explore the application of the method in Combinatorial Geometry. Consider a subset of points $S$ in a unit square in $\mathbb R^2$ . $T(S)$ is defined as the area of the smallest triangle that can be drawn from three points in the set $S$ . For an integer $n$ , define $T(n)$ as the maximum value of $T(S)$ over all sets $|S| = n$ . It can be verified that $T(5) = 1/4$ .

Proposition.

$T(n) \ = \ \Omega (1/n^2)$

proof. We make two claims. First,

$\mathbb P[\Delta PQR < \epsilon] \ \leq \ 16\pi \epsilon$

i.e. the probability that a randomly chosen triangle has area less than a threshold value is linearly dependent on the threshold. Secondly, given a choice of $2n$ points in the unit square, it is possible to remove less than $n$ squares to obtain a set of points which none of the three points form a triangle that has an area greater than $1/(100n^2)$ .

To verify the first claim, find the probability of choosing a base $PQ$ of length b. Using elementary calculus, we deduce $\mathbb P[PQ = b] = 2 \pi b$ . The height can range from zero to $2\epsilon /b$ . Thus, for a fixed choice of $P, Q$ , the choice of $R$ lies on a tube of width $4\epsilon/b$ around the line segment. Integrate over all possible $b$ ‘s and bound the choice of $R$ from above.

$\mathbb P[PQR < \epsilon] \ \leq \ \int_0^{\sqrt 2} db (2 \pi b) \sqrt 2 \frac{4 \epsilon} b \ = \ 16 \pi \epsilon$

Now, fix $\epsilon = 1/(100n^2)$ and count the number of triangles that have area less than this threshold. Call this random variable $X$ . Upon invoking linearity of expectation,

$\mathbb E [X] \ = \ \binom {2n}{3} \mathbb P[PQR < 1/100] \ \leq \ \frac{8n^3}{6} (0.6) n^{-2} \ \leq \ n$

so it is possible to come up with $2n$ points such that there exists less than $n$ triangles of area under the threshold. From this configuration, remove each point from each triangle and some more arbitrary points to obtain $n$ points that form no triangle of area under the threshold. This proves

$T(n) \geq 1/(100n^2)$

which gives the desired bounds. □

Remark. One important principle entailed in this proposition is that sometimes it is useful to take more objects than necessary. We needed a set of $n$ points. By choosing alterations as a method of attack, it is reasonable to start with more points, i.e. $2n$ , and remove $n$ of them to come up with the desired configuration.

Reference: The Probalistic Method, Noga Alon math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMethod3ed.pdf

Comments

Leave a Reply Cancel reply