Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on Isomorphism theorems for semigroups of order-preserving transformations with restricted range
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Finding necessary and sufficient conditions for isomorphism between two semigroups of order-preserving transformations over an infinite domain with restricted range was an open problem in cite{FHQS}. In this paper, we show a proof strategy to answer that question.
rate research
Read More
Let g be a strategy-proof rule on the domain NP of profiles where no alternative Pareto-dominates any other and let g have range S on NP. We complete the proof of a Gibbard-Satterthwaite result - if S contains more than two elements, then g is dictatorial - by establishing a full range result on two subdomains of NP.
For each subchain $X$ of a chain $X$, let $T_{RE}(X, X)$ denote the semigroup under composition of all full regressive transformations, $alpha:Xrightarrow X$ satisfying $xalphaleq x$ for all $xin X$. Necessary and sufficient conditions for $T_{RE}(X,X)$ and $T_{RE}(Y,Y)$ to be isomorphic are given. This isomorphism theorem is applied to classify the semigroup of regressive transformations $T_{RE}(X,X)$ where $X$ are familiar subchains of $R$, the chain of real numbers.
First we give a definition of a coverage on a inverse semigroup that is weaker than the one gave by a Lawson and Lenz and that generalizes the definition of a coverage on a semilattice given by Johnstone. Given such a coverage, we prove that there exists a pseudogroup that is universal in the sense that it transforms cover-to-join idempotent-pure maps into idempotent-pure pseudogroup homomorphisms. Then, we show how to go from a nucleus on a pseudogroup to a topological groupoid embedding of the corresponding groupoids. Finally, we apply the results found to study Exels notions of tight filters and tight groupoids.
In this work, we present a standard model for Galois rings based on the standard model of their residual fields, that is, a sequence of Galois rings starting with ${mathbb Z}_{p^r} that coves all the Galois rings with that characteristic ring and such that there is an algorithm producing each member of the sequence whose input is the size of the required ring.
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs $G$ and $H$, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP-complete: for each $u in V(G)$, we are given a list ${mathfrak L}(u) subseteq V(H)$ of possible images of $u$. After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso. We prove the following: 1) When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso. 2) Combinatorial algorithms for GraphIso translate into algorithms for ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs. 3) Algorithms based on group theory do not translate: ListIso remains NP-complete for cubic colored graphs with sizes of color classes bounded by 8. Also, ListIso allows to classify results for the graph isomorphism problem. Some algorithms are robust and translate to ListIso. A fundamental problem is to construct a combinatorial polynomial-time algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NP-hard for them, so no robust algorithm for cubic graph isomorphism exists, unless P = NP.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
