3
$\begingroup$

If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ we have $$A\in E_1 \text{ if and only if } f(A) \in E_2.$$ We say that $H=(\omega, E)$ is a complete regular linear hypergraph on $\omega$ if

  1. $e_1\neq e_2\in E \implies |e_1\cap e_2| = 1$ and

  2. for all $n\in \omega$ we have $|\{e\in E: n \in e\}| = \aleph_0$.

Question. Assuming ${\sf ZFC}$, if $H_i = (\omega, E_i)$ are complete regular linear hypergraphs for $i = 1,2$, are $H_1$ and $H_2$ necessarily isomorphic?

$\endgroup$
4
  • 1
    $\begingroup$ Since we won't always know if there is a bijection between aleph nought and its square, I suspect the answer is very dependent on the underlying set theory. My guess is ZFC shows there is an isomorphism. Gerhard "See What Projective Geometry Says" Paseman, 2020.06.03. $\endgroup$ Commented Jun 3, 2020 at 17:50
  • $\begingroup$ Thanks for your comment @GerhardPaseman - my framework for this question is ZFC, but I forgot to add this to the question - will do! $\endgroup$ Commented Jun 3, 2020 at 17:56
  • $\begingroup$ In the absence of set-theoretic specification I guess ZFC is assumed. $\endgroup$
    – YCor
    Commented Jun 3, 2020 at 18:08
  • $\begingroup$ Since the underlying set is well ordered, this induces a well ordering on the edge set. However, choice may still be needed to establish an isomorphism. If both edge sets are recursively computable, then it may be possible to construct a recursive isomorphism without choice. However this assumes a lot. Gerhard "Not Sure Which To Choose" Paseman, 2020.06.03. $\endgroup$ Commented Jun 3, 2020 at 19:31

2 Answers 2

4
$\begingroup$

If $K$ is a field of cardinality $\aleph_0$, then the points and lines of the projective plane over $F$ constitute a complete regular linear hypergraph. The field $K$ can be recovered (up to isomorphism) from the hypergraph, so this produces lots of non-isomorphic such hypergraphs.

$\endgroup$
3
$\begingroup$

No. Given a hypergraph $H$, the $2$-shadow of $H$ is the $2$-uniform graph where we take each pair which is contained in an edge of $H$. This is isomorphism invariant.

Now consider the following graph on $\mathbb{Q}^2\cup (\mathbb{Q}\cup\{\infty\})$, where we think of $\mathbb{Q}\cup\infty$ as a slope. For each line in $\mathbb{Q}^2$, we draw an edge containing the points of the line and its slope; this is $H_1$. This is a complete regular linear hypergraph: obviously there are infinitely many lines through any given point, or of any given slope, and any two lines either have the same slope and no points in common, or otherwise different slopes and one point in common. The 2-shadow of this is a complete graph with all the edges between different slopes removed. In other words, it has one maximal independent set and every other pair is an edge.

Now we draw another graph $H_2$, whose vertices will be all rational lines in $\mathbb{Q}^3$ together with all rational normals in $\mathbb{Q}^3$. For each plane in $\mathbb{Q}^3$, we put an edge containing all the lines in that plane, together with the normal to the plane. Again, this is a complete regular linear hypergraph; for any line or normal, there are infinitely many planes through the line or with the normal, but any two planes either have the same normal and no line in common, or different normals and exactly one line in common.

But the 2-shadow of $H_2$ is more complicated than that of $H_1$. The set of normals is still an independent set, and it is a maximal independent set, because any line is contained in a plane which has a normal. But there are pairs of lines which are not in any plane (skew ones), so there are non-edges outside this maximal independent set.

$\endgroup$
0

You must log in to answer this question.

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