2
$\begingroup$

I am looking for a proof of the following lemma. Let $E_0$ be the set of edges of an undirected graph with no loops with vertex set a cardinal $\kappa$. Let $E_1$ be the family of two-element subsets of $\kappa$ that are not edges.

For $i\in\{0,1\}$ and $x<\kappa$ let $G_i(x)=\{y<\kappa\mid \{x,y\}\in E_i\}$.

For $\lambda\ge\aleph_0$, let $H=\big\{\epsilon\mid \epsilon \text{ is a set of ordered pairs }\text{and } |\epsilon|\le\lambda\text{ and }\epsilon\text{ is a function from a subset of $\kappa$ into }\{0,1\}\big\}$.

For $\epsilon\in H$, let $G_\epsilon=\{y<\kappa\mid\text{ for all $x$ in the domain of }\epsilon \text{, }y\in G_{\epsilon(x)}(x)\}$.

Assuming $\kappa=2^\lambda$, show that there is a graph on the vertex set $\kappa$ such that, for all $\epsilon\in H$, $|G_\epsilon|=\kappa$.

Show that for any such graph, there are pairwise disjoint sets $A_\alpha$ ($\alpha<\kappa$) such that $|G_\epsilon\cap A_\alpha|=\kappa$ for $\alpha<\kappa$ and $\epsilon\in H$.

The only proof Hajnal gives is the statement $\kappa^\lambda=\kappa$.

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$

0

You must log in to answer this question.

Browse other questions tagged .