Let $G$ be a finite semigroup with order $n$ odd. Let $S_i \in G, i=1,\ldots,\binom{n}{(n+1)/2}$ be all the subsets of $G$ of size $(n+1)/2$.
Let $E(S_i)$ be the set obtained "expanding" $S_i$ with the following rules:
- if $x \in S_i$ then $x \in E(S_i)$
- if $x,y \in E(S_i)$ then $xy \in E(S_i)$
- if $xy \in E(S_i)$ then $x \in E(S_i)$ and $y \in E(S_i)$
I conjecture that there always exists an element $a$ contained in at least $\binom{n}{(n+1)/2}-1$ of the "expanded" sets $E(S_i), i=1,\ldots,\binom{n}{(n+1)/2}$.
Can we give a counterexample or say something about this conjecture?
Best Answer
I conjecture that there always exists an element $a$ contained in at least $\binom{n}{(n+1)/2}-1$ of the "expanded" sets $E(S_i), i=1,\ldots,\binom{n}{(n+1)/2}$.
(Rephrasing to better match what is below: I conjecture that there always exists an element $a$ contained in all, except possibly $1$, of the "expanded" sets $E(S_i), i=1,\ldots,\binom{n}{(n+1)/2}$.)
This conjecture is false. I will give a counterexample that is a strong semilattice of groups.
Background . (Strong semilattice of groups)
Let $(S,\wedge)$ be a meet semilattice, let $(G_s,\ast_s)$, $s\in S$, be an $S$-indexed family of groups, and for $s <t$ in $S$ let $\varphi_{t,s}\colon G_t\to G_s$ be a group homomorphism. Assume that (i) when $r\leq s\leq t$ we have $\varphi_{s,r}\circ \varphi_{t,s}=\varphi_{t,r}$ and (ii) when $s=t$ the homomorphism $\varphi_{t,s}=\varphi_{s,s}$ is the identity endomorphism of $G_s$. The associated strong semilattice of groups, $\mathcal S$, has universe equal to the disjoint union $\sqcup_{s\in S} G_s$ and has multiplication defined by the rule: $x\in G_s$, $y\in G_t$ implies $xy = \varphi_{s,s\wedge t}(x)\ast_{s\wedge t} \varphi_{t,s\wedge t}(y)$. This is a semigroup multiplication.
(Character supports)
Let $\mathbf{2}$ be the subsemigroup of the multiplicative semigroup $(\mathbb R,\cdot)$ with universe $\{0,1\}$. This is a $2$-element (meet) semilattice. If $S$ is any semigroup, call a homomorphism $\chi\colon S\to \mathbf{2}$ a character and call $\chi^{-1}(1)$ the support of $\chi$. A subset $U\subseteq S$ of a semigroup $S$ is a character support if and only if $xy\in U \Leftrightarrow (x\in U)\& (y\in U)$. Character supports are closed under intersection, since if $\chi, \chi'\colon S\to \mathbf{2}$ have supports $U, U'$, then the product character $(\chi\cdot \chi')(x):=\chi(x)\cdot \chi'(x)$ has support $U\cap U'$. Therefore, if $S$ is a finite semigroup, each subset $U\subseteq S$ is contained in (or 'generates') a smallest character support. In the problem statement, this smallest character support containing $U$ is denoted $E(U)$ and is called the set obtained by 'expanding' $U$.
Foreground. (The example.)
Let $R=\{1,2,\ldots,r\}$ and let $S$ be the meet semilattice whose elements are the proper subsets of $R$ and whose operation is intersection. This semilattice is the power set $\mathcal{P}(R)$ without the top element under the operation of intersection.
Choose a finite group $H$. For each $s\in S$ define $G_s$ to be $H$ if $s$ is a maximal proper subset of $R$. Define $G_s$ to be the $1$-element group, $\mathbf{1}$, otherwise. The maps $\varphi_{t,s}$ are completely determined by this information: when $s=t$ we must have $\varphi_{s,s}=\textrm{id}_{G_s}$ and when $s<t$ we must have $\varphi_{t,s}\colon H\to \mathbf{1}$ the constant homomorphism. The associated strong semilattice of groups has a copy of $H$ living at each maximal element of ${\mathcal P}(R)-\{R\}$ and a copy of $\mathbf{1}$ living at each `submaximal' element of ${\mathcal P}(R)-\{R\}$. ('Submaximal' means: strictly below some maximal element.)
If $h:=|H|$, then the size of our semigroup $\mathcal S$ is $rh+ (2^r - r - 1)\;(=r(h-1)+(2^r-1))$. This counts the $r$ copies of $H$ living at the maximal elements of ${\mathcal P}(R)-\{R\}$ together with one copy of $\mathbf{1}$ living at each submaximal element of ${\mathcal P}(R)-\{R\}$. The size of this semigroup can be odd, e.g. $|\mathcal S|$ is odd whenever $r$ is even or whenever $r$ and $h$ are both odd. (I am mentioning that $|\mathcal S|$ can be odd, since that is one of the restrictions in the problem.)
Claim. For each $a\in \mathcal S$ there are at least $$ \binom{(r-1)(h-1)+(2^{r-1}-1)}{\frac{r(h-1)}{2}+2^{r-1}} $$ sets of the form $E(S_i)$ that fail to contain $a$. (For example, if $r=4$, this says that there are at least $\binom{3h+4}{2h+6}$ sets of the form $E(S_i)$ that fail to contain $a$. This number is greater than $1$ whenever $h=|H|>2$, hence the conjecture in the problem statement is false.)
Reasoning for Claim. Choose any $a\in \mathcal S$. Then $a\in G_U$ for some $U\in {\mathcal P}(R)-\{R\}$. $U$ is a proper subset of $R$, so there is some $k\in R-U$. The set $Y$ of all $y\in \mathcal S$ such that $y\in G_V$ for some $V$ containing $k$ is a character support. [Showing that $Y$ is a character support of $\mathcal S$ reduces to showing that an intersection of sets $V, V'\in {\mathcal P}(R)-\{R\}$ will contain $k$ iff both $V$ and $V'$ contain $k$.]
The size of $Y$ can be computed to be $(r-1)(h-1)+(2^{r-1}-1)$. The main takeaway from this paragraph is that for any $a\in \mathcal S$ there is a relatively large character support $Y$ such that $a\notin Y$.
Now, following the notation of the problem statement, use $S_i$ to represent some subset of $\mathcal S$ that has size $(|\mathcal S|+1)/2$. Since $Y$ is a character support and $E(S_i)$ is the least character support containing $S_i$, we derive that $S_i\subseteq Y$ implies $E(S_i)\subseteq Y$, which further implies that $a\notin E(S_i)$. Thus, $a$ does not belong to any $E(S_i)$ where $S_i$ is a subset of $Y$ of size $(|\mathcal S|+1)/2$. The number of subsets of $Y$ of size $(|\mathcal S|+1)/2$ can be computed in terms of $r$ and $h$ to be $$ \binom{(r-1)(h-1)+(2^{r-1}-1)}{\frac{r(h-1)}{2}+2^{r-1}}. \Box $$
(One sentence summary: There is a semigroup $\mathcal S$ such that for every $a\in \mathcal S$ there is a large character support $Y$ that does not contain $a$, therefore $a$ does not belong to the many character supports of the form $E(S_i)$ that are subsets of $Y$.)