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
0answers
27 views

Intersection of Shifted Subsets of $\mathbb{Z}_n$

This question is taken from the example sheet in the description of this video. Let $\mathbb{Z}_n$ be the set of integers mod $n$, and for a subset $A \subseteq \mathbb{Z}_n$ and $x \in \mathbb{Z}_n$,...
0
votes
0answers
70 views

Queens and kings in a round table

i have this question in probability. i tried to solve it a lot of times but i dont know how to do it. THE QUESTION: Around a round table are arranged 2n numbered chairs. n pairs of king and queen ...
2
votes
0answers
49 views

$G$ contains two disjoint independent sets $A, B$ so that $|A| + |B| \geq 2\sum_{i=1}^n \frac{1}{d_{i}+1}$ where $d_{i}$ is degree of vertex $v_{i}$

Let $G$ be a graph on $n$ vertices with degrees $d_{1} \geq d_{2} \geq ...\geq d_{n} \geq 1$. Then, $G$ contains two disjoint independent sets $A, B \subset V, A \cap B = \emptyset$ such that $|A| + |...
2
votes
1answer
33 views

How to generate a random preference relation on a finite set uniformly?

A preference relation (total preorder, weak order) on a set $S$ is a binary relation $ \precsim $ on $S$ that satisfies: completeness: for any $x, y \in S$, either $x \precsim y$ or $y \precsim x$ ...
0
votes
0answers
22 views

Probabilistic Method for Boolean code

I have thought about the question for a long time but have no idea of how to solve it. It is a question that I found on the Advanced Algorithm. I thought it may involves Chernoff bound or Dimension ...
1
vote
0answers
56 views

Prove there are at least $2$ lines with the property that each of them divides the plane into $2$ regions with the same number of red and blue points. [duplicate]

Let $n \geq 2$ a natural number, and $2n$ points chosen in plane, $n$ red points and $n$ blue points. There are no $3$ collinear points among the $2n$ points in plane. A 'good' line is a line that ...
1
vote
1answer
35 views

What even is a vertex Lipschitz condition?

I am re-reading parts of the probabilistic method by Alon and Spencer. On page 100 it says A graph theoretic function $f$ satisfies the vertex Lipschitz condition if whenever $H$ and $H'$ differ at ...
1
vote
1answer
26 views

Probability of $K_{a, b}$ being monochromatic

I am studying Alon-Spencer's The Probabilistic Method, and theorem 2.3.2 reads: $\exists$ a 2-coloring of $K_{m, n}$ with atmost ${m \choose a}{n \choose b}2^{1-ab}$ monochromatic $K_{a,b}$ Now while ...
1
vote
1answer
25 views

Probability of hamming distance smaller or equal than d of two strings with k 1-bits

Let two bit-strings of size $n$ have $k$ number of $1$-bits. If the first bit-string has the form $1^k0^{n-k}$ (for $n=5$ and $k=2$ the bit-string would look $11000$) and the second bit-string is ...
3
votes
2answers
578 views

Moment Generating Function (MGF) of Hypergeometric Distribution is No Greater Than MGF of Binomial Distribution with the Same Mean

The Setup Consider a hypergeometric distribution $X$ with parameters $N, n, m,$ i.e. $$\mathbb{P}[X = k] = \frac{{m \choose k} {N-m \choose n-k}}{{N \choose n}},$$ for $k$ running from $0$ to $\min\{n,...
2
votes
1answer
52 views

Alon and Frankl Disjoint Pairs

I am trying to read through Alon and Frankl's 1985 paper "The maximum number of disjoint pairs in a family of subsets". Let $\mathcal{F}$ be a family of $m=2^{(1/2+\delta)n}$ subsets of $X=\{...
1
vote
0answers
60 views

Is Jensen's inequality being used in the conclusion of the proof of the Vapnik-Chervonenkis inequality?

I am trying to resolve some compilation queries that arose in parsing the proof of the Vapnik-Chervonenkis inequality, and would appreciate some assistance on clarifying a particular step. The proof ...
1
vote
0answers
29 views

Number of triangles in an $(n, n / 2,2 \sqrt{n})$-expander

Prove that for every $\epsilon>0$ there exists an $n_{0}=n_{0}(\epsilon)$ so that for every $(n, n / 2,2 \sqrt{n})$ - graph $G=(V, E)$ with $n>n_{0}$, the number of triangles $M$ in $G$ ...
1
vote
1answer
68 views

Show that $G_{n,p}$ does not contain a certain subgraph.

LEMMA. Let $a=a(n), c=c(n)$ be functions of $n$ such that $a(n) \geq 1.1$ and $c(n)=$ $o\left(a n^{1-1 / a}\right) .$ Then, for $p(n)=c(n) / n, G(n, p)$ a.s. contains no subgraphs with $s$ vertices, $...
2
votes
1answer
339 views

Is this a strict Lower bound on the amount of numbers less than x but coprime to y?

Let $\Lambda(x,y)$ be the relative totient function that counts the amount of numbers less than $x$, which are coprime to $y$. After interpreting Euler's totient function, $\phi(y)$, as a result of ...
0
votes
0answers
32 views

Show $0.35\left(\frac{2 a}{c}\right)^{a /(a-1)} \exp \left(-\frac{2}{a-1}\right) \frac{c}{2a} \to 0$, for $a(n)\geq 1.1, c(n)=$ $o(a n^{1-1 / a})$.

I’ve just got back to study some probabilistic graph theory, so I’m not sure how to deal with proving the following lemma. Lemma. Let $a=a(n), c=c(n)$ be functions of $n$ such that $a(n) \geq 1.1$ ...
1
vote
2answers
73 views

Help in probabilistic proof of the Caro-Wei theorem

While studying Turan's theorem, I would like to ask about some parts of this proof. I am weak at probability, so unless I spread and open everything up and formalize, I would not be able to understand....
3
votes
1answer
36 views

Estimation of order of sum-covering subset

This question is from Tao and Vu's book, Exercise 1.1.7., which is part of the chapter "The probabilistic method". The problem is: Problem. Consider a nonempty subset $A$ of finite abelian ...
1
vote
0answers
95 views

An interesting combinatorial property

For an integer $n$, let $[n] = \{1,\cdots,n\}$. A family $N$ of subsets of $[n]$ , i.e. $N\subset 2^{[d]}$ is said to have Property B(i,j) if the following holds: For every $I,J\subset [n]$ such that $...
2
votes
2answers
80 views

Probabilistic Method: the size of largest induced triangle-free subgraph of $G(n, 1/2)$ is $\Theta(\log(n))$?

It's a related homework from the MIT course Probabilistic Methods in Combinatorics (the text book is The Probabilistic Methods by Alon and Spencer, but this exercise is not from the original book): ...
0
votes
2answers
59 views

Exercise 6.5.2 of the Probabilistic Methods(4th Edtion) by Alon and Spencer

A family of subsets $\mathcal{G}$ is called intersecting if $G_{1} \cap G_{2} \neq \emptyset$ for all $G_{1}, G_{2} \in \mathcal{G}$. Let $\mathcal{F}_{1}, \mathcal{F}_{2}, \ldots, \mathcal{F}_{k}$ be ...
0
votes
0answers
36 views

How to understand the $o(1)$ notation in the note by Zhao for the Probabilistic Method book?

In Zhao's note(page 86) for Noga Alon's Probabilistic Methods: Remark 8.1.4. When $\mathbb{P}(A_i)=o(1)$, Harris inequality gives us $$ \mathbb{P}(X=0)=\mathbb{P}\left(\bar{A}_{1} \cdots \bar{A}_{k}\...
1
vote
1answer
84 views

Question about Posa rotation.

I’m reading a text that discusses Posa rotation, which is defined as follows. Given a graph $G$ and a vertex $x_{0} \in V(G)$ suppose that $P=x_{0} x_{1} \ldots x_{k}$ is a longest path in $G$ ...
1
vote
0answers
23 views

Threshold for the existence of a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{n,p}$.

Let $\frac{0.35\text{log}n}{n} \leq p \leq \frac{2\text{log}n}{n}$. Show that w.h.p there does not exist a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{...
5
votes
1answer
62 views

The Probabilistic Method: proving existence of functions satisfying certain property

Let $\mathcal{X}$ be a subset of $\mathbb{R}^n$ and let $\mathcal{F}$ be a space of functions: $$\mathcal{F} = \{f | f: \mathcal{X} \to \mathbb{R} \}$$ Let $P_\mathcal{X}$ be a probability ...
1
vote
1answer
71 views

A problem about probabilistic method

Prove that there exists a constant $0<c \leq 1$ such that, if we put $2^{n}$ distinct closed unit balls in $\mathbb{R}^{n}$, each centered at $\{-1,1\}^{n}$, then every hyperplane containing the ...
1
vote
1answer
49 views

Relationship between the random graph models $G_{n,k}$ and $G_{n,p}$.

This is an excerpt from “Introduction to Random Graphs” by Frieze and Karoński We start with an empty graph on the set $[n]$, and insert $m$ edges in such a way that all possible ${n \choose 2} \...
2
votes
1answer
52 views

Relation between $k$ and $n$ in Alon and Spencer, 4th Edition, Section 10.3

On page 184, in section 10.3 of Alon and Spencer (The Probabilistic Method, 4th Edition), line -8, it is written: "Then $$n = \sqrt{2}^{k(1+o(1))}, ..."$$ At this point in the text, what is this ...
1
vote
1answer
33 views

Horizontal crossing of a random subgraph of an $n\times m$ grid.

Consider the $m\times n$ ($m$ wide $n$ tall) grid $G_{m,n}$, and let $H_{m,n}$ be a random subgraph, where each edge of $G_{m,n}$ is an edge of $H$ independently with probability $\frac{1}{2}$. A ...
0
votes
2answers
33 views

Probability of two sets being contained in a set $S$.

I'm working on the following problem, and I'm afraid there is something fundamental I am not understanding. Let $s_1,\dots,s_m$ be independent random elements in $[n]$ not necessarily uniform or ...
2
votes
1answer
62 views

Edge coloring so that each cycle contains at least 3 colors.

I'm trying to use the Lovász local lemma to prove the following. Every graph with maximum degree $\Delta$ can be edge-colored (no two adjacent edges have the same color) using $O(\Delta)$ colors so ...
0
votes
0answers
24 views

Explicit construction for achievability in Shannon's noisy channel coding theorem

The existence direction in Shannon's second theorem states: for a noisy (discrete memoryless) channel $(\mathcal X, p(y\vert x), \mathcal Y)$ with channel capacity $C$, all rates $R< C$ are ...
5
votes
2answers
188 views

Transposition Distance between two permutations.

I'm working on the following problem. Suppose that $A \subseteq S_n$ is a subset of at least $n!/2$ permutations, and let $A(t)$ be the set of permutations that can be obtained from starting at some ...
2
votes
1answer
79 views

A problem of permutations using the probabilistic method.

If found this problem in the book "The probabilist method" of Alon and Spencer: Prove that there is an absolut constant $c>0$ with the following property: let $A$ be a $n\times n$ matrix ...
2
votes
2answers
50 views

Non-periodic paths of length 4 in a graph and the Lovasz Local Lemma

Let $G$ be a graph with maximum degree $\Delta$ and consider colouring its edges, each with one of $k$ colours. A path $v_0v_1v_2v_3v_4$ in a $G$ is $\textit{periodically coloured}$ if $v_0v_1$ and $...
5
votes
1answer
127 views

there exists a $c>0$ such that every $3$-regular bipartite graph is a $(2n,3,c)$-expander

Definition: A graph $G = (V, E)$ is called an $(n, d, c)$-expander if it has $n$ vertices, the maximum degree of a vertex is $d$, and, for every set of vertices $W \subset V$ of cardinality $|W| \le n∕...
4
votes
1answer
117 views

Is there a logic with quantifier "almost always".

I would like to describe a reasoning with quantifier "almost always". For example, if probability of $Z$ is above $95$%, I would like to say that $Z$ is "almost always true". Is ...
2
votes
1answer
84 views

hint on a solved old exam question on probabilistic methods calcualation

In my note I have some previous exam solved question as follows in Probabilistic methods section: Example: We have $k$ classes $C_1, C_2,...,C_k$ where each $C_i$ has uniform distribution over $-(2^{...
1
vote
1answer
56 views

$\epsilon$-regular pair of vertex sets definition

Introducing Szemeredi's Regularity Lemma requires the definition of $\epsilon$-regularity, which I cannot get good intuition for, because the official intuition clashes with, well let me explain. ...
9
votes
2answers
171 views

there is a positive constant $c$ such that for any $n$ real numbers $a_i$ with $\sum a_i^2=1$, $\mathbb P[|\sum \epsilon_i a_i|\le1]\ge c$

Question (4.8.2 from the Probabilistic Method 4th edition by Alon and Spencer): Show that there is a positive constant $c$ such that for any $n$ real numbers $a_1,\dots,a_n$ satisfying $\sum\limits_{i=...
4
votes
1answer
193 views

three-uniform hypergraph on $n$ vertices with at least $n/3$ edges contains an independent set of size at least $\frac{2n^{3/2}}{3\sqrt{3m}}$

Here is question 3 from chapter 3 Part 1 of The Probabilistic Method, 4th edition. Prove that every three-uniform hypergraph with $n$ vertices and $m \ge n∕3$ edges contains an independent set (i.e., ...
3
votes
1answer
301 views

off diagonal Ramsey number (4,k) lower bound probabilistic method asymptotic reasoning

I want to show that $R(4,k)\ge\Omega((k/\ln k)^2)$, where $R(4,k)$ is the Ramsey number. This question is quite close to what I'm after, the asymptotic part is only missing (and they talk about $3$ ...
0
votes
1answer
104 views

Show that any graph has an independent set of size at least $\frac{n^2}{2m+n}$

I am trying to show that any graph with n vertices and m edges has an independent set of size at least: $$\frac{n^2}{2m+n}$$ I have already shown that any graph has an independent set of size at least:...
0
votes
1answer
32 views

Prove that there exist a set $ S⊆V $ for a graph G which contains a matching M, such that there are $ frac{|E|+m}{2} $ between S and V\S

Let $ G =(V,E)$ be a graph. Suppose that G contains a Matching M consisting of m edges. I have to prove that there exists a set $ S⊆V $ such that there are at least: $ \frac{|E|+m}{2} $ edges between ...
1
vote
2answers
142 views

Exercise 2.7.5 of the probabilistic method

Let $H$ be a graph, and let $n > |V(H)|$ be an integer.Suppose there is a graph on $n$ vertices and $t$ edges containing no copy of $H$, and suppose that $tk>n^2\log_en$. Show that there is a ...
0
votes
2answers
91 views

The probabilistic method exercise 2.7.4

This is exercise 2.7.2 of the book "the probabilistic method". Suppose $p>n>10m^2$, with $p$ prime, and let $0<a_1<a_2<...<a_m<p$ be integers. Prove that there is an ...
2
votes
0answers
56 views

Regular Graph with a Partition Half of Neighbors Are in the Partition and Half Are Not

Hi Math Stachexchange, I am a Computer Science student who are new to this forum. I got troubled by this graph problem. Hearing that it is a useful forum, I wonder if I can get any helps here. To ...
0
votes
1answer
48 views

Efficient Algorithm for finding a large sum-free subset.

Erdos's famous result shows that given n nonzero integers, there is a sum-free subset of size> n/3. The traditional proof gives only a pseudopolynomial time algorithm. Alon-Spencer claims that ...
2
votes
2answers
53 views

In random graph what do we mean by almost every graph in G(n,p) has a property Q?

I am reading the book random graph by Bollobas. There it is said that almost every graph in G(n,p) has a property Q if P(Q)$\rightarrow$ 1 as n $\rightarrow \infty$. Now, I don't understand the ...
2
votes
0answers
41 views

How to characterize sail-free $3$-uniform hypergraph?

Please have a look at the problem below. Given a 3-uniform hypergraph $H=(V, E),$ the matching number $\nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $\tau(H)$ ...

1
2 3 4 5 6