2
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ Nice - can you put this as an answer? Or would it be better to delete the question entirely? $\endgroup$
    – Dominic van der Zypen
    Commented Mar 23, 2017 at 6:56
  • $\begingroup$ what if we take $\mathcal{C}$ to be the three sets $\{1,2\}$, $[n]\setminus \{1 \}$ and $[n]\setminus\{2\}$? $\endgroup$
    – Pietro Majer
    Commented Mar 23, 2017 at 6:58
  • $\begingroup$ 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 $\endgroup$
    – Dominic van der Zypen
    Commented Mar 23, 2017 at 7:01
  • 1
    $\begingroup$ 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) $\endgroup$
    – Dominic van der Zypen
    Commented Mar 23, 2017 at 7:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – monkeymaths
    Commented Mar 23, 2017 at 11:09

2 Answers 2

Reset to default
4
$\begingroup$

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\}\ $$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Can you describe this more concretely? I am afraid I don't understand your answer $\endgroup$
    – Dominic van der Zypen
    Commented Mar 23, 2017 at 10:18
  • $\begingroup$ I should get a minimal example as well (I just got distracted by editing above answer :) ). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Mar 23, 2017 at 10:30
  • $\begingroup$ 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. $\endgroup$
    – monkeymaths
    Commented Mar 24, 2017 at 14:18
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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