# Are two “perfectly dense” hypergraphs on $\mathbb{N}$ necessarily isomorphic?

We say that a hypergraph $$(\mathbb{N}, E)$$ where $$E\subseteq {\cal P}(\mathbb N)$$ is perfectly dense if

1. $$\mathbb{N}\notin E$$,
2. all $$e\in E$$ are infinite,
3. $$e_1, e_2 \in E$$ implies $$|e_1\cap e_2| = 1$$, and
4. for all $$m\neq n\in \mathbb{N}$$ there is $$e\in E$$ such that $$\{m,n\}\subseteq e$$.

If $$(\mathbb{N}, E_i)$$ are perfectly dense for $$i=1,2$$, are these hypergraphs necessarily isomorphic? If not, how large can a collection of perfectly dense, pairwise non-isomorphic hypergraphs be?

(Will also accept posts answering the first question only, but I am curious about the second, too.)

• Just to check: the hypergraph $(\mathbb{N}, \{\{\mathbb{N}\}\})$, consisting of one "edge" being the entire line, is "perfectly dense", right? – user44191 Mar 2 '19 at 9:30
• Yeah sorry - I don't want a mega-edge like that - will edit. Thanks! – Dominic van der Zypen Mar 2 '19 at 9:59
• Then these conditions are almost exactly those of a projective plane (en.wikipedia.org/wiki/Projective_plane ). – user44191 Mar 2 '19 at 11:19

There are continuum-many pairwise non-isomorphic perfectly dense hypergraphs. Below is a sketch of a proof.

Given a countably infinite field $$\mathbb{K}$$, the projective plane $$\mathbb{KP}_2$$ over $$\mathbb{K}$$ can be seen as a perfectly dense hypergraph, where vertices are points and edges are lines. I will show that from the hypergraph structure of $$\mathbb{KP}_2$$, it is possible to recover the field $$\mathbb{K}$$ up to isomorphism. Since there are $$2^{\aleph_0}$$ pairwise non-isomorphic countably infinite fields (take for instance $$\mathbb{K}=\mathbb{Q}\left(\{\sqrt{p} \mid p \in A\}\right)$$ for $$A$$ a subset of prime numbers), this will be enough to conclude.

So let $$\mathbb{K}$$ be a contably infinite field and $$P$$ be a projective plane over $$\mathbb{K}$$. I choose three arbitrary and pairwise distinct lines $$L_\infty$$ (the line at infinity), $$L_x$$ (the $$x$$-axis) and $$L_y$$ (the $$y$$-axis) in $$P$$. Let $$P'=P \setminus L_\infty$$, $$L'_x = L_x \cap P$$ and $$L'_y = L_y \cap P$$. Let $$0_P$$ be the intersection between $$L_x$$ and $$L_y$$, and choose arbitrarily $$1_x \in L'_x \setminus \{0_P\}$$ and $$1_y \in L'_y \setminus \{0_P\}$$. Since $$P'$$ is an affine plane, there exists a unique affine isomorphism $$\varphi \colon \mathbb{K}^2 \to P'$$ with $$\varphi(0, 0) = 0_P$$, $$\varphi(1, 0) = 1_x$$ and $$\varphi(0, 1) = 1_y$$. We can transfer the field structure of $$\mathbb{K}$$ to $$L'_x$$ by the bijection $$a \mapsto \varphi(a, 0)$$; we still denote by $$+$$ and $$\cdot$$ the field operations on $$L'_x$$. We show that these operations are actually definable only from $$L_x$$, $$L_y$$, $$L_\infty$$, $$1_x$$, $$1_y$$ and from the hypergraph structure of $$P$$; since $$L_x$$, $$L_y$$, $$L_\infty$$, $$1_x$$, $$1_y$$ have been chosen arbitrarily, it will be enough to conclude.

A few more notation. For $$A, B \in P$$, I will denote by $$(AB)$$ the line passing through $$A$$ and $$B$$. Say that two lines in $$P$$, distinct from $$L_\infty$$, are parallel if they are equal or are distinct and intersect on $$L_\infty$$, and that a line $$L$$ in $$P$$ is horizontal (resp. vertical) if it is distinct from $$L_\infty$$ and parallel to $$L_x$$ (resp. $$L_y$$). The notions of parallelism, horizontality and verticality are definable from $$L_x$$, $$L_y$$, $$L_\infty$$ and from the hypergraph structure on $$P$$.

Now let $$A, B \in L'_x$$; we show how to define $$A + B$$ and $$A\cdot B$$. Let $$A'$$ be the intersection of $$L_y$$ and of the parallel to $$(1_x1_y)$$ passing through $$A$$. Let $$C$$ be the intersection of the vertical line passing through $$B$$ and of the horizontal line passing through $$A'$$. Then $$A+B$$ is the intersection of $$L_x$$ and of the parallel to $$(1_x1_y)$$ passing through $$C$$, and $$A \cdot B$$ is the intersection between $$L_x$$ and the parallel to $$(1_yB)$$ passing through $$A'$$.

P.S.: I would be curious to see a simpler purely combinatorial proof; I am sure such a proof should exist.

• Very nice, thanks for this proof sketch! I would never have thought that a "detour" to countably infinite fields was needed. – Dominic van der Zypen Mar 2 '19 at 14:15
• @DominicvanderZypen I don't think it is needed! I think (and I hope) that there is a more direct proof! – N. de Rancourt Mar 2 '19 at 14:32
• It may also be useful to note that there are many more planes than this - these are the Pappian planes. – user44191 Mar 2 '19 at 22:04