MC322: Discrete Mathematics

Problem Set #1
Instructor: Sang-Hyun Yoon

Recall the standard set-theoretic notation:

• A k-set or k-element set is a set of k elements.
– Similarly, k-subset refers to a subset of k elements.
• [n] ¬ {1, 2, . . . , n} (i.e. “standard” n-element set)
• 2X ¬ {A ⊆ X } (i.e. the powerset of X )
X
 
• ¬ {A ⊆ X : |A| = k} (i.e. the set of every k-subset of X )
k
• F ⊆ 2X is called a k-uniform family if |A| = k for all A ∈ F .
• F ⊆ 2X is said to be intersecting if A ∩ B 6= ∅ for all A, B ∈ F .
• A permutation σ on X is a bijection σ : X → X .
• For a function f : X → Y and a subset A ⊆ X , f (A) ¬ { f (x) | x ∈ A}.

1. (100 points) Given positive integers n, r, k and s1 , s2 , · · · , s r with s1 , · · · , s r ≥ k, let

[n]
   
• C (n, r, k) = c : → [r]
k
– i.e. the set of all functions that map k-subsets of [n] to numbers 1, 2, . . . , r
[n]
 
• α c, s1 , · · · , s r ) = “for some i ∈ [r], there is A ∈ such that
si
A
 
c(B) = i for all B ∈ ”
k
– i.e. for some i ∈ [r], there is an si -subset A ⊂ [n] all of whose k-subsets corre-
spond to number i under c ∈ C (n, r, k)
– The predicate α is defined for each fixed c ∈ C (n, r, k).
• R r (k; s1 , · · · , s r ) ¬ min{n > 0 | α c, s1 , · · · , s r ) = true for all c ∈ C (n, r, k)}
– i.e. the smallest number n with the property that, if the k-subsets of an n-set
are arbitrarily colored with r colors, then for some i ∈ [r], there is an si -subset
of [n], all of whose k-subsets have color i.
• R r (k; s) ¬ R r (k; s1 , · · · , s r ) where s1 = s2 = . . . = s r = s.

3-1
Note that it is not clear a priori that the number R r (k; s1 , · · · , s r ) is finite. Indeed, it could
be the case that there is no finite number satisfying the conditions of R r (k; s1 , . . . , s r ) for
some choice of k, s1 , · · · , s r .
Prove the following step by step:

(a) R2 (k; s, t) ≤ R2 k−1; R2 (k; s−1, t), R2 (k; s, t −1) + 1 .

– Tips: Make use of induction on (k, s, t) where the underlying total order  on
{(k, s, t)} is defined by:
(k, s, t)  (k0 , s0 , t 0 ) ⇐⇒ earlier(k, s, t, k0 , s0 , t 0 ) is true where
boolean earlier(k, s, t, k0 , s0 , t 0 ) {
if (k 6= k0 ) return k < k0 ;
return s + t ≤ s0 + t 0 ;
}
(b) R r+1 (k; s) ≤ R r k; R2 (k; s) .

(c) R r (k; s1 , · · · , s r ) is finite for all r, k, s1 , · · · , s r .

2. (100 points)
Let n, k be positive integers such that n ≥ 2k. Let F ⊆ 2X be an intersecting k-uniform
family where X = Zn . Define

• Bs ¬ s + x mod n x ∈ {0, 1, . . . , k−1}


for each s ∈ X ,
• S ¬ the set of all permutations on X .

Prove the following step by step:

(a) {s ∈ X | Bs ∈ F } ≤ k.
(b) {s ∈ X | σ(Bs ) ∈ F } ≤ k for each σ ∈ S .
n−1
 
(c) |F | ≤ .
k−1
– Make use of double counting of R = {(σ, s) ∈ S × X | σ(Bs ) ∈ F }, i.e.
|R| = {s ∈ X | σ(Bs ) ∈ F } = {σ ∈ S | σ(Bs ) ∈ F }
P P
σ∈S s∈X

3-2
Recall the standard linear-algebraic notation:

Given a field (F, , €) and an integer n ≥ 1, let ⊕ and be binary operations defined by:
• ⊕ : Fn × Fn → Fn ; u ⊕ v = (u1  v1 , · · · , un  vn )
where u = (u1 , . . . , un ), v = (v1 , . . . , vn ) ∈ Fn
• : F × Fn → Fn ; λ v = (λ € v1 , · · · , λ € vn )
We say that
• (Fn , ⊕, ) is a vector space over (F, , €), and each v ∈ Fn is a vector.
– We use u + v and λv instead of u ⊕ v and λ v, resp., if no confusion arises.
For V ⊆ Fn and v1 , . . . , vm ∈ V , we say that:
• {λ1 v1 + . . . + λm vm | λi ∈ F} is the span of v1 , . . . , vm , denoted by span{v1 , . . . , vm }.
• u ∈ V is linearly dependent on v1 , . . . , vm if u ∈ span{v1 , . . . , vm }.
• v1 , . . . , vm are linearly independent if none of them is linearly dependent on the rest.
/ span{v1 , . . . , vi−1 , vi+1 , . . . , vm } for all i = 1, . . . , m.
– i.e. vi ∈
• The set {v1 , v2 , . . . , vm } is a basis of V if v1 , . . . , vm are linearly independent and
span{v1 , . . . , vm } = V .

3. (100 points)
Let k, n be positive integers with 1 ≤ k ≤ n. Let F = {A1 , . . . , Am } ⊆ 2[n] such that

|Ai ∩ A j | = k for all i 6= j.

Prove the following step by step:

(a) Define v1 , . . . , vm ∈ {0, 1}n by:

(
1 if j ∈ Ai
j-th coordinate of vi is
0 / Ai .
if j ∈
Then, v1 , · · · , vm are linearly independent in the vector space Rn .
(b) m ≤ n.

3-3