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

315 questions
Filter by
Sorted by
Tagged with
21 views

23 views

### Probabilistic Transversals in Hypergraphs

This is a result from Noga Alon's 1990 paper, "Transversal Numbers of Uniform Hypergraphs". In section 3: $\,H = (\,V,E\,)$ is a random $k$-uniform hypergraph on a set $V$ of $n$ vertices, ...
• 1
1 vote
59 views

### Prove for $0 < p \leq 1/9$ that $p\cdot\prod_{k=1}^n(1-(1-p)^k)\geq e^{-3/p}$

This is part of a proof that I saw in lectures but the lecturer quickly skipped any calculation and just stated this result. It's not obvious to me that this must be true from the formula, although ...
98 views

• 119
1 vote
49 views

81 views

### Residue classes of size $k^2$ intersect interval size $O\left(p/k\right)$ in $\mathbb{Z}_p$

I encounter this problem in Noga Alon's book and I have been struggling to solve it: Prove that there exists a constant $C > 0$ such that for every $A \subset \mathbb{Z}_p$ where $|A| = k^2$, there ...
1 vote
28 views

### choosing points in grid such that every small rectangle contains a point

I've started reading the article "ɛ-nets and simplex range queries" and I found a weaker claim that i've been told can be proved more easily: Prove that there is a constant $C > 0$ so ...
• 150
1 vote
68 views

### Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $1-|A\cap (B+x)|/|Z|\leq(1-|A|/|Z|)(1-|B|/|Z|)$

Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $$1-\frac{|A\cap (B+x)|}{|Z|}\leq \left(1-\frac{|A|}{|Z|}\right)\left(1-\frac{|B|}{|Z|}\right)$$ ...
• 1,609
92 views

### Producing even cycles in directed graphs - Alon and Spencer, Exercise 3.4

Show that there is a finite $n_0$ such that any directed graph on $n>n_0$ vertices in which each outdegree is at least $\log_2(n)-\frac{1}{10}\log_2\log_2n$ contains an even simple directed cycle. ...
74 views

### Question about convex optimization with binomial coefficients

I don't have any experience with optimization other than some very basic problems from elementary calculus, but I want to understand a particular claim from Alon and Spencer's The Probabilistic Method....
48 views

• 21
122 views

### Obtaining deterministic information from probability theory [closed]

A simple but very useful fact that constitutes the basis of the probabilistic method is the following: if an event $A$ has positive probability, then it can't be empty: there should exist at least one ...
• 358
39 views

### How do the conditional probabilities work in the main proof of the general Lovasz Local Lemma without a non-zero probability condition?

In the proof of the Lovasz Local Lemma (general case), we want to prove that $Pr \left[ \bigwedge_{i = 1}^{n} \bar{A_i} \right] \ge \prod_{i=1}^{n}(1 - x_i) > 0$. The proof uses a helper lemma ...
131 views

### Graph with large minimum degree can be union of few complete (bipartite) graphs

Problem: Let $G$ be a bipartite graph with $n$ vertices on each side and minimum degree $n-d$. Show that it can be written as the union of $O(d\log n)$ complete bipartite graphs. My approach with ...
• 713
103 views

• 713
1 vote
89 views

### Lovasz local lemma and chernoff bound

I am really stuck when it comes to solving the problem below. I think I should use Lovasz's local lemma symmetric version but I don't really know how? I don't know how to find the probability of the ...
• 31
29 views

### How to prove that a function is unitarily invariant

I am struggling to prove the following, any hints or solutions are very welcome. I have really no idea whee to start. Thank you very much.
• 121
67 views

### random generation of lie algebras

It is well known that a nonabelian finite simple group, say $\mathrm{PSL}_n(\mathbf{F}_p)$, can be generated by two elements. In fact, the probability that two elements generate it tends to $1$ as the ...
• 1,243
68 views

### Is it necessary to use a uniform distribution in the probabilistic method?

In the probabilistic method, I often see we define a sample space and sample the elements of the sample space uniformly at random and use it to prove something exists. For example, in the proof of a ...
• 31
1 vote
61 views

### Clarification on a step in Erdős's probabilistic proof for the lower bound of Ramsey Numbers?

Generally I understand this argument, but I would like a more complete proof that the "best chance" you'll get at finding a complete monochromatic subgraph is if we treat each complete ...
• 221
1 vote
77 views

### Showing a $3$-regular $K_4$ free graph has a bipartite subgraph with at least $(7/9) m$ edges using probabilistic method.

Question: Given $G(V,E)$, a $3$-regular $K_4$ free graph. Show that $G$ has a bipartite subgraph with at least $(7/9) m$ edges. My attempt: Since $G$ is $3$-regular and $K_4$ free, it is $3$ ...
• 2,447
1 vote
64 views

### Why is $\sum_{m=1}^{n}\frac{(\nu(m)-\log\log n)^2}{n\log\log n}=\int_{-\infty}^{\infty}\omega^2\, \mathrm{d}\sigma_n(\omega)$?

I was reading an article on Probabilistic Number Theory by M.Kac where I am not able to understand why a particular equation mentioned here in page $657$ equation $(7.7)$ is true? I do understand that ...
• 857
1 vote
110 views

152 views

### Expected value in probabilistic method

I am asked to prove the following statement: For every connected, undirected and simple graph $G=(V,E)$, one can can always find a vertex $v\in V$ such that \sum_{x\in\Gamma (v)}\frac{\deg(x)}{\deg(...
• 434
1 vote
48 views

### Sort a group of distributions

Given a group of $n$ probability distributions, $P_1, P_2, \ldots, P_n$, we sample an outcome for each of the distributions $X_i \sim P_i, \forall i \in [n]$, and we want to compute the probability of ...
• 2,098
I am trying to show that a graph $G$ with $n$-vertices and $pn^2$ edges ($n\geqslant10$, and $p\geqslant10/n$) contains two vertex-disjoint and isomorphic subgraphs with at least $ap^2n^2$ edges, ...