2
$\begingroup$

A complete linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. $|e|\geq 2$ for all $e\in E$,
  2. $|e_1\cap e_2|=1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$, and
  3. for all $v\in V$ we have $|\{e\in E:v\in e\}| \geq 2.$

For $n>2$ set $\mathbb{N}_n =\{1,\ldots,n\}$ and $$\ell(n)=\min\{|E|: E\subseteq{\cal P}(\mathbb{N}_n) \text{ and }(\mathbb{N}_n, E) \text{ is complete linear}\},$$ so $\ell(n)$ is the greatest lower bound for the number of edges on a complete linear hypergraph on $n$ points.

Question: What is the value of $\ell(n)$, depending on $n$?

(Note concerning least upper bounds: If $H=(V,E)$ is a complete linear hypergraph with $|V|=n>2$, then $|E| \leq n$ by the theorem of DeBruijn-Erdos, and we can reach $|E| = n$ with the so-called "near pencil", see the same link.)

Improve this question
$\endgroup$
2
  • $\begingroup$ A few remarks. (1) The De Bruijn-Erdos theorem isn't quite applicable here because [a] that theorem is about geometric line configurations {not about hypergraphs} and [b] that theorem is a statement about the collection of ALL lines containing at least two points. (2) In either case, the theorem would actually imply $|E| \geq n$. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 20:39
  • $\begingroup$ However, because any two edges intersect in $1$ point, we do in fact get $|E| \leq n$ by Fisher's inequality. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 20:45

3 Answers 3

Reset to default
3
$\begingroup$

Let $L$ be the number of edges in the configuration and $n$ the number of points. Then $n \leq {L \choose 2}$ and this bound is tight.

There are configurations with that many points: Let the points correspond to the two element subsets of $\{1, 2, \ldots, k\}$. And let the edges correspond to the numbers $\{1, 2, \ldots , k\}$. Then say edge $L_i$ contains the vertex $v_{\{a,b\}}$ iff $i \in \{a,b\}$. This is linear, and it has ${k \choose 2}$ points and $k$ edges. It covers each point exactly twice.

Any configuration has at most that many points: The previous answer can be pushed to give $L \geq \sqrt{2n}$, but we can get our above bound exactly. Let $\mathcal{L}$ be the set of edges. For each point $i \in \{1, 2, \ldots , n\}$, associate a set $V_i \subseteq \mathcal{L}$, which is the edges in $\mathcal{L}$ containing the point $i$. Then for all $i \neq j$, we have $|V_i \cap V_j| \leq 1$ (else there are two edges containing the same two points). We know that each point is covered at least twice, so $|V_i| \geq 2$. For each set $V_i$, let $W_i$ be any subset of size $2$ (it doesn't matter how we pick $W_i$). Then the sets $W_i$ are distinct $2$-element subsets of $\mathcal{L}$, which means there are at most ${L \choose 2}$ of them.

Added afterwards: To complete the discussion, we have the corresponding lower bound on $n$ that $L \leq n$. This is by (generalized) Fisher's inequality, and it uses the fact that the intersection of any two edges has size $1$. And this can be attained by the near pencil mentioned in original post or a projective plane.

So together, we have $L \leq n \leq {L \choose 2}$ and both bounds are best possible.

Improve this answer
$\endgroup$
5
  • $\begingroup$ In fact, the proof also shows ${L \choose 2} \geq \sum_{i=1} ^{n} {|V_i| \choose 2} \geq n$. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 1:45
  • $\begingroup$ And it seems like you don't need the condition $|e_i| \geq 2$. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 17:51
  • $\begingroup$ It is wrong that there can be $n\choose 2$ edges, see DeBruijn Erdos theorem. And it turns out I dont understand your lower bound either $\endgroup$
    – Dominic van der Zypen
    Commented Nov 22, 2016 at 18:38
  • $\begingroup$ Here's another way to get the bound $n = {L \choose 2}$ that's more geometric. Namely, just take $L$ lines in the plane that are in general position (i.e., no three intersect in a point and no two are parallel). [This is what happens if you draw $L$ lines at random.] Only consider the $n = {L \choose 2}$ points where they intersect. Then each line has $L-1$ points on it, each point is on exactly $2$ lines, and any two points determine a line. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 20:42
  • $\begingroup$ By the way, I agree that there cannot be ${n \choose 2}$ edges. But there can be ${L \choose 2}$ points. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 20:52
1
$\begingroup$

It is about $\sqrt n$. If each edge has size at most $\sqrt n$, then you need at least $2n/\sqrt n=2\sqrt n$ edges to cover everything twice. If there's an edge of size at least $\sqrt n$, then you need at least these many other edges to cover each of its points at least twice. With some more involved argument of this kind, you might even get asymptotically $2\sqrt n$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks -- what I don't see yet is how to cover $n^2$ points, say, with $2n$ edges such that every pair of edges intersect and such that every point is covered by at least $2$ edges. Can you give a short example on that? $\endgroup$
    – Dominic van der Zypen
    Commented Nov 21, 2016 at 16:58
  • $\begingroup$ Here is an example with $n=k^2+2$ and $2k+1$ lines. Start with two points on the $x$ axis. Draw $k$ lines of positive slope leaving one and $k$ of negative slope leaving the other. Keep only the intersection points. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 21, 2016 at 19:37
  • $\begingroup$ Actually, I was just thinking of a grid... $\endgroup$
    – domotorp
    Commented Nov 21, 2016 at 21:58
  • $\begingroup$ This is a grid of $2k$ lines on $k^2$ points plus a 2 point line "$h,v$" with $h$ a point common to all horizontal lines and $v$ common to all vertical lines. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 21, 2016 at 23:07
  • $\begingroup$ This same argument can be pushed to show a lower bound of about $\sqrt{2n}$. $\endgroup$
    – Pat Devlin
    Commented Nov 22, 2016 at 0:25
1
$\begingroup$

I'll conjecture that for $n \gt 20$, $\ell(n) \le \sqrt{2n}+3.$

It seems optimal to have most points on only two lines. So consider first the case that there is at most one line with points on it having more than two lines.

Write $[a_1,a_2,\cdots,a_t]$ for the configuration of one line with $t$ points with point $i$ having $a_i$ other lines on it. Assuming that all other points have only $2$ lines on them, the number of other points is $$\sum_{i \lt j}a_ia_j= \frac{(\sum a_i)^2-\sum a_i^2}{2}$$ giving a total of $n=\frac{(\sum a_i)^2-\sum a_i^2}{2}+t$ points and $e=1+\sum a_i$ lines.

In brief $[n,e,[a_1,a_2,\cdots,a_t]$

If all the $a_i=1$ then $n=\binom{t}2$ and $e=t+1$ so $e=\lceil \sqrt{2n}\rceil$ which, as noted by several people, is minimal. So for $\binom{t}2 \lt n \le \binom{t+1}2$ the best we can possibly have is $e=t+2.$

Here are the best results of this special type with up to $11$ lines.

$[6, 4, [1, 1, 1]], [7, 7, [1, 5]], [8, 5, [1, 1, 2]], [9, 9, [1, 7]], $

$[10, 5, [1, 1, 1, 1]], [11, 6, [1, 2, 2]], [12, 7, [1, 1, 4]], [13, 6, [1, 1, 1, 2]], [14, 7, [1, 2, 3]],$

$ [15, 6, [1, 1, 1, 1, 1]], [16, 7, [1, 1, 1, 3]], [17, 7, [1, 1, 2, 2]], [18, 8, [1, 3, 3]], [19, 7, [1, 1, 1, 1, 2]], [20, 9, [1, 2, 5]],$

$ [21, 7, [1, 1, 1, 1, 1, 1]], [22, 8, [1, 2, 2, 2]], [23, 8, [1, 1, 1, 1, 3]], [24, 8, [1, 1, 1, 2, 2]], [25, 9, [1, 1, 2, 4]], [26, 8, [1, 1, 1, 1, 1, 2]], [27, 9, [1, 1, 1, 1, 4]],$

$[28, 8, [1, 1, 1, 1, 1, 1, 1]], [29, 9, [1, 1, 1, 2, 3]], [30, 9, [1, 1, 2, 2, 2]], [31, 9, [1, 1, 1, 1, 1, 3]], [32, 9, [1, 1, 1, 1, 2, 2]], [33, 10, [1, 2, 3, 3]], [34, 9, [1, 1, 1, 1, 1, 1, 2]], [35, 10, [1, 1, 1, 3, 3]], $

$[36, 9, [1, 1, 1, 1, 1, 1, 1, 1]] [37, 10, [1, 2, 2, 2, 2]], [38, 10, [1, 1, 1, 1, 2, 3]], [39, 10, [1, 1, 1, 2, 2, 2]], [40, 10, [1, 1, 1, 1, 1, 1, 3]], [41, 10, [1, 1, 1, 1, 1, 2, 2]], [42, 11, [1, 1, 2, 2, 4]], [43, 10, [1, 1, 1, 1, 1, 1, 1, 2]], [44, 11, [1, 1, 1, 1, 2, 4]],$

$[45, 10, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [46, 11, [1, 1, 1, 1, 1, 1, 4]], [47, 11, [1, 1, 2, 2, 2, 2]], [48, 11, [1, 1, 1, 1, 1, 2, 3]], [49, 11, [1, 1, 1, 1, 2, 2, 2]], [50, 11, [1, 1, 1, 1, 1, 1, 1, 3]], [51, 11, [1, 1, 1, 1, 1, 1, 2, 2]], [53, 11, [1, 1, 1, 1, 1, 1, 1, 1, 2]], $

$[55, 11, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]$

A slight variation is to take a configuration (of this type or another), pick $s$ lines no $3$ sharing a point and consider the $\binom{s}{2}$ intersection points. These can be fused into one point preserving $e$ and decreasing $n$ to $n+1 -\binom{s}{2}.$

For example the configuration $[22, 8, [1, 2, 2, 2]]$ can have $3$ points determined by $3$ lines fused into $1$ to get a solution for $(20,8).$ This is better than the solution given with $(20,9).$

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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