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
    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
    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
    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
    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
    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
    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
    Sep 9, 2014 at 17:31

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.