Skip to main content
2 of 2
added 53 characters in body

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.)