A characterization of the posets that admit a finite multi-utility representation is presented. This result is also connected to the concept of order dimension of a poset as defined by Dushnik and ...Miller (1941).
For a fixed poset P, a family F of subsets of n is induced P-saturated if F does not contain an induced copy of P, but for every subset S of n such that S ∉ F, P is an induced subposet of F ∪{S}. The ...size of the smallest such family F is denoted by sat∗ (n, P). Keszegh, Lemons, Martin, Pálvölgyi and Patkós Journal of Combinatorial Theory Series A, 2021 proved that there is a dichotomy of behaviour for this parameter: given any poset P, either sat* (n, P) = O(1) or (Formula presented). In this paper we improve this general result showing that either (Formula presented). Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset (Formula presented) we have (Formula presented); so if true this conjecture implies our result is tight up to a multi-plicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset P, either sat* (n, P) = O(1) or (Formula presented). We prove that this latter conjecture is true for a certain class of posets P.
Boolean Dimension and Local Dimension Trotter, William T.; Walczak, Bartosz
Electronic notes in discrete mathematics,
August 2017, 2017-08-00, Letnik:
61
Journal Article
Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted classes of posets. ...Bounded dimension gives a succinct representation of the poset, admitting constant response time for queries of the form “is x>y?”. This application motivates looking for stronger notions of dimension, possibly leading to succinct representations for more general classes of posets. We focus on two: boolean dimension, introduced in the 1980s and revisited in recent research, and local dimension, a very new one. We determine precisely which values of dimension/boolean dimension/local dimension imply that the two other parameters are bounded. This is an extended abstract; see arXiv:1705.09167 for a full version.
The concept of hesitant set was introduced by Hu, which purpose is to unify hesitant fuzzy sets, interval-valued hesitant fuzzy sets, shadowed sets etc. This paper discusses the construction of ...decision evaluation functions and three-way decisions based on hesitant sets over three-way decision spaces. First, this paper presents the construction methods of decision evaluation functions based on hesitant sets over semi-three-way decision spaces and quasi-three-way decision spaces. Second, this paper presents some transformation methods of decision evaluation functions based on hesitant sets from semi-three-way decision spaces and quasi-three-way decision spaces to three-way decision spaces. Third, this paper presents three-way decisions based on hesitant sets. Numerous examples are given to support this paper’s argument on the existence of semi-(quasi-)decision evaluation functions and significance of the transformation methods.
Due to the successful applications in abundant practical application problems involving fuzzy sets and systems, overlap functions on unit closed interval have attracted continuous attentions of many ...scholars since they were proposed. In particular, recently, the author extended the concept of overlap functions on unit closed interval to the so-called quasi-overlap functions on bounded partially ordered sets. In this paper, we pay attention to the extension constructions of quasi-overlap functions and their derivative concepts on function spaces with bounded partially ordered sets as underlying sets. Specifically, first, based on quasi-overlap functions and their derivative concepts on any bounded partially ordered set, we give the way to construct quasi-overlap functions and their derivative concepts on function space composed of all fuzzy sets with that bounded partially ordered set as the truth values set along with the function space composed of all order-preserving functions from arbitrary sup semilattice to that bounded partially ordered set, respectively. Second, we introduce the concepts of representable quasi-overlap functions and representable derivative concepts of quasi-overlap functions on function spaces and obtain their equivalent characterizations. Third, we discuss some vital properties of representable quasi-overlap functions and representable derivative concepts of quasi-overlap functions on function spaces. Fourth, it should be mentioned that the obtained results cover the cases of quasi-overlap functions and their derivative concepts on function spaces composed of all interval-valued fuzzy sets and type-2 fuzzy sets when the underlying bounded partially ordered set is taken as the corresponding truth values set, respectively.
Recently, Hu proposed the notion of three-way decision spaces based on partially ordered sets with involutive negations by the axiomatic definition. However, involutive negation is so strong that ...imposes restrictions on the use of the theory of three-way decision spaces from theoretical point of view. Therefore, this paper attempts to extend the concept of three-way decision spaces from partially ordered sets with involutive negations to partially ordered sets with negations. At first, we generalize three-way decision spaces and three-way decisions based on general partially ordered sets with negations such that the existing three-way decisions are the specific cases of generalized three-way decision spaces discussed in this paper. And then, we give some new decision evaluation functions in generalized three-way decision spaces (e.g., decision evaluation functions based on fuzzy sets, interval-valued fuzzy sets, fuzzy relations, shadowed sets and hesitant fuzzy sets), which enriched the class of decision evaluation functions. In particular, they provide more choices for decision-makers in realistic decision-making problems. Finally, in order to illustrate the practical applications of the results presented in this paper, we analyse a practical example of an evaluation problem of credit card applicants.
Three-way decisions on three-way decision spaces are based on fuzzy lattices, i.e. complete distributive lattices with involutive negators. However, now some popular structures, such as hesitant ...fuzzy sets and type-2 fuzzy sets, do not constitute fuzzy lattices. It limits applications of the theory of three-way decision spaces. So this paper attempts to generalize measurement on decision conclusion in three-way decision spaces from fuzzy lattices to partially ordered sets. First three-way decision spaces and three-way decisions are discussed based on general partially ordered sets. Then this paper points out that the collection of non-empty subset of 0, 1 and the family of hesitant fuzzy sets are both partially ordered sets. Finally this paper systematically discusses three-way decision spaces and three-way decisions based on hesitant fuzzy sets and interval-valued hesitant fuzzy sets and obtains many useful decision evaluation functions.
Given a partial order Q, its semiorder dimension is the smallest number of semiorders whose intersection is Q. When we look at the class of partial orders of fixed semiorder dimension k, no ...characterization is known, even in the case k=2. In this paper, we give a characterization of the class of interval orders with semiorder dimension two. It follows from our results that partial orders that are interval orders with semiorder dimension two can be recognized efficiently. As our characterization makes use of a certain substructure, we also discuss the possibility of a forbidden suborder characterization. We give a partial answer to this question by listing all forbidden suborders for a special case. We further transfer our characterization result to the class of interval graphs that induce orders with semiorder dimension two.
Abstract
The Dushnik–Miller dimension of a poset
P
is the least
d
for which
P
can be embedded into a product of
d
chains. Lewis and Souza isibility order on the interval of integers
$$N/\kappa , N$$
...N
/
κ
,
N
is bounded above by
$$\kappa (\log \kappa )^{1+o(1)}$$
κ
(
log
κ
)
1
+
o
(
1
)
and below by
$$\Omega ((\log \kappa /\log \log \kappa )^2)$$
Ω
(
(
log
κ
/
log
log
κ
)
2
)
. We improve the upper bound to
$$O((\log \kappa )^3/(\log \log \kappa )^2).$$
O
(
(
log
κ
)
3
/
(
log
log
κ
)
2
)
.
We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.
PDF
