12
votes
Accepted
Theorems like the Lovász Local Lemma?
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein ...
- 128k
6
votes
Accepted
Quantum probabilistic method?
The Hilbert-Polya approach to the Riemann hypothesis follows this path, by attempting to relate the zeroes of the Riemann zeta function to a quantum mechanical scattering problem. The probability ...
- 188k
6
votes
Domination problem with sets
Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.
Stage 1. Take maximal subfamily $\mathcal{A} \subseteq
\{S_1,....,S_k\} =:\mathcal{S} $ such that:
$\...
- 237
4
votes
Domination problem with sets
59k/140 sets suffice
Using your three equations, it is possible to get an improved upper bound of $59k/140$ (instead of $3k/7 = 60k/140$).
$$12a+8b+4c \leq 3k$$
$$ a+4b+2c \leq k$$
$$ a+b+4c \leq k$$...
- 193
4
votes
Accepted
$\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\}$
Let $N(k) = \max \{n \in \mathbb N: \; {n \choose k} 2^{1-{k\choose 2}} < 1 \}$.
Note that $$\frac{{n+1 \choose k}}{{n \choose k}} = \frac{n+1}{n+1-k}$$
so it suffices to prove that $N(k)/k \to \...
- 54.2k
4
votes
Accepted
Existence of (near) equidistant codewords
$\beta$ cannot be too much larger than $1/2$;
namely we must have $\beta \leq k/(2k-2)$.
To prove this, identify the $x_i$ with vectors $v_i \in {\bf R}^n$
each of whose coordinates is $1$ or $-1$,
...
- 79.9k
4
votes
Accepted
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
Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below).
For each colour $i \in [n]$, let $a_i$ be the number of vertices incident to an edge of ...
- 32.1k
3
votes
Accepted
Probabilistic method Alon and Spencer Azuma's inequality
$\newcommand\ep\epsilon$The martingale $(X_i)$ is given by the formula
$$X_i:=E(X|\ep_1,\dots\ep_i).$$
By the independence of the $\ep_i$'s,
$$X_i=g_i(\ep_1,\dots,\ep_i),$$
where
$$g_i(t_1,\dots,t_i):=...
- 128k
3
votes
Set theoretic forcing, large cardinals and probabilistic methods
Random real forcing is naturally connected with probability and measure theory, in an essential way, since the generic real that is added by the forcing has all the Borel properties that hold with ...
- 237k
3
votes
What are fun elementary subjects in probability?
A quincunx (balls dropping through what is typically a triangle of nails, creating a roughly binomial distribution) is fun to watch. Real ones are extremely sensitive to errors in the locations of the ...
3
votes
Theorems like the Lovász Local Lemma?
Here's a connection that I found interesting.
A positive solution to the Kadison-Singer problem would follow from a positive solution to a stronger conjecture I called ${\rm KS}_2$ (and the eventual ...
- 42.8k
2
votes
Theorems like the Lovász Local Lemma?
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or ...
- 196
2
votes
Set theoretic forcing, large cardinals and probabilistic methods
Today I saw the following paper in which probabilistic arguments are used in a forcing argument:
Halfway New Cardinal Characteristics.
See the proof of 3.4. The paper is written by Jörg Brendle, ...
- 32.2k
2
votes
Existence of (near) equidistant codewords
Following up on Noam's answer: for $k = 3$ I think the bound is even tighter, $\beta \leq 2/3$.
If $d(x,y), d(y,z) > n(\frac{2}{3} + \epsilon)$, then if we define $A = \{i \ : \ x_i \neq y_i\}$ and ...
- 2,621
2
votes
Why subcopula is less used in modelling?
The complication when using subcopulas to model estimations is that the domain of the subcopula depends on the marginal distribution functions, it is unknown and has to be estimated from data. In ...
- 188k
1
vote
Existence of (near) equidistant codewords
The problem is more involved than I thought [deleted my non answer]. The comments below may or may not help you:
In the book Combinatorics of Symmetric Designs by Ionin and Shrikande, Binary ...
- 10.4k
Only top scored, non community-wiki answers of a minimum length are eligible