{Treewidth of the Kneser Graph and the Erd\H{o}s-Ko-Rado Theorem}
Daniel J. Harvey\footnote{Department of Mathematics and Statistics
Melbourne
and David R. Wood\footnote{School of Mathematical Sciences
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph $\Kneser(n,k)$ is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of $n$ with respect to $k$, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erd\H{o}s-Ko-Rado Theorem (for large $n$ with respect to $k$) when a number of disjoint pairs of $k$-sets are allowed. %Might want to add a bit more here
Kneser.tex
\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,enumerate}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\usepackage{algorithm}
%\usepackage{algorithmic}   
 %\floatname{algorithm}{Algorithm} 
 %\renewcommand{\algorithmicrequire}{\textbf{Input:}} 
 %\renewcommand{\algorithmicensure}{\textbf{Output:}} 
\usepackage[lmargin=30mm,rmargin=30mm,bmargin=30mm,tmargin=30mm]{geometry}
%\usepackage[numbers,sort&compress]{natbib}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{definition}[1][Definition]{\begin{trivlist}\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\theoremstyle{remark}
\newtheorem{claim}{Claim}

%\newcommand{\ceil}[1]{\ensuremath{\protect\lceil#1\rceil}}
%\newcommand{\floor}[1]{\ensuremath{\protect\lfloor#1\rfloor}}
%\newcommand{\CEIL}[1]{\ensuremath{\protect\left\lceil#1\right\rceil}}
%\newcommand{\FLOOR}[1]{\ensuremath{\protect\left\lfloor#1\right\rfloor}}

\DeclareMathOperator{\tw}{tw}
\DeclareMathOperator{\sep}{sep}
\DeclareMathOperator{\Kneser}{Kneser}

\begin{document}

\title{\bf{Treewidth of the Kneser Graph and the Erd\H{o}s-Ko-Rado Theorem}}
\author{Daniel J. Harvey\footnote{Department of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia  (\texttt{d.harvey@pgrad.unimelb.edu.au}). Supported by an Australian Postgraduate Award.} \,and David R. Wood\footnote{School of Mathematical Sciences, Monash University, Melbourne, Australia (\texttt{david.wood@monash.edu}). Supported by the Australian Research Council.}}
\maketitle

\begin{abstract}
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The \emph{Kneser graph} $\Kneser(n,k)$ is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of $n$ with respect to $k$, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erd\H{o}s-Ko-Rado Theorem (for large $n$ with respect to $k$) when a number of disjoint pairs of $k$-sets are allowed. %Might want to add a bit more here
\end{abstract}

\section{Introduction}
\label{section:intro} %and perhaps talk about Turan -- then make sep changes. This is our Monday goal.

A \emph{tree decomposition} of a graph $G$ is a pair $(T, (B_{x} \subset V(G) :x \in V(T)))$ where $T$ is a tree and $(B_{x} \subseteq V(G): x \in V(T))$ is a collection of sets, called \emph{bags}, indexed by the nodes of $T$. The following properties must also hold:
\begin{itemize}
\item for each $v \in V(G)$, the nodes of $T$ that index the bags containing $v$ induce a non-empty connected subtree of $T$,
\item for each $vw \in E(G)$, there exists some bag containing both $v$ and $w$.
\end{itemize}

The \emph{width} of a tree decomposition is the size of the largest bag, minus 1. The \emph{treewidth} of a graph $G$, denoted $\tw(G)$, is the minimum width of a tree decomposition of $G$.

Treewidth is an important concept in modern graph theory. Treewidth was initially defined by Halin \cite{Halin76} (with different nomenclature to the modern standard) and then later by Robertson and Seymour \cite{GMII}, who used it in their famous series of papers proving the Graph Minor Theorem \cite{GMall}. The treewidth of a graph essentially describes how ``tree-like" it is, where lower treewidth implies a more ``tree-like" structure. (A forest has treewidth at most 1, for example.) Treewidth is also of key interest in the field of algorithm design---for example, treewidth is a key parameter in fixed-parameter tractability \cite{Bodlaender-AC93}. \newline

Let $[n] = \{1, \dots, n\}$. For any set $S \subseteq [n]$, a subset of $S$ of size $k$ is called a \emph{$k$-set}, or occasionally a $k$-set in $S$. Let $\binom{S}{k}$ denote the set of all $k$-sets in $S$. We say two sets \emph{intersect} when they have non-empty intersection.

The \emph{Kneser graph} $\Kneser(n,k)$ is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint.

Kneser graphs were first investigated by Kneser \cite{kneser}. The chromatic number of $\Kneser(n,k)$ was shown to be $n-2k+2$ by Lov\'{a}sz \cite{lazlo}, as Kneser originally conjectured. This was an important proof due to the development of the topological methods involved. Many other proofs of this result have been found, for example consider \cite{Ziegler}, which gives a more combinatorial version. The Kneser graph is also of interest with regards to fractional chromatic number \cite{fgt}. The famous Erd\H{o}s-Ko-Rado Theorem \cite{EKR} has a well-known relationship to the Kneser graph, as does the generalisation to cross-intersecting families by Pyber \cite{Pyber}. We discuss these in more detail in Section~\ref{section:prelim}, and shall use both of these results to prove the following two theorems about the treewidth of the Kneser graph.

\begin{theorem}
\label{theorem:main}
Let $G$ be a Kneser graph with $n \geq 4k^2 - 4k + 3$ and $k \geq 3$. Then $$\tw(G) = \binom{n-1}{k}-1.$$
\end{theorem}
This theorem is our main result, giving an exact answer for the treewidth of the Kneser graph when $n$ is sufficiently large. In order to prove this, we show that $\binom{n-1}{k}-1$ is both an upper bound and lower bound on the treewidth. We construct a tree decomposition directly in Section~\ref{section:upper} to prove an upper bound. In Section~\ref{section:lbone} we prove the lower bound by using the relationship between treewidth and separators.
%After deleting any separator $X$ from $V(G)$, the remaining vertices form a pair of \emph{cross-intersecting families}. We show there is an upper bound on the order of these sets, and so a lower bound on $|X|$.

%\begin{theorem}
%\label{theorem:secondary}
%Let $G$ be a Kneser graph with $n \geq \frac{1}{2}(\sqrt{5k^2 - 12k + 8} + 3k + 2)$ and $k \geq 3$. Then $\binom{n-1}{k} - \binom{n-1}{k-1} - 1 \leq \tw(G) \leq \binom{n-1}{k} - 1$.
%\end{theorem}
%When we only have a weaker lower bound, we can prove a much weaker result on the treewidth of the Kneser graph, as stated above. We believe that the lower bound on the treewidth should be able to be improved here, giving a result similar to Theorem~\ref{theorem:main}.

We also prove the following more precise result when $k=2$.

\begin{theorem}
\label{theorem:ktwo}
Let $G$ be a Kneser graph with $k=2$. Then \newline
$$\tw(G) =
\begin{cases}
0 &\text{ if } n \leq 3 \\
1 &\text{ if } n = 4 \\
4 &\text{ if } n = 5 \\
\binom{n-1}{2} - 1 &\text{ if } n \geq 6.
\end{cases}$$
\end{theorem}

The upper bounds for Theorem~\ref{theorem:ktwo} are proved in Section~\ref{section:upper}, and the lower bounds in Section~\ref{section:ktwolow}.

%Finally, we prove the following related Tur\'{a}n style result about intersection graphs of $\binom{[n]}{k}$. 
%Recall that the \emph{intersection graph} of a collection of sets $S$ is the graph with vertex set $S$ and an edge between two vertices iff their corresponding sets in $S$ intersect. Note the obvious relationship to the Kneser graph---the Kneser graph is the complement to an intersection graph with $S=\binom{[n]}{k}$. Also recall the famous result of Tur\'{a}n \cite{turan}, which states that the edge-maximal graph with $n$ vertices and no $(r+1)$-clique is constructed by partitioning the vertex set into $r$ (almost) equal sized colour classes and taking every possible polychromatic edge. Such a graph is known as a \emph{Tur\'{a}n graph}. We provide a result on the maximum order of a Tur\'{a}n graph that is a subgraph of a complement of the Kneser graph.

Finally, in the process of proving Theorem~\ref{theorem:main}, we prove the following generalisation of the Erd\H{o}s-Ko-Rado Theorem (Theorem~\ref{theorem:ekr} in Section~\ref{section:prelim}), which says that if $n \geq 2k$ and $H$ is a complete subgraph in the complement of $\Kneser(n,k)$ then $|H| \leq \binom{n-1}{k-1}.$ We prove the same bound for balanced complete multipartite graphs. %rather than requiring all $k$-sets of a family $\mathcal{A}$ to intersect, instead we allow a certain number of $k$-sets to be disjoint. 
%This idea has been explored recently by Gerbner et al.\cite{almostisect}; there each $k$-set in a family $\mathcal{A}$ must be disjoint from all but at most $b$ $k$-sets in $\mathcal{A}$, for some fixed parameter $b$. Here, instead we partition a family of $k$-sets into colour classes and allow any two $k$-sets inside a colour class to be disjoint.

\begin{theorem}
\label{theorem:turan}
Say $p \in [\frac{2}{3},1)$ and $n \geq \max(4k^2 - 4k +3, \frac{1}{1-p}(k^2 -1)+2)$. If $H$ is a complete multipartite subgraph of the complement of $\Kneser(n,k)$ such that no colour class contains more than $p|H|$ vertices, then $|H| \leq \binom{n-1}{k-1}$.
 
%Let $H$ be the intersection graph with $V(H) = \binom{[n]}{k}$, and say $n \geq 4k^2 - 4k + 3$. If $H'$ is a complete multipartite subgraph of $H$ with equal sized colour classes, then $|V(H')| \leq \binom{n-1}{k-1}$.
\end{theorem}

Note that similar, but incomparable, generalisations of the Erd\H{o}s-Ko-Rado Theorem have recently been explored in \cite{almostisect,sperner,scott}.
Theorem~\ref{theorem:turan} is proven in Section~\ref{section:lbone}, since it follows almost directly from our proof of the lower bound on the treewidth of a Kneser graph.

\section{Basic Definitions and Preliminaries}
\label{section:prelim}

From now on, we refer to the graph $\Kneser(n,k)$ as $G$, with $n$ and $k$ implicit. 

%The set of elements $\{1, \dots, b\}$ shall be denoted by $[b]$. We refer to a set of size $a$ that contains elements from some $[b]$ as an \emph{$a$-set}, or sometimes, as an $a$-set on $[b]$. That is, the vertices of $G$ are $k$-sets on $[n]$.  For any set $S$, we let $\binom{S}{a}$ denote the set of all $a$-sets with elements chosen from $S$. Therefore, $V(G) = \binom{[n]}{k}$. We shall say two $a$-sets \emph{intersect} if they have a non-empty intersection.

Let $\Delta(H)$ be the maximum degree of a graph $H$ and $\delta(H)$ be the minimum degree of a graph $H$. Also let $\alpha(H)$ be the size of the largest independent set of $H$, where an \emph{independent set} is a set of pairwise non-adjacent vertices. If $k=1$, then $G$ is the complete graph. If $n < 2k$ then $G$ has no edges. If $n=2k$ then $G$ is an induced matching. From now on, we shall assume that $n \geq 2k+1$ and $k \geq 2$, since the treewidth is trivial in the other cases.

%We now prove some basic but useful results about the Kneser graph and treewidth.
%
%\begin{proposition}
%\label{prop:easy}
%If $k=1$, then $G$ is the complete graph. If $n < 2k$ then $G$ has no edges. If $n=2k$ then $G$ is an induced matching.
%\end{proposition}
%\begin{proof}
%If $k=1$, then $G$ has $n$ vertices, and clearly no two vertices intersect as $k$-sets. When $n < 2k$, then any two $k$-sets must share an element, as it is impossible to construct two disjoint sets of $k$-elements from a total of less than $2k$. Similarly, when $n = 2k$, for any $k$-set there is exactly one other $k$-set which it does not intersect, that is, exactly the other $k$ elements.
%\end{proof}
%
%From now on, we shall assume that $n \geq 2k+1$ and $k \geq 2$, since the treewidth is trivial in the other cases.
%
%\begin{proposition}
%\label{prop:regular}
%$G$ is $\binom{n-k}{k}$-regular.
%\end{proposition}
%\begin{proof}
%Choose a vertex $v$. The neighbours of $v$ are exactly the vertices of the set $\binom{[n]-v}{k}$.
%\end{proof}
%
%\begin{proposition}
%$\tw(H) \geq \delta(H)$
%\end{proposition}

%\begin{corollary}
%\label{corollary:deltabound}
%$\tw(G) \geq \binom{n-k}{k}$
%\end{corollary}
%This is a well-known result and presented without proof, however, a similar argument is used in part of Lemma~\ref{lemma:lbn6}.

%\begin{proposition}
%\label{prop:closed}
%If $H_1$ is a minor of $H_2$, then $\tw(H_1) \leq \tw(H_2)$.
%\end{proposition}
%\begin{proof}
%If $(T, (B_{x : x \in V(T)}))$ is a minimum width tree decomposition for $H_2$, then when we perform vertex deletions, edge deletions and edge contractions on $H_2$, we can perform equivalent operations on the vertices in the bags of $(B_{x : x \in V(T)})$. This will then give a tree decomposition for $H_1$, but the width will not have increased from $\tw(H_2)$. So $\tw(H_1) \leq \tw(H_2)$.
%\end{proof}

In order to prove a lower bound on the treewidth of the Kneser graph, we use a known result about the relationship between treewidth and separators.

\begin{definition}%(Originally defined in \cite{GMII}, this definition from \cite{Reed97}.)
Given a constant $p \in [\frac{2}{3},1)$, a \emph{$p$-separator} (of order $k$) is a set $X \subset V(G)$ such that $|X| \leq k$ and no component of $G-X$ contains more than $p|G-X|$ vertices. %The \emph{separation number} $\sep(G)$ is the smallest integer $k$ such that for every $S \subset V(G)$ there is a separator $X$ with respect to $S$ and $|X| \leq k$.
\end{definition}

\begin{theorem} \cite{GMII}
\label{theorem:sep}
%$\sep(G) \leq \tw(G)+1$
For each $p \in [\frac{2}{3},1)$, every graph $G$ has a $p$-separator of order $\tw(G)+1$.
\end{theorem}

It can easily be shown that we can partition the components of $G-X$ into two parts, such that the components in a part contain, in total, at most $p|G-X|$ vertices. %We abuse notation and treat this partition of the components as a partition of the vertex set. Now every vertex of $S-X$ is in exactly one part of the partition, so we can say one part contains at least half of the vertices of $S-X$, and the other part contains at most half. 
This gives the following lemma.

%From this point on, we let $X$ be the smallest separator with respect to $V(G)$. Thus $\sep(G) \geq |X|$. Label the two parts of $G-X$ as $A$ and $B$. Now every vertex of $G-X$ is in either $A$ or $B$, so one must contain at least half of the total, and the other contains at most half of the total. Thus, without loss of generality, we can say the following:
%\begin{itemize}
%\item $\frac{1}{3}|G-X| \leq |A| \leq \frac{1}{2}|G-X|$,
%\item $\frac{1}{2}|G-X| \leq |B| \leq \frac{2}{3}|G-X|$.
%\end{itemize}

%In order to show that $X$ is forced to be large, we shall show that $G-X$ is forced to be small. 

\begin{lemma}
\label{lemma:part}
Let $X$ be a $p$-separator. Then $V(G-X)$ can be partitioned into two parts $A$ and $B$, with no edge between $A$ and $B$, such that
\begin{itemize}
\item $(1-p)|G-X| \leq |A| \leq \frac{1}{2}|G-X|$,
\item $\frac{1}{2}|G-X| \leq |B| \leq p|G-X|$.
\end{itemize}
\end{lemma}


%\section{Combinatorial Preliminaries}
%\label{section:comb}

We use a few important well known combinatorial results.

%\begin{theorem}[Erd\H{o}s-Ko-Rado \cite{EKR,EKRSimple}]
%\label{theorem:ekr}
%If $n \geq 2k$ and $\mathcal{A}$ is a family of distinct subsets of $[n]$, such that each is of size at most $k$, no subset is contained within another, and each pair of subsets intersects, then the maximum number of sets in $\mathcal{A}$ can be given by the binomial coefficient $\binom{n-1}{k-1}$.
%\end{theorem}

%Also, the following related result holds.
%\begin{lemma}
%When $n > 2k$, then the unique maximum families are the families in which all subsets in $\mathcal{A}$ have size $k$, and some element $i$ is in all subsets of $\mathcal{A}$.
%\end{lemma}

%Now, from this, the following result about Kneser graphs follows directly.

%\begin{lemma}[Independent Sets of Kneser graphs]
%\label{lemma:ekr}
%$\alpha(G) = \binom{n-1}{k-1}$, and the maximum independent sets are found by taking an element $i \in [n]$ and considering all vertices using $i$.
%\end{lemma}
%\begin{proof}
%Consider an independent set $X$ in the Kneser graph $G$. $X$ is a set of $k$-sets chosen from $[n]$. Now all $k$-sets of $X$ pairwise intersect as the vertices are pairwise non-adjacent. Because each of these sets has size $k$, no set is contained within another. Since $n \geq 2k+1$, $|X| \leq \binom{n-1}{k-1}$ by Theorem~\ref{theorem:ekr}. Also, as $n \geq 2k+1$, when $X$ is a maximum independent set, then $X$ contains all vertices using a fixed element $i$.
%\end{proof}

\begin{theorem}[Erd\H{o}s-Ko-Rado \cite{EKR,EKRSimple}]
\label{theorem:ekr}
Let $G$ be $\Kneser(n,k)$ for some $n \geq 2k$. Then $\alpha(G) = \binom{n-1}{k-1}.$
%Let $n \geq 2k$ and let $\mathcal{A}$ be an independent set in the Kneser graph $G$. Then $|\mathcal{A}| \leq \binom{n-1}{k-1}$. %If $n > 2k$ and $|\mathcal{A}| = \binom{n-1}{k-1}$, then $\mathcal{A}$ is the set of all vertices of $G$ containing a fixed element $i \in [n]$.
\end{theorem}

The original Erd\H{o}s-Ko-Rado Theorem defines $\mathcal{A}$ as a set of $k$-sets in $[n]$, such that the $k$-sets of $\mathcal{A}$ pairwise intersect. Our formulation in terms of vertices in the Kneser graph is clearly equivalent. %, however. Also, the original theorem can be extended to allow subsets of $[n]$ using at most $k$ elements, as long as no subset is contained within another. This is not relevant to our results, so it has been omitted. 
We will use Theorem~\ref{theorem:ekr} when determining an upper bound for $\tw(G)$.

The second major result is by Pyber \cite{Pyber}. %and relates to \emph{cross-intersecting families}.
Let $\mathcal{A}$ and $\mathcal{B}$ be sets of vertices of the Kneser graph $G$, such that for all $v \in \mathcal{A}$ and $w \in \mathcal{B}$ the pair $vw$ is not an edge. Then we say the pair $(\mathcal{A}, \mathcal{B})$ are \emph{cross-intersecting families}.

\begin{theorem}[Erd\H{o}s-Ko-Rado for Cross-Intersecting Families \cite{Pyber, MatsuToku}]
\label{theorem:ekrx}
Let $n \geq 2k$ and let $(\mathcal{A},\mathcal{B})$ be cross-intersecting families in the Kneser graph $G$. Then $|\mathcal{A}||\mathcal{B}| \leq \binom{n-1}{k-1}^2$. If $n \geq 2k+1$ and $(\mathcal{A},\mathcal{B})$ are cross-intersecting families such that $|\mathcal{A}||\mathcal{B}| = \binom{n-1}{k-1}^2$, then $\mathcal{A} = \mathcal{B} = \{v | i \in v\}$ for a fixed element $i \in [n]$.
\end{theorem}

As with Theorem~\ref{theorem:ekr}, the original formulation by Pyber of Theorem~\ref{theorem:ekrx} is more general. We have given the result in an equivalent form that is sufficient for our requirements. %The first statement in the theorem was originally proven by Pyber \cite{Pyber}. Matsumoto and Tokushige \cite{MatsuToku} proved the statement regarding the maximum choice of $\mathcal{A}$ and $\mathcal{B}$.

%\begin{theorem}[Erd\H{o}s-Ko-Rado for Cross-Intersecting Families]
%\label{theorem:ekrx}
%Let $\mathcal{A}$ and $\mathcal{B}$ be families of distinct subsets of $[n]$, such that
%\begin{itemize}
%\item each is of size at most $k$ (for $\mathcal{A}$) or of size at most $l$ (for $\mathcal{B}$),
%\item no subset in $\mathcal{A}$ is contained within another subset of $\mathcal{A}$ (and the equivalent holds for $\mathcal{B}$),
%\item any subset in $\mathcal{A}$ and subset in $\mathcal{B}$ intersect.
%\end{itemize}
%Then $|\mathcal{A}||\mathcal{B}| \leq \binom{n-1}{k-1}\binom{n-1}{l-1}$ whenever $n \geq 2k+l-2$ and $k \geq l$.
%\end{theorem}

%Now, in our case we can simply set $k=l$ and assume that all subsets have size exactly $k$, as we did in Lemma~\ref{lemma:ekr}. This second assumption does not actually change anything---Pyber \cite{Pyber} shows that all other cases are equivalent to the uniform size case. Also, given that $k=l$, it is actually sufficient to assume that $n \geq 2k$, see Pyber \cite{Pyber} again. Matsumoto and Tokushige \cite{MatsuToku} extended this to show that when $n \geq 2k+1$, the maximum cross-intersecting families are of the form $\mathcal{A} = \mathcal{B} = \{ v : v \in \binom{[n]}{k}, i \in v \}$ for some fixed $i \in [n]$. (Note their result is slightly more general, this is just the result when $k=l$.)

Let $X$ be a $\frac{2}{3}$-separator and $A$,$B$ the parts of the vertex partition of $G-X$ as in Lemma~\ref{lemma:part}. Now for all $v \in A$ and $w \in B$, $v$ and $w$ are in different components and as such are non-adjacent. So $(A,B)$ are cross-intersecting families. We know $|A| = c|G-X|$ where $\frac{1}{3} \leq c \leq \frac{1}{2}$. By Theorem~\ref{theorem:ekrx}, it follows that $c(1-c)|G-X|^{2} \leq \binom{n-1}{k-1}^2$. It follows that $|G-X| \leq \frac{3}{\sqrt{2}}\binom{n-1}{k-1}$. (We leave the precise calculation to the reader.) This gives a lower bound on $|X|$, and as such a lower bound on the treewidth (by Theorem~\ref{theorem:sep}). Hence $\tw(G) \geq \binom{n}{k} - \frac{3}{\sqrt{2}}\binom{n-1}{k-1} -1$.

However, note that the parts $A$ and $B$ of $V(G-X)$ are vertex disjoint, but that the definition of a pair of cross-intersecting families does not require this. In fact, Theorem~\ref{theorem:ekrx} shows that in the case where $|\mathcal{A}||\mathcal{B}|$ is maximised, $\mathcal{A}=\mathcal{B}$. We show we can do better than the above na\"{i}ve lower bound on $\tw(G)$ when $\mathcal{A}$ and $\mathcal{B}$ are disjoint. 

%Recall the definition of separators in Section~\ref{section:sep}, including the vertex sets $A$ and $B$ in $V(G)-X$. If $v \in A$ and $w \in B$, then there is no edge $vw$, and $v$ and $w$ must intersect. So $A,B$ are cross-intersecting families. However, there are a few issues. Firstly, the results about cross-intersecting families do not assume that $\mathcal{A}$ and $\mathcal{B}$ are disjoint; in fact, the maximum case as shown above occurs when $\mathcal{A} = \mathcal{B}$. This implies we should be able to do better than the general bound in our case, as $A$ and $B$ are disjoint sets of vertices.

%Also, what we really desire is an upper bound on $|Y| = |A| + |B|$, not an upper bound on $|A||B|$. Given Proposition~\ref{remark:abbounds}, we can show that $|Y| \leq \frac{\sqrt{3}}{2}\binom{n-1}{k-1} \approx 2.1\binom{n-1}{k-1}$. For Theorem~\ref{theorem:main} we improve $\frac{\sqrt{3}}{2}$ to $1$, and for Theorem~\ref{theorem:secondary}, we improve it slightly to $2$.

Before considering our final preliminary, we provide the following definitions. %Finally, we shall consider some of the tools used by Pyber \cite{Pyber} and Matsumoto and Tokushige \cite{MatsuToku}, which we shall use to prove our results.
%\begin{definition}
%\label{definition:colex}
Consider all of the $a$-sets in $[b]$. Define the \emph{colexicographic} or \emph{colex} ordering on the $a$-sets as follows: if $x$ and $y$ are distinct $a$-sets, then $x < y$ when $\max(x-y) < \max(y-x)$. This is a strict total order. %Note that since $x \neq y$, it follows $x-y$ and $y-x$ are non-empty and disjoint, so this is well-defined.
%\end{definition}
%
%\begin{definition}
%\label{definition:first}
A set $X$ of $a$-sets in $[b]$ is \emph{first} if $X$ consists of the first $|X|$ $a$-sets in the colex ordering of all the $a$-sets in $[b]$.
%\end{definition}

%\begin{remark}
%\label{remark:firstsets}
Now consider the colex ordering of $a$-sets in $[b]$. All of the $a$-sets in $[i]$ (where $i<b$) come before any $a$-set containing an element greater than or equal to $i+1$. To see this, note if $x$ is an $a$-set in $[i]$ and $y$ is an $a$-set with $j \in y$ such that $j \geq i+1$, then $\max(x-y) \leq \max(x) \leq i$, and $\max(y-x) \geq j \geq i+1$ as $j \in y-x$. %Similarly, if $x$ and $y$ share their $j$ maximum elements, then the same principle holds on the remaining elements. That is, if $x$ and $y$ both use $n$, but the rest of $x$ is contained with $\{1, \dots, i\}$ and $y$ uses $i+1$, then $x < y$. 
We will use this when determining the make-up of first sets in Section~\ref{section:lbone}.  
%\end{remark}

%\begin{definition}
%\label{definition:shadow}
Let $X$ be a set of $a$-sets in $[b]$. For $c \leq a$, the \emph{$c$-shadow of $X$} is the set $\{ x : |x| = c,$ and $\exists y \in X$ such that $x \subseteq y\}$. That is, the $c$-shadow contains all $c$-sets that are contained within $a$-sets of $X$.
%\end{definition}
%
%\begin{definition} %NOT SURE IF REQUIRED, or exactly the best place to put this
If $x$ is an $a$-set in $[b]$, let the \emph{complement} of $x$ be the $(b-a)$-set $y = [b]-x$. If $X$ is a set of $a$-sets on $[b]$, then the \emph{complement} of $X$ is $\overline{X} := \{ y: y$ is the complement of some $x \in X \}$. Note $|X| = |\overline{X}|$.
%\end{definition}

\begin{lemma}[A first set minimises the shadow \cite{Kruskal,Katona} (see \cite{Frankl2} for a short proof)]
\label{lemma:minshadow}
Let $X$ be a set of $a$-sets on $[b]$, $c \leq a$ and $S$ be the $c$-shadow of $X$. Suppose $|X|$ is fixed but $X$ is not. Then $|S|$ is minimised when $X$ is first.
\end{lemma}

%This lemma follows from the Kruskal-Katona Theorem (\cite{Kruskal,Katona}, but see \cite{Frankl2} for a short proof). 
This idea is also used by Pyber \cite{Pyber} and Matsumoto and Tokushige \cite{MatsuToku}. Intuitively, the shadow $S$ should be minimised whenever the $a$-sets of $X$ ``overlap" as much as possible, so that each $c$-set in $S$ is a subset of as many $a$-sets as possible.

%I think we are good up to here.
\section{Upper Bound for Treewidth}
\label{section:upper}
This section proves the upper bounds on $\tw(G)$ in Theorems~\ref{theorem:main} and \ref{theorem:ktwo}.

In both Theorem~\ref{theorem:main} and~\ref{theorem:ktwo}, the upper bound is almost always $\binom{n-1}{k}-1$. The only exceptions are the trivial cases (when $n \leq 2k$), and the case when $k=2$ and $n=5$, which is the Petersen graph. The Petersen graph is well-known to have treewidth $4$ (\cite{peterstree}, for example). What follows is a general upper bound on the treewidth of any graph, which is sufficient to prove the remaining cases.

\begin{lemma}
\label{lemma:gub}
If $H$ is any graph, then $\tw(H) \leq \max\{\Delta(H), |V(H)| - \alpha(H) - 1\}$.
\end{lemma}
\begin{proof}
Let $\alpha := \alpha(H)$. We shall construct a tree decomposition with underlying tree $T$, where $T$ is a star with $\alpha(H)$ leaves. Let $R$ be the bag indexed by the central node of $T$, and label the other bags $B_1, \dots, B_{\alpha}$. Let $X := \{x_1, \dots x_\alpha \}$ be a maximum independent set in $H$. Let $R:= V(H)-X$ and $B_i := N(x_{i}) \cup \{x_i\}$ for all $i \in \{1, \dots, \alpha\}$. We now show this is a tree decomposition:

Any vertex not in $X$ is contained in $R$. Given the structure of the star, any induced subgraph containing the central node is connected. Alternatively, if a vertex is in $X$, then it appears only in bags indexed by leaves. However, since $X$ is an independent set, $x_i \in X$ appears only in $B_i$, not in any other bag $B_j$. A single node is obviously connected. 
If $vw$ is an edge of $H$, then at most one of $v$ and $w$ is in $X$. Say $v = x_i \in X$. Then $v,w$ both appear in the bag $B_i$. Otherwise neither vertex is in $X$, and both vertices appear in $R$.

So this is a tree decomposition. The size of $R$ is $|V(H)| - \alpha(H)$. The size of $B_{i}$ is the degree of $x_i$, plus one, which is at most $\Delta(H) + 1$. From here our lemma is proven.
\end{proof}

We now consider this result for the Kneser graph itself.
\begin{lemma}
If $G$ is a Kneser graph with $k \geq 2$ and $n \geq 2k+1$, then $\tw(G) \leq \binom{n}{k-1} - 1$.
\end{lemma}
\begin{proof}
%By Lemma~\ref{lemma:gub}, $\tw(G) \leq \max\{\Delta(G), |V(G)| - \alpha(G) - 1\}$. Since $G$ is regular, $\Delta(G) = \binom{n-k}{k}$ by Proposition~\ref{prop:regular}. Also, by Lemma~\ref{lemma:ekr}, $\alpha(G) = \binom{n-1}{k-1}$ and $|V(G)| = \binom{n}{k}$. Thus $\tw(G) \leq \max\{\binom{n-k}{k}, \binom{n-1}{k} - 1\} = \binom{n-1}{k} -1$, since $k \geq 2$ and $n \geq 2k+1$.
By Lemma~\ref{lemma:gub} and Theorem~\ref{theorem:ekr}, and since $n \geq 2k+1$, $$\tw(G) \leq \max\left\{\Delta(G), |V(G)| - \alpha(G) - 1\right\} = \max\left\{\binom{n-k}{k}, \binom{n}{k} - \binom{n-1}{k-1} - 1\right\}.$$ Since $k \geq 2$,  $\tw(G) \leq \binom{n-1}{k}-1$, as required.
\end{proof}

%Now we consider the $k=2$ and $n=5$ case. Note that this graph is in fact the famous Petersen graph. By showing $\tw(G) \leq 4$ in this case, we are showing that $\tw(G) \leq \binom{n-1}{k} - 2$, that is, one less than in the previous cases.

%\begin{lemma}
%Let $G$ be the Petersen graph, the Kneser graph when $k=2,n=5$. Then $\tw(G) \leq 4$.
%\end{lemma}
%\begin{proof}
%We simply construct a tree decomposition $(T, (B_{x : x \in V(T)}))$ for $G$ where each bag contains at most five vertices.
%Root $T$ at a node $r$, and let $r$ have three children $x,y,z$. The nodes $x$ and $y$ themselves have children $a$ and $b$ respectively. These six nodes are the only nodes of $T$. Construct the bags as follows:
%\begin{itemize}
%\item $B_r = \{(3,4),(1,5),(2,5),(3,5),(4,5)\}$
%\item $B_x = \{(1,4),(1,5),(2,5),(3,5),(4,5)\}$
%\item $B_y = \{(2,4),(1,5),(2,5),(3,5),(4,5)\}$
%\item $B_z = \{(1,2),(3,4),(3,5),(4,5)\}$
%\item $B_a = \{(2,3),(1,4),(1,5),(4,5)\}$
%\item $B_b = \{(1,3),(2,4),(2,5),(4,5)\}$
%\end{itemize}
%By inspection, this is a valid tree decomposition of $G$.
%\end{proof}

%This proves all required upper bounds.

%\section{Lower Bound for Treewidth in Theorem~\ref{theorem:main}}
\section{Separators in the Kneser Graph}
\label{section:lbone}
To complete the proof of Theorem~\ref{theorem:main}, it is sufficient to prove a lower bound on the treewidth. The following lemma, together with Theorem~\ref{theorem:sep}, provides this. It is the heart of the proof of Theorem~\ref{theorem:turan}.

\begin{lemma}
\label{lemma:keylemma}
Let $X$ be a $p$-separator of the Kneser graph $G$. If $n \geq \max(4k^2 - 4k +3, \frac{1}{1-p}(k^2 -1)+2)$, then $|X| \geq \binom{n-1}{k}$.
\end{lemma}

%Firstly, we shall prove a lower bound for the treewidth as required in Theorem~\ref{theorem:main}, which will complete the proof of that theorem.
%Assume, for the sake of a contradiction, that $\tw(G) < \binom{n-1}{k}-1$. Hence $\sep(G) < \binom{n-1}{k}$ by Theorem~\ref{theorem:sep}. So there exists a separator $X$ with respect to $V(G)$ with $|X| < \binom{n-1}{k}$; this is the statement we shall obtain a contradiction for. %This is changed line.
%Then $|G-X| > \binom{n-1}{k-1}$. By Lemma~\ref{lemma:part}, $G-X$ has two parts $A$ and $B$ such that $\frac{1}{3}|G-X| \leq |A| \leq \frac{1}{2}|G-X|$ and $\frac{1}{2}|G-X| \leq |B| \leq \frac{2}{3}|G-X|$ and no edge has an endpoint in both $A$ and $B$. Recall that for Theorem~\ref{theorem:main}, we assume $n \geq 4k^2 - 4k + 3$.

\begin{proof}
Assume, for the sake of a contradiction, that $|X| < \binom{n-1}{k}$. Then $|G-X| > \binom{n-1}{k-1}$. By Lemma~\ref{lemma:part}, $G-X$ has two parts $A$ and $B$ such that $(1-p)|G-X| \leq |A| \leq \frac{1}{2}|G-X|$ and $\frac{1}{2}|G-X| \leq |B| \leq p|G-X|$ and no edge has an endpoint in both $A$ and $B$. 

For a given element $i \in [n]$, let $A_i := \{v \in A: i \in v\}$. Also define $A_{-i} := \{v \in A: i \notin v\}$. So $A_i$ and $A_{-i}$ partition the set $A$, for any choice of $i$. Define analogous sets for $B$.

\begin{claim}
\label{claim:akth}
There exists some $i$ such that $|B_{i}| \geq \frac{1}{k}|B|$.
\end{claim}
\begin{proof}
As $|A| \geq (1-p)|G-X| > 0$, there is a vertex $v \in A$. Without loss of generality, $v = \{1, \dots, k\}$. Each $w \in B$ is not adjacent to $v$, and so $w$ and $v$ intersect. Thus each $w$ must contain at least one of $1, \dots, k$. Hence at least one of these elements appears in at least $\frac{1}{k}|B|$ of the vertices of $B$, as required.
\end{proof}

Without loss of generality, $|B_n| \geq \frac{1}{k}|B|$.

\begin{claim}
\label{claim:lbbn}
$|B_n| > \binom{n-3}{k-2} + \binom{n-2}{k-2}$.
\end{claim}
\begin{proof}
$|B| \geq \frac{1}{2}|G-X| \geq \frac{1}{2}\binom{n-1}{k-1}$. Then by Claim~\ref{claim:akth} and our subsequent assumption, $|B_{n}| \geq \frac{1}{k}|B| \geq \frac{1}{2k}|G-X| \geq \frac{1}{2k}\binom{n-1}{k-1}$. Assume for the sake of a contradiction that $|B_n| \leq \binom{n-3}{k-2} + \binom{n-2}{k-2}$.
So $$\frac{1}{2k}\binom{n-1}{k-1} \leq \binom{n-3}{k-2} + \binom{n-2}{k-2}.$$
Thus $$(n-1)! \leq 2k(k-1)(n-k)((n-3)! + (n-2)!).$$
Hence $$n^2 - 3n + 2 = (n-1)(n-2) \leq 2k(k-1)(2n-k-2) = 4k^{2}n -4kn -2k^3 - 2k^2 + 4k.$$
%$$n^2 - 3n +2 \leq 4k^2n - 2k^3 -4kn - 2k^2 + 4k$$
So $n^2 + (4k-4k^2 - 3)n + 2k^3 + 2k^2 - 4k + 2 \leq 0.$
Since $n \geq 4k^2 - 4k + 3$, it follows $2k^3 + 2k^2 - 4k + 2 \leq 0$. Given that $k \geq 1$, this provides our desired contradiction.
\end{proof}

%GOOD UP TO HERE, I THINK -
%Given a vertex $v$, there are $(n-k)$ elements of $\{1, \dots, n\}$ which are not in $v$. Label this set of $(n-k)$ elements as $\overline{v}$, which we call the \emph{complement of $v$}, or just as a \emph{complement}.  For any set of vertices $Z$, define the set $\overline{Z} = \{\overline{v} : v \in Z\}$. There is a one-to-one correspondence between vertices and complements, so $|Z| = |\overline{Z}|$.

Consider the set $\overline{A_{-n}}$, that is, the complements of the vertices in $A$ that do not contain $n$. So every set in $\overline{A_{-n}}$ contains $n$. Let $\overline{A_{-n}}^{*} := \{ \overline{v} - n: \overline{v} \in \overline{A_{-n}}\}$. That is, remove $n$ from each set in $\overline{A_{-n}}$. There is clearly a one-to-one correspondence between $(n-k)$-sets in $\overline{A_{-n}}$ and $(n-k-1)$-sets in $\overline{A_{-n}}^{*}$.

Similarly, define $B_n^* := \{ v-n : v \in B_n\}$. That is, remove from each vertex of $B_n$ the element $n$, which they all contain. The resultant sets are $(k-1)$-sets in $[n-1]$.

\begin{claim}
\label{claim:avshadow}
If $v^* \in B_n^*$ and $\overline{w}^* \in \overline{A_{-n}}^*$, then $v^* \not\subseteq \overline{w}^*$.
\end{claim}
\begin{proof}
Assume, for the sake of a contradiction, that $v^* \subseteq \overline{w}^*$. Then it follows that $v \subset \overline{w}$, by re-adding $n$ to both sets. Thus $v$ and $w$ are adjacent. However, $v \in B_n \subset B$ and $w \in A_n \subset A$, which is a contradiction.
\end{proof}

Let $S$ be the $(k-1)$-shadow of $\overline{A_{-n}}^*$. Hence if $v \in B_n^*$, then $v \notin S$, by Claim~\ref{claim:avshadow}.
%that is, $S := \{ v: v \in \binom{[n-1]}{k-1}, v \subset w$ for some $w \in \overline{A_{-n}}^*\}$. 
So, it follows that $$B_n^* \subseteq \binom{[n-1]}{k-1} - S.$$

Hence we have an upper bound for $|B_n^*|$ when we take $|S|$ to be minimised. By Lemma~\ref{lemma:minshadow}, $|S|$ is minimised when $\overline{A_{-n}}^*$ is first. %, that is, it is the first $|\overline{A_{-n}}^*|$ $(n-k-1)$-sets in the colexicographic ordering of $1, \dots, n$.

\begin{claim}
\label{claim:ubann}
$|A_{-n}| \leq \binom{n-3}{k-2}$.
\end{claim}
\begin{proof}
$|A_{-n}| = |\overline{A_{-n}}| = |\overline{A_{-n}}^*|$, so it is sufficient to show that $|\overline{A_{-n}}^*| \leq \binom{n-3}{k-2}$. Assume for the sake of contradiction that $|\overline{A_{-n}}^*| \geq \binom{n-3}{k-2} = \binom{n-3}{n-k-1}$. 

Firstly, we show that $|S| \geq \binom{n-3}{k-1}$. It is sufficient to prove this lower bound when $|S|$ is minimised. Hence we can assume that $\overline{A_{-n}}^*$ is first, and contains the first $\binom{n-3}{n-k-1}$ $(n-k-1)$-sets in the colexicographic ordering. That is, it contains all $(n-k-1)$-sets on $[n-3]$. This is because there are $\binom{n-3}{n-k-1}$ such sets, and they come before all other sets in the ordering. In that case, $S$ contains all $(k-1)$-sets in $[n-3]$. As all of the $(k-1)$-sets in $[n-3]$ are in $S$, it follows that $|S| \geq \binom{n-3}{k-1}$, as required.

%%WAS IN ABOVE PARAGRAPH To see this, consider a $(k-1)$-set chosen from $\{1, \dots, n-3\}$. Then add other elements of $\{1, \dots, n-3\}$ to obtain an $(n-k-1)$-set on $\{1, \dots, n-3\}$. So this $(n-k-1)$-set is in $\overline{A_{-n}}^*$ and so our original $(k-1)$-set is in $S$.

%Now, we cannot assume that $\overline{A_{-n}}^*$ is first, but when it is first, $|S|$ is minimised. Thus, irrespective of $\overline{A_{-n}}^*$, we know that $|S| \geq \binom{n-3}{k-1}$. 
Then it follows that $|B_n^*| \leq \binom{n-1}{k-1} - \binom{n-3}{k-1}  = \binom{n-3}{k-2} + \binom{n-2}{k-2}$. However,
$|B_n^*| = |B_n| > \binom{n-3}{k-2} + \binom{n-2}{k-2}$ by Claim~\ref{claim:lbbn}. This provides our desired contradiction.
\end{proof}

\begin{claim}
\label{claim:anb}
%$|A_n| \geq k|A_{-n}|$.
$|A_n| \geq \frac{k}{k+1}|A|$.
\end{claim}
\begin{proof}
First, show that $|A_n| \geq k|A_{-n}|$. Suppose otherwise, for the sake of a contradiction. By Claim~\ref{claim:ubann}, $|A| = |A_n| + |A_{-n}| < (k+1)|A_{-n}| \leq (k+1)\binom{n-3}{k-2}$. But $|A| \geq (1-p)|G-X|$. Hence $(1-p)\binom{n-1}{k-1} < (k+1)\binom{n-3}{k-2}$. Thus $(n-1)(n-2) < \frac{1}{1-p}(k+1)(k-1)(n-k) \leq \frac{1}{1-p}(k+1)(k-1)(n-2)$. Thus $n < \frac{1}{1-p}(k^2 - 1)+1$, which contradicts our lower bound on $n$.
%\begin{corollary}
%\label{corollary:anb}
%$|A_n| \geq \frac{k}{k+1}|A|$
%\end{corollary}
%\begin{proof}

Then $|A_n| \geq k|A_{-n}| = k(|A| - |A_n|)$. So $(k+1)|A_n| \geq k|A|$ as required.
\end{proof}

\begin{claim}
\label{claim:bnisb}
$B_n = B$.
\end{claim}
\begin{proof}
Suppose, for the sake of a contradiction, that there exists some vertex $v \in B$ such that $n \notin v$. So each $w \in A_n$ contains $n$ (by definition) and some element of $v$ (which is not $n$), since $vw$ is not an edge. Any vertex of $A_n$ can be constructed as follows---take element $n$, choose one of the $k$ elements of $v$, and choose the remaining $k-2$ elements from the remaining $n-2$ elements of $[n]$. Thus $$|A_n| \leq 1\cdot k\binom{n-2}{k-2}.$$ Note this is actually a weak upper bound, since we have counted some of the vertices of $A_n$ more than once. Recall $|A| \geq (1-p)|G-X| \geq (1-p)\binom{n-1}{k-1}$. So by Claim~\ref{claim:anb}, $$\frac{(1-p)k}{(k+1)}\binom{n-1}{k-1} \leq \frac{k}{k+1}|A| \leq k\binom{n-2}{k-2}.$$
Thus $\frac{n-1}{k-1} \leq \frac{1}{1-p}(k+1)$ and $n \leq \frac{1}{1-p}(k^2-1)+1$, which contradicts our lower bound on $n$. 
\end{proof}

\begin{claim}
\label{claim:anisa}
$A_n = A$.
\end{claim}
\begin{proof}
This follows by essentially the same argument as Claim~\ref{claim:bnisb}. Assume our claim does not hold and there exists $v \in A$ such that $n \notin v$. By Claim~\ref{claim:bnisb}, $|B_n| = |B| \geq \frac{1}{2}\binom{n-1}{k-1}$. There is an upper bound on $|B_n|$ equal to the upper bound on $|A_n|$ in the previous proof. Then
$$\frac{1}{2}\binom{n-1}{k-1} \leq |B| = |B_n| \leq k\binom{n-2}{k-2},$$ and so $n \leq 2k(k-1)+1.$ This contradicts our lower bound on $n$.
\end{proof}

Claims~\ref{claim:bnisb} and \ref{claim:anisa} show that every vertex in $G-X = A \cup B$ contains $n$. Thus $|G-X| \leq \binom{n-1}{k-1}$ and $|X| \geq \binom{n-1}{k}$, our desired contradiction. %However $|X| \leq \sep(G) \leq \tw(G) + 1$, and $\tw(G) < \binom{n-1}{k} -1$ by our initial assumption. %%MODIFIED LINE
\end{proof}

%Hence, we obtain our desired contraction. We now have an upper and lower bound for $\tw(G)$ when $n \geq 4k^2 - 4k +3$, and Theorem~\ref{theorem:main} is proven.

By Lemma~\ref{lemma:keylemma}, if $X$ is a $\frac{2}{3}$-separator of the Kneser graph $G$ and $n \geq 4k^2 -4k + 3$, then $|X| \geq \binom{n-1}{k}$. Hence by Theorem~\ref{theorem:sep}, $\tw(G) \geq \binom{n-1}{k}-1$. This proves Theorem~\ref{theorem:main}. 

Also, Lemma~\ref{lemma:keylemma} allows us to prove Theorem~\ref{theorem:turan}.
%As a result, we can easily prove Theorem~\ref{theorem:turan}.
%\begin{theorem}
%Let $H$ be the intersection graph with $V(H) = \binom{[n]}{k}$. If $H'$ is a complete multipartite subgraph of $H$ with equal sized colour classes, then $|V(H')| \leq \binom{n-1}{k-1}$.
%\end{theorem}
\begin{proof}[Proof of Theorem~\ref{theorem:turan}]
Let $C_1, \dots, C_r$ be the colour classes of $H$ and recall $G = \Kneser(n,k)$. Let $X:= V(\overline{G}) - V(H)$, so that $X,C_1, \dots, C_r$ is a partition of the vertex set of $\overline{G}$ (and also $G$). In $G$ there are no edges between any pair $C_i,C_j$, and $|C_i| \leq p|H| = p|G-X|$ for each $i$. So $X$ is a $p$-separator of $G$, and $|X| \geq \binom{n-1}{k}$ by Lemma~\ref{lemma:keylemma}. Hence $|H| \leq \binom{n-1}{k-1}$.
%Let $x \in C_i$ and $y \in C_j$ such that $i \neq j$. So $x$ and $y$ must intersect, and so they are not adjacent to each other in $\Kneser(n,k)$. So $X,C_1, \dots, C_r$ is a partition of the vertex set of $\Kneser(n,k)$ with no edge between any pair $C_i,C_j$ and  Hence no component of $\overline{H}-X$ contains more than $\frac{2}{3}$ of the vertices of $\overline{H}-X$, and $X$ is a separator for $\overline{H}$. Since $\overline{H}$ is the Kneser graph and $n \geq 4k^2 - 4k +3$, it follows from Corollary~\ref{corollary:hardtobreakvg} that $|X| \geq \binom{n-1}{k}$. So $|C_1 \cup \dots \cup C_r| = V(H') \leq \binom{n-1}{k-1}$, as required.
\end{proof} 

\section{Lower Bound for Treewidth in Theorem~\ref{theorem:ktwo}} %%BEFORE RE-WRITE, 1.5 PAGES
\label{section:ktwolow}
To complete our proof of Theorem~\ref{theorem:ktwo}, we need to obtain a lower bound on the treewidth when $k=2$. If $n \leq 4$, then Theorem~\ref{theorem:ktwo} is trivial. When $n=5$, then $G$ is the Petersen graph, which has a $K_5$-minor forcing $\tw(G) \geq 4$. Hence we may assume that $n \geq 6$. 

Assume, for the sake of a contradiction that $\tw(G) < \binom{n-1}{2} -1$. Let $(T, (B_x:x \in V(T)))$ be a minimum width tree decomposition for $G$, and normalise the tree decomposition such that if $xy \in E(T)$, then $B_x \not\subseteq B_y$ and $B_y \not\subseteq B_x$. By Theorem~\ref{theorem:sep}, there exists a $\frac{2}{3}$-separator $X$ such that $|X| < \binom{n-1}{2}$. In fact, by the original proof in \cite{GMII}, we can go further and assert that $X$ is a subset of a bag of $(B_x:x \in V(T))$.

Now $|G-X| = \binom{n}{2} - |X| > \binom{n-1}{1} = n-1$. By Lemma~\ref{lemma:part}, $V(G-X)$ has two parts $A$ and $B$ such that $\frac{1}{3}|G-X| \leq |A|,|B| \leq \frac{2}{3}|G-X|$ and there is no edge with an endpoint in $A$ and $B$. (Note that this bound on $|A|$ and $|B|$ is slightly weaker than in Lemma~\ref{lemma:part}, but has the benefit of being the same on both parts.) As $n \geq 6$, it follows that $|A|,|B| \geq 2$. By Theorem~\ref{theorem:ekr}, $V(G-X)$ is too large to be an independent set, and so it contains an edge, with both endpoints in $A$ or both endpoints in $B$.

Without loss of generality this edge is $\{1,2\}\{3,4\} \in A$. Then $B \subseteq \{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$. If $B$ contains an edge, then $V(G-X) \subseteq \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$ and has maximum order $6$. Otherwise, without loss of generality, $B = \{\{1,3\},\{1,4\}\}$ and $A = \{\{3,4\},\{1,i\}| i \notin \{1,3,4\}\}$, so $|G-X| = n$. (Note $A$ must be exactly that set, or $|G-X|$ is too small.)

If $n \geq 7$, then $|G-X| \geq 7$ and the first case cannot occur. However in the second case, $|B| = 2 < \frac{1}{3}\cdot 7 \leq \frac{1}{3}n$. So neither case can occur, and we have forced a contradiction on either $|G-X|$ or $|B|$. This completes the proof when $n \geq 7$. Hence, let $n = 6$, and  note $|G-X|=6$ in either case.

Now we use the fact that $X$ is a subset of some bag $B_x$. Now for all $x \in V(T)$, $|B_x| \leq \binom{5}{2}-1 = 9$. As $|G-X|=6$, it follows $|X|=9$. Hence $X$ is exactly a bag of maximum order. For either choice of $G-X$, note that $A$ is a connected component. So there is some subtree of $T - x$ that contains all vertices of $A$. Let $y$ be the node of this subtree adjacent to $x$. Also note, for either choice of $G-X$, that each vertex of $X$ has a neighbour in $A$. So every vertex of $B_x$ is also in bag $B_y$, which contradicts our normalisation.

%Let $(T, (B_x:x \in V(T))$ be a tree decomposition for $G$ such that $|B_x| \leq \binom{5}{2}-1=9$ for all $x \in V(T)$. We can normalise this tree decomposition so that $|B_x|=9$ for all $x \in V(T)$, and so $|B_x \cap B_y| = 8$ for each $xy \in E(T)$. It is also known that either $B_x$ is a separator (with respect to $V(G)$) for some $x \in V(T)$, or $B_x \cap B_y$ is a separator (with respect to $V(G)$) for some $xy \in E(T)$ (\cite{GMII}, see also \cite{pttt}). In the second case, $|X| = |B_x \cap B_y| = 8$ and $|G-X| = \binom{6}{2} - 8 = 7$, which is too large. So there exists a separator with respect to $V(G)$ denoted $X$ such that $X = B_x$. For either choice of $G-X$ note that $A$ is a connected component. So there is some subtree of $T - x$ that contains all vertices of $A$. Let the root of this subtree be denoted $y$. Also note, for either choice of $G-X$, that each vertex of $X$ has a neighbour in $A$. So every vertex of $B_x$ is also in bag $B_y$, which contradicts our normalisation.

Thus, if $n \geq 6$, then $\tw(G) \geq \binom{n-1}{2}-1$. This completes the proof of Theorem~\ref{theorem:ktwo}.

\section{Open Questions}
We conjecture that Theorem~\ref{theorem:main} should also hold for smaller values of $n$.
\begin{conjecture}
\label{conjecture:full}
Let $G$ be a Kneser graph with $n \geq 3k$ and $k \geq 2$. Then $\tw(G) = \binom{n-1}{k}-1$.
\end{conjecture}
This conjecture follows directly from Theorem~\ref{theorem:ktwo} when $k=2$. The Petersen graph also shows that $n \geq 3k$ is a tight bound when $k=2$.

In general, we can determine a slightly better tree decomposition when $n < 3k-1$. Let $X = \{v \in V(G): 1 \in v\}$, and let $W$ be an independent set in $V(G)-X$ such that no two vertices of $W$ have a common neighbour in $X$. We define a tree decomposition for $G$ with underlying tree $T$ as follows. Let $r$ denote the root node of $T$, and let $r$ have one child node for each vertex in $W$ and each vertex in $X$ adjacent to no vertex in $W$. Label each of these child nodes by their associated vertex of $G$. Let each node labeled by a vertex $w \in W$ have one child node for each vertex of $N(w) \cap X$. Label each of those child nodes by their associated vertex of $G$, and note that since every vertex of $X$ has at most one neighbour in $W$, no vertex of $G$ labels more than one node of $T$.

Define the bag indexed by $r$ to be $V(G)-W-X$. Note this bag contains less than $\binom{n-1}{k}$ vertices when $W \neq \emptyset$. If a node is labeled by a vertex $v \in X$, let the corresponding bag be $N(v) \cup \{v\}$. These bags contain $\binom{n-k}{k}+1$ vertices. If a node is labeled by a vertex $w \in W$, let the corresponding bag be $\{w\} \cup \{u : uw \in E(G), 1 \notin u\} \cup \{u : ux \in E(G)$ where $xw \in E(G)$ and $1 \in x\}$. These bags contain less than $\binom{n-1}{k}$ vertices whenever $|W| \geq 2$, as they contain no vertex in $X$, and each contains only one vertex from $W$. This is a valid tree decomposition, but we omit the proof. When $|W| \geq 2$, the width of this tree decomposition is less than the width given by Lemma~\ref{lemma:gub}.

%We say these nodes are associated to the stated vertices. For each vertex of $X$ with a neighbour in $W$, note by definition it must have exactly one. For each such vertex $v$, add an associated leaf node adjacent to the node associated with the neighbour of $v$ in $W$. These are all nodes of $T$, there are $|W| + |X| + 1$ of them. Then let $B_y$ be a bag indexed by node $y$. If $y$ is associated with some $v \in X$, then let $B_{y} = N(v) \cup \{v\}$. If $y$ is associated with some $v \in W$, then let $B_y = \{v\} \cup \{u : uv \in E(G), 1 \notin u\} \cup \{u : ux \in E(G)$ where $xv \in E(G)$ and $1 \in x\}$. If $y = r$, then let $B_y = V(G) - W -X$. This is a tree decomposition, but we omit the proof.
%Now assume that $|W| \geq 2$. Now $B_r$ contains less than $\binom{n-1}{k}$, since it does not contain the $\binom{n-1}{k-1}$ of $X$ or the vertices of $W$. If $y$ is associated with a vertex of $W$, then $B_y$ does not contain any vertex using $1$, or any vertex of $W$ other than the one $y$ is associated with. If $y$ associated with a vertex of $X$, it contains $\binom{n-k}{k}+1$ vertices. So in either case, $|B_y| < \binom{n-1}{k}$. Hence the width of this tree decomposition is less than $\binom{n-1}{k} - 1$.

However, when $|W| \leq 1$, this tree decomposition has the same width as given by Lemma~\ref{lemma:gub}. We can construct $W$ such that $|W| \geq 2$ iff $n < 3k-1$. For example, let $W = \{\{2,\dots,(k+1)\},\{(k+1), \dots, 2k\}\}.$ If $n \leq 3k-2$, then any vertex of $X$ must be non-adjacent to at least one vertex of $W$. Alternatively, if $n \geq 3k-1$ and $|W| \geq 2$, then there exists two vertices $x,y \in W$ such that $|x \cup y| \leq 2k-1$. Then $X$ contains a vertex adjacent to both $x$ and $y$.
Hence, for general $n$, we cannot improve the lower bound on $n$ in Theorem~\ref{theorem:main} to $3k-2$ or below. This does leave a question about what may occur for $n=3k-1$. It is possible that Theorem~\ref{theorem:main} holds for $n \geq 3k-1$, with the Petersen graph as a single exception. 

%%FOLLOWING TWO PROBABLY IN THESIS

%%Let $X$ be a $p$-separator and say $A$ and $B$ are the parts of $V(G-X)$ by Lemma~\ref{lemma:part}. In Lemma~\ref{lemma:keylemma}, we showed that $B_n^* \subseteq \binom{[n-1]}{k-1} - S$, where $S$ is the $(k-1)$-shadow of $\overline{A_{-n}}^*$. Similarly, we can argue that $B \subseteq \binom{[n]}{k} - S$, where $S$ is the $k$-shadow of $\overline{A}$. This is a key point in the papers by Pyber \cite{Pyber} and Matsumoto and Tokushige \cite{MatsuToku}. However, since $A$ and $B$ are disjoint, we could say that $B \subseteq \binom{[n]}{k} - (S \cup A)$, since $B$ cannot contain a vertex in $A$, or a neighbour of such a vertex. However, we do not know what choice of $A$ minimises $S \cup A$. (It can be seen that it is not the first $|A|$ sets under the colex order.) %Determining the optimal choice of $A$ would allow us to use much stronger arguments, and hopefully improve the lower bound on $n$. 

%%If we improved Lemma~\ref{lemma:keylemma} by determining the optimal $A$, then we would improve both Theorem~\ref{theorem:main} and \ref{theorem:turan}. We believe that this should be possible, and that the optimal choice of $A$ that minimises $S \cup A$ should be similar to (but not exactly) the first $|A|$ sets under colex order. This would hopefully allow an argument similar to that of Pyber, and give a lower bound on $n$ that is linear in terms of $k$ (ideally with a small constant).

%Recall in Section~\ref{sec:lbtwo} we showed that $B \subseteq V(G) - S$, where $S$ is the $k^{th}$-shadow of $\overline{A}$. Given that $A$ and $B$ are disjoint, we could improve this to $B \subseteq V(G) - (S \cup A)$. This would suggest a stronger result might be possible. However, while we know for which choice of $A$ the order of $S$ is minimised (that is, when $\overline{A}$ is first), we don't know which choice of $A$ minimises $S \cup A$. If $\overline{A}$ is first and $|A| = \binom{n-1}{k-1}$ then $A$ contains all vertices using $n$, and $S$ contains all vertices not using $n$. But then $B = \emptyset$. However if instead we remove from $A$ a vertex $(1, \dots, k-1, n)$ and replace it with $(1, \dots, k)$, then $B$ is not forced to be empty---it could contain $(1, \dots, k-1, n)$. So the optimal choice of $A$ is not when $\overline{A}$ is first. Note that Pyber \cite{Pyber} argues that $A,B$ are optimal when $A$ is first, and so argues that when $|A| \geq \binom{n-1}{k-1}$, then $A$ contains all $k$-sets using $n$ and also that all $k$-sets in $B$ use $n$. This is a much stronger argument, but we are not able to replicate it as we do not know the optimal choice of $A$. We have attempted to generalise the shifting argument of Frankl in \cite{Frankl2}, but it does not appear to extend to this case. 

\subsection*{Acknowledgements}
Thanks to Alex Scott for helpful conversations, and for pointing out references \cite{almostisect,sperner,scott}.

\bibliographystyle{plain}
\bibliography{Kneserbib}

\end{document}

Kneser.bbl
\begin{thebibliography}{10}

\bibitem{Bodlaender-AC93}
Hans~L. Bodlaender.
\newblock A tourist guide through treewidth.
\newblock {\em Acta Cybernet.}, 11(1-2):1--21, 1993.

\bibitem{EKR}
Paul Erd{\H{o}}s, Chao Ko, and Richard Rado.
\newblock Intersection theorems for systems of finite sets.
\newblock {\em Quart. J. Math. Oxford Ser. (2)}, 12:313--320, 1961.

\bibitem{Frankl2}
P\'eter Frankl.
\newblock A new short proof for the {K}ruskal-{K}atona theorem.
\newblock {\em Discrete Math.}, 48(2-3):327--329, 1984.

\bibitem{sperner}
D\'aniel Gerbner, Nathan Lemons, Cory Palmer, D\"om\"ot\"or P\'al\"olgyi,
  Bal\'azs Patk\'os, and Vajk Sz\'ecsi.
\newblock Almost cross-intersecting and almost cross-sperner pairs of families
  of sets.
\newblock {\em Graphs and Combinatorics}, 29:489--498, 2013.

\bibitem{almostisect}
D\'aniel Gerbner, Nathan Lemons, Cory Palmer, Bal\'azs Patk\'os, and Vajk
  Sz\'ecsi.
\newblock Almost intersecting families of sets.
\newblock {\em SIAM. Discrete Mathematics}, 26(4):1657--1669, 2012.

\bibitem{Halin76}
Rudolf Halin.
\newblock {$S$}-functions for graphs.
\newblock {\em J. Geometry}, 8(1-2):171--186, 1976.

\bibitem{EKRSimple}
Gyula O.~H. Katona.
\newblock A simple proof of the {E}rd{\H o}s-{C}hao {K}o-{R}ado theorem.
\newblock {\em J. Combin. Theory Ser. B}, 13:183--184, 1972.

\bibitem{Katona}
Gyula~O.H. Katona.
\newblock A theorem of finite sets.
\newblock In {\em Theory of graphs ({P}roc. {C}olloq., {T}ihany, 1966)}, pages
  187--207. Academic Press, New York, 1968.

\bibitem{kneser}
Martin Kneser.
\newblock Aufgabe 360.
\newblock {\em Jahresbericht der Deutschen Mathematiker-Vereinigung, 2.
  Abteilung}, 58:27, 1955.

\bibitem{Kruskal}
Joseph~B. Kruskal.
\newblock The number of simplices in a complex.
\newblock In {\em Mathematical optimization techniques}, pages 251--278. Univ.
  of California Press, Berkeley, Calif., 1963.

\bibitem{lazlo}
L{\'a}szl{\'o} Lov{\'a}sz.
\newblock Kneser's conjecture, chromatic number, and homotopy.
\newblock {\em J. Combin. Theory Ser. A}, 25(3):319--324, 1978.

\bibitem{peterstree}
Lambertus Marchal.
\newblock {\em Treewidth}.
\newblock PhD thesis, Maastricht University, 2012.

\bibitem{MatsuToku}
Makoto Matsumoto and Norihide Tokushige.
\newblock The exact bound in the {E}rd{\H o}s-{K}o-{R}ado theorem for
  cross-intersecting families.
\newblock {\em J. Combin. Theory Ser. A}, 52(1):90--97, 1989.

\bibitem{Pyber}
L\'aszl\'o Pyber.
\newblock A new generalization of the {E}rd{\H o}s-{K}o-{R}ado theorem.
\newblock {\em J. Combin. Theory Ser. A}, 43(1):85--90, 1986.

\bibitem{GMall}
Neil Robertson and Paul~D. Seymour.
\newblock Graph minors {I--XXIII}.
\newblock {\em J. Combin. Theory Ser. B}, 1983--2012.

\bibitem{GMII}
Neil Robertson and Paul~D. Seymour.
\newblock Graph minors. {II}. {A}lgorithmic aspects of tree-width.
\newblock {\em J. Algorithms}, 7(3):309--322, 1986.

\bibitem{fgt}
Edward~R. Scheinerman and Daniel~H. Ullman.
\newblock {\em Fractional graph theory}.
\newblock Wiley, 1997.

\bibitem{scott}
Alex Scott and Elizabeth Wilmer.
\newblock Hypergraphs of bounded disjointness.
\newblock http://people.maths.ox.ac.uk/scott/Papers/boundeddisjointness.pdf.

\bibitem{Ziegler}
G\"{u}nter~M. Ziegler.
\newblock Generalized {K}neser coloring theorems with combinatorial proofs.
\newblock {\em Inventiones Math}, 147:671--691, 2001.

\end{thebibliography}
