Intereting Posts

Can non-linear transformations be represented as Transformation Matrices?
Is this a convergent series?
Is the integral $\int_0^\infty \frac{\mathrm{d} x}{(1+x^2)(1+x^a)}$ equal for all $a \neq 0$?
Formula for $\sum_{k=0}^n k^d {n \choose 2k}$
Step in Proof of Cardinality of Product of two Groups
Hard Definite integral involving the Zeta function
Uniformly distributed rationals
Families of curves over number fields
Prove $\int_0^{\pi/2} J_0 (\cos x) dx=\frac{\pi}{2} \left(J_0 \left(\frac{1}{2} \right)\right)^2$
solution of first order differential equation and maximal interval
538.com's Puzzle of the Overflowing Martini Glass – How to compute the minor and major axis of an elliptical cross-section of a cone
Why is Erdős–Szekeres theorem sharp?
Prove that integral of continuous function is continuously differentiable
Whitehead's axioms of projective geometry and a vector space over a field
What are the requirements for separability inheritance

Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup … \cup V_n$ be a

partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality

4. Is it true that there must be an independent set of $G$ containing precisely

one vertex from each $V_i$? (Prove or supply a counter example.)

I think this is not right because just consider square with four vertices and four edges,but I have doubt that it is proper counter example.please help with your knowledge,thank you very much.

actually this is exercise 4 of chapter 5 from alon spencer probabilistic method.so I also tag this question as mentioned.

- 3-regular connected planar graph
- Graph theory problem (edge-disjoint matchings)
- Degree sequence of connected graphs
- “faces” of a non-planar graph
- Trees with odd degree sequence
- How to prove the optimal Towers of Hanoi strategy?

- Secret Santa Perfect Loop problem
- Connection Between Automorphism Groups of a Graph and its Line Graph
- Question regarding bipartite graphs and their subgraphs.
- Easy to read books on Graph Theory
- How would I find a minimum weight spanning tree for W?
- How to construct a k-regular graph?
- graph theory - clique graph
- Number of paths in regular graphs, where starting and ending nodes are same
- vertex cover , linear program extreme point
- Counting the number of polygons in a figure

I know this is an old question, but I’m writing up solutions to Alon and Spencer, so I thought I’d supply an answer for whomever comes across this in the future

We prove the statement is true. Let $V_i = \{v_i^{(1)},v_i^{(2)},v_i^{(3)},v_i^{(4)}\}$. Pick a set $S$ by randomly choosing from each $V_i$ one vertex, uniformly and independently. Define $A_{i,k;j,l}$ to be the event that $v_i^{(k)}$ and $v_j^{(l)}$ are both in $S$ and adjacent. Now, define \begin{equation*}

x_{i,k;j,l} = \left\{ \begin{array}{ll}

0 &\quad\text{ if } v_{i}^{(k)} \text{ and } v_{j}^{(l)} \text{ are not adjacent.} \\

\frac{1}{2} &\quad\text{ if } v_{i}^{(k)} \text{ and } v_{j}^{(l)} \text{ are adjacent.}

\end{array} \right.

\end{equation*}

Let $i,j,k,l$ s.t. $v_i^{(k)}$ and $v_{j}^{(l)}$ are not adjacent. Then \begin{equation*}

\mathbb{P}[A_{i,k;j,l}] = 0 \leq 0 = x_{i,k;j,l} \prod (1 – x_{i’,k’;j’,l’}).

\end{equation*}

If $v_i^{(k)}$ and $v_{j}^{(l)}$ are adjacent, then there are only two vertices adjacent to either of the two vertices, implying that \begin{equation*}

\mathbb{P}[A_{i,k;j,l}] = \frac{1}{16} \leq \frac{1}{2}\cdot \left(\frac{1}{2}\right)^2 = x_{i,k;j,l} \prod\limits_{(i’,k’;j’,l’) \sim (i,k;j,l)} (1 – x_{i’,k’;j’,l’}).

\end{equation*}

Thus the hypotheses of the local lemma are satisfied, implying that there is a choice of $S$ that is an independent set.

- Rudin's PMA Exercise 2.18 – Perfect Sets
- Liapunov's Inequality for $L_p$ spaces
- Showing independence of random variables
- Generalizing Lagrange multipliers to use the subdifferential?
- Importance of Linear Algebra
- Determine variables that fit this criterion…
- Prove that there is exactly one perpendicular line
- Uniqueness of the random variable from its distribution
- On maximal submodules of projective modules
- $f \in L^1$, but $f \not\in L^p$ for all $p > 1$
- Is the class of cardinals totally ordered?
- Is there a topological group that is connected but not path-connected?
- Nets of Geodesic spheres
- what is separation of variables
- about weak derivative of Bochner integrable function