All Questions
Tagged with semigroups-and-monoids co.combinatorics
56 questions
6
votes
3
answers
551
views
Conjecture about commutative 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, ...
- 1,000
2
votes
1
answer
423
views
Conjecture about semigroups
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" $...
- 1,000
14
votes
4
answers
742
views
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$.
I have verified the statement for $n \leq 4$ with a Mathematica code.
I have ...
- 143
6
votes
1
answer
393
views
Algebra generated by transformation matrices
Let $T_n$ be the full transformation monoid of an $n$-set $N_n$ with elements 1,...,n consisting of all functions $f: N_n \rightarrow N_n$.
We can associate to each function $f$ a matrix $M_f$ in the ...
- 26.5k
2
votes
0
answers
64
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
0
votes
1
answer
142
views
Left syndeticity and right syndeticity in nilpotent group
$\DeclareMathOperator\Pf{\mathcal{P}_\mathrm{f}}$Question: Does there exist any reference regarding the study of left and right syndeticity in nilpotent group? More specifically, did anyone introduce/...
- 73
1
vote
0
answers
274
views
Functional equation $f(x*y) = f(f(x)*f(y))$
Find all endo-functions $f$ on a commutative semigroup $(\mathbb{S},*)$ such that
$f(x*y) = f(f(x)*f(y))$.
Typical case of interest are $(\mathbb{N},+)$ or $(\mathbb{Z}/k\mathbb{Z},+)$ or $(\mathbb{Z}/...
- 1,306
6
votes
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 41.8k
25
votes
2
answers
1k
views
The number of polynomials on a finite group
A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. ...
- 41.8k
6
votes
1
answer
135
views
Automorphisms of special egg-box diagrams
By a egg-box diagram I will simply mean a (possibly infinite) rectangular array of holes, with some of the holes containing an egg (denoted by a filled-in circle) and the rest of the holes are empty (...
- 18.7k
15
votes
2
answers
655
views
Indecomposable contracting maps on the integers
$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if
$$|f(j) - f(i)| \leq |j-i|$$
for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call ...
- 156k
9
votes
1
answer
889
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 10.5k
7
votes
0
answers
193
views
Factoring a function from a finite set to itself
Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\...
- 695
8
votes
1
answer
645
views
Isomorphic morphisms. A 27-morphism category
Two morphisms of category $\ \mathbf C\ $ are isomorphic to one
another $\ \Leftarrow:\Rightarrow\ $ they are the opposite edges that are drawn horizontally (aimed East) of a commutative square that ...
- 4,786
2
votes
0
answers
203
views
Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?
It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G.
More generally here (MO275769) Qiaochu Yuan ...
- 24.9k
8
votes
1
answer
238
views
Functions over monoids which factor in two different ways
This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there.
Let $S$ be a commutative monoid and $f(x_1, \dots, x_n)$ be a function from $S^n$ ...
- 32.1k
3
votes
0
answers
134
views
Partial orders on $\mathbb{N}^m$ compatible with addition
I'm looking for a classification (or just non-trivial examples) of partial orders on monoid $\mathbb{N}^{m}$ that are compatible with addition. That is, partial orders $\leq$ satisfying two additional ...
- 645
3
votes
0
answers
81
views
Size of the kernel (minimal ideal) of a finite semigroup
Let $A$ be an irreducible nonnegative $N\times N$ integer matrix with constant row sum $D$. Let $A_1, \dots, A_D$ be nonnegative integer matrices, each with constant row sum $1$, such that $\sum_k A_k ...
- 695
11
votes
0
answers
286
views
Does every finite poset have a rigid endomorphism?
Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
- 4,416
5
votes
0
answers
107
views
Heuristics for the word problem for monoids
The question is about a purely practical problem:
Given is a list of identities, as in http://www.findstat.org/MapsDatabase/Mp00069:
...
- 5,822
5
votes
1
answer
142
views
On the width of the Catalan monoid and the rank of K-groups of the Furstenberg transformation group
The semigroup algebra of the Catalan monoid is isomorphic to the incidence algebra of $P_n$, where $P_n$ is the poset consisting of subsets of { 1,...,n } where for two subsets $X \leq Y$ if and only ...
- 26.5k
2
votes
0
answers
89
views
Semigroups associated to binary necklaces and their semigroup algebra
I came across the following semi-group and the associated finite dimensional semi-group algebras over a field $K$ (which are Nakayama algebras) as they have very nice homological properties. My ...
- 26.5k
6
votes
0
answers
89
views
Maximal number of commuting functions of a finite set
Let $S$ be a finite set with $n$ elements and let $F_S$ denote the set of functions from $S$ to $S$. I wonder whether anything is known about the maximal cardinality of a commuting subset of $F_S$? A ...
- 23.2k
12
votes
0
answers
321
views
Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field
Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...
- 38.6k
2
votes
0
answers
116
views
Bijection between monoid of nilpotent decreasing self-maps and local subsemigroup
Let $\mathcal{C}_X\cong\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $X=\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$) and decreasing ($...
- 355
2
votes
1
answer
156
views
Additivity of the upper Banach density
The following notion of upper Banach density was defined (Definition 2.1(c)) by Hindman and Strauss in their paper 'Density in arbitrary semigroups':
Definition: Let $S$ be a semigroup, let $\mathcal{...
- 73
1
vote
1
answer
326
views
Closed submonoid of $(\mathbb{C}^*)^n$
The answer of this question might be known but I was not able to find any answer. Let $n\geq 1$ and $S$ be a closed submonoid of $(\mathbb{C}^*)^n$, that is, a closed and stable by product subset of $(...
- 143
1
vote
1
answer
77
views
What is the minimal possible size of a subset of this semigroup satisfying the following conditions?
Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:
$\forall a \in P[A]$ ...
- 2,618
7
votes
2
answers
383
views
Counting nilpotent self-maps of $\{1,\dots,n\}$ with image of a given cardinal
Let $\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$ and decreasing ($\forall x$, $\alpha(...
- 355
2
votes
1
answer
229
views
Has the "semidirect monoid of a semiring" been considered anywhere?
Given a semiring $S$, we get a monoid $M(S)$ as follows:
The underlying set of $S$ is $S^2$
The identity element is $(0,1)$
The law of composition is given by $$(a,A)(b,B) = (Ba+b,AB),$$ where $a,A,b$...
- 3,793
10
votes
1
answer
673
views
Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?
Given any finite relation $R$ if we let $\circ$ denote relation composition and define $R^n=\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}$ then does there exist an explicit formula for the ...
- 2,506
2
votes
2
answers
134
views
On a generating set of numerical semigroups of multiplicity three
Let $S$ be a numerical semigroup. Let $\mathbb N$ denote the monoid of non-negative integers under addition. Let $F(S)=\max (\mathbb N \setminus S)$ be the Frobenius number of $S$; let $g(S)=|\mathbb ...
user111492
6
votes
0
answers
81
views
Representing meet-semilattices with vector spaces of specified dimensions
Take $K$ to be a field and take $L$ to be a finite meet-semilattice. I'm interested in the set of functions $n: L \rightarrow \mathbb{Z}^{\ge 0}$ such that there is some function $V$ from $L$ to ...
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
9
votes
1
answer
154
views
Inductive and reducible functions
The question was asked by a Computer Scientist and is closely related to parallel computing. But it is clearly of algebraic nature, so I decided to post it here.
Let $X$ be a set and $\bar X$ be the ...
user6976
5
votes
2
answers
137
views
The smallest number of vertices for a graph with the same endomorphism monoid
Let $G$ be a directed graph without loop and suppose that $M$ is its endomorphism monoid.
First how we can create a simple graph $\Gamma$ (using $G$), with the same endomorphism monoid? and then how ...
- 237
6
votes
1
answer
259
views
are endomorphisms "small" compared to the full transformations?
$\DeclareMathOperator\End{End}$Let $T_n$ be the full transformation semigroup/monoid of $[n]=\{1,\dots,n\}$. Let $\End(T_n)$ be the set of [endomorphisms][1] of $T_n$. Then, $\# T_n=n^n$ and
$$\# \End(...
- 43.2k
5
votes
2
answers
402
views
Maximal commuting subsets of $\text{End}(X)$
Let $X$ be a set and let $\text{End}(X)$ be the set of all functions $f:X\to X$. We say that $f, g\in \text{End}(X)$ commute if $g\circ f = f\circ g$, and $S\subseteq \text{End}(X)$ is a commuting ...
- 48.9k
17
votes
0
answers
536
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
9
votes
0
answers
373
views
Embedding $\beta\mathbb{N}$ into a product of Cantor sets
Let us consider $\beta\mathbb{N}$, the Stone-Čech compactification of the natural numbers (where we do not take $0$ to be a natural number, so the only idempotent elements are nonprincipal ...
- 297
10
votes
2
answers
444
views
Iterated sumset inequalities in cancellative semigroups
This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le \frac{|AA|^n}{|A|^n}|A|$...
- 8,688
6
votes
2
answers
237
views
Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$
This question relates to Realizing groups as automorphism groups of graphs.
Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?
- 48.9k
8
votes
1
answer
319
views
Über theorem on unavoidable patterns?
Let $A$ be an alphabet of $k$ symbols,
and $p$ a pattern.
An example of a pattern is $p=XX$, where $X$ is any finite
string of symbols from $A^+$.
Avoiding $p$ is avoiding any subword repeated twice ...
- 151k
4
votes
1
answer
196
views
Is the monoid of taking iterated images and inverse images freely generated by the image and inverse image operation?
Let $\mathcal{F}$ denote the class of all functions. Let $U,L:\mathcal{F}\rightarrow\mathcal{F}$ denote the mappings where if $f:X\rightarrow Y$, then $U(f):P(X)\rightarrow P(Y),L(f):P(Y)\rightarrow P(...
3
votes
0
answers
174
views
Number of k-generated semigroups
Given some $k>1$, I am interested in the number of $k$-generated semigroups of order $n$ (either up to isomorphism or all associative binary operations on an n-element set). At first I thought $3$-...
- 53
5
votes
1
answer
485
views
Are semigroups with finite-to-one right multiplication "moving"?
A semigroup $S$ is moving if $S$ is infinite, and for all finite
$F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that,
for all but finitely many $s\in S$,
$$
\{a_{...
- 3,104
6
votes
2
answers
781
views
What is the combinatorial data classifying non-normal affine toric varieties?
Recall that a toric variety is a variety $V$ containing an open dense algebraic torus. Here an algebraic torus means a finite product of copies of the multiplicative group of the ground field (which I ...
- 38.6k
13
votes
1
answer
2k
views
Coin problem with permutations
Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers.
It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c \mathbb{N}...
- 1,081
5
votes
2
answers
387
views
Concatenation of strings [closed]
We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
- 59
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k