2
$\begingroup$

Denote $[n]=\{1,2,\dots,n\}$. Assume $n\geq2$.

Question. Is it true that given any $S_1,S_2,\dots,S_{2n}$ (repetition allowed) subsets of $[2n]$ with $a\in S_a$ and $\# S_a=n$ for all $1\leq a\leq 2n$, there exist $i, j, k\in[2n]$ (not all equal) such that $$i\in S_j, \qquad j\in S_k, \qquad k\in S_i \,\, ?$$

EDIT. There was an unfortunate typo: $\#S_a=n$ instead of $\#S_a=a$. Sorry.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
6
$\begingroup$

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (since all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there is an arrow $c\to b$ $C$ to $B$, we may take $i=c,j=a,k=b$. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$. It gives two opposite edges for $n>2$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Fedor: Of course, as often, your solutions are cute and concise but cryptic at some points. Do you think the argument holds for sets $S_1,\dots,S_{3n}\subset[3n]$ and $a\in S_a, \#S_a=n$? $\endgroup$
    – T. Amdeberhan
    Commented May 4, 2017 at 12:15
  • 1
    $\begingroup$ No, take $S_a=\{a,a+1,\dots,a+(n-1)\}$ (all modulo $3n$). But there are rooms for improvement, of course. $\endgroup$
    – Fedor Petrov
    Commented May 4, 2017 at 12:36
4
$\begingroup$

If we take again $n=2$, $S_1=\{1,2 \}$ $S_2=\{2,3 \}$ $S_3=\{3,4 \}$ $S_4=\{4,1 \}$

is a counterexample, right?

To see this label the vertices of an square clockwise with $1,2,3,4$. The $3-$distributed condition for this $n$ is equivalent to find a triangle in the graph with edges the $S_i's$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Roman: Cute example. Do you know if this is a general failure? That is, what if $n\geq3$? $\endgroup$
    – T. Amdeberhan
    Commented May 2, 2017 at 14:17

You must log in to answer this question.

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