The partition bargaining problem

Consider the problem of partitioning n items among d players where the utility of each player for bundles of items is additive; so, player r has utility for item i and the utility of that player for a bundle of items is the sum of the 's over the items i in his/her bundle. Each partition S of the items is then associated with a d-dimensional utility vector V^S whose coordinates are the utilities that the players assign to the bundles they get under S. Also, lotteries over partitions are associated with the corresponding expected utility vectors. We model the problem as a Nash bargaining game over the set of lotteries over partitions and provide methods for computing the corresponding Nash solution, to prescribed accuracy, with effort that is polynomial in n. In particular, we show that points in the pareto-optimal set of the corresponding bargaining set correspond to lotteries over partitions under which each item, with the possible exception of at most d(d-1)/2 items, is assigned in the same way.     

On a conjecture of Erd?s, Graham and Spencer, II

It is conjectured by Erd?s, Graham and Spencer that if 1≤a₁≤a₂≤?≤a_s are integers with , then this sum can be decomposed into n parts so that all partial sums are ≤1. This is not true for as shown by a₁=?=a_n−2=1, . In 1997 Sandor proved that Erd?s-Graham-Spencer conjecture is true for . Recently, Chen proved that the conjecture is true for . In this paper, we prove that Erd?s-Graham-Spencer conjecture is true for .     

Facet-inducing web and antiweb inequalities for the graph coloring polytope

For a graph G and its complement , we define the graph coloring polytope P(G) to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G. We show that for an antiweb in G the corresponding inequality is facet-inducing for P(G) if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.     

Connectivity preserving transformations for higher dimensional binary images

An N-dimensional digital binary image (I) is a function I:Z^N→{0,1}. I is connected if and only if its black pixels and white pixels are each (3^N−1)-connected. I is only connected if and only if its black pixels are (3^N−1)-connected. For a 3-D binary image, the respective connectivity models are and . A pair of (3^N−1)-neighboring opposite-valued pixels is called interchangeable in a N-D binary image I, if reversing their values preserves the original connectedness. We call such an interchange to be a (3^N−1)-local interchange. Under the above connectivity models, we show that given two binary images of n pixels/voxels each, we can transform one to the other using a sequence of (3^N−1)-local interchanges. The specific results are as follows. Any two -connected 3-dimensional images I and J each having n black voxels are transformable using a sequence of O((c₁+c₂)n²) 26-local interchanges. Here, c₁ and c₂ are the total number of 8-connected components in all 2-dimensional layers of I and J respectively. We also show bounds on connectivity under a different interchange model as proposed in [A. Dumitrescu, J. Pach, Pushing squares around, Graphs and Combinatorics 22 (1) (2006) 37-50]. Next, we show that any two simply connected images under the , connectivity model and each having n black voxels are transformable using a sequence of O(n²) 26-local interchanges. We generalize this result to show that any two , -connected N-dimensional simply connected images each having n black pixels are transformable using a sequence of O(Nn²)(3^N−1)-local interchanges, where N>1.     

On strong unimodality of multivariate discrete distributions

A discrete function f defined on Zⁿ is said to be logconcave if for , , . A more restrictive notion is strong unimodality. Following Barndorff-Nielsen [O. Barndorff-Nielsen, Unimodality and exponential families, Commun. Statist. 1 (1973) 189-216] a discrete function is called strongly unimodal if there exists a convex function such that  if . In this paper sufficient conditions that ensure the strong unimodality of a multivariate discrete distribution, are given. Examples of strongly unimodal multivariate discrete distributions are presented.     

On a convex operator for finite sets

Let S be a finite set with m elements in a real linear space and let J_S be a set of m intervals in R. We introduce a convex operator co(S,J_S) which generalizes the familiar concepts of the convex hull, , and the affine hull, , of S. We prove that each homothet of that is contained in can be obtained using this operator. A variety of convex subsets of with interesting combinatorial properties can also be obtained. For example, this operator can assign a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For two types of families J_S we give two different upper bounds for the number of vertices of the polytopes produced as co(S,J_S). Our motivation comes from a recent improvement of the well-known Gauss-Lucas theorem. It turns out that a particular convex set co(S,J_S) plays a central role in this improvement.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

Graphs, partitions and Fibonacci numbers

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2^n-1+5 have diameter ?4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ?4) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.     

Improved induced matchings in sparse graphs

An induced matching in a graph G=(V,E) is a matching M such that (V,M) is an induced subgraph of G. Clearly, among two vertices with the same neighbourhood (called twins) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj et al. [10] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least and that there are twinless planar graphs that do not contain an induced matching of size greater than . We improve both these bounds to , which is tight up to an additive constant. This implies that the problem of deciding whether a planar graph has an induced matching of size k has a kernel of size at most 28k. We also show for the first time that this problem is fixed parameter tractable for graphs of bounded arboricity.Kanj et al. also presented an algorithm which decides in -time whether an n-vertex planar graph contains an induced matching of size k. Our results improve the time complexity analysis of their algorithm. However, we also show a more efficient -time algorithm. Its main ingredient is a new, O^∗(4^l)-time algorithm for finding a maximum induced matching in a graph of branch width at most l.     

Large solutions to non-monotone semilinear elliptic systems

We present the existence of entire large positive radial solutions for the non-monotonic system Δu=p(|x|)g(v), Δv=q(|x|)f(u) on Rn where n?3. The functions f and g satisfy a Keller-Osserman type condition while nonnegative functions p and q are required to satisfy the decay conditions and . Further, p and q are such that min(p,q) does not have compact support.     

Two classes of edge domination in graphs

Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures.