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

Question

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

Answer 1

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<i\}$. 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.

Answer 2

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$.