Search

The yolk, an important concept of spatial majority voting theory, is assumed to be unique when the number of individuals is odd. We prove that this claim is true in $$ {\mathbb {R}} ^{2}$$ but false in $$ {\mathbb {R}} ^{3}$$ , and discuss the differing implications of non-uniqueness from the normative and predictive perspectives.

Define the predictability number α(T) of a tournament T to be the largest supermajority threshold \({\frac{1}{2} < \alpha\leq 1}\) for which T could represent the pairwise voting outcomes from some population of voter preference orders. We establish that the predictability number always exists and is rational. Only acyclic tournaments have predictability 1; the Condorcet voting paradox tournament has predictability \({\frac{2}{3}}\); Gilboa has found a tournament on 54 alternatives (i.e. vertices) that has predictability less than \({\frac{2}{3}}\) , and has asked whether a smaller such tournament exists. We exhibit an 8-vertex tournament that has predictability \({\frac{13}{20}}\) , and prove that it is the smallest tournament with predictability < \({\frac{2}{3}}\) . Our methodology is to formulate the problem as a finite set of two-person zero-sum games, employ the minimax duality and linear programming basic solution theorems, and solve using rational arithmetic.

Fast algorithms can be created for many graph problems when instances are confined to classes of graphs that are recursively constructed. This article first describes some basic conceptual notions regarding the design of such fast algorithms, and then the coverage proceeds through several recursive graph classes. Specific classes include trees, series-parallel graphs, k -terminal graphs, treewidth- k graphs, k -trees, partial k -trees, k -jackknife graphs, pathwidth- k graphs, bandwidth- k graphs, cutwidth- k graphs, branchwidth- k graphs, Halin graphs, cographs, cliquewidth- k graphs, k -NLC graphs, k -HB graphs, and rankwidth- k graphs. The definition of each class is provided. Typical algorithms are applied to solve problems on instances of most classes. Relationships between the classes are also discussed.

Given a class Γ of curves in [0, 1]2, we ask: in a cloud of n uniform random points, how many points can lie on some curve γ ∈ Γ? Classes studied here include curves of length less than or equal to L, Lipschitz graphs, monotone graphs, twice-differentiable curves, and graphs of smooth functions with m-bounded derivatives. We find, for example, that there are twice-differentiable curves containing as many as O P (n 1/3) uniform random points, but not essentially more than this. More generally, we consider point clouds in higher-dimensional cubes [0, 1] d and regular hypersurfaces of specified codimension, finding, for example, that twice-differentiable k-dimensional hypersurfaces in R d may contain as many as O P (n k/(2d-k)) uniform random points. We also consider other notions of ‘incidence’, such as curves passing through given location/direction pairs, and find, for example, that twice-differentiable curves in R 2 may pass through at most O P (n 1/4) uniform random location/direction pairs. Idealized applications in image processing and perceptual psychophysics are described and several open mathematical questions are identified for the attention of the probability community.

D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\Omega(n\log n/\log\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log2 n) upper bound.

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes.

Crowder et al. (Oper. Res. 31 (1983) 803-834) conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special case is solvable in linear time.

We present new explicit lower bounds for some Ramsey numbers. All the graphs are cyclic and are on a prime number of vertices. We give theoretical motivation for searching for Ramsey graphs of prime order and provide additional computational evidence that primes tend to be better than composites.

For any voting rule on a policy space R^d with a finite number of voters, it is known that there is an instability dimension w which characterizes the rule: that is, if d >= w, then the core or voting equilibrium is unstable. On the other hand, with an infinite population represented by a continuous probability distribution, f, a core may exist as long as the required supra-majority, @a, exceeds some function of d. Caplin and Nalebuff, for example, have shown that if f is log concave then @a = 1 - (d/(d + 1))^d. This paper attempts to relate these two classes of results by considering the limiting behavior as the sample size, n, approaches infinity. We consider an @a(n)-rule of the form @a(n) = (n/2) + k(n), and obtain an upper bound @x(d,n,k(n)) on the probability that the origin is not a core point, in the case f satisfies a weak symmetry property. In particular, we show that if k(n) is of order nd log n, then @x approaches zero, so the origin is a core point with probability 1 in the limit. As corollary, we demonstrate that if the rule is of the form (1 - (1/e))n, then a core exists with probability 1 in the limit, as long as f is log-concave. The technique allows computation of the limiting probability of a core in terms of a parameter, known as the min-max value of distribution f, the dimension of the space, and the relative size of the required majority.

The popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction property with a limited number of terminals is essential to the linear time solution of problems on these graphs. A second useful property of these graphs is that decomposition is deterministic with respect to the series-parallel rules. This implies that the parse-tree of decomposition (which is required by the algorithms) can be determined in a straightforward manner by repeatedly applying the decomposition rules. Subject to retaining these properties, we examine how far the series-parallel graphs can be generalized. Corollaries of our results yield the deterministic decomposition of the series-parallel and Halin graph classes.

The planar Ramsey number PR ( k , l ) ( k , l ≥ 2) is the smallest integer n such that any planar graph on n vertices contains either a complete graph on k vertices or an independent set of size l . We find exact values of PR ( k , l ) for all k and l . Included is a proof of a 1976 conjecture due to Albertson, Bollobas, and Tucker that every triangle-free planar graph on n vertices contains an independent set of size ⌊ n /3⌋ + 1.

The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.

We conjecture a generalization of Dilworth’s theorem to direct products of partial orders. In particular, we conjecture that the largest “semiantichain” and the smallest “unichain covering” have the same size. We consider a special class of semiantichains and unichain coverings and determine when equality holds for them. This conjecture implies the existence of k-saturated partitions. A stronger conjecture, for which we also prove a special case, implies the Greene–Kleitman result on simultaneous k- and $(k + 1)$-saturated partitions.

For an arbitrary poset P, subposets {P i : 1≤i≤k} form a transitive basis of P if P is the transitive closure of their union. Let u be the minimum size of a covering of P by chains within posets of the basis, s the maximum size of a family of elements with no pair comparable in any basis poset, and a the maximum size of an antichain in P. Define a dense covering to be a collection D of chains within basis posets such that each element belongs to a chain in D within each basis poset and is the top of at least k-1 chains and the bottom of at least k-1 chains in D. Dense coverings generalize ordinary chain coverings of poset. Let d=min {|D|−(k−1)|P|}. For an arbitrary poset and transitive basis, a convenient network model for dense coverings yields the following: Theorem 1: d≥a, with equality iff P has a minimum chain decomposition in which every pair of consecutive elements on each chain are comparable in some basis poset. Theorem 2: u≥s≥d≥a. Theorem 3: s=d iff s=a. The most interesting special case is where the transitive basis expresses P as the product of two posets, in which case u and s measure the minimum and maximum sizes of unichain coverings and semiantichains.

3-SAT is NP-complete when restricted to instances where each variable appears in at most four clauses. When no variable appears in more than three clauses, 3-SAT is trivial and SAT is NPcomplete. When no variable appears in more than two clauses, SAT may be solved in linear time.