On the dimension to represent a graph by a unit distance graph

It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR ^2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR ^2d.     

A threshold for the size of random caps to cover a sphere

Consider a unit sphere on which are placed N random spherical caps of area 4p(N). We prove that if % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaa0aaaeaaca% qGSbGaaeyAaiaab2gaaaWaaeWaaeaacaWGWbWaaeWaaeaacaWGobaa% caGLOaGaayzkaaGaai4Taiaad6eacaGGVaGaaeiBaiaab+gacaqGNb% Gaaeiiaiaad6eaaiaawIcacaGLPaaacqGH8aapcaaIXaaaaa!454E!\[\overline {{\rm{lim}}} \left( {p\left( N \right)\cdotN/{\rm{log }}N} \right) < 1\], then the probability that the sphere is completely covered by N caps tends to 0 as N , and if % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaWaaaeaaca% qGSbGaaeyAaiaab2gaaaWaaeWaaeaacaWGWbWaaeWaaeaacaWGobaa% caGLOaGaayzkaaGaai4Taiaad6eacaGGVaGaaeiBaiaab+gacaqGNb% Gaaeiiaiaad6eaaiaawIcacaGLPaaacqGH+aGpcaaIXaaaaa!4551!\[\underline {{\rm{lim}}} \left( {p\left( N \right)\cdotN/{\rm{log }}N} \right) > 1\], then for any integer n>0 the probability that each point of the sphere is covered more than n times tends to 1 as N .     

Minimum concave cost production system: A further generalization of multi-echelon model

We will consider a concave minimization problem associated with a series production system in which raw material is processed inm consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during periodi, i = 1,,n, are known in advance. Our problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave.The origin of this model is the classical economic lot size problem of Wagner and Whitin and was extensively studied by Zangwill. This model is very important from the theoretical as well as practical point of view and this is one of the very rare instances in which polynomial time algorithm has been constructed for concave minimization problems.The purpose of this paper is to extend the model further to the situation in which time lag is associated with processing at each facility. We will propose an efficient O(n ⁴ m) algorithm for this class of problems.