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.