4
$\begingroup$

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.)

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

1 Answer 1

3
$\begingroup$

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.

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

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.