[SOLVED] CS201 Assignment 1

CS201 Assignment

1. Define n-varaiate polynomials P_d and Q_d as:

,

and P₀(x₁,x₂,…,x_n) = 1 = Q₀(x₁,x₂,…,x_n). Show that for any d > 0:

.

2. Let α ∈ R and N be a natural number. Using pigeon-hole principle, show that there exists integers p and q such that 1 ≤ q ≤ N and
3. Let G = (V,E) be a graph where V is the vertex set and E is the edge set. A bijective mapping f : V → V is an automorphism if it has the property that (u,v) ∈ E ⇐⇒ (f(u),f(v)) ∈ E. Consider the following graph.

1

Let A = {a₁,a₂,a₃},B = {b₁,b₂,b₃},M = {m₁,m₂,m₃,m₄}. Then, the vertex set of the above graph is V = A ∪ B ∪ M. Consider a bijective mapping g : A ∪ B → A ∪ B such that g(a_i) ∈ {a_i,b_i} and g(b_i) ∈ {a_i,b_i} for all i ∈ {1,2,3}, i.e., g maps the ordered pair [a_i,b_i] to either [a_i,b_i] (no swap) or [b_i,a_i] (swap).

Show that g can be extended to an automorphism f for the above graph if and only if the number of swaps performed by g is even.

4. An endomorphism of a ring R is a ring homomorphism φ : R 7→ R. Prove that φ : F_P →7 F_p, φ(x) = x^p is an endomorphism where p is a prime number.

2