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.
329 questions
2
votes
0
answers
52
views
Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph
Show that every n-uniform non 2 colorable hypergraph $H$ contains atleast $\frac{n}{2} {2n-1 \choose n-1}$ unordered pairs of edges each overalapping at exactly 1 vertex. I came across this problem in ...
2
votes
0
answers
62
views
Every k-fold cover of the real line by intervals can be decomposed into k distinct covers.
A k-fold cover of the real line is a family of sets such that each point is contained inside atleast k sets in the family.
I am trying to prove the following fact which i came across in Yufei Zhao's ...
1
vote
0
answers
40
views
Understanding the combinatorial bound choice in a covering argument (Vershynin's HDP)
I'm studying Roman Vershynin's High-Dimensional Probability and am working through Corollary 0.0.4, where he constructs an epsilon-net for a polytope $P$ via averages of vertices. Here's what confused ...
- 21
0
votes
1
answer
226
views
A proof of Rolle's theorem using an uniform distribution
I want to know if the following proof is correct or not. Is this proof known in the literature? Thank you very much for your reply.
Rolle’s Theorem: Let $f:[a,b]\to\mathbb{R}$ be such that $f\in C^1\...
- 1,155
0
votes
1
answer
101
views
The Probabilistic Method, exercise 2.7.9
This is Exercise 2.7.9 from "The Probabilistic Method" by Noga Alon and Joel Spencer. It's stated as follow:
Let $G = (V, E)$ be a bipartite graph with $n$ vertices and a list $S(v)$ of ...
- 468
2
votes
0
answers
76
views
topics in probabilistic group theory
I'm a graduate student interested in probabilistic group theory, particularly applications of probability to finite groups beyond commuting probabilities and word maps. I’ve explored topics like gap ...
0
votes
0
answers
52
views
Erdős-Spencer bound on size of covering designs
Theorem 13.4 in "Probabilistic Methods in Combinatorics" by Erdős & Spencer (1974) states that
$$M(n,k,\ell) \le \frac{{n \choose \ell}}{{k \choose \ell}} \big( 1 + \log {k \choose \ell} ...
- 945
1
vote
1
answer
102
views
Ex 13.6.5 of 'The Probabilistic Method 4th' written by Alon-Spencer. Where's my mistake?
I saw this problem Probabilistic methods
and I tried to solve it.
Let $n>cm\sqrt{\ln m}$ where $c$ is a large constant. For $1\leq i\leq n$, let $\overrightarrow {u_i}\in\mathbb{R}^m$ with $\|\...
- 1,334
2
votes
2
answers
182
views
Chromatic number of a graph with prohibited cliques
How can I bound the maximal possible chromatic number of a graph $G$ with $N$ vertices, such that $\omega(G)≤\kappa$ (where $\omega(G)$ is clique number)?
I can pretty simply prove that for any ...
- 47
1
vote
1
answer
71
views
How does the explanation of this overestimation here work?
I am reading about count-min-sketch which for the implementation is based on a 2 dimensional array to store the frequencies.
The width of the array (the number of columns) is calculated by $$\frac{e}{\...
- 1,737
0
votes
0
answers
115
views
Tournament on n vertices that has property $S_k$ [duplicate]
A tournament is an orientation of the edges of a complete graph. We say that a tournament has property $S_k$ if for every set of $k$ players there is one who beats them all. We are able to prove that ...
- 285
0
votes
1
answer
118
views
Probabilistic Method to construct a low intersecting family of sets
I have a question to the following exercise I found in this book:
If I understand the hint correctly, we construct some set $S_i$ by going through each element of the "universe" $\{1, ..., ...
- 35
1
vote
1
answer
118
views
An inequality of a sum
This inequality is from equation $\left(\bf 20\right)$ in this paper.
$\ell \geq 1$ is a variable related to the big O notation below.
$\gamma := \lfloor \log_{0.9}(1/l)\rfloor + 1$.
For $i \geq 1$, $\...
- 29
0
votes
1
answer
71
views
Comparison of two crossing number inequalities
Let $G$ be a simple graph with $n$ vertices and $m$ edges. The crossing number of $G$, denoted by $cr(G)$, is the minimum number of crossings in a planar embedding ...
- 469
2
votes
0
answers
138
views
Asymptotic upper bound on independence number in random graph
currently I'm learning about random graphs, and struggle with the following result, which is supposed to be well known. Nonetheless I couldn't find a proof of this, and I'm stuck proving it myself:
...
- 621