For any set $X$, let $[X]^2 = \big\{\{a,b\}: a, b\in X \land a\neq b\big\}$. Let $\kappa$ be an infinite cardinal. Is there a set ${\cal E} \subseteq {\cal P}([\kappa]^2)$ such that

  1. for all $E \in {\cal E}$ the simple undirected graph $(\kappa,E)$ is connected,
  2. if $E_1\neq E_2\in {\cal E}$ then the graphs $(\kappa,E_1)$ and $(\kappa, E_2)$ are non-isomorphic, and
  3. $|{\cal E}| = 2^\kappa$


  • $\begingroup$ $(\kappa,E)$ may be any connected graph or it is related with $\kappa$ or $E$? Without these restrictions the question looks trivial, because we can pick any family of of size $2^\kappa$ consisting of mutually non-isomorphic graphs. $\endgroup$ – Alex Ravsky Sep 13 '17 at 8:12
  • 1
    $\begingroup$ Usually you write down a simple undirected graph as $G = (V,E)$ where $V$ is the set of vertices, and $E$ is the set of edges. In my question we have $V = \kappa$, and $E$ as described. $\endgroup$ – Dominic van der Zypen Sep 13 '17 at 8:15
  • $\begingroup$ I have to work now but I can propose a following family of $2^\kappa$ guessed mutually non-isomorphic graphs whose vertex set is an ordinal $\kappa+\kappa+1$. For each subset $A$ of $\kappa$ let $G_A$ has edges $(\lambda,\kappa+\mu)$ for each $\mu\le\lambda<\kappa$ and $(a,\kappa+\kappa)$ for each $a\in A$. $\endgroup$ – Alex Ravsky Sep 13 '17 at 8:31

Under the axiom of choice, the answer is yes. Interpret $\kappa$ as its initial ordinal. We take the vertex to consist of distinct vertices $A_\alpha,B_\alpha,C_\alpha,D_\alpha$ for each $\alpha<\kappa$. In each of the graphs, $B_\alpha$ is connected to $A_\alpha$ and $C_\alpha$ and possibly to $D_\alpha$, so that $B_\alpha$ always hes degree $2$ or $3$. $D_\alpha$ will only be connected to $B_\alpha$ if anything, so will have degree $0$ or $1$. We connect $A_\alpha$ to $C_\beta$ for $\alpha<\beta$. For any $S\subseteq\kappa$ let $G_S$ be the graph in which an edge between $B_\alpha$ and $D_\alpha$ is present iff $\alpha\in S$.

If I'm not mistaken, then we can show by transfinite induction of $\alpha$ that in any isomorphism between $G_S,G_{S'}$, $A_\alpha$ goes to $A_\alpha$, $B_\alpha$ to $B_\alpha$ and $C_\alpha$. But since $B_\alpha$ has degree $3$ in $G_S$ iff $\alpha\in S$, it follows that this can truly be an isomorphism only if $S=S'$.


Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$, the star $K_{1,3}$ has an asymmetric subdivision with $n$ vertices.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

  • $\begingroup$ Lovely -- thanks for this addition! $\endgroup$ – Dominic van der Zypen Apr 21 '20 at 13:23
  • $\begingroup$ Thanks for your effort to look this up @bof. I always enjoy reading your answers tremendously! $\endgroup$ – Dominic van der Zypen Apr 22 '20 at 5:00
  • $\begingroup$ "Presumably".${}$ $\endgroup$ – Andrés E. Caicedo Apr 22 '20 at 19:49

The general fact is that every mathematical structure of size $\kappa$, in a language of size at most $\kappa$, can be coded as a (connected, undirected, simple) graph of size $\kappa$. What I mean is that this coding process respects isomorphism, so that structure $M$ is isomorphic to $M'$ if and only if the corresponding graph encodings are isomorphic as graphs. It follows that since there are $2^\kappa$ many non-isomorphic structures (e.g. partial orders, groups, subsets of $\langle\kappa,<\rangle$, or what have you), there must also be $2^\kappa$ many non-isomorphic graphs.

In this way, the isomorphism problem of $\mathcal{L}$-structures of size $\kappa$ reduces to the graph isomorphism problem, and this is a sense in which graph-isomorphism is complete. For example, since for countable structures such as countable groups or partial orders, the graph-encoding process is Borel, it follows that the isomorphism relation for countable groups or basically for any kind of countable structures is Borel reducible to the graph isomorphism relation on countable graphs, in the sense of Borel equivalence relation theory.

There are many accounts of the graph encoding, and it is a good exercise to construct your own. But to say a little more about it, suppose we have a structure $\langle\kappa,\ldots\rangle$ with domain $\kappa$. We first aim to reduce to directed graphs. We may think of the relations and functions of the structures in terms of their graphs, and thereby reduce to coding subsets of various $\kappa^n$. And we can encode the copies of these $\kappa^n$ and their projection functions, so that we can tell whether a node in the graph is representing an element of $\kappa$ or a pair or a triple and how they project and so on, and then we can also code any subset of these by adding a node that points directly at the satisfying instances, plus some extra rigid structure that uniquely determines the pointing node. Finally, we reduce from directed graphs to graphs. One way to do this is to replace each directed edge with an assemblage of undirected edges, in such a way that we can tell which are the endpoints and which way the original edge pointed.

When I teach my graduate logic course, we usually do this coding explicitly, and the particular encoding that I use results in connected simple graphs.

  • $\begingroup$ A wonderful summary of the universality of graphs, and a wonderful application of the robustness of infinite cardinalities under finitely-many modifications. I have two questions: (0) Does one have to assume that the structure on $\kappa$ which one is reducing to a graph on $\kappa$ has finitely many relations each of finite arity, or can one loosen one of these two finiteness-conditions? (I would guess that if $\kappa$ is uncountable, one can go to countably many relations of countable arity each, yet I am not sure about what could go wrong in the technical encoding work then.) $\endgroup$ – Peter Heinig Sep 13 '17 at 14:50
  • $\begingroup$ (1) Do you know whether in the literature one can find a discussion of whether the construction you gave can be made a functor $\mathsf{CategoryOfStructuresWithFinitelyManyRelationsOfFiniteArityOn}\kappa\mathsf{WithStructureHomomorphisms}$ $\to$ $\mathsf{CategoryOfUndirectedSimpleGraphsOn}\kappa\mathsf{WithGraphHomomorphisms}$? The isomorphism-preservation you mention is of course only a necessary condition for the possibility of such a functor. One would have to say precisely what to do with a given structure homomorphism, and prove the functoriality. Has this been written about? $\endgroup$ – Peter Heinig Sep 13 '17 at 14:53
  • $\begingroup$ In my reduction, I had said that the language could have size $\kappa$ (not just finitely many). So, $\kappa$ many functions and relations, and I had meant finite arity, since that is the usual concept of first-order structure. Using infinite arities could be possible with some cardinals, such as if $\kappa$ is a strong limit closed under those arities, but in the general case, this opens the door to the effects of cardinal arithmetic that I believe prevent the universal fact. $\endgroup$ – Joel David Hamkins Sep 13 '17 at 15:36
  • $\begingroup$ Regarding your second comment, I find the functorial perspective natural here, but I don't know any account written in that category theoretic language. For example, most of the Borel-reducibility work that I am familiar with is not undertaken with category-theoretic language. $\endgroup$ – Joel David Hamkins Sep 13 '17 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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