Heights of simple games

We consider simple games which are constructed as iterated weighted majority games. It turns out that every proper simple game can be obtained in this way. The minimal number of iterations necessary to obtain a given game is called the height of this game. We investigate the behaviour ofh (n), the maximal height of a simple game withn players.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

The desirability relation of simple games

We prove some properties of simple games with a complete desirability relation, and investigate the relationships between the desirability of a simple game G and that of some simple games that are derived from G. We also provide an example of a proper simple game that has a complete and acyclic desirability relation but is not a weighted majority game.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Clique partitions of distance multigraphs

We consider the minimum number of cliques needed to partition the edge set of D(G), the distance multigraph of a simple graph G. Equivalently, we seek to minimize the number of elements needed to label the vertices of a simple graph G by sets so that the distance between two vertices equals the cardinality of the intersection of their labels. We use a fractional analogue of this parameter to find lower bounds for the distance multigraphs of various classes of graphs. Some of the bounds are shown to be exact.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Common behaviour of power indices

The variations ensuing in a weighted majority game are studied when a player increases his weight in prejudice of others or decreases in favor, or trades shares outside the game (in particular when an-person game becomes an (n+1)-person one). An invariant behaviour for different game values is found for all these cases. Possible applications to politics, shareholdings and large games are pointed out.     

Bounding partial sums of Fourier series in weighted L2-norms,with applications to matrix analysis

For integrable functions f defined on the interval [−π,π], we denote the partial sums of the corresponding Fourier series by S_n(f) (n=0,1,2,…). In this paper, we deal with the problem of bounding sup_n||S_n||, where ||·|| denotes an operator norm induced by a weighted L²-norm for functions f on [−π,π]. For weight functions w belonging to a class introduced by Helson and Szegö (Ann. Mat. Pura Appl. 51 (1960) 107), we present explicit upper bounds for sup_n||S_n|| in terms of w.The authors were led to the problem of deriving explicit upper bounds for sup_n||S_n||, by the need for such bounds in an analysis related to the Kreiss matrix theorem—a famous result in the fields of linear algebra and numerical analysis. Accordingly, the present paper highlights the relevance of bounds on sup_n||S_n|| to these fields.     

The spectral radius of graphs without paths and cycles of specified length

Let G be a graph with n vertices and μ(G) be the largest eigenvalue of the adjacency matrix of G. We study how large μ(G) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Harmonic morphisms from the compact semisimple Lie groups and their non-compact duals

In this paper we prove the local existence of complex-valued harmonic morphisms from any compact semisimple Lie group and their non-compact duals. These include all Riemannian symmetric spaces of types II and IV. We produce a variety of concrete harmonic morphisms from the classical compact simple Lie groups SO(n), SU(n), Sp(n) and globally defined solutions on their non-compact duals SO(n,C)/SO(n), SLn(C)/SU(n) and Sp(n,C)/Sp(n).     

Heights of representative systems

Representative systems are hierarchical aggregation schemes that are applicable in social choice theory, multiattribute decision making, and in the study of three-valued logics. For example, many procedures for voting on issues—including simple majority voting and weighted voting—can be characterized as representative system. Such systems also include procedures in which vote outcomes of constituencies are treated as votes in a higher level of an election system. The general form of a representative system consists of a “supreme council” which aggregates vote outcomes of secondary councils, which in turn aggregate vote outcomes of tertiary councils, and so forth.An n-variable representative system maps n-tuples of 1's, 0's and ?1's into {1,0,?1} through a nested hierarchy of sign functions. The height of a representative system is the fewest number of hierarchical levels that are needed to characterize the system. The height μ(n) of all n-variable representative systems is the largest height of such systems. It was shown previously that μ(n) ? n ? 1 for all positive integers n and that μ(n) = n ? 1 for n from 1 to 4 inclusive. The present paper proves that μ(5) = μ(6) = 4 and that μ(n) ? ?2 for all n ? 6. The height function μ is known to be unbounded.     

On the least size of a graph with a given degree set

The degree set of a finite simple graph G is the set of distinct degrees of vertices of G. A theorem of Kapoor et al. [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] asserts that the least order of a graph with a given degree set D is 1+max(D). We look at the analogous problem concerning the least size of a graph with a given degree set D. We determine the least size for the sets D when (i) |D|?3; (ii) D={1,2,…,n}; and (iii) every element in D is at least |D|. In addition, we give sharp upper and lower bounds in all cases.     

Hermite pseudospectral approximations. An error estimate

We find an error bound for the pseudospectral approximation of a function in terms of Hermite functions, hn(x)=e−x²Hn(x), in certain weighted Sobolev spaces. We use properties of Hermite polynomials, as well as an asymptotic expression for their largest zeroes to achieve the mentioned estimate.     

Forms of representation for simple games: Sizes,conversions and equivalences

Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Norm inequalities for vector functions

We study vector functions of Rn into itself, which are of the form x?g(|x|)x, where g:(0,∞)→(0,∞) is a continuous function and call these radial functions. In the case when g(t)=tc for some c∈R, we find upper bounds for the distance of image points under such a radial function. Some of our results refine recent results of L. Maligranda and S.S. Dragomir. In particular, we study quasiconformal mappings of this simple type and obtain norm inequalities for such mappings.     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model

LetV be a set inR ⁿ consisting of finitely many hyperplanes. The linear recognition problem given byV is to determine, using ternary comparisons of the form “f(x):0” wheref:R ⁿ →R is a linear function, whether a pointxεR _n is inV. We consider lower bounds on the number of comparisons whenV corresponds to some NP-complete problems. A technique is proposed for proving such bounds. If the tests “f(x):0” are restricted so thatf always defines some hyperplane inV, then some NP-complete problems are shown to have exponential lower bounds inn. Examples of larger classes of linear test functions are found such that the exponential lower bounds are still valid.     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.