Recent content by joypav

Another proof for your consideration (I was busy busy busy working on problems today!). Proof: Fix $v \in V(G)$. G is r-regular, so we know $|N(v)|=r$. Label $v$'s neighbors $u_1, ..., u_r$. Let $A_{u_i}$ be the event that $u_i \in S$ and let $X_{u_i}$ be its indicator. Let $X_v = \sum_{i=1}^r...

For completeness, I will post a "proof" I came up with. As you can see, at the end I skipped over some much needed justification that I couldn't seem to figure out. Some help with this would be appreciated! However, I do think that my general idea is correct. Proof: (a) Let $G \sim G(n,p)$...

Problem: Suppose that the function $p : N \rightarrow [0, 1]$ satisfies $p >> n^{-1}ln(n)$ (i.e. $n^{-1}ln(n) = o(p)$). (a) Prove that as $n \rightarrow \infty$, the random graph $G(n, p)$ has minimum degree at least $\frac{np}{2}$ almost surely. Idea: Look at the degree of each individual...

Problem: A vertex set $S$ in a graph $G$ is said to be totally t-dominating, for a positive integer t, if $|N(v) \cap S| \geq t$ for all $v \in V (G)$. Suppose that r, t, n are positive integers such that $r > 2t$ and $t \geq \frac{14}{3}\cdot ln(2n)$, and let $G$ be an r-regular n-vertex graph...

Is the only difference that three have to be numbers and three have to be letters? Because your calculation "10*9*8*26*25*24" suggests that repetition is not allowed. However, if repetition is allowed and there must be three letters and three numbers, we can find all unique combinations as...

For completeness, here is the proof I wrote. I'm not sure it is correct! May be some mistakes in the details. Known Theorem: Define $T'(n,q)$ to be q disjoint cliques with sizes of vertex sets as equal as possible. Let G be a graph with n vertices and $|E(T'(n,q))|$ edges. Then, $$\alpha (G)...

I have already proved that for a graph $G$ with $n$ vertices and $|E(T'(n,q))|$ edges, $\alpha (G) \geq q$. Additionally, if $\alpha (G) = q$ then it must be that $G \cong T'(n,q)$. Apparently this is the "dual version" of Turan's Theorem. How does this theorem imply Turan's? That $ex(n...

Let $n$ be a positive integer, and let $G$ be a random graph from $G(n, 1/2)$. Let $e_1, . . . , e_{n \choose 2}$ be the possible edges on the vertex set ${1, . . . , n}$, and for each $i$, let $A_i$ be the event that $e_i ∈ E(G)$. Prove that the events $A_1, . . . , A_{n \choose 2}$ are...

Problem: Let $X_n$ be independent random variables such that $X_1 = 1$, and for $n \geq 2$, $P(X_n=n)=n^{-2}$ and $P(X_n=1)=P(X_n=0)=\frac{1}{2}(1-n^{-2})$. Show $(1/\sqrt{n})(\sum_{m=1}^{n}X_n-n/2)$ converges weakly to a normal distribution as $n \rightarrow \infty$.Thoughts: My professor...

I think I may have a proof.. I will post it here so the question is complete, but also feel free to make sure it is correct! Proof: Case i: $S = \emptyset$ Then both 1. and 2. are obviously true. Case ii: $S \ne \emptyset$ Assuming 1. to be true, choose the smallest possible $S$ satisfying...

The problem given is... Let G be a graph with no perfect matching. Then, for some $S \subset G$, 1. $|S|<O(G−S)$ 2. Each vertex in S is adjacent to vertices in at least three odd components of $G−S$. (where $O(G−S)$ is the number of odd components of $G−S$) Number 1. is the contrapositive of...

Problem: Prove that for any $x \in R^n$ and any $0<p<\infty$ $\int_{S^{n-1}} \rvert \xi \cdot x \rvert^p d\sigma(\xi) = \rvert x \rvert^p \int_{S^{n-1}} \rvert \xi_1 \rvert^p d\sigma(\xi)$, where $\xi \cdot x = \xi_1 x_1 + ... + \xi_n x_n$ is the inner product in $R^n$. Some thinking... I...

Thank you! Makes sense. I wonder why we haven't seen the "push forward"? (Wondering) In the very first integral, is that meant to be $d\lambda$?

Let $S^{n-1} = \left\{ x \in R^2 : \left| x \right| = 1 \right\}$ and for any Borel set $E \in S^{n-1}$ set $E* = \left\{ r \theta : 0 < r < 1, \theta \in E \right\}$. Define the measure $\sigma$ on $S^{n-1}$ by $\sigma(E) = n \left| E* \right|$. With this definition the surface area...

Ahh okay, then it is as simple as $\nu = \nu_1 + \nu_2$, where $\nu_1=\nu$ and $\nu_2 \equiv 0$?