For any cardinal $\kappa$, let $[\kappa]^{<\kappa}$ denote the collection of subsets of $\kappa$ with cardinality $<\kappa$. Is there an infinite cardinal $\kappa$ and ${\cal C}\subseteq [\kappa]^{<\kappa}$ with the following properties?

  1. $c \neq d \in {\cal C} \implies |c\cap d|= 1$,
  2. For all $\alpha\in \kappa$ we have $|\{c\in {\cal C}: \alpha\in c\}|>1$.
  • 2
    $\begingroup$ Take a complete graph on $\kappa$, for any $\kappa>2$. $\endgroup$ – Wojowu Jun 2 '20 at 8:35
  • $\begingroup$ @bof Oh how silly of me, I misread that as an inequality $\leq 1$. $\endgroup$ – Wojowu Jun 2 '20 at 11:05

There is no such $\kappa$. Consider an infinite cardinal $\kappa$ and assume for a contradiction that $\mathcal C$ has the stated properties. For $\alpha\in\kappa$ let $\mathcal C(\alpha)=\{c\in\mathcal C: \alpha\in c\}$.

Claim 1. $|\mathcal C|\ge\kappa$.

Proof. The map $\{c,d\}\mapsto c\cap d$ is a surjection from $\binom{\mathcal C}2$ to $\binom\kappa1$.

Claim 2. $\alpha\in\kappa\implies\mathcal C(\alpha)\ne\mathcal C$,

Proof. Choose $c\in\mathcal C(\alpha)$, $c\ne\{\alpha\}$, choose $\beta\in c\setminus\{\alpha\}$, and choose $d\in\mathcal C(\beta)\setminus\{c\}$; then $d\in\mathcal C\setminus\mathcal C(\alpha)$.

Claim 3. $\alpha\in\kappa,\ d\in\mathcal C\setminus\mathcal C(\alpha)\implies|\mathcal C(\alpha)|\le|d|\lt\kappa$.

Proof. The map $c\mapsto c\cap d$ is an injection from $\mathcal C(\alpha)$ to $\binom d1$.

Now choose $c\in\mathcal C$, $\alpha\in c$, and $d\in\mathcal C(\alpha)\setminus\{c\}$. Let $\lambda=\max(|d|,|\mathcal C(\alpha)|)\lt\kappa$. Since $|\mathcal C(\beta)|\le|d|$ for all $\beta\in c\setminus\{\alpha\}$, and since $\mathcal C=\bigcup_{\beta\in c}\mathcal C(\beta)$, we have $|\mathcal C|\le|c|\cdot\lambda\lt\kappa$, contradicting Claim 1.


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.