Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
26 views

Varshamov-Gilbert, question about proof with probabilistic method

Let $d \in \mathbb{N}$ such that $d \equiv 0 \pmod{4}$, and take $S_1, \dots, S_d \sim Bernoulli(0, 1)$. Define for $v \in \{0,1\}^d$ the ball $B(v, d/2) = \{w \in \{0,1\}^d : \|v - w\|_1 \leq d/2\}$....
0
votes
1answer
68 views

Round table and microphones, a pigeonhole problem [closed]

20 people are sitting around a table. 9 of them want to give a speech, and there are 9 microphones on the table in front of 9 random people. The microphones are fixed but we can turn the table.How can ...
0
votes
1answer
10 views

Bound on the tail of a Poisson branching process

I'm trying to understand this argument from "The Probabilsitic Method" book: Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] =...
1
vote
1answer
29 views

There is probability $O(p^k)=O(n^{-k})$ that $C(v)$ has more than $k-1$ edges?

In this proof from "The Probabilistic Method" by Alon and Spencer, p.206, they argue that if $v$ is an aribtrary vertex with connected component of size $k$, then there is probability $O(p^k)=O(n^{-k})...
0
votes
0answers
12 views

Expected iterations of finding a non-repetitive sequence

I am working on problem 8 in chapter 5 of The Probabilistic Method and I couldn't solve the second half of it. Problem: For every $n\ge1$ and every sequence of lists of symbols $L_1,L_2,..., L_n$, ...
0
votes
1answer
32 views

Kraft-McMillan inequality probablistic proof

I'm studying probabilistic methods at the moment and i saw this problem which i can not provide a probabilistic proof for it. I would be really thankful if someone could provide me with that. Let $...
2
votes
1answer
117 views

Past exam question: probabilistic method

Let $G=(V,E)$. We want to give for each vertex $v$ in $V$ a number $f_v$ s.t. for every vertex we have $$ (\sum_{v: (u,v)\in E} f_v)+f_u \not \equiv 0 \mod{(n+1)}$$ Let A be the following algorithm ...
3
votes
1answer
98 views

Expected minimum number of transpositions to sort permutation

For a permutation $\pi$, let $S(\pi$) be the minimum number of transpositions required to sort the elements in increasing order. Show that for a random permutation $\pi \in S_{10001}$ $E[S(\pi)] ≥ ...
0
votes
0answers
14 views

One opportunity, many stakeholders : which model to distribute one to many based on frequencies

I'm facing a situation where one sales opportunity can be the result of one or many stakeholders involved in its negotiations. I'm trying to model how much of an opportunity as unit/value has to be ...
4
votes
0answers
90 views

monotone subsequences of permutation

Prove that the number of permutations of $\{1, ..., n\}$ containing a monotone increasing or decreasing subsequence of length at least $3\sqrt{n}$ is $o(n!)$. (Hint: pick a random permutation, and ...
0
votes
1answer
81 views

Probability that we choose even edges for a vertex

We choose each edge in a graph $G$ (with $m$ edges) at random independently with probability $p\in[0,1]$. What is a probability that we chose an even number of edges at the vertex $v$ which has degree ...
1
vote
2answers
78 views

Ramsey number finding constant

Let $K_n$ denote a complete graph with $n$ vertices. Given any positive integers $k$ and $l$, the Ramsey number $R(k, l)$ is defined as the smallest integer $n$ such that in any two-coloring of the ...
1
vote
0answers
21 views

A negative correlation property in a random matrix

I am trying to prove the following negative correlation property. (where neither FKG or the BK inequality apply) Any input/idea is much appreciated: Suppose each row of an $n\times n$ matrix is ...
4
votes
1answer
127 views

Prove that we can divide a group of 90 people into 3 groups each with 30 people so that everyone has a friend in group

Prove that we can divide a group of 90 people into 3 groups each with 30 people so that each has a friend in group if each one has more than 30 friends. Friendships is a symmetric relation. I tryed ...
0
votes
0answers
31 views

Minimum number of edges in a graph for which adding any new edge increases the number of copies of $K_{10}$. [duplicate]

Question 5 from The Probabilistic Method by Alon and Spencer. Let $G$ be a graph on $n\geq 10$ vertices such that the addition of any edge not yet in $G$ increases the number of copies of $K_{10}$ in ...
0
votes
0answers
28 views

Given graph $G$ that is “close” to another graph $G'$ can we find certain bipartite subgraph of $G$

Suppose that $G$ is a graph with $2n$ vertices and $n^2$ edges. Let $\epsilon>0$. We say that $G$ is $\mathbf{\epsilon-close}$ to $K_{n,n}$ if $$\frac{|E(G)\triangle E(K_{n,n})|}{\binom{2n}{2}} \...
7
votes
1answer
111 views

Prove that there exists a row or a column of the chessboard which contains at least √n distinct numbers.

On each cell of an $n \times n$ chessboard, we write a number from $1, 2, 3, . . . , n$ in such a way that each number appears exactly $n$ times. Prove that there exists a row or a column of the ...
1
vote
1answer
74 views

Show that under certain conditions on $n$ and the minimum outdegree, a directed graph must contain an even cycle.

This is a question from the book Probabilistic Methods in Combinatorics, question 4 in chapter 3.7. I have been struggling with it for some time now but I do not want to just look up the solution, so ...
1
vote
1answer
21 views

Question about a condition of the asymmetric Lovasz Local Lemma

As I've gathered from numerous explanations of the asymmetric Lovasz Local Lemma (ALLL), the ALLL is a generalization of the notion that if a collection of independent events is such that each event ...
2
votes
1answer
61 views

Intuition behind using probabilistic method to find complete bipartite subgraph

Problem 6 of 2008 Iran TST is as follows: Let $T$ be a directed complete graph with $801$ vertices. Prove you can find two disjoint set of vertices $L, R \subset V_T$ with $|L| = |R| = 7$ such ...
1
vote
1answer
36 views

Computing the expected number of overlapping committee members

Here is the problem, which comes from the probabilistic method section of Introduction to Probabilty. A group of 100 people are assigned to 15 committees of size 20,such that each person serves on ...
0
votes
1answer
82 views

Maximum $n$ such that ${n \choose k} \,2^{1 - {k \choose 2}} < 1$ (where $k$ is a constant)

Maximum value of $n$ such that the expression given below does not exceed 1. ($k$ is a constant) $${n \choose k} 2^{1 - {k \choose 2}} < 1$$ Any hints on how to approach this problem. Thanks. ...
2
votes
1answer
48 views

Deviating from the mean +-1 variables

I stumbled across the following exercise (the book Probability and Computing): Let $b_1, b_2, \cdots b_{m/2}$ all equal 1 and $b_{m/2 + 1}, \cdots, b_m$ all equal $-1$. We now pick $Y_1, \cdots, Y_m$ ...
1
vote
1answer
58 views

Theorem of Hardy & Ramanujan - second moment Method

I am trying to understand the second moment method proof of the following theorem: Let $\omega(n)\rightarrow\infty$ arbitrarily slowly and $\vartheta(x)$ the number of primes which divide $x$. Then ...
1
vote
0answers
55 views

Finding threshold for Erdos-Renyi random graph to be connected using branching process

I know the usual method of showing that an Erdos-Renyi random graph $G(n,p)$ is connected is by letting $X_k$ be the random variable counting the number of connected components on $k$ vertices and ...
1
vote
2answers
383 views

Expected number of hamiltonian paths in a tournament

The following theorem is from Alon&Spencer's The probabilistic method, in the beginning of chapter 2: Theorem 2.1.1: There is a tournament $T$ with $n$ vertices and at least $\frac{n!}{2^{n-1}}$ ...
2
votes
1answer
46 views

Why a randomly chosen element of a class satisfying property `p`, implies existence of an element of said class that satisfies `p`?

I guess I understand that if a randomly chosen element has zero probability of satisfying p (the negation of the conditional), then it does not necessary mean no ...
2
votes
1answer
79 views

$\frac{N}{n}$; probability

Here is an interesting identity: $$(n\leq N)~\dfrac{N}{n}=1+\dfrac{N-n}{N-1}+\dfrac{(N-n)(N-n-1)}{(N-1)(N-2)}+\cdots+ \dfrac{(N-n)(N-n-1)\cdots 2\cdot 1}{(N-1)(N-2)\cdots (n+1)n}. $$ I failed to ...
4
votes
1answer
80 views

Clique numbers and Theorem 4.5.1 in “The Probabilistic Method” by Alon and Spencer

My question is "What is the precise formulation of the following theorem from Alon and Spencer's book The Probabilistic Method?" For context, Let $G(n,1/2)$ be the probability space of random graphs ...
1
vote
0answers
59 views

Translating an Arithmetic Progression in $\mathbf Z/p\mathbf Z^*$, how much Overlap is Possible?

Let $n$ be an integer and $p>n$ be a prime. Assume for simplicity that $p-1$ is divisible by $n$, and that $p-1=nk$. Let $a$ be a member of $(\mathbf Z/p\mathbf Z)^*$ and assume that $a\neq 1$. I ...
2
votes
1answer
34 views

Proving lower bound of row/column occurencies of numbers in 2D n-element grid

I need to solve the following problem: Given $n \times n$ grid of numbers from $1$ to $n$ where each number occurs in a grid exactly $n$ times, prove that there exists a row or column which ...
2
votes
0answers
84 views

Proof by probabilistic method for coins on chessboard puzzle

Here's a puzzle I worked through a while ago: Alice and Bob are in prison, and the warden poses the following game. Alice will be lead alone into a room with an 8x8 chessboard. The warden will place ...
0
votes
1answer
51 views

The probabilistic method with a network graph

This is a question from a course about probabilistic methods in combinatorics. Let a network be represented by a graph G (each user is represented by a vertex and every communication route between ...
1
vote
1answer
100 views

The probabilistic method

Let $G = (V,E) $ be a finite graph. For any set $ W $ of vertices and any edge $e \in E $, define the indicator function $$ I_W(e) = \begin{cases} 1 , &\ e \textrm{ connects } W \textrm{ and } W^...
1
vote
1answer
294 views

Distance between two vertices picked at random from random graph.

Given random undirected and unweighted graph $G = \langle V, E\rangle$ and random queries consiting of picking two vertices $u, v$ at random how to find the shortest path from $u$ to $v$? Is there ...
0
votes
1answer
44 views

Expected number of multipled edges multihypergraph

I have a graph G of n vertices and with a k-list color assignment for each vertex out of $\sigma$ colors. If a choose at random all k colors for each list assignment I can model this with a k-uniform ...
2
votes
0answers
104 views

Lower bound on sizes of “sum” and “product” of a set of real numbers

The problem is like this: Let $A$ be a finite subset of $\mathbb{R}$. Define $A+B = \{ a+ b \mid a \in A,\ b \in B\}$ and $A\cdot B = \{a \times\ b \mid a\in A, \ b\in B\}$ Prove that $$|A+A|\cdot|...
1
vote
1answer
38 views

Separating a set with pairs of subsets whose size is constrained

There are two problems I am trying to solve. The first is a special case of the second, but I shall include it anyway as it possibly provides some insight. Let $0<\lambda\le 1$ and let $X$ be a ...
2
votes
1answer
57 views

existence of $(K,\alpha)$-disperser with degree $D=O(\log\frac{N}{K})$

A bipartite graph $G=(V_1=[N],V_2=[M],E)$ is a $(K,\alpha)$-disperser if for every $X\subseteq V_1$ of cardinality $K$, $|\Gamma(X)|>(1-\alpha)M$. That is, every large enough set in $V_1$ misses ...
2
votes
1answer
69 views

A graph with a few number of edges has a big subgraph with low degree vertices

Suppose $G$ is a graph that $|E(G)| \leq \epsilon |G|^2$, prove that there is $H \subset G$ such that $|H| \geq |G|/2$ and for all $v \in H$ we have $d_H(v) \leq 4 \epsilon |H| $. $|G|$ is the ...
0
votes
1answer
115 views

Looking for a mild introduction to probabilistic methods.

TL,DR: I am looking for an introductory text in probabilistic methods that are suitable for an undergraduate student who has not taken Analysis/Algebra level classes. Below is the detail. I am a ...
1
vote
2answers
75 views

Probabilistic proof: why are we allowed to work with an “arbitrary” probability?

Let $G = (V,E)$ be a graph with $n$ vertices and $e$ edges. Then $G$ contains a bipartite subgraph with at least $e/2$ edges. The proofs starts like this: Let $T \subset V$ be a random subset ...
3
votes
2answers
185 views

How might we approach Collatz Conjecture by probabilistic method?

How might we approach Collatz Conjecture by probabilistic method - or similar? I was thinking along the following lines. Suppose we select some integer at random. What is the expected value of the ...
0
votes
0answers
69 views

Mantel's Theorem on $G(n,p)$.

I want to prove the following theorem: With high probability, every subgraph $G\subset G(n,1/2)$ with $$e(G)\geq \left(\frac{1}{2}+\epsilon\right)\frac{n^2}{4}$$ contains a triangle. I think ...
1
vote
2answers
184 views

Find the smallest constant (China TST 2015)

For a positive integer $n$, and a non empty subset $A$ of $\{1,2,...,2n\}$, call $A$ good if the set $\{u\pm v|u,v\in A\}$ does not contain the set $\{1,2,...,n\}$. Find the smallest real number $c$, ...
4
votes
2answers
287 views

Graph theory in disguise?

There are $2n-1$ two-element subsets of set $\{1,2,...,n\}$. Prove that one can choose $n$ out of these such that their union contains no more than $\frac{2}{3}n+1$ elements. I was trying this one ...
12
votes
1answer
951 views

Domination problem with sets

Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets of $M$, satisfying: (1) $|S_i|\leq 3,i=1,2,...,k$ (2) Any element of $M$ is an element of at least $4$ sets among $S_1,....,...
5
votes
1answer
213 views

Every $Ck$-diregular-graph contains $k$ vertex-disjoint even dicycles

I'm looking for a reference (or proof) for the following claim: Let $D$ be a directed graph whose outdegrees and indegrees are all equal to $Ck$. Then there are $k$ vertex-disjoint cycles of even ...
10
votes
0answers
421 views

Covering of the plane by the grid squares

Consider the covering of the plane by the grid squares, that is, by the unit squares whose vertices are the grid points. Prove that there is an absolute constant $C > 0$ so that for every $0.1 &...
4
votes
1answer
154 views

How to determine the weights in the asymmetric Lovasz Local Lemma

The application of the asymmetric Lovasz Local Lemma requires finding a weight function $x$ on the bad events satisfying the property in the link. Often, one uses a constant weight function, giving ...