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?

  • $\begingroup$ 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. $\endgroup$ Mar 17 '15 at 3:22
  • $\begingroup$ @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$. $\endgroup$
    – 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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.