# $KG(\mathfrak a_1,\mathfrak b_1)\cong KG(\mathfrak a_2,\mathfrak b_2)$ with $(\mathfrak a_1,\mathfrak b_1)\neq(\mathfrak a_2,\mathfrak b_2)$

Let $$\mathfrak a,\mathfrak b$$ be cardinals (a cardinal being identified with the smallest ordinal of that cardinality), $$\mathfrak b\subseteq\mathfrak a$$. The Kneser graph $$KG(\mathfrak a,\mathfrak b)$$ is the simple graph with vertex set $$V(KG(\mathfrak a,\mathfrak b))=\binom{\mathfrak a}{\mathfrak b}:=\{X\subseteq \mathfrak{a}:|X|=\mathfrak b\}$$ and $$XY\in E(KG(\mathfrak a,\mathfrak b))$$ iff $$X\cap Y=\emptyset$$.

Do there exist cardinal pairs $$(\mathfrak a_1,\mathfrak b_1)\neq(\mathfrak a_2,\mathfrak b_2)$$ with $$\mathfrak a_1,\mathfrak a_2$$ infinite and $$\mathfrak b_1,\mathfrak b_2\neq 0$$ such that $$KG(\mathfrak a_1,\mathfrak b_1)$$ and $$KG(\mathfrak a_2,\mathfrak b_2)$$ are isomorphic, in short $$KG(\mathfrak a_1,\mathfrak b_1)\cong KG(\mathfrak a_2,\mathfrak b_2)$$?

## 1 Answer

No. If $$G=KG(\mathfrak a,\mathfrak b)$$, where $$\mathfrak a$$ is infinite and $$0\lt\mathfrak b\le\mathfrak a$$, then $$\mathfrak a$$ and $$\mathfrak b$$ are determined by the structure of the graph $$G$$.

$$\mathfrak a$$ is the maximum cardinality of a clique (set of pairwise adjacent vertices) in $$G$$.

$$\mathfrak b=1$$ if and only if $$G$$ is a complete graph. If $$\mathfrak b\gt1$$, then $$\mathfrak b$$ is the maximum cardinality of a clique in $$G$$ for which there is a vertex of $$G$$ which is adjacent to no element of the clique.

• How do I even know that the maximum clique cardinality exists when it doesn't in $\sum K_n$? – SK19 Jun 11 at 9:48
• @SK19 In the graph $KG(\mathfrak a,\mathfrak b)$ the maximum clique cardinality exists and is equal to $\mathfrak a$ because (1) tvhere is a clique of cardinality $\mathfrak a$, and (2) every clique has cardinality $\le\mathfrak a$. Do you need a proof of !1) or (2) or both? – bof Jun 11 at 14:45
• @SK19 Anent (1), the fact that $KG(\mathfrak a,\mathfrak b)$ has a clique of cardinality $\mathfrak a$, i.e., that a set of cardinality $\mathfrak a$ contains a collection of $\mathfrak a$ pairwise disjoint subsets of cardinality $\mathfrak b$, follows from the fact that $\mathfrak a\mathfrak b=\mathfrak a$. – bof Jun 11 at 14:53
• @SK19 On the other hand, let $\mathcal X$ be any clique in $KG(\mathfrak a,\mathfrak b)$. Let $f$ be a choice function on $\mathcal X$, i.e., $f(X)\in X$ for each $X\in\mathcal X$. Then $f:\mathcal X\to\mathfrak a$ is an injection, whence $|\mathcal X|\le\mathfrak a$. – bof Jun 11 at 15:00