Questions tagged [probabilistic-method]

Probabilistic methods prove existence results in a nonconstructive fashion, by showing the chance of randomly selecting a solution is greater than zero.

256 questions
Filter by
Sorted by
Tagged with
27 views

Intersection of Shifted Subsets of $\mathbb{Z}_n$

This question is taken from the example sheet in the description of this video. Let $\mathbb{Z}_n$ be the set of integers mod $n$, and for a subset $A \subseteq \mathbb{Z}_n$ and $x \in \mathbb{Z}_n$,...
70 views

Queens and kings in a round table

i have this question in probability. i tried to solve it a lot of times but i dont know how to do it. THE QUESTION: Around a round table are arranged 2n numbered chairs. n pairs of king and queen ...
49 views

52 views

339 views

Is this a strict Lower bound on the amount of numbers less than x but coprime to y?

Let $\Lambda(x,y)$ be the relative totient function that counts the amount of numbers less than $x$, which are coprime to $y$. After interpreting Euler's totient function, $\phi(y)$, as a result of ...
32 views

Show $0.35\left(\frac{2 a}{c}\right)^{a /(a-1)} \exp \left(-\frac{2}{a-1}\right) \frac{c}{2a} \to 0$, for $a(n)\geq 1.1, c(n)=$ $o(a n^{1-1 / a})$.

I’ve just got back to study some probabilistic graph theory, so I’m not sure how to deal with proving the following lemma. Lemma. Let $a=a(n), c=c(n)$ be functions of $n$ such that $a(n) \geq 1.1$ ...
73 views

Help in probabilistic proof of the Caro-Wei theorem

While studying Turan's theorem, I would like to ask about some parts of this proof. I am weak at probability, so unless I spread and open everything up and formalize, I would not be able to understand....
This question is from Tao and Vu's book, Exercise 1.1.7., which is part of the chapter "The probabilistic method". The problem is: Problem. Consider a nonempty subset $A$ of finite abelian ...