# Minimizing the maximum degree of a set of sets

Suppose that ${\cal C}$ is a set of subsets of $\{1,\ldots,n\}$ with the following properties:

1. $\{1,\ldots,n\}\notin {\cal C}$,
2. for all $x,y\in \{1,\ldots, n\}$ there is $A\in {\cal C}$ such that $\{x,y\}\subseteq A$, and
3. $|A\cap B| \leq 1$ for all $A\neq B\in{\cal C}$.

For $j\in \{1,\ldots,m\}$ we set the degree of $j$ to be $\text{deg}(j) = |\{A\in {\cal C}: j\in A\}|$ and set $$m({\cal C}) = \max\big\{\text{deg}(j): j\in\{1,\ldots,n\}\big\}.$$

Is it possible that $m({\cal C}) < n-1$? If yes, how small in terms of $n$ can $m({\cal C})$ become?

(You only need to answer the first question to get the answer accepted; the second question is a bonus question.)

• Nice - can you put this as an answer? Or would it be better to delete the question entirely? – Dominic van der Zypen Mar 23 '17 at 6:56
• what if we take $\mathcal{C}$ to be the three sets $\{1,2\}$, $[n]\setminus \{1 \}$ and $[n]\setminus\{2\}$? – Pietro Majer Mar 23 '17 at 6:58
• Very nice - all these examples escaped me! - I was wondering, what happens if you add a 3rd condition to the 2 stated in the question: $|A\cap B| \leq 1$ for all $A\neq B\in{\cal C}$. -- Just edited the question accordingly – Dominic van der Zypen Mar 23 '17 at 7:01
• If I understand your argument correctly, we get that $|{\cal C}| \geq n-1$, but how does it imply that the maximum degree of all the points is $\geq n-1$? (Probably I'm missing something) – Dominic van der Zypen Mar 23 '17 at 7:12
• A simple example with $m = n/2 + 1$: For $n = 2k$ even, take as your ground-set $X$ the set of all points $(i,r)$ in the plane where $1 \leq i \leq k$ and $r \in \{ 0, 1 \}$. Take $\mathcal{C}$ as the set of all lines through at least two of these points. (1) Not all lie on a line (if $k \geq 2$). (2) Any two lie on a common line. (3) Any two lines have at most one common point. (4) Each point lies in $k+1$ lines. – monkeymaths Mar 23 '17 at 11:09

Consider the 9-point affine plane $\ F_3\times F_3,\$ over the 3-element Galois field $\ F_3.\$ Then $\ n=9,\$ while the respective $\ m(C)=4 < n-1$.

Here $\ C\$ is the set of affine lines, i.e. sets described by the linear equations (homogeneous and non-homogenous, just like in an elementary school).

The explicit set of 4 straight lines which include point (0\ 0) is:

$$\{(0\ 0)\ \ (0\ 1)\ \ (0\ 2)\}$$ $$\{(0\ 0)\ \ (1\ 0)\ \ (2\ 0)\}$$ $$\{(0\ 0)\ \ (1\ 1)\ \ (2\ 2)\}$$ $$\{(0\ 0)\ \ (1\ 2)\ \ (2\ 1)\}$$

Now let us consider a 6-point space which is a union of two parallel lines of the above plane, i.e. now $\ n=6.\$ Then in family $\ C\$ consists of the intersections of the straight lines with our 6-point space (all members of this new space are two 3-point sets, and nine 2-point sets). Now $\ m(C) = 4 < n-1.$ This time I believe that this $\ n=6\$ is minimal.

Thge example is simple enough to forget about geometry--let our space be $\ \{\, 1\ 2\ 3\ 4\ 5\ 6\,\}.\$ Then let consist of two 3-point sets:

$\{a+1\ \ a+2\ \ a+3\}\quad$ for $\ a=0\$ and for $\ a=3$

and nine 2-point sets:

$$\{a\ b\}\ :\ (a\ b)\in \{1\ 2\ 3\}\times\{4\ 5\ 6\}\$$.

• Can you describe this more concretely? I am afraid I don't understand your answer – Dominic van der Zypen Mar 23 '17 at 10:18
• I should get a minimal example as well (I just got distracted by editing above answer :) ). – Włodzimierz Holsztyński Mar 23 '17 at 10:30
• Note that working in an arbitrary $F_p \times F_p$ for a prime number $p$ should yield a set $\mathcal{C}$ of lines with $m(\mathcal{C}) = p+1$, where the ground-set has size $n = p^2$. I don't know if the square root is optimal. – monkeymaths Mar 24 '17 at 14:18

I'll show that

THEOREM $\ n=5\$ is minimal.

First, observe that it's not possible for all members of $\ C\$ to have 2 (or less) points. Indeed, all sets $\ \{0\ x\},\$ where $\ x\ne 0\,$ would belong to $\ C,\$ hence $\ m(C)\ge n-1.\$

Thus, we may assume that there is $\ A\in C\$ such that $\ \{1\ 2\ 3\}\subseteq A.\$ If there was only one point $\ b\notin A\$ then $\ \{a\ b\}\in C\$ for every $\ a\in A,\$ hence $\ m(C)\ge |A|=n-1\$ -- a contradiction.

We see that the minimal $\ n\$ is at least $\ 5.\$

Indeed, we have a 5-point example consisting of complex numbers

$$-1\qquad -\!i\qquad 0\qquad i\qquad 1$$

The members of $\ C\$ are defined as the nontrivial intersections of the Euclidean lines with the given 5-point set (where nontrivial means that the intersection has at least $\ 2\$ different points). We see like Euclid would that $\ m(C)=3<4 = n-1.\$ This proves the $\ n=5\$ is correct and minimal. END of PROOF

REMARK   Whenever we have a system described by Dominic (just don't insist on points being consecutive integers) then the trace of such a system on a subset forms a similar system.