1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Sorry... condition 3 was wrong. $\endgroup$ Commented Dec 3, 2016 at 17:43

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Dec 3, 2016 at 17:56

You must log in to answer this question.

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