Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Modification of Lemma 0 in Hajnal's Paperpaper "Embedding Finite Graphsfinite graphs into Graphs Coloredgraphs colored with Infinitely Many Colors"infinitely many colors"

Source Link
Tri
  • 1.6k
  • 10
  • 8

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