Points and lines inequality

112 Views Asked by At

Suppose you have an abstract configuration of $P$ points and $L$ lines such that for any two points $p$ and $q$, there exists a unique line $\ell$ passing through both $p$ and $q$.

By an "abstract configuration" I just mean that there is a set $\mathcal P$ of points and a set $\mathcal L$ of lines and an incidence relation $R\subseteq\mathcal P\times\mathcal L$.

Is it true that $P\leq L$ unless the configuration is "degenerate"? In other words, is there a simple classification of configurations with $P>L$?

If not, under what conditions can we conclude that $P\leq L$?


In the special case where all points have an equal number $k$ of lines through them (such as in the game of Spot-It) then the following argument shows that $P\leq L$ unless there is a line containing all $P$ points:

Suppose that there is not a line containing all $P$ points. Let $\ell$ be a line and let $n_\ell$ count the number of points on $\ell$. Let $p$ be a point not on $\ell$. Each point on $\ell$ gives a line passing through $p$. Thus, $n_\ell\leq k$. Summing over $\ell$ gives $$kL\geq\sum_\ell n_\ell=\sum_pk=kP$$ so $P\leq L$.

1

There are 1 best solutions below

0
On BEST ANSWER

Assume that $\left\lvert\mathcal P\right\rvert\geq\left\lvert\mathcal L\right\rvert+1$ and that there does not exist a line passing through all points.

We will apply Halls' theorem to show that there exists an injective function $f\colon\mathcal L\to\mathcal P$ such that for each line $\ell\in\mathcal L$, the point $f(\ell)$ does not lie on $\ell$. To verify the condition for Hall's theorem, let $S\subseteq\mathcal L$ and let $$T=\{p\in\mathcal P:p\text{ does not lie on every line }\ell\in S\}.$$ We need to check that $\left\lvert S\right\rvert\leq\left\lvert T\right\rvert$.

  • If $\left\lvert S\right\rvert=0$ then $\left\lvert T\right\rvert\geq0$ so $\left\lvert S\right\rvert\leq\left\lvert T\right\rvert$.
  • If $\left\lvert S\right\rvert=1$ then $\left\lvert T\right\rvert\geq1$ by our assumption that there does not exist a line passing through all points. Thus, $\left\lvert S\right\rvert\leq\left\lvert T\right\rvert$.
  • If $\left\lvert S\right\rvert\geq2$ then $\left\lvert T\right\rvert\geq\left\lvert\mathcal P\right\rvert-1$ by the uniqueness of lines passing through two specified points. Then we have $\left\lvert S\right\rvert\leq\left\lvert\mathcal L\right\rvert\leq\left\lvert\mathcal P\right\rvert-1\leq\left\lvert T\right\rvert$.

We can now apply Hall's theorem to obtain our injective function $f\colon\mathcal L\to\mathcal P$. For a point $p\in\mathcal P$, let $n_p$ denote the number of lines passing through $p$. For a line $\ell\in\mathcal L$, let $n_\ell$ denote the number of points on $\ell$. The key inequlity is $n_\ell\leq n_{f(\ell)}$ which follows from the fact that each point on $\ell$ gives a unique line passing through $f(\ell)$. Then we have $$\sum_{p\in\mathcal P}n_p=\sum_{\ell\in\mathcal L}n_\ell\leq\sum_{\ell\in\mathcal L}n_{f(\ell)}<\sum_pn_p$$ where the last inequality is strict (since the image of $f$ is a proper subset of $\mathcal P$) unless some $n_p=0$. However, if some $n_p=0$ then $\left\lvert\mathcal P\right\rvert=1$ (since if there was another point $q$ then there would be a line passing through both $p$ and $q$) which forces $\left\lvert\mathcal L\right\rvert=0$.

To summarize, we have $\left\lvert\mathcal P\right\rvert\leq\left\lvert\mathcal L\right\rvert$ unless we are in one of the following two degenerate configurations:

  • There exists a line passing through all points.
  • There is only one point, and there are no lines.