# Modification of Lemma 0 in Hajnal's paper "Embedding finite graphs into graphs colored with infinitely many colors"

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

https://math.stackexchange.com/questions/4940024/lemma-0-in-hajnals-paper-embedding-finite-graphs-into-graphs-colored-with-infi

Bonus question. Is there such a graph without a $$K_4$$?

This can be done by modifying the basic inductive construction of the Rado graph. The general idea is to enumerate all of the potential $$\epsilon$$ functions, and add $$\kappa$$ new vertices realizing each of them. Then iterate this process $$\lambda^+$$ many times to "catch your tail".

Here are more details. Given a graph $$M=(V,E)$$ on a vertex set of size at most $$\kappa$$ we construct a new graph $$M^*$$ as follows. The vertex set of $$M^*$$ consists of $$V$$ together with $$\kappa$$ many new vertices $$(w_{A,i})_{i<\kappa}$$ for every set $$A\subset V$$ of size at most $$\lambda$$. The edges of $$M^*$$ consist of $$E$$ together with mmthe edges $$E(v,w_{A,i})$$ for all $$v\in A$$ and $$i<\kappa$$. In other words, for each subset $$A$$ of $$V$$ with size at most $$\lambda$$, we add $$\kappa$$ many new vertices connected to every element of $$A$$ (and nothing else). The number of $$\lambda$$-element subsets of $$V$$ is at most $$\kappa$$ ($$\kappa^\lambda=\kappa$$ is used here). So $$M^*$$ has $$\kappa$$ vertices.

Now, let $$M_0$$ be any graph with at most $$\kappa$$ vertices (e.g. a single vertex), and iteratively construct $$M_i$$ for $$i<\lambda^+$$ by setting $$M_{i+1}=(M_i)^*$$, and taking unions when $$i$$ is a limit ordinal. Let $$M$$ be the union of all the $$M_i$$'s. Then $$M$$ has $$\kappa$$ many vertices, so we may assume the vertex set of $$M$$ is $$\kappa$$ itself. We verify that $$M$$ satisfies the main condition of Lemma 0. Fix $$\epsilon \in H$$ and let $$X$$ be its domain. So $$|X|\leq\lambda$$. Since $$\lambda^+$$ is regular, there must be some $$i<\lambda^+$$ such that $$X$$ is entirely contained in the vertex set of $$M_i$$. Let $$A=\{x\in X:\epsilon(x)=0\}$$. Then in $$M_{i+1}$$, the $$\kappa$$ many new vertices added for $$A$$ are all in $$G_\epsilon$$ (as computed in $$M$$).

For the second part of Lemma 0, first note that $$|H|=\kappa$$ ($$\kappa^\lambda=\kappa$$ is used again here). Now in general, given any collection $$(X_i)_{i<\kappa}$$ of subsets of $$\kappa$$, each of size $$\kappa$$, there is some collection $$(A_\alpha)_{\alpha<\kappa}$$ of pairwise disjoint subsets of $$\kappa$$ such that $$|A_\alpha\cap X_i|=\kappa$$ for all $$\alpha$$ and $$i$$. I imagine there is a slicker way to do this but, for example:

1. Let $$(X'_i)_{i<\kappa}$$ be a listing of $$(X_i)_{i<\kappa}$$ in which each $$X_i$$ appears $$\kappa$$ many times. For $$i<\kappa$$, inductively define $$x_i$$ to be some element of $$X'_i\backslash\{x_j:j. Now let $$Y_i=\{x_j:X'_j=X_i\}$$. Then the sequence $$(Y_i)_{i<\kappa}$$ is pairwise disjoint, and each $$Y_i$$ is a subset of $$X_i$$ of size $$\kappa$$.
2. For each $$i<\kappa$$, let $$(A_{\alpha,i})_{\alpha<\kappa}$$ be a partition of $$Y_i$$ into $$\kappa$$ many sets of size $$\kappa$$. Set $$A_\alpha=\bigcup_{i<\kappa} A_{\alpha,i}$$.

As far as the Bonus Question, any such graph must contain a complete subgraph on $$\lambda^+$$ vertices. Indeed, fix some $$\alpha<\lambda^+$$ and suppose we have vertices $$(v_i)_{i<\alpha}$$ forming a complete graph. Let $$\epsilon$$ have domain $$\{v_i:i<\alpha\}$$ and constant value $$0$$. Choose $$v_\alpha\in G_\epsilon$$; so $$\{v_i:i\leq\alpha\}$$ is a complete graph. By induction, this builds a complete subgraph graph on $$\lambda^+$$ vertices.

A construction that uses the equality $$\kappa^\lambda=\kappa$$ directly runs as follows. By that equality the set $$H$$ has cardinality $$\kappa$$, so we can find a surjection $$f:\kappa\to H$$ such that for every $$\varepsilon\in H$$ the set $$\{\alpha:f(\alpha)=\varepsilon\}$$ has cardinality $$\kappa$$, and $$\operatorname{dom}\varepsilon\subseteq \alpha$$ whenever $$f(\alpha)=\varepsilon$$. Note that the cofinality of $$\kappa=2^\lambda$$ is larger than $$\lambda$$, hence the domains of the members of $$H$$ are bounded in $$\kappa$$.

Now let $$G=\bigl\{\{\beta,\alpha\}:\beta\in\operatorname{dom}f(\alpha)$$ and $$f(\alpha)(\beta)=0\bigr\}$$. Then for every $$\varepsilon\in H$$ the set $$G_\varepsilon$$ contains $$\{\alpha:f(\alpha)=\varepsilon\}$$, so it has cardinality $$\kappa$$.