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
    Commented Mar 2, 2019 at 9:30
  • $\begingroup$ Yeah sorry - I don't want a mega-edge like that - will edit. Thanks! $\endgroup$ Commented 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
    Commented 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$ Commented 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$ Commented 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
    Commented Mar 2, 2019 at 22:04

You must log in to answer this question.

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