A saturated linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. $|e|\geq 2$ for all $e\in E$,
  2. $|e_1\cap e_2| = 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$, and
  3. $|\{e\in E:v\in e\}| = 2.$

Let $E$ be the set of $n\in\mathbb{N}$ such that it is impossible to have a saturated linear hypergraph on $\{1,\ldots, n\}$. (For instance, $4\in E$.) Is $E$ infinite?

  • $\begingroup$ Sorry... condition 3 was wrong. $\endgroup$ – Dominic van der Zypen Dec 3 '16 at 17:43

This is similar to an answer I gave before.

For each point $v$, let $L_v$ denote the edges containing $v$. Then we know that each set $L_v$ has cardinality 2, and they're distinct.

Moreover, if the edges are $e_1, e_2, \ldots , e_m$, then since every pair of edges intersect, we'll need that the sets $L_v$ are in bijection with the two-element subsets of $m$.

Thus, a configuration as you desire exists iff $n$ is of the form ${m \choose 2}$ (and $m \geq 3$ so that each edge will have at least 2 points).

So yes, the set $E$ is infinite, and it's equal to $\{1\}$ union the set of integers that aren't triangle numbers.

  • $\begingroup$ To see why such configurations exist with that many points and edges, see the constructions in my previous answer on your similar questions. $\endgroup$ – Pat Devlin Dec 3 '16 at 17:56

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.