Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
Saúl RM's user avatar
  • 9,856
9 votes
1 answer
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, ...
Riemann's user avatar
  • 664
0 votes
0 answers
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$, ...
dohmatob's user avatar
  • 6,764
4 votes
1 answer
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.
Marina Drygala's user avatar
3 votes
1 answer
128 views

Probabilistic method Alon and Spencer Azuma's inequality

Theorem 7.5.2 states: Let $v_1, \dots, v_n$ be vectors with $\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=\|\epsilon_1 v_1 + \...
Marina Drygala's user avatar
4 votes
3 answers
251 views

Existence of (near) equidistant codewords

My question is originally related to coding theory, but fairly easy to state in pure combinatorial way. Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
hookah's user avatar
  • 1,096
2 votes
1 answer
65 views

Why subcopula is less used in modelling?

I don't know if it is a good idea to post my question in MathOverflow instead of Mathexchange. But it seems to me that it is more appropriate to post my question in MathOverflow. By definition, copula ...
InTheSearchForKnowledge's user avatar
0 votes
0 answers
57 views

Counting progressions for Ramsey-type number

I'm currently learning about Ramsey theory and how to use the probabilistic method to find lower bounds. Currently I'm looking at a family, which I'll call $H$, that is composed of the following ...
Jessica's user avatar
1 vote
0 answers
75 views

Probabilistic method with multiple objective functions

Let $\mathcal X$ be a finite set and $f$ a function from $\mathcal X$ to $\mathbb R^+$. Basic probabilistic method says that if I can find a probability distribution on $\mathcal X$ and show that $E[f(...
EEStudent's user avatar
14 votes
3 answers
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 ...
tuna's user avatar
  • 523
2 votes
0 answers
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$. ...
Aditya's user avatar
  • 21
11 votes
2 answers
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 ...
nonuser's user avatar
  • 237
1 vote
1 answer
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}}$ ...
xFioraMstr18's user avatar
0 votes
0 answers
153 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,\...
user avatar
7 votes
2 answers
332 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 $...
Mohammad Golshani's user avatar
3 votes
1 answer
240 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 ...
user avatar
12 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....
8 votes
1 answer
721 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 ...
George Shakan's user avatar
3 votes
0 answers
238 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 ...
Turbo's user avatar
  • 13.7k
33 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
161 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 ...
user avatar
16 votes
1 answer
393 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$? ...
Fedor Petrov's user avatar