On the uniform edge-partition of a tree

We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

Oberwolfach rectangular table negotiation problem

We completely solve certain case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Let H(k,3) be a bipartite graph with bipartition X={x₁,x₂,…,x_k},Y={y₁,y₂,…,y_k} and edges x₁y₁,x₁y₂,x_ky_k−1,x_ky_k, and x_iy_i−1,x_iy_i,x_iy_i+1 for i=2,3,…,k−1. We completely characterize all complete bipartite graphs K_n,n that can be factorized into factors isomorphic to G=mH(k,3), where k is odd and mH(k,3) is the graph consisting of m disjoint copies of H(k,3).     

Unavoidable patterns

Let Fk denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollobás conjectured that for every ?>0 and positive integer k there is n(k,?) such that every 2-edge-coloring of the complete graph of order n?n(k,?) which has at least edges in each color contains a member of Fk. This conjecture was proved by Cutler and Montágh, who showed that n(k,?)<⁴k/?. We give a much simpler proof of this conjecture which in addition shows that n(k,?)<?−ck for some constant c. This bound is tight up to the constant factor in the exponent for all k and ?. We also discuss similar results for tournaments and hypergraphs.     

On the isoperimetric problem with respect to a mixed Euclidean–Gaussian density

The isoperimetric problem with respect to the product-type density on the Euclidean space Rh×Rk is studied. In particular, existence, symmetry and regularity of minimizers is proved. In the special case k=1, also the shape of all the minimizers is derived. Finally, a conjecture about the minimality of large cylinders in the case k>1 is formulated.     

On the complexity of the k-customer vehicle routing problem

We investigate the complexity of the k-CUSTOMER VEHICLE ROUTING PROBLEM: Given an edge weighted graph, the problem requires to compute a minimum weight set of cyclic routes such that each contains a distinguished depot vertex and at most other k customer vertices, and every customer belongs to exactly one route.     

Hessian Measures III

In this paper, we continue previous investigations into the theory of Hessian measures. We extend our weak continuity result to the case of mixed k-Hessian measures associated with k-tuples of k-convex functions, on domains in Euclidean n-space, k=1,2,…,n. Applications are given to capacity, quasicontinuity, and the Dirichlet problem, with inhomogeneous terms, continuous with respect to capacity or combinations of Dirac measures.     

Movement of hot spots on the exterior domain of a ball under the Neumann boundary condition

We consider the Cauchy-Neumann problem of the heat equation in the exterior domain of a ball in R^N, and study the movement of hot spots of the solution as t→∞.     

The two-dimensional Prouhet-Tarry-Escott problem

In this paper we generalize the Prouhet-Tarry-Escott problem (PTE) to any dimension. The one-dimensional PTE problem is the classical PTE problem. We concentrate on the two-dimensional version which asks, given parameters n,k∈N, for two different multi-sets {(x₁,y₁),…,(xn,yn)}, of points from Z² such that for all d,j∈{0,…,k} with j?d. We present parametric solutions for n∈{2,3,4,6} with optimal size, i.e., with k=n−1. We show that these solutions come from convex 2n-gons with all vertices in Z² such that every line parallel to a side contains an even number of vertices and prove that such convex 2n-gons do not exist for other values of n. Furthermore we show that solutions to the two-dimensional PTE problem yield solutions to the one-dimensional PTE problem. Finally, we address the PTE problem over the Gaussian integers.     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).     

On k-summability of formal solutions for a class of partial differential operators with time dependent coefficients

We study the k-summability of divergent formal solutions for the Cauchy problem of a certain class of linear partial differential operators with time dependent coefficients. The problem is reduced to a k-summability property of formal solutions for a linear similar ordinary differential equation associated with the Cauchy problem.     

The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables Xk and real numbers ak, determine the probability p that the sum k_∑akXk lies near some number v. For arbitrary coefficients ak of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

Graphs of order two less than the Moore bound

The problem of determining the largest order n_d,k of a graph of maximum degree at most d and diameter at most k is well known as the degree/diameter problem. It is known that n_d,k?M_d,k where M_d,k is the Moore bound. For d=4, the current best upper bound for n_4,k is M_4,k-1. In this paper we study properties of graphs of order M_d,k-2 and we give a new upper bound for n_4,k for k?3.     

Variational formula and overdetermined problem for the principle eigenvalue of k-Hessian operator

We first deduce the first variational formula and some overdetermined problems for the principle eigenvalue of the k-Hessian operator, and then prove Serrin type symmetry result for our overdetermined problems.     

ESTIMATES ON EIGENVALUES FOR THE BIHARMONIC OPERATOR ON A BOUNDED DOMAIN IN H~n（-1）

In this paper, we consider eigenvalues of the Dirichlet biharmonic operator on a bounded domain in a hyperbolic space. We obtain universal bounds on the (k + 1)th eigenvalue in terms of the first kth eigenvalues independent of the domains.     

A uniqueness theorem for indefinite Sturm-Liouville operators

In this paper, we discuss the inverse problem for indefinite Sturm-Liouville operators on the finite interval [a, b]. For a fixed index n(n = 0, 1, 2, ··· ), given the weight function ω(x), we will show that the spectral sets {λ n (q, h a , h k )} +∞ k=1 and {λ-n (q, h b , h k )} +∞ k=1 for distinct h k are sufficient to determine the potential q(x) on the finite interval [a, b] and coefficients h a and h b of the boundary conditions.     

Strategic disclosure of random variables

We consider a game G_n played by two players. There are n independent random variables Z₁, … , Z_n, each of which is uniformly distributed on [0,1]. Both players know n, the independence and the distribution of these random variables, but only player 1 knows the vector of realizations z ? (z₁, … , z_n) of them. Player 1 begins by choosing an order _zk1,…,_zkn$z_{k_1}\text{,}\dots \text{,}{z}_{k_n}$ of the realizations. Player 2, who does not know the realizations, faces a stopping problem. At period 1, player 2 learns _zk1$z_{k_1}$. If player 2 accepts, then player 1 pays _zk1$z_{k_1}$ euros to player 2 and play ends. Otherwise, if player 2 rejects, play continues similarly at period 2 with player 1 offering _zk2$z_{k_2}$ euros to player 2. Play continues until player 2 accepts an offer. If player 2 has rejected n − 1 times, player 2 has to accept the last offer at period n. This model extends Moser’s (1956) problem, which assumes a non-strategic player 1.     

Planar graphs without adjacent cycles of length at most seven are 3-colorable

We prove that every planar graph in which no i-cycle is adjacent to a j-cycle whenever 3≤i≤j≤7 is 3-colorable and pose some related problems on the 3-colorability of planar graphs.