Extremal Combinatorics

Term Test 1

SolutionsOctober 15, 202680 minutes36 marksFull PDF

Test information

MATH 426/529: Extremal Combinatorics. Term Test 1. October 15, 2026.

Name: Solutions. Student number: blank.

Instructions

This exam is 80 minutes.
There are 36 marks available.
No collaboration is allowed.
Write complete solutions. Unless otherwise stated, justify your answers.

Marks available
Question	Marks
1	6
2	8
3	11
4	11
Total	36

Question 1

6 marks

1(a)

Provide an example of a sunflower $F \subseteq 2^{ℕ}$ with four petals.

Solution

For example, $F = {{1}, {2}, {3}, {4}}$ is a sunflower with 4 petals and core $\emptyset$ .

1(b)

What does it mean for a set system $F \subseteq 2^{[n]}$ to shatter a set $S \subseteq [n]$ ?

Solution

It means that, for all $T \subseteq S$ , there exists $A \in F$ such that $S \cap A = T$ .

1(c)

What does it mean for a set $A = {a_{1}, \dots, a_{k}}$ to come before another set $B = {b_{1}, \dots, b_{k}}$ in colexicographic order on $(\binom{ℕ}{k})$ ?

Solution

Assuming that $a_{1} < \dots < a_{k}$ and $b_{1} < \dots < b_{k}$ , it means that $a_{i} < b_{i}$ where $i = \max {j : a_{j} \neq b_{j}}$ .

Question 2

8 marks

2(a)

State each of the following theorems from lectures.

The Erdős–Ko–Rado Theorem.

Solution

Let $n$ and $k$ be positive integers such that $k \leq n / 2$ . If $F \subseteq (\binom{[n]}{k})$ is intersecting, then

| F | \leq (\binom{n - 1}{k - 1})

2(b)

State each of the following theorems from lectures.

The Sauer–Shelah Lemma.

Solution

Let $n \geq 1$ and $0 \leq k \leq n$ be integers. If

| F | > \sum_{i = 0}^{k - 1} (\binom{n}{i})

then the VC-dimension of $F$ is at least $k$ .

(Or, I would also accept: Every finite set system $F$ shatters at least $| F |$ sets.)

2(c)

State each of the following theorems from lectures.

The LYM Inequality.

Solution

If $A \subseteq 2^{[n]}$ is an antichain, then

\sum_{A \in A} \frac{1}{(\binom{n}{| A |})} \leq 1

2(d)

State each of the following theorems from lectures.

The Harris–Kleitman Inequality.

Solution

If $A, B \subseteq 2^{[n]}$ are downsets, then

\frac{| A \cap B |}{2^{n}} \geq \frac{| A |}{2^{n}} \cdot \frac{| B |}{2^{n}}

Question 3

11 marks

3(a)

Let $F$ be the collection of all subsets of $ℝ$ that can be written as a union of at most 2 intervals. Prove that the VC-dimension of $F$ is equal to 4.

Solution

First, let us show that it is at least four. Let $S = {1, 2, 3, 4}$ . We show that $F$ shatters $S$ .

It is easy to find a set in $F$ whose intersection with $S$ is $\emptyset$ . It is also easy to isolate each singleton, e.g. $S \cap [1.5, 2.5] = {2}$ . Any pair can also be isolated using a union of two intervals. Any subset of $S$ of size 3 contains two consecutive points, which can be covered by one interval, and the other point can be covered by a second interval. E.g.

S \cap ([0, 2.5] \cup [3.5, 4.5]) = {1, 2, 4}

Also, $S \cap [- 10, 10] = S$ .

Now, to see that it is exactly four, consider any set $S = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}} \subseteq ℝ$ with $x_{1} < x_{2} < x_{3} < x_{4} < x_{5}$ .

Then there can be no set $A \in F$ such that $S \cap A = {x_{1}, x_{3}, x_{5}}$ because any interval containing $x_{1}$ and $x_{3}$ must contain $x_{2}$ , any interval containing $x_{3}$ and $x_{5}$ must contain $x_{4}$ , and any interval containing $x_{1}$ and $x_{5}$ contains all of $S$ . So, the VC-dimension is 4.

3(b)

Let $F \subseteq 2^{[n]}$ be a downset. Prove that the VC-dimension of $F$ is equal to

\max {| A | : A \in F}

Solution

Let $A \in F$ such that $| A | = \max {| A | : A \in F}$ . Since $F$ is a downset, every subset of $A$ is in $F$ . Also, clearly, if $B \subseteq A$ , then $A \cap B = B$ . So $F$ shatters $A$ .

Now, suppose $S \subseteq [n]$ such that $| S | > \max {| A | : A \in F}$ . Then, for any $A \in F$ , we have $| A \cap S | \leq | A | < | S |$ . So there is no set $A \in F$ such that $A \cap S = S$ , and so $F$ does not shatter $S$ .

3(c)

Give examples of two functions $f, g : ℕ \to ℕ$ such that $f = Θ (g)$ but there does not exist a constant $c > 0$ such that $f \sim c \cdot g$ .

Hint: Recall that two functions $φ, ψ : ℕ \to ℕ$ satisfy $φ \sim ψ$ if $\lim_{n \to \infty} \frac{φ (n)}{ψ (n)} = 1$ .

Solution

Let

f (n) = {\begin{cases} 1 & if n is odd \\ 2 & if n is even \end{cases}

g (n) = 1

Then $\frac{1}{2} f (n) \leq g (n) \leq f (n)$ for all $n$ . Therefore $g = Θ (f)$ . However, the limit

\lim_{n \to \infty} \frac{f (n)}{g (n)}

does not exist.

Question 4

11 marks

4(a)

Let $a_{1}, \dots, a_{n} \geq 1$ , and let $b \in ℝ$ . Define

F = {S \subseteq [n] : b \leq \sum_{i \in S} a_{i} < b + 1}

Prove that $| F | \leq (\binom{n}{⌊ n / 2 ⌋})$ .

Solution

We show that $F$ is an antichain, from which the result will follow by Sperner’s Theorem.

If $F$ is not an antichain, then there exist $A, B \in F$ such that $A ⊊ B$ . So,

\sum_{i \in B} a_{i} = \sum_{i \in A} a_{i} + \sum_{i \in B ∖ A} a_{i}

\geq \sum_{i \in A} a_{i} + 1

(because $a_{i} \geq 1$ for all $i$ and $B ∖ A \neq \emptyset$ ).

Since $A \in F$ , we know $\sum_{i \in A} a_{i} \geq b$ . But then $\sum_{i \in B} a_{i} \geq b + 1$ , which contradicts the assumption that $B \in F$ .

4(b)

Let $F \subseteq (\binom{[n]}{3})$ such that $| F | = 11$ . Prove that

| \partial F | \geq 12

Solution

By Kruskal–Katona, $| \partial F |$ is minimized when $F$ is the first 11 sets in colex.

The 11th set is ${a_{1}, a_{2}, a_{3}}$ where $a_{1} < a_{2} < a_{3}$ and

11 = 1 + (\binom{a_{1} - 1}{1}) + (\binom{a_{2} - 1}{2}) + (\binom{a_{3} - 1}{3})

Since $(\binom{5}{3}) = 10 < 11$ , we must have $a_{3} \geq 6$ . We have

11 = 1 + (\binom{1 - 1}{1}) + (\binom{2 - 1}{2}) + (\binom{6 - 1}{3})

and so $a_{1} = 1, a_{2} = 2, a_{3} = 6$ . So,

| \partial F | \geq | (\binom{[5]}{3}) \cup {{1, 2, 6}} |

First 11 sets in colex.

= | (\binom{[5]}{2}) \cup {{1, 6}, {2, 6}} |

= 12

Term Test 1

Search results

Instructions

Question 1

1(a)

1(b)

1(c)

Question 2

2(a)

2(b)

2(c)

2(d)

Question 3

3(a)

3(b)

3(c)

Question 4

4(a)

4(b)

Scan