Skip to main content
Focused the proposed answer more on the more important aspect of the OP's question: the unrestrictedness of the hypergraphs (instead of emphasising the OP's definition of isomorphism)
Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Joel's answer is spot on, and makes full use of your very demanding definition of an isomorphism ofnot requiring any further properties that your hypergraphs (there are other notions which require the bijection between the ground sets to respect less)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

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.

Joel's answer is spot on, and makes full use of your very demanding definition of an isomorphism of hypergraphs (there are other notions which require the bijection between the ground sets to respect less), but it might perhaps be nice to know that also with both

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

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.

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

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.

Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Joel's answer is spot on, and makes full use of your very demanding definition of an isomorphism of hypergraphs (there are other notions which require the bijection between the ground sets to respect less), but it might perhaps be nice to know that also with both

  • less demands on the isomorphism
  • more demands on each 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.