1
$\begingroup$

Let $\lambda$ be an infinite cardinal. For each $\nu<\lambda$, let $(E_\xi^\nu:\xi<\lambda^+)$ be a family of pairwise disjoint sets each of cardinality at most $\lambda$.

Assume that for every set $T$ of cardinality at most $\lambda$ and for any $\nu<\lambda$, $|\{\xi<\lambda^+:E_\xi^\nu\cap T\ne\emptyset\}|\le\lambda$.

Prove that there are ordinals $\xi(\nu,\eta)<\lambda^+$ ($\nu<\lambda$, $\eta<\lambda^+$) such that the sets $(E_{\xi(\nu,\eta)}^\nu:\nu<\lambda\text{, }\eta<\lambda^+)$ are pairwise disjoint.

This seems to be gist of (and is almost copied from) the top of page 312 of Hajnal, A., "Embedding finite graphs into graphs colored with infinitely many colors," Israel J. Math. 73 (1991), no. 3, 309–319. https://www.researchgate.net/publication/225726350_Embedding_finite_graphs_into_graphs_colored_with_infinitely_many_colors

$\endgroup$
2
  • $\begingroup$ That is not quite the gist. It states that the assumption on sets of cardinality $\lambda$ is not an assumption but a fact: since the $E^\nu_\xi$ are pairwise disjoint $\xi\mapsto \min(E^\nu_\xi\cap T)$ is an injection into $T$, where $\xi$ runs through the indices corresponding to a nonempty intersection. And second: Hajnal indicates how to prove this, by induction. $\endgroup$
    – KP Hart
    Commented Jul 3 at 11:03
  • $\begingroup$ @KPHart I still think I captured the "gist." Since it was a fact, I threw it in as a fact one could use. Hajnal's indication of how to prove the main result I want was completely unhelpful to me. $\endgroup$
    – Tri
    Commented Jul 3 at 13:48

1 Answer 1

3
$\begingroup$

Consider the reverse lexicographic order $\prec$ on $\lambda\times\lambda^+$ ($(\alpha,\beta)\prec(\gamma,\delta)$ iff $\beta<\delta$ or $\beta=\delta$ and $\alpha<\gamma$); its order type is equal to $\lambda^+$.

Choose the ordinals $\xi(\nu,\eta)$ by recursion with respect to this well-order. We can take $\xi(0,0)=0$, because there are no demands yet. Assume $\xi(\alpha,\beta)$ is found for $(\alpha,\beta)\prec(\nu,\eta)$. Let $T=\bigcup\{E^\alpha_{\xi(\alpha,\beta)}:(\alpha,\beta)\prec(\nu,\eta)\}$. Then $|T|\le\lambda$ and by the assumption/fact above $\{\xi:E^\nu_\xi\cap T=\emptyset\}$ has cardinality $\lambda^+$. Let $\xi(\nu,\eta)$ be the minimum of that set. In this way we guarantee that $E^\alpha_{\xi(\alpha,\beta)}\cap E^\nu_{\xi(\nu,\eta)}=\emptyset$ whenever $(\alpha,\beta)\prec(\nu,\eta)$.

$\endgroup$
1
  • $\begingroup$ KP Hart, thank you for the answer! @KP Hart $\endgroup$
    – Tri
    Commented Jul 4 at 5:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .