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
0 votes
0 answers
21 views

Bounding d-regular graph traversal length for every starting node and every traversal

Question: (Past exam question i'm using to revise) Let $G = (V,E)$. A connected d-regular graph. Let $v_1 \in V$. Assume that at each node, the ends of the edges incident with the node are labelled $1,...
Willow's user avatar
  • 1
0 votes
0 answers
31 views

$G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges

I want to show that with probability converging to $1$, $G(n,1/2)$ has a bipartite subgraph with at least $n^2+Cn^{3/2}$ edges for some positive constant $C$. The hint for this is to use a greedy ...
Anon's user avatar
  • 515
5 votes
1 answer
40 views

Existence of disjoint paritions of $\mathbb{Z}_m$

For any integer $m \in \mathbb{N}$, let $\mathbb{Z}_m$ denote the integers modulo $m$. For any two subset $A, B \subset \mathbb{Z}_m$, and $x \in \mathbb{Z}_m$, denote $s(A,B,x) := \vert \{(a,b) \mid ...
total dependent random choice's user avatar
0 votes
1 answer
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, ...
swjj's user avatar
  • 1
1 vote
1 answer
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 ...
Alex Scruton's user avatar
5 votes
1 answer
98 views

Combinatoric and subsets

I recently encountered a question Let $n \in \mathbb{Z} ^+$, Let $U$ be a set containing $n$ elements. Let $\mathcal{S} \subseteq P(U)$. Let $m \in \mathbb{Z}^+, m \leq n$. Prove that $$ |\mathcal{S}| ...
welly's user avatar
  • 113
1 vote
0 answers
33 views

The Probabilistic Method exercise 2.7.7

Let $\mathbf{F}$ be a family of subsets of N = {1,2,...,n}, and suppose there are no $A, B \in \mathbf{F}$ satisfying $A \subset B$. Let $\delta \in S_n$ be a random permutation of the elements of N ...
Yuqi LU's user avatar
  • 11
1 vote
1 answer
146 views

Need help understanding some proof examples

I tried asking r/learnmath twice and got no replies unfortunately, so I'm going to repost it here: These are example proofs from Proofs by Jay Cummings, so I'm not sure if I need to 'show work' ...
wyboo's user avatar
  • 45
1 vote
1 answer
69 views

Closed Set in Product Topology

I am trying to understand the Compactness Argument in a Graph Theory Problem using Probabilistic Methods. $V$ is infinite set. For each finite subset $X \subset V$, let $C_X \subset [2]^V$ be the ...
tom_choudhurry's user avatar
0 votes
0 answers
36 views

Proof of existence of independent set given partition of vertices in a random graph

I'm unsure of how to solve the following question. Intuitively, I am considering using an FKG inequality by creating some increasing and decreasing sequences, but I'm having trouble formalising it. ...
J K's user avatar
  • 1
0 votes
0 answers
41 views

upper bound the number of 5-cycles in a random graph

Let $k$ be the number of edges of a graph $G$, I’d want to show that $G$ can contain at most $(2k)^\frac{5}{2}$ cycles of length $5$. I thought about showing this for the Erdös-Renyi graph model $G(2k,...
whatisaring's user avatar
1 vote
0 answers
42 views

Boolean Satisfiability: Probabilistic Method

I'm currently take a non-credit course in extremal combinatorics and this question is given as an exercise for the Lovasz Local Lemma. It follows directly from the symmetric version of the lemma if ...
Renrael Htam's user avatar
0 votes
0 answers
59 views

Vectors and probabilistic method

I've seen task Probabilistic method proof and I've come up with some questions (problems) I understand how to solve Probabilistic method proof problem Now I am interested in the following questions: ...
jirraffe's user avatar
1 vote
1 answer
57 views

Connections in a graph using probabilistic method problem

There are n people in a city and each person has 1000 friends (friendship is mutual - if A is a friend of B, then B is a friend of A). Prove that it is possible to choose a group S of people such that ...
jirraffe's user avatar
1 vote
0 answers
30 views

is the assumption If X⊥⊥Y | Z and X⊥⊥Y then (X⊥⊥Z or Y ⊥⊥Z) true? [duplicate]

is the assumption If X⊥⊥Y | Z and X⊥⊥Y then (X⊥⊥Z or Y ⊥⊥Z) true ? where X⊥⊥Y means is independent of Y and X⊥⊥Y means that X is independent of Y given Z? I have been trying to prove or disprove the ...
MproBoss's user avatar
0 votes
0 answers
29 views

Prove that the discarded eigenvalues should be adjacent in Probabilistic PCA

I've been trying to understand Probabilistic PCA and I got stuck on the following equation that tries to find what should the discarded eigenvalues be $$\mathcal{L} = -\frac{N}{2}\left\{d \ln(2\pi)+\...
Chirag Mehta's user avatar
1 vote
0 answers
49 views

Arithmetic Triangle Removal Lemma

Here is the problem: Here is my approach: I attempted the following: I constructed a graph on $[N]=\{1,\cdots,N\}$, adding an edge between $a,b$ in $[N]$ iff $|a-b| \in A.$ Then each $(x,y,x+y) \in A^...
Kai Wang's user avatar
  • 713
0 votes
1 answer
166 views

Prove that every k-uniform hypergraph with n vertices and m edges has a transversal of size at most n(log k)/k + m/k. [closed]

Let me know if there's a similar question but I couldn't find any. This question is from the course on probabilistic methods. I have tried several approaches, but none has seemed to converge to a ...
Eran723's user avatar
  • 99
0 votes
0 answers
32 views

Show that the number of edge-disjoint triangles is Poisson-distributed

Let $G(n,p)$ be the binomial random graph with vertex set $[n]$. Let $E_k$ denote the event that $G(n,p)$ contains some collection of $k$ edge-disjoint triangles. Show that $\mathbb{P}[E_k] \leq \frac{...
PepeHands's user avatar
2 votes
1 answer
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 ...
PepeHands's user avatar
1 vote
0 answers
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 ...
DIexp's user avatar
  • 150
1 vote
0 answers
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)$$ ...
Ishigami's user avatar
  • 1,609
3 votes
0 answers
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. ...
ratatouille's user avatar
2 votes
2 answers
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....
weekendwarrior's user avatar
2 votes
1 answer
48 views

How do I verify that these two bounds imply another which uses asymptotic notation (probabilistic graph theory)?

I am trying to read The Probabilistic Method (for leisure, not for school) by Alon and Spencer, and I am having trouble seeing why a particular step is true: In chapter 1 they prove that If ${n \...
weekendwarrior's user avatar
4 votes
1 answer
141 views

Coloring arithmetic progression

I've been looking at some old notes from the course Probabilistic Combinatorics and I saw the following question: Prove that there exists a constant $N$ and a red/blue coloring of $\mathbb{Z}$ ...
DIexp's user avatar
  • 150
2 votes
0 answers
122 views

51 points are inside a unit square. How do I prove that a circle with radius 1/7 can always cover 3 of them without using the Pigeonhole Principle?

I looked at this page: 51 points lie inside an square of side 1.Prove that it's possible to draw a circle of radius $\frac17$ covering at least 3 of theses points Instead of using the Pigeonhole ...
py_math's user avatar
  • 302
0 votes
1 answer
49 views

existence of a subset with specific properties

P({1,2,...,n}) is the power set of the set {1,2,...,n}. F $\subset$ P({1,2,...,n})$\setminus${∅} but not P itself. it is known that $$\sum_{f \in F} \frac {1}{2^{|f|}} \le\frac{n}{logn}$$ I need to ...
noam alon's user avatar
2 votes
0 answers
75 views

Proof for existence and size of set $B$, that does not include any subset $f$ from collection $F$.

I'm trying to solve the following question: Let $\mathcal{F}\subset\mathcal{P}\left(\left\{ 1,\ldots,n\right\} \right)\backslash\left\{ \emptyset\right\}$ a collection of non-empty subsets of $\left\{ ...
Tuxedo's user avatar
  • 21
-4 votes
2 answers
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 ...
user_12345's user avatar
0 votes
0 answers
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 ...
chelslou's user avatar
4 votes
1 answer
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 ...
Kai Wang's user avatar
  • 713
5 votes
1 answer
103 views

Probabilistic coin weighing [duplicate]

Let $S_1, \ldots, S_k$ be subsets of $\{1, \ldots, n\}$ with $k \leq 1.99 \frac{n}{\log_2(n)}$, prove that there are two distinct subsets $X,Y$ of $\{1, \ldots, n\}$, such that for all $1 \leq i \leq ...
zimba bwe's user avatar
0 votes
1 answer
149 views

Variant of Bollobas' Two Family Theorem

Problem: Let $A_1,\cdots,A_m$ be sets with size $r$ and $B_1,\cdots,B_m$ be sets with size $s$. Suppose $A_j\cap B_j=\emptyset \forall j=1,\cdots,m$ and for each $j\ne k$, at least one of $A_j\cap B_k,...
Kai Wang's user avatar
  • 713
1 vote
0 answers
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 ...
Azermatt's user avatar
0 votes
1 answer
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.
laura's user avatar
  • 121
2 votes
0 answers
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 ...
darko's user avatar
  • 1,243
3 votes
1 answer
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 ...
STN's user avatar
  • 31
1 vote
1 answer
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 ...
Jeff Bass's user avatar
  • 221
1 vote
0 answers
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$ ...
AspiringMat's user avatar
  • 2,447
1 vote
1 answer
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 ...
Anish Ray's user avatar
  • 857
1 vote
1 answer
110 views

Sufficient condition for a hypergraph to be 2-colorable

Let $H=(V,E)$ be a hypergraph with the property that each edge has at least $k \ge 2$ vertices. Show that if for each edge $e$ of $H(E)$ holds $$ 8 \sum_{j \ge k} \frac{d_{e,j}}{2^j} \le 1$$ where $...
3nondatur's user avatar
  • 4,182
0 votes
1 answer
68 views

A version of an algorithm for an "uniform" subset sum problem?

Let $l_1,\cdots,l_n \sim U(0,1)$ be i.i.d uniform variables. Given $L>0$ a natural number, let us define the "uniform" subset sum problem as: Find $I \subset \{1,\cdots,n\}=:[n]$ such ...
mathoverflowUser's user avatar
1 vote
1 answer
163 views

Existance of bipartite $K_{2,2}$- free graph

The problem I'm dealing is the following: Prove that for each $n$ exists a bipartite graph without $K_{2,2}$ subgraph and $\Omega(n^{4/3})$ edges. I wanted to solve this using probability: Start with ...
Jova's user avatar
  • 433
2 votes
1 answer
64 views

Prove that there are two sets of vectors with the same summation.

I'm stuck on the following problem: Seeing as it's from chapter 4 of "The Probabilistic Method", the proof has to be by the first or second-moment method. I've tried to model the problem ...
ThighCrush's user avatar
2 votes
1 answer
105 views

Proof that if $np - \log n \rightarrow c$ the probability that $G(n,p)$ is connected goes to $e^{-e^{-c}}$ using Janson's inequalities

I am interested in showing that in the Erdõs-Rényi random graph $G(n,p)$ for $p = p(n)$ satisfying $np - \log n \rightarrow c \in \mathbb{R}$ the probability of $G(n,p)$ being connected goes to $e^{-e^...
empty set's user avatar
4 votes
1 answer
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(...
user265131's user avatar
1 vote
0 answers
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 ...
Vezen BU's user avatar
  • 2,098
2 votes
1 answer
148 views

Probability of a game never ending [closed]

The game rules are simple. You take one fair coin and flip it. You start counting how many times did you get heads and how many times did you get tails. When the number of tails equal the number of ...
user avatar
0 votes
0 answers
60 views

Existence of a pair of isomorphic subgraphs in a given graph with large number of edges

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, ...
Drill_zoo's user avatar
  • 321

1
2 3 4 5
7