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

$\endgroup$
  • $\begingroup$ Nice - can you put this as an answer? Or would it be better to delete the question entirely? $\endgroup$ – Dominic van der Zypen Mar 23 '17 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 Mar 23 '17 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 Mar 23 '17 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 Mar 23 '17 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 Mar 23 '17 at 11:09
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\}\ $$.

$\endgroup$
  • 2
    $\begingroup$ Can you describe this more concretely? I am afraid I don't understand your answer $\endgroup$ – Dominic van der Zypen Mar 23 '17 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 Mar 23 '17 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 Mar 24 '17 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.