On the solution of w-stable sets

The notion of m-stable sets was introduced in Peris and Subiza (2013) for abstract decision problems. Since it may lack internal stability and fail to discriminate alternatives in cyclic circumstances, we alter this notion, which leads to an alternative solution called w-stable set. Subsequently, we characterize w-stable set and compare it with other solutions in the literature. In addition, we propose a selection procedure to filter out more desirable w-stable sets.     

Score sets ink-partite tournaments

The set S of distinct scores (outdegrees) of the vertices of ak-partite tournamentT(X ₁, X₂, ···, X_k) is called its score set. In this paper, we prove that every set of n non-negative integers, except {0} and {0, 1}, is a score set of some 3-partite tournament. We also prove that every set ofn non-negative integers is a score set of somek-partite tournament for everyn ≥k ≥ 2.     

Cycle factors in strongly connected local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A digraph is 2-connected if the removal of an arbitrary vertex results in a strongly connected digraph.In 2004 and 2005, Li and Shu investigated the structure of strongly connected, but not 2-connected tournaments. Using their structural results they were able to give sufficient conditions for a strongly connected tournament T to have complementary cycles or a k-cycle factor, i.e. a set of k vertex disjoint cycles that span the vertex set of T.Inspired by the articles of Li and Shu we develop in this paper the structure necessary for a strongly connected local tournament to be not cycle complementary. Using this structure, we are able to generalize and transfer various results of Li and Shu to the class of local tournaments.     

On the number of Hamiltonian cycles in tournaments

The main results assert that the minimum number of Hamiltonian bypasses in a strong tournament of order n and the minimum number of Hamiltonian cycles in a 2-connected tournament of order n increase exponentially with n. Furthermore, the number of Hamiltonian cycles in a tournament increases at least exponentially with the minimum outdegree of the tournament. Finally, for each k?1 there are infinitely many tournaments with precisely k Hamiltonian cycles.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

On a generalization of distance sets

A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.     

Constructions of generalized Sidon sets

We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s₁+s₂,s_i∈S; such sets are called Sidon sets if g=2 and generalized Sidon sets if g?3. We extend to generalized Sidon sets the Sidon-set constructions of Singer, Bose, and Ruzsa. We also further optimize Kolountzakis’ idea of interleaving several copies of a Sidon set, extending the improvements of Cilleruelo, Ruzsa and Trujillo, Jia, and Habsieger and Plagne. The resulting constructions yield the largest known generalized Sidon sets in virtually all cases.     

On k-stable functions

We prove that a k-continuous or a k-stable function cannot depend on more than k4^k?1 variables and related facts.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

On stable solutions to the Ordinal Social Choice problem

A concept of k-stable alternatives is introduced. Relationship of classes of k-stable alternatives with dominant, uncovered and weakly stable sets is established. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 3, pp. 318–320. Presented by Academician S.N. Vasil’ev July 24, 2008 The article was translated by the authors.     

Approximation with a fixed number of solutions of some multiobjective maximization problems

We investigate the problem of approximating the Pareto set of some multiobjective optimization problems with a given number of solutions. Our purpose is to exploit general properties that many well studied problems satisfy. We derive existence and constructive approximation results for the biobjective versions of Max Submodular Symmetric Function (and special cases), Max Bisection, and Max Matching and also for the k-objective versions of Max Coverage, Heaviest Subgraph, Max Coloring of interval graphs.     

Classification of seven-point four-distance sets in the plane

A point set X in the plane is called a k-distance set if there are exactly k different distances between two distinct points in X. In this paper, we classify 7-point 4-distance sets and show that there are forty two 7-point 4-distance sets in the plane up to isomorphism, we also give some results about diameter graphs.     

A geometric study of the D-stability problem

The set of D-stable matrices is studied from a differentiable viewpoint, and some general properties of the set are obtained. We study also those 4 by 4 D-stable matrices A which have the property that A+tI is D-stable for all t?0. An example of a 4 by 4 D-stable matrix A without the property is given.     

IPr sets with polynomial weights and Szemerédi's theorem

In the mid 1980s H. Furstenberg and Y. Katznelson defined IPr sets in abelian groups as, roughly, sets consisting of all finite sums of r fixed elements. They obtained, via their powerful IP Szemerédi theorem for commuting groups of measure preserving transformations, many IPr set applications for the density Ramsey theory of abelian groups, including the striking result that, given e>0 and k∈N, there exists some r∈N such that for any IPr set R⊂Z and any E⊂Z with upper density >?, E contains a k-term arithmetic progression having common difference r∈R. Here, polynomial versions of these results are obtained as applications of a recently proved polynomial extension to the Furstenberg-Katznelson IP Szemerédi theorem.     

Solution-free sets for linear equations

We study the maximum size and the structure of sets of natural numbers which contain no solution of one or more linear equations. Thus, for every natural i and k?2, we find the minimum α=α(i,k) such that if the upper density of a strongly k-sum-free set is at least α, then A is contained in a maximal strongly k-sum-free set which is a union of at most i arithmetic progressions. We also determine the maximum density of sets of natural numbers without solutions to the equation x=y+az, where a is a fixed integer.     

The k-Dominating Graph

Given a graph G, the k-dominating graph of G, D _k (G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D _k (G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D _k (G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of D _k (G). In this paper we give conditions that ensure D _k (G) is connected.     

On critical sets of a finite Moore family

Cluster collections obtained within the framework of most cluster structures studied in data analysis and classification are essentially Moore families. In this paper, we propose a simple intuitive necessary and sufficient condition for some subset of objects to be a critical set of a finite Moore family. This condition is based on a new characterization of quasi-closed sets. Moreover, we provide a necessary condition for a subset containing more than k objects (k ≥ 2) to be a critical set of a k-weakly hierarchical Moore family. Finally, as a consequence of this result, we identify critical sets of some k-weakly hierarchical Moore families and thereby generalize a result earlier obtained by Domenach and Leclerc in the particular case of weak hierarchies.