8
$\begingroup$

Let $S = \{1,...,n\}$ be a set of $n$ elements and let $Y$ be a set of non-empty subsets of $S$ with the following requirements:

  • $|Y|$ is odd.
  • Every element in $S$ is contained in an even number of sets in $Y$.
  • Every pair of elements of $S$ is contained in an even number of sets in $Y$.

Question: Does there exist $y_1 \neq y_2 \in Y$ such that $(\exists_{a \in y_1} \forall_{b \in y_2} : a < b) \wedge (\exists_{a \in y_1} \forall_{b \in y_2} : a > b)$, that is, such that $y_1$ contains an element that is strictly smaller than all elements in $y_2$ and an element that is strictly larger than all elements in $y_2$?

Below you find two examples of systems that satisfy the requirements. Set containment of the elements are displayed using lines. In both examples the answer is YES no matter the ordering of the elements, is this always the case?

Two examples

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Note that you can rewrite your conditions in a nice way. Let $A$ be the $|Y| \times |S|$ matrix of $0$'s and $1$'s, as Max Alekseyev considers. With matrix operations considered modulo $2$, your conditions are that $A^T A = 0$, in other words, that the image of $A$ is an isotropic subspace of $\mathbb{F}_2^{|Y|}$. (In particular, your hypotheses are invariant under column operations, and your conclusion isn't.) $\endgroup$
    – David E Speyer
    Commented Apr 30, 2019 at 17:01
  • $\begingroup$ @DavidESpeyer: I do not quite follow your comment that conclusion is not invariant under column operations. Surely, $y_1,y_2$ depend on the column order, and different orders may in principle correspond to different pairs $y_1,y_2$. So, what is the point in your comment? $\endgroup$
    – Max Alekseyev
    Commented Apr 30, 2019 at 19:24

1 Answer 1

Reset to default
6
$\begingroup$

After numerous failed attempts to prove this, I found a counterexample with $n=6$ and $|Y|=13$: $$\{1\}, \{1,2\}, \{3,4\}, \{5,6\}, \{1,2,3\}, \{2,3,4\}, \{3,4,5\}, \{4,5,6\}, \{1,3\}, \{2,4\}, \{3,5\}, \{3,4,6\}, \{3,6\}$$ or in the form of $13\times 6$ incidence matrix: $$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1\\ \end{bmatrix} $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice example. $\endgroup$
    – Jari de Kroon
    Commented May 1, 2019 at 7:53
  • $\begingroup$ @JarideKroon: I suspect it may be the smallest counterexample. So, from perspective of small examples, you conjecture looked very plausible. But it was a real challenge to search for a proof, and to convince myself that the conjecture may be false. Afterwards the counterexample was found with Integer programming. $\endgroup$
    – Max Alekseyev
    Commented May 1, 2019 at 15:17

You must log in to answer this question.

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