Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Blister Patterns and Energy Minimization in Compressed Thin Films on Compliant Substrates

This paper is motivated by the complex blister patterns sometimes seen in thin elastic films on thick, compliant substrates. These patterns are often induced by an elastic misfit that compresses the film. Blistering permits the film to expand locally, reducing the elastic energy of the system. It is therefore natural to ask: what is the minimum elastic energy achievable by blistering on a fixed area fraction of the substrate? This is a variational problem involving both the elastic deformation of the film and substrate and the geometry of the blistered region. It involves three small parameters: the nondimensionalized thickness of the film, the compliance ratio of the film/substrate pair, and the mismatch strain. In formulating the problem, we use a small‐slope (Föppl–von Kármán) approximation for the elastic energy of the film, and a local approximation for the elastic energy of the substrate. For a one‐dimensional version of the problem, we obtain “matching” upper and lower bounds on the minimum energy, in the sense that both bounds have the same scaling behavior with respect to the small parameters. The upper bound is straightforward and familiar: it is achieved by periodic blistering on a specific length scale. The lower bound is more subtle, since it must be proved without any assumption on the geometry of the blistered region. For a two‐dimensional version of the problem, our results are less complete. Our upper and lower bounds only “match” in their scaling with respect to the nondimensionalized thickness, not in the dependence on the compliance ratio and the mismatch strain. The lower bound is an easy consequence of our one‐dimensional analysis. The upper bound considers a two‐dimensional lattice of blisters and uses ideas from the literature on the folding or “crumpling” of a confined elastic sheet. Our main two‐dimensional result is that in a certain parameter regime, the elastic energy of this lattice is significantly lower than that of a few large blisters. © 2015 Wiley Periodicals, Inc.     

A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

Experiments on solvingr-SAT random formulae have provided evidence of a satisfiability threshold phenomenon with respect to the ratio of the number of clauses to the number of variables of formulae. Presently, only the threshold of 2-SAT formulae has been proved to exist and has been computed to be equal to 1. For 3-SAT formulae and more generally forr-SAT formulae, lower and upper bounds of the threshold have been established. The best established bounds concern 3-SAT. For an observed threshold of about 4.25, the best lower bound is 3.003 and the best upper bound 4.76. In this paper we establish a general upper bound of the threshold forr-SAT formulae giving a value for 3-SAT of 4.64, significantly improving the previous best upper bound. For this we have defined a more restrictive structure than a satisfying truth assignment for characterizing the satisfiability of a SAT formula which we have called negatively prime solution (NPS). By merely applying the first moment method to negatively prime solutions of a randomr-SAT formula we obtain our bound.     

On binary linear <Emphasis Type="Italic">r</Emphasis>-identifying codes

A subspace C of the binary Hamming space F ⁿ of length n is called a linear r-identifying code if for all vectors of F ⁿ the intersections of C and closed r-radius neighbourhoods are nonempty and different. In this paper, we give lower bounds for such linear codes. For radius r =  2, we give some general constructions. We give many (optimal) constructions which were found by a computer search. New constructions improve some previously known upper bounds for r-identifying codes in the case where linearity is not assumed.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

Functional Quantization and Small Ball Probabilities for Gaussian Processes

Quantization consists in studying the L ^r -error induced by the approximation of a random vector X by a vector (quantized version) taking a finite number n of values. We investigate this problem for Gaussian random vectors in an infinite dimensional Banach space and in particular, for Gaussian processes. A precise link proved by Fehringer⁽⁴⁾ and Dereich et al. ⁽³⁾ relates lower and upper bounds for small ball probabilities with upper and lower bounds for the quantization error, respectively. We establish a complete relationship by showing that the same holds for the direction from the quantization error to small ball probabilities. This allows us to compute the exact rate of convergence to zero of the minimal L ^r -quantization error from logarithmic small ball asymptotics and vice versa.     

Extremal k-edge-hamiltonian hypergraphs

An r-uniform hypergraph is k-edge-hamiltonian iff it still contains a hamiltonian-chain after deleting any k edges of the hypergraph. What is the minimum number of edges in such a hypergraph? We give lower and upper bounds for this question for several values of r and k.     

On complete caps in the projective geometries over\mathbb{F}_3

It is known that the largest size of cap in PG(5, 3) is 56, but very little is known about complete caps of smaller size; the previously known complete caps withk < 56 all had size at most 43. In this paper we construct complete 48-caps and show that any 53-cap is extendable to a 56-cap. From this last result, we derive new upper bounds on the largest size of cap in PG(r, 3) forr 6. The results are obtained from a blend of geometric and coding theoretic techniques.     

The conjugacy vector of ap-group of maximal class

We find the conjugacy vector, i.e., we determine the number of conjugacy classes which compose the sets of the elements with centralizers of equal order, for several general families ofp-groups of maximal class which include those of order up top ⁹. As a consequence, we obtain the number of conjugacy classes,r(G), for the groups in these families. Also, we provide upper and lower bounds forr(G) and characterize when they are attained. Examples are given showing that the bounds are actually attained. This work has been supported by DGICYT grant PB91-0446 and by the University of the Basque Country.     

Optimally small sumsets in groups IV. Counting multiplicities and the <Emphasis Type="Italic">λ</Emphasis><Subscript><Emphasis Type="Italic">G</Emphasis></Subscript> functions

We continue our investigation on how small a sumset can be in a given abelian group. Here small takes into account not only the size of the sumset itself but also the number of elements which are repeated at least twice. A function λ _G (r, s) computing the minimal size (in this sense) of the sum of two sets with respective cardinalities r and s is introduced. (Lower and upper) bounds are obtained, which coincide in most cases. While upper bounds are obtained by constructions, lower bounds follow in particular from the use of a recent theorem by Grynkiewicz.     

Symmetric Subsets and Colorings of Connected Compact Groups

We find upper and lower bounds for the Haar measure of a monochromatic symmetric subset, which can be found in every measurable r-coloring of a connected compact group.     

Concavity and efficient points of discrete distributions in probabilistic programming

We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems with discrete random variables. The results are illustrated with numerical examples. Received: October 1998 / Accepted: June 2000?Published online October 18, 2000     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

Local Minima and Convergence in Low-Rank Semidefinite Programming

The low-rank semidefinite programming problem LRSDP_r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP_r via the nonconvex change of variables X=RR^T. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.     

Connected Covering Numbers

A connected covering is a design system in which the corresponding block graph is connected. The minimum size of such coverings are called connected coverings numbers. In this paper, we present various formulas and bounds for several parameter settings for these numbers. We also investigate results in connection with Turán systems. Finally, a new general upper bound, improving an earlier result, is given. The latter is used to improve upper bounds on a question concerning oriented matroid due to Las Vergnas.     

The multicovering radius problem for some types of discrete structures

The covering radius problem is a question in coding theory concerned with finding the minimum radius r such that, given a code that is a subset of an underlying metric space, balls of radius r over its code words cover the entire metric space. Klapper (IEEE Trans. Inform. Theory 43:1372–1377, 1997) introduced a code parameter, called the multicovering radius, which is a generalization of the covering radius. In this paper, we introduce an analogue of the multicovering radius for permutation codes (Des. Codes Cryptogr. 41:79–86, cf. 2006) and for codes of perfect matchings (cf. 2012). We apply probabilistic tools to give some lower bounds on the multicovering radii of these codes. In the process of obtaining these results, we also correct an error in the proof of the lower bound of the covering radius that appeared in (Des. Codes Cryptogr. 41:79–86, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.     

Searching for an edge in a graph

Consider the problem of determining the endpoints of an unknown edge x in a given graph G by asking questions of the form “Is vertex v an endpoint of edge e in G?”. Sharp upper and lower bounds are derived, and it is shown that determining the minimum number of questions in NP-complete.     

On the optimal control of arrivals to a single queue with arbitrary feedback delay

We consider a problem of admission control to a single queue in discrete time. The controller has access to k step old queue lengths only, where k can be arbitrary. The problem is motivated, in particular, by recent advances in high-speed networking where information delays have become prominent. We formulate the problem in the framework of Completely Observable Controlled Markov Chains, in terms of a multi-dimensional state variable. Exploiting the structure of the problem, we show that under appropriate conditions, the multi-dimensional Dynamic Programming Equation (DPE) can be reduced to a unidimensional one. We then provide simple computable upper and lower bounds to the optimal value function corresponding to the reduced unidimensional DPE. These upper and lower bounds, along with a certain relationship among the parameters of the problem, enable us to deduce partially the structural features of the optimal policy. Our approach enables us to recover simply, in part, the recent results of Altman and Stidham, who have shown that a multiple-threshold-type policy is optimal for this problem. Further, under the same relationship among the parameters of the problem, we provide easily computable upper bounds to the multiple thresholds and show the existence of simple relationships among these upper bounds. These relationships allow us to gain very useful insights into the nature of the optimal policy. In particular, the insights obtained are of great importance for the problem of actually computing an optimal policy because they reduce the search space enormously. This revised version was published online in June 2006 with corrections to the Cover Date.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.