Intereting Posts

Let $X$ be a Moore space and $e(X)=\omega$. Is it metrizable?
Erdős and the limiting ratio of consecutive prime numbers
I'm trying to find the longest consecutive set of composite numbers
Limit of factorial function: $\lim\limits_{n\to\infty}\frac{n^n}{n!}.$
Square of digit reversal equals digit reversal of square?
How many numbers between $100$ and $900$ have sum of their digits equal to $15$?
For set of positive measure $E$, $\alpha \in (0, 1)$, there is interval $I$ such that $m(E \cap I) > \alpha \, m(I)$
How find this equation integer solution:$x^2y^2=4x^5+y^3$
If $a\in \mathrm{clo}(S)$, does it follow that there exists a sequence of points in $S$ that converges to $a$?
Prove $\sum_{k=0}^{58}\binom{2017+k}{58-k}\binom{2075-k}{k}=\sum_{k=0}^{29}\binom{4091-2k}{58-2k}$
How many ways are there to position two black rooks and two white rooks on an 8X8 chessboard
Sum and Product of two transcendental numbers cannot be simultaneously algebraic
Does the notion of “rotation” depend on a choice of metric?
$f:\bf S^1 \to \bf R$, there exist uncountably many pairs of distinct points $x$ and $y$ in $\bf S^1$ such that $f(x)=f(y)$? (NBHM-2010)
How can we prove that $2e^2\int_{0}^{\infty} {x\ln x\over 1-e^{2e\pi{x}}}\mathrm dx=\ln A?$

A theorem in graph theory is as the following,

Let $G=(V,E)$ be a finite graph where $V$ is the set of vertexes and $E$ is the set of edges. Then there exists a vertex subset $W$, i.e. $W \subset V$, such that the number of edges connecting $W$ and $W^C$ is at least $\frac{|E|}{2}$, where $W^C = V\backslash W$ and $|E|$ is the total number of edges in the graph $G$.

The question is to prove this theorem by a probabilistic approach.

- Exact probability of random graph being connected
- How to prove the next properties for Critical graph?
- Counting the number of paths on a graph
- vertex cover , linear program extreme point
- Applications of the number of spanning trees in graphs
- Lower bound for monochromatic triangles in $K_n$

**My idea is as follows**:

Let $|V|=n,|W|=m$, then the maximum number of possible edges between $W,W^C$ is $m\times(n-m)$. The maximum number of possible edges in graph $G$ is $C_n^2 = \frac{n!}{2!\times(n-2)!}$. We can treat the edges as if they were randomly scattered in the $C_n^2$ positions, and with probability $p=\frac{m\times(n-m)}{C_n^2}$ one edge would connect $W,W^C$.

Then it is like a Bernoulli trial of $|E|$ times with success probability $p=\frac{m\times(n-m)}{C_n^2}$, and the probability there are at least $\frac{|E|}{2}$ edges connecting $W,W^C$ is $\sum\limits_{k = \left\lceil {\frac{1}{2}|E|} \right\rceil }^{|E|} {C_{|E|}^k{p^k}{{(1 – p)}^{|E| – k}}} $. But this probability is for a particular $W$. We need to show with probability there exists one or more such $W$ satisfying the conditions of the above-mentioned theorem. I got stuck here. Anyone can help with this proof? Thank you!

- Creating unusual probabilities with a single dice, using the minimal number of expected rolls
- Characteristic function of random variable $Z=XY$ where X and Y are independent non-standard normal random variables
- Does Convergence in probability implies convergence of the mean?
- What is the average of rolling two dice and only taking the value of the higher dice roll?
- Probability a rotation has a small distance to a vector
- Determine the probability that each of the 8 members serves on at least one of the three committees.
- Borel $\sigma$-Algebra definition.
- What is the probability that when you place 8 towers on a chess-board, none of them can beat the other.
- Why weak law of large number still alive?
- How to approach number guessing game(with a twist) algorithm?

Take the graph $G = (V,E)$ and for each vertex, randomly select whether it will lie in $W$ with independent probability $p = \frac{1}{2}$. For each edge $e_i \in E$, define the random variable $X_i$, which is $1$ if $e$ connects $W$ to $W^C$, and $0$ otherwise. Then, $\mathbb{P}(X_i = 1) = \frac{1}{2}$, and $\mathbb{E}(X_i) = \frac{1}{2}$.

By linearity of expectation: $$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) = \mathbb{E}(\sum X_i) = \sum E(X_i) = \sum \frac{1}{2} = \frac{|E|}{2}$$

Since the expected number of edges crossing the cut is $\frac{|E|}{2}$, there must be at least one choice of $W$ that has at least $\frac{|E|}{2}$ edges crossing the cut.

You can see that the claim holds with certainty because if you assume that all possible choices for $W$ have fewer than $\frac{|E|}{2}$ edges crossing the cut, then we get the contradictory:

$$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) < \frac{|E|}{2}$$

ETA: To those who are still confused – here is a small explicit example:

Suppose $V = \{v_1, v_2\}$ and $E = \{(v_1,v_2)\}$.

We consider all possible choices for $W$, where vertices are independently placed in $W$ with probability $\frac{1}{2}$:

- $W = \emptyset$. No edges cross the cut. This has probability $\mathbb{P}(v_1 \notin W \cap v_2 \notin W) = \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4}$.
- $W = \{v_1\}$. One edge crosses the cut. This has probability $\mathbb{P}(v_1 \in W \cap v_2 \notin W) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
- $W = \{v_2\}$. One edge crosses the cut. Again, this has probability $\mathbb{P}(v_1 \notin W \cap v_2 \in W) = \frac{1}{4}$.
- $W = \{v_1,v_2\}$. No edge crosses the cut. Again, probability is $\frac{1}{4}$.

Then, $\mathbb{P}((v_1,v_2) \textrm{ crosses the cut}) = \frac{1}{2}$ and the expected number of crossing edges is $$0\cdot \frac{1}{4} + 1\cdot \frac{1}{4}+1\cdot \frac{1}{4}+0\cdot \frac{1}{4} = \frac{1}{2} = \frac{|E|}{2}$$

If all of the possibilities had fewer than $\frac{|E|}{2}$ edges crossing the cut, the expectation would have to be less than $\frac{|E|}{2}$. Therefore, there must be at least one choice for $W$ such that at least $\frac{|E|}{2}$ edges crosses the cut. In this case, one such choice is $W = \{v_1\}$.

- How to solve this to find the Null Space
- Divergent series and $p$-adics
- Finding a closed form for $\cos{x}+\cos{3x}+\cos{5x}+\cdots+\cos{(2n-1)x}$
- In ZF, how would the structure of the cardinal numbers change by adopting this definition of cardinality?
- Forcing series convergence
- How to find the direction vector of a ball falling off an ellipsoid?
- Solve a seemingly simple limit $\lim_{n\to\infty}\left(\frac{n-2}n\right)^{n^2}$
- The prime order is cyclic
- Why is the $L_p$ norm strictly convex for $1<p<\infty?$
- Finding $g_i:\mathbb{R}^n\to\mathbb R$ s.t $f(x)=\sum\limits_{i=1}^nx_i\cdot g_i(x)$
- Extended ideals and algebraic sets
- Definition of the image as coker of ker == ker of coker?
- How to interpret Lagrangian function (specifically not Lagrangian multiplier)
- N-th derivative of a product in binomial expansion?
- Brauer group of a finite field is trivial