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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Dec 21, 2015 at 16:47

You must log in to answer this question.

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