2
$\begingroup$

Let $H_i = (V_i, E_i)$ be hypergraphs for $i=1,2$. Then we say that $H_1\cong H_2$ if there is a bijection $\varphi:V_1\to V_2$ such that $A\in E_1$ implies $\varphi(A) \in E_2$ and $B\in E_2$ implies $\varphi^{-1}(B)\in E_1$.

Is there a collection $\cal C$of pairwise non-isomorphic hypergraphs on $\omega$ with $|{\cal C}| = 2^{2^{\aleph_0}}$?

$\endgroup$
2
  • $\begingroup$ Your definition of isomorphism seems too restrictive. A fuller definition should still give the required result but it'd be clearly harder (more advanced). $\endgroup$ Commented Apr 16, 2017 at 20:11
  • 1
    $\begingroup$ I find this to be a very natural concept of hypergraph isomorphism, indeed, the most natural, since it is respecting what I take to be exactly the relevant structure: the vertices and the edges and the membership of a vertex on an edge. $\endgroup$ Commented Apr 16, 2017 at 20:22

3 Answers 3

4
$\begingroup$

The answer is yes.

Consider the collection $\mathcal C$ of hypergraphs of the following form. They have underlying set $\omega$ as the vertices, the natural numbers. The finite edges in the hypergraph are all and only the sets of the form $\{0,1,\ldots,n\}$. And then the hypergraph can have any desired collection of infinite edge sets.

Since there are $2^{\aleph_0}$ many infinite subsets of $\omega$, it follows that there are $2^{2^{\aleph_0}}$ many members of $\mathcal C$. And I claim that they are all pairwise non-isomorphic. To see this, note first that $\{0\}$ is the only edge with one member, and so the isomorphism must fix $0$. Similarly, $\{0,1\}$ is the only edge with two members, and so the isomorphism must fix $1$. And so on. The finite edges force the isomorphism to fix every individual vertex, and so non-identical members of $\mathcal C$ will be non-isomorphic.

EDIT   Let $\ F:=\ \{\{1\ \ldots\ n\}: n\in\mathbb N\},\ $ and $\ D:=\{X\in 2^\mathbb N : |X|=|\mathbb N|\}. $ Then define: $$ C\ :=\ \{ F\cup G:\ G\subseteq D\} $$ The Dominic's isomorphisms are reduced to just one identity ismorphism per selected hypergraph, i.e. there are no non-trivial Domininc's isomorphisms between members of $\ C$.

$\endgroup$
4
  • $\begingroup$ ? -- The edges of ALL hypergraphs from the collection belotg to a countable family, namely $\ \{1\ldots n\} :n\in\mathbb N\}.\ $ Thus your collection has cardinality $2^\aleph_0,\ $ which smaller than required. Am I wrong? *** I am sure that I misinterpreted your answer. Perhaps your answer is more involved. ? $\endgroup$ Commented Apr 16, 2017 at 20:07
  • $\begingroup$ No, you've misunderstood @WłodzimierzHolsztyński. My hypergraphs allow, in addition to those finite edges, any collection of infinite edges. There are $2^{\aleph_0}$ many infinite edges, and so there are $2^{2^{\aleph_0}}$ many ways to form a hypergraph using them. $\endgroup$ Commented Apr 16, 2017 at 20:20
  • 1
    $\begingroup$ Thank you. Now I have your intended meaning, and by now it was not difficult to follow it. $\endgroup$ Commented Apr 16, 2017 at 20:34
  • 1
    $\begingroup$ @WłodzimierzHolsztyński Thanks for the edit, even though you haven't said it exactly as I would have. $\endgroup$ Commented Apr 17, 2017 at 1:33
7
$\begingroup$

Others have already answered, but I think the following counting argument is worth pointing out:

  • there are $2^{2^{\aleph_0}}$ hypergraphs on $\omega$ (since a hypergraph on $\omega$ is just a collection of nonempty subsets of $\omega$),

  • each isomorphism class contains at most $2^{\aleph_0}$ elements (since there are that many permutations of $\omega$),

so there must be $2^{2^{\aleph_0}}$ isomorphism classes.

$\endgroup$
2
  • $\begingroup$ Very nice. This argument shows that every collection of size $2^{2^{\aleph_0}}$ has a subcollection of that size consisting of pairwise non-isomorphic hypergraphs. $\endgroup$ Commented Apr 16, 2017 at 18:24
  • $\begingroup$ Great and natural argument! $\endgroup$ Commented Apr 18, 2017 at 5:36
4
$\begingroup$

Joel's answer is spot on, and makes full use of your not requiring any further properties that your hypergraphs should have, but it might perhaps be nice to know that also with both

  • less demands on the isomorphism
  • more demands on each of the hypergraphs

the number of isomorphism classes can still reach

$2^{2^{\aleph_0}}$

in natural situations.

For example, in

Infinite Matroids and Determinacy of Games

a proof is given that there exist

$2^{2^{\aleph_0}}$

pairwise non-isomorphic hypergraphs with the additional nice property that each of them is a tame infinite matroid (in the sense of Bruhn--Diestel--Kriesell--Pendavingh--Wollan) on the ground set $\omega$, and each moreover is free of certain minors.

In short, a matroid on an infinite set $E$ is an abstract simplicial complex on $E$ satisfying two additional properties,

an exchange-axiom (analogous to the classical exchange axiom for finite matroids)

and axiom (IM),

which stipulates the existence of maximal elements in certain infinite subposets of the lattice of subsets $(2^E,\subseteq)$, and which does not have an analogue in the theory of finite matroids. If $E$ is finite, (IM) is always satisfied, which is why this notion of infinite matroids extends the classical definition of matroids. The property of being tame means that there does not exist any circuit intersecting a cocircuit in infinitely many ground-set elements. Such matroids naturally arise in the theory of countable infinite graphs.

A natural further requirement would be to ask,

  • that the hypergraph be a an ultrafilter on $\omega$.

(Of course, then we do not ask that it be an abstract simplicial complex, since there being both a complex and a filter is impossible.)

Pospíšil proved a century ago or so that on $\omega$ there exist $2^{2^{\aleph_0}}$ ultrafilters, distinct as sets. (Using terminology of (hyper-)graph theory, this is labelled counting, and by itself does not answer your question.)

In his thesis, A. Blass, using a natural notion of isomorphism of ultrafilters, gave, en route to the main results of the thesis, a reason why w.r.t. to that notion each isomorphism class of ultrafilters on $\omega$ must have size at most $2^{\aleph_0}$. (I could give some details provided you are interested, and provided I find the time; but probably it will be better if Blass himself would do so.) Combined with Pospíšil's theorem it follows that there must be $2^{2^{\aleph_0}}$ isomorphism classes of ultrafilters on $\omega$ w.r.t. Blass' notion of isomorphism. If I am not mistaken (I did not write a proof), if two ultrafilters are isomorphic w.r.t. your notion of isomorphism of hypergraphs, then they are isomorphic w.r.t. Blass' notion; hence there are at least as many isomorphism classes w.r.t. your notion as w.r.t. his. Therefore his result also implies that there are $2^{2^{\aleph_0}}$ ultrafilters on $\omega$ which are pairwise non-isomorphic w.r.t. your notion.

Moreover, applying to an ultrafilter the endofunctor $F$ of $\textsf{Sets}$ which is defined by replacing each set in a set of sets by its complement w.r.t. the ground-set results in an abstract simplicial complex, and if two ultrafilters $\mathcal{D}_0$ and $\mathcal{D}_1$ are non-isomorphic w.r.t. your notion of isomorphism, then $F(\mathcal{D}_0)$ and $F(\mathcal{D}_1)$ are non-isomorphic again, so in that sense, Blass' argument yields $2^{2^{\aleph_0}}$ isomorphism classes of abstract simplicial complexes on $\omega$, too.

So apparently we have the following examples:

if any hypergraph on $\omega$ is allowed: Joel's construction

if each hypergraph is required to be an ultrafilter on $\omega$: Blass' arguments

if each hypergraph is required to be an abtract simplicial complex on $\omega$: Blass' arguments viewed through $F$

if each hypergraph is required to be an abtract simplicial complex which moreover is required to be a matroid in the sense of Bruhn--Diestel--Kriesell--Pendavingh--Wollan: the construction of Bowler and Carmesin in the article cited above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .