1
$\begingroup$

I first asked the question below at math.stackexchange.com ( https://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in mathoverflow.net instead. Here's the question:

An intersecting linear hypergraph is a pair $H=(P,\mathcal{L})$ where $P\neq\emptyset$ is a finite set and $\mathcal{L}$ is a collection of subsets of $P$ such that

  • every member of $\mathcal{L}$ has at least 2 elements, and
  • if $l_1, l_2 \in \mathcal{L}$ then there is $p\in P$ such that $l_1 \cap l_2 = \{p\}$.

I am convinced that in any intersecting linear hypergraph $H=(P,\mathcal{L})$ we have at least as many points as lines (i.e. $|P| \geq |\mathcal{L}|$). How can this be proved (if it is correct at all)? And if it is correct, does $|P| \geq |\mathcal{L}|$ also hold if $P$ is infinite?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You can probably use the proof of fisher's inequality for this. $\endgroup$
    – The Masked Avenger
    Commented Sep 8, 2014 at 7:45
  • 2
    $\begingroup$ This is indeed Fisher's Inequality. You are perhaps thinking of $\mathcal{P}$ and $\mathcal{L}$ as lines, which is fine, But if you call the elements of $\mathcal{P}$ lines and those of $\mathcal{L}$ points then your rule says that every two points determine a unique line. $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 8, 2014 at 8:39
  • $\begingroup$ Thanks for pointing me to Fisher's inequality. I assume this argument can be generalised to prove the statement for intersecting linear hypergraphs with infinite number of points and lines (or maybe in that case, an easy set-theoretic argument does the job, will have to think about it). $\endgroup$
    – Dominic van der Zypen
    Commented Sep 8, 2014 at 11:05

1 Answer 1

Reset to default
1
$\begingroup$

The usual proof of Fisher's inequality is very finite. I will call things in $\mathcal{P}$ points and those in $\mathcal{L}$ lines although the reverse might be more natural. Let $L=|\mathcal{L}|,P=|\mathcal{P}|$ and let line $\ell_i$ have $c_i+1$ points. Consider $A$, the $L \times P$ $0,1$ matrix giving incidence between the two sets. It has rank at most $\min(L,P).$ Now $B=AA^T$ is an $L \times L$ matrix with all off diagonal entries $1$ and diagonal entries $1+c_i$. It is easy to find the determinant of $B$ and that it is positive. In fact it is $\Pi c_i(1+\Sigma\frac{1}{c_i})$. So $A$ has rank at least that of $B$ which is $L.$ Hence $\min(P,L) \ge L.$ The case $P=L$ is quite interesting but is another story.

In the infinite case I think it always happens that $P=L$ if we eliminate unneeded points, however this is not that special. For $\mathcal{P}$ infinite we would consider that the set $\mathcal{P}_2$ of pairs from $\mathcal{P}$ has the same size as $\mathcal{P}$ itself. But $|\mathcal{L}|$ is certainly no larger $|\mathcal{P}_2$ since any pair of points from a line $\ell$ determines it uniquely.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If L is a set family (and not a multiset) one can remove the cardinality restriction and get a slightly larger class of designs. $\endgroup$
    – The Masked Avenger
    Commented Sep 9, 2014 at 4:40
  • $\begingroup$ I'm not sure what you mean. It doesn't seem that $\mathcal{L}$ could be a multiset since any line has at least two points and shares exactly one with any other line. $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 9, 2014 at 5:26
  • $\begingroup$ Only that the intersection condition by itself (and L a set) means that at most one member of L has one point, and that such a design also satisfies Fisher's inequality. $\endgroup$
    – The Masked Avenger
    Commented Sep 9, 2014 at 6:55
  • $\begingroup$ OK yes. In this formulation any two lines intersect but not every pair of points is co-linear. If we swap the names point and line then we have a set L of points each pair of which belongs to a unique line p from P. Then there can be a single line of all the points or else |P|>=|L|. For |P|=|L| you either have a line of |L|-1 points with one more point connected to them all or else $|L|=|P|=q^q+q+1$ (for some $q$)and all lines have $q+1$ points. $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 9, 2014 at 17:31

You must log in to answer this question.

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