Search

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure - a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is - an element of the board can only be claimed if all the smaller elements in the poset are already claimed. We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

In this dissertation, we study poset associahedra and the combinatorics surrounding them. We provide a simple realization of poset associahedra and affine poset cyclohedra. Furthermore, we show that the f-vector of a poset associahedron depends only on the comparability graph of the poset. We investigate a connection between certain poset associahedra and the theory of stack-sorting. Finally, we show that when the poset is a rooted tree, the 1-skeleton of the poset associahedronorients to a lattice. These lattices generalize both the weak Bruhat order and the Tamari lattice.

2023 Acuerdos transformativos CRUE, In this paper we propose a way to triangulate a pointed order polytope. Pointed order polytopes are a generalization of order polytopes that include some important groups of polytopes appearing when bipolar scales arise in Decision Making or Game Theory, as the set of bi-capacities or the set of normalized bi-games, even for cases with restricted cooperation. Triangulating polytopes is an important and difficult problem that allows an elegant way to generate uniform random points in the polytope. For order polytopes, there exists a nice result that allows a way to triangulate this family of polytopes based on generating linear extensions. In this paper we prove a similar result for pointed order polytopes. The results in this paper allow to derive a procedure to generate random points inside a pointed order polytope that depends only on the structure of the subjacent poset, a problem that usually is simpler to tackle. In particular, this could be applied to generate bi-capacities or bi-capacities belonging to some subfamilies (e.g. k-symmetric, k-interactive, ...) in a random way., Depto. de Estadística e Investigación Operativa, Fac. de Ciencias Matemáticas, Instituto de Matemática Interdisciplinar (IMI), TRUE, pub

An Alexandroff space is a topological space in which every intersection of open sets isopen. There is one to one correspondence between AlexandroffT0-spaces andpartially ordered sets(posets). We investigate AlexandroffT0-topologies on finite quandles. We prove that there is anon-trivial topology on a finite quandle making right multiplications continuous functions if andonly if the quandle has more than one orbit. Furthermore, we show that right continuous posets onquandles withnorbits aren-partite. We also find, for the even dihedral quandles, the number ofall possible topologies making the right multiplications continuous. Some explicit computations forquandles of cardinality up tofiveare given

In this paper we present a new method for deriving a random linear extension of a poset. This new strategy combines Probability with Combinatorics and obtains a procedure where each minimal element of a sequence of subposets is selected via a probability distribution. The method consists in obtaining a weight vector on the elements of P, so that an element is selected with a probability proportional to its weight. From some properties on the graph of adjacent linear extensions, it is shown that the probability distribution can be obtained by solving a linear system. The number of equations involved in this system relies on the number of what we have called positioned antichains, that allows a reduced number of equations. Finally, we give some examples of the applicability of the algorithm. This procedure cannot be applied to every poset, but it is exact when it can be used. Moreover, the method is quick and easy to implement. Besides, it allows a simple way to derive the number of linear extensions of a given poset., Ministerio de Economía y Competitividad (MINECO), Depto. de Estadística e Investigación Operativa, Fac. de Ciencias Matemáticas, TRUE, pub

We introduce $\delta$-cliffs, a generalization of permutations and increasing trees depending on a range map $\delta$. We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe sufficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps $\delta$, have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak Bruhat order of permutations, we construct algebras whose products form intervals of the lattices of $\delta$-cliff. We provide necessary and sufficient conditions on $\delta$ to have associative, finitely presented, or free algebras. We end this work by using the previous Fuss-Catalan posets to define quotients of our algebras of $\delta$-cliffs. In particular, one is a generalization of the Loday-Ronco algebra.Mathematics Subject Classifications: 05E99, 06A07, 06A11, 16T30

We introduce \(\delta\)-cliffs, a generalization of permutations and increasing trees depending on a range map \(\delta\). We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe sufficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps \(\delta\), have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak Bruhat order of permutations, we construct algebras whose products form intervals of the lattices of \(\delta\)-cliff. We provide necessary and sufficient conditions on \(\delta\) to have associative, finitely presented, or free algebras. We end this work by using the previous Fuss-Catalan posets to define quotients of our algebras of \(\delta\)-cliffs. In particular, one is a generalization of the Loday-Ronco algebra.Mathematics Subject Classifications: 05E99, 06A07, 06A11, 16T30

Let be a finite poset (partially ordered set) with cardinality . A linear extension of is an order-preserving bijection : , that is, if in then . We define the poset probability as the proportion of linear extensions where . We are primarily interested in for incomparable elements . The probability has significance in areas such as information theory. Let

Let be a finite poset (partially ordered set) with cardinality . A linear extension of is an order-preserving bijection : , that is, if in then . We define the poset probability as the proportion of linear extensions where . We are primarily interested in for incomparable elements . The probability has significance in areas such as information theory. Let

The official Italian well-being measuring system (“Equitable and Sustainable Well-being—BES”) is probably the worldwide most advanced attempt to pursue the beyond GDP perspective effectively. In it, well-being is described in terms of 12 domains and a complex multi-indicator system of around 130 indicators, drawn mainly from Istat (official Italian statistical bureau) surveys and administrative archives. In order to get a more synthetic view of well-being, in the last four BES reports Istat employed aggregative procedures providing composite indicators for each well-being domain. The aggregative road to synthesis is however problematic, when complex and non-highly correlated indicator systems are to be summarized, mainly due to its compensative nature and interpretational difficulties. As a valuable alternative, in this paper we adopt a non-aggregative approach to synthesis, based on Partially Ordered Set Theory (Poset Theory) and show how it can be used to provide more “complexity-preserving”insights into well-being. In particular, we describe each well-being domain as a partially ordered set and compute synthetic indicators for well-being rankings at regional level for year 2017, getting more robust and interpretable results than with mainstream aggregative procedures.

In this paper, we address the measurement of vulnerability at municipality level, by using novel non-aggregative tools for the construction of synthetic indicators and for the extraction of rankings, based on the theory of partially ordered sets. We compare the results of the non-aggregative procedure to those provided by the Italian National Institute of Statistics, through the Index of Social and Material Vulnerability (applied to 2011 census data) and show that, although the overall pictures rendered by the two approaches are very similar, they are not equivalent, some local areas being resolved and some municipalities being ranked differently. The synthetic vulnerability scores are complemented with a measure of the degree of diversity of the vulnerability patterns, to give a more faithful picture of the complexity of the phenomenon and provide policy-makers with a more realistic view on it.

In this paper, we introduce the concept of a poset dismantlable by doubly irreducibles. We also introduce the operations, `1-sum' and `2-sum' of posets. Using these operations, we obtain the structure theorem for posets dismantlable by doubly irreducibles, which generalizes the structure theorem for dismantlable lattices.

To an extended generalized permutohedron we associate the weighted integer points enumerator, whose principal specialization is the f-polynomial. In the case of poset cones it refines Gessel's P-partitions enumerator. We show that this enumerator is a quasisymmetric function obtained by universal morphism from the Hopf algebra of posets.

Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomassé and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 8d with a direct and elementary argument, and show that this bound is tight up to a constant factor. Specifically, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset.

In recent years, sustainable development has become one of the main issues of scientific and institutional debate. The literature on this concept is wide and often presents conflicting positions. This leads to considering sustainable development as a contested concept. The growing interest and importance of this topic has also led to an increasing focus on the aspect of its measurement. Dealing with the measurement of complex phenomena, like sustainable development, means dealing with synthesis. The traditional and dominant approach to the synthesis of multi-indicator systems of cardinal variables is the use of the aggregative-compensative approach. Despite its success, this approach presents a series of critical issues. In this paper, we propose a method of synthesizing multi-indicator systems over time based on the Partial Order Theory. Applying and comparing the method we proposed and an aggregative method, the Adjusted Mazziotta–Pareto Index, to one of the 15 sustainable development goals, we highlight the strengths of the new methodological proposal.

The propensity for sustainability actions and awareness among population might be driven by ad hoc policies. For example, in the transportation framework, the bike is (re)gaining popularity as a mean of transportation both convenient and environmental-prone,and consequently more and more cities around the world are developing bike-sharing systems in urban areas to let their citizens be more ‘green’. Satisfaction for bike-sharing systems could be influenced in general by how the service is managed and by users’ attitudes towards sustainability:if users’ participation in sustainability is high, then the level of satisfaction will increase and the service will result more successful. In this paper we analyze the connection between propensity and orientation towards sustainability and satisfaction for a particular bike-sharing system via Partially Ordered Sets based methodology.

Partially ordered sets (posets) are fundamental combinatorial objects with important applications in computer science. Perhaps the most natural algorithmic task, given a size-n poset, is to compute its number of linear extensions. In 1991 Brightwell and Winkler showed this problem to be #P-hard. In spite of extensive research, the fastest known algorithm is still the straightforward O(n 2ⁿ)-time dynamic programming (an adaptation of the Bellman-Held-Karp algorithm for the TSP). Very recently, Dittmer and Pak showed that the problem remains #P-hard for two-dimensional posets, and no algorithm was known to break the 2ⁿ-barrier even in this special case. The question of whether the two-dimensional problem is easier than the general case was raised decades ago by Möhring, Felsner and Wernisch, and others. In this paper we show that the number of linear extensions of a two-dimensional poset can be computed in time O(1.8286ⁿ). The related jump number problem asks for a linear extension of a poset, minimizing the number of neighboring incomparable pairs. The problem has applications in scheduling, and has been widely studied. In 1981 Pulleyblank showed it to be NP-complete. We show that the jump number problem can be solved (in arbitrary posets) in time O(1.824ⁿ). This improves (slightly) the previous best bound of Kratsch and Kratsch.

Measuring health status is becoming a more and more relevant task, especially in relation to ageing societies. In this contribution, we first propose the use of a methodology based on the theory of Ordered Sets that allows to build synthetic indicators out of a set of ordinal variables, respecting the ordinal nature of the variables included. Secondly, using survey data, we calculate two synthetic indicators to evaluate self-rated health status of the elderly population living in Italy.

We find necessary and separate sufficient conditions for the difference between two labeled partially ordered set's (poset) partition generating functions to be positive in the fundamental basis. We define the notion of a jump sequence for a poset and show how different conditions on the jump sequences of two posets are necessary for those posets to have an order relation in the fundamental basis. Our sufficient conditions are of two types. First, we show how manipulating a poset's Hasse diagram produces a poset that is greater according to the fundamental basis. Secondly, we also provide tools to explain posets that are constructed by combining other posets in certain ways through the so-called Ur-operation. Finally, we are able to provide both necessary and sufficient conditions for positivity among posets of Greene shape (k,1) and among a subclass of caterpillar posets, and a complete (and graphically pleasing) representation of the order relations between posets of the former type.

We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.

We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12.

A clutter is a family of mutually incomparable sets. The set of circuits of a matroid, its set of bases, and its set of hyperplanes are examples of clutters arising from matroids. In this paper we address the question of determining which are the matroidal clutters that best approximate an arbitrary clutter ¿. For this, we first define two orders under which to compare clutters, which give a total of four possibilities for approximating ¿ (i.e., above or below with respect to each order); in fact, we actually consider the problem of approximating ¿ with clutters from any collection of clutters S, not necessarily arising from matroids. We show that, under some mild conditions, there is a finite non-empty set of clutters from S that are the closest to ¿ and, moreover, that ¿ is uniquely determined by them, in the sense that it can be recovered using a suitable clutter operation. We then particularize these results to the case where S is a collection of matroidal clutters and give algorithmic procedures to compute these clutters., Peer Reviewed, Postprint (author's final draft)

In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276., SCOPUS: ar.j, info:eu-repo/semantics/published

We prove that every planar poset P of height h has dimension at most 192h + 96. This improves on previous exponential bounds and is best possible up to a constant factor. We complement this result with a construction of planar posets of height h and dimension at least (4/3)h - 2., SCOPUS: ar.j, info:eu-repo/semantics/published

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Kahn and Kim (J. Comput. Sci. 51, 3, 390–399, 1995) have shown that for a finite poset P, the entropy of the incomparability graph of P (normalized by multiplying by the order of P) and the base-2 logarithm of the number of linear extensions of P are within constant factors from each other. The tight constant for the upper bound was recently shown to be 2 by Cardinal et al. (Combinatorica 33, 655–697, 2013). Here, we refine this last result in case P has width 2: we show that the constant can be replaced by 2−ε if one also takes into account the number of connected components of size 2 in the incomparability graph of P. Our result leads to a better upper bound for the number of comparisons in algorithms for the problem of sorting under partial information., SCOPUS: ar.j, info:eu-repo/semantics/published

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Дисертаційну роботу присвячено вивченню квадратичної форми Тітса скінченних частково впорядкованих множин за допомогою методу (min, max)-еквівалентності та застосуванню отриманих результатів у теорії зображень. Основними результатами дисертації є повний опис скінченних частково впорядкованих множин із додатно визначеною формою Тітса та P-критичних частково впорядкованих множин. Доведено, що будь-яка частково впорядкована множина з додатно визначеною формою Тітса порядку n>7 є серійною. Доведено також, що частково впорядкована множина є P-критичною тоді і лише тоді, коли вона (min, max)-еквівалентна деякій критичній множині Клейнера. Вказані результати застосовано в останньому розділі дисертації до вивчення частково впорядкованих множин, категорія ін'єктивних зображень яких має rep-скінченний тип., The disertation is devoted to the study of the quadratic Tits form of finite posets by the method of (min, max)-equivalence, and applications of received results in the theory of representations of posets. The main results of the disertation are classifications the posets with positive Tits form and P-critical posets. It is proved that any poset with positive Tits form of order n>7 is serial, and that a poset is P-critical if and only if it is (min, max)-equivalent to some critical Kleiner set. In the last chapter of the dissertation the indicated results apply to the study of posets with the category of injective representations to be of $rep$-finite type., Диссертационная работа посвящена изучению квадратичной формы Титса конечных частично упорядоченных множеств с помощью метода (min, max)-эквивалентности, а также применению полученных результатов в теории представлений частично упорядоченных множеств. Основным результатом диссертации является полное описание конечных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств. Доказано, что любое частично упорядоченное множество с положительно определенной формой Титса порядка n>7 серийное. Доказано также, что частично упорядоченное множество является P-критическим тогда и только тогда, когда оно (min, max)-эквивалентно некоторому критическому множеству Клейнера. Описания несерийных частично упорядоченных множеств с положительно определенной формой Титса и P-критических частично упорядоченных множеств получены методом «(min, max)-эквивалентности», предложенным научным руководителем. Доказано, что (min, max)-эквивалентность множеств равнозначна min-эквивалентности. Описан алгоритм, с помощью которого можно классифицировать все частично упорядоченные множества, min-эквивалентные фиксированному частично упорядоченному множеству. Показано, что любое частично упорядоченное множество с положительно определенной формой Титса (min, max)-эквивалентно частично упорядоченному множеству без циклов и частично упорядоченному множеству ширины w<3. Указанные результаты применяются в последнем разделе диссертации для изучения частично упорядоченных множеств inj-конечного типа (т. е. таких, категория инъективных представлений которых имеет rep-конечный тип). Доказано, что частично упорядоченное множество с положительно определенной формой Титса имеет inj-конечный тип. Доказано также, что для квазипримитивного частично упорядоченного множества S, не являющегося самодуальным, категории инъективных представлений множеств S и Sop имеют (одновременно) rep-конечный тип тогда и только тогда, когда форма Титса S есть положительно оп

Let P(n) denote the set of all subsets of {1,...,n} and let P(n,p) be the set obtained from P(n) by selecting elements independently at random with probability p. The Boolean lattice is a partially ordered set, or poset, consisting of the elements of P(n), partially ordered by set inclusion. A basic question in extremal poset theory asks the following: Given a poset P, how big is the largest family of sets in the Boolean lattice which does not contain the structure P as a subposet? The following random analogue of this question is also of interest: Given a poset P, how big is the largest family of sets in P(n,p) which does not contain the structure P as a subposet? In this thesis, we present new proofs for a collection of deterministic extremal subposet problems. We also discuss a new technique called the Hypergraph Container Method in depth and use it to prove a random version of De Bonis and Katona's (r+1)-fork-free theorem.

A graph is associated with a poset. If the set of upper bounds of the set of lower bounds of two elements in a poset is the poset itself then we say that these two elements are adjacent in the graph. Properties of this graph are studied. It is shown that if the chromatic number of the associated graph is finite then the clique number is equal to the chromatic number. Some properties of this graph are obtained.

Unlike poset antimatroids, chordal graph shelling antimatroids have received little attention as regard their structures, optimization properties and associated circuits. Here we consider a special case of those antimatroids, namely the split graph shelling antimatroids. We establish a connection between the structure of split graph shelling antimatroids and poset shelling antimatroids. We discuss some applications of this new connection, in particular, we give a simple polynomial time algorithm to find a maximum weight feasible set in split graph shelling antimatroids., SCOPUS: ar.j, info:eu-repo/semantics/published

Let P be a finite poset. By definition, the linear extension polytope of P has as vertices the characteristic vectors of all linear extensions of P. In case P is an antichain, it is the linear ordering polytope. The linear extension polytope appears in combinatorial optimization in the context of scheduling with precedence constraints, see e.g. [A. Schulz, Polytopes and Scheduling, Phd Thesis, TU Berlin, 1996]. It seems also relevant to order theory, being similar in spirit to other constructions such as the linear extension graph, see e.g. [M. Massow, Linear extension graphs and linear extension diameter, PhD thesis, TU Berlin, 2009]. In this work, we relate the combinatorial properties of the poset P to the polyhedral structure of its linear extension polytope. Of particular interest is a natural relaxation of the linear extension polytope. We prove that the relaxation is exact in case P is a width-2 poset, and formulate a conjecture stating exactly when the relaxation is exact., SCOPUS: ar.j, info:eu-repo/semantics/published

In this paper we establish a natural definition of Lusternik-Schnirelmann category for simplicial complexes via the well known notion of contiguity. This simplicial category has the property of being invariant under strong equivalences, and it only depends on the simplicial structure rather than its geometric realization. In a similar way to the classical case, we also develop a notion of simplicial geometric category. We prove that the maximum value over the simplicial homotopy class of a given complex is attained in the core of the complex. Finally, by means of well known relations between simplicial complexes and posets, specific new results for the topological notion of LS-category are obtained in the setting of finite topological spaces.

In this paper we establish a natural definition of Lusternik-Schnirelmann category for simplicial complexes via the well known notion of contiguity. This simplicial category has the property of being invariant under strong equivalences, and it only depends on the simplicial structure rather than its geometric realization. In a similar way to the classical case, we also develop a notion of simplicial geometric category. We prove that the maximum value over the simplicial homotopy class of a given complex is attained in the core of the complex. Finally, by means of well known relations between simplicial complexes and posets, specific new results for the topological notion of LS-category are obtained in the setting of finite topological spaces.

Consider $Spec(Z[x])$, the set of prime ideals of $Z[x]$ as a partially ordered set under inclusion. By removing the zero ideal, we denote $G_{Z}=Spec(Z[x])\{0}$ and view it as an infinite bipartite graph with the prime ideals as the vertices and the inclusion relations as the edges. In this paper, we investigate fundamental graph theoretic properties of $G_{Z}$. In particular, we describe the diameter, circumference, girth, radius, eccentricity, vertex and edge connectivity, and cliques of $G_{Z}$. The complement of $G_{Z}$ is investigated as well.

Consider $Spec(Z[x])$, the set of prime ideals of $Z[x]$ as a partially ordered set under inclusion. By removing the zero ideal, we denote $G_{Z}=Spec(Z[x])\{0}$ and view it as an infinite bipartite graph with the prime ideals as the vertices and the inclusion relations as the edges. In this paper, we investigate fundamental graph theoretic properties of $G_{Z}$. In particular, we describe the diameter, circumference, girth, radius, eccentricity, vertex and edge connectivity, and cliques of $G_{Z}$. The complement of $G_{Z}$ is investigated as well.

In this paper we establish a natural definition of Lusternik-Schnirelmann category for simplicial complexes via the well known notion of contiguity. This simplicial category has the property of being invariant under strong equivalences, and it only depends on the simplicial structure rather than its geometric realization. In a similar way to the classical case, we also develop a notion of simplicial geometric category. We prove that the maximum value over the simplicial homotopy class of a given complex is attained in the core of the complex. Finally, by means of well known relations between simplicial complexes and posets, specific new results for the topological notion of LS-category are obtained in the setting of finite topological spaces.

In this paper we establish a natural definition of Lusternik-Schnirelmann category for simplicial complexes via the well known notion of contiguity. This simplicial category has the property of being invariant under strong equivalences, and it only depends on the simplicial structure rather than its geometric realization. In a similar way to the classical case, we also develop a notion of simplicial geometric category. We prove that the maximum value over the simplicial homotopy class of a given complex is attained in the core of the complex. Finally, by means of well known relations between simplicial complexes and posets, specific new results for the topological notion of LS-category are obtained in the setting of finite topological spaces.

Consider $Spec(Z[x])$, the set of prime ideals of $Z[x]$ as a partially ordered set under inclusion. By removing the zero ideal, we denote $G_{Z}=Spec(Z[x])\{0}$ and view it as an infinite bipartite graph with the prime ideals as the vertices and the inclusion relations as the edges. In this paper, we investigate fundamental graph theoretic properties of $G_{Z}$. In particular, we describe the diameter, circumference, girth, radius, eccentricity, vertex and edge connectivity, and cliques of $G_{Z}$. The complement of $G_{Z}$ is investigated as well.

Consider $Spec(Z[x])$, the set of prime ideals of $Z[x]$ as a partially ordered set under inclusion. By removing the zero ideal, we denote $G_{Z}=Spec(Z[x])\{0}$ and view it as an infinite bipartite graph with the prime ideals as the vertices and the inclusion relations as the edges. In this paper, we investigate fundamental graph theoretic properties of $G_{Z}$. In particular, we describe the diameter, circumference, girth, radius, eccentricity, vertex and edge connectivity, and cliques of $G_{Z}$. The complement of $G_{Z}$ is investigated as well.

In this paper different characterizations of chain-complete posets are given in terms of the fixed points of certain class of functions. Further, an error in the proof of a result of Taskovic is pointed out and a correct proof of the same is given.

We introduce a partial order (sic)(M) on the set BX of formal balls of a fuzzy metric space (X, M, Lambda) in the sense of Kramosil and Michalek, and discuss some of its properties. We also characterize when the poset (BX, (sic)(M)) is a continuous domain by means of a new notion of fuzzy metric completeness introduced here. The well-known theorem of Edalat and Heckmann that a metric space is complete if and only if its poset of formal balls is a continuous domain, is deduced from our characterization