Search

Let G be a graph with n vertices and m edges. One of several hierarchies towards the stability number of G is the exact subgraph hierarchy (ESH). On the first level it computes the Lovász theta function ϑ (G) as semidefinite program (SDP) with a matrix variable of order n + 1 and n + m + 1 constraints. On the k th level it adds all exact subgraph constraints (ESC) for subgraphs of order k to the SDP. An ESC ensures that the submatrix of the matrix variable corresponding to the subgraph is in the correct polytope. By including only some ESCs into the SDP the ESH can be exploited computationally. In this paper we introduce a variant of the ESH that computes ϑ (G) through an SDP with a matrix variable of order n and m + 1 constraints. We show that it makes sense to include the ESCs into this SDP and introduce the compressed ESH (CESH) analogously to the ESH. Computationally the CESH seems favorable as the SDP is smaller. However, we prove that the bounds based on the ESH are always at least as good as those of the CESH. In computational experiments sometimes they are significantly better. We also introduce scaled ESCs (SESCs), which are a more natural way to include exactness constraints into the smaller SDP and we prove that including an SESC is equivalent to including an ESC for every subgraph. • A new hierarchy for the stable set problem. • Theoretical investigation with respect to the exact subgraph hierarchy. • Computational comparison with the exact subgraph hierarchy. [ABSTRACT FROM AUTHOR]

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Z n , assuming that P is a polyhedron, defined by systems A x ≤ b or A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form s O (n) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For s = o (log n) , this bound outperforms the state-of-the-art ILP feasibility complexity bound (log n) O (n) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For s = ϕ o (log n) , where ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound ϕ O (n log n) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830, 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545, 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems. [ABSTRACT FROM AUTHOR]

A balanced transferable utility game (N, v) has a stable core if its core is externally stable, that is, if each imputation that is not in the core is dominated by some core element. Given two payoff allocations x and y, we say that xoutvotesy via some coalition S of a feasible set if x dominates y via S and x allocates at least v(T) to any feasible T that is not contained in S. It turns out that outvoting is transitive and the set M of maximal elements with respect to outvoting coincides with the core if and only if the game has a stable core. By applying the duality theorem of linear programming twice, it is shown that M coincides with the core if and only if a certain nested balancedness condition holds. Thus, it can be checked in finitely many steps whether a balanced game has a stable core. We say that the game has a super-stable core if each payoff vector that allocates less than v(S) to some coalition S is dominated by some core element and prove that core super-stability is equivalent to vital extendability, requiring that each vital coalition is extendable. [ABSTRACT FROM AUTHOR]

Minimal balanced collections are a generalization of partitions of a finite set of n elements and have important applications in cooperative game theory and discrete mathematics. However, their number is not known beyond n = 4. In this paper we investigate the problem of generating minimal balanced collections and implement the Peleg algorithm, permitting to generate all minimal balanced collections till n = 7. Secondly, we provide practical algorithms to check many properties of coalitions and games, based on minimal balanced collections, in a way which is faster than linear programming-based methods. In particular, we construct an algorithm to check if the core of a cooperative game is a stable set in the sense of von Neumann and Morgenstern. The algorithm implements a theorem according to which the core is a stable set if and only if a certain nested balancedness condition is valid. The second level of this condition requires generalizing the notion of balanced collection to balanced sets. [ABSTRACT FROM AUTHOR]

Given a graph G , a near-bipartition of G is a partition of V (G) into S and F , where S is a stable set, and F induces a forest. Given a graph G and a vertex set P inducing a P 4 in G , a vertex v is said partner of P if v ∈ V (G) ∖ P and G [ P ∪ { v } ] has at least two P 4 's. A graph G is P 4 -tidy if any P 4 in G has at most one partner. In this paper, we study the property of having a near-bipartition on P 4 -tidy graphs. We also consider a variant of that property that requires F being a tree. While the problem of determining whether an input graph has a near-bipartition is NP-complete even for graphs with maximum degree four, perfect graphs, graphs with diameter three, line graphs, and planar graphs, we show that the class of near-bipartite P 4 -tidy graphs admit finite forbidden induced subgraph characterization. In addition, we also present a characterization for P 4 -tidy graphs admitting a partition of its vertex set into a stable set and a tree. [ABSTRACT FROM AUTHOR]

In this paper, we study local stable/unstable sets of sensitive homeomorphisms with the shadowing property defined on compact metric spaces. We prove that local stable/unstable sets always contain a compact and perfect subset of the space. As a corollary, we generalize results in [Artigue et al. Beyond topological hyperbolicity: the Lshadowing property, J. Differ. Equ. 268(6) (2020), pp. 3057–3080.] and [Carvalho and Cordeiro, Positively N-expansive homeomorphisms and the L-shadowing property, J. Dyn. Differ. Equ. 31(2) (2019), pp. 1005–1016.] proving that positively countably expansive homeomorphisms defined on compact metric spaces satisfying either transitivity and the shadowing property, or the L-shadowing property, can only be defined in countable spaces. [ABSTRACT FROM AUTHOR]

Two independent approaches have been used to analyze choices. A prominent notion is rationalizability: individuals choose maximizing binary relations. An alternative is to analyze choices in terms of standards of behavior with the notion of von Neumann–Morgenstern (vNM)‐stability. We introduce a new concept (r‐ $r \mbox{-} $stability) that in turn extends the notion of stability and rationality. Our main result establishes that every rationalizable choice function is r‐ $r \mbox{-} $stable and every vNM‐stable choice has an r‐ $r \mbox{-} $stable selection. An appealing property of r‐ $r \mbox{-} $stability is that well‐known solution concepts (top cycle, uncovered set, ...) are r‐ $r \mbox{-} $stable, while they are neither rationalizable nor vNM‐stable. [ABSTRACT FROM AUTHOR]

This study analyzes von Neumann-Morgenstern stable sets in an assignment game. Núñez and Rafels (2013) have shown that the union of the extended cores of all μ -compatible subgames is a stable set. Typically, the set of all μ -compatible subgames includes many elements, most of which are inessential for obtaining the stable set. We provide an algorithm to find a set of μ -compatible subgames for obtaining the stable set when the valuation matrix is positive. Moreover, this algorithm finds the minimum set of μ -compatible subgames for obtaining the stable set when each column and row in the valuation matrix is constituted from different positive numbers. Our simulation result reveals that the average size of the minimum set of μ -compatible subgames for obtaining the stable set is significantly lower than that of the set of all μ -compatible subgames. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generalization of topological R-module using β-open sets called irresolute β-topological algebra (group, ring and module). We show that the center of an irresolute β-hausdorff ring is β-closed and if N is Q-submodule of an irresolute β-topological R-module M, then βCl(N)M is also βCl(Q)R-submodule where Q,N are subsets of R,M respectively. Several other properties of them are investigated. [ABSTRACT FROM AUTHOR]

The inherent characteristics of real-world data is uncertainty. If data is generated in valid experiments or collected standard, probability theory or fuzzy theory is a powerful tool for analysis it in the uncertainty conditions. But data is not always reliable; especially when it is not possible to perform multiple tests or reliable data collection. In this context, referring to the beliefs of experts in the field in question is an alternative approach and uncertainty theory is a tool by which the beliefs of experts can be mathematically incorporated into the problem-solving structure. A stable set has a wide range of applications in many fields, while in most cases its problems are without reliable data. In this paper, we investigate the finding of stable weighted sets with uncertain weights. These weights have an uncertain distribution based on the degree of belief of the field expert. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we come to an integer linear programming model with definite coefficients. The second method is based on the concept of uncertain expected value. Finally, a numerical example for these two methods is presented.

In an information graph situation, a finite set of agents and a source are the set of nodes of an undirected graph with the property that two adjacent nodes can share information at no cost. The source has some information (or technology), and agents in the same component as the source can reach this information for free. In other components, some agent must pay a unitary cost to obtain the information. We prove that the core of the derived information graph game is a von Neumann-Morgenstern stable set if and only if the information graph is cycle-complete, or equivalently if the game is concave. Otherwise, whether there always exists a stable set is an open question. If the information graph consists of a ring that contains the source, a stable set always exists and it is the core of a related situation where one edge has been deleted. [ABSTRACT FROM AUTHOR]

Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this problem has several applications in real life, there is need to find efficient algorithms to solve this problem. Recently, Gaar and Rendl enhanced semidefinite programming approaches to tighten the upper bound given by the Lovász theta function. This is done by carefully selecting some so-called exact subgraph constraints (ESC) and adding them to the semidefinite program of computing the Lovász theta function. First, we provide two new relaxations that allow to compute the bounds faster without substantial loss of the quality of the bounds. One of these two relaxations is based on including violated facets of the polytope representing the ESCs, the other one adds separating hyperplanes for that polytope. Furthermore, we implement a branch and bound (B&B) algorithm using these tightened relaxations in our bounding routine. We compare the efficiency of our B&B algorithm using the different upper bounds. It turns out that already the bounds of Gaar and Rendl drastically reduce the number of nodes to be explored in the B&B tree as compared to the Lovász theta bound. However, this comes with a high computational cost. Our new relaxations improve the run time of the overall B&B algorithm, while keeping the number of nodes in the B&B tree small. [ABSTRACT FROM AUTHOR]

The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature. [ABSTRACT FROM AUTHOR]

Let G be a graph G whose largest independent set has size m. A permutation π of {1,...,m} is an independent set permutation of G if aπ(1)(G)≤aπ(2)(G)≤⋯≤aπ(m)(G), where ak(G) is the number of independent sets of size k in G. In 1987 Alavi, Malde, Schwenk, and Erdős proved that every permutation of {1,...,m} is an independent set permutation of some graph with α(G)=m, that is, with the largest independent set having size m. They raised the question of determining, for each m, the smallest number f(m) such that every permutation of {1,...,m} is an independent set permutation of some graph with α(G)=m and with at most f(m) vertices, and they gave an upper bound on f(m) of roughly m2m. Here we settle the question, determining f(m)=mm, and make progress on a related question, that of determining the smallest order such that every permutation of {1,...,m} is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on {1,...,m} can be realized by the independent set sequence of some graph with α(G)=m and with at most mm+2 vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of {1,...,m} is a matching permutation of some graph with the largest matching having size m, putting an upper bound of 2m−1 on the number of matching permutations of {1,...,m}. Confirming their speculation that this upper bound is not tight, we improve it to O(2m∕m). [ABSTRACT FROM AUTHOR]

To attain the general form of stable coalition structure, this paper addressed the problem of retailers’ coalition stability in a two-stage supply chain consisting of one supplier and multiple retailers. A profit gain function was established via introducing market gain coefficient and coalition cost coefficient for different coalition structures. Based on the function, the profit of each retailer in all kinds of coalition structures was analysed, and the general feature of a stable coalition structure was attained by the largest consistent set method and the stable set method. Furthermore, some insights were obtained. For example, stable coalition structures are equidistributed or approximate equidistributed; with supplier’s cost increasing, the size of the retailers’ coalition increases. Finally, the above conclusions are verified by numerical simulation. The results of this paper provide a reference for retailers’ coalition in a supply chain, such as automobile or Information Technology supply chain. [ABSTRACT FROM PUBLISHER]

For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis (1991) introduced an extended formulation for the odd cycle inequalities of the stable set polytope, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there can exist exponentially many odd cycles in given graphs in general. We present another extended formulation for the odd cycle polytope that uses less variables and inequalities than Yannakakis' formulation. Moreover, we compare the running time of both formulations as relaxations of the maximum stable set problem in a computational study. [ABSTRACT FROM AUTHOR]

We show that the core of a generalized assignment problem satisfies two types of stability properties. First, the core is the unique stable set defined using the weak domination relation when outcomes are restricted to individually rational and pairwise feasible ones. Second, the core is the unique stable set with respect to a sequential domination relation that is defined by a sequence of weak domination relations that satisfy outsider independence. An equivalent way of stating this result is that the core satisfies the property commonly stated as the existence of a path to stability. These results add to the importance of the core in an assignment problem where agents' preferences may not be quasilinear. [ABSTRACT FROM AUTHOR]

In this paper, we review some results of the solution of generalized stable sets introduced by Van Deemen (1991) as a variant of stable sets for abstract decision problems. This solution will be investigated and reviewed for the more general case of irreflexive but not necessarily asymmetric or complete dominance relations. It is proven that the fundamental properties of this solution are preserved also for this kind of dominance relations. Two main shortcomings of the solution of generalized stable sets are firstly that it may contain Pareto-suboptimal alternatives when the dominance relation is derived from pairwise majority comparison, and secondly that it may fail to discriminate among the alternatives under consideration when the dominance relation is a Hamilton cycle, i.e. a cycle that includes all alternatives. A refinement of generalized stable sets is proposed in order to address these two shortcomings. This refinement is called the solution of undisturbed generalized stable sets. It will be shown that undisturbed generalized stable sets are Pareto optimal and have discriminating power in the case of Hamilton cycles. In addition, and perhaps more important, we prove that this refinement is always a subset of the solutions of the uncovered set and of the unsurpassed set. This implies that undisturbed generalized stable set also may be seen as a refinement of both the uncovered set and the unsurpassed set. • We applied the generalized stable sets to irreflexive dominance relations. • This refinement is proposed to address two shortcomings of generalized stable sets. • The proposal improves the Copeland winner set, the uncovered set, the unsurpassed set. [ABSTRACT FROM AUTHOR]

We study the topological entropy of stable sets for countable discrete infinite bi-orderable amenable group actions. It is shown that in any positive entropy system, there is a measure-theoretically "large" set such that the topological entropy of stable set of any point from the set is no less than the measure-theoretic entropy of the system, moreover the closure of the stable set of any point from the set contains a weak mixing set. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is monopolar if V can be partitioned into a stable set and a set inducing the union of vertex-disjoint cliques. Motivated by an application of the clique partitioning problem on monopolar graphs to the cosmetic manufacturing, we study the complexity of computing classical graph parameters on the class of monopolar graphs. We show that computing the clique partitioning, stability and chromatic numbers of monopolar graphs is NP -hard. Conversely, we prove that every monopolar graph has a polynomial number of maximal cliques thus obtaining that a maximum-weight clique can be found in polynomial time on monopolar graphs. [ABSTRACT FROM AUTHOR]

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in O (| V | (| V | log | V | + | E |)) time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in O (| V | 2) time. In two companion papers we showed that the MWSS problem can be solved in O (| E | log | V |) time in claw-free graphs with α (G) ≤ 3 and in O (| V | | E |) time in {claw, net}-free graphs with α (G) ≥ 4 . These results prove that the MWSS problem in a claw-free graph can be solved in O (| V | 2 log | V |) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs. [ABSTRACT FROM AUTHOR]

We investigate second-order generalized Beverton{Holt difference equations of the form... where f is a function nondecreasing in both arguments, the parameter a is a positive constant, and the initial conditions x-1 and x0 are arbitrary nonnegative numbers in the domain of f. We will discuss several interesting examples of such equations and present some general theory. In particular, we will investigate the local and global dynamics in the event f is a certain type of linear or quadratic polynomial, and we explore the existence problem of period-two solutions. [ABSTRACT FROM AUTHOR]

A fundamental result from Boolean modal logic states that a first-order definable class of Kripke frames defines a logic that is validated by all of its canonical frames. We generalise this to the level of non-distributive logics that have a relational semantics provided by structures based on polarities. Such structures have associated complete lattices of stable subsets, and these have been used to construct canonical extensions of lattice-based algebras. We study classes of structures that are closed under ultraproducts and whose stable set lattices have additional operators that are first-order definable in the underlying structure. We show that such classes generate varieties of algebras that are closed under canonical extensions. The proof makes use of a relationship between canonical extensions and MacNeille completions. [ABSTRACT FROM AUTHOR]

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach. [ABSTRACT FROM AUTHOR]

We investigate the global behavior of two difference equations with exponential nonlinearities ... where the parameters b; c are positive real numbers and p ... (0; 1) and ... where the parameters a; b are positive numbers. The the initial conditions x-1; x0 are arbitrary nonnegative numbers. The two equations are well known mathematical models in biology which behavior was studied by other authors and resulted in partial global dynamics behavior. In this paper, we complete the results of other authors and give the global dynamics of both equations. In order to obtain our results we will prove several results on global attractivity and boundedness and unboundedness for general second order difference equations ... which are of interest on their own. [ABSTRACT FROM AUTHOR]

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a vertex that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins, and consequently obtain a polynomial time recognition algorithm for the class. In this paper we further use this decomposition theorem to obtain polynomial time algorithms for maximum weight clique, maximum weight stable set and coloring problems. We also show that for a graph G in the class, if its maximum clique size is ω , then its chromatic number is bounded by max ⁡ { ω , 3 } , and that the class is 3-clique-colorable. [ABSTRACT FROM AUTHOR]

As usual, Pn (n≥1) denotes the path on n vertices, and Cn (n≥3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H‐free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P7,C4,C5)‐free graphs; in fact, we give a complete structural characterization of (P7,C4,C5)‐free graphs that do not admit a clique‐cutset. We use this decomposition theorem to show that the class of (P7,C4,C5)‐free graphs is χ‐bounded by a linear function (more precisely, every (P7,C4,C5)‐free graph G satisfies χ(G)≤3/2ω(G)). We also use the decomposition theorem to construct an O(n3) algorithm for the minimum coloring problem, an O(n2m) algorithm for the maximum weight stable set problem, and an O(n3) algorithm for the maximum weight clique problem for this class, where n denotes the number of vertices and m the number of edges of the input graph. [ABSTRACT FROM AUTHOR]

We define two families of graphs and prove the strong and the weak path partition conjectures for subfamilies of these graphs. [ABSTRACT FROM AUTHOR]

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (eg, the class of perfect graphs and the class of even‐hole‐free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. Furthermore, we obtain polynomial χ‐bounding functions for these classes. [ABSTRACT FROM AUTHOR]

Abstract Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph G to be sum-perfect if for every induced subgraph H of G , α (H) + ω (H) ≥ | V (H) |. (Here α and ω denote the stability number and clique number, respectively.) We give a set of 27 graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of the graphs in the set as an induced subgraph. [ABSTRACT FROM AUTHOR]

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.

Berge’s Lemma says that for each independent set S and maximum independent set X , there is a matching from S − X into X − S , namely, a function of S − X into X − S such that ( s , f ( s ) ) is an edge for each s ∈ S − X . Levit and Mandrescu prove A Set and Collection Lemma. It is a strengthening of Berge’s Lemma, by which one can obtain a matching M : S − ⋂ Γ → ⋃ Γ − S , where S is an independent set and Γ is a collection of maximum independent sets. Jarden, Levit and Mandrescu invoke new inequalities from A Set and Collection Lemma and yield a new characterization of König–Egerváry graphs. In the current paper, we study Berge systems (collections of vertex sets, where the conclusion of Berge’s Lemma hold). The work is divided into two parts: the general theory of Berge systems and Berge systems associated with groups (or more precisely, in non-commuting graphs). We first show that there exists many Berge systems. The notion of an ideal is central in several branches of mathematics. We define ‘a graph ideal’, which is a natural generalization of ‘an ideal’ in the context of graph theory. We show that every graph ideal carries a Berge system. We prove a sufficient condition for a Berge system to be a multi-matching system (collections where the conclusion of a Set and Collection Lemma holds). We get new inequalities in multi-matching systems. Here, we do a turn about from the general theory of Berge systems into the study of Berge systems in non-commuting graphs. We prove that for every group G , if A and B are maximal abelian subsets of 〈 A , B 〉 G and | A | ≤ | B | , then there is a non-commutative matching of A − B into B − A . It means that every non-commuting graph carries a Berge system. Moreover, we apply the sufficient condition to get a multi-matching system in the context of non-commuting graphs and invoke new inequalities in group theory. Surprisingly, the new results concerning groups, do not hold for rings. [ABSTRACT FROM AUTHOR]

Coalitional game deals with the situation that involves cooperations among the players. When the payoffs are characterized by uncertain variables, classical coalitional game evolves to uncertain coalitional game. Some solutions of uncertain coalitional game have been proposed such as core and Shapley value. This paper goes further to present another concept of solution—stable set for uncertain coalitional game, and shows that the core is the subset of the stable set in an uncertain coalitional game. Finally, an electricity suppliers cooperation problem is analyzed by the stable set in uncertain coalitional game. [ABSTRACT FROM AUTHOR]

The present paper attempts to bridge the gap between the cooperative and the non-cooperative approach employed to examine the size of stable coalitions, formed to address global environmental problems. We do so by endowing countries with foresightedness, that is, by endogenizing the reaction of the coalition’s members to a deviation by one member. We assume that when a country contemplates withdrawing or joining an agreement, it takes into account the reactions of other countries ignited by its own actions. We identify conditions under which there always exists a unique set of farsighted stable IEAs. The new farsighted IEAs can be much larger than those some of the previous models supported but are not always Pareto efficient. [ABSTRACT FROM AUTHOR]

I develop a model of collaboration between tournament participants in which agents collaborate in pairs, and an endogenous structure of collaboration is represented by a weighted network. The agents are forward‐looking and capable of coordination; they value collaboration with others and higher tournament rankings. I use von Neumann–Morgenstern stable sets as a solution. I find stable networks in which agents collaborate only within exclusive groups. Both an absence of intergroup collaboration and excessive intragroup collaboration lead to inefficiency. I provide a necessary and sufficient condition for the stability of efficient outcomes in winner‐takes‐all tournaments. I show that the use of transfers does not repair efficiency. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing resolving sets for a differential game or an optimal control problem based on information on the dynamics of the system, control resources, and boundary conditions. The construction of largest possible sets with such properties (the maximal stable bridge in a differential game or the controllability set in a control problem) is a nontrivial problem due to their complicated geometry; in particular, the boundaries may be nonconvex and nonsmooth. In practical engineering tasks, which permit some tolerance and deviations, it is often admissible to construct a resolving set that is not maximal. The constructed set may possess certain characteristics that would make the formation of control actions easier. For example, the set may have convex sections or a smooth boundary. In this context, we study the property of stability (weak invariance) for one class of sets in the space of positions of a differential game. Using the notion of stability defect of a set introduced by V.N. Ushakov, we derive a criterion of weak invariance with respect to a conflict control dynamic system for cylindrical sets. In a particular case of a linear control system, we obtain easily verified sufficient conditions of weak invariance for cylindrical sets with ellipsoidal sections. The proof of the conditions is based on constructions and facts of subdifferential calculation. An illustrating example is given. [ABSTRACT FROM AUTHOR]

In this paper we present results on the existence of invariant curves for planar maps that are monotone with respect to either the south-east or north-east ordering. Some of these curves are the stable or unstable manifolds of hyperbolic fixed points (saddle points) or non-hyperbolic fixed points, and are also the boundary of basins of attraction of such points. [ABSTRACT FROM AUTHOR]

Let D be a digraph. A stable set S of D and a path partition P of D are orthogonal if every path P ∈ P contains exactly one vertex of S. In 1982, Berge defined the class of α -diperfect digraphs. A digraph D is α-diperfect if for every maximum stable set S of D there is a path partition P of D orthogonal to S and this property holds for every induced subdigraph of D. An anti-directed odd cycle is an orientation of an odd cycle (x 0 , ... , x 2 k , x 0) with k ≥ 2 in which each vertex x 0 , x 1 , x 2 , x 3 , x 5 , x 7 , ... , x 2 k − 1 is either a source or a sink. Berge conjectured that a digraph D is α -diperfect if and only if D does not contain an anti-directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not α -diperfect. [ABSTRACT FROM AUTHOR]