Let $l\geq 3$ be an integer. Is there $n\in\mathbb{N}$ and a hypergraph $H=(\{1,\ldots,n\},E)$ with the following properties?

  1. for all $e\in E$ we have $|e| \geq l$
  2. $e_1\neq e_2 \in E \implies |e_1 \cap e_2|\leq 1 $
  3. every edge intersects at least $n$ other edges, that is, for every $e\in E$ we have $|\{d\in E: d\neq e \text{ and } d\cap e\neq \emptyset\}|\geq n.$

(It would also be nice to know what the smallest value for $n$ is, given any $l \geq 3$. Obviously $n\geq 2l -1$ but this is a very weak lower bound.)

  • 1
    $\begingroup$ If by $n$ other edges you allow the edge itself, then yes. Just take the Fano Plane. $\endgroup$ – Tony Huynh Jan 21 '17 at 19:28
  • $\begingroup$ Thanks for your example. No, I don't want to allow the edge itself. $\endgroup$ – Dominic van der Zypen Jan 22 '17 at 7:00
  • $\begingroup$ Edited the post accordingly. $\endgroup$ – Dominic van der Zypen Jan 22 '17 at 7:06
  • 1
    $\begingroup$ A finite projective plane is still a solution for any $n$. Or does $n$ denote $|V|$? $\endgroup$ – domotorp Jan 22 '17 at 8:27
  • 2
    $\begingroup$ Steiner triple systems. $\endgroup$ – Brendan McKay Jan 22 '17 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.