# 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.

22 questions
Filter by
Sorted by
Tagged with
92 views

### Can we find background noise for every Følner sequence in a countable amenable group?

Let $G$ be a countable amenable group. We consider sequences $(z_g)_{g\in G}$ of complex numbers with $|z_g|=1$ for all $g\in G$. I will say $(z_g)_{g\in G}$ is background noise for a (left-)Følner ...
• 9,856
457 views

### Quantum probabilistic method?

The probabilistic method uses arguments from probability to prove deterministic statements. This has been applied to diverse fields such as combinatorics, topology and number theory. In this method, ...
• 664
98 views

### Phase-transitions for a property of random bipartite graphs

Let $N_1$, $N_2$, and $k$ be positive integers. Let $V_1$ and $V_2$ be finite sets with $|V_i| = N_i \ge 1$. Consider a bipartite graph $G=(V_1,V_2,E)$ constructed as follows. For every $x \in V_1$, ...
• 6,764
147 views

### For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours

Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
128 views

845 views

### Theorems like the Lovász Local Lemma?

The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent. What other theorems exist in this genre? That is, what other theorems have ...
• 523
174 views

### On an exercise in The Probabilistic Method : random dilate of a set in a finite field

This is related to Problem $4.6$ in The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following: Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
• 21
596 views

### Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond. Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets ...
• 237
1 vote
228 views

### $\lim_{k\to\infty}{n\choose k}2^{1-{k\choose2}}$, where $n=\max\{n\in\mathbb{N}:{n\choose k}2^{1-{k\choose2}}<1\}$

How do you prove $\lim_{k\to\infty,k\in\mathbb{N}}{n\choose k}2^{1-{k\choose2}}=1$, where $n=\max\{n\in\mathbb{N}:{n\choose k}2^{1-{k\choose2}}<1\}$? The expression ${n\choose k}2^{1-{k\choose2}}$ ...
• 276
Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$. What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are \mbox{ subsets }L_1,L_2,\...