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


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


2 Answers 2


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.