1
$\begingroup$

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

  1. for $e\in E$ we have $|e|\geq 2$, and
  2. if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.

An injective edge choice function of a linear hypergraph is an injective map $f:E\to V$ such that:

for all $e\in E$ we have $f(e)\in e$.

Obviously, if $|E|>|V|$ there cannot be such a function.

Question. If $H=(V,E)$ is a linear hypergraph with $V$ finite and $|e|\geq 3$ for all $e\in E$, does $H$ necessarily have an injective edge choice function?

Improve this question
$\endgroup$
4
  • $\begingroup$ Maybe I misread something, but does 2. hold if $e\cap e_1=\emptyset$ anyway? So the question is if $H$ has a set of distinct representatives.Surely it does not, if $|E|>|V|$. $\endgroup$
    – Péter Komjáth
    Commented May 15, 2019 at 15:26
  • $\begingroup$ You are right @PéterKomjáth! I should formulate this in a more elegant way. - An interesting subquestion is whether $|e|>2$ for all $e\in E$ implies $|E|\leq |V|$? $\endgroup$
    – Dominic van der Zypen
    Commented May 15, 2019 at 17:52
  • 1
    $\begingroup$ No, there's an affine plane on 9 points with 12 lines, and every line has length 3. $\endgroup$
    – LeechLattice
    Commented May 16, 2019 at 2:51
  • $\begingroup$ Thanks - can you post this as an answer such that we can close this thread? $\endgroup$
    – Dominic van der Zypen
    Commented May 16, 2019 at 7:34

1 Answer 1

Reset to default
1
$\begingroup$

Even $|E|\leq|V|$ does not hold: An affine plane contains more lines than points.

Improve this answer
$\endgroup$

You must log in to answer this question.

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