Energy Bounds for a Compressed Elastic Film on a Substrate

We study pattern formation in a compressed elastic film which delaminates from a substrate. Our key tool is the determination of rigorous upper and lower bounds on the minimum value of a suitable energy functional. The energy consists of two parts, describing the two main physical effects. The first part represents the elastic energy of the film, which is approximated using the von Kármán plate theory. The second part represents the fracture or delamination energy, which is approximated using the Griffith model of fracture. A simpler model containing the first term alone was previously studied with similar methods by several authors, assuming that the delaminated region is fixed. We include the fracture term, transforming the elastic minimisation into a free boundary problem, and opening the way for patterns which result from the interplay of elasticity and delamination. After rescaling, the energy depends on only two parameters: the rescaled film thickness, \({\sigma }\), and a measure of the bonding strength between the film and substrate, \({\gamma }\). We prove upper bounds on the minimum energy of the form \({\sigma }^a {\gamma }^b\) and find that there are four different parameter regimes corresponding to different values of a and b and to different folding patterns of the film. In some cases, the upper bounds are attained by self-similar folding patterns as observed in experiments. Moreover, for two of the four parameter regimes we prove matching, optimal lower bounds.     

Wrinkles as the Result of Compressive Stresses in an Annular Thin Film

It is well‐known that an elastic sheet loaded in tension will wrinkle and that the length scale of the wrinkles tends to 0 with vanishing thickness of the sheet [Cerda and Mahadevan, Phys. Rev. Lett. 90, 074302 (2003)]. We give the first mathematically rigorous analysis of such a problem. Since our methods require an explicit understanding of the underlying (convex) relaxed problem, we focus on the wrinkling of an annular sheet loaded in the radial direction [Davidovitch et al., Proc. Natl. Acad. Sci. 108 (2011), 18227]. Our main achievement is identification of the scaling law of the minimum energy as the thickness of the sheet tends to 0. This requires proving an upper bound and a lower bound that scale the same way. We prove both bounds first in a simplified Kirchhoff‐Love setting and then in the nonlinear three‐dimensional setting. To obtain the optimal upper bound, we need to adjust a naive construction (one family of wrinkles superimposed on a planar deformation) by introducing a cascade of wrinkles. The lower bound is more subtle, since it must be ansatz‐free. © 2014 Wiley Periodicals, Inc.     

Coarsening of Folds in Hanging Drapes

We consider the elastic energy of a hanging drape—a thin elastic sheet, pulled down by the force of gravity, with fine‐scale folding at the top that achieves approximately uniform confinement. This example of energy‐driven pattern formation in a thin elastic sheet is of particular interest because the length scale of folding varies with height. We focus on how the minimum elastic energy depends on the physical parameters. As the sheet thickness vanishes, the limiting energy is due to the gravitational force and is relatively easy to understand. Our main accomplishment is to identify the “scaling law” of the correction due to positive thickness. We do this by (i) proving an upper bound, by considering the energies of several constructions and taking the best; and (ii) proving an ansatz‐free lower bound, which agrees with the upper bound up to a parameter‐independent prefactor. The coarsening of folds in hanging drapes has also been considered in the recent physics literature, by using a self‐similar construction whose basic cell has been called a “wrinklon.” Our results complement and extend that work by showing that self‐similar coarsening achieves the optimal scaling law in a certain parameter regime, and by showing that other constructions (involving lateral spreading of the sheet) do better in other regions of parameter space. Our analysis uses a geometrically linear Föppl‐von Kármán model for the elastic energy, and is restricted to the case when Poisson's ratio is 0. © 2016 Wiley Periodicals, Inc.     

Anisotropic a posteriori error estimation for the mixed discontinuous Galerkin approximation of the Stokes problem

This article presents a posteriori error estimates for the mixed discontinuous Galerkin approximation of the stationary Stokes problem. We consider anisotropic finite element discretizations, i.e., elements with very large aspect ratio. Our analysis covers two‐ and three‐dimensional domains. Lower and upper error bounds are proved with minimal assumptions on the meshes. The lower error bound is uniform with respect to the mesh anisotropy. The upper error bound depends on a proper alignment of the anisotropy of the mesh, which is a common feature of anisotropic error estimation. In the special case of isotropic meshes, the results simplify, and upper and lower error bounds hold unconditionally. The numerical experiments confirm the theoretical predictions and show the usefulness of the anisotropic error estimator. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Axial Compression of a Thin Elastic Cylinder: Bounds on the Minimum Energy Scaling Law

We consider the axial compression of a thin elastic cylinder placed about a hard cylindrical core. Treating the core as an obstacle, we prove upper and lower bounds on the minimum energy of the cylinder that depend on its relative thickness and the magnitude of axial compression. We focus exclusively on the setting where the radius of the core is greater than or equal to the natural radius of the cylinder. We consider two cases: the “large mandrel” case, where the radius of the core exceeds that of the cylinder, and the “neutral mandrel” case, where the radii of the core and cylinder are the same. In the large mandrel case, our upper and lower bounds match in their scaling with respect to thickness, compression, and the magnitude of pre‐strain induced by the core. We construct three types of axisymmetric wrinkling patterns whose energy scales as the minimum in different parameter regimes, corresponding to the presence of many wrinkles, few wrinkles, or no wrinkles at all. In the neutral mandrel case, our upper and lower bounds match in a certain regime in which the compression is small as compared to the thickness; in this regime, the minimum energy scales as that of the unbuckled configuration. We achieve these results for both the von Kármán–Donnell model and a geometrically nonlinear model of elasticity. © 2017 Wiley Periodicals, Inc.     

Efficient algorithms for three‐dimensional axial and planar random assignment problems

Beautiful formulas are known for the expected cost of random two‐dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP‐hard. For 3‐dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear‐time algorithm that, with high probability, finds a solution of cost O(n^–1+o(1)). For 3‐dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching‐based algorithm that with high probability returns a solution with cost O(n log n). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 160–196, 2015     

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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.     

Optimal Fine‐Scale Structures in Compliance Minimization for a Shear Load

We return to a classic problem of structural optimization whose solution requires microstructure. It is well‐known that perimeter penalization assures the existence of an optimal design. We are interested in the regime where the perimeter penalization is weak; i.e., in the effect of perimeter as a selection mechanism in structural optimization. To explore this topic in a simple yet challenging example, we focus on a two‐dimensional elastic shape optimization problem involving the optimal removal of material from a rectangular region loaded in shear. We consider the minimization of a weighted sum of volume, perimeter, and compliance (i.e., the work done by the load), focusing on the behavior as the weight ɛ of the perimeter term tends to 0. Our main result concerns the scaling of the optimal value with respect to ɛ. Our analysis combines an upper bound and a lower bound. The upper bound is proved by finding a near‐optimal structure, which resembles a rank‐2 laminate except that the approximate interfaces are replaced by branching constructions. The lower bound, which shows that no other microstructure can be much better, uses arguments based on the Hashin‐Shtrikman variational principle. The regime being considered here is particularly difficult to explore numerically due to the intrinsic nonconvexity of structural optimization and the spatial complexity of the optimal structures. While perimeter has been considered as a selection mechanism in other problems involving microstructure, the example considered here is novel because optimality seems to require the use of two well‐separated length scales.© 2016 Wiley Periodicals, Inc.     

Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

Ground state energy scaling laws during the onset and destruction of the intermediate state in a type I superconductor

The intermediate state of a type I superconductor is a classical example of energy‐driven pattern formation, first studied by Landau in 1937. Three of us recently derived five different rigorous upper bounds for the ground‐state energy, corresponding to different microstructural patterns, but only one of them was complemented by a lower bound with the same scaling [Choksi, Kohn, and Otto, J. Nonlinear Sci. 14 (2004), 119–171]. This paper completes the picture by providing matching lower bounds for the remaining four regimes, thereby proving that exactly those five different regimes are traversed with an increasing magnetic field. © 2007 Wiley Periodicals, Inc.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences

We present a general approach to the problem of determining tight asymptotic lower bounds for generalized central moments of the optimal alignment score of two independent sequences of i.i.d. random variables. At first, these are obtained under a main assumption for which sufficient conditions are provided. When the main assumption fails, we nevertheless develop a “uniform approximation” method leading to asymptotic lower bounds. Our general results are then applied to the length of the longest common subsequences of binary strings, in which case asymptotic lower bounds are obtained for the moments and the exponential moments of the optimal score. As a by-product, a local upper bound on the rate function associated with the length of the longest common subsequences of two binary strings is also obtained.     

Efficient computation of sparse structures

Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault‐tolerance or load‐balance properties. We propose and study “low‐average degree” or “sparse” versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 322–344, 2016     

The lower bounds of life span of classical solutions to one‐dimensional initial‐Neumann boundary value problems for general quasilinear wave equations

In this paper, we will study the lower bounds of the life span (the maximal existence time) of solutions to the initial‐boundary value problems with small initial data and zero Neumann boundary data on exterior domain for one‐dimensional general quasilinear wave equations u_tt?u_xx=b(u,Du)u_xx+F(u,Du). Our lower bounds of the life span of solutions in the general case and special case are shorter than that of the initial‐Dirichlet boundary value problem for one‐dimensional general quasilinear wave equations. We clarify that although the lower bounds in this paper are same as that in the case of Robin boundary conditions obtained in the earlier paper, however, the results in this paper are not the trivial generalization of that in the case of Robin boundary conditions because the fundamental Lemmas 2.4, 2.5, 2.6, and 2.7, that is, the priori estimates of solutions to initial‐boundary value problems with Neumann boundary conditions, are established differently, and then the specific estimates in this paper are different from that in the case of Robin boundary conditions. Another motivation for the author to write this paper is to show that the well‐posedness of problem 1.1 is the essential precondition of studying the lower bounds of life span of classical solutions to initial‐boundary value problems for general quasilinear wave equations. The lower bound estimates of life span of classical solutions to initial‐boundary value problems is consistent with the actual physical meaning. Finally, we obtain the sharpness on the lower bound of the life span 1.8 in the general case and 1.10 in the special case. Copyright © 2015 John Wiley & Sons, Ltd.     

A reduced theory for thin‐film micromagnetics

Micromagnetics is a nonlocal, nonconvex variational problem. Its minimizer represents the ground‐state magnetization pattern of a ferromagnetic body under a specified external field. This paper identifies a physically relevant thin‐film limit and shows that the limiting behavior is described by a certain “reduced” variational problem. Our main result is the Γ‐convergence of suitably scaled three‐dimensional micromagnetic problems to a two‐dimensional reduced problem; this implies, in particular, convergence of minimizers for any value of the external field. The reduced problem is degenerate but convex; as a result, it determines some (but not all) features of the ground‐state magnetization pattern in the associated thin‐film limit. © 2002 Wiley Periodicals, Inc.     

Obtaining upper bounds of heat kernels from lower bounds

We show that a near‐diagonal lower bound of the heat kernel of a Dirichlet form on a metric measure space with a regular measure implies an on‐diagonal upper bound. If in addition the Dirichlet form is local and regular, then we obtain a full off‐diagonal upper bound of the heat kernel provided the Dirichlet heat kernel on any ball satisfies a near‐diagonal lower estimate. This reveals a new phenomenon in the relationship between the lower and upper bounds of the heat kernel. © 2007 Wiley Periodicals, Inc.