Intereting Posts

How can this equation produce an integer as a result? $\frac{1}{1+\cos(40^0)}+\frac{1}{1+\cos(80^0)}+\frac{1}{1+\cos(160^0)}=18$
Why doesn't Hom commute with taking stalks?
Two tails in a row – what's the probability that the game started with a head?
Proving that for infinite $\kappa$, $|^\lambda|=\kappa^\lambda$
If $\psi h$ is in $L^2$ for all $h\in L^2$, must $\psi$ be essentially bounded?
Cayley-Hamilton Theorem – Trace of Exterior Power Form
Alternate definition of Hilbert space operator norm
Fields of characteristics and affine conics
What can we say about the kernel of $\phi: F_n \rightarrow S_k$
What is category theory?
Exchange order of “almost all” quantifiers
A sequence of measures on a sigma algebra
Is $x^x=y$ solvable for $x$?
Project Euler – 34 / Find a mathematical approach for upper bound
Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination.

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.

- Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.
- For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?
- Question regarding bipartite graphs and their subgraphs.
- Textbook on Graph Theory using Linear Algebra
- Shooting Game for Fun
- What is difference between cycle, path and circuit in Graph Theory

**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!

- Prove a graph Containing $2k$ odd vertices contains $k$ distinct trails
- Minimal time gossip problem
- Probability questions of watch problem
- Probability distribution for the position of a biased random walker on the positive integers
- Is a probability of 0 or 1 given information up to time t unchanged by information thereafter?
- How many words can be formed from 'alpha'?
- Independent Events- $P(\text{neither/exactly/at least one})$
- Another counting problem on the number of ways to place $l$ balls in $m$ boxes.
- In a graph, connectedness in graph sense and in topological sense
- The limit of binomial distributed random variable

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 many 5-cards poker hands are there containing at least 3 of the 4 suits?
- If $4^n + 2^n + 1$ is prime, then $n$ must be a power of $3$
- Derivative of $\log |AA^T|$ with respect to $A$
- Foundations book using category theory for student embarking on PhD in mathematical biology?
- Distance between powers of 2 and 3
- Trying to show Tautology
- Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$
- Problem with definition of limit (why not big delta?)
- How do I get a tangent to a rotated ellipse in a given point?
- The equivalence of definitions Riemann integral
- Drawing heart in mathematica
- In a slice category C/A of a category C over a given object A, What is the role of the identity morphism of A in C with respect to C/A
- Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$
- Why is the determinant of a symplectic matrix 1?
- If $a^2$ divides $b^2$, then $a$ divides $b$