# Complete bipartite subgraph in Kneser graph

The Kneser graph $KG_{n,k}$ is the graph whose vertices correspond to the $k$-element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. What is the maximum number of vertices in a complete bipartite subgraph of $KG_{n,k}$?

In a complete bipartite subgraph, we need two sets $X,Y$ of vertices such that all pairs of subsets corresponding to vertices in each side are not disjoint, while any vertex in $X$ and any vertex in $Y$ are disjoint. Supposing that $n$ is even, we can divide the set of $n$ elements into two subsets $A,B$ of $n/2$ elements. Choose as $X$ all vertices corresponding to $k$-element subsets of $A$ that contain a fixed element $a\in A$, and similarly for $B$. This yields $2\cdot\dbinom{n/2-1}{k-1}$ vertices in $A\cup B$.

Is this the best possible?

• Let $V$ be the ground set, and fix a set $C$ of $k$ elements. Let $x \notin C$, and let $X$ be all the $k$ subsets of $V \setminus C$ that contain $x$. The bipartition $\{X, \{C\}\}$ has ${{n - k - 1} \choose {k - 1}} + 1$ vertices, which is greater than your result when $k < n/2$ and large enough $n$ (though your result is greater for small values of $n$, thanks wolfram). I think this can still be improved though. – Manuel Lafond Mar 17 '15 at 3:22
• @ManuelLafond, I agree. Your method (very non-balanced complete bipartite graph, i.e. $K_{m, 1}$) has much better asymptotic rate. For fixed $k$ python55's solution is asymptotic to $(n/2)^{k-1}$, whereas your solution is asymptotic to $(n-k)^{k-1}$ and $n-k$ is (eventually) much bigger than $n/2$. – TravisJ Mar 20 '15 at 13:17

Suppose that the sets $X$ correspond to one of the vertex partitions of your complete bipartite graph and that the sets in $Y$ correspond to the other. The following must be true: $X$ is an intersecting family (every $x_{i}\in X, x_{j}\in X$ satisfy $x_{i}\cap x_{j}\neq \emptyset$ so that vertices in $X$ are not adjacent. Similarly, in $Y$. It also needs to be the case that for every $x\in X$ and every $y\in Y$ that $x\cap y=\emptyset$ so that there is an edge from $x$ to $y$.

Let $A=\bigcup_{x\in X} x$ and $B=\bigcup_{y\in Y} y$. Note that $A$ and $B$ are disjoint (otherwise there is an $x\in X$ and a $y\in Y$ with $x\cap y\neq \emptyset$). This fact justifies initially partitioning your base elements into two disjoint sets. Let $a=|A|$ and $b=|B|$ noting that $a+b=n$.

Note that the set $X$ is an intersecting family of $k$-sets, coming from a base set with $a$ elements. The Erdos-Ko-Rado theorem (http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem) says that the most $k$-sets that can be contained in $X$ is: $\binom{a-1}{k-1}$. This implies that

$$|X| \leq \binom{a-1}{k-1} \text{ and } |Y|\leq \binom{b-1}{k-1}.$$

Thus, the largest complete bipartite graph you could have is:

$$\max \binom{a-1}{k-1} + \binom{n-a-1}{k-1}.$$

We must assume that both $a$ and $b$ are at least $k$--assuming that we expect the complete bipartite graph to contain an edge--then optimize the partition. Some quick experimentation with python code shows that this is optimized when $a=k$ (or $b=k$ by symmetry). Thus, the most vertices you could have in a complete bipartite subgraph of the Kneser graph is:

$$\binom{n-k-1}{k-1}+1.$$

The way this can be achieved is by setting aside a single $k$-element subset (for one partition, that half of the complete bipartite graph has a single vertex), and taking all $k$-subsets that intersect a single (preselected) element on the other side.