Combinatorics

2004

• B1.5

  Combinatorics | Part II, 2004

  State and prove Menger's theorem (vertex form).

  Let $G$ be a graph of connectivity $\kappa(G) \geq k$ and let $S, T$ be disjoint subsets of $V(G)$ with $|S|,|T| \geq k$. Show that there exist $k$ vertex disjoint paths from $S$ to $T$.

  The graph $H$ is said to be $k$-linked if, for every sequence $s_{1}, \ldots, s_{k}, t_{1}, \ldots, t_{k}$ of $2 k$ distinct vertices, there exist $s_{i}-t_{i}$ paths, $1 \leq i \leq k$, that are vertex disjoint. By removing an edge from $K_{2 k}$, or otherwise, show that, for $k \geqslant 2$, $H$ need not be $k$-linked even if $\kappa(H) \geq 2 k-2$.

  Prove that if $|H|=n$ and $\delta(H) \geq \frac{1}{2}(n+3 k)-2$ then $H$ is $k$-linked.

  comment

• B2.5

  Combinatorics | Part II, 2004

  State and prove Sperner's lemma on antichains.

  The family $\mathcal{A} \subset \mathcal{P}[n]$ is said to split $[n]$ if, for all distinct $i, j \in[n]$, there exists $A \in \mathcal{A}$ with $i \in A$ but $j \notin A$. Prove that if $\mathcal{A}$ splits $[n]$ then $n \leq\left(\begin{array}{c}a \\ \lfloor a / 2\rfloor\end{array}\right)$, where $a=|\mathcal{A}|$.

  Show moreover that, if $\mathcal{A}$ splits $[n]$ and no element of $[n]$ is in more than $k<\lfloor a / 2\rfloor$ members of $\mathcal{A}$, then $n \leq\left(\begin{array}{l}a \\ k\end{array}\right)$.

  comment

• B4.1

  Combinatorics | Part II, 2004

  Write an essay on Ramsey's theorem. You should include the finite and infinite versions, together with some discussion of bounds in the finite case, and give at least one application.

  comment

2003

• B1.5

  Combinatorics | Part II, 2003

  Let $G$ be a graph of order $n \geqslant 4$. Prove that if $G$ has $t_{2}(n)+1$ edges then it contains two triangles with a common edge. Here, $t_{2}(n)=\left\lfloor n^{2} / 4\right\rfloor$ is the Turán number.

  Suppose instead that $G$ has exactly one triangle. Show that $G$ has at most $t_{2}(n-1)+2$ edges, and that this number can be attained.

  comment

• B2.5

  Combinatorics | Part II, 2003

  Prove Ramsey's theorem in its usual infinite form, namely, that if $\mathbb{N}^{(r)}$ is finitely coloured then there is an infinite subset $M \subset \mathbb{N}$ such that $M^{(r)}$ is monochromatic.

  Now let the graph $\mathbb{N}^{(2)}$ be coloured with an infinite number of colours in such a way that there is no infinite $M \subset \mathbb{N}$ with $M^{(2)}$ monochromatic. By considering a suitable 2-colouring of the set $\mathbb{N}^{(4)}$ of 4 -sets, show that there is an infinite $M \subset \mathbb{N}$ with the property that any two edges of $M^{(2)}$ of the form $a d, b c$ with $a<b<c<d$ have different colours.

  By considering two further 2-colourings of $\mathbb{N}^{(4)}$, show that there is an infinite $M \subset \mathbb{N}$ such that any two non-incident edges of $M^{(2)}$ have different colours.

  comment

• B4.1

  Combinatorics | Part II, 2003

  Write an essay on the Kruskal-Katona theorem. As well as stating the theorem and giving a detailed sketch of a proof, you should describe some further results that may be derived from it.

  comment

2002

• B1.5

  Combinatorics | Part II, 2002

  Prove that every graph $G$ on $n \geqslant 3$ vertices with minimal degree $\delta(G) \geqslant \frac{n}{2}$ is Hamiltonian. For each $n \geqslant 3$, give an example to show that this result does not remain true if we weaken the condition to $\delta(G) \geqslant \frac{n}{2}-1$ ( $n$ even) or $\delta(G) \geqslant \frac{n-1}{2}$ ( $n$ odd).

  Now let $G$ be a connected graph (with at least 2 vertices) without a cutvertex. Does $G$ Hamiltonian imply $G$ Eulerian? Does $G$ Eulerian imply $G$ Hamiltonian? Justify your answers.

  comment

• B2.5

  Combinatorics | Part II, 2002

  State and prove the local $L Y M$ inequality. Explain carefully when equality holds.

  Define the colex order and state the Kruskal-Katona theorem. Deduce that, if $n$ and $r$ are fixed positive integers with $1 \leqslant r \leqslant n-1$, then for every $1 \leqslant m \leqslant\left(\begin{array}{l}n \\ r\end{array}\right)$ we have

  $$\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n]^{(r)},|\mathcal{A}|=m\right\}=\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n+1]^{(r)},|\mathcal{A}|=m\right\}$$

  By a suitable choice of $n, r$ and $m$, show that this result does not remain true if we replace the lower shadow $\partial A$ with the upper shadow $\partial^{+} \mathcal{A}$.

  comment

• B4.1

  Combinatorics | Part II, 2002

  Write an essay on Ramsey theory. You should include the finite and infinite versions of Ramsey's theorem, together with a discussion of upper and lower bounds in the finite case.

  [You may restrict your attention to colourings by just 2 colours.]

  comment

2001

• B1.5

  Combinatorics | Part II, 2001

  Let $\mathcal{A} \subset[n]^{(r)}$ where $r \leqslant n / 2$. Prove that, if $\mathcal{A}$ is 1-intersecting, then $|\mathcal{A}| \leqslant\left(\begin{array}{l}n-1 \\ r-1\end{array}\right)$. State an upper bound on $|\mathcal{A}|$ that is valid if $\mathcal{A}$ is $t$-intersecting and $n$ is large compared to $r$ and $t$.

  Let $\mathcal{B} \subset \mathcal{P}([n])$ be maximal 1-intersecting; that is, $\mathcal{B}$ is 1-intersecting but if $\mathcal{B} \subset \mathcal{C} \subset \mathcal{P}([n])$ and $\mathcal{B} \neq \mathcal{C}$ then $\mathcal{C}$ is not 1-intersecting. Show that $|\mathcal{B}|=2^{n-1}$.

  Let $\mathcal{B} \subset \mathcal{P}([n])$ be 2 -intersecting. Show that $|\mathcal{B}| \geqslant 2^{n-2}$ is possible. Can the inequality be strict?

  comment

• B2.5

  Combinatorics | Part II, 2001

  As usual, $R_{k}^{(r)}(m)$ denotes the smallest integer $n$ such that every $k$-colouring of $[n]^{(r)}$ yields a monochromatic $m$-subset $M \in[n]^{(m)}$. Prove that $R_{2}^{(2)}(m)>2^{m / 2}$ for $m \geqslant 3$.

  Let $\mathcal{P}([n])$ have the colex order, and for $a, b \in \mathcal{P}([n])$ let $\delta(a, b)=\max a \triangle b$; thus $a<b$ means $\delta(a, b) \in b$. Show that if $a<b<c$ then $\delta(a, b) \neq \delta(b, c)$, and that $\delta(a, c)=\max \{\delta(a, b), \delta(b, c)\} .$

  Given a red-blue colouring of $[n]^{(2)}$, the 4 -colouring

  $$\chi: \mathcal{P}([n])^{(3)} \rightarrow\{\text { red, blue }\} \times\{0,1\}$$

  is defined as follows:

  $$\chi(\{a, b, c\})= \begin{cases}(\text { red, } 0) & \text { if }\{\delta(a, b), \delta(b, c)\} \text { is red and } \delta(a, b)<\delta(b, c) \\ (\text { red }, 1) & \text { if }\{\delta(a, b), \delta(b, c)\} \text { is red and } \delta(a, b)>\delta(b, c) \\ (\text { blue, } 0) & \text { if }\{\delta(a, b), \delta(b, c)\} \text { is blue and } \delta(a, b)<\delta(b, c) \\ \text { (blue, } 1) & \text { if }\{\delta(a, b), \delta(b, c)\} \text { is blue and } \delta(a, b)>\delta(b, c)\end{cases}$$

  where $a<b<c$. Show that if $M=\left\{a_{0}, a_{1}, \ldots, a_{m}\right\} \in \mathcal{P}([n])^{(m+1)}$ is monochromatic then $\left\{\delta_{1}, \ldots, \delta_{m}\right\} \in[n]^{(m)}$ is monochromatic, where $\delta_{i}=\delta\left(a_{i-1}, a_{i}\right)$ and $a_{0}<a_{1}<\cdots<a_{m}$.

  Deduce that $R_{4}^{(3)}(m+1)>2^{2^{m / 2}}$ for $m \geqslant 3$.

  comment

• B4.1

  Combinatorics | Part II, 2001

  Write an essay on extremal graph theory. You should give proofs of at least two major theorems and you should also include a description of alternative proofs or further results.

  comment