2
$\begingroup$

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact).

=================

REFORMULATION

An ordered pair $(A\ B)$ of subsets of the ring of integers $\mathbf Z$ is called globally ordered if $\ \Leftarrow:\Rightarrow\ \ a \le b\ $ for every $a\in A$ and $b\in B$.

Let $k>1$ be an arbitrary natural number. Let $\ S\ $ be a finite family of k-element subsets of $\mathbf Z,\,$ each two of which have a non-empty intersection. Is it true that if no two members of $S$ form a globally ordered pair then it's possible to color $\mathbf Z$ in such a way that every member of $S$ is bicolored ?

================

PS. I'd like to ask the author to be a bit more detailed and explicit about the definitions related to the coloring.

================

THE ORIGINAL QUESTION:

Assume we have a set of numbers $\{ 1, 2, ..., n \}$ and a set of subsets $\{ M_1, ..., M_s \}$, such that $|M_i| = k$ and $ \forall i,j\ (i\ne j\implies|M_i \cap M_j| = 1)$.

Let's define 2-chain -- it is two subsets, $M_i, M_j$ with one common element - $x$ and for every element $y \in M_i$ true that $y < x$, and and for every element $z \in M_j$ true that $z > x$. It's increasing 2-chain and in the same way we could define decreasing 2-chain.

We make a random permutation of numbers.

Proof that if there is exist such permutation that there is no 2-chains, that it's possible to colour all numbers in a way that all $M_i$ will be bicolored.

I think that we should use Lovász local lemma, but I can't build proper probability space.

Improve this question
$\endgroup$
8
  • $\begingroup$ @bof , of course, for $i \neq j$, sorry for mistake in formulation. $\endgroup$
    – DislocatedShoulder
    Dec 21, 2015 at 5:37
  • $\begingroup$ Accidentally, I omitted the condition about the 1-point intersections. Now I have inserted the non-empty intersections and (I hope) it seems to be fine. $\endgroup$
    – Włodzimierz Holsztyński
    Dec 21, 2015 at 5:44
  • $\begingroup$ I feel that the globally ordered together with the later appearance of the non-empty intersection are after all ok. The 1-point follows from these conditions. $\endgroup$
    – Włodzimierz Holsztyński
    Dec 21, 2015 at 5:48
  • $\begingroup$ @Włodzimierz Holsztyński yes, thank you for reformulation. I think I'd like to remain both formulation of problems, cause your smoother and more general, and mine, cause it's original problem in form that I have heard it. $\endgroup$
    – DislocatedShoulder
    Dec 21, 2015 at 5:53
  • $\begingroup$ Why can't you just, for each element of $S$ (or each $M_i$), colour the top element red and the bottom element blue? What am I missing? $\endgroup$
    – bof
    Dec 21, 2015 at 6:51

1 Answer 1

Reset to default
5
$\begingroup$

Yes. Let $S$ be a family of finite subsets of some linearly ordered set $L.$ Suppose that each member of $S$ has at least two elements, and that no two members of $S$ form a "globally ordered pair". Then we can color every element of $L$ red or blue so that, for each $X\in S,$ the top element of $X$ is red and the bottom element of $X$ is blue.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answer is of course utterly trivial, so I suppose I have either misunderstood the question or something has been omitted from the statement. $\endgroup$
    – bof
    Dec 21, 2015 at 6:21
  • $\begingroup$ You didn't use the assumption about the 1-point intersections, which was extra nice on your part. Of course elements which are not extremal for any member one can color in an arbitrary way. $\endgroup$
    – Włodzimierz Holsztyński
    Dec 21, 2015 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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