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)$?


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.

  • $\begingroup$ How do I even know that the maximum clique cardinality exists when it doesn't in $\sum K_n$? $\endgroup$ – SK19 Jun 11 at 9:48
  • $\begingroup$ @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? $\endgroup$ – bof Jun 11 at 14:45
  • $\begingroup$ @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$. $\endgroup$ – bof Jun 11 at 14:53
  • $\begingroup$ @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$. $\endgroup$ – bof Jun 11 at 15:00

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.