Return to Question

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question, sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any commutative magma (and therefore any commutative semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups, but I will try to double check when I have some time.

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question, sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any commutative magma (and therefore any commutative semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups.

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any magma (and therefore any semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups, but I will try to double check when I have some time.

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question, sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any commutative magma (and therefore any commutative semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups, but I will try to double check when I have some time.

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$ (note that $X$ and $Y$ need not be disjoint, and they can even be equal).

Proving it should be difficult, because it would imply the union-closed sets conjecture: if $S$ is a union-closed family without any element in at least half of the sets, then $a \setminus b \subseteq y_1 \cap \cdots \cap y_m \cap a = \emptyset$ and $b \setminus a \subseteq x_1 \cap \cdots \cap x_m \cap b = \emptyset$ and then $a = b$, a contradiction.

Is it easier to find a counterexample?

EDIT

I didn't mention my previous question sorry. There, if I didn't make errors, I think I proved, but with a calculator, experimentally with an ILP, that any magma (and therefore any semigroup) of order $n=4$ satisfy the conjecture. Regarding the counterexamples found there for $n \ge 5$ I don't think they are semigroups, but I will try to double check when I have some time.