0
$\begingroup$

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.)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ If by $n$ other edges you allow the edge itself, then yes. Just take the Fano Plane. $\endgroup$
    – Tony Huynh
    Jan 21, 2017 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, 2017 at 7:00
  • $\begingroup$ Edited the post accordingly. $\endgroup$
    – Dominic van der Zypen
    Jan 22, 2017 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, 2017 at 8:27
  • 2
    $\begingroup$ Steiner triple systems. $\endgroup$
    – Brendan McKay
    Jan 22, 2017 at 9:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.