Combinatorics and Graph Theory 2004-

Part A- Combinatorics and Graph Theory

1. A subset S of the vertices of a simple graph G is called independent if no two vertices of S are adjacent in G. The independence number of G, α(G), is then the maximum of the sizes of the independent sets. Show that if G has n vertices, then

α(G) · χ(G) ≥ n,

where χ(G) is the chromatic number of G.

2. Let c_n be the number of ways to distribute n (indistinguishable) pieces of candy among three children in such a way that the oldest child receives an even number of pieces, the middle child receives an odd number of pieces, and the youngest child receives a number of pieces that is congruent to 2 (mod 3). Find a closed form for the generating function

F(x) = _n=0∑^∞c_nxⁿ,

and find the radius of convergence.

3. Let (k₁, . . . , k_n) be a sequence of n ≥ 1 nonnegative integers such that n = k₁ + 2k₂ + 3k₃ + · · · + nk_n. Prove that the number of partitions of an n-element set into

is

n!/_t=1∏ⁿ[(t!)^k_t · k_t!].

4. Show that for any positive n and r:

where S(x, y) is the Stirling number of the second kind. (S(x, y) = 0 for x < y.)

5. Prove that the number of partititions of an integer n with at most two repeats of each part equals the number of partitions of n into parts none of which is divisible by three. For example, if n = 4, there are four partitions of each kind.

At most two repeats:                                                     No multiples of three:

4 = 4                                                                           4 = 4

4 = 3 + 1                                                                     4 = 2 + 2

4 = 2 + 2                                                                     4 = 2 + 1 + 1

4 = 2 + 1 + 1                                                               4 = 1 + 1 + 1 + 1

6. You are going to make a 12-bead bracelet. Each bead in your supply is either spherical or cubical, and each is one of k different colors. Your bracelet will have eight spherical and four cubical beads, with very third bead being cubical. How many different bracelets can you make? (Two bracelets are identified as the same if you can get the second one by either rotating the first one or flipping it over.)

7. There is a finite projective plane of order 2 (three points on each line; three lines through every point; a total of 7 lines and 7 points). The plane generates a graph: the vertices are the points, with an edge between two vertices/points if they are on a common line. Show that this graph is not planar.

Part B- Combinatorial Matrix Theory

1.For n, m ≥ 2, let G be a bipartite graph on the n + m vertices

X ∪ Y: X = {x₁, . . . , x_n}, Y = {y₁, . . . , y_m}, X ∩ Y = ∅

such that all edges connect vertices of X to vertices of Y . Show that a largest set S of edges such that no two edges in S are incident at a common vertex has the same size as a smallest set of vertices

A ∪ B: A ⊆ X and B ⊆ Y

such that every edge of G connects a vertex of A to a vertex of B.

2. Let A and B be nonnegative n × n matrices such that all lines in A sum to k and all lines in B sum to l. Show that all lines in AB must sum to kl.

3. Let q = p^α, where p is prime and α ≥ 1. This problem outlines an independent proof that in the finite projective plane of order q constructed from the vector space

V = GF(q) × GF(q) × GF(q),

the number of "lines" is q² + q + 1. Prove each statement.

[a]: The number of ordered pairs of independent vectors in V is (q³ - 1)(q³ - q).

[b]: For any two-dimensional subspace W ⊆ V, the number of ordered bases of W is (q² - 1)(q² - q).

[c]: The number of two-dimensional subspaces of V is q² + q + 1.

4. Let A and B be n × n and m × m matrices respectively, with respective characteristic polynomials

φ_A(x) = (x - λ₁)· · ·(x - λ_n) and φ_B(x) = (x - µ₁)· · ·(x - µ_m).

Show that the charactistic polynomial of A ⊗ B is

φ_A⊗B(x) = _i=1∏ⁿ_j=1∏^m(x - λ_iµ_j).

5. Let A be an n × n matrix. Find necessary and sufficient conditions on the Jordan form of A so that the sequence (A, A², A³, . . .) remains bounded but does not converge.

6. Let (X₁, . . . , X_m) be a sequence of sets, and let x₁ ∈ X₁. Show that if for every choice 1 ≤ i₁ < i₂ <· · · < i_k ≤ n we have

|X_i1 ∪ X_i2 ∪ · · · ∪ X_ik| ≥ k + 1,

then (X₁, . . . , X_m) has an SDR in which x₁ represents X₁.

7. Show how a (4t) × (4t) Hadamard matrix may be used to generate a (nonsymmetric) 2-(v, k, λ) design with v = 4t, k = 2t, and λ = 2t - 1.

8. Let A be a square, nonnegative, irreducible matrix. Show that the following are equivalent.

[a] k is the index of imprimitivity of A.

[b] k is the smallest positive integer for which [∃m] [A^m(I + A + · · · + A^k-1) > 0].

[c] k is the smallest positive integer for which [∃N][∀m  ≥  N][A^m(I + A + · · · + A^k-1) > 0].

Part C- Theory of Computation

1. Let

M₁ = (K₁, {a, b}, δ₁, s₁, F₁)

and

M₂ = (K₂, {a, b}, δ₂, s₂, F₂)

be two DFA's. Construct from them a DFA M₃ for which L(M₃) = L(M₁) ∩ L(M₂). Prove that your DFA works.

2. Co-N P is the set of languages

{L ⊆ Σ^∗: L^- ∈ NP}.

Suppose one had a language L₀ that was both N P-complete and in co-N P. Show that this would imply that NP = co-N P.

3. Show that the following context-free grammar generates the language

{w ∈ {a, b}^∗: w has the same number of a's and b's}.

V = {S, A, B}; Σ = {a, b}; and the rules are listed below.

S → aB | bA | ε

A → aS | bAA

B → bS | aBB

4. Show that the function

f(x) = x^{x^...^x} (x times)

is primitive recursive.

5. Say you have a CFG G in Chomsky Normal Form (so that every rule has exactly two symbols to the right of the "→"). Describe an algorithm for deciding whether L(G) is finite or not.

6. Show that the language {aⁿb^{n^2}: n = 1, 2, 3 . . .} is not context free.

7. Let L ⊆ Σ^∗ be a language such that both L and L^- are r.e. Show that L is recursive.

8. Describe a Turing machine that computes the function f(w) = ww^R, for w ∈ {a, b}^∗.