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

**2**

votes

**0**answers

101 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$. ...

**8**

votes

**2**answers

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

**2**

votes

**0**answers

48 views

### General SLLN-like asymptotic mean concentration

Disclaimer: As I am not very knowledgeable of the field to which this question pertains, I will introduce a temporary terminology to convey the idea of my question at the risk of conflicting with ...

**1**

vote

**1**answer

125 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}}$ ...

**0**

votes

**0**answers

143 views

### A Non-trivial intersecting set system problem

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,\...

**7**

votes

**2**answers

292 views

### Set theoretic forcing, large cardinals and probabilistic methods

This question is motivated by the work of Ajtai "The complexity of the pigeonhole principle" and similar works. In this paper, the author proves that $PHP_n$, the pigeonhole principle for $n,$ does ...

**3**

votes

**1**answer

222 views

### An extremal combinatorics problem involving column summation

Given $n\in\Bbb N$, $\alpha>0$, $\beta\in\big[\frac12,1\big]$ denote $\mathcal R_{n,\alpha,\beta}$ as collection of all $2^n\times 2^{n^\alpha}$ $0/1$ matrices with every row summing to strictly ...

**13**

votes

**12**answers

2k views

### What are fun elementary subjects in probability?

I have to read several lectures on probability or applications of probability for high school students (of high level). There is no necessary part I must lecture, that is, my aim is just advertisement....

**7**

votes

**1**answer

441 views

### Does $|A+A|$ concentrate near its mean?

Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...

**3**

votes

**0**answers

190 views

### Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time.
(1) Is there any ...

**31**

votes

**7**answers

2k views

### List of proofs where existence through probabilistic method has not been constructivised

The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show ...

**1**

vote

**1**answer

143 views

### Assigning random orientation to an edge in a regular graph

Given a simple regular graph of degree $d$ on $n$ vertices.
Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random ...

**16**

votes

**1**answer

316 views

### Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others

What are known estimates for maximal $M$ for which their exists subsets $A_1,\dots,A_M$ in $\{1,\dots,n\}$ such that there do not exist different indexes $i,j,k$ for which $A_i\subset A_j\cup A_k$?
...