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?

  • $\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 May 15 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 May 15 at 17:52
  • 1
    $\begingroup$ No, there's an affine plane on 9 points with 12 lines, and every line has length 3. $\endgroup$ – Bullet51 May 16 at 2:51
  • $\begingroup$ Thanks - can you post this as an answer such that we can close this thread? $\endgroup$ – Dominic van der Zypen May 16 at 7:34

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


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.